【数据结构复习之路】线性表（严蔚敏版）万字详解&主打基础

【数据结构复习之路】线性表（严蔚敏版）万字详解&主打基础
专栏：数据结构复习之路

数据结构的三要数：逻辑结构、数据的运算、存储结构（物理结构）。

我接下来要介绍的线性表，顾名思义也将从这三个大方向进行阐述：

一、线性表的定义——逻辑结构

线性表是具有相同数据类型的 n (n >= 0) 个数据元素的有限序列，其中n 为表长，当n = 0 时，线性表是一个空表。若用L 命名线性表，则其一般表示为：

$L = (a_{_{1}} , a_{_{2}},...,a_{_{i-1}} ,a_{_{i}},a_{_{i + 1}},...,a_{_{n}})$

⚠️ 线性表的特性：数据元素同类型、有限、有序。

⚠️ 线性表的重要术语：
1. $a_{_{i}}$ 是线性表中的 "第 i 个" 元素，是线性表中的位序（从1 开始），通俗点说，i 称为数据元素 $a_{_{i}}$ 在线性表中的位序。
2. 除第一个元素外，每个元素有且仅有一个直接前驱（ $a_{_{i-1}}$ 是 $a_{_{i}}$ 的直接前驱）；除最后一个元素外，每个元素有且仅有一个直接后继（ $a_{i + 1}$ 是 $a_{i }$ 的直接后继）。
二、线性表的基本操作——数据运算

1）InitList（L），初始化线性表为空

2）Length（L），返回表L的长度，即表中元素个数

3）Get（L，i），L中位置i处的元素（1≤i≤n）

4）Prior（L，i），取i的前驱元素

5）Next（L，i），取i的后继元素

6）Locate（L，x），元素x在L中的位置

7）Insert（L，i，x），在表L的位置i处插入元素x

8）Delete（L，p），从表L中删除位置p处的元素

9）IsEmpty(L) ，如果表L为空表(长度为0)则返回true，否则返回false

10）Clear（L），清除所有元素

11）Traverse（L），遍历输出所有元素

12）Find（L，x），查找并返回元素

13）Update（L，x），修改元素

14）DestroyList (L) ，销毁线性表，释放占用的内存空间

………………

上述函数运算操作，我都会在讲下文存储结构（顺序表，链表）时，结合它来依次展现。

⚠️ 记得要养成用英文表达的习惯（印象分+1）

⚠️ 上述函数的形参我都没有加 “ &” ，这取决于你对参数的修改结果是否需要 ” 带回来 “。

三、顺序表和链表——存储结构

3.1 顺序表

3.1.1 顺序表的定义

将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。

采用顺序存储结构的线性表简称为“ 顺序表”。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）= LOC（a1）+（i-1）* L （1≤i≤n）其中，L是元素占用存储单元的长度。（在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中）

3.1.2 静态分配和动态分配

1、存储空间是静态的，定义了MaxSize的大小后，不可再改变
```
#define MaxSize 10    // 定义最大长度
typedef struct{
     ElemType data[MaxSize];  // 用静态的 “数组” 存放数据元素（定义后，不可再改变数组长度大小）
     int length;     //顺序表的当前长度
}SqList;      //顺序表的类型定义（静态分配方式）
```
初始化，InitList (SqList &L)：
```
void InitList (SqList &L)
{
    for (int i = 0 ; i < MaxSize ; ++i)
	 {
	 	L.data[i] = 0;  //将所有数据元素设置为 默认初始值 （并非是0，依题意）
	 }	
	 L.length = 0; //初始长度为 0 
} 
```
2、动态申请（malloc）和释放内存空间（free），MaxSize 可根据需要改变
```
#define InitSize 10  //顺序表的初始长度 
typedef struct{   
	ElemType *data; //指示动态分配数组的指针 
	int MaxSize;   //顺序表的最大容量 
	int length;   //顺序表的当前长度 
}SeqList;   //顺序表的类型定义（动态分配方式） 
```
初始化， InitList (SeqList &L)：
```
void InitList (SeqList &L)
{
	//用 malloc 函数申请一片连续的存储空间 
    L.data = (int *)malloc(InitSize * sizeof(int)); //这里假设用的int型
	L.length = 0; //初始长度为 0 
	L.MaxSize = InitSize; 
} 
```
将动态数组的长度再增加 len ，IncreaseSize (SeqList &L ，int len)
```
void IncreaseSize (SeqList &L , int len)
{
	int *p = L.data; // 便于释放原先初始化的内存空间 
    L.data = (int *)malloc((L.MaxSize + len) * sizeof(int)); //重新申请一片连续的内存空间 
    for (int i = 0 ; i < L.length ; ++i)
    {
    	L.data[i] = p[i]; //将原先数据复制到新的内存区域 
	}
	L.MaxSize = L.Maxsize + len; //顺序表的最大长度增加 len 
	free(p); //释放原来的内存空间 
} 
```
当然通过realloc函数也是可以，而且更加方便，这我在栈和队列里面讲过。

