企业官网建设流程全解析

我们知道，在使用顺序表的时候，查找某一元素的时间复杂度是O(1)，但在插入和删除元素时的时间复杂度为O(n)，而且空间放满了就需要进行扩容。为了提高增删查改的效率，我们引入了一种新的存储结构 —— 链表来存储线性表。

链表

链表的数据在内存中的存储是不连续的，每个元素之间靠指针建立起连接。也就是说，链表的连续不是靠存储结构体现的，而是靠元素之间的逻辑关系来体现的。
怎么体现的呢？我们先来看一个图：

这里的plist是指向第一个元素的头指针，每个元素里不仅存放数据，还存放了指向下一个元素的指针，这就是链表的逻辑结构。这里的每一个元素称为一个结点。每个结点独立地开辟一块内存空间。
而在存储结构中，我们可以很直观地发现链表中元素的存储不是连续的：

为了更深入的理解链表，这里我们先介绍一个最基础的链表：单链表。

单链表

单链表中每个结点包含两个部分：数据和指向后继元素的指针。指向第一个结点的指针叫做头指针，尾指针指向空。
单链表结点的定义方式如下：

typedefintLDataType;//结点存放的数据类型的重命名typedefstructListNode{LDataType data;//结点数据structListNode*next;//指向下一个结点的指针}LNode,*Linklist;//结构体的重命名，方便使用

单链表又分为两种，一种是不带哨兵位的头指针，另一种是带哨兵位的头指针。
不带哨兵位的头指针：头指针直接指向第一个结点。

带哨兵位的头指针：头指针指向哨兵结点，该结点不存放数据，哨兵结点指向的下一个结点才是第一个结点。

这里我们选择实现带哨兵位的头指针的单链表的接口函数，包括初始化、查找、插入、删除等函数。
我们添加一个头文件命名为List.h，用来声明结构体、函数和包含各种库函数的头文件，一个源文件List.c，用来实现单链表的各种接口函数，一个源文件test.c，方便简单测试。

接口函数的定义

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefintLDataType;//结点存放的数据类型的重命名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 个位置结点不为空。

头删和尾删可以复用该函数：

简单测试一下：

说明代码逻辑没什么问题。

销毁

销毁单链表就是从头结点开始把所有结点释放掉：

以上就是单链表的实现过程了。如有错误欢迎指正~