数据结构笔记：线性表走起！（链式存储结构简介）

每日一句，送给最珍贵的你：

草在结它的种子 风在摇它的叶子 我们站着，不说话 -《门前》顾城

上次我们学到了线性表的顺序存储结构。

往期推荐：数据结构：线性表走起！（顺序存储结构）

每日推荐：

关于上次讲的顺序存储结构，我们都知道它是有缺点的，最大的缺点便是在插入和删除数据时需要移动大量元素，显然在运行时需要耗费大量的时间。

那怎么解决呢？首先，我们知道顺序存储结构就和有序排队差不多，即它们两个相邻数据之间是存在邻里关系的，在内存中的位置也是挨着的，之间并没有空隙，也就造成了在插入时无法介入，而删除后，又会造成空隙，导致效率低下。

在链式存储结构中便会解决上述问题，链式存储结构和顺序存储结构都是各有优点和缺点，谈不上谁比谁好，离开实际环境谈好坏，都是**。关于各种优缺点在后面会给大家介绍到。

线性表链式存储结构定义

书上的定义挺繁琐的，简单来说便是某个元素指向另一个元素，然后另一个元素指向下一个元素，这样每个元素之间自然而然形成了某种关系， 某种链表也就形成啦，如下：

链式存储结构存在以下特点：用一组任意的存储单元存储线性表中的数据元素，这组存储单元可以是连续的，也可以是不连续的，也就是说，这些数据元素可以存在内存未被占用的情况。

链式存储结构和顺序存储结构有很大不同的是一点是数据元素不仅仅只存元素信息，还要存储它的后继元素的存储地址，如下图所示：

这里把存储数据元素的域称为数据域，把存储直接后继元素的域称为指针域。指针域中存储的信息称为指针或链，这两部分信息组成数据元素ai的存储映像，称之为结点。当有n个结点时，即组成了线性表的链式存储结构，又因为每个结点中只包含一个指针域，所以叫做单链表。

我们也把链表中第一个结点的存储位置叫做头指针，那么链表的存储也必须是从头指针开始存储的啦，...当指针指向最后一个元素时，那么最后一个数据元素的指针并不会消失，小编好像也没有说会消失哦

。我们规定的线性链表的最后一个结点指针为”空“（通常用“NULL”或“^”符号表示）。

在第一个头指针的结点之前我们会另外设置一个结点，称为头结点，在这个头结点的数据域中可以不存储任何信息，哈哈哈，小编也不知为啥它会有这个特权呢？

当然在头结点的数据域也是可以存储信息的，比如线性表的长度等附加信息（一般无意义），头结点的指针域指向第一个结点的指针。

关于小编存在的几点疑问：

1. 头结点的指针域是头指针吗？ ：网上说法不一，按照个人逻辑，头指针是指向第一个结点的，那么头结点便是第一个结点，即头指针是指向第一个头结点的数据域。在单链表中可以没有头结点（可有可无，尽量还是写为好），但不能没有头指针。
2. 头结点可以不写吗？ 这里简单介绍头结点的作用：1.防止单链表是空而设，当链表为空时,带头结点的头指针就指向头结点，如果当链表为空时,单链表没有带头结点,那么它的头指针就为NULL。 2.方便单链表的特殊操作，能有效减少代码量，当插入在表头或者删除第一个结点时不用考虑特殊情况，删除或插入用户的第一个节点的值和删除或插入中间的值用一样的代码，这就保持了单链表操作的统一性! 3.单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理也统一了，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会。 4.总的来说，没有头结点对第一个结点的操作大多和中间结点不太一样，很多操作都要考虑特殊情况，有头结点的话就不必考虑那么多，也不容易出现代码错误。
3. 头结点的数据域可以存放有效数据嘛？ ：只能说头结点的数据域并不是不能填写，而是如果填写实际有效数据后那么头结点的意义便荡然无存了...但是还是可以填写如结点数（在实际有效数据中可有可无）等等的数据。

在单链表中，我们可以用C语言的结构指针来描述：

typedef strcut Node{    //线性表单链表的存储结构
ElemType data;
strcut Node *Next;
}Node;
typedef strcut Node *LinkList;    //定义LinkList

由上面的代码可知，结点由存放数据元素的数据域和存放后继节点指针的指针域组成。

假设p是指向线性表的第i个元素的指针，那么p->data便是结点ai的数据域，p->next便是结点ai的指针域，那么p->next指向谁呢？当然是指向第i+1个元素啦。p->next->data即是结点第a(i+1)的数据域啦！

未完待续...