数据结构-基础篇-链表带入主题1 链表到底在解决什么1.1 从顺序表的短板说起1.2 链表的优势和代价2 我们这次实现的单链表2.1 结点长什么样2.2 带头结点不是“第一个有效数据”3 先把工程分清楚4 代码实现顺着指针走4.1 创建一个新结点4.2 初始化先造一个头结点4.3 按值查找找到了就把结点地址交出来4.4 按下标查找为什么循环有两个条件4.5 指定位置插入两句代码的顺序不能反5 用当前接口快速测一下尾带入主题我在上期讲顺序表时拿贪吃蛇举例蛇身是一串有先后关系、还会不断增删的数据。顺序表就像小朋友排队大家挨着站但如果中间有人想插队后面的人都得往旁边挪。那么问题来了有没有一种结构不要求大家挤在同一排座位上但又能知道下一个人是谁有这就是今天的主角——链表。我上期那个“我的世界藏宝图”的说法还能继续用一个宝箱里不仅放着自己的数据还放着下一张藏宝图。你顺着地图一直找就能把所有宝箱都找到。1 链表到底在解决什么1.1 从顺序表的短板说起顺序表把数据放在一段连续的内存里所以想拿下标为i的数据时直接arr[i]就行时间复杂度是O(1)。但它也有自己的脾气中间插入一个元素后面的元素通常都得往后挪中间删除一个元素后面的元素通常都得往前补容量满了还要扩容运气不好时得重新找一块更大的连续空间再把旧数据搬过去。链表的想法很直接不强求结点在物理内存上挨在一起谁的后面是谁由指针记下来。顺序表 [10][20][30][40] 内存地址连续 单链表 [10 | next] --- [20 | next] --- [30 | next] --- NULL 每个结点实际可以分散在不同位置所以“非连续、非顺序”说的是物理存储位置链表在逻辑上依旧很有顺序还是10 - 20 - 30 - 40。1.2 链表的优势和代价先别急着说“链表完爆顺序表”数据结构没有谁全面碾压谁都是看场景。操作顺序表单链表按下标访问第i个元素O(1)O(n)要顺着next走过去已知目标位置的前驱后插入/删除通常要搬移元素改几个指针即可O(1)查找某个值O(n)O(n)空间申请一次申请一段连续空间用一个结点申请一个结点链表不需要整体扩容想多放一个数据就申请一个新结点。但链表不能写L[3]直接跳到第三个数据因为结点不保证连续只能从头顺着地图找。每个结点还要额外存一个指针所以也不是“零成本”。做题时别只背“链表插入删除快”。如果要插到第i个位置你仍要先找到第i - 1个结点这一步本身就是O(n)。2 我们这次实现的单链表2.1 结点长什么样先看我项目里List.h的核心定义typedefintLDataType;typedefstructListNode{LDataType data;// 存储数据structListNode*next;// 存放后继结点地址}LNode,*LinkList;LDataType是给数据类型起的“昵称”。现在存的是int以后如果想存char或其他类型集中改这一处即可。data是结点真正的数据域。next是指针域存下一个结点的地址。struct ListNode*不能只写成LNode*因为此时LNode这个别名还没定义完结构体名字struct ListNode则已经可用。LNode, *LinkList表示LNode是结点类型而LinkList等价于LNode*。后面的代码里我直接使用LNode*看起来更直白一点。关于自引用的问题请看自引用2.2 带头结点不是“第一个有效数据”本项目实现的是带头结点的单链表。刚初始化时先申请一个头结点它的data这里放的是-1但这个值不算链表里的有效数据。L │ ▼ [头结点 | next] --- [10 | next] --- [20 | next] --- NULL data -1 有效数据 有效数据为什么明明可以少申请一个结点还要多放一个头结点因为它能让头插、头删以及普通位置的操作尽量走同一套逻辑。例如在下标0插入时不带头结点的链表要修改调用者手中的头指针往往需要二级指针带头结点时直接改L-next就够了。牺牲一个结点的空间换来更统一、更不容易绕晕的代码我觉得这笔买卖挺值。有些写法会用头结点的data存链表长度。这里不这样做data的类型可能会改成char、double等拿它强行存长度既不通用也可能溢出。3 先把工程分清楚和上期顺序表一样别把所有东西塞进一个.c文件。当前项目分成三个文件文件负责什么List.h结点结构、类型别名与函数声明List.c链表函数的具体实现Test.cmain函数后续在这里测试接口头文件中目前声明的接口如下// 创建一个新结点LNode*BuyListNode(intdata);// 初始化链表LNode*ListInit();// 按照值查找LNode*ListLocateElem(LNode*L,LDataType x);// 按下标查找LNode*ListGetElem(LNode*L,inti);// 在下标 i 处插入数据 xvoidListInsert(LNode*L,inti,LDataType x);这篇先把当前工程已经写好的接口吃透。打印、删除、销毁、头尾插删这些等代码真正补上后再单独接着写别把“课件有”当成“我的工程已经有”。4 代码实现顺着指针走4.1 创建一个新结点只要链表要增加结点就不能在函数里随便定义一个局部变量函数结束后局部变量就没了链表手里只会剩下一张失效藏宝图。所以要在堆区用malloc申请空间。LNode*BuyListNode(intdata){LNode*BuyNode(LNode*)malloc(sizeof(LNode));if(!BuyNode){printf(申请失败\n);exit(-1);}BuyNode-datadata;BuyNode-nextNULL;returnBuyNode;}拆开来看malloc(sizeof(LNode))申请刚好放得下一个结点的空间。if (!BuyNode)malloc失败会返回NULL此时继续用BuyNode-data就是在空指针上操作会出事。BuyNode-data data给新结点装入数据。BuyNode-next NULL新结点暂时没有后继先让它指向空。return BuyNode把这个新结点的地址交给调用者。这里统一封装一个申请结点的函数后面初始化和插入都能复用也不用每次都重复写“申请失败怎么办”。4.2 初始化先造一个头结点LNode*ListInit(){LNode*NodeBuyListNode(-1);returnNode;}这个函数只干一件事创建并返回一个头结点。因为BuyListNode已经把next初始化为NULL所以刚创建的链表状态就是L --- [头结点 | NULL]调用时记得把返回值接住LNode*LListInit();你现在Test.c里只有一行ListInit();这样创建出的头结点没有指针保存后续既不能继续操作也无法释放。写测试时应该像上面那样交给L管起来。4.3 按值查找找到了就把结点地址交出来比如链表有效数据是10 - 20 - 30我们想找值为20的结点不是从L开始比较因为L指向的是头结点头结点不算有效数据。LNode*ListLocateElem(LNode*L,LDataType x){assert(L);LNode*curL-next;while(cur){if(cur-datax){returncur;}curcur-next;}returnNULL;}assert(L)开发调试时确保传进来的头指针不是空指针。它不是给用户输入做错误处理的万能盾牌在定义了NDEBUG的发布构建中断言会被关闭。cur是current的缩写表示当前走到的结点。cur L-next跳过头结点从第一个有效结点开始。while (cur)只要当前结点不是NULL就继续找。找到第一个相等数据后直接返回结点地址找完整条链还没有就返回NULL。使用时一定判断返回值别一上来就p-dataLNode*posListLocateElem(L,20);if(pos){printf(找到了%d\n,pos-data);}else{printf(没找到\n);}链表没有下标直达能力所以最坏情况下要走完整条链时间复杂度是O(n)。4.4 按下标查找为什么循环有两个条件LNode*ListGetElem(LNode*L,inti){assert(L);assert(i0);intj0;LNode*iNodeL-next;while(iNode!NULLji){j;iNodeiNode-next;}returniNode;}这里的下标从0开始头结点 - [10] - [20] - [30] - NULL 0 1 2假设要找下标2iNode先指向10每循环一次就沿next往后走一格同时j加一走两次后它正好指向30。while(iNode ! NULL j i)两个条件一个都不能少j i到了目标下标就停iNode ! NULL如果i比链表实际长度还大不能继续访问iNode-next。所以当前实现对于过大的下标会返回NULL调用处也要先判断LNode*posListGetElem(L,2);if(pos){printf(下标 2 的数据是%d\n,pos-data);}这也是链表和顺序表最明显的不同顺序表的arr[2]可以直接算地址链表必须一个结点一个结点地走因此按下标查找是O(n)。4.5 指定位置插入两句代码的顺序不能反接口语义是在有效数据的下标i位置插入x。voidListInsert(LNode*L,inti,LDataType x){assert(i0);assert(L);LNode*i_1NodeL;intj-1;while(ji-1i_1Node){j;i_1Nodei_1Node-next;}assert(i_1Node);LNode*NewNodeBuyListNode(x);NewNode-nexti_1Node-next;i_1Node-nextNewNode;}插入第i个位置前必须先找到它前面的第i - 1个结点。这里有头结点帮忙所以把头结点视作“下标-1的结点”最容易理解i_1Node Lj -1一开始就在头结点当i 0时不用进入循环i_1Node正好就是头结点完成头插当i 1时走一步i_1Node正好指向下标0的有效结点当i等于当前长度时找到最后一个有效结点后插入完成尾插。假设原链表是头结点 - [10] - [30] - NULL现在在下标1插入20i_1Node指向10。最关键的是下面两句NewNode-nexti_1Node-next;i_1Node-nextNewNode;变化过程是第一句10 - 30 变成 10 - 30 20 -----^ 第二句10 的 next 改为 20 头结点 - [10] - [20] - [30] - NULL为什么不能交换顺序如果先写i_1Node-next NewNode;原来10指向30的那条线就断了而新结点的next还是NULL此时你已经找不到30了。所以链表题卡住时先画结点和箭头再写代码。尤其是插入、删除真正容易错的不是malloc而是指针改动的先后顺序。当前实现会用assert(i_1Node)拦住超过“末尾后一位”的非法插入位置。正常情况下允许的下标范围是0到当前链表长度含长度本身。5 用当前接口快速测一下把Test.c临时改成下面这样就能把现有接口串起来看#includeList.hintmain(){LNode*LListInit();ListInsert(L,0,10);// 10ListInsert(L,1,30);// 10 - 30ListInsert(L,1,20);// 10 - 20 - 30LNode*byValueListLocateElem(L,20);if(byValue){printf(按值找到%d\n,byValue-data);}LNode*byIndexListGetElem(L,2);if(byIndex){printf(下标 2 是%d\n,byIndex-data);}return0;}预期输出为按值找到20 下标 2 是30尾链表不是“数据没有顺序”而是把数据之间的顺序从连续内存换成了next指针来维护。带头结点的单链表让头部操作和普通操作统一很多初学时特别推荐先把这一版吃透。单链表最核心的习惯就是沿next遍历改指针前先想清楚会不会丢掉后面的链。这次的代码已经完成了创建、初始化、两种查找和指定位置插入下一步就可以自然接上打印、删除、销毁以及头插头删、尾插尾删。链表刚开始看像一堆地址真正画两次、改两次指针后就会发现它不是玄学就是一张一张藏宝图接起来而已。