前言
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的
指针链接次序实现的 。链表的结构总共有8种，我们这里来进行单链表的增删查改实现
对单链表的理解
单链表就像是一辆火车，一个节点一个节点相链接，当获得了头结点的地址后，便可通过单链表特有的结构体找到接下来所链接的所有节点。
下面请看源码，源码下面有四个相关问题及相应解答
若要批评建议请不吝评论，不懂可以私聊我
头文件
// slist.h typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode; // 动态申请一个节点 SListNode* BuySListNode(SLTDateType x); // 单链表打印 void SListPrint(SListNode* plist); // 单链表尾插 void SListPushBack(SListNode** pplist, SLTDateType x); // 单链表的头插 void SListPushFront(SListNode** pplist, SLTDateType x); // 单链表的尾删 void SListPopBack(SListNode** pplist); // 单链表头删 void SListPopFront(SListNode** pplist); // 单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x); // 单链表在pos位置之后插入x // 为什么不在pos位置之前插入？ void SListInsertAfter(SListNode* pos, SLTDateType x); // 单链表删除pos位置之后的值 // 为什么不删除pos位置？ void SListEraseAfter(SListNode* pos); // 单链表的销毁 void SListDestroy(SList* plist);
源代码
// slist.c #include "SList.h" //动态申请节点 SListNode* BuySListNode(SLTDateType x) { SListNode* node = (SListNode*)malloc(sizeof(SListNode)); // 开辟内存 node->data = x; node->next = NULL; return node; } //打印输出 void SListPrint(SListNode* plist) { SListNode* cur = plist; // 利用cur进行遍历，对*plist不修改 while (cur) //while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; //遍历 } printf("NULL\n"); } //尾插 void SListPushBack(SListNode** pplist, SLTDateType x) // 要实现对指针*pplist进行修改，就要传入*pplist的地址，即双指针 { SListNode* newnode = BuySListNode(x); //动态申请节点 if (*pplist == NULL) //先判断链表是否为空 { *pplist = newnode; } else { SListNode* tail = *pplist; //利用tail对链表进行遍历 while (tail->next != NULL) //当tail->next为空即tail已指向链表尾部 { tail = tail->next; } tail->next = newnode; } } //尾删 void SListPopBack(SListNode** pplist) //同上双指针的作用 { SListNode* prev = NULL; //prev作用是对tail指向地址进行保存，从而进行尾删 SListNode* tail = *pplist; // 1.空或只有一个节点 // 2.两个及以上的节点 if (tail == NULL || tail->next == NULL) { free(tail); *pplist = NULL; } else { while (tail->next) { prev = tail; tail = tail->next; } free(tail); //释放尾部节点空间 tail = NULL; prev->next = NULL; //对新尾部节点next置空 } } // 头插 void SListPushFront(SListNode** pplist, SLTDateType x) { assert(pplist); //断言pplist，若是空指针程序直接结束 // 1.空 // 2.非空 SListNode* newnode = BuySListNode(x); //申请动态节点 if (*pplist == NULL) //两种情况 { *pplist = newnode; } else { newnode->next = *pplist; //头插实现 *pplist = newnode; //更新头指针pplist指向新地址 } } //头删 void SListPopFront(SListNode** pplist) { //三种情况 // 1.空 // 2.一个 // 3.两个及以上 SListNode* first = *pplist; if (first == NULL) //若为空 { return; } else if (first->next == NULL) //只有一个节点 { free(first); *pplist = NULL; } else //两个及以上 { SListNode* next = first->next; free(first); *pplist = next; } } //查找 SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* cur = plist; while (cur) //当cur指针为空时，即已遍历完最后一个 { if (cur->data == x) return cur; cur = cur->next; } return NULL; } //单链表在pos位置之后插入x //若要实现pos位置之前插入x，需要遍历找到pos之前节点地址，才能进行链接 void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos);//断言pos是否为空指针 SListNode* next = pos->next; //对pos之后节点地址进行保存，便于后续链接 // pos newnode next SListNode* newnode = BuySListNode(x); pos->next = newnode; //进行链接 newnode->next = next; } // 删除pos位置之后节点 //要实现删除pos节点，同样需要找到上一个节点进行链接，这是单链表的局限性，而双向循环链表则可以很方便的进行删除和链接 void SListEraseAfter(SListNode* pos) { assert(pos); //断言pos指针 //对pos之后 pos->next->next 进行保存，便于后续删除pos位置后节点和pos节点进行链接 SListNode* next = pos->next; if (next != NULL) { SListNode* nextnext = next->next; free(next); pos->next = nextnext; //链接 } }
为什么有的要asser断言指针变量？
答：防止传入空指针而程序内容进行修改，若为空指针则直接程序结束
为什么头删尾删头插尾插函数要传入双指针？
答：要对指针变量而不是指针所指向的结构体或说内存空间进行修改，就要传入双指针，指向指针的指针对指针变量plist进行修改
为什么不在pos位置之前插入？
答：若要实现pos位置之前插入x，需要遍历找到pos之前节点地址，才能进行链接。
为什么不删除pos位置？
要实现删除pos节点，同样需要找到上一个节点进行链接，这是单链表的局限性，而双向循环链表则可以很方便的进行删除和链接。
本节完
