数据结构导论【三】之 栈、队列和数组_初始化为空的栈

接上一篇：数据结构导论【二】之 线性表

一、栈

1.栈的基本概念

①定义

栈是只能在表的一端（表尾）进行插入和删除的线性表；

其中：
允许插入及删除的一端（表尾）称为栈顶（Top）；
另一端（表头）称为栈底（Bottom）。
当表中没有元素时称为空栈。

S = （a1, a2, a3, …, an）【a1是栈底元素，an是栈顶元素】
进栈 – 在栈顶插入一元素
出栈 – 在栈顶删除一元素

栈和队列可看作是特殊的线性表，它们是 运算受限的线性表 。

②示意图

例：一叠书或一叠盘子。

③栈的特点 - 后进先出

栈中元素按a1,a2,a3,…an的次序进栈，出栈的第一个元素应为栈顶元素。换句话说，栈的修改是按照后进先出的原则进行的。
因此，栈称为后进先出线性表（LIFO）。

④栈的基本操作

栈的用途 – 常用于暂时保存有待处理的数据。

⑤栈的基本运算

1、初始化栈：InitStack(S);
2、判栈空：EmptyStack(S);
3、进栈：Push(S, x);
4、出栈：Pop(S);
5、取栈顶：GetTop(S);

2.栈的顺序实现

①顺序栈及常用名词

• 顺序栈 – 即栈的顺序实现

• 栈容量 – 栈中可存放的最大元素个数

• 栈顶指针 top – 指示当前栈顶元素在栈中的位置；

• 栈空 – 栈中无元素时，表示栈空；

• 栈满 – 数组空间已被占满时，称栈满；

• 下溢 – 当栈空时，再要求作出栈运算，则称『下溢』。

• 上溢 – 当栈满时，再要求作进栈运算，则称『上溢』。

②顺序栈的类型定义

const int maxsize = 6;
typedef struct seqstack {
	DataType data[maxsize];
	int top;
} SeqStk; // 顺序栈类型

SeqStk *s; /* 定义一顺序栈s */
// 约定栈的第 1 个元素存在data[1]中。
// 则s -> top == 0 代表顺序栈 s 为空；
// s -> top == maxsize - 1 代表顺序栈s为满；
1
2
3
4
5
6
7
8
9
10

③顺序栈的运算

// 初始化
int Initstack(SeqStk * stk) {
	stk -> top = 0;
	return 1;
}

// 判栈空【栈空时返回值为1，否则返回值为0】
int EmptyStack(SeqStk *stk) {
	return (stk -> top == 0) ? 1 : 0;
}

// 进栈【数据元素x进顺序栈stk】
int Push(SeqStk *stk, DataType x) {
	// 判断是否上溢
	if (stk -> top == maxsize - 1) {
		error('栈满');
		return 0;
	} else {
		stk -> top++; // 修改栈顶指针，指向新栈顶
		stk -> data[stk -> top] = x; // 元素x插入新栈顶中
		return 1;
	}
}

// 出栈【顺序栈sq的栈顶元素出栈】
int Pop(SeqStk *stk) {
	// 判断是否下溢
	if (stk -> top == 0) {
		error('栈空');
		return 0;
	} else {
		stk -> top--; // 修改栈顶指针，指向新栈顶
		return 1;
	}
}

