顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。
它具有随机存储的特点：每个元素都与一个序号存在唯一对应关系。
定义与初始化
1#define MAXSIZE 100
2
3typedef int ElemType;
4
5struct SeqList {
6 ElemType *data; // 定义首元素地址
7 int length; // 顺序表容量
8};
9
10/* ----- 初始化顺序表 ----- */
11void InitList(SeqList &L) {
12 L.data = (ElemType*)malloc(MAXSIZE * sizeof(ElemType)); // 分配内存空间
13 if (L.data == NULL) {
14 // 初始化失败
15 return;
16 }
17 L.length = 0;
18}
在函数参数中使用取指（
&）是 C++ 的用法，C 语言只能传递指针。1// 纯C语言实现 2void InitList(SeqList *L) { 3 L->data = (ElemType*)malloc(MAXSIZE * sizeof(ElemType)); 4 if (L->data == NULL) { 5 return; 6 } 7 L->length = 0; 8}
顺序表基本操作
任何一个数据结构都应具备“增、删、改、查” 4种基本操作。
1/* ----- 遍历顺序表 ----- */
2void List(SeqList &L) {
3 for (int i = 0; i < L.length; i++) {
4 printf("%d ", L.data[i]);
5 }
6 printf("\n");
7}
8
9/* ----- 插入元素 ----- */
10// 在尾部添加元素
11void Append(SeqList &L, ElemType e) {
12 if (L.length >= MAXSIZE) {
13 // 顺序表内存已满
14 return;
15 }
16 else {
17 L.data[L.length] = e;
18 L.length ++;
19 }
20 return;
21}
22
23// 向顺序表中插入元素
24void Insert(SeqList &L, int pos, ElemType e) {
25 if (pos <= L.length && pos >= 1 && L.length + 1 <= MAXSIZE) {
26 for (int i = L.length - 1; i >= pos - 1; i--) {
27 L.data[i + 1] = L.data[i];
28 }
29 L.data[pos-1] = e;
30 L.length ++;
31 }
32 return;
33}
34
35/* ----- 删除元素 ----- */
36// 删除特定元素
37void Delete(SeqList &L, int pos, ElemType e) {
38 e = L.data[pos-1];
39 if (pos >= 1 && pos <= L.length) {
40 for (int i = pos; i < L.length; i++) {
41 L.data[i-1] = L.data[i];
42 }
43 L.length --;
44 }
45 return;
46}
47
48// 清空顺序表
49void DeletAll(SeqList &L) {
50 L.length = 0;
51}
52
53/* ----- 查找元素 ----- */
54int Find(SeqList &L, ElemType e) {
55 for (int i = 0; i < L.length; i++) {
56 if (L.data[i] == e) {
57 return i;
58 }
59 }
60 return -1;
61}
顺序表查找算法的时间复杂度：
$$ACN = \frac{1}{n} \sum_{i=0}^{n-1} (i+1) = \frac{1}{n} (1+2+\cdots+n) = \frac{1}{n} \cdot \frac{n(1+n)}{2} = \frac{1+n}{2} = O(n) $$
顺序表的应用
重复元素剔除
思路1：先排序，再去重
思路2：使用桶排序。
1// 获取构造“桶”的参数
2// 查找最小最大值
3void FindMinMax(SeqList &L, ElemType &minVal, ElemType &maxVal) {
4 if (L.length == 0) return;
5
6 minVal = maxVal = L.data[0];
7 for (int i = 1; i < L.length; i++) {
8 if (L.data[i] < minVal) minVal = L.data[i];
9 if (L.data[i] > maxVal) maxVal = L.data[i];
10 }
11}
12
13// 通用桶排序去重（支持负数）
14void BucketSortUnique(SeqList &L) {
15 if (L.length <= 0) {
16 return;
17 }
18
19 ElemType minVal, maxVal;
20 FindMinMax(L, minVal, maxVal);
21
22 int range = maxVal - minVal + 1;
23
24 // 动态创建桶数组
25 int *bucket = (int*)calloc(range, sizeof(int));
26 if (bucket == NULL) {
27 printf("内存分配失败！\n");
28 return;
29 }
30
31 // 标记存在的元素
32 for (int i = 0; i < L.length; i++) {
33 bucket[L.data[i] - minVal] = 1;
34 }
35
36 // 重构顺序表
37 int newLength = 0;
38 for (int i = 0; i < range; i++) {
39 if (bucket[i] == 1) {
40 L.data[newLength] = i + minVal;
41 newLength ++;
42 }
43 }
44 L.length = newLength;
45
46 free(bucket);
47}
算法特点：
- 时间复杂度：$O(n + k)$，其中 $n$ 是元素个数，$k$ 是数值范围
- 空间复杂度：$O(k)$，需要额外的桶数组
- 稳定性：稳定（保持原有相对顺序，但去重后这个特性不重要）
- 适用场景：元素取值范围不大
链表
链表是用一段物理地址不连续的存储单元依次存储数据元素的线性结构。因为存储地址不连续，所以不能用下标索引的方式寻找元素，而是要在结点之间设置指针串联起来。
由此可见，链表不具备随机存储的特点。
定义与初始化
1/* ----- 定义 ----- */
2struct Node {
3 ElemType data;
4 Node *next;
5};
6
7/* ----- 初始化 ----- */
8void Initial(Node &L) {
9 L = (Node*) malloc (sizeof(Node));
10 L.data = 0;
11 L.next = NULL;
12}
链表基本操作
1/* ----- 遍历链表 ----- */
2void ListNode(Node &L) {
3 Node *p = L.next;
4 printf("链表中的元素有：");
5 while(p != NULL) {
6 printf("%d ", p.data);
7 p = p.next; //指针指向下一个节点
8 }
9 printf("\n");
10}
11
12int ListLength(Node &L) {
13 int length = 0;
14 Node *p = L;
15 while(p != NULL) {
16 length ++;
17 p = p.next;
18 }
19 length --;
20 return length;
21}
22
23/* ----- 增加元素 ----- */
24// 头插法：在第一个节点前插入
25void InsertHead(Node &L, ElemType e) {
26 // 创建新节点
27 Node *p = (Node*)malloc(sizeof(Node));
28 // 新节点的data赋值e
29 p.data = e;
30 // 新节点的next指向头节点原来指向的下一个节点
31 p.next = L.next;
32 // 头节点的next指向新节点
33 L.next = p;
34 printf("插入成功！\n");
35}
36
37// 尾插法：在链表尾节点后插入
38
39//寻找尾节点
40Node* GetTail(Node &L) {
41 Node *p = L;
42 while(p.next != NULL) {
43 p = p.next;
44 }
45 return p;
46}
47
48void InsertTail(Node &L, ElemType e) {
49 // 将元素转换成链表元素
50 Node *newNode = (Node*)malloc(sizeof(Node));
51 newNode.data = e;
52 // 获取尾节点
53 Node *p = GetTail(L);
54
55 newNode.next = p.link; // 相当于 newNode->next = NULL
56 p.next = newNode;
57 printf("插入成功！\n");
58}
59
60
61// 任意插入
62//寻找特定位置的元素
63Node* Find(Node &L, int pos) {
64 Node *p = L;
65 for(int i = 0; i<pos-1; i++) {
66 p = p.next;
67 if(p == NULL) {
68 printf("未找到该元素！\n");
69 return NULL;
70 }
71 }
72 return p;
73}
74
75void InsertNode(Node &L, int pos, ElemType e) {
76 Node *p = Find(L, pos);
77 if(p != NULL) {
78 InsertHead(p, e);
79 }
80}
81
82/* ----- 删除元素 ----- */
83// 删除指定位置的元素
84void Delete(Node &L, int pos) {
85 Node *p = Find(L, pos);
86 if(p != NULL && p.next != NULL) {
87 Node *q = p.next; // q指向pos对应的结点
88 p.next = q.next; // p指向q的后继结点
89 free(q); // 删除pos对应的结点
90 }
91 return;
92}
93
94// 释放链表
95void Free(Node &L) {
96 Node *p = L.next;
97 Node *q;
98
99 while(p != NULL) {
100 q = p.next;
101 free(p);
102 p = q;
103 }
104 L.next = NULL;
105}
链表操作的应用
合并链表
设被拼接链表为append_list，其头结点为append_list.head：
1void Append(Node &List, Node &append_list) {
2 // append_list.head是被拼接元素的头结点
3
4 // append_list连接到尾结点之后
5 last->next = append_list.head->next;
6 // 更新尾结点
7 last = append_list.last;
8 len += append_list.len;
9
10 // append_list清除
11 append_list.head->next = NULL;
12 append_list.len = 0;
13 return;
14}
特殊链表
| 类型 | 特点 |
|---|---|
| 循环链表 | 链表中最后一个结点的指针指向头结点，整个链表形成一个环 |
| 双向链表 | 链表中的结点有两个指针，一个指向该结点的前驱，另一个指向该结点的后继 |
栈
栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一端称作栈顶，另一端称作栈底。
栈的特点是后进先出（LIFO）。
定义与基本操作
1/* ----- 定义 ----- */
2struct Stack {
3 ElemType data;
4 Stack *next;
5};
6
7/* ----- 初始化 ----- */
8void Initial(Stack &S) {
9 S = (Stack*) malloc (sizeof(Stack));
10 if (!S.base) {
11 return;
12 }
13 S.top = S.base;
14 S.size = M
15 return;
16}
17
18/* ----- 判断栈空 ----- */
19bool IsEmpty(Stack &s) {
20 if(s.top == -1) {
21 // 栈为空
22 return true;
23 }
24 // 栈非空
25 return false;
26}
27
28/* ----- 入栈 ----- */
29void push(Stack &s, ElemType e) {
30 if(s.top == MAXSIZE-1) {
31 // 栈已满
32 return;
33 }
34 else {
35 s.top ++;
36 s.data[s.top] = e;
37 }
38 return;
39}
40
41/* ----- 出栈 ----- */
42void pop(Stack &s, ElemType &e) {
43 if(s.top == -1) {
44 // 栈为空
45 return;
46 }
47 else {
48 e = s.data[s.top];
49 s.top --;
50 }
51 return;
52}
53
54/* ----- 获取栈顶元素 ----- */
55void get_top(Stack &s, ElemType &e) {
56 if(s.top == -1) {
57 // 栈为空
58 return;
59 }
60 else {
61 e = s.data[s.top];
62 }
63 return;
64}
栈的应用
括号匹配
思路：从左到右扫描，遇到左括号则入栈；遇到右括号，若栈顶不是对应的左括号，则返回错误，反之则栈顶元素出栈。最后当且仅当扫描完毕且栈空时证明括号匹配。
括号匹配
表达式求值
表达式的三种形式
| 形式 | 表达式 | 举例 |
|---|---|---|
| 中缀表达式 | $\mathrm{Exp} = S_1 + op + S_2$ | $a \times b + (c-d/e) \times f$ |
| 前缀表达式 | $\mathrm{Exp} = op + S_1 + S_2$ | $ + \times a \ b \times - c \ / \ d \ e \ f$ |
| 后缀表达式 | $\mathrm{Exp} = S_1 + S_2 + op$ | $ a \ b \times c \ d \ e \ / -f \times +$ |
操作符优先级
| 操作符 | # |
( |
^ |
*, /, % |
+,- |
) |
|---|---|---|---|---|---|---|
| 栈内 | 0 | 1 | 7 | 5 | 3 | 8 |
| 栈外 | 0 | 8 | 6 | 4 | 2 | 1 |
#标识了表达式的开始与结束。优先级的特点为：保持级差，同级进栈升高，左括号入栈降至最低。
实现表达式求值
| 操作 | |
|---|---|
| ① | 使用两个工作栈，一个存放运算符OP，另一个存放数据NUM。 |
| ② | 置数据栈为空栈，表达式起始符#为运算符栈的栈底元素。 |
| ③ | 自左向右扫描表达式，读取到操作数则压入NUM栈，读取到运算符（记为C2）则与OP栈顶元素（记为C1）比较优先级。若C2 >= C1，则C2入栈，继续扫描表达式；若C2 < C1，则C1出栈，并从操作数栈取出两个元素a，b按C1运算，运算结果压入NUM栈。 |
| ④ | 重复操作 ③ 直到扫描结束。 |
递归
参见此处 。
队列
队列是只允许在表的一段进行插入，在另一端删除元素的线性表。
在队列中，允许插入的一端称作队头，允许删除的一端称作队尾。
特点：先进先出（FIFO）
双向队列
循环队列
将顺序队列想象为一个环状空间，即将队列首尾相连。
此时队列的操作必须考虑循环的存在。
| 操作 | |
|---|---|
| 队头指针加1 | front = (front+1) % MAXSIZE |
| 队尾指针加1 | rear = (rear+1) % MAXSIZE |
| 队列初始化 | front = rear = 0 |
| 队列为空 | front == rear |
| 队列已满 | (rear+1) % MAXSIZE == front |
串
基本概念
串是 $n$ $(n>0)$ 个字符的有限序列，记作S: 'c1c2c3...cn'
| 概念 | 内容 |
|---|---|
| 空串 | 含0个字符的串 |
| 空格串 | 只含有空格的串 |
| 串的长度 | 串中所含字符的个数 |
| 两个字符串相等 | 两个串的长度相等且对应字符也相同 |
| 子串 | 一个串中任意连续个字符组成的子序列 |
| 主串 | 包含主串的串 |
串的存储
定长顺序存储
用一组地址连续的存储单元存储串值
1#define MAXSTRLEN 255
2typedef unsigned char sstring[MAXSTRLEN+1]; // 0号单元存串长
堆分配存储
1typedef struct HString {
2 char *ch;
3 int length;
4}
其中Hstring.ch使用malloc和free分配存储空间。
链式存储
用链表存储串。每个节点存储串的n个字符。当串长不是n的整数倍时，最后一个结点的剩余位置用#补齐。
串的模式匹配
| 算法模式 | 具体操作 |
|---|---|
| 朴素匹配算法 | 两个指针i和j分别指向主串和模式串，当匹配失败时，i加1，同时j指向模式串开头，重新开始匹配。 |
| KMP算法 | 参见【此处】 |
数组和广义表
数组的表示
对于数组，一旦规定了它的维数和各维度的长度，便可为它分配存储空间。反之，只要给出一组下标便可求出相应数组元素的存储位置。
设每个数据元素占 $L$ 个存储单元，则二维数组 A[m][n] 中任一元素 a[i][j] 的存储位置为：
推广到一般情况，可得 $n$ 维数组的元素
$$\mathrm{LOC}(j_1,j_2,\cdots,j_n) = \mathrm{LOC}(0,0,\cdots,0) + \sum_{i=1}^{n}c_i j_i$$a[j1][j2]...[jn]的存储位置：其中 $c_n = L，c_{i-1}=b_i \times c_i$
数组元素的存储位置与其下标存在一一对应的关系，所以存取数组中任一元素的时间均相等。我们称具有这一特点的存储结构为随机存储结构。
矩阵的压缩存储
特殊矩阵
| 类型 | 存储方法 |
|---|---|
| 对称矩阵 | 为每一对对称元素分配一个存储空间，则可将 $n^2$ 个元素压缩到 $\displaystyle \frac{n(n+1)}{2}$ 个元素的空间中。以一维数组 sa[n(n+1)/2] 存储，则 sa[k] 与 a[i][j] 之间存在对应关系：$$k=\left\{\begin{matrix} \displaystyle \frac{i(i-1)}{2}+j-1 & i \geqslant j \\\\ \displaystyle \frac{j(j-1)}{2} + i - 1 & i < j \end{matrix} \right.$$ |
| 三角矩阵 | 与对称矩阵相同，只需再分配一个元素的空间存储常数 $c$ 即可 |
| 对角矩阵 | 与对称矩阵类似 |
稀疏矩阵
设矩阵a[m][n]中有t个元素不为0，若稀疏因子 $\displaystyle \delta = \frac{t}{m \times n}$ 很小时，称之为稀疏矩阵。
为了压缩存储空间，只需要存储稀疏矩阵中的非零元。因此，除了存储非零元的值之外，还需要同时记下它所在行和列的位置 $(i,j)$。这样，三元组 $(i,j,a_{ij})$ 就与稀疏矩阵的一个非零元相对应。