3.1.3 插入操作（后移)和删除操作（前移）

静态分配的操作与动态分配异曲同工。

下面函数的含义：在 L 的位序 i 处插入元素 e 。

⚠️ ：位序是从1 开始的，而静态数组是从下标 0 开始的！
```
//静态分配 
bool ListInsert (SqList &L , int i , int e)
{
	if (i < 1 || i > L.length + 1) return false; //判断 i 的范围是否有效 
	if (L.length >= MaxSize) return false; // 当前存储空间已满，不能再插入，当然如果是动态分配可以选择扩容 
	for (int j = L.length ; j >= i ; j--)
	{
		L.data[j] = L.data[j-1]; //将第 i 个元素及之后的元素后移 
	}
	L.data[i-1] = e; //在位置 i 处放入 e 
	L.length++; //当前长度+1 
	return true; //成功插入 
} 
//动态分配
bool ListInsert(SqList &L, int i, int e){
    if (i < 1 || i > L.length + 1){ 
        return false;
    }
//    if (L.length >= MaxSize) return false; //不选择扩容
	if (L.length >= MaxSize)  IncreaseSize (L , len) //自己选择len的大小 
    for (int j = L.length ; j >= i ; j--)
	{
		L.data[j] = L.data[j-1]; 
	}
	L.data[i-1] = e; 
    L.length++;   
    return true;
}
```
下面函数的含义：删除 L 中位序 i 处的元素。
```
//静态分配
bool listDelete (SqList &L , int i)
{
	if (i < 1 || i > L.length) return false; //判断 i 的范围是否有效 
	for (int j = i ; j < L.length ; j++)
	{
		L.data[j-1] = L.data[j]; //将第 i 个元素之后的元素前移 
	}
	L.length--; //当前长度 -1 
	return true; //成功删除 
} 
```
3.1.4 按位查找和按值查找

GetElem ( L ，i ) ：按位查找操作。获取表 L 中第 i 个位置的元素的值。
```
//静态分配：
ElemType GetElem (SqList L , int i)
{
    return L.data[i - 1];
} 
//动态分配：
ElemType GetElem (SeqList L , int i)
{
    return L.data[i - 1]; //和访问普通数组的方法是一样的(因为data本来就是指向动态分配数组的指针) 
} 
```
LocateElem ( L , e) ：按值查找操作。查找具有给定关键字值的元素，返回它的位序。
```
//静态分配：
int LocateElem (SqList L , int e)
{
    for (int i = 0 ; i < L.length ; ++i)
    {
    	if (L.data[i] == e)
    	{
    		return i + 1;
		}
	}
	return 0;
} 
```
3.1.5 优缺点分析

从上面代码中，不难看出顺序表的时间复杂度，因此它的优缺点也就显而易见了：

优点：

1、可以通过下标访问元素，存取效率高

2、无须增加额外的存储空间表示结点间的逻辑关系，存储密度高。

缺点：

1、插入和删除运算不方便，通常须移动大量结点，效率较低。

2、难以进行连续的存储空间的预分配，尤其是当表变化较大时，即使是动态分配，也需要很大时间代价。

