数据结构：线性表之单链表

我们知道在使用顺序表的时候查找某一元素的时间复杂度是O(1)但在插入和删除元素时的时间复杂度为O(n)而且空间放满了就需要进行扩容。为了提高增删查改的效率我们引入了一种新的存储结构 —— 链表来存储线性表。链表链表的数据在内存中的存储是不连续的每个元素之间靠指针建立起连接。也就是说链表的连续不是靠存储结构体现的而是靠元素之间的逻辑关系来体现的。怎么体现的呢我们先来看一个图这里的plist是指向第一个元素的头指针每个元素里不仅存放数据还存放了指向下一个元素的指针这就是链表的逻辑结构。这里的每一个元素称为一个结点。每个结点独立地开辟一块内存空间。而在存储结构中我们可以很直观地发现链表中元素的存储不是连续的为了更深入的理解链表这里我们先介绍一个最基础的链表单链表。单链表单链表中每个结点包含两个部分数据和指向后继元素的指针。指向第一个结点的指针叫做头指针尾指针指向空。单链表结点的定义方式如下typedefintLDataType;//结点存放的数据类型的重命名typedefstructListNode{LDataType data;//结点数据structListNode*next;//指向下一个结点的指针}LNode,*Linklist;//结构体的重命名方便使用单链表又分为两种一种是不带哨兵位的头指针另一种是带哨兵位的头指针。不带哨兵位的头指针头指针直接指向第一个结点。带哨兵位的头指针头指针指向哨兵结点该结点不存放数据哨兵结点指向的下一个结点才是第一个结点。这里我们选择实现带哨兵位的头指针的单链表的接口函数包括初始化、查找、插入、删除等函数。我们添加一个头文件命名为List.h用来声明结构体、函数和包含各种库函数的头文件一个源文件List.c用来实现单链表的各种接口函数一个源文件test.c方便简单测试。接口函数的定义#pragmaonce#includestdio.h#includestdlib.h#includeassert.htypedefintLDataType;//结点存放的数据类型的重命名typedefstructListNode{LDataType data;//结点数据structListNode*next;//指向下一个结点的指针}LNode,*Linklist;//结构体的重命名方便使用//申请一个结点LNode*BuyNewNode(LDataType x);//初始化单链表LNode*ListInit();//在单链表中查找元素x找到则返回该结点的位置i反之返回-1LNode*ListLocateElem(LNode*L,LDataType x);//查找单链表中第i个位置的数据LDataTypeListGetElem(LNode*L,inti);//打印单链表voidListPrint(LNode*L);//单链表的长度intListSize(LNode*L);//在单链表第i个位置插入元素xvoidListInsert(LNode*L,inti,LDataType x);//删除单链表第i个位置的元素voidListDelete(LNode*L,inti);//销毁单链表voidListDestroy(LNode*L);//头插和尾插voidListInsertFront(LNode*L,LDataType x);voidListInsertBack(LNode*L,LDataType x);//头删和尾删voidListDeleteFront(LNode*L);voidListDeleteBack(LNode*L);下面我们来实现这些接口函数。初始化初始化单链表对于带有哨兵位头结点的单链表来说就是要拿到这个哨兵结点的地址。那么我们在此之前还需要定义一个函数用来申请创建结点我们用malloc动态申请能存放一个结点的空间再用NewNode接收这个空间申请成功则初始化这个空间。注意我们不能直接创建一个结点LNode NewNode因为这样创建出来的结点是局部变量出函数后该结点的内存就会被释放掉我们得到的结点就是野指针越界访问了。用malloc的话不手动free释放该结点就一直存在。然后我们就可以实现初始化单链表的函数了这里传-1过去是标记该结点是哨兵结点然后把哨兵结点返回来。如果我们想通过让外部传进来的单链表指向该哨兵结点然后不返回任何值呢上面这个代码是错的如果我们想改变指针L的内容的话就需要对二级指针解引用来改变这个指针的内容传址调用不然无法实现该功能。我们的初始化函数也可以这么写。查找查找分为两种一种是按值查找在单链表中找元素x找到则返回该结点的位置 i 找不到则返回-1.另一种是按下标查找返回位置 i 的结点中的数据。我们先来看按值查找我们把要查找的值x传过去遍历一遍单链表找到则返回该结点位置 i 遍历结束说明没有找到则返回-1.第二种是按下标 i 查找这种查找我们额外需要确保传进来的下标位置 i 的有效性。这里第一层assert断言确保 i 是个≥0的值然后循环条件多加了一个确保结点不为空。后面加assert断言确保 i 没有越界超过结点数。超过就说明传进来的 i 有问题。打印打印很简单就是把每个结点的数据按顺序遍历打印一遍就好了。插入插入实际上就是在某个位置插入一个新结点让该位置的前一个结点指向这个新结点然后让这个新结点指向前一个结点原来指向的结点。根据图我们可以分析出来要在第 i 个位置插入元素我们就要先找到第 i -1个位置的结点。插入分为三种头插、尾插、中间插。对于尾插和中间插都是常见情况但头插需要额外考虑。我们头插是插入在哨兵结点后面的之前我们每次都是先从第一个结点开始遍历的所以在这个地方我们要从哨兵结点开始遍历多遍历一遍原来第一个结点开始从0遍历到 i -1要往后找三个现在是从哨兵结点开始找多一次所以是从-1开始遍历到 i -1。这样就可以解决这三种不同的情况了头插和尾插就可以复用该函数这里ListSize是求单链表长度的函数很简单这里就直接给出来了我们简单测试一下说明代码没问题。删除知道插入怎么实现后删除就更简单了要删除第 i 个位置的元素然后让 第 i -1个结点指向第 i 个位置的结点的下一个结点再把第 i 个结点free释放掉就好了。需要确保的是第 i 个位置结点不为空。头删和尾删可以复用该函数简单测试一下说明代码逻辑没什么问题。销毁销毁单链表就是从头结点开始把所有结点释放掉以上就是单链表的实现过程了。如有错误欢迎指正~