- 数据结构（C语言版）
- 邓文华主编
- 6507字
- 2020-08-28 01:27:57
3.1 栈
3.1.1 栈的定义及其基本运算
图3.1 栈的示意图
栈（Stack）是限制在表的一端进行插入和删除操作的线性表。允许进行插入、删除操作的这一端称为栈顶（Top），另一个固定端称为栈底。当表中没有元素时称为空栈。如图3.1所示的栈中有三个元素，进栈的顺序是a1、a2、a3，当需要出栈时其顺序为a3、a2、a1，所以栈又称为“后进先出”（Last-In First-Out，LIFO）或“先进后出”（First-In Last-Out，FILO）的线性表，简称“LIFO表”或“FILO表”。
（注：LIFO规范的写法有两种：Last-In First-Out、Last In，First Out。FILO类似。）
在日常生活中，有很多类似栈的例子，读者可以列举。在程序设计中，常常需要将数据按其保存时相反的顺序来使用，这时就需要用一个栈这样的数据结构来实现。
对于栈，常见的基本运算有以下几种。
（1）栈初始化：Init_Stack ( s )。
初始条件：栈s不存在。
操作结果：构造了一个空栈。
（2）判栈空：Empty_Stack ( s )。
初始条件：栈s已存在。
操作结果：若s为空栈，则返回1，否则返回0。
（3）入栈：Push_Stack ( s，x )。
初始条件：栈s已存在。
操作结果：在栈s的顶部插入一个新元素x，x成为新的栈顶元素，栈发生变化。
（4）出栈：Pop_Stack ( s )。
初始条件：栈s存在且非空。
操作结果：栈s的顶部元素从栈中删除，栈中少了一个元素，栈发生变化。
（5）读栈顶元素：Top_Stack ( s )。
初始条件：栈s存在且非空。
操作结果：栈顶元素作为结果返回，栈不变化。
3.1.2 栈的存储结构和基本运算的实现
由于栈是运算受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作不同而已。
1.顺序栈
利用顺序存储方式实现的栈称为顺序栈。类似于顺序表的定义，栈中的数据元素用一个预设的足够长度的一维数组来实现：datatype data[MAXSIZE]，栈底位置可以设置在数组的任意一个端点，而栈顶是随着插入和删除而变化的，用int top来作为栈顶的指针，指明当前栈顶的位置，同样将data和top封装在一个结构中，顺序栈的类型描述如下：
#define MAXSIZE 100
typedef struct
{ datatype data[MAXSIZE];
int top;
} SeqStack
定义一个指向顺序栈的指针：
SeqStack *s;
通常将0下标端设为栈底，这样空栈时栈顶指针top=-1；入栈时，栈顶指针加1，即s->top++；出栈时，栈顶指针减1，即s->top--。
栈顶指针top与栈中数据元素的关系如图3.2所示，其中图3.2（a）为空栈，图3.2（c）是A、B、C、D、E 5个元素依次入栈之后栈的状态及栈顶指针所指位置，图3.2（d）是在图3.2（c）之后E、D相继出栈，此时，栈中还有3个元素，或许最近出栈的元素D、E仍然在原先的单元存储中，但由于top指针已经指向了新的栈顶，则存储D、E的单元已经属于无效数据，意味着元素D、E已不在栈中了，通过这个示意图要深刻理解栈顶指针的作用。
图3.2 栈顶指针top与栈中数据元素的关系
对上述存储结构基本操作的实现如下。
（1）置空栈：首先建立栈空间，然后初始化栈顶指针。
SeqStack *Init_SeqStack( )
{ SeqStack *s;
S=malloc(sizeof(SeqStack));
s->top= -1; return s;
}
（2）判空栈。
int Empty_SeqStack(SeqStack *s)
{ if (s->top==-1) return 1;
else return 0;
}
（3）入栈。
int Push_SeqStack (SeqStack *s, datatype x)
{ if (s->top==MAXSIZE-1) return 0; /*栈满不能入栈*/
else { s->top++;
s->data[s->top]=x;
return 1;
}
}
（4）出栈。
int Pop_SeqStack(SeqStack *s, datatype *x)
{ if (Empty_SeqStack ( s ) ) return 0; /*栈空不能出栈 */
else { *x=s->data[s->top];
s->top--; return 1;
} /*栈顶元素存入*x，返回*/
}
（5）取栈顶元素。
datatype Top_SeqStack(SeqStack *s)
{ if ( Empty_SeqStack ( s ) ) return 0; /*栈空*/
else return (s->data[s->top] );
}
两点说明：
① 对于顺序栈，入栈时，首先判断栈是否满了，栈满的条件为s->top==MAXSIZE-1，栈满时，不能入栈，否则会出现空间溢出，引起错误，这种现象称为上溢。
② 出栈和读栈顶元素操作，先判断栈是否为空，为空时不能操作，否则会产生错误。通常栈空时常作为一种控制转移的条件。
2.链栈
用链式存储结构实现的栈称为链栈。通常链栈用单链表表示，因此其结点结构与单链表的结点结构相同，在此用LinkStack表示，即有：
typedef struct node
{ datatype data;
struct node *next;
} StackNode * LinkStack;
说明：top为栈顶指针，即LinkStack top。
因为栈中的主要运算是在栈顶插入、删除的，显然选链表的头部做栈顶是最方便的，而且没有必要像单链表那样为了运算方便附加一个头结点。通常将链栈表示为图3.3所示的形式。链栈基本操作的实现如下。
（1）置空栈。
图3.3 链栈示意图
LinkStack Init_LinkStack( )
{ return NULL;
}
（2）判栈空。
int Empty_LinkStack(LinkStack top)
{ if (top==NULL) return 1;
else return 0;
}
（3）入栈。
LinkStack Push_LinkStack(LinkStack top, datatype x)
{ StackNode *s;
s=malloc(sizeof(StackNode));
s ->data=x; s ->next=top; top=s;
return top;
}
（4）出栈。
LinkStack Pop_LinkStack (LinkStack top, datatype *x)
{ StackNode *p;
if (top==NULL) return NULL;
else { *x=top->data; p=top; top=top->next; free (p);
return top;
}
}
3.1.3 栈的应用举例
由于栈的“后进先出”特点，在很多实际问题中都利用栈做一个辅助的数据结构来进行求解，下面通过几个例子进行说明。
【例3.1】 数制转换问题。
将十进制数N转换为r进制的数，其转换方法为利用辗转相除法。以N=3467，r=8为例，转换方法如下：
按逆序取余数，即得转换结果：（3467）10=（6613）8。
可以看出，转换得到的八进制数是按低位到高位的顺序产生的，而转换结果的输出通常是从高位到低位依次输出，恰好与产生过程相反，因此，在转换过程中，每得到一位八进制数就将其进栈保存，转换完毕后再依次出栈，则正好是转换结果。
算法思想如下：当N>0时，重复步骤①和步骤②。
① 若N≠0，则将N % r压入栈s中，执行步骤 ②；若N=0，将栈s的内容依次出栈，算法结束。
② 用N/r代替N，返回步骤 ①。
算法实现如下，分别用两种不同的方法进行描述。
算法3.1（a） 算法3.1（b）
typedef int datatype;
void conversion( int N, int r)
{ SeqStack s;
datetype x;
Init_SeqStack(&s);
while ( N )
{ Push_SeqStack ( &s ，N % r );
N=N / r ;
}
while (! Empty_SeqStack(& s ) )
{ Pop_SeqStack (&s ，&x ) ;
printf (" %d"，x ) ;
}
}
#define L 10
void conversion( int N，int r )
{ int s[L], top; /*定义一个顺序栈*/
int x;
top=-1; /*初始化栈*/
while ( N )
{ s [++top]=N % r; /*将余数入栈 */
N=N / r ; /*商作为被除数继续*/
}
while ( top != -1)
{ x=s[top - - ];
printf( "%d", x );
}
}
算法3.1（a）是将对栈的操作抽象为模块调用，使问题的层次更加清楚；而算法3.1（b）中直接用int数组s和int 变量top作为一个栈来使用。两种描述方法的实现过程其实是相同的，只是前者的可读性要更清晰。初学者往往将栈视为一个很复杂的东西，不知道如何使用，通过这个例子可以消除栈的“神秘”。当应用程序中需要按数据保存时相反的顺序使用数据时，就要想到栈。通常用顺序栈较多，因为很便利。
在后面的例子中，为了在算法中表现出问题的层次，有关栈的操作调用了相关函数，像算法3.1（a）那样，对余数的入栈操作：Push_SeqStack(&s，N % r )；因为是用C语言描述，第一个参数是栈的地址才能对栈进行加工（在后面的例子中，为了算法清楚、易读，在不至于混淆的情况下，不再加地址运算符，请读者注意）。
【例3.2】 表达式求值问题。
表达式求值是程序设计语言编译中一个最基本的问题。它的实现也需要栈的运用。下面介绍的算法是由运算符优先级确定运算顺序的对表达式求值算法。
一个表达式是由运算数（operand）、运算符（operator）和界限符（delimiter）组成的有意义的式子。一般地，运算数既可以是常量又可以是被说明的变量或常量标识符。运算符从运算数的个数上分，有单目运算符和双目运算符；从运算类型上分，有算术运算符、关系运算符和逻辑运算符。界限符主要是指左右括号和表达式结束符。在此仅限于讨论只含常量的双目运算的算术表达式。
假设所讨论的算术运算符包括：+、-、*、/、%、^（乘方）和括号（）。
设运算规则为：
（1）运算符的优先级为：（）→ ^ → *、/、%→ +、-；
（2）有括号出现时先算括号内的，后算括号外的，对于多层括号，由内向外进行；
（3）乘方连续出现时先算最右面的。
可以将表达式作为一个满足表达式语法规则的串来存储，如3*2^（4+2*2-1*3）-5。
为实现表达式求值，需要设置两个栈：一个称为运算符栈OPTR，用以寄存运算符；另一个称为运算数栈OPND，用以寄存运算数和运算结果。求值的处理过程是：自左至右扫描表达式的每一个字符，当扫描到运算数时，就将其压入栈OPND；当扫描到运算符时，若这个运算符比OPTR栈顶运算符的优先级高则入栈OPTR，继续向后处理，若这个运算符比OPTR栈顶运算符的优先级低则从OPND栈中弹出两个运算数，从OPTR栈中弹出栈顶运算符进行运算，并将运算结果压入栈OPND，继续处理当前字符，直到遇到结束符为止。
根据运算规则，左括号“(”在栈外时它的级别最高，而进栈后它的级别则最低了；乘方运算的结合性是自右向左，所以，它的栈外级别高于栈内。也就是说，有的运算符栈内、栈外的优先级别是不同的。当遇到右括号“)”时，一直需要对OPTR栈进行出栈操作，并弹出相应的操作数，做对应的运算，直到遇到栈顶为左括号“(”将其出栈为止。
OPND栈初始化为空，为了使表达式中的第一个运算符入栈，OPTR栈中预设一个最低级的运算符“（”。根据以上分析，每个运算符的栈内、栈外优先级别如下：
以上算法的基本思想是：
（1）首先置OPND栈为空栈，表达式起始符“(”为OPTR栈的栈底元素；
（2）依次读入表达式中的每个字符，若是运算数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先级后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素为“(”且当前读入的字符为“#”)。
算法3.2 表达式求值算法。
OperandType EvaluateExpression( )
{ /*算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和运算数栈*/
/*OP为运算符集合*/
Init_Stack (OPTR)； Push_Stack (OPTR, '(' )；
Init_Stack (OPND)； c=getchar( )；
while ( c!='#' )
{ if (!In (c, OP)) /*不是运算符则进栈*/
{ Push_Stack (OPND,c); c=getchar(); }
else
switch (Precede(GetTop(OPTR),c))
case '<': /*栈顶元素优先权低*/
Push_Stack (OPTR,c); c=getchar();
break;
case '=': /*脱括号并接受下一字符*/
Pop_Stack (OPTR,x); c=getchar();
break;
case '>': /*退栈并将运算结果入栈*/
Pop_Stack (OPTR, theta);
Pop_Stack (OPND, b);
Pop_Stack (OPND, a);
Push_Stack (OPND, Operate(a, theta, b));
break;
} /*Switch*/
} /*while*/
return GetTop(OPND);
} /*EvaluateExpression*/
算法3.2中还调用了两个函数。其中，Precede是判定OPTR栈的栈顶运算符与读入的运算符之间优先关系的函数；Operate为进行二元运算a θ b的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算的结果。
表达式3*2^(4+2*2-1*3)-5求值过程中两个栈的状态情况如表3.1所示。
在实际编译程序中，为了处理方便，常常首先把表达式转换成等价的后缀表达式。所谓后缀表达式，是指将运算符放在运算数之后的表达式。在后缀表达式中，不再需要括号，所有的计算按运算符出现的顺序严格地从左向右进行，而不用再考虑运算符的级别和运算规则。如表达式3*2^(4+2*2-1*3)-5的后缀表达式为：3 2 4 2 2 *+1 3 * - ^ * 5 - 。
表3.1 表达式3*2^(4+2*2-1*3)-5的求值过程
3.1.4 栈与递归的实现
栈的另一个非常重要的应用就是在程序设计语言中实现递归。递归是指在定义自身的同时又出现对自身的引用。如果一个函数在其定义体内直接调用自己，则称其为直接递归函数；如果一个函数经过一系列中间调用语句，通过其他函数间接调用自己，则称其为间接递归函数。
1.具有递归特性的问题
现实中，许多问题具有固有的递归特性。
（1）递归定义的数学函数
很多数学函数是递归定义的，如阶乘函数可写成递归定义：
以上函数用C语言实现如下：
long Fact ( int n )
{ long f; /*长整数类型可以使数据不容易溢出*/
if ( n== 0 ) f=1;
else f=n * Fact( n - 1 );
return f;
}
（2）递归数据结构的处理
在本书的后续章节中将要学习的一些数据结构，如二叉树、树等，由于结构本身固有的递归特性，因此自然地采用递归方法进行处理。
（3）递归求解方法
许多问题的求解可以通过递归分解的方法实现，虽然有些问题本身没有明显的递归结构，但用递归方法求解比迭代求解更简单，也更直观，如八皇后问题、Hanoi塔问题等。
n阶Hanoi塔问题：假设有三个分别命名为X、Y、Z的塔座，在塔座X上叠放着n个直径大小各不相同、小盘压在大盘之上的圆盘堆。现要求将塔座X上的n个圆盘移至塔座Z上，并仍按同样的顺序叠放。移动圆盘时必须遵循下列规则：
① 每一次只能够移动一个圆盘；
② 圆盘可以插放在X、Y和Z中任何一个塔座上；
③ 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
解决以上问题的基本思想如下：
当n=1时，问题简单，只要将该圆盘从塔座X上移动到塔座Z上即可；
当n>1时，需要利用塔座Y作为辅助塔座，若能设法将除底下最大的圆盘之外的n-1个圆盘从塔座X移动到塔座Y上，就可以将最大的圆盘从塔座X移至塔座Z上，然后再将塔座Y上的其余n-1个圆盘移动到塔座Z上。而如何将n-1个圆盘从一个塔座移至另一个塔座，则与原问题具有相同的特征属性，只是问题的规模小1，因此可以用同样的方法求解。
算法3.3 求解n阶Hanoi塔问题的递归算法。
void Hanoi ( int n, char x, char y, char z )
/*将塔座x上从上到下编号为1至n，且按直径由小到大叠放的n个圆盘，按规则移动到塔座
z上，塔座y用做辅助塔座。*/
{ if ( n==1 )
move ( x, n, z ) ; /*将编号为1的圆盘从塔座x移动到塔座z*/
else
{ Hanoi ( n-1, x, z, y ); /*将x上编号为1至n-1的圆盘移至y，z作为辅助塔座*/
move ( x, n, z ); /*将编号为n的圆盘从x移动到z */
Hanoi ( n-1, y, x, z ); /*将y上编号为1至n-1的圆盘移至z，x作为辅助塔座*/
}
}
掌握递归的具体执行过程对于理解递归具有重要作用。
下面就以三个圆盘的移动为例来说明以上递归函数Hanoi ( 3, A, B, C )的具体递归调用过程，如图3.4所示。
Hanoi ( 3, A, B, C ) /*调用函数hanoi将A上的3个圆盘移至B，C作为辅助塔*/
Hanoi ( 2, A, C, B ); /*将A上的2个圆盘移至B，C作为辅助塔*/
Hanoi ( 1, A, B, C ); /*将A上的1个圆盘移至C */
move ( A, 1, C ); /*将1号圆盘从A搬到C */
move ( A, 2, C ); /*将2号圆盘从A搬到B */
Hanoi ( 1, C, A, B ); /*将C上的1个圆盘移至B */
move ( C, 1, B ); /*将1号圆盘从C搬回到B*/
move ( A, 3, C ); /*将3号圆盘从A搬到C */
Hanoi ( 2, B, A, C ); /*将B上的2个圆盘移至C，A作辅助塔*/
Hanoi ( 1, B, C, A ); /*将B上的1个圆盘移至C */
move ( B, 2, C ); /*将2号圆盘从B搬到C */
Hanoi ( 1, A, B, C ); /*将A上的1个圆盘移至C */
move (A, 1, C ); /*将1号圆盘从A搬到C */
图3.4 Hanoi塔问题的递归函数运行示意图
通过上面的例子可以看出，递归既是强有力的数学方法，又是程序设计中一个非常有用的工具。其特点是对问题描述简洁，结构清晰。
2.递归算法的设计方法与递归过程的实现
所谓递归算法，就是在算法中直接或间接调用自身的算法。应用递归算法的前提有两个：
（1）原问题可以层层分解为类似的子问题，且子问题比原问题的规模更小；
（2）规模最小的子问题具有直接解，即不需要再调用自身。
设计递归算法的原则就是通过自身的简单情况来定义自身，设计递归算法的方法如下。
（1）寻找分解方法：将原问题转化为子问题求解（例如n!=n*(n-1)!）。
（2）设计递归出口：即根据规模最小的子问题确定递归的终止条件（例如求解n！，当n=1时，n!=1）。
为更好地理解递归函数的实现过程，有必要回顾函数调用的系统实现过程。在实现函数调用过程时，需要解决两个问题：一是如何实现函数的调用；二是如何实现函数的返回。
实现函数调用，系统需要做三件事：
（1）保留调用函数本身的参数与返回地址；
（2）为被调用函数的局部变量分配存储空间，并给对应的参数赋值；
（3）将程序控制转移到被调用函数的入口。
从被调用函数返回到调用函数之前，系统也应完成三件事：
（1）保存被调用函数的计算结果，即返回结果；
（2）释放被调用函数的数据区，恢复调用函数原先保存的参数；
（3）依照原先保存的返回地址，将程序控制转移到调用函数的相应位置。
在实现函数调用时，应按照“先调用的后返回”原则处理调用过程，因此上述函数调用时函数之间的信息传递和控制转移必须通过栈来实现。在实际实现中，系统将整个程序运行所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区（压栈），而当从一个函数退出时，就释放它的存储区（出栈）。显然，当前正在运行的函数的数据区必然在栈顶。
在一个递归函数的运行过程中，调用函数和被调用函数是同一个函数，因此，与每次调用时相关的一个重要概念就是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层，从第1层再次调用递归函数为进入第2层，以此类推，从第i层递归调用自身则进入“下一层”，即第i+1层。反之，退出第i层则应返回至“上一层”，即i-1层。为了保证递归函数正确执行，系统需要设立一个递归工作栈作为整个递归函数执行期间的数据存储区。每层递归所需信息构成一个工作记录，其中包括递归函数的所有实参和局部变量，以及上一层的返回地址等。每进入一层递归，就产生一个新的工作记录压栈；每退出一层递归，就从栈顶弹出一个工作记录释放。因此当前执行层的工作记录必为栈顶元素，称该记录为活动记录，并称指示活动记录的栈顶指针为环境指针。由于递归工作栈由系统来管理，不需要用户操心，所以用递归法编程非常方便。
【例3.3】 2阶Fibonacci数列的递归实现。
算法3.4 求2阶Fibonacci数列的递归算法。
int Fib ( int n )
{ if ( n== 0 ) return 0;
else if ( n== 1 ) return 1;
else return Fib ( n –1 )+Fib ( n–2 )
}
图3.5给出了Fib(4)递归调用过程的示意图，图3.6给出了递归调用过程中栈的状态变化情况。
图3.5 Fib(4)递归调用过程示意图
图3.6 Fib(4)递归调用过程中栈的状态变化过程
可以看出，计算Fib( n )的递归函数在n>1时的执行过程大致可分为五个阶段：
① 调用Fib ( n-1 )，即进栈操作；
② 返回Fib ( n-1 )的值，即出栈操作；
③ 调用Fib(n-2 )，再次进栈；
④ 返回Fib ( n-2 )的值，出栈；
⑤ 计算Fib ( n )的值，然后返回。