3.2 链表

链式表示，指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域：

① 存储数据元素信息的域称为数据域；

② 存储直接后继存储位置的域称为指针域。

3.2.1 单链表

用代码定义一个单链表：
```
typedef struct Lnode{
	ElemType data;  //数据域 
	struct Lnode *next; //指针域 
}Lnode, *LinkList;
```
这里的 Lnode 和 LinkList 的关系：

Lnode 等价于 struct Lnode； LinkList 等价于 struct node *

所以 Lnode * 等价于 LinkList
那为什么要选择这两种表达呢？

从他们的英语单词的命名就清楚（增强代码的可读性）：
- LinkList 强调这是一个单链表
- Lnode 强调这是一个结点
1、不带头结点的单链表定义：
```
void InitList(LinkList &L)
{
   L = NULL;	
} 
```
空表判断方法： L == NULL;

2、带头结点的单链表定义：
```
void InitList(LinkList &L)
{
   L = (Lnode *)malloc(sizeof(Lnode));
   L -> next = NULL; 
} 
```
空表判断方法：L -> next == NULL;

看个人习惯。不过，我推荐带头节点，下文会讨论。

3.2.1.1 按位序插入（带头节点 vs 不带头节点）

在第 i 个位置插入元素 e 【带头结点】。

辅助理解：如果 i = 1 （插在表头）：
```
bool ListInsert(LinkList &L , int i , Elemtype e)
{
   if (i < 1) return false;
   Lnode *p = L; //指针P 指向当前扫描到的结点
   int jp = 0; // 当前jp(P) 指向的是第几个结点
   while (p != NULL && jp < i - 1)
   {
    	p = p -> next;
   	    jp++;
   }
   if (p == NULL) return false;
   //找到插入的位置后 
   Lnode *s = (Lnode *)malloc(sizeof(Lnode));
   s -> data = e;
   s -> next = p -> next;
   p -> next = s;
   return true;
} 
```
在第 i 个位置插入元素 e 【不带头结点】。

辅助理解：如果 i = 1 （插在表头）：
```
bool ListInsert(LinkList &L , int i , Elemtype e)
{
   if (i < 1) return false;
   if (i == 1) //特殊处理
   {
        Lnode *s = (Lnode *)malloc(sizeof(Lnode));
        s -> data = e;
        s -> next = L;
        L = s //头指针指向新结点
		return true; 
   }
   Lnode *p = L; //指针P 指向当前扫描到的结点
   int jp = 1; // 当前jp(P) 指向的是第几个结点（注意这里）
   while (p != NULL && jp < i - 1)
   {
    	p = p -> next;
   	    jp++;
   }
   if (p == NULL) return false;
   //找到插入的位置后 
   Lnode *s = (Lnode *)malloc(sizeof(Lnode));
   s -> data = e;
   s -> next = p -> next;
   p -> next = s;
   return true;
} 
```
总结：

1、对比上面两个代码，显然带头结点的代码量更短，并且对于头节点的插入不需要特殊讨论，这两种方法考试都有可能考察，所以都要掌握，但自己写代码，我的建议是选带头节点的！

2、 s -> next = p -> next 和 p -> next = s 这两个步骤顺序不能倒过来，否则p -> next = s ，然后

s -> next = p -> next = s ，这不就指向自己了嘛？

3、理解了按位序插入的操作后，那指定结点的前后插操作，就顺其自然了。

指定结点的后插操作（在p结点之后插入元素e）：O(1)
```
bool InsertNextNode(Node *p , Elemtype e)
{
   if (p == NULL) return false; // p结点必须存在
   //将s连接在P结点后 
   Lnode *s = (Lnode *)malloc(sizeof(Lnode));
   s -> data = e;
   s -> next = p -> next;
   p -> next = s;
   return true;
} 
```
指定结点的前插操作（在p结点之前插入元素e）：O(1)
```
bool InsertNextNode(Node *p , Elemtype e)
{
   if (p == NULL) return false; // p结点必须存在
   //这里先在P结点之后连接一个结点S，然后再交换这两个结点的数据，S结点就在P结点前面了 
   Lnode *s = (Lnode *)malloc(sizeof(Lnode));
   s -> next = p -> next;
   p -> next = s;
   //交换数据 
   s -> data = p -> data;
   p -> data = e; 
   return true;
} 
```
3.2.1.2 按位序删除（带头结点 vs 不带头结点）

