虽然顺序具有方便下标随机访问(因为是连续物理空间)的优点,但是也具有一定的缺陷,

如:

1. 插入数据,空间不足时要扩容,但是扩容有性能消耗

2. 头部或者中间位置插入删除数据,需要挪动数据,效率比较低

3. 空间扩容太大,可能存在一定空间占用,浪费空间,不能按需申请和释放空间

由于这些缺陷,链表诞生了

那么链表是什么?

概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。

从上图可看出:

1. 链式结构在逻辑上是连续的,但是在物理上不一定连续

2. 现实中的结点一般都是从堆上申请出来的

3. 从堆上申请的空间,是按照一定的此略来分配的,两次申请的空间可能连续,也可能不连续

链表分类:

单向或者双向

 带头或者不带头

循环或者非循环

 常用的结构:

无头单向非循环链表

结构简单,一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在面试笔试中出现很多。

带头双向循环链表

结构最复杂
,一般用在单独处处数据,实际中使用的链表数据结构,都是带头双向循环链表。另外整个结构虽然结构复杂,但是使用代码实现以后会发现会带来很多优势,实现反而简单了

 这里实现的是无头单向非循环链表

将要完成接口有:
//创建结点 SListNode* BuySListNode(SListDateType x); //打印链表 void
PrintSList(SListNode* phead); //尾插 void SListPushBack(SListNode** pphead,
SListDateType x); //头插 void SListPushFornt(SListNode** pphead, SListDateType
x); //尾删 void SListPopBack(SListNode** pphead); //头删 void
SListPopFront(SListNode** pphead); //查找指定值 SListNode* SListFind(SListNode*
phead, SListDateType x); //在指定位置前插入 void SListInsertBefore(SListNode** pphead,
SListNode* pos, SListDateType x); //在指定位置后插入 void SListInsertAfter(SListNode*
pos, SListDateType x); //删除指定位置 void SListErase(SListNode** pphead, SListNode*
pos); //删除指定位置后结点 void SListEraseAfter(SListNode* pos); //销毁链表 void
SListDestroy(SListNode** pphead);
注:无头单向非循环链表需要理解二级指针传参,以及链表为空和不存在与顺序表的为空和不存在

定义的结构体结点:
typedef int SListDateType;//方便类型灵活变换 typedef struct SListNode { int date;//数据
struct SListNode* next;//存放下一个结点的地址 }SListNode;
创建新结点:

这里需要注意,由于链表的特点,我们操作结构体指针,而不是操作结构体,这一点与顺序表不同,所以我们要做的不是初始化,而是要写一个创建新结点的接口函数,当结点创建好就把数据放入
//创建新结点 SListNode* BuySListNode(SListDateType x) { //开辟一块动态内存 SListNode*
newnode = (SListNode*)malloc(sizeof(SListNode)); //开辟失败终止程序 if (newnode ==
NULL) { printf("Fail\n"); exit(-1); } else { newnode->date = x;//将x放入新开辟date
newnode->next = NULL;//开辟空间后不知道指向哪,先置空 } //将开辟空间返回 return newnode; }
尾部插入结点:

这里需要注意

由于尾插可能会改变第一个结点(链表为空),既然第一个结点会被改变,就应该传地址,而传过来的应该是一个一级指针指向链表的第一个结点,所以这里应该用二级指针接收

尽管传过来的一级指针指向的链表可能为空(即这个一级指针被赋为空),这也只是说明链表为空,但是存在这个链表,但是pphead作为应该二级指针指向传过来的一级指针,所以pphead里存放了这个一级指针的地址,既然有这个一级指针,那么这个一级指针便有地址存放一级指针,所以pphead不可能为空,否则就不是链表为空,那是链表不存在了,这是非法的情况

当链表为空需要分开讨论,直接将新创建的结点赋值

其他情况如下:

void SListPushBack(SListNode** pphead, SListDateType x) {
assert(pphead);//pphead不能为空 //传x并接收创建的结点 SListNode* newnode = BuySListNode(x);
//如果传的是NULL,说明是空链表,将开辟的空间直接赋给空的链表 if (*pphead == NULL) {
//当链表尾空,将第一次新开的结点赋值,则*pphead存放的则始终是第一个结点 *pphead = newnode; }
//如果传的不是NULL,说明不是空链表,原来的链表有结点 else { //找尾巴,将头结点给找尾结点 SListNode* tail = *pphead;
//当tail中的next等于NULL,说明其就是结尾的结点 while (tail->next != NULL) {
//找尾结点,不断的将下一个结点的地址给tail,直到下一个结点的地址是NULL tail = tail->next; }
//当tail->next==NULL,将新开的结点赋值,替换NULL tail->next = newnode; } }
打印链表:

由于是打印,第一个结点也不会被改变,所以采用传值,即传一级指针的值,就用一级指针接收
void PrintSList(SListNode* phead) { SListNode* cur = phead;//将头结点赋值给现结点
//使用现结点遍历,cur->next==NULL是链表结束的标志 while (cur != NULL) { printf("%d->",
cur->date); cur = cur->next; } printf("NULL\n"); }
头部插入结点:

这里头部插入和尾部插入同理,

插入情况如下:

