顺序存储结构不足的解决办法
通过 线性表之数组 这篇文章的介绍，我们知道线性表的顺序存储是有缺点的，最大的缺点就是 插入、删除时需要移动大量元素，对于像数组这样在编程中常用的数据结构显然会产生很低的效率，那么有什么比较好的方法解决吗?
俗话说 解铃还须系铃人，要想解决这个问题，我们必须要了解产生这个问题的原因
为什么当插入、删除时需要移动大量元素，仔细分析后我们发现除了头、尾元素其他每两个相邻元素之间没有空隙，因为线性表的顺序存储内存地址是连续的，所以就没办法快速的插入，而当删除后，当中就会留有空隙，自然就需要弥补，这就是问题所在。
聪明的计算机大师们早为我们提供了一个很好的解题思路：如果要不想在插入、删除时移动大量元素，那么我们就让每两个相邻元素之间留有 足够多的空间，那么这个足够多的空间是多少呢?足够多那肯定不会再是一个固定的值，既然这样我们就干脆不再考虑相邻位置了，哪里有空位就到哪里，只需要让每个元素知道它的下一个元素在哪里，这样，我们可以在第一个元素时，就能知道第二个元素的位置(内存地址)，而找到它；在第二个元素时，再找到第三个元素的位置(内存地址)。这样所有的元素我们就能通过遍历找到了
线性表链式存储结构的定义
线性表的链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着这些数据元素可以存在内存未被占用的任意位置
以前在线性表的顺序存储结构中，每个数据元素只需要存储数据元素信息就可以了。现在在线性表的链式存储结构中，除了要存储数据元素信息外，还要存储它直接后继元素的内存地址
因此，为了表示每个数据元素 ai 和它直接后继元素 ai + 1 的逻辑关系,对于数据元素 ai 除了要存储它自身的数据信息外，还要存储其直接后继元素的内存地址。我们把存储数据元素信息的域称为 数据域，存储其直接后继元素内存地址的域称为 指针域。指针域中存储的信息称为 指针或链。这两部分信息组成数据元素 ai 的存储映像，称为 结点(node)
n 个结点(数据元素 ai 的存储映像)链接成一个链表，即为线性表(a1、a2、a3......ai)的链式存储结构，因为此链表的每个结点只包含一个指针域，所以叫做 单链表。单链表正是通过每个结点的指针域将线性表的数据元素按照其逻辑次序链接在一起，如下图：
QQ20200627-171832@2x.png
我们把链表中第一个结点的内存地址称为 头指针，整个链表的存取就必须从头指针开始进行了，之后的每一个结点其实就是上一个结点指针域中存储的指针指向的位置，而对于链表中的最后一个结点是没有后继元素的，所以我们规定，线性表的最后一个结点指针为 空(通常用 NULL 或者 ^ 符号表示)
QQ20200627-172916@2x.png
有时候为了更加方便对链表进行操作，我们会在单链表的第一个结点前附设一个结点，称为 头结点。头结点的数据域可以不存储任何数据元素信息，但是也可以存储线性表的长度等附加信息，头结点的指针域存储的指针是第一个结点的内存地址
QQ20200627-174012@2x.png
注意：如果单链表是空表，那么头结点的指针域为 空
线性表链式存储结构示意
我们一般使用如下示意图表示单链表的存储结构：
QQ20200627-233931@2x.png
若带有头结点的单链表则使用如下图表示：
QQ20200627-234059@2x.png
空链表使用如下图表示：
QQ20200627-234154@2x.png
根据前面的介绍我们知道 结点(node)是由存储数据元素的数据域和存放其直接后继结点内存地址的指针域两部分组成。 假设 p 是指向单链表中第 i 个元素的指针，则该结点 ai 的数据域我们可以用 p->data 来表示，p->data 的值是一个数据元素，结点 ai 的指针域可以用 p->next 表示，p->next 的值是一个指针。p->next 指向谁呢?当然是指向第 i + 1 个元素，即指向 ai + 1 的指针。也就是说 p->data = ai，p->next->data = ai + 1，如下图所示：
QQ20200627-235234@2x.png
在 C 语言中可用结构体指针来描述单链表：
typedef struct node
{
ElemType data;
struct node *next;
}Node,LinkList;
从这个结构定义中更能清晰的看出，结点是由存放数据元素的数据域与存放后继结点地址的指针域组成
单链表的读取
在线性表的顺序存储结构中，我们要想计算任意一个元素的内存地址是很容易的，因为线性表的顺序存储结构中内存地址是连续的。但是在单链表中由于存储单元可能不是连续的，所以我们要想知道第 i 个元素的内存地址，就必须要从头指针开始。因此，对于单链表要想实现获取第 i 个元素数据，在算法上相对麻烦一些
获取单链表第 i 个数据的算法思路：
1.声明一个结点 cur，让其指向单链表的第一个结点，初始化 j 为 1
2.当 j < i 时，就遍历单链表，让 cur 的指针向后移动，不断指向下一个结点，j 累加 1
3.若到链表末尾 cur 为空，则第 i 个元素不存在
4.反之查找成功，并返回该节点的数据
实现代码算法如下：
Status getElement(LinkList *pList,int i,ElemType *e) {
// 判断单链表是否存在
if(!pList) {
printf("list not exist\n");
return FALSE;
}
// 只能获取位置 1 以及以后的元素
if(i < 1) {
printf("i is invalid\n");
return FALSE;
}
// 声明一个结点 cur,让其指向单链表的第一个结点
Node *cur = pList->next;
for(int j = 1;j < i;j+) {// j 为计数器，初始化为1
cur = cur->next;
if(cur == NULL) {
printf("dont find cur\n");
return FALSE;
}
}
// 获取第i个结点的数据
*e = cur->data;
return TRUE;
}
从上面的解题思路中可知，要想获取第 i 个元素数据，需要从头开始直至第 i 个元素为止。那么，这个算法的时间复杂度就取决于 i，最好的情况是第一个结点就是我们所要查找的数据即 i = 1,时间复杂度为 O(1)，最坏的情况是我们要查找的元素在单链表的最后一位或不在单链表中，那么此时需要遍历 n 次，此时时间复杂度为 O(n)
在单链表中获取第 i 个元素数据其核心思想是 工作指针后移，从上述介绍中我们能感受到单链表并不适合查找，但是事物都是有两面性的，根据前面的介绍我们也能想到单链表在 数据插入、删除方面效率应该比较高，下面我们来看下单链表的插入与删除
单链表的插入与删除
单链表的插入
假设存储数据元素 e 的结点为 s,现在我们要把结点 s 插入到 p、p->next 之间，我们该如何插入呢？
注意：根据前面的介绍可知道 p->next 的值是一个指针，指向的是结点 p 的直接后继元素 ai + 1
QQ20200628-122843@2x.png
要想实现上述元素插入，我们需要将 p->next、s->next 的值做一点改动，现在 p->next、s->next 指向的都是其各自的直接后继指针，现在我们 把 p 的后继结点改成 s 的后继结点，再把 s 变成 p 的后继结点，伪代码实现如下：
s->next = p->next;p->next=s;
QQ20200628-152732.png
试想一下，如果我们把上面代码的顺序调整一下会怎么样?
调整后的顺序是：把 s 变成 p 的后继结点，再把 p 的后继结点变成 s 的后继结点
p->next = s;s->next = p->next;
仔细分析下，如果先把 s 变成 p 的后继结点，那么这时 p->next 指向的就是结点 s,即 p->next 是结点 s 在内存中的地址，则 s->next = p->next 就相当于 s->next = s，所以这个执行顺序是不能调整的，插入结点 s 之后如下图所示：
QQ20200628-154752.png
单链表第 i 个位置之前插入新结点的算法思路：
1.声明一个节点 front ，让结点 front 指向单链表的头结点，初始化 j 从 1 开始
2.当 j < i 时，就遍历单链表，让结点 front 的指针向后移动，不断指向下一个结点，j 累加 1
3.若到链表末尾 front 为空，则说明第 i 个元素不存在
4.否则查找成功，在系统中创建一个新结点 pTemp
5.将数据元素 e 赋值给 pTemp->data
6.执行单链表插入标准语句 pTemp->next = front->next;front->next = pTemp;
7.返回成功
实现代码如下：
Status insertList(LinkList *pList,int i,const ElemType e) {
// 判断单链表是否存在
if(!pList) {
printf("list not exist\n");
return FALSE;
}
// 只能在位置 1 以及后面插入
if(i < 1) {
printf("i is invalid\n");
return FALSE;
}
// 在这里我们声明一个结点 front,让其指向单链表 pList 的头结点
Node *front = pList;
for(int j = 1;j < i;j++) {// j 为计数器，初始化为1
front = front->next;
if(front == NULL) {
printf("dont find front\n");
return FALSE;
}
}
// 创建一个新结点，存放要插入的新元素
Node *temp = (Node *)malloc(sizeof(Node));
if(!temp){
printf("malloc error\n");
}
temp->data = e;
// 插入新结点
temp->next = front->next;
front->next = temp;
return TRUE;
}
注意：单链表插入新结点实现的难点在于如何找到 i 位置的前一个结点
头部插入和尾部插入
单链表的头部插入就是新结点始终在第一个结点的位置，这种算法简称为 头插法，如下图所示：
QQ20200629-190756@2x.png
代码实现如下：
Status inserListHead(LinkList *pList,cosnt ElemeType e) {
// 判断单链表 pList 是否为空
if(!pList) {
printf("list not exist");
return FALSE;
}
// 声明一个新结点,让该结点指向单链表的头结点
Node *head = pList;
// 创建一个临时结点,存储新插入的元素
Node *temp = (Node *)malloc(sizeof(Node));
if(!temp) {
printf("malloc error");
}
temp->data = e;
// 执行插入操作
temp->next = head->next;
head->next = temp;
return TRUE;
}
单链表的尾部插入就是将新结点插入到尾部结点后面，这种简称 尾插法，如下图所示：
QQ20200701-201905.png
代码实现如下：
Status insertListTail(LinkList *pList,const ElemeType e) {
// 判断单链表是否为空
if(!pList) {
printf("List is not exist");
return FALSE:
}
// 声明一个结点 cur,让该结点指向单链表的头结点
Node *cur = pList;
// 创建一个临时结点,用于存放新插入的数据元素
Node *temp = (Node *)malloc(sizeof(Node));
if(!temp) {
printf("malloc error");
}
// 查找单链表的尾结点,若到单链表的尾结点,则为 NULL
while(cur->next) {
cur = cur->next;
}
temp->data = e;
// 执行插入操作
temp->next = cur->next;
cur->next = temp;
return TRUE;
}
单链表的删除
我们先来看一下单链表的存储结构示意图
QQ20200628-163941.png
假设存储数据元素 ai 的结点是 q,要想实现在单链表中删除结点 q 的操作，其实就是将结点 p 的直接后继结点的后继结点变成 p 的直接后继结点，用伪代码表示就是：
p->next = p->next->next;
使用 q 代替 p->next，代码表示如下：
q = p->next;p->next = q->next;
单链表第 i 个数据删除结点的算法思路：
1.声明一个节点 front,让其指向单链表的第一个结点，初始化 j 为 1
2.当 j < i ，遍历单链表，让 front 的指针向后移动，不断的指向下一个结点，j 累加 1
3.若到链表末尾 p 为空，则在单链表中没有第 i 个元素
4.反之则查找成功，查找到要删除位置的前一个元素 front，并赋值给 pTemp
5.执行单链表的删除结点语句 front->next = front->next->next;
6.将 pTemp 结点的数据元素赋值给 e，并返回
7.释放 pTemp 结点，并指向 NULL
8.返回成功
Status deleteList(LinkList *pList,int i,ElemType *e) {
// 判断单链表是否存在
if(!pList) {
printf("list not exist\n");
return FALSE;
}
// 只能删除位置 1 以及后面的结点
if(i < 1) {
printf("i is invalid\n");
return FALSE;
}
// 在这里我们声明一个结点 front,让其指向单链表 pList 的头结点
Node *front = pList;
for(int j = 1;j < i;j++) {// j 为计数器，初始化为1
front = front->next;
if(front == NULL) {
printf("dont find front\n");
return FALSE;
}
}
// 提前保存要删除的结点
Node *temp = front->next;
*e = temp->data;//将要删除结点的数据赋值给e
// 删除结点
front->next = front->next->next;
// 销毁结点
free(temp);
temp = NULL;
return TRUE;
}
总结：通过上面对单链表的插入和删除算法的介绍，可以看出来它们都包含两部分：第一部分是先遍历查找第 i 个元素;第二部分执行插入和删除操作。根据前面文章中介绍的复杂度分析法分析，它们的时间复杂度都是 O(n)。线性表的链式存储结构相比较线性表的顺序存储结构来说，在数据元素的读取上没有太大的优势，线性表的顺序存储结构支持随机访问，根据下标随机访问的时间复杂度为 O(1);而对于单链表读取第 i 个位置的数据元素时因为其内存地址不是连续的,都必须要先从头指针开始遍历,时间复杂度为 O(n)
在数据元素的插入和删除方面，单链表的优势就比较明显了，尤其是 插入或者删除操作越频繁，单链表的效率优势就更加明显 假设现在我们要在第 i 个元素后插入 10 个元素,对于顺序存储结构来说，每一次插入都需要移动 n - i 个元素，每次都是 O(n);而对于单链表，我们只需要在第一次时，找到第 i 个元素指针，此时时间复杂度为 O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度为 O(1)
知识点补充
- 关于 malloc 函数的用法
在 C 语言中, malloc 函数主要用于动态内存分配，函数原型是：
void *malloc(unsigned int size)
此函数的返回值是分配内存块的起始地址(首地址)，或者说，这是一个指针类型的函数，返回的指针指向该分配内存块的首地址，分配成功则返回指向分配内存块的首地址，反之返回空指针 NULL；此外需要注意的是，该函数返回的是 void 类型的指针，void 类型说明类型还未确定，因此该函数的返回值可以指向任意类型的数据，因此必要时需要做类型强制转换
比如，现在我们声明了一个链表结构体：
typedef struct Node
{
ElemeType data;
struct Node *next;
}list;
现在我们要定义一个 Node 类型的指针变量，可以使用如下语句：
*a = (list*)malloc(sizeof(list));
其中，(list *) 表示类型强制转换，sizeof(list) 表示获取 list 类型占用空间大小
网友评论