删除表 L 中第 i 个位置的元素，并用e 返回删除元素的值【带头节点】。

辅助理解：当 i = 4 (删除最后一个结点)：
```
bool ListInsert(LinkList &L , int i , Elemtype &e)
{
   if (i < 1) return false;
   Lnode *p = L; //指针P 指向当前扫描到的结点
   int jp = 0; // 当前jp(P) 指向的是第几个结点
   while (p != NULL && jp < i - 1)
   {
    	p = p -> next;
   	    jp++;
   }
   if (p == NULL) return false; // i 值要合法 
   if (p -> next == NULL) return false; //准备删除的结点必须存在 
   Lnode *q = p -> next; //令q指向被删除结点（可简化代码） 
   e = q -> data; 
   p -> next = q -> next;
   free(q); //记得要释放内存 
   return true;
} 
```
【不带头结点】
```
bool ListInsert(LinkList &L , int i , Elemtype &e)
{
   if (i < 1) return false;
   Lnode *p; //指针P 指向当前扫描到的结点
   int jp = 1; // 当前jp(P) 指向的是第几个结点
   if (i == 1) {
   	   p = L;
   	   e = p -> data;
   	   L = p -> next;
   	   free(p);
   	   return true;
   }
   p = L;
   while (p != NULL && jp < i - 1)
   {
    	p = p -> next;
   	    jp++;
   }
   if (p == NULL) return false; // i 值要合法 
   if (p -> next == NULL) return false; //准备删除的结点必须存在 
   Lnode *q = p -> next; //令q指向被删除结点（可简化代码） 
   e = q -> data; 
   p -> next = q -> next;
   free(q); //记得要释放内存 
   return true;
} 
```
【补充】

指定结点的删除操作（删除结点P）：
```
bool DeleteNode(Node *p)
{
   if (p == NULL) return false; // p结点要存在 
   Lnode *q = p -> next; 
   p -> data = q -> data; 
   p -> next = q -> next;
   free(q); //记得要释放内存 
   return true;
} 
```
⚠️：由于单链表只能在确定一个结点后，往后查找，不能往前查找，所以这里可以先交换p和q的数据，在删除q，间接的删除p结点。

下文的双链表，会带大家实现往前、往后查找~

3.2.1.3 尾插法和头插法（建立单链表）

依次输入10、16、27：
```
//尾插法
 
LinkList CreatList (LinkList &L)
{
	int n;
	scanf("%d" , &n);
	L = (LinkList)malloc(sizeof(Lnode)); //建立头节点
	Lnode *s  , *r = L; 
	for (int i = 0 ; i < n ; ++i)
	{
		int x; //假设插入n个整型 x; 
		scanf("%d", &x);
		s = (Node *)malloc(sizeof(Lnode)); 
		s -> data = x;
		r -> next = s;
		r = s;
	}
	r -> next = NULL;
	return L; 
}
```
依次输入10、16、27：
```
//头插法
 
LinkList CreatList (LinkList &L)
{
	int n;
	scanf("%d" , &n);
	L = (LinkList)malloc(sizeof(Lnode)); //建立头节点
	L -> next = NULL; //注意这里 
    Lnode *s;
	for (int i = 0 ; i < n ; ++i)
	{
		int x; //假设插入n个整型 x; 
		scanf("%d", &x);
		s = (Node *)malloc(sizeof(Lnode)); 
		s -> data = x;
		s -> next = L -> next;
		L -> next = s;
	}
	return L; 
}
```
3.2.1.4 销毁单链表

带头结点的自己动手写~
```
//【不带头结点】
void Destory (LinkList &L)
{
	Node *p = L;
	Node *p1 = L;
	while (p1 != NULL)
	{
		p1 = p1 -> next;
		free(p);
		p = p1;
	}
	L = NULL; 
}
```
⚠️：在清空链表后再次访问链表的节点将导致未定义行为。因此，我们在清空链表后立即将 head 指针设置为 NULL，以防止访问无效的内存地址。