void SListPushFornt(SListNode** pphead, SListDateType x) {
assert(pphead);//pphead不能为空 //接收创建的新结点 SListNode* newnode = BuySListNode(x);
//将首结点地址给新建结点的next newnode->next = *pphead; //将新建结点的地址放首结点 *pphead = newnode; }
尾部删除结点:

尾删和前面的尾插同理,还要注意链表为空以及链表只有一个结点的两种特殊情况,得分开情况讨论,因为prev不能为空,所以分情况讨论

没有结点无法删除

只有一个结点则直接删除

 其他情况如下:

void SListPopBack(SListNode** pphead) { assert(pphead);//链表必须存在 //空链表直接返回 if
(*pphead == NULL) { return; } //链表只有一个结点,直接释放 else if ((*pphead)->next == NULL)
{ free(*pphead); *pphead = NULL; } //链表大于一个结点 else { //采用双指针做法 SListNode* tail
= *pphead; SListNode* prev = NULL; //找尾 while (tail->next != NULL) {
//保留前一个结点的地址 prev = tail; tail = tail->next; } //释放尾结点并置空 free(tail); tail =
NULL; //前一个结点的next置空 prev->next = NULL; /* 两次解引用的做法 while (tail->next->next !=
NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; */ } }
头部删除结点:

与尾插同理,还要链表不能为空,为空无法删除

void SListPopFront(SListNode** pphead) { assert(pphead);//链表必须存在 //链表为空 if
(*pphead == NULL) { return; } //链表不为空 else { //存放第二个结点的地址 SListNode* next =
(*pphead)->next; //释放第一个结点 free(*pphead); //指向第二个结点 *pphead = next; } }
查找指定的值:

由于是查找,不改第一个结点,所以传值,用一级指针接收
SListNode* SListFind(SListNode* phead, SListDateType x) { //遍历链表的现指针
SListNode* cur = phead; //查找x while (cur) { if (cur->date == x) { return cur; }
cur = cur->next; } //找不到 return NULL; }
在指定位置前插入:

 与尾插同理,第一个结点可能改变,而且待插位置不能为空,这里需要分情况讨论,

当插入的结点是第一个结点时,正好是头插,因为prev不能为空,所以单独讨论

当插入的结点不是第一个时:

void SListInsertBefore(SListNode** pphead, SListNode* pos, SListDateType x) {
assert(pphead);//链表必须存在 assert(pos);//插入的位置不能为空 //当插入的结点是第一个时 if (pos ==
*pphead) { SListPushFornt(pphead, x); } //当插入的结点不是第一个时 else { //从第一个结点开始遍历
SListNode* prev = *pphead; //查找pos位置 while (prev->next != pos) { prev =
prev->next; } //创建新的结点 SListNode* newnode = BuySListNode(x); //插入 prev->next =
newnode; newnode->next = pos; } }
在指定位置后插入:

这种情况第一个不可能被改变,所以传值就行,使用一级指针接收,以及待插位置不能为空

void SListInsertAfter(SListNode* pos, SListDateType x) {
assert(pos);//插入的位置不能为空 //创建结点 SListNode* newnode = BuySListNode(x); //插入
newnode->next = pos->next; pos->next = newnode; }
删除指定位置的结点:

有可能删除第一个结点,二级指针接收,位置不能为空

需要分情况讨论:

当删除的结点是第一个结点时,也就是头删,需要单独讨论,因为prev不能为空

其他情况如下:

void SListErase(SListNode** pphead, SListNode* pos) { assert(pphead);//链表必须存在
assert(pos);//查找的位置不能为空 //当删除的位置是第一个结点时 if (*pphead == pos) {
SListPopFront(pphead); } //当删除的位置是不是第一个结点时 else { //从第一个结点开始遍历 SListNode* prev
= *pphead; //查找pos while (prev->next != pos) { prev = prev->next; } //删除结点
prev->next = pos->next; free(pos); pos = NULL; } }
删除指定位置后的结点:

不可能删除第一个结点,所以传值,一级指针接收,位置不能为空

void SListEraseAfter(SListNode* pos) { assert(pos);//pos不能为空 //存放待删除的结点
SListNode* next = pos->next; //pos不是最后一个结点,也就是next不能为空 if (next) { //删除结点
pos->next = next->next; free(next); next = NULL; } }
销毁链表:

第一个结点会被改变,传地址,二级指针接收
void SListDestroy(SListNode** pphead) { assert(pphead);//链表得存在 SListNode* cur
= *pphead; while (cur) { //指向待删除的下一个结点 SListNode* next = cur->next; //删除
free(cur); //指向下一个结点,正好到了最后一个结点cur被置空 cur = next; } }
由此可见,单链表结构:

适合头插头删

不适合尾部或者中间某个位置插入删除

技术
©2019-2020 Toolsou All rights reserved,
C语言——qsort函数CSS实现溢出显示省略号网络层协议——ICMP协议C语言小游戏-俄罗斯方块Qt入门教程【基础控件篇】QCalendarWidget日历控件用python来控制wifi连接vue中input框只能输入数字Python内置函数C语言数据结构-顺序表删除重复V2.0.0abaqus质量缩放系数取值_ABAQUS的质量缩放