链表详解(三)

链表功能实现

链表的查找SLNode* SLFind(SLNode* phead, SLNDataType x)

我们用指针cur去遍历这个链表，如果cur的数据val值是和x想等的，那么就直接返回cur这个位置的节点，如果cur->val!=x,那么我们就让cur走到下一个节点cur=cur->next,当遍历完整个链表后我们还是没有找到和x相等的val,那么我们就直接返回一个NULL就行了

代码

SLNode* SLFind(SLNode* phead, SLNDataType x)
{assert(pphead);SLNode* cur = phead;while (cur){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}

链表任意位置前插入void SLInsert(SLNode**pphead，SLNode* pos, SLNDataType x)

函数功能为在pos位置前插入链表数据x

在实现这个函数之前，有一个问题，就是pphead和*pphead的区别

pphead是一个二级指针，所有pphead表示对所一级指针的地址，也就是指向链表头节点指针的地址
*pphead是对pphead解引用，表示指向链表头节点的指针，注意不是指向链表头节点指针的地址

那么我们知道了这两个都区别，我们再来看看下面这个问题

pphead *pphead pos这三个是否需要断言

首先pphead断言 assert（pphead）表示我们要检查指向链表头节点指针的地址是否为空，换句话说就是如果传入为空，这个函数是否会出现问题，显然，如果我们传入为空，那么我们就无法找到指向链表头节点指针，

那*pphead断言assert（*pphead）就表示我们要检查链表头节点指针是否指向的空，如果指向空，就代表这个链表为空链表，我们就可以当这个函数为头插，或者尾插，所有这并不会对这个函数造成影响

pos断言assert（pos）表示传入参数插入位置指针的地址是否为空，如果为空，那么我们也就找不到插入的位置，所以pos是需要断言的
但是有一种情况pos只能为空，就是*pphead为空，空链表我们要插入的地址当然只能传空，为了防止这种情况我们就需要像这样断言 assert((!(*pphead) == !pos) || pos && *pphead)

!(*pphead) == !pos)表示pos为空时为假，pphead为空时也为假，通过！对两个取反，使假变成真
pos && pphead表示pos和pphead都不为空
这两个只需要满足其中的一个就可以继续用插入函数
当pos和pphead二者中只有一个为空时就会断言报错

还有一种情况就是pos的位置根本不在链表中，我们整个链表都找完了，就是没有找到pos的位置，所有我们要判断当链表遍历完时，仍然没有找到pos的位置，我们就需要提醒一下找不到pos的位置

代码

void SLInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);assert((!(*pphead) == !pos) || pos && *pphead);if ((*pphead == pos))//头插情况{SLPushFront(pphead, x);}else {SLNode* prev = *pphead;while (prev->next != pos){if (prev->next == NULL){printf("找不到pos的位置");exit（-1）;}prev = prev->next;}	SLNode* newnode = CreateNode(x);prev->next = newnode;newnode->next = pos;}
}

链表任意位置前删除void SLErase(SLNode**pphead，SLNode* pos)

函数功能为删除pos位置的节点
这个函数和之前的函数实现方式都是差不多的,删除一个节点,就需要找到这个节点的前一个节点

void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);SLNode* prev = *pphead;while (prev->next != pos){if (prev->next == NULL){printf("找不到pos的位置");exit(-1);}prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}

这个代码过程如下图

prev->next=pos

让prev->next=pos->next

释放pos指向节点的空间

上面的代码还是少考虑了只有一个节点时的情况
prev->next为空,但是prev已经在pos所在的位置了

我们就应该加一个判断,if(*pphead=pos),然后就直接头删

代码

void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){SLPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){if (prev->next == NULL){printf("找不到pos的位置");exit(-1);}prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

链表任意位置后插入void SLInsertAfter( SLNode* pos,SLNDataType x)

之前是在pos位置之前插入,我们需要遍历链表才能找到pos位置之前的节点,所以需要传pphead,而这个函数是在pos位置后插入,所有就不需要传pphead

void SLInsertAfter( SLNode* pos,SLNDataType x)
{assert(pos);SLNode* newnode = CreateNode(x);pos->next = newnode;newnode->next = pos->next;
}

这是一段错误的代码



我们发现按照上面的逻辑pos->next其实就是newnode->next,所以在用这个函数时就会出现问题

代码

void SLInsertAfter( SLNode* pos,SLNDataType x)
{assert(pos);SLNode* newnode = CreateNode(x);newnode->next = pos->next;pos->next = newnode;
}

例题

用void SLInsertAfter( SLNode* pos,SLNDataType x)实现在pos位置前插入一个节点
思路:虽然我们不知道pos位置前一个节点的地址,但是我们可以通过这个函数在pos位置后插入一个节点,然后让这个节点的数据val和pos位置的数据val交换,就可以实现这pos位置之前插入节点

链表任意位置后删除void SLEraseAfter(SLNode* pos, SLNDataType x)

我们来看看下面一段代码

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

这段代码有人认为程序运行的过程如下

其实是这样的

这段代码不仅没有删除pos的下一个节点,反而让pos下一个节点的next指针变成了野指针

正确的方法是需要用tail指针保存pos->next,然后让pos->next=pos->next->next,之后再释放掉tail指向的空间

void SLEraseAfter(SLNode* pos, SLNDataType x)
{assert(pos);SLNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}

但是我们还需要考虑到pos为尾节点的情况,因为pos->next=NULL，而pos->next->next就不知道是什么了,所以我们还需要加一下断言

代码

void SLEraseAfter(SLNode* pos, SLNDataType x)
{assert(pos);assert(pos->next);SLNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}

销毁链表void SLDestroy(SLNode** pphead)

代码

void SLDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur != NULL){SLNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}