赞
踩
链表和顺序表都是线性表的一种,但是顺序表在物理结构和逻辑结构上都是连续的,但链表在逻辑结构上是连续的,而在物理结构上不一定连续;来看以下图片来认识链表与顺序表的差别
这里以动态顺序表为例,和链表中的单链表对比一下
动态顺序表
单链表
这里就可以很清晰的看到顺序表的底层其实就是一个数组,数据的是连续存储的(顺序表物理结构连续);而链表它每一个数据都不是连续的(链表物理结构上不一定连续)。
通过观察上图,我们会发现链表每一个节点都存放在数据和下一个节点的地址。
那么来想一下,为了链表每一个节点都统一起来,都存储有效数据和下一个节点的地址,我们就需要创建应该结构体,来存储有效数据和下一个节点的指针;
注:这里只是单链表
- typedef int SLType;
- typedef struct SLTNode
- {
- SLType data;
- struct SLTNode* next;
- }SLT;
创建好链表节点,接下来就来实习单链表存储数据的这些功能。
先来看一下单链表都实现都哪些功能
- //输出链表
- void SLTPrint(SLT* phead);
- //创建节点
- SLT* SLTCreat(SLType x);
- //单链表头插
- void SLTPushFront(SLT** pphead, SLType x);
- //单链表尾插
- void SLTPushBack(SLT** pphead, SLType x);
- //单链表头删
- void SLTPopFront(SLT** pphead);
- //单链表尾删
- void SLTPopBack(SLT** pphead);
- //查找数据
- SLT* SLTFind(SLT* phead, SLType x);
- //指定位置之前插入
- void SLTInsert(SLT** pphead, SLT* pos, SLType x);
- //指定位置之后插入
- void SLTInsertAfter(SLT* pos, SLType x);
- //删除指定节点
- void SLTErase(SLT** pphead, SLT* pos);
- //删除指定位置后一个节点
- void SLTEraseAfter(SLT* pos);
创建节点
这里创建节点,还是使用动态内存来创建,创建完成后,将数据存储进去,并把新节点的下一个节点置为NULL
代码如下:
- //创建节点
- SLT* SLTCreat(SLType x)
- {
- SLT* newnode = (SLT*)malloc(sizeof(SLT));
- assert(newnode);
- newnode->data = x;
- newnode->next = NULL;
- return newnode;
- }
测试一下代码是否正确
可以看到代码没有问题。
输出链表
由于这里实现单链表,存储的是整型数据,就以整型的方式输出,若存储其他类型的数据,就以存储类型的方式输出。
输出链表,首先就要遍历链表,因为链表最后一个节点里存储的下一个节点的地址为空(即最后一个节点 ->next 为空)所以,遍历链表结束的条件就是ptail ==NULL,没输出一个就让ptail指向下一个节点,直到为空,遍历结束。
来写代码实现:
- //输出链表
- void SLTPrint(SLT* phead)
- {
- SLT* ptail = phead;
- while (ptail!= NULL)//也可以直接写成 ptail
- {
- printf("%d -> ", ptail->data);
- ptail = ptail->next;
- }
- printf("NULL\n");
- }
这里先创建两个节点并存储数据输出看一下结果
- int main()
- {
- SLT* plist = SLTCreat(1);
- plist->next = SLTCreat(2);
- SLTPrint(plist);
- return 0;
- }
这里也成功输出插入的两个数据。(最后一个节点的next指向空)
单链表头插
在链表头部插入数据,不用像顺序表那样去移动所以的有效数据,链表只需要改变一个指针的指向即可
假设现在链表中已经存在两个数据,再进行头插,这时就只需要改变plist的指向即可,当然新节点的next指针也要指向下一个节点(plist指向的节点)。
代码如下:
- //单链表头插
- void SLTPushFront(SLT** pphead, SLType x)
- {
- assert(pphead);
- SLT* newnode = SLTCreat(x);
- newnode->next = *pphead;
- *pphead = newnode;
- }
还有一种情况,如果现在链表中没有数据,再进行头插,这里代码也能实现链表没有数据时的头插
单链表尾插
链表的尾插,因为指针传的是指向头节点的指针的地址,所以,我们需要先遍历链表,找到链表的尾部,再修改尾节点的next指针指向。
假设现在链表中已经存在两个数据,再进行尾插,此时我们只需要找到链表的尾部,修改尾节点next指针指向即可,代码如下
- //单链表尾插
- void SLTPushBack(SLT** pphead, SLType x)
- {
- assert(pphead);
- SLT* newnode = SLTCreat(x);
- SLT* ptail = *pphead;
- //遍历链表
- while (ptail->next)
- {
- ptail = ptail->next;
- }
- ptail->next = newnode;
- }
考虑了这种情况,再来看以下链表为空的情况,如果链表为空,这里ptail->next就对空指针进行解引用操作了;所以,我们需要判断链表是否为空?如果为空,插入的新节点就是头节点,直接让plist(即*pphead)指向新节点即可;如果不为空就正常进行尾插。
最终代码如下:
- //单链表尾插
- void SLTPushBack(SLT** pphead, SLType x)
- {
- assert(pphead);
- SLT* newnode = SLTCreat(x);
- if (*pphead == NULL) //判断链表是否为空
- {
- *pphead = newnode;
- }
- else {
- SLT* ptail = *pphead;
- //遍历链表
- while (ptail->next)
- {
- ptail = ptail->next;
- }
- ptail->next = newnode;
- }
- }
这里代码可以正常进行尾插。
单链表头删
链表头删,首先我们要判断链表是否为空,如果为空(空链表没有数据该如何删除呢)
链表头删,我们需要修改plist(*pphead)指向链表的下一个节点即头节点的next指针。
此外:因为我们的节点都是动态申请的内存,所以在删除时,需要把它释放掉。
思路很简单,写一下代码:
- //单链表头删
- void SLTPopFront(SLT** pphead)
- {
- assert(pphead && *pphead);
- SLT* del = (*pphead);
- *pphead = (*pphead)->next;
- free(del);
- del = NULL;
- }
再来看一个如果链表为空,又是啥结果呢?
现在链表已经为空,在执行一次头删代码
这里assert断言报错。
单链表尾删
首先尾删与头删一样,链表不能为空。
尾删与尾插也有共同之处,就是遍历链表,找到链表的尾节点。找到尾节点,删除尾节点;然后修改尾节点上一个节点的next指针为NULL;所以在遍历链表时就要多记录一个节点。
- //单链表尾删
- void SLTPopBack(SLT** pphead)
- {
- assert(pphead && *pphead);
- SLT* ptail = *pphead;
- SLT* pcur = *pphead;
- //遍历链表
- while (ptail->next)
- {
- pcur = ptail;
- ptail = ptail->next;
- }
- pcur->next = NULL;
- free(ptail);
- ptail = NULL;
- }
在测试的时候我们会发现一个问题,如果链表只有一个节点,删除之后我们的plist指针并没有置为空,而我们的空间已经释放掉了,这是很危险的;所以这里我们先判断一下链表是否只有一个节点,如果是,我们释放完空间以后,将(*pphead)置为空,以免出现野指针的情况。
完善后代码:
- //单链表尾删
- void SLTPopBack(SLT** pphead)
- {
- assert(pphead && *pphead);
- if ((*pphead)->next== NULL)
- {
- free(*pphead);
- *pphead = NULL;
-
- }
- else {
- SLT* ptail = *pphead;
- SLT* pcur = *pphead;
- //遍历链表
- while (ptail->next)
- {
- pcur = ptail;
- ptail = ptail->next;
- }
- free(ptail);
- ptail = NULL;
- pcur->next = NULL;
- }
- }
测试没有问题,代码能够完成尾删这个功能。
查找数据
查找数据,遍历链表查找数据,如果找到就返回数据所在节点的地址,如果没有找到就返回NULL;
- //查找数据
- SLT* SLTFind(SLT* phead, SLType x)
- {
- SLT* ptail = phead;
- while (ptail)
- {
- if (ptail->data == x)
- {
- return ptail;
- }
- ptail = ptail->next;
- }
- return NULL;
- }
这里测试以下:
数据存在时
数据不存在时
指定节点之前插入
在链表指定节点之前插入数据,我们还需要知道指定节点的前一个节点,所以仍然需要遍历链表,寻找指定节点pos前一个节点。
- //指定位置之前插入
- void SLTInsert(SLT** pphead, SLT* pos, SLType x)
- {
- assert(pphead && *pphead);
- SLT* ptail = *pphead;
- if (ptail == pos)//头插
- {
- SLTPushFront(pphead, x);
- }
- else
- {
- SLT* newnode = SLTCreat(x);
- while (ptail->next != pos)//找到pos位置
- {
- ptail = ptail->next;
- }
- newnode->next = pos;
- ptail->next = newnode;
- }
- }
当然,这里如果故意传NULL给pos,(这就没啥意义了)这里也可以写以下assert断言pos。
指定节点之后插入
在指定节点之后插入数据,就不需要再进行遍历链表,这里直接插入即可。
- //指定位置之后插入
- void SLTInsertAfter(SLT* pos, SLType x)
- {
- assert(pos);
- SLT* newnode = SLTCreat(x);
- newnode->next = pos->next;
- pos->next = newnode;
- }
删除指定节点
删除链表中的指定节点,我们需要这个节点的上一个节点,所以又需要遍历链表,找到pos上一个节点,修改pos->next指针指向。
代码如下:
- //删除指定节点
- void SLTErase(SLT** pphead, SLT* pos)
- {
- //找到pos上一个节点
- SLT* ptail = *pphead;
- while (ptail->next != pos)
- {
- ptail = ptail->next;
- }
- SLT* p = pos->next;
- free(pos);
- pos = NULL;
- ptail->next = p;
- }
删除指定节点后一个节点
删除链表指定节点后一个节点,因为pos就是删除节点的上一个节点,所以不需要遍历链表,直接删除即可。
- //删除指定位置后一个节点
- void SLTEraseAfter(SLT* pos)
- {
- assert(pos->next);
- SLT* del = pos->next;
- pos->next = pos->next->next;
- free(del);
- del = NULL;
- }
这里如果传过来的就是链表的尾节点,那删除后一个节点,所以断言pos->next;
- #include"SList.h"
- //创建节点
- SLT* SLTCreat(SLType x)
- {
- SLT* newnode = (SLT*)malloc(sizeof(SLT));
- assert(newnode);
- newnode->data = x;
- newnode->next = NULL;
- return newnode;
- }
- //输出链表
- void SLTPrint(SLT* phead)
- {
- SLT* ptail = phead;
- while (ptail != NULL)//也可以直接写成 ptail
- {
- printf("%d -> ", ptail->data);
- ptail = ptail->next;
- }
- printf("NULL\n");
- }
- //单链表头插
- void SLTPushFront(SLT** pphead, SLType x)
- {
- assert(pphead);
- SLT* newnode = SLTCreat(x);
- newnode->next = *pphead;
- *pphead = newnode;
- }
- //单链表尾插
- void SLTPushBack(SLT** pphead, SLType x)
- {
- assert(pphead);
- SLT* newnode = SLTCreat(x);
- if (*pphead == NULL) //判断链表是否为空
- {
- *pphead = newnode;
- }
- else {
- SLT* ptail = *pphead;
- //遍历链表
- while (ptail->next)
- {
- ptail = ptail->next;
- }
- ptail->next = newnode;
- }
- }
- //单链表头删
- void SLTPopFront(SLT** pphead)
- {
- assert(pphead && *pphead);
- SLT* del = (*pphead);
- *pphead = (*pphead)->next;
- free(del);
- del = NULL;
- }
- //单链表尾删
- void SLTPopBack(SLT** pphead)
- {
- assert(pphead && *pphead);
- if ((*pphead)->next== NULL)
- {
- free(*pphead);
- *pphead = NULL;
-
- }
- else {
- SLT* ptail = *pphead;
- SLT* pcur = *pphead;
- //遍历链表
- while (ptail->next)
- {
- pcur = ptail;
- ptail = ptail->next;
- }
- free(ptail);
- ptail = NULL;
- pcur->next = NULL;
- }
- }
- //查找数据
- SLT* SLTFind(SLT* phead, SLType x)
- {
- SLT* ptail = phead;
- while (ptail)
- {
- if (ptail->data == x)
- {
- return ptail;
- }
- ptail = ptail->next;
- }
- return NULL;
- }
- //指定位置之前插入
- void SLTInsert(SLT** pphead, SLT* pos, SLType x)
- {
- assert(pphead && *pphead);
- SLT* ptail = *pphead;
- if (ptail == pos)//头插
- {
- SLTPushFront(pphead, x);
- }
- else
- {
- SLT* newnode = SLTCreat(x);
- while (ptail->next != pos)//找到pos位置
- {
- ptail = ptail->next;
- }
- newnode->next = pos;
- ptail->next = newnode;
- }
- }
- //指定位置之后插入
- void SLTInsertAfter(SLT* pos, SLType x)
- {
- assert(pos);
- SLT* newnode = SLTCreat(x);
- newnode->next = pos->next;
- pos->next = newnode;
- }
- //删除指定节点
- void SLTErase(SLT** pphead, SLT* pos)
- {
- //找到pos上一个节点
- SLT* ptail = *pphead;
- while (ptail->next != pos)
- {
- ptail = ptail->next;
- }
- SLT* p = pos->next;
- free(pos);
- pos = NULL;
- ptail->next = p;
- }
- //删除指定位置后一个节点
- void SLTEraseAfter(SLT* pos)
- {
- assert(pos->next);
- SLT* del = pos->next;
- pos->next = pos->next->next;
- free(del);
- del = NULL;
- }
感谢各位大佬支持并指出问题,
如果本篇内容对你有帮助,可以一键三连支持以下,感谢支持!!!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。