数据结构（C语言版）严蔚敏吴伟民编著第3章栈和队列

程序员文章站 2022-05-22 14:56:10

...

数据结构（C语言版）严蔚敏吴伟民编著第3章栈和队列

前言
3.1 栈
- 3.1.1 抽象数据类型栈的定义
- 3.1.2 栈的表示和实现
3.2 栈的应用举例
3.3 栈与递归的实现
3.4 队列

前言

栈和队列是两种重要的线性结构，从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此可称为限定性的数据结构。但从数据类型角度看，它们是和线性表大不相同的两类重要的抽象数据类型。由于它们广泛应用在各种软件系统中，因此在面向对象的程序设计语言中，它们是多型数据类型。

3.1 栈

3.1.1 抽象数据类型栈的定义

栈是限定仅在表尾进行插入或删除操作的线性表。因此对于栈来说，表尾端有其特殊的含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。假设栈S=(a₁,a₂,…a_n)，则称a₁为栈底元素，a_n为栈顶元素。栈中元素按a₁，a₂，…，a_n的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此栈又称为后进先出的线性表，简称LIFO结构（last in first out）。

3.1.2 栈的表示和实现

和线性表类似，栈也有两种存储表示方法。顺序栈，即栈的顺序存储结构是利用一组利用地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。通常的习惯做法是以top=0表示空栈，鉴于C语言中数组的下标约定从0开始，则当以C作描述语言时，如此设定会带来很大不便；另一方面，由于栈在使用过程中所需最大空间的大小很难估计，因此一般来说，在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。为此，可设定两个常量，STACK_INIT_SIZE（存储空间初始分配量）和STACKINCREMENT（存储空间分配增量），并以下述类型说明作为顺序栈的定义：

typedef struct{
	SElemType   *base;
	SElemType   *top;
	int    stacksize;
}SqStack;

其中，stacksize指示栈的当前可使用的最大容量。栈的初始化操作为：按设定的初始分配量进行第一次存储分配，base可称为栈底指针，在顺序栈中，它始终指向栈底的位置，若base的值为NULL，则表明栈结构不存在。称top为栈顶指针，其初值指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增加1，删除栈顶元素时，指针top减1，因此非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
以下是顺序栈的模块说明：

// 栈的顺序存储表示
#define STACK_INIT_SIZE 1OO  // 存储空间初始分配量
#define STACKINCREMENT  10   // 存储空间分配增量
typedef struct{
	SElemType   *base;  // 在栈构造之前和销毁之后，base的值为NULL
	SElemType   *top;   // 栈顶指针
	int    stacksize;   // 当前已分配的存储空间，以元素为单位
}SqStack;
// 基本操作的算法描述
Status InitStack(SqStack &S){
	// 构造一个空栈S
	S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if(!S.base) exit(OVERFLOW);   // 存储分配失败
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}// InitStack

Status GetTop(SqStack,SElemType &e){
	// 若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
	if(S.top=S.base) return ERROR;
		e = *(S.top - 1);
		return OK;
}//GetTop

Status Push(Sqstack &S,SElemType e){
	// 插入元素e为新的栈顶元素
	if(S.top - S.base >=S.stacksize) { // 栈满，追加存储空间
		S.base = (SElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType));
		if(!S.base) exit(OVERFLOW);    // 存储分配失败
		S.top = S.base+ S.staksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return OK;
}// Push

Status Pop(SqStack &S, ElemType &e){
	// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
	if(S.top = S.base) return ERROR;
	e = *--S.top;
	return OK;
}// Pop

对于栈的链式表示其操作易于实现。

3.2 栈的应用举例

由于栈结构具有后进先出的固有特性，致使栈成为程序设计中的有用工具。

3.2.1 数制转换

十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法是基于下列原理：
N=（N div d）×d +N mod d（其中：div为整除运算，mod为求余运算）
假设现在需要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值得八进制数。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说是从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。

void conversion(){
	// 对于输入的任意一个非负十进制数，打印输出与其等值的八进制数
	InitStack(S);      // 构造空栈
	scanf("%d",N);
	while(N){
		Push(S,N % 8);
	}
	while (!StackEmpty(S)){
		Pop(S,e);
		printf("%d",e);
	}
}// conversion

3.2.2 括号匹配的检验

在算法在中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。

3.2.3 行编辑程序

一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。由于在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法是不合适的。较好的一个做法是：设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。为此，可设这个输入缓冲区为一个栈结构，每当从终端接受了一个字符之后先作如下判别：如果它不是退格符或者退行符，则将该字符压入栈顶；如果是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，则将字符栈清为空栈。

3.2.4 迷宫求解

求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常采用的是穷举求解的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中使用栈也就是自然而然的事情了。

3.2.5 表达式求值

任何一个表达式都是由操作数、运算符和界限符组成的。操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。表达式求值是程序设计语言编译中的一个基本问题。它的实现是栈应用的又一个典型例子。

3.3 栈与递归的实现

