在数据结构中我们知道顺序表虽然尾插的时间复杂度O(1),但其无论是中间/头部的插⼊删除时间复杂度O(N)),还是增容时所面临空间的消耗都不可忽视思考我们当如何解决以上问题呢一、什么是链表其与数组的区别是什么1、链表一种物理上不连续但数据元素的逻辑顺序通过链表中指针次序所链接的存储结构2、其与数组的区别对比维度数组顺序表单链表无尾指针内存存储物理内存连续内存碎片化、不连续访问方式支持arr[i] 直接取O(1)不支持必须从头遍历O(n)头部插入/删除O(n)所有元素后移O(1)仅修改指针指向尾部插入均摊O(1)偶尔扩容拷贝O(n)每次要遍历到末尾中间插入/删除O(n)后续元素整体移位O(n)需要先找到目标位置空间开销仅存储数据额外开销小每个节点多存1个next指针额外内存开销大容量大小固定/动态扩容扩容有性能损耗无固定上限按需申请节点无需扩容3、链表结构(以单链表SLT [Single Linked Table]为例#includestdio.h#includestdlib.h// 1. 定义节点结构体structSLTNode{intdata;structSLTNode*next;};// 2. 给结构体起别名typedefstructSLTNodeNode;// 3. 给结构体指针起别名简化代码typedefstructSLTNode*PNode;采用struct关键字定义链表节点结构体节点分为两部分数据域 int data用于存储链表需要保存的数据可按需更换数据类型指针域 struct SListNode* next一级结构体指针存储下一个相邻节点的内存地址通过地址串联所有节点形成链式结构。使用typedef对结构体及结构体指针重命名Node等价于 struct SLTNode代表单个节点实体PNode等价于 struct SLTNode*代表节点指针简化链表操作代码书写。单链表逻辑特征节点内存不连续仅依靠next指针维系前后节点关系尾部节点next指针置NULL代表链表结束。二、链表的基本功能代码实现1、工具函数新建节点PNodeBuyNode(intx){PNode newNode(PNode)malloc(sizeof(Node));if(newNodeNULL){perror(malloc failed);exit(-1);}newNode-datax;newNode-nextNULL;returnnewNode;}malloc动态开辟内存初始化数据next 置空所有插入操作都会复用这个函数注意事项这里的newNode的类型是一级指针PNode即newNode存有对应节点的地址其指向一个节点2、打印链表遍历查看数据调试必备voidSLTPrint(PNode phead){PNode curphead-next;//跳过哨兵头节点while(cur!NULL){printf(%d - ,cur-data);curcur-next;}printf(NULL\n);}这里phead是一个不存有数据的指针(哨兵头节点)通过phead-next找到链表中第一个存有数据的有效节点通过cur指针不断将节点的数据打印而出并且将cur不断赋值成其所指向的下一节点的指针直至cur变为空指针 打印截止3、头插在链表最前面插入数据voidSLTPushFront(Node**pphead,LinkData x){Node*newnodeBuyNode(x);newnode-next*pphead;*ppheadnewnode;}错误写法// 错误写法无法修改外部头指针voidSLTPushFront(Node*phead,LinkData x){Node*newnodeBuyNode(x);newnode-nextphead;pheadnewnode;// 只修改函数内局部副本外部原指针完全不变}C 语言函数传参属于值拷贝传递如果头插函数仅使用一级指针Node* phead作形参当head为空指针时调用函数headNULL的值被拷贝到形参phead中此时phead也是NULL此时虽然他们的值都是NULL,但地址却是不一样的比如下方中的phead值为NULL 存有地址0x0003 自己地址为0x0002传入后会出现新的phead值NULL 存有地址0x0003但其地址可能时0x00A34、尾插在链表末尾插入数据(原理与3差不多) ps这里的ptail为为了找到原链表的尾节点不直接用*pphead为了便于寻找的同时不改动头节点voidSLTPushBack(Node**pphead,LinkData x){Node*newnodeBuyNode(x);Node*ptail*pphead;if(*ppheadNULL){*ppheadnewnode;}else{while(ptail-next){ptailptail-next;}ptail-nextnewnode;}}5、其余本质上实现原理与之前一致这里简要概述// 头删voidSLTPopFront(Node**pphead);// 尾删voidSLTPopBack(Node**pphead);// 按值查找节点Node*SLTFind(Node*phead,LinkData x);// 在pos节点前插入数据voidSLTInsert(Node**pphead,LinkData x,Node*pos);// 在pos节点后插入数据voidSLTInsertAfter(Node*pos,LinkData x);// 释放整条链表并置空头指针voidSLTDestroy(Node**pphead);各功能实现与简短说明5.1. 头删 SLTPopFrontvoidSLTPopFront(Node**pphead){Node*del*pphead;*ppheaddel-next;free(del);}说明可能修改头指针使用二级指针直接更新表头并释放原首节点。5.2. 尾删 SLTPopBackvoidSLTPopBack(Node**pphead){// 链表仅有一个节点if((*pphead)-nextNULL){free(*pphead);*ppheadNULL;return;}// 找到倒数第二个节点Node*cur*pphead;while(cur-next-next)curcur-next;free(cur-next);cur-nextNULL;}说明链表只剩单个节点时需要置空头指针必须二级指针。5.3. 查找 SLTFindNode*SLTFind(Node*phead,LinkData x){Node*curphead;while(cur){if(cur-datax)returncur;curcur-next;}returnNULL;}说明仅遍历读取数据不修改表头一级指针即可。5.4. 指定节点前插入 SLTInsertvoidSLTInsert(Node**pphead,LinkData x,Node*pos){Node*newnodeBuyNode(x);// 插入位置为头部更新表头if(*ppheadpos){newnode-next*pphead;*ppheadnewnode;return;}// 寻找 pos 的前驱节点Node*cur*pphead;while(cur-next!pos)curcur-next;cur-nextnewnode;newnode-nextpos;}说明若 pos 是头节点会改变链表头部使用二级指针。5.5. 指定节点后插入 SLTInsertAftervoidSLTInsertAfter(Node*pos,LinkData x){Node*newnodeBuyNode(x);newnode-nextpos-next;pos-nextnewnode;}说明永远不会改动链表头部仅修改节点内部 next一级指针够用。5.6. 销毁链表 SLTDestroyvoidSLTDestroy(Node**pphead){assert(pphead);Node*cur*pphead;while(cur){Node*nextcur-next;free(cur);curnext;}// 外部头指针置空防止野指针*ppheadNULL;}说明销毁后需要清空外部头指针变量必须二级指针。总结需要修改外部头指针头删、尾删、pos 前插、销毁链表 → 参数 Node**仅遍历 / 后置插入不改动表头查找、pos 后插 → 参数 Node*二级指针核心逻辑C 语言值传递只有传入指针变量的地址才能修改外部原始指针。
在数据结构中我们知道顺序表虽然尾插的时间复杂度O(1),但其无论是中间/头部的插⼊删除时间复杂度O(N)),还是增容时所面临空间的消耗都不可忽视思考我们当如何解决以上问题呢一、什么是链表其与数组的区别是什么1、链表一种物理上不连续但数据元素的逻辑顺序通过链表中指针次序所链接的存储结构2、其与数组的区别对比维度数组顺序表单链表无尾指针内存存储物理内存连续内存碎片化、不连续访问方式支持arr[i] 直接取O(1)不支持必须从头遍历O(n)头部插入/删除O(n)所有元素后移O(1)仅修改指针指向尾部插入均摊O(1)偶尔扩容拷贝O(n)每次要遍历到末尾中间插入/删除O(n)后续元素整体移位O(n)需要先找到目标位置空间开销仅存储数据额外开销小每个节点多存1个next指针额外内存开销大容量大小固定/动态扩容扩容有性能损耗无固定上限按需申请节点无需扩容3、链表结构(以单链表SLT [Single Linked Table]为例#includestdio.h#includestdlib.h// 1. 定义节点结构体structSLTNode{intdata;structSLTNode*next;};// 2. 给结构体起别名typedefstructSLTNodeNode;// 3. 给结构体指针起别名简化代码typedefstructSLTNode*PNode;采用struct关键字定义链表节点结构体节点分为两部分数据域 int data用于存储链表需要保存的数据可按需更换数据类型指针域 struct SListNode* next一级结构体指针存储下一个相邻节点的内存地址通过地址串联所有节点形成链式结构。使用typedef对结构体及结构体指针重命名Node等价于 struct SLTNode代表单个节点实体PNode等价于 struct SLTNode*代表节点指针简化链表操作代码书写。单链表逻辑特征节点内存不连续仅依靠next指针维系前后节点关系尾部节点next指针置NULL代表链表结束。二、链表的基本功能代码实现1、工具函数新建节点PNodeBuyNode(intx){PNode newNode(PNode)malloc(sizeof(Node));if(newNodeNULL){perror(malloc failed);exit(-1);}newNode-datax;newNode-nextNULL;returnnewNode;}malloc动态开辟内存初始化数据next 置空所有插入操作都会复用这个函数注意事项这里的newNode的类型是一级指针PNode即newNode存有对应节点的地址其指向一个节点2、打印链表遍历查看数据调试必备voidSLTPrint(PNode phead){PNode curphead-next;//跳过哨兵头节点while(cur!NULL){printf(%d - ,cur-data);curcur-next;}printf(NULL\n);}这里phead是一个不存有数据的指针(哨兵头节点)通过phead-next找到链表中第一个存有数据的有效节点通过cur指针不断将节点的数据打印而出并且将cur不断赋值成其所指向的下一节点的指针直至cur变为空指针 打印截止3、头插在链表最前面插入数据voidSLTPushFront(Node**pphead,LinkData x){Node*newnodeBuyNode(x);newnode-next*pphead;*ppheadnewnode;}错误写法// 错误写法无法修改外部头指针voidSLTPushFront(Node*phead,LinkData x){Node*newnodeBuyNode(x);newnode-nextphead;pheadnewnode;// 只修改函数内局部副本外部原指针完全不变}C 语言函数传参属于值拷贝传递如果头插函数仅使用一级指针Node* phead作形参当head为空指针时调用函数headNULL的值被拷贝到形参phead中此时phead也是NULL此时虽然他们的值都是NULL,但地址却是不一样的比如下方中的phead值为NULL 存有地址0x0003 自己地址为0x0002传入后会出现新的phead值NULL 存有地址0x0003但其地址可能时0x00A34、尾插在链表末尾插入数据(原理与3差不多) ps这里的ptail为为了找到原链表的尾节点不直接用*pphead为了便于寻找的同时不改动头节点voidSLTPushBack(Node**pphead,LinkData x){Node*newnodeBuyNode(x);Node*ptail*pphead;if(*ppheadNULL){*ppheadnewnode;}else{while(ptail-next){ptailptail-next;}ptail-nextnewnode;}}5、其余本质上实现原理与之前一致这里简要概述// 头删voidSLTPopFront(Node**pphead);// 尾删voidSLTPopBack(Node**pphead);// 按值查找节点Node*SLTFind(Node*phead,LinkData x);// 在pos节点前插入数据voidSLTInsert(Node**pphead,LinkData x,Node*pos);// 在pos节点后插入数据voidSLTInsertAfter(Node*pos,LinkData x);// 释放整条链表并置空头指针voidSLTDestroy(Node**pphead);各功能实现与简短说明5.1. 头删 SLTPopFrontvoidSLTPopFront(Node**pphead){Node*del*pphead;*ppheaddel-next;free(del);}说明可能修改头指针使用二级指针直接更新表头并释放原首节点。5.2. 尾删 SLTPopBackvoidSLTPopBack(Node**pphead){// 链表仅有一个节点if((*pphead)-nextNULL){free(*pphead);*ppheadNULL;return;}// 找到倒数第二个节点Node*cur*pphead;while(cur-next-next)curcur-next;free(cur-next);cur-nextNULL;}说明链表只剩单个节点时需要置空头指针必须二级指针。5.3. 查找 SLTFindNode*SLTFind(Node*phead,LinkData x){Node*curphead;while(cur){if(cur-datax)returncur;curcur-next;}returnNULL;}说明仅遍历读取数据不修改表头一级指针即可。5.4. 指定节点前插入 SLTInsertvoidSLTInsert(Node**pphead,LinkData x,Node*pos){Node*newnodeBuyNode(x);// 插入位置为头部更新表头if(*ppheadpos){newnode-next*pphead;*ppheadnewnode;return;}// 寻找 pos 的前驱节点Node*cur*pphead;while(cur-next!pos)curcur-next;cur-nextnewnode;newnode-nextpos;}说明若 pos 是头节点会改变链表头部使用二级指针。5.5. 指定节点后插入 SLTInsertAftervoidSLTInsertAfter(Node*pos,LinkData x){Node*newnodeBuyNode(x);newnode-nextpos-next;pos-nextnewnode;}说明永远不会改动链表头部仅修改节点内部 next一级指针够用。5.6. 销毁链表 SLTDestroyvoidSLTDestroy(Node**pphead){assert(pphead);Node*cur*pphead;while(cur){Node*nextcur-next;free(cur);curnext;}// 外部头指针置空防止野指针*ppheadNULL;}说明销毁后需要清空外部头指针变量必须二级指针。总结需要修改外部头指针头删、尾删、pos 前插、销毁链表 → 参数 Node**仅遍历 / 后置插入不改动表头查找、pos 后插 → 参数 Node*二级指针核心逻辑C 语言值传递只有传入指针变量的地址才能修改外部原始指针。