3.2.2 双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表，下文会讲解。

双链表的定义：
```
typedef struct Dnode{
	ElemType data;
	struct Dnode *prior , *next; //前驱、后继指针 
}Dnode , *Dlinklist; 
```
双链表的初始化（带头结点）：
```
void InitDlinklist(Dlinklist &L)
{
	L = (Dnode *)malloc(sizeof (Dnode));
	L -> prior = NULL;
	L -> next = NULL;
}
```
3.2.2.1 双链表的插入

双链表的插入的顺序有多种，如下图，我们要在 P 结点的后面插入结点 S ，那么2 和 3一定要在4

的前面执行，因为我们需要通过 P 结点，找到 r 结点（p -> next），所以只有先将结点 S 和结点 r

连接完后，在能修改 p -> next = s 。而1步骤可以顺便在哪执行。所以综上，双链表的插入顺序最多有8种（基于下图虚线箭头的编号）：

1234 ，2134 ，2314 ， 2341 ， 1324 ， 3124 ， 3214 ， 3241

快选一种自己喜欢的顺序吧！

我比较喜欢 2314 的插入顺序。代码如下：

在P结点之后插入S结点：

辅助理解：将S插入在尾结点后面
```
bool InsertNextDnode(Dnode *p , Dnode *s)
{
	if (p == NULL || s == NULL) return false; //非法参数 
	s -> next = p -> next;
	if (p -> next != NULL) //如果P结点有后继结点 
	{
		p -> next -> prior = s;
	} 
	s -> prior = p;
	p -> next = s;
	return true;
}
```
⚠️

1、修改指针指向时，要按照图中代码顺序写

2、在P结点之前插入S结点，相当于倒过来看，本质和这个思想是一样的，就不写了

3、对于双向链表中的某一个结点p，它的后继的前驱以及它的前驱的后继都是它自己，即：
```
p -> next -> prior == p == p -> prior -> next
```
3.2.2.2 双链表的删除

删除P 结点的后继结点 q
```
bool DeleteNextDnode(Dnode *p)
{
	if (p == NULL) return false; //非法参数 
	Dnode *q = p -> next; 
	if (q = NULL)  return false;//p结点没有后继结点 
	p -> next = q -> next;
	if (q -> next != NULL)
	{
		q -> next -> prior = p;
	} 
	free(q); // 释放空间 
	return true;
}
```
3.2.2.3 双链表的销毁

可以结合 DeleteNextDnode(Dnode *p) 这个函数来实现
```
bool DestroyList(DLinkList &L)
{
	while (L -> next != NULL)
	{
		DeleteNextDnode(L); //不能直接用上面写那个函数（无返回值、形参记得带 &）
	}
	free(L); // 释放头结点 
	L = NULL;//头指针指向NULL 
	return true;
}
```
3.2.3 循环链表

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

3.2.3.1 循环单链表

插入、删除、建立这些操作和单链表几乎一样，就不写了

很多时候，当我们只需要对单链表的头部和尾部进行操作的话，这个循环单链表还是有点瑕疵的，我们虽然可以在O（1）的复杂度找到头节点，但由于头指针指向的是头节点，我们仍然需要

O（n）的复杂度才能找到尾部，因此，我们可以将头指针改为指向尾部结点，即：

从上图可以看到，终端结点可以用尾指针 L 指示，则查找终端节点是O(1)，而首元结点，其实就是

L -> next -> next ，其时间复杂度也是O(1)。

3.2.3.2 循环双链表

让表头结点的Prior 指向表尾结点、让表尾结点的next 指向头节点。

1、循环双链表和双链表的插入是一样的，并且没那么多考虑:
```
	s -> next = p -> next;
    p -> next -> prior = s;
	s -> prior = p;
	p -> next = s;
```
2、删除操作同理：
```
	Dnode *q = p -> next;  
	p -> next = q -> next;
	q -> next -> prior = p;
	free(q); 
```
当然操作还有很多，但基本和前面的代码一样，对比着写吧。

