【软考设计师】S01 数据结构 E01 线性结构 P01 线性表

---

前言——线性结构

线性结构是一种基本的数据结构，主要用于对客观世界中具有单一前驱和后继的数据关系进行描述。线性结构的特点是数据元素之间呈现一种线性关系，即元素“一个接一个排列”。

---

线性表

线性表的定义

• 线性结构： 线性表是最简单、最基本也是最常用的一种线性结构；
• 存储结构： 顺序存储、链式存储；

• 基本操作： 插入、删除和查找；

线性表的特点

线性表可为空。非空线性表的特点如下：

1. 存在唯一一个称为“第一个”的元素；
2. 存在唯一一个称为“最后一个”的元素；
3. 除第一个元素外，每个元素都有且只有一个直接前驱；
4. 除最后一个元素外，每个元素都有且只有一个直接后继；

线性表的存储结构

线性表的存储结构分为顺序存储和链式存储。

顺序存储

基础概念：

1. 精辟： 用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
2. 公式： 以 $LOC(a_1)$ 表示线性表中第一个元素的存储位置，在顺序存储结构中，第 $i$ 个元素 $a_i$ 的存储位置为：$$LOC(a_i)=LOC(a_1)+(i-1)\ast L$$ 其中 $L$ 表示每个数据元素所占空间的字节数。
3. 优点： 可以随机存取表中的元素：根据上述的公式，我们可以根据计算关系得知表中任一个元素的位置。
4. 缺点： 插入和删除操作需要移动元素：在插入前要移动元素以挪出空的存储单元，然后再插入元素；删除时同样需要移动元素，以填充被删除元素空出来的存储单元。

基本操作：

1. 插入： 在表长为 $n$ 的线性表中插入新元素时，共有 $n+1$ 个插入位置。在位置 $1$ 插入新元素，表中原有 $n$ 个元素都需要移动；在位置 $n+1$ 插入新元素时，不需要移动任何元素。因此等概率下，插入一个新元素需要移动的元素个数期望 $E_{insert}$ 为：$$E_{insert}=\sum _{i=1}^{n+1}{P}_i\ast （n-i+1）=\frac{1}{n+1}\sum _{i=1}^{n+1}(n-i+1)=\frac{n}{2}$$ 其中 $P_i$ 表示在表中的位置 $i$ 插入新元素的概率。
2. 删除： 在表长为 $n$ 的线性表中删除元素时，共有 $n$ 个可删除的元素。删除元素 $a_1$ 时需要移动 $n-1$ 个元素；删除元素 $a_n$ 时不需要移动元素。因此等概率下，删除一个元素需要移动的元素个数期望 $E_{delete}$ 为：$$E_{delete}=\sum _{i=1}^n{q}_i\ast (n-i)=\frac{1}{n}\sum _{i-1}^n(n-i)=\frac{n-1}{2}$$ 其中 $q_i$ 表示删除第 $i$ 个元素（即 $a_i$）的概率。

---

链式存储

线性表的链式存储是通过指针链接起来的结点来存储数据元素，基本结点结构为：

其中数据域用于存储数据元素的值，指针域用于存储当前元素的直接前驱或直接后继的位置信息。指针域中的信息称为指针（或链）。

单链表

因为链式存储存储各元素的结点的地址并不要求是连续的，因此存储数据元素的同时必须存储元素之间的逻辑关系。结点与结点之间通过指针域构成一个链表，若节点中只有一个指针域，则称为单链表（或称线性链表）。

假设单链表中的元素是整型，则单链表结构类型的定义为：

typedef struct node{int data;				/*结点的数据域，假设为整型*/struct node *next;		/*结点的指针域*/
}NODE, *LinkList

在链式存储结构中，只需要一个指针（称为头指针，上图中 head）指向第一个结点，就可以顺序地访问到表中的任意一个元素。

在链式存储结构下，进行插入和删除元素，其实实质上都是对相关指针的修改。

插入：

在单链表中，若在 $p$ 所指结点后插入新结点 $s$，基本步骤如下：

