五、功能的实现
1）打印单链表
//打印 单链表 void SLTPrint(SLTNode* phead);
void SLTPrint(SLTNode* phead) { SLTNode* cur = phead;//① while (cur != NULL)//② { printf("%d -> ",cur->data); cur = cur->next;//③ } printf("NULL\n"); }
① 这里也可以直接用phead进行循环，但是像这样创建一个 “当前节点” （cur源自单词current）会比较“美观”。（But 如果这个函数内部后面还需要用头节点的话就不能直接用phead，否则会找不到头）
② 控制结束的条件
③ 遍历
2）创建新节点
链表的结点：按需分配，随用随创
链表的头插、尾插（只要是插入）都需要创建一个新节点，然后插到对应位置。所以我们可以直接把“创建新节点”封装成一个函数，以便后面直接调用：👇
SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//① if(newnode == NULL)//② { perror("malloc newnode fail: "); return; } //③给新节点赋值 newnode->x; newnode->next = NULL; return newnode;//别忘了返回newnode }
①动态开辟一个新节点，.h头文件里要包含 <stdlib.h>
②判断开辟是否成功，如果不成功则输出错误并返回
③给新节点的数据域赋值，指针域赋为空：NULL，这样做的好处是： 不需要最后对链表尾结点的指针域置空。
3）尾插
在链表尾部插入一个节点
先看这段代码：
void SLTPushBack(SLTNode** pphead, SLTDataType x); { SLTNode* newnode = BuySLTNode(x); SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; }
上面这段代码的前提是，我们已经假定这个链表有>=1个节点，但是如果*pphead为空呢？
如果为空，则只执行：
SLTNode* newnode = BuySLTNode(x); SLTNode*tail = *pphead;
初始化：SLTNode* phead = NULL;
传参： SLTPushBack(&phead, x);）
当phead为NULL时，也就不存在tail->next了
所以切记要先判断*pphead是否为空：
void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; //找原链表的尾结点 while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
4）尾删
尾删比较麻烦，因为要判断链表是否为空以及分情况讨论结点个数。
先看这段代码：
void SLTPopBack(SLTNode** pphead) { assert(pphead && *pphead);//① SLTNode* tail, * tailpre;//② tail = *pphead->next; tailpre = *pphead; while (tail->next) { tail = tail->next; tailpre = tailpre->next; } free(tail);//③ tailpre->next = NULL;//④ }
①pphead（二级指针）和*pphead绝对不可以为空，最好断言一下
②定义tail和tail前一个结点tailpre，目的是释放tail后，直接得到新的尾结点，方便置空
③没必要再把tail置空：tail = NULL;因为tail是局部变量，函数结束就自动销毁了
④释放后，新的尾结点的next置空
看似没什么毛病·······
但是，上面没有考虑只有一个结点的情况！！
⚡如果只有一个结点， tail = *pphead->next;后，tail为NULL，下面的执行就出大问题了
解决办法是判断一下：
void SLTPopBack(SLTNode** pphead) { assert(pphead && *pphead); if ((*pphead)->next == NULL)//只有一个结点 { free(*pphead); *pphead = NULL; } else// >=2个结点 { SLTNode* tail, * tailpre; tail = *pphead->next; tailpre = *pphead; while (tail->next) { tail = tail->next; tailpre = tailpre->next; } free(tail); tailpre->next = NULL; } }
5）头插
按照尾插的路子，可能会这样写：
void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySLTNode(x); if (*pphead == NULL) { *pphead = newnode; } else { newnode->next = *pphead; *pphead = newnode; } }
当然没有错，但是仔细想一想，其实没有必要判断*pphead是否为空，因为即使*pphead为空，执行else部分依然没毛病！
化简为：
void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySLTNode(x); newnode->next = *pphead; *pphead = newnode; }
6）头删
头删相比较尾删很简单，因为不需要像尾删一样找tail前一个结点。
头删可以直接删：
void SLPopFront(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* next = (*pphead)->next;//临时存一下第二个元素的结点 free(*pphead); *pphead = next; }
7）查找
查找链表中的某个元素，只需遍历一遍链表。返回data == 要查找的元素第一次出现的节点的地址；如果链表中没有要查找的元素，返回NULL。
<注意，空链表也可以查找，返回NULL即可>↓
SLTNode* SLFind(SLTNode* phead, SLDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) return cur; cur = cur->next; } return NULL; }
8）删除
分两种情况：链表只有一个节点、链表有多个节点。
1、只有一个节点：如果*pphead == pos，相当于头删，直接调用前面的函数即可。
2、有多个节点：遍历链表，直到找到地址为pos的结点，按照尾删的思路，删除即可。
void SLErase(SLTNode** pphead, SLTNode* pos) { assert(pphead && *pphead && pos);//都不能为空 if (*pphead == pos) { SLPopFront(pphead); } else { SLTNode* cur = *pphead; while (cur->next != pos) { cur = cur->next; } SLTNode* next = cur->next->next; cur->next = next; free(pos);//一定要free } }
9）插入结点
在pos前插入：
void SLInsert(SLTNode** pphead, SLTNode* pos, SLDataType x) { assert(pphead && pos); if (pos == *pphead) { SLPushFront(pphead, x); } else { SLTNode* cur = *pphead; while (cur->next != pos) { cur = cur->next; } SLTNode* insnode = BuyNode(x); cur->next = insnode; insnode->next = pos; } }
10）销毁
对于销毁链表，如果只free掉 *pphead行么？
当然不行！！
因为单链表由一个一个的结点连接起来的。如果只free(*pphead)，头结点是释放了，但是后面的节点没被释放，还占用着空间但是已经找不到他们的地址了。
所以应该逐个释放👇
void SLDestroy(ListNode** pphead) { ListNode* cur = *pphead; while (cur) { ListNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; //最后别忘了置空 }
销毁完后 最好把*pphead 置空，防止销毁链表后对链表误操作而导致的野指针问题。
