数据结构 - 链表 (三)

这篇博客完成单链表的最后部分，包括单链表的查找，任意位置插入删除数据，以及动态内存的释放。

1. 单链表的查找

单链表的结构如下图所示，我们查找数据只需将链表遍历一遍是否有需要查找的数据，同时也要考虑链表初始为空的情况。

SLTNode* STFind(SLTNode* phead, SLTDataType x){SLTNode* cur = phead;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}

 2. 在 pos 位置 之前/之后 插入数据

 在此处我们考虑两种情况，一是 pos 位置处即为头结点位置，以及 pos 位置是中间结点的位置，如下图所示：

第一种情况我们只需调用之前的头部插入数据的函数即可 ，第二种情况我们需要遍历到 pos 前一个位置，在此处插入结点即可。

void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead);assert(pos);if (*pphead == pos){SLPushFront(pphead, x); //调用头插函数}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->next = pos;}}

 而则在 pos 位置之后插入数据则十分简单，直接在后面插入结点即可。代码如下：

void SLInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = BuyLTNode(x);newnode->next = pos->next;pos->next = newnode;}

3. 在 pos 位置/之后删除数据

在 pos 位置删除数据数据同样判断两种情况，当 pos 位置是头结点时，调用头删函数即可，否则遍历到 pos 结点位置，然后跳过 pos 结点，指向下一个结点的地址，再 free(pos) 即可。

void SLErase(SLTNode** pphead, SLTNode* pos){assert(pphead);assert(pos);if (pos == *pphead){SLPopFront(pphead);//头部删除数据}else {SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}}

 删除 pos 位置之后的数据则十分简单，代码如下：

void SLEraseAfter(SLTNode* pos){assert(pos);assert(pos->next);SLTNode* next = pos->next;pos->next = next->next;free(next);}

 4. 内存释放

free 每一个结点，phead 置空即可 ，代码如下：

void SLDestory(SLTNode** pphead){assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;}

5. 结果

SLTNode* pos = STFind(plist,3);//找 data = 3 的结点SLInsert(&plist, pos, 100);//在 3 前插入100SLTPrint(plist);SLInsertAfter(pos, 200);//在 3 后插入200SLTPrint(plist);SLEraseAfter(pos);//删除 3 后面的 200SLTPrint(plist);SLErase(&plist,pos);//删除 3 SLTPrint(plist);SLDestory(&plist);//内存释放

---