s->next = p->next;
p->next = s;

我们先将 $p$ 所指结点的后继结点指针赋给 $s$ 所指结点的指针域，然后将 $p$ 所指结点的指针域修改为 $s$ 所指结点。

删除：

在单链表中，删除 $p$ 所指结点的后继结点时，步骤如下：

q = p->next;
p->next = p->next->next;
free(q)

我们先令临时指针 $q$ 指向待删除的结点，然后修改 $p$ 所指结点的指针域为指向 $p$ 所指向结点的后继的后继结点，从而将元素所在结点从链表中删除，最后释放 $q$ 所指结点的空间。

头结点：

在实际应用中，为了简化对链表状态的判定和处理，特别引入一个不存储数据元素的结点，称为头结点，将其作为链表的第一个结点并令头指针指向该结点。

单链表的操作（查找、插入、删除）
单链表的查找操作：

LinkList Find_List(LinkList L, int k)	/*L为带头结点单链表的头指针*/
/*在表中查找第k个元素，若找到，返回该元素结点的指针；否则，返回空指针NULL*/
{LinkList p; int i;i = 1; p = L->next;		/*初始时，令p指向第一个元素结点，i为计数器*/while(p && i<k) {		/*顺指针链向后查找，直到p指向第k个元素结点或p为空指针*/p = p->next; i++;}if(p && i==k) return p;	/*存在第k个元素且指针p指向该元素结点*/return NULL
} /*Find_List*/

单链表的插入操作：

int Insert_List(LinkList L, int k, int newElem)	/*L为带头结点单链表的头指针*/
/*将元素newElem插入表中的第k个元素之前，若成功则返回0，否则返回-1*/
/*该插入操作等同于将元素newElem插入在第k-1个元素之后*/
{LinkList p,s;		/*p,s为临时指针*/if(k == 1) p = L;	/*元素newElem要插入到第1个元素之前*/else p = Find_List(L, k-1)		/*查找表中的第k-1个元素并令p指向该元素结点*/if(!p) return -1;				/*表中不存在第k-1个元素，不满足运算要求*/s = (NODE *)malloc(sizeof(NODE));	/*创建新元素的结点空间*/if(!s) return -1;s->data = newElem;s->next = p->next; p->next = s;	/*将元素newElem插入到第k-1个元素之后*/return 0;
} /*Insert_List*/

单链表的删除操作：

int Delete_List(LinkList L, int k)	/*L为带头结点的单链表的头指针*/
/*删除表中的第k个元素结点，若成功则返回0，否则返回-1*/
/*删除第k个元素相当于令第k-1个元素结点的指针域指向第k+1个元素所在结点*/
{LinkList p,q;		/*p,q为临时指针*/if(k == 1) p = L;	/*删除的是第一个元素结点*/else p = Find_List(L, k-1);		/*查找表中的第k-1个元素并令p指向该元素结点*/if(!p||!p->next) return -1;		/*表中不存在第k个元素*/q = p->next;					/*令q指向第k个元素结点*/p->next = q->next;	free(q);	/*删除结点*/return 0;
} /*Delete_List*/

所以综上，当线性表采用链表作为存储结构时，我们不能对数据元素进行随机访问，但是具有插入和删除操作不需要移动元素的优点。

双向链表

每个结点包含两个指针，分别指向当前元素的直接前驱和直接后继。其特点是可以从表中任意的结点出发，从两个方向上遍历链表。

若双向链表中结点的 front 和 next 指针域分别指示当前结点的直接前驱和直接后继，则在双向链表中插入结点的操作过程表示为：

s->front = p->front;
p->front->next = s;
s->next = p;
p->front = s;

在双向链表中删除结点的操作过程表示为：

p->front->next = p->next;
p->next->front = p->front;
free(p);

循环链表

在单向链表（或双向链表）的基础上令表尾结点的指针指向链表的第一个结点，构成循环链表。其特点是可以从表中任意结点开始遍历整个链表。

静态链表

借助数组来描述线性表的链式存储结构，用数组元素的下标表示元素所在结点的指针。

---