【数据结构】单链表专题（详细代码及配图）

小编主页详情-请点击小编gitee代码仓库-请点击本文主要介绍了数据结构的单链表内容全由作者原创无AI同时深度解析了单链表增删查改等功能并带有配图帮助博友们更好的理解点个关注不迷路下面进入正文~~前言学习了顺序表之后我们发现顺序表存在以下问题1.中间/头部插入效率低下2.增容降低运行效率3.增容造成空间浪费那么有什么办法可以解决这些问题下面我们来介绍链表的概念1.链表的概念及结构概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的顺序结构是通过链表中的指针链接次序实现的。链表也是线性表的一种~物理结构不是线性的逻辑结构一定是线性的那么链表具体是什么东西呢举一个具体的例子链表的结构跟火车很类似如果是旺季我们可以增加车厢如果是淡季我们可以减少车厢每一节车厢都是独立的添加或减少车厢不会影响其他车厢。想象一下假如每节车厢的车门都是上锁的并且需要用不同的钥匙打开每次只能携带一把钥匙的情况下如何从车头走到车尾最简单的做法在每一节车厢都存放下一届节车厢的钥匙。在链表里每一节车厢是长什么样的每个车厢我们称之为节点/结点节点的组成主要有两个部分当前节点要保存的数据和保存下一个节点的地址指针变量。图中的指针变量plist保存的是第一个节点的地址我们称plist此时指向第一个节点。如果我们希望plist指向第二个节点时只需修改plist保存的内容为0x0012FFA0。2.单链表的具体功能的实现2.1单链表需要实现的功能//打印链表 void SLTPrint(SLTNode* phead); //尾插 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); //在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos之后的节点 void SLTEraseAfter(SLTNode* pos); //销毁链表 void SListDesTroy(SLTNode** pphead);2.2打印链表通过phead第一个节点的指针先访问数据再移动到head-next下一个节点的指针知道phead为空才停止访问最后打印NULL收尾。我们习惯用临时变量pcur保存第一个节点的地址这样做是为了方便我们后续找到第一个节点的地址。void SLTPrint(SLTNode* phead) { SLTNode* pcur phead; while (pcur)//pcur ! NULL { printf(%d-, pcur-data); pcur pcur-next; } printf(NULL\n); }2.3链表的的尾插在实现尾插之前我们先画个图帮助我们理解思路1.创建新节点为了方便后续创建新节点的使用我们将创建新节点这一步骤定义为一个函数SLTBuyNodeSLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); if (newnode NULL) { perror(malloc); exit(1); } newnode-data x; newnode-next NULL; return newnode; }2.创建尾节点的指针我们要尾插一个节点因此我们要找到尾节点的指针ptail然后将ptail-next改为新创建节点的地址因此找到尾节点是必要的。我们可以先将ptail指向第一个节点当ptail-nex不等于NULL时将ptail ptail-next直到ptail-next为NULL此时就说明了我们找到尾节点的指针了。SLTNode* ptail *pphead; while (ptail-next) { ptail ptail-next; }3.将ptail-next指向新节点ptail-next newnode那我们不加思考地写出完整的代码void SLTPushBack(SLTNode* phead, SLTDataType x) { SLTNode* newnode SLTBuyNode(x); SLTNode* ptail phead; while (ptail-next) { ptail ptail-next; } ptail-next newnode; }我们发现程序并没有像我们如期的一样打印1-NULL这是为什么呢我们想想如果我们的链表一开始为空链表及plistpheadptailNULL那我们还能进行ptail-next吗很显然不行程序会报错。因此我们需要判断传入的phead是否为NULL如果是直接让phead指向新节点如果不是再进行后面的操作新代码如下void SLTPushBack(SLTNode* phead, SLTDataType x) { //assert(pphead); SLTNode* newnode SLTBuyNode(x); if (phead NULL) { phead newnode; } else { SLTNode* ptail phead; while (ptail-next) { ptail ptail-next; } ptail-next newnode; } }我们再运行一下我们发现这次程序成功输出了但却只输出了NULL并没有输出我们预想的1-NULL这又是为什么呢别急我们调试一下我们发现plist并没有指向新的节点而是NULL说明plist的值并没有发生改变这是因为我们在函数传参的时候使用的是传值调用形参的改变要影响实参必须要传地址第一个节点 *plist------**pphead指向第一个节点的指针 plist-------*pphead指向第一个节点的指针的地址 plist------pphead那么我们要改变指向第一个节点的指针就要传入指向第一个节点的指针的地址 plist同时不要断言ppheadassert(pphead)防止传入了一个空指针NULL下面是修改后正确的代码void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); //*pphead 就是指向第一个节点的指针 //空链表和非空链表 SLTNode* newnode SLTBuyNode(x); if (*pphead NULL) { *pphead newnode; } else { //找尾 SLTNode* ptail *pphead; while (ptail-next) { ptail ptail-next; } ptail-next newnode; } }我们运行一下代码结果是1-NULL结果没有任何问题通过这个头插的代码给了我们两个启发1.写代码的时候要着重思考头和尾的特殊情况2.当我们需要改变函数的实参必须要传入实参的地址2.4链表的头插思路1.创建新节点2.newnode-next*pphead3.*ppheadnewnodevoid SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode SLTBuyNode(x); newnode-next *pphead; *pphead newnode; }我们检查一下当链表为空链表时*pphead为NULLnewnode-next为NULL*pphead被赋值为新创建节点的地址没有任何问题2.5链表的尾删思路1.创建ptail找尾节点的地址2.创建prev找到尾节点前一个节点的地址3.将ptail指向的节点的空间释放掉并置为NULL4.prev-nextNULL;5.断言*pphead和pphead如果链表为空那就没有节点可以删除根据这个思路我们写出如下代码void SLTPopBack(SLTNode** pphead) { assert(pphead*pphead); SLTNode* ptail *pphead; SLTNode* prev *pphead; while (ptail-next) { prev ptail; ptail ptail-next; } free(ptail); ptail NULL; prev-next NULL; }同样的我们来思考一下如果链表只有一个节点代码可不可行ptail和prev都可以正常创建ptail-nextNULL不会进入循环ptail指向的空间被释放掉注意ptail和prev指向的是同一块空间因此prev此时是野指针对野指针使用箭头操作符访问成员元素编译器会直接报错因此如果链表只有一个节点代码不可行当只有一个节点时不用创建prev和ptail变量只需将*pphead指向的空间释放掉并置为NULL即可更正后的代码如下void SLTPopBack(SLTNode** pphead) { //链表不能为空 assert(pphead*pphead); //链表只有一个节点 if ((*pphead)-next NULL)//-优先级高于* { free(*pphead); *pphead NULL; } //链表有多个节点 else { SLTNode* ptail *pphead; SLTNode* prev *pphead; while (ptail-next) { prev ptail; ptail ptail-next; } free(ptail); ptail NULL; prev-next NULL; } }这里需要注意-优先级高于*因此需要用 先对pphead进行解引用操作2.6链表的头删思路1.链表不能为空2.创建next变量存储(*pphead)-next3.free(*pphead)4.*ppheadnextvoid SLTPopFront(SLTNode** pphead) { assert(pphead *pphead); SLTNode* next (*pphead)-next;//- 优先级高于* free(*pphead); *pphead next; }2.7链表的查找如果找到了数据为x的节点返回此节点的地址如果没找到返回空指针NULLSLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* pcur phead; while (pcur) { if (pcur-data x) return pcur; pcur pcur-next; } return NULL; }2.8在指定位置之前插入数据思路1.创建新节点2.找到pos的前一个节点prev3.prev-nextnewnode4.newnode-nextpos根据思路我们写出如下代码void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead *pphead); SLTNode* newnode SLTBuyNode(x); SLTNode* prev *pphead; while (prev-next ! pos) { prev prev-next; } prev-next newnode; newnode-next pos; }那么当链表只有一个节点的时候还能正常头插吗当链表只有一个节点的时候*ppheadposprevprev-next为NULLprev-next!pos条件为真进入循环prev被赋值为NULL。对为NULL的prev进行箭头访问数据时编译器会报错不能正常头插。因此当*ppheadpos时直接使用链表头插函数正确的代码如下void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead *pphead); assert(pos); //若pos *pphead;说明是头插 if (*pphead pos) { SLTPushFront(pphead, x); } else { SLTNode* newnode SLTBuyNode(x); SLTNode* prev *pphead; while (prev-next ! pos) { prev prev-next; } prev-next newnode; newnode-next pos; } }2.9在指定位置之后插入数据问一个问题先红色后绿色可行吗答案不可行当pos-nextnewnode时就无法通过pos-nest找到下一个节点了正确代码如下void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode SLTBuyNode(x); newnode-next pos-next; pos-next newnode; }2.10删除pos节点思路1.创建变量prev指向pos前一个节点2.prev-nextpos-next3.释放pos并置NULL根据这个思路我们写出下面代码void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead *pphead); assert(pos); SLTNode* prev *pphead; while (prev-next ! pos) { prev prev-next; } prev-next pos-next; free(pos); pos NULL; }如果链表中pos为头节点还能正常删除吗我们推测一下如果pos为头节点那么刚开始的时候*ppheadposprevprev-next为NULLprev-next!pos条件为真进入循环prev被赋值为NULL。对为NULL的prev进行箭头访问数据时编译器会报错不能正常删除。因此当*ppheadpos时直接使用链表头删函数正确的代码如下void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead *pphead); assert(pos); if (*pphead pos) { SLTPopFront(pphead); } else { SLTNode* prev *pphead; while (prev-next ! pos) { prev prev-next; } prev-next pos-next; free(pos); pos NULL; } }2.11删除pos之后的节点思路1.如果先将pos-next指向pos-next-next那么将无法找到需要删除的数据并无法将其释放如果先将pos-next释放掉那么将无法通过pos-next找到pos-next-next因此我们要先定义一个临时变量del记录pos-next2.将pos-next指向pos-next-next3.释放del并置零需要注意pos不能为最后一个节点所以需要对pos-next断言下面为正确的代码void SLTEraseAfter(SLTNode* pos) { assert(pos pos-next); SLTNode* del pos-next; pos-next pos-next-next; free(del); del NULL; }2.12销毁链表思路通过pcur遍历整个链表用next记录pcur-nest即pcur的下一个节点的地址将pcur所指向的空间释放掉后再将pcur赋值为next。当pcur为NULL时停止循环。正确代码如下void SListDesTroy(SLTNode** pphead) { assert(pphead *pphead); SLTNode* pcur *pphead; SLTNode* next *pphead; while (pcur) { next pcur-next; free(pcur); pcur next; } *pphead NULL; }结语这篇文章全文由作者手写图片由画图软件所制无AI制作希望各位博友能有所收获欢迎各位博友的讨论觉得不错的小伙伴别忘了点赞关注哦~