// 取栈顶元素
DataType GetTop(SeqStk *stk) {
	if (EmptyStack(stk)) {
		return NULLData;
	} else {
		return stk -> data[stk -> top];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

3.栈的链接实现 – 链栈

①链栈的定义

栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行。栈顶指针就是链表的头指针。

链式栈的类型说明如下：

// 链栈类型
// 下溢条件：LS -> next == NULL;
// 上溢：不需要考虑栈满现象
typedef struct node {
	DataType data;
	struct node *next;
} LkStk;
1
2
3
4
5
6
7

②链栈的基本运算

// 初始化
void InitStack(LkStk *LS) {
	LS = (LkStk *)malloc(sizeof(LkStk));
	LS -> next = NULL;
}

// 判栈空
int EmptyStack(LkStk *LS) {
	return (LS -> next == NULL) ? 1 : 0;
}

// 进栈 -- 在栈顶插入一元素x
void Push(LkStk *LS, DataType x) {
	LkStk *temp;
	temp = (LkStk *) malloc(sizeof(LkStk));
	temp -> data = x;
	temp -> next = LS -> next;
	LS -> next = temp;
}

// 出栈 -- 在栈顶删除一元素，并返回是否成功
int Pop(LkStk * LS) {
	LkStk *temp;
	if (!EmptyStack(LS)) {
		temp = LS -> next;
		LS -> next = temp -> next;
		free(temp);
		return 1;
	} else {
		return 0;
	}
}

// 取栈顶元素
DataType GetTop(LkStk *LS) {
	if (!EmptyStack(LS)) {
		return LS -> next -> data;
	} else {
		return NULLData;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

进栈示意图：

出栈示意图

4.栈的应用和递归

①栈的应用举例

例一：栈的基本应用实例

例二：阅读程序片段，写出运行结果

const int maxsize = 50;
typedef struct seqstack {
	char data[maxsize];
	int top;
} SeqStk;

main() {
	SeqStk stk;
	int i;
	char ch;
	InitStack(&stk);
	for (ch = 'A'; ch <= 'A' + 10; ch++) {
		Push(&stk, ch);
		printf("%c", ch);
	}
	printf("\n");

	while(!EmptyStack(&stk)) {
		ch = GetTop(&stk);
		Pop(&stk);
		printf("%c", ch);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

输出结果：
ABCDEFGHIJK
KJIHGFEDCBA

例三：写一个算法，借助栈将下图所示的带头结点的单链表逆置。

void ReverseList(LkStk *head) {
	LkStk *S;
	DataType x;
	InitStack(S); // 初始化链栈
	p = head -> next;
	while (p != NULL) {
		Push(S, p -> data); // 元素进栈
		p = p -> next;
	}
	p = head -> next;
	while (!EmptyStack(S)) { // 栈不为空时
		p -> data = GetTop(S); // 元素填入单链表中
		Pop(S); // 出栈
		p = p -> next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

②递归与递归的阅读

a.递归的定义

如果一个函数在完成之前又调用自身，则称之为递归函数。
例：求整数n的阶乘函数
程序实现

int f(int n) {
	if (n == 0) {
		return 1;
	} else {
		return n * f(n - 1);
	}
}
1
2
3
4
5
6
7

b.递归的一般形式

void fname(参数表) {
	if (递归出口) {
		// 简单操作
	} else {
		fname(参数表); // 调用自身[可能有多次调用]
	}
}
1
2
3
4
5
6
7

二、队列

1.队列的基本概念

队列（Queue）也是一种运算受限的线性表。
队列 – 只允许在表的一端进行插入，而在另一端进行删除的线性表。
其中：
允许删除的一端称为队头(front)。
允许插入的一端称为队尾(rear)。
队列Q=（a1, a2, a3, …, an）

示意图：



例如：
排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出（First In First Out）的线性表，简称FIFO表。
当队列中没有元素时称为空队列。在空队列中依次加入元素a1, a2, …, an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1, a2, …, an，也就是说队列的修改是依先进先出的原则进行的。

队列特点：先进先出（FIFO）
**队列的用途：**常用于暂时保存有待处理的数据。

2.队列的基本操作

①队列初始化

InitQueue(Q);
设置一个空队列Q；

②判队列空

EmptyQueue(Q);
若队列Q为空，则返回值为1，否则返回值为0;

③入队列

EnQueue(Q, x);
将数据元素x从Q队尾一端加入队列，使其成为队列的新尾元素；

④出队列

OutQueue(Q);
删除队列首元素。

⑤取队列首元素

返回队列首元素的值。

3.队列的顺序实现 - 循环队列

用一维数组作为队列的存储结构。

队列容量–队列中可存放的最大元素个数。

约定：front = rear = 0
进队：rear增1，元素插入尾指针所指位置
出队：front增1，取头指针所指位置元素

队头指针front – 始终指向实际队头元素的前一位置
队尾指针rear – 始终指向实际队尾元素

// 初始化队列
const int maxsize = 20;
typedef struct seqqueue {
	DataType data[maxsize];
	int front, rear;
} SeqQue;
SeqQue sq;

// 入队列
sq.rear = sq.rear + 1;
sq.data[sq.rear] = x;

// 出队列
sq.front = sq.front + 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

①顺序队列

只能从数组的一头插入、另一头删除。
上溢条件：sq.rear == maxsize - 1（队满）
下溢条件：sq.rear == sq.front（队列空）

假溢出:sq.rear == maxsize - 1,但队列实际容量并未达到最大容量的现象。

假溢出是极端现象：队列中的项不多于1，也导致『上溢』
假溢出会导致浪费空间。
为了克服『假溢出』问题，我们引入了循环队列。

②循环队列

a.定义

为队列分配一块存储空间（数组表示），并将这一块存储空间看成头尾相连接的。

示意图：

• 头指针front – 顺时针方向落后于实际队头元素一个位置
• 尾指针rear – 指向实际队尾元素

b.循环队列循环的实现

// 入队操作：队尾指针增1
Sq.rear = (sq.rear + 1) % maxsize;

// 出队操作：队头指针增1
Sq.front = (sq.front + 1) % maxsize;

// 循环队列类型定义
typedef struct Cycqueue {
	DataType data[maxsize];
	int front, rear;
} CycQue;
CycQue CQ;
1
2
3
4
5
6
7
8
9
10
11
12

c.规定(小重点)：

下溢条件即队列空：CQ.front == CQ.rear

上溢条件即队列满：尾指针从后面追上头指针
即：(CQ.rear + 1) % maxsize == CQ.front（尾赶头）
（浪费一个空间，队满时实际队容量 = maxsize - 1）

d.循环队列的基本运算

// 队列的初始化
void InitQueue(CycQue CQ) {
	CQ.front = 0;
	CQ.rear = 0;
}

// 判队列空
int EmptyQueue(CycQue CQ) {
	return (CQ.rear == CQ.front) ? 1 : 0;
}

// 入队列
int EnQueue(CycQue CQ, DataType x) {
	if ((CQ.rear + 1) % maxsize == CQ.front) {
		error("队列满");
		return 0;
	} else {
		CQ.rear = (CQ.rear + 1) % maxsize;
		CQ.data[CQ.rear] = x;
		return 1;
	}
}

// 出队列
int  OutQueue(CycQue CQ) {
	if (EmptyQueue(CQ)) {
		error("队列空");
		return 0;
	} else {
		CQ.front = (CQ.front + 1) % maxsize;
		return 1;
	}
}

// 取队列首元素
DataType GetHead(CycQue CQ) {
	if (EmptyQueue(CQ)) {
		return NULLData;
	} else {
		return CQ.data[(CQ.front + 1) % maxsize];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

4.队列的链接实现 - 链队列

①链式队列的定义

用链表表示的队列，即它是限制仅在表头删除和表尾插入的单链表。

显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。
附设俩指针：
头指针front – 指向表头结点；队头元素结点为front -> next;
尾指针rear – 指向链表的最后一个结点（即队尾结点）

链队列类型说明：

可将队头和队尾这俩个指针封装在一起，将链队列的类型定义为一个结构类型：

typedef struct LinkQueueNode {
	DataType data;
	struct LinkQueueNode * next;
} LkQueNode;

typedef struct LkQueue {
	LkQueue *front, *rear;
} LkQue;
LkQue LQ;
1
2
3
4
5
6
7
8
9

LQ.front – 链式队的队头指针
LQ.rear – 链式队的队尾指针
链式队的上溢：可不考虑；（因动态申请空间）
链式队的下溢：即链式队为空时，还要求出队；此时链表中无实在结点：

规定：链队列空时，令rear指针也指向表头结点。

链队列下溢条件：
LQ.front -> next == NULL 或 LQ.front == LQ.rear;

②链队列的基本运算

// 队列的初始化
void initQueue(LkQue *LQ) {
	LkQueNode *temp;
	temp = (LkQueueNode *) malloc(sizeof(LkQueNode));
	LQ.front = temp;
	LQ.rear = temp;
	LQ.front.next = NULL;
}
// 判队列空
int EmptyQueue(LkQue LQ) {
	return (LQ.rear == LQ.front) ? 1 : 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

示意图：

// 入队列
void EnQueue(LkQue *LQ; DataType x) {
	LkQueNode *temp;
	temp = (LkQueNode *) malloc(sizeof(LkQueNode));
	temp.data = x;
	temp.next = NULL;
	LQ.rear.next = temp;
	LQ.rear = temp;
}
1
2
3
4
5
6
7
8
9

示意图：

// 出队列
void OutQueue(LkQue *LQ) {
	LkQueNode *temp;
	if (EmptyQueue(LQ)) {
		error("队空");
		return 0;
	} else {
		temp = LQ.front.next;
		LQ.front.next = temp.next;
		if (temp.next == NULL) {
			LQ.rear = LQ.front;
		}
		free(temp);
		return 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

示意图：

// 取队列首元素
DataType GetHead(LkQue LQ) {
	LkQueNode *temp;
	if (EmptyQueue(LQ)) {
		return NULLData;
	} else {
		temp = LQ.front.next;
		return temp.data;
	}
}
1
2
3
4
5
6
7
8
9
10

PS:描述栈和队列实现的头文件如下：
Seqstack.h: 顺序栈的定义及其实现。
Lkstack.h:链栈的定义及其实现。
Sequeue.h:顺序队列的定义及其实现。
Lkqueue.h:链队列的定义及其实现。

---

三、数组

数组可看成是一种特殊的线性表，其特殊在于，表中的数组元素本身也是一种线性表。

1.数组的逻辑结构和基本运算

数组–是线性表的推广，其每个元素由一个值和一组下标组成，其中下标个数称为数组的维数。
数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其他复杂的结构更为简单。多维数组是线性表的推广。例如二维数组：

二维数组Amn可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。
数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组通常只有俩种基本运算：

①读–给定一组下标，读取相应的数据元素；
②写–给定一组下标，修改相应的数据元素；

2.数组的存储结构

①存储结构–顺序存储结构

由于计算机的内存结构是一维的。因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。

又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。

②寻址公式（以行为主存放）

例如，二维数组Amn按『行优先顺序』存储在内存中，假设每个元素占用k个存储单元。
元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i行一共有i * n个元素，第i行上aij前面又有j个元素，故它前面一共有i * n + j个元素，因此，aij的地址计算函数为：
LOC(aij) = LOC(a00) + (i * n + j) * k

3.矩阵的压缩存储

为了 节省存储空间 ，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

①特殊矩阵

特殊矩阵： 即指非零元素或零元素的分布有一定规律的矩阵。下面我们讨论几种特殊矩阵的压缩存储。

a.对称矩阵

1.定义：在一个n阶方阵A中，若元素满足下述性质：

aij == aji  && 0 <= i && j <= n - 1;
1

则称A为对称矩阵。如下图便是一个5阶对称矩阵。

b.物理存储

对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每俩个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按『行优先顺序』存储主对角线（包括对角线）以下的元素，其存储形式如图所示：

因此，我们可以按图中箭头所指的次序将这些元素存放在一个一维数组==S[0…n(n + 1) / 2 - 1]==中。为了便于访问对称矩阵A中的元素，我们必须在aij和S[k]之间找一个对应关系。

c.下标变换公式（以下三角表示）【一定要根据实际的题算几遍才能掌握精髓】

算三角矩阵中一共有多少个元素【aij之前的i行（从第0行到第i-1行）】：
一共有1+2+…+i个元素。
换算规律公式：i(i + 1) / 2。

1.若 i >= j,则aij在下三角矩阵中。

在第 i 行上，aij之前恰有j个元素（即ai0, ai1, ai2, ai3, …, aij - 1）。
因此有：
k = (i * (i + 1) / 2) + j
0 <= k <= n(n + 1) / 2 - 1

---

2.若 i < j,则aij是在上三角矩阵中。因为aij = aji，所以只要交换上述对应关系式中的i和j即可得到：
k = (j * (j + 1) / 2) + i
0 <= k <= n(n + 1) / 2 - 1

---

有了上述的下标交换关系，对于任意给定一组下标(i , j)，均可在S[k]中找到矩阵元素aij，反之，对所有的k = 0, 1, 2, …n(n + 1) / 2 - 1，都能确定S[k]中的元素在矩阵中的位置(i, j)。由此，称S[n(n + 1) / 2]为对称矩阵A的压缩存储，见下图：

例如a31和a13均存储在sa[7]中，这是因为：
k = i * (i + 1) / 2 + j = 3 * (3 + 1) / 2 + 1 = 7

②三角矩阵

以主对角线划分，三角矩阵有上三角和下三角俩种。
上三角矩阵如图A所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图B所示。在大多数情况下，三角矩阵常数为零。

三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有 n(n + 1) / 2 个，因此，三角矩阵可压缩存储到向量s[0…n(n + 1) / 2]中，其中c存放在向量的最后一个分量中。

③稀疏矩阵的压缩存储

稀疏矩阵：设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数，则称A为稀疏矩阵。
稀疏矩阵的压缩存储： 即只存储稀疏矩阵中的非零元素。
目的：节省存储空间。

由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i, j）。反之，一个三元组（i, j, aij）唯一确定了矩阵A的一个非零元素。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。

---

1.三元组顺序表
稀疏矩阵的三元组顺序表表示法： 将矩阵中的非零元素化成三元组形式并按行的不减次序（同行按列的递增次序）存放在内存中。

三元组表结构： 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法–三元组顺序表。

const int maxnum = 10;
typedef struct node {
	int i, j; // 非零元素的行下标和列下标
	DataType v; // 非零元素的值
} NODE; // 三元组

typedef struct spmatrix {
	NODE data[maxnum]; // 非零元素三元组表
	int mu, nu, tu; // 矩阵的行数，列数和非零元素个数
} SpMtx; // 稀疏矩阵三元组表存储类型
1
2
3
4
5
6
7
8
9
10

设：SpMtrx M; 则下图中所示的稀疏矩阵的三元组的表示如右

---

---

---

下一篇：数据结构导论【四】之 树和二叉树