网站建设 长安镇,网站无缝背景,拉新奖励的app排行,工业和信息化部投诉平台入口本文图皆为作者手绘,所有代码基于vs2022运行测试 系列文章目录
数据结构初探:顺序表篇 文章目录 系列文章目录前言一、链表基础概念二、链表的分类简化边界条件处理使代码更清晰简洁提高程序稳定性 1.单链表(不带头不循环的单链表);1.1存储结构;1.2准备工作1.3链表增删查改的实… 本文图皆为作者手绘,所有代码基于vs2022运行测试 系列文章目录
数据结构初探:顺序表篇 文章目录 系列文章目录前言一、链表基础概念二、链表的分类简化边界条件处理使代码更清晰简洁提高程序稳定性 1.单链表(不带头不循环的单链表);1.1存储结构;1.2准备工作1.3链表增删查改的实现1.SList.h2.SList.c2.1链表的打印2.2节点的创建2.3链表的尾插2.4链表的头插2.5链表的尾删2.6链表的头删2.7链表的查找2.8链表的中间插入2.9链表的pos位置删除;2.10 链表的在pos位置之后插入2.11链表的在pos位置之后删除2.12链表的销毁2.13完整代码 3.test.c 1.4单链表的优缺点 2.双向带头循环链表 总结 前言
在编程的世界里数据结构是构建高效算法的基石而链表作为一种基础且重要的数据结构有着独特的魅力和广泛的应用场景。本文将深入探讨链表的奥秘从基础概念到复杂操作再到实际应用帮助你全面掌握链表这一数据结构。 一、链表基础概念
链表从本质上来说是一种线性的数据结构。它由一系列节点组成这些节点就像是链条上的环相互连接形成了链表。每个节点都包含两个关键部分数据域和指针域。数据域用于存储我们需要的数据比如一个整数、一个字符串或者更为复杂的对象而指针域则存储着下一个节点的内存地址通过这个指针各个节点得以串联起来形成了链表的结构。
与我们熟悉的数组相比链表在内存分配和操作方式上有着显著的不同。数组在内存中是连续存储的这使得它可以通过索引快速地访问任意位置的元素实现高效的随机访问。但这种连续存储的特性也带来了一些限制比如在插入和删除元素时往往需要移动大量的元素操作的时间复杂度较高。而链表则不同它的节点在内存中并不要求连续存储插入和删除操作只需要修改相关节点的指针即可时间复杂度较低。不过链表由于没有索引访问特定位置的元素需要从头节点开始依次遍历这在一定程度上影响了它的访问效率。 以下是其基础结构:
二、链表的分类
接下来我会用一张图让你知道所有链表的类别: 这里共有八种链表形式,其中要说的一点是带头/不带头,也可以叫做带哨兵位/不带哨兵位. 哨兵位: 在链表等数据结构中带有哨兵位的头结点有以下重要作用
简化边界条件处理
插入操作在普通链表插入节点到头部时需要单独处理头指针的更新以防丢失链表头部。而有了哨兵头结点插入操作就可统一为在哨兵头结点后的节点插入无需特殊处理头指针。删除操作删除链表第一个节点也需特殊处理头指针。有了哨兵头结点删除操作可视为删除哨兵头结点后的节点使删除操作逻辑统一。
使代码更清晰简洁
遍历操作在遍历链表时无需在循环中专门处理头指针的特殊情况可直接从哨兵头结点的下一个节点开始遍历让遍历代码更简洁。其他操作对于链表的合并、拆分等复杂操作哨兵头结点能使操作的边界条件更清晰让代码逻辑更易理解和维护减少因边界条件处理不当导致的错误。
提高程序稳定性
避免空指针问题在没有哨兵头结点的链表中如果链表为空进行某些操作可能会导致空指针引用错误。而有了哨兵头结点即使链表暂时没有数据节点也有一个固定的头结点存在可有效避免空指针问题提高程序的稳定性和健壮性。
但是在现实生活中用的最多的链表类型有两种,分别是: 不带头不循环的单链表; 双向带头循环链表; 接下来就让我们分开来讲讲吧!
1.单链表(不带头不循环的单链表);
1.1存储结构;
这张图就是它的结构: 看完了图结构,现在我们来了解一下它的逻辑代码结构:
typedef int SLTDataType;//方便修改变量类型;
//定义链表结构体
typedef struct SListNode
{SLTDataType data;//数据存储struct SListNode* next;//存储下一个节点的地址
}SLTNode;这就是我们创建的节点结构:
这就是链表的节点结构,要想构成庞大的数据链,我们还需要增删查改函数的实现;
1.2准备工作
创建对应的三个文件夹: 1.SList.h:用于存储创建链表的节点结构体和增删查改函数的函数声明,以及对应的库函数,方便生成程序时的链接; 2.SList.c:用于函数的实现; 3.test.c:用于测试和修改; ps:2和3,均要包含头文件1,即 #includeSList.h
1.3链表增删查改的实现
1.SList.h
让我们先来看看链表的函数声明长什么样:
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestring.htypedef int SLTDataType;
//定义链表结构体
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
//打印
void SLTPrint(SLTNode* phead);
//节点的创建
SLTNode* CreatNode(SLTDataType d);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在pos位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//在pos位置之后删除
void SLTEraseAfter(SLTNode* pos);
//销毁
void SLTDestroy(SLTNode* phead);是不是感觉和顺序表大差不差? 但是接下来具体实现的时候你就会感觉到不同了!
2.SList.c
2.1链表的打印
//因为是对结构体内部指向的数据进行访问,我们只需要传一级指针,
//就可以做到改变实参的操作;
void SLTPrint(SLTNode* phead)
{//将传的头指针赋给curSLTNode* cur phead;//只要不为空,就一直执行循环while (cur ! NULL){//相当于遍历链表,进行打印;printf(%d--, cur-data);cur cur-next;//更新循环条件;}printf(NULL\n);//防止多次调用后,数据连在一起,所以添加换行符;
}不太理解的话可以结合下图辅助理解:
2.2节点的创建
//因为需要它返回一个新节点给我,所以,我们的返回类型为SLTNode*
SLTNode* CreatNode(SLTDataType x)//因为我们是为了存储值而创建的节点,所以要传对应类型的值;
{//进行动态内存开辟,开一个结构体大小的空间作为新节点SLTNode* newNode (SLTNode*)malloc(sizeof(SLTNode));if (newNode NULL)//判断是否开辟失败;{perror(malloc fail);//返回错误行return NULL;//直接结束}newNode-data x;//赋值给data;newNode-next NULL;//因为是新节点,还未链接,所以我们置空return newNode;//节点创建完成并返回;
}基础的动态内存开辟的使用;
2.3链表的尾插
//思考:为什么传的是二级指针呢?
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//进行断言,防止传为空,从而报错;SLTNode* newNode CreatNode(x);//节点的创建的复用
//判断链表是否为空if (*pphead NULL){//若为空,则直接链接,让头直接指向新节点;*pphead newNode;}else{//若不为空,则找尾节点SLTNode* tail *pphead;//从头开始找while (tail-next ! NULL)//如果节点的nextNULL,则找到了尾,跳出循环{tail tail-next;//进入循环则是还没找到尾,继续往下走;}tail-next newNode;//找到尾后,直接将tail的next链接至新节点即可}
}就是不断找尾,然后尾插,记得要先判断是否为空; 现在我们来看看为什么要传二级指针:我们在对链表进行插入、删除节点等操作时可能需要修改头指针的值。若只传递头指针的副本一级指针函数内对指针的修改不会影响到函数外的头指针。而传递二级指针即指针的指针函数就可以通过修改二级指针所指向的内容来改变头指针的值使函数外的头指针也能得到正确更新。比如在向空链表插入第一个节点时需要让头指针指向新插入的节点就需要通过二级指针来实现。
2.4链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newNode CreatNode(x);//复用newNode-next *pphead;//本身头指针就是指向第一个节点的地址,现在我先让新节点的next指向头节点*pphead newNode;//所以新节点就成为了链表的第一个节点,再对头指针进行更新;
} 这就是头插的完整逻辑,大家可以试试特殊情况下,这个还成不成立,比如说链表为空是的头插;
2.5链表的尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//暴力检查//assert(*pphead);//当为空链表时;if (*pphead NULL)//判断是否为空{printf(链表为空,无法删除\n);return;//为空就直接结束;}//当只有一个节点时;if ((*pphead)-next NULL){free(*pphead);//直接释放,这就已经删除了;*pphead NULL;//然后置为空return;}//当有多个节点时;SLTNode* tail *pphead;//从头开始找尾节点的前一个节点while (tail-next-next ! NULL)//直接找尾的话,之后就无法找到新的尾的next进行置空了{tail tail-next;}free(tail-next);//free掉真正的尾tail-next NULL;//对新的尾的next进行置空;
}结合下图进行理解: 完善逻辑链;
2.6链表的头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//当链表为空时;if (*pphead NULL){printf(链表为空,无法删除\n);return;}else//不为空链表时,指针名称可以是del,head,first...{SLTNode* head *pphead;//保存第一个节点的地址*pphead head-next;//将头指针链接到第二个节点free(head);//释放并且置空head NULL;}
}逻辑如图:
2.7链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{//从头开始找SLTNode* cur phead;while (cur)只要不为空就继续{if (cur-data x)//如果找到了{return cur;//就返回所在节点的地址}else{cur cur-next;//否则继续往下找}}return NULL;//没找到就返回空指针
}就是遍历查找啦;
2.8链表的中间插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);assert(pphead);//pos为头部时;if (pos *pphead){SLTPushFront(pphead, x);//相当于头插;//也可以直接将头插写在这里,然后给pos为头,直接复用也可}else{SLTNode* prev *pphead;//从头开始找while (prev-next ! pos)//直到找到pos节点的前一个{prev prev-next;}SLTNode* newNode CreatNode(x);//复用prev-next newNode;newNode-next pos;//进行链接}
}也可以找尾,然后给尾地址,这个也可以变成尾插 逻辑参考下图:
2.9链表的pos位置删除;
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pphead);//为头部时if (pos *pphead){SLTPopFront(pphead);//相当于头删}else{SLTNode* prev *pphead;while (prev-next ! pos)//找到pos的前一个{prev prev-next;}prev-next pos-next;//前一个与后一个链接起来free(pos);//再将pos释放}为尾部时的逻辑代码,理解即可//SLTNode* tail *pphead;//while (tail-next ! NULL)//{// tail tail-next;//}//if (pos tail)//{// SLTPopBack(*pphead);//}}参考上文的图例,可以自己尝试画画图来加深印象哦!
2.10 链表的在pos位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newNode CreatNode(x);newNode-next pos-next;pos-next newNode;//直接进行链接;}2.11链表的在pos位置之后删除
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}
后面这两个是不是非常简单,就是因为我们已经知道pos,而且只要往后找就好啦;
2.12链表的销毁
void SLTDestroy(SLTNode* phead)
{SLTNode* cur phead;while (cur)//逐个销毁{SLTNode* tmp cur-next;free(cur);cur tmp;}
}2.13完整代码
#define _CRT_SECURE_NO_WARNINGS 1#includeSList.h//链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d--, cur-data);cur cur-next;}printf(NULL\n);
}//链表元素的创建
SLTNode* CreatNode(SLTDataType x)
{SLTNode* newNode (SLTNode*)malloc(sizeof(SLTNode));if (newNode NULL){perror(malloc fail);return NULL;}newNode-data x;newNode-next NULL;return newNode;
}//链表的尾部插入
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newNode CreatNode(x);if (*pphead NULL){*pphead newNode;}else{SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newNode;}
}//链表头部插入的逻辑代码;
void SLTPushFront1(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newNode CreatNode(x);if (*pphead NULL){*pphead newNode;//完全可以忽略这一步,直接用下一步即可;}else{newNode-next *pphead;*pphead newNode;}
}//链表的头部插入(优化);
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newNode CreatNode(x);newNode-next *pphead;*pphead newNode;
}//链表的尾部删除(详细);
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//暴力检查//assert(*pphead);//当为空链表时;if (*pphead NULL){printf(链表为空,无法删除\n);return;}//当只有一个节点时;if ((*pphead)-next NULL){free(*pphead);*pphead NULL;return;}//当有多个节点时;SLTNode* tail *pphead;while (tail-next-next ! NULL){tail tail-next;}free(tail-next);tail-next NULL;
}//链表的头部删除;
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//当链表为空时;if (*pphead NULL){printf(链表为空,无法删除\n);return;}else//不为空链表时,指针名称可以是del,head,first...{SLTNode* head *pphead;*pphead head-next;free(head);head NULL;}
}//链表的数据查找;
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}else{cur cur-next;}}return NULL;
}//链表的中间插入;
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);assert(pphead);//pos为头部时;if (pos *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newNode CreatNode(x);prev-next newNode;newNode-next pos;}
}//删除pos位置的链表节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pphead);//为头部时if (pos *pphead){SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}为尾部时//SLTNode* tail *pphead;//while (tail-next ! NULL)//{// tail tail-next;//}//if (pos tail)//{// SLTPopBack(*pphead);//}}//在pos之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newNode CreatNode(x);newNode-next pos-next;pos-next newNode;}//在pos位置后删除
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}//链表的销毁
void SLTDestroy(SLTNode* phead)
{SLTNode* cur phead;while (cur){SLTNode* tmp cur-next;free(cur);cur tmp;}
}接下来是测试代码;
3.test.c
直接上完整代码;
#define _CRT_SECURE_NO_WARNINGS 1#includeSList.hvoid test1()
{SLTNode* phead NULL;//βSLTPushBack(phead, 1);SLTPushBack(phead, 2);SLTPushBack(phead, 3);SLTPushBack(phead, 4);SLTPrint(phead);//ͷSLTPushFront(phead, 20);SLTPushFront(phead, 40);SLTPushFront(phead, 60);SLTPushFront(phead, 360);SLTPrint(phead);//βɾSLTPopBack(phead);SLTPopBack(phead);SLTPopBack(phead);SLTPrint(phead);//ͷɾSLTPopFront(phead);SLTPopFront(phead);SLTPopFront(phead);SLTPopFront(phead);SLTPopFront(phead);SLTPopFront(phead);SLTPrint(phead);}void test2()
{SLTNode* phead NULL;SLTPushBack(phead, 1);SLTPushBack(phead, 2);SLTPushBack(phead, 3);SLTPushBack(phead, 4);SLTPrint(phead);SLTNode* ret SLTFind(phead, 2);printf(%d\n, ret-data);ret-data * 2;SLTPrint(phead);SLTInsert(phead, ret, 5);SLTPrint(phead);SLTInsertAfter(ret, 10000);SLTPrint(phead);SLTEraseAfter(ret);SLTPrint(phead);SLTErase(phead, ret);SLTPrint(phead);SLTDestroy(phead);phead NULL;SLTPrint(phead);}int main()
{test2();return 0;
}1.4单链表的优缺点
其优缺点如下 优点
动态性单链表可以根据需要动态地分配和释放内存空间无需预先知道数据的数量在插入和删除节点时只需修改指针不需要移动大量数据操作效率较高。例如在实时处理大量用户请求的系统中使用单链表可以灵活地添加和删除请求节点。插入和删除操作简便在单链表中插入和删除节点通常只需要修改相关节点的指针时间复杂度为O(1)。比如要在两个节点A和B之间插入节点C只需让A的指针指向CC的指针指向B即可。节省内存相较于一些需要连续内存空间的数据结构单链表的节点可以分散存储在内存中能更有效地利用内存碎片只要内存中有可用空间就可以创建新节点。
缺点
随机访问困难单链表只能顺序访问要访问第i个节点必须从表头开始逐个节点遍历时间复杂度为O(n)。比如要查找链表中间的某个节点需要从头开始依次查找。额外空间开销每个节点除了存储数据本身外还需要额外的空间存储指针当数据量较小时指针占用的空间比例可能较大会造成一定的空间浪费。节点指针易出错在进行插入、删除操作或遍历链表时如果指针操作不当如指针丢失、指针指向错误等可能会导致链表结构破坏出现数据丢失或程序崩溃等问题。而且调试这类问题相对困难。
2.双向带头循环链表
篇幅至此,且容我下次再续 总结
单链表是一种优缺点都很鲜明的数据结构。在实际的编程应用中我们需要根据具体的需求和场景来权衡是否选择使用单链表。如果应用场景对插入和删除操作的效率要求较高而对随机访问的需求较少同时内存空间比较零散那么单链表无疑是一个很好的选择。但如果需要频繁地进行随机访问操作或者对内存空间的利用率要求极高我们可能就需要考虑其他更合适的数据结构了。通过深入了解单链表的特性我们能够在编程过程中更加游刃有余地选择和运用合适的数据结构从而编写出更高效、更优质的代码。