3.2.4 静态链表

用数组描述的链表，即称为静态链表。

在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标cur。

1、数据域 data，用来存放数据元素；

2、游标cur相当于单链表的next指针，存放该元素的后继在数组中的下标。

这种结构便于在不设 ”指针“ 类型的高级程序设计语言中使用链表结构。它结合了顺序表和单链表的特点，但说实话和单链表相关操作非常相似。为什么要叫 “静态”链表呢？因为在定义前，要像静态分配一样，预先分配一个较大的MAXSIZE的数组空间。

静态链表中，除了数据本身通过游标组成的链表外，还需要有一条连接各个空闲位置的链表，称为备用链表。通常静态链表会将第一个数据元素放到数组下标为 1 的位置（a[1]）中，它也常俗称为：数据链表表头；而 a[0] 被称为：备用链表表头；

数组第一个元素，即下标为0的元素的cur存放备用链表的第一个结点的下标；而数组的最后一个元素的cur（即a[7].cur）则存放备用链表表头的下标 0，当备用链表用完后，a[0].cur = a[7].cur = 0;

当然有时候数组的最后一个元素的cur，也可以存第一个有数值的元素的下标，数据域不存放任何东西，游标域存放首元结点的数组下标(相当于头结点)。但这完全没这个必要，头节点设在开头或结尾，都是可以的。并且没有头节点也是ok的，下图我仅仅在 a[1] 设了一个头指针，没有将a[1] 设为头节点，也是可以的。

数据链表的表尾的cur 也需要设置为0，这样我们才知道已经遍历到表尾了。

在前面的动态链表中，节点的申请和释放分别借用malloc()和free()两个函数来实现。而在静态链表中，我们需要自己实现这两个函数，当然这里不是分配地址和销毁地址，而是通过mallocList函数为我们找到一个数组中空闲的地址空间，而备用链表的作用就是这个。

为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标连成一个备用链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新节点。因为 a[0] 是备用链表的表头，我们知道它的位置，操作它的直接后继节点相对容易，无需遍历备用链表，耗费时间复杂度为 O(1)将它的直接后继节点地址空间用于分配。

mollocList ( )函数：
```
int mallocList(component * &spareList) {
    int i = spareList[0].cur; //当前数组第一个元素的cur存的值就是要返回的第一个备用空间的下标
    if (spareList[0].cur) {
        spareList[0].cur = spareList[i].cur; //把下一个分量用来做备用
    }
    return i;
}
```
free ( ) 函数：
```
void freeList(component * &spareList, int k) {
    //这操作和删除单链表结点太像了
    spareList[k].cur = spareList[0].cur; 
    spareList[0].cur = k;//把要删除的分量下标赋值给第一个元素的cur，以备下次分配空闲空间
}
```
静态链表可没有单链表、顺序表重要，所以只需要掌握简单的插入、删除就可以了

1、静态链表的定义：
```
#define MAXSIZE 1000    //假设链表的最大长度是1000
typedef struct{
    ElemType data;
    int cur;    
} Component , SLinkList[MAXSIZE];
 
//这里的SLinkList[MAXSIZE] 等价于你想定义一个“长度为MAXSIZE的Node型数组"。
//比如 SLinkList a;
//相当于定义了一个Component a[MAXSIZE];
```
2、静态链表的初始化：

一开始没有插入数据，整个数组都应设为备用链表。

备用链表和数据链表本身就同属于定义的node数组，所以下文就都用array统称。
```
void Initlist(component * &array) {
    int i = 0;
    for (i = 0; i < MAXSIZE; i++) {
        array[i].cur = i + 1;//将每个数组分量链接到一起
        array[i].data = 0; //记得初始化为0
    }
    array[MAXSIZE - 1].cur = 0;//链表最后一个结点的游标值为0
}
```
3.2.4.1 插入操作

