数据结构教案第三章栈和队列

1、3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.4 行编辑程序 3.2.5 表达式求值 3.1 栈3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后

2、进先出表（LIFO）。3.1.2 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top例、一叠书或一叠盘子。 栈的抽象数据类型的定义如下：P44 a n a n-1 a2 a1栈顶 栈底top7 6 5 4 3 2 1 -1 top用来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定

3、义如下： # define StackSize 100 typedef char DataType; typedef struct DataType dataStackSize; int top; SeqStack; 设S是SeqStack类型的变量。若栈底位置在向量的低端，即s.data0是栈底元素，那么栈顶指针s.top是正向增加的，即进栈时需将s.top加1，退栈时需将s.top 减1。因此，s.topdata=x; pnext=top; top=p ; return top; （4）出栈DataType Pop(LinkStack &top) DataType x; Stack

4、Node *q=top; if(stackempty(top) error(“stack underflow.”); x=qdata; top=qnext; free(q); return x; （5） 取栈顶元素 DataType stacktop(LinkStack top) if(stackempty(top) error(“stack is empty.”); return topdata; 3.2 栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。 3.2.1 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解

5、决方法很多,其中一个简单算法基于下列原理: N=(N div d)*d+N mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 void conversion( ) SeqStack s; initstack(s); scanf (“%d”,&n); while(n) Push(s,n%8); n=n/8; while(! stackempty(s) e=Pop(s); /退栈 printf(“%d”,e); 3.2.2

6、 括号匹配的检验 （）（）（） 对于输入一个表达式字符串，试写一个算法判断其中括号是否匹配，若匹配则返回TRUE,否则返回FALSE。 解题分析：循环读入表达式中字符，如遇左括号就进栈；若遇右括号，则判断栈受否为空，若空则返回FALSE,否则退栈；循环结束后再判断栈是否为空，若栈空则说明不匹配，否则匹配。算法如下： lBoolean Expr( )l SeqStack s; initstack(s);l ch=getchar( );l while(ch!=n) l if(ch=( ) Push(s,ch);l else if(ch=) )l if(stackempty(s)l return F

7、ALSE;l else x=Pop(s);l ch=getchar( );l l if(stackempty(s) return TRUE;l else return FALSE;l l 3.2.3 字符串回文的判断 利用顺序栈的基本运算，设计一个算法，判断一个给定的字符串是否具有中心对称，即“回文”（也就是正读和反读均相同的字符序列）。例如：ababbaba、abcba都是中心对称的回文。 解题分析：首先要知道中心在哪儿，有了中心位置后，就可以从中间向两头进行比较。若完全相同，则该字符串是回文，否则不是。先求串的长度，将串的前一半入栈，再利用退栈操作将其与后一半字符比较。因此，设计算法如下：

8、 int Symmetry(char str ) SeqStack s; int i=0,j,k; initstack(s); while(stri) i+; /stri!=0 for(j=0;ji/2;j+) Push(s,strj); /前一半字符入栈 k=(i+1)/2; for(j=k;jnext=NULL; （2）判队空 int queueempty(LinkQueue Q) return q.front=qrear; （3）入队列 void enqueue(LinkQueue &Q, DataType x) QueueNode *p; p=(QueueNode * )mal

9、loc(sizeof(QueueNode); pdata=x; pnext=NULL; Q.rearnextr=p; Q.rear=p; (4) 出队列 在出队算法中,当原队中只有一个结点时,不仅需要修改头结点指针域，还序修改尾指针。因此只修改头指针，删除头结点，使链队列的队头结点成为新的头结点。 DataType dequeue(LinkQueue &Q) DataType x; QueueNode *p; if(queueempty(Q) error(“queue underflow”); p=Q.front; x=pnext-data; Q.front=pnext; free(p

10、); return x; (5) 取队头元素 DataType queuefront(LinkQueue Q) if(queueempty(Q) error(“queue is empty.”); return Q.frontnext-data; l3.5 栈和队列综合应用- 表达式求值问题l 我们在很早就开始学习如何写和计算表达式。可以想象，大部分小学生开始在计算诸如8+5*(7-3)之类的表达式时，都碰到了一些困难。通过一段的学习之后，学生就能够掌握和描述计算步骤了，例如上述表达式可描述为：7减去3得4，5乘以4得20，8加20得到28，因此表达式的值为28。如果进一步问为什么要以这个次序

11、计算该表达式，回答起来就比较困难了。当然，随着时间的推移，人们逐步熟悉了这种表达式的求值顺序，即运算规则：有括号先算括号内，无括号时，先做乘除法，再做加减法；对于相同的级别的运算按从左到右次序计算。这是人们一直沿袭下来使用的手工运算规则。如今，计算机已成为人们生活中不可缺少的使用工具。那么，计算机能否计算给定的算术表达式的值呢？回答是肯定的。表达式计算是实现程序设计语言的基本问题之一，也是栈和队列应用的一个典型的例子。l 要求：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，利用给定的算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值过程中运算符栈、操作数栈、输入字符和

12、主要操作的变化过程。l 分析：人们在书写表达式时通常采用的是一种为“中缀”表示形式，也就是将运算符放在两个操作数中间，用这种“中缀”形式表示的表达式称为中缀表达式。但是，这种表达式表示形式对计算机处理来说是不大合适的。对于表达式的表示还有一种形式，称之为“后缀”表达式，即将运算符紧跟在两个操作数的后面。例如前面的中缀表达式8+5*(7-3)可以写成8573 - * +的后缀表达式，要计算该表达式，可以从左到右扫描它，直到遇到一个运算符，在这个后缀表达式中所遇到的是减号“-”。由于每个运算符对它直接前面的两个操作数进行运算，于是就执行7-3的运算，并用此运算结果4取代原表达式的7、3、-；这样原

13、表达式就变成了854 * +；接着进行下一步计算得到新表达式8 20 +，再计算得结果 28。这种计算方法既简单又方便，特别是适合计算机的处理方式。因此，要用计算机来处理计算算术表达式问题，首先要解决的问题是如何将人们习惯书写的中缀表达式转换成计算机容易处理的后缀表达式。 l3.5.1. 中缀表达式到后缀表达式的转换l 如何将一个中缀表达式转换成后缀表达式呢？我们来分析一下，先假定在算术表达式中只含有四种基本运算符，操作数是在10以内的整数，没有括号。假设有一个中缀表达式4+2*3，它的后缀表达式为423 * +。在扫描到中缀表达式中的2后，比能立即输出 +，因为 *具有较高的优先级，必须先运

14、算，因此先要保存 +。也就是说，新扫描到的运算符优先级必须与前一个运算符的优先级做比较，如果新的运算符优先级高，就要向前一个运算符那样保存它，直到扫描到第二个操作数，并将它输出后才能将该运算符输出。因此，在转化中必须保存两个运算符，后保存的运算符先输出。用计算机来实现这一转化过程，就需要用到后进先出即栈的概念。l 如果在中缀表达式中含有小括号，那么由于括号隔离了优先级规则，它在整个表达式的内部产生了完全独立的子表达式，因此，就需要有所改变前面的算法。当扫描到一个左括号时，需要将其压入栈中，使其在栈中产生一个“伪栈底”。这样，算法就可以像前面一样的进行。但当扫描到一个右括号时，就需要将从栈顶到这

15、个“伪栈底”中的所有运算符全部弹出，然后再将这个“伪栈底”删除。l 综上分析，可得到通过栈将中缀表达式转换为后缀表达式的算法思想如下：l 顺序扫描中缀算术表达式，当读到数字时直接将其送至输出队列中；当读到运算符时，将栈中所有优先级高于或等于该运算符的运算符弹出，送至输出队列中，再将当前运算符入栈；当读入左括号时，即入栈；当读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列中，再删除栈中的左括号。l1算法设计l 在有了上述分析之后，实现其转换的算法就不难给出。为了简化算法，我们把括号也作为运算符看待，并规定它的优先级为最低，另外将表达式中的操作数规定为1位数字字符，运算

16、符也只包括 +、-、*、/ 四种。读者可根据需要，可对算法的功能加以扩充。l为了方便边界条件（栈空）的判断，提高算法的运行效率，在扫描读入中缀表达式之前，在空栈中预先压入一个“#”字符，作为栈底元素，另外，在表达式的最后增加一个“#”字字符。作为中缀表达式的结束标志，该结束符与栈底元素“#”配对。本算法不包括输入表达式的语法检查，但可以过滤掉输入符号之间的空格。其具体算法如下：l lvoid CTPostExp(SeqQueue &Q )l SeqStack S; /运算符栈l char c, t ; InitStack(S); /初始化栈 l Push(S,#); /压入栈底元素#l

17、 do /扫描中缀表达式l c=getchar( );l switch(c) l case : break; /去除空格符l case 0 : case 1: case 2: case 3: case 4: case 5: l case 6 : case 7: case 8: case 9: EnQueue(Q,c); break;l case ( : Push(S,c); break;l case ) : case #:l do t=Pop(S);l if(t!=(& t!=#) EnQueue(Q,t);l while(t!=(& S-top!=-1); break;l l

18、 l case + :l case - :l case * :l case / :l while(Priority(c) =0 & ch=9) Push(S,ch-0);l else y=Pop(S); x=Pop(S);l switch(ch) l case + : Push(S,x+y); break;l case - : Push(S,x-y); break;l case * : Push(S,x*y); break;l case / : Push(S,x/y); break;l l l l return GetTop(S);l 习 题1、设将整数以万计、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题： （1）若入栈次序为push(1),pop(),push(2)，push(3)，pop()，pop( )，push(4)，pop( )，则出栈的数字序列为什么？ （2）能否得到出栈序列车员423和平共处五项原则432？并说明为什么不能得到或如何得到。 （3）请分析1、2、3、4的24种排列中，哪些