目录
- 链表功能实现
- 链表的查找SLNode* SLFind(SLNode* phead, SLNDataType x)
- 代码
- 链表任意位置前插入void SLInsert(SLNode**pphead,SLNode* pos, SLNDataType x)
- 代码
- 链表任意位置前删除void SLErase(SLNode**pphead,SLNode* pos)
- 代码
- 链表任意位置后插入void SLInsertAfter( SLNode* pos,SLNDataType x)
- 代码
- 例题
- 链表任意位置后删除void SLEraseAfter(SLNode* pos, SLNDataType x)
- 代码
- 销毁链表void SLDestroy(SLNode** pphead)
- 代码
链表功能实现
链表的查找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;
}