在链表中位序为k的元素后插入一个元素，Datahead表示数据链表的首元结点在数组中的位置(不一定就是从1开始)，num表示要插入的数据。
```
 
bool insertList(SLinkList &array, int &Datahead, int k, int num) {
    int temp = Datahead; 
    int insert = 0;
    if(k < 1 || k > ListLength(array)){ //ListLength函数自己实现
        return false;
    }
    //找到要插入位置的上一个结点在数组中的位置
    for (int i = 1 ; i < k ; i++) {
        temp = array[temp].cur;
    }
 
    insert = mallocList(array);//申请空间，准备插入
    array[insert].data = num; 
 
    array[insert].cur = array[temp].cur;//新插入结点的游标等于其直接前驱结点的游标
    array[temp].cur = insert;//直接前驱结点的游标等于新插入结点所在数组中的下标
    return true;
}
```
如果要插入操作是在位序为k的位置插入元素，就还要考虑在位序为1 的位置插入，此时Datahead的位置就要改变：
```
if (i == 1)
{
	insert = mallocList(array);
	array[insert].data = num;
	array[insert].cur = temp;
	Datahead = insert;
	return true;
}
```
3.2.4.2 删除操作

删除位序为 i 的结点。
```
 
bool DeleteList(SLinkList &array , int i , int &Datahead){
    int temp = Datahead;
    if (i == 1)
    {
    	Datahead = array[temp].cur;
    	freeList(array , temp);
    	return true;
	}
    if(i<1 || i > ListLength(L)){
        return false;
    }
    for (int j = 2 ; j < i ; j++){
        temp = array[temp].cur;   
    }
    
    int p = array[temp].cur; //找到要删除结点的前一个结点 
    array[temp].cur = a[p].cur;
    freeList(array , p );
    return true;
}
```
四、总结

如果表长难以预估、经常要增加/删除元素，选链表。

如果可以预估、查询（搜索）操作较多，选顺序表。

总之，当我们选择一种数据结构，解决一类问题时，存储的考虑（空间）、运算的考虑（时间）、环境的考虑（方式），反正，如果你能熟练掌握本章的线性表的基本操作，顺序表和链表的适用场景就基本熟烂于心了，解决一类问题的前提是你了解这类问题！

最后，非常感谢大家的阅读。我接下来还会更新栈和队列，如果本文有错误或者不足的地方请在评论区(或者私信)留言，一定尽量满足大家，如果对大家有帮助，还望三连一下啦。

我的个人博客，欢迎访问！

Reference

【1】严蔚敏、吴伟民：《数据结构（C语言版）》

【2】b站：王道数据结构

【3】高级线性表——静态链表(最全静态链表解读)
相关阅读:
【幂等幂等幂等，重要的知识说三遍！】常见的九种解决方案汇总
 在Spring Boot中使用JTA实现对多数据源的事务管理
 linux权限
 递归题目树型实战
 算法训练第六周
 JAVA学习第十课：java事件处理
 Python（5）：字典
 日历视图，轻松解决时间管理难题_三叠云
 思腾云计算
 springsecurity学习笔记-未完
原文地址：https://blog.csdn.net/m0_74215326/article/details/132910341

一、线性表的定义——逻辑结构

二、线性表的基本操作——数据运算

三、顺序表和链表——存储结构

3.1 顺序表

3.1.1 顺序表的定义

3.1.2 静态分配和动态分配

3.1.3 插入操作（后移)和删除操作（前移）

3.1.4 按位查找和按值查找

3.1.5 优缺点分析

3.2 链表

3.2.1 单链表

3.2.1.1 按位序插入（带头节点 vs 不带头节点）

3.2.1.2 按位序删除（带头结点 vs 不带头结点）

3.2.1.3 尾插法和头插法（建立单链表）

3.2.1.4 销毁单链表

3.2.2 双向链表

3.2.2.1 双链表的插入

3.2.2.2 双链表的删除

3.2.2.3 双链表的销毁

3.2.3 循环链表

3.2.3.1 循环单链表

3.2.3.2 循环双链表

3.2.4 静态链表

3.2.4.1 插入操作

3.2.4.2 删除操作

四、总结

Reference