栈还有一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。递归是程序设计中一个强有力的工具。其一，有很多函数是递归定义的。其二，有的数据结构，如二叉树、广义表等，由于节骨本身固有的递归特性，则它们的操作可递归地描述。其三，还有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简单。
与汇编程序设计中主程序和子程序之间的链接及信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的链接及信息交换需通过栈来进行。通常在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需完成3件事：（1）将所有的实在参数、返回地址等信息传递给被调用函数保存；（2）为被调用函数的局部变量分配存储区；（3）将控制转移到被调函数的入口。而从被调用函数返回调用函数之前，系统也应完成3件事情：（1）保存被调函数的计算结果；（2）释放被调函数的数据区；（3）依照被调函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时，按照后调用先返回的原则，上述函数之间信息传递和控制转移必须通过栈来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数退出时，就释放它的存储区，则当前正运行的函数的数据区必须在栈顶。
一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，因此，和每次调用相关的的一个重要的概念是递归函数运行的层次。为了保证递归函数正确执行，系统需设立一个“递归工作栈”作整真个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有的实在参数、所有的局部变量已经上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。
实际上，在调用函数和被调用函数之间不一定传递参数的值，也可以传递参数的地址。通常，每个程序设计语言都有它自己约定的传递方法，包括被调用函数的执行结果如何返回调用函数等。由于递归函数结构清晰，程序易读，而且它的正确性容易得到证明，因此利用允许递归调用的语言，如C语言进行程序设计时，给用户编制程序和调试程序带来很大方便。因此对这样一类递归问题时，不需要用户自己而由系统来管理递归工作栈。

3.4 队列

3.4.1 抽象数据类型队列的定义

和栈相反，队列是一种先进先出（first in first out，FIFO）的线性表，它只允许在表的一端进行插入，而在另一端删除元素。在队列中，允许插入的一端叫做队尾，允许删除的一端称为队头。假设队列为q=（a₁,a₂,…,a_n），那么a₁是对头元素，a_n是队尾元素。队列中的元素是按照a₁,a₂，…a_n的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在a₁,a₂，…a_n-1都离开队列之后，a_n才能退出队列。
除了栈和队列之外，还有一种限定性数据结构是双端队列。双端队列是限定插入和删除操作在表的两端进行的线性表。尽管双端队列看起来似乎比栈和队列灵活，但实际上在应用程序中远不及栈和队列有用。

3.4.2 链队列——队列的链式表示和实现

和线性表类似，队列也可以有两种存储表示。用链表表示的队列简称为链队列。一个链队列显然需要两个分别指向队头和队尾的指针，分别称为头指针和尾指针才能唯一确定。这里，和线性表的单链表一样，为了操作方便起见，我们也给链队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判决条件为头指针和尾指针均指向头节点。链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针。

// 单链队列——队列的链式存储结构
typedef struct QNode{
	QElemType     data;
	struct QNode *next;
}QNode, *QueuePtr;

typedef struct{
	QueuePtr front; // 队头指针
	QueuePtr  rear; // 队尾指针
}LinkQueue;

Status InitQueue(LinkQueue &Q){
	// 构造一个空队列Q
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if(!Q.front) exit ERROR;     // 存储分配失败
	Q.front.next = NULL;
	return OK;
}

Status DestroyQueue(LinkQueue &Q){
	// 销毁队列Q
	while(Q.front){
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
	return OK;
}

Status EnQueue(LinkQueue &Q,QElemType e){
	// 插入元素e为Q的新的队尾元素
	p = (QueuePtr)malloc(sizeof(QNode));
	if(!p) exit(OVERFLOW);    // 存储分配失败
	p->data = e; p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return OK;
}

Status DEQueue(LinkQueue &Q, QElemType &e){
	// 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
	if(Q.front == Q.rear) return ERROR;
	p = Q.front->next;
	e = p->data;
	Q.front->next = p-next;
	if(Q.rear == p) Q.rear = Q.front;
	free(p);
	return OK;
}

在上述模块的算法描述中，请注意删除队列头元素算法中的特殊情况。一般情况下，删除队伍头元素时仅需修改头结点中的指针，但当队伍中最后一个元素被删后，队伍尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）。

3.4.3 循环队列——队列的顺序表示和实现

在循环队列中，只凭等式Q.front = Q.rear无法判别队列空间是“空”还是“满”。可有两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置，指环状的下一位置上”作为队列呈“满”状态的标志。从上述分析可见，在C语言中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序设有循环队列，则必须为它设定一个最大队伍长度；若用户无法预估所用队列的最大长度，则宜采用链队列。

// 循环队列——队列的顺序存储结构
#define MAXQSIZE 100  // 最大队列长度
typedef struct{
	QElemType *base;   // 初始化的动态分配存储空间
	int front;         // 头指针，若队列不空，指向队列头元素
	int rear;          // 尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

Status InitQueue(SqQueue &Q){
	// 构造一个空队列Q
	Q.base =(QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
	if(!Q.base) exit(OVERFLOW);    // 存储分配失败
	Q.front = Q.rear = 0;
	return OK;
}

int QueueLength(SqQueue Q){
	// 返回Q的元素个数，即队列的长度
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

Status EnQueue(SqQueue &Q, QElemType e){
	// 插入元素e为Q的新的队尾元素
	if((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; // 队列满
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1)% MAXQSIZE;
	return OK;
}

Status DeQueue(SqQueue &Q, QElemType &e){
	// 若队列不空，则删除Q的队头元素，并用e返回其值，并返回OK，否则返回ERROR
	if(Q.front == Q.rear) return ERROR;
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK;
}

相关标签：数据结构 C语言数据结构 c语言

上一篇：数据结构（C语言版）严蔚敏吴伟民编著第1章绪论

下一篇：数据结构（C语言版）严蔚敏吴伟民编著第4章串

数据结构（C语言版）严蔚敏吴伟民编著第3章栈和队列