第三章(数据结构)

1、第三章第三章 栈和队列栈和队列第第1 1页页【学习目标】【学习目标】1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。用问题中正确选用它们。2. 熟练掌握栈类型的两种实现方法。熟练掌握栈类型的两种实现方法。3. 熟练掌握循环队列和链队列的基本操作实现算法。熟练掌握循环队列和链队列的基本操作实现算法。4. 理解递归算法执行过程中栈的状态变化过程。理解递归算法执行过程中栈的状态变化过程。 【知识点】【知识点】顺序栈、链栈、循环队列、链队列顺序栈、链栈、循环队列、链队列 注意它们的基本操作实现时的特殊情况，如栈满和栈空

2、、注意它们的基本操作实现时的特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法队满和队空的条件以及它们的描述方法 。【学习指南】【学习指南】 第第2 2页页 栈栈和和队列队列是在程序设计中被广泛使用的两种线性是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，数据结构，它们的特点在于基本操作的特殊性，栈必栈必须按须按后进先出后进先出的规则进行操作的规则进行操作，而，而队列必须按队列必须按先先进先出进先出的规则进行操作的规则进行操作。和线性表相比，它们的插。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性入和删除操作受更多的约束和限定，故又称为

3、限定性的线性表结构。的线性表结构。 和线性表相比，从和线性表相比，从数据结构数据结构的角度看，它们的角度看，它们都是线性结构，即数据元素之间的关系相同。但它都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是作集不同外，主要区别是对插入和删除操作的对插入和删除操作的限定限定。 第第3 3页页 线性表：线性表： Insert(L,i,x) Delete(L,i) (1in+1) (1in)栈：栈：Insert(L,n+1,x) Delete(L,n)队列：队列：Insert(L,n+1,x) D

4、elete(L,1) 插插 入入删删 除除线性表线性表允许在表内任一位置进行插入和删除；允许在表内任一位置进行插入和删除；栈栈只允许在表尾一端进行插入和删除；只允许在表尾一端进行插入和删除；队列队列只允许在表尾一端进行插入，在表头一端进行只允许在表尾一端进行插入，在表头一端进行删除。删除。 第第4 4页页3.1.1栈的类型定义栈的类型定义 栈（栈（Stack）是限定只能在表的一端进行插入和删除操作是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作的线性表。在表中，允许插入和删除的一端称作栈顶栈顶(top)，不允许插入和删除的另一端称作不允许插入和删除的另一端称作栈

5、底栈底(bottom) 。 通常称通常称往栈顶插入元素的操作为往栈顶插入元素的操作为入栈入栈，称，称删除栈顶元素的操作为删除栈顶元素的操作为出栈出栈。因为后入栈的元素先于先。因为后入栈的元素先于先入栈的元素出栈，故被称为是一种入栈的元素出栈，故被称为是一种后进先出后进先出的结构，因此又称的结构，因此又称LIFO（LastIn First Out的缩写）的缩写）表表 如左图所示的铁路调度站表示栈的特点如左图所示的铁路调度站表示栈的特点 第第5 5页页类型定义如下类型定义如下：ADT Stack 数据对象：数据对象：D ai| ai ElemSet, i=1,2,.,n, n0 数据关系：数据关系

6、：R1 | ai-1,aiD, i=2,.,n 约定约定 an端为栈顶，端为栈顶，a1 端为栈底端为栈底。 基本操作：基本操作：InitStack(&S) 构造一个空栈构造一个空栈 S。DestroyStack(&S) 初始条件：栈初始条件：栈 S 已存在。操作结果：栈已存在。操作结果：栈 S 被销毁。被销毁。ClearStack(&S) 初始条件：栈初始条件：栈 S 已存在。操作结果：将已存在。操作结果：将 S 清为空栈。清为空栈。 StackEmpty(S) 判空，通常以它作为循环结束的条件判空，通常以它作为循环结束的条件 GetTop(S, &e) 取栈顶元素，只以取栈顶元素，只以 e

7、返回栈顶元素，并不从栈中删除返回栈顶元素，并不从栈中删除Push(&S, e) 入栈操作入栈操作 Pop(&S, &e) 出栈操作，不仅以出栈操作，不仅以 e 返回栈顶元素，并将它从栈中删除。返回栈顶元素，并将它从栈中删除。 ADT Stack 第第6 6页页3.1.2 栈的存储表示和操作的实现栈的存储表示和操作的实现一、顺序栈类型的定义一、顺序栈类型的定义 和线性表类似，栈也有两种存储表示，其顺序存储结构简称和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈。为顺序栈。和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的

8、存储空间，最多元素的存储空间，base 为这个存储空间的基地址，也为这个存储空间的基地址，也即一维数组的地址。即一维数组的地址。从名称来讲，从名称来讲，“栈顶指针栈顶指针”意为指示栈顶元素在栈中的位置，意为指示栈顶元素在栈中的位置，但它的值实际是栈中元素的个数，和顺序表中的但它的值实际是栈中元素的个数，和顺序表中的 length 值值的意义相同。的意义相同。为了应用方便，这个为了应用方便，这个最大空间的容量最大空间的容量应由使用这个顺序栈应由使用这个顺序栈的程序员决定，它的默认值和顺序表的默认值相同。的程序员决定，它的默认值和顺序表的默认值相同。第第7 7页页v顺序栈的结构顺序栈的结构top指

9、向压栈时下一个元素将要存放的位置。指向压栈时下一个元素将要存放的位置。出栈时出栈时top减一指向弹栈时下一个元素的取值位置。减一指向弹栈时下一个元素的取值位置。栈空的条件：栈空的条件：top=base栈满的条件：栈满的条件：top-base = stacksizetoptopbase空栈空栈basetopABCABCbase满栈满栈DE 栈的表示和实现栈的表示和实现非空非满栈非空非满栈第第8 8页页v顺序表示顺序表示 #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; S

10、ElemType *top; int stacksize; SqStack;其中其中stacksize表示栈当前可以使用的最大容量。表示栈当前可以使用的最大容量。Base为栈底，为栈底，Top为栈顶。栈顶指针指向栈顶元为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压栈时元素所放的位置）素的下一个位置（即下次压栈时元素所放的位置） 顺序队列顺序队列第第9 9页页v基本操作的实现基本操作的实现：初始化栈初始化栈 Status InitStack(SqStack &S) /构造一个空栈构造一个空栈 S.base = (SElemType *)malloc (STACK_INIT_SIZE*size

11、of (SElemType); if (!S.base) exit (OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; /InitStack 第第1010页页压栈压栈: Status Push(SqStack &S, SElemType e) /元素元素e插入到栈中，成为新的栈顶插入到栈中，成为新的栈顶 if (S.top-S.base=S.stacksize) /栈满栈满 S.base=(SElemType *)realloc (S.base, (S.stacksize+STACKINCREMENT) *

12、 sizeof(SElemType); if (!S.base) exit (OVERFLOW); S.top = S.base + S.stacksize; S.stacksize+=STACKINCREMENT; / if *S.top+ = e; return OK; /Push 第第1111页页弹栈弹栈: Status Pop(SqStack &S, SElemType &e) /从栈顶读取数据放入从栈顶读取数据放入e内，栈中下一元素所内，栈中下一元素所 /在位置成为新的栈顶在位置成为新的栈顶 if（S.top = = S.base）return ERROR; /栈栈空空 e = *

13、- S.top; return OK; /Pop 注意注意top的操作顺序和值的变化。的操作顺序和值的变化。 压栈：压栈：valuetop; top+; 弹栈：弹栈：top-; top-value; 第第1212页页Status GetTop(SqStack S,SElemType &e) if (S.top=S.base) return ERROR; e=*(S.top-1); return OK;思考：语句思考：语句e=*(S.top-1); 改为改为e=*(-S.top);是是否正确？否正确？第第1313页页二、链栈二、链栈链栈即为栈的链式存储结构。链栈即为栈的链式存储结构。 链栈的定义

14、更简单，结点结链栈的定义更简单，结点结构和单链表中的结点结构相构和单链表中的结点结构相同，无须重复定义。注意同，无须重复定义。注意链链栈中指针的方向是从栈顶指栈中指针的方向是从栈顶指向栈底的，这正好和单链表向栈底的，这正好和单链表是相反的。是相反的。第第1414页页能否将链栈中的指针方向反过来，从栈底到栈顶？能否将链栈中的指针方向反过来，从栈底到栈顶？ 不行不行，如果反过来的话，删除栈顶元素时，为修改，如果反过来的话，删除栈顶元素时，为修改其前驱指针，需要从栈底一直找到栈顶。其前驱指针，需要从栈底一直找到栈顶。 因为链栈的操作是线形表链式存储结构的特例，因为链栈的操作是线形表链式存储结构的特例

15、，因此，相关操作可以自己总结出来。因此，相关操作可以自己总结出来。 第第1515页页v压栈的处理：压栈的处理： p=malloc(Lnode); p-next = s-next; s-next=p;弹栈的处理弹栈的处理: p=s-next; s-next=s-next-next;spp 栈的链式表示：栈的链式表示： 假设以首结点作为栈顶，链带有头结点。假设以首结点作为栈顶，链带有头结点。第第1616页页补充：一种新的栈的类型定义 # define StackSize 100 typedef char datatype; typedef struct datatype datastacksize

16、; int top; seqstack; SeqStack *s;思考：如何判断空栈和满栈思考：如何判断空栈和满栈第第1717页页3.2、栈的应用举例、栈的应用举例 3.2.1 数制转换数制转换 由于栈的操作具有后进先出的固有特性，致使栈成为程由于栈的操作具有后进先出的固有特性，致使栈成为程序设计中的有用工具。反之，凡应用问题求解的过程具有序设计中的有用工具。反之，凡应用问题求解的过程具有后进先出后进先出的天然特性的话，则求解的算法中也必然需要利的天然特性的话，则求解的算法中也必然需要利用用栈栈。 十进制数十进制数N和其他和其他d进制数的转换是计算机实现计算的基本进制数的转换是计算机实现计算的

17、基本问题，其解决方法很多，其中一个简单算法基于下列原理：问题，其解决方法很多，其中一个简单算法基于下列原理：N = (N div d)d + N mod d (其中：其中：div 为整除运算，为整除运算，mod 为求余运算为求余运算) 例如：例如：(1348)10=(2504)8 N N div 8 N % 8 1348 168 4 168 21 0 21 2 5 2 0 2 第第1818页页假设现要编制一个满足下列要求的程序：对于假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出输入的任意一个非负十进制整数，打印输出与其等值的八进制数。与其等值的八进制数。八进制的

18、各个数位产生的顺序是从低位到高位八进制的各个数位产生的顺序是从低位到高位的，而打印输出的顺序，一般来说应从高位的，而打印输出的顺序，一般来说应从高位到低位，这恰好和计算过程相反。到低位，这恰好和计算过程相反。 第第1919页页void conversion ()/ 对于输入的任意一个非负十进制整数，打印输出与其等值的对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数八进制数InitStack(S); / 构造空栈构造空栈scanf(“%d”,N)/ 输入一个十进制数输入一个十进制数while(N)Push(S,N % 8);/ “余数余数”入栈入栈N = N/8;/ 非零非零“商商”

19、继续运算继续运算 / whilewhile (!StackEmpty) / 和和“求余求余”所得相逆的顺序输出八进制的各位数所得相逆的顺序输出八进制的各位数Pop(S,e);cout e; / while / conversion 第第2020页页 检验括号是否匹配的方法可用检验括号是否匹配的方法可用期待的急迫程度期待的急迫程度这个概念这个概念来描述。即来描述。即后出现的后出现的左括弧左括弧，它等待与其匹配的，它等待与其匹配的右括弧右括弧出出现的现的急迫急迫心情要比先出现的左括弧高心情要比先出现的左括弧高。换句话说，。换句话说，对对左括左括弧弧来说，后出现的比先出现的来说，后出现的比先出现的优

20、先优先等待检验等待检验，对对右括弧右括弧来说，每个出现的右括弧要去找在它之前来说，每个出现的右括弧要去找在它之前最后最后出现的那个左出现的那个左括弧去匹配括弧去匹配。显然，必须将先后出现的左括弧依次保存，为了。显然，必须将先后出现的左括弧依次保存，为了反映这个优先程度，反映这个优先程度，保存左括弧的结构用栈最合适保存左括弧的结构用栈最合适。这样对出。这样对出现的右括弧来说，只要现的右括弧来说，只要栈顶元素栈顶元素相匹配即可。如果在栈顶的相匹配即可。如果在栈顶的那个左括弧正好和它匹配，就可将它从栈顶删除。那个左括弧正好和它匹配，就可将它从栈顶删除。什么样的情况是什么样的情况是“不匹配不匹配”的情

21、况呢？的情况呢？1来的右括弧非是所来的右括弧非是所“期待期待”的；的；2来的是来的是“不速之客不速之客”；3直到结束，也没有到来所直到结束，也没有到来所“期待期待”的。的。这三种情况对应到栈的操作即为：这三种情况对应到栈的操作即为：1和栈顶的左括弧不相匹配；和栈顶的左括弧不相匹配；2栈中并没有左括弧等在哪里；栈中并没有左括弧等在哪里；3栈中还有左括弧没有等到和它相匹配的右括弧。栈中还有左括弧没有等到和它相匹配的右括弧。 3.2.2 、括弧匹配检验、括弧匹配检验第第2121页页1“匹配匹配”不是不是“相等相等”。因此若在遇到左括弧。因此若在遇到左括弧时是将当前这个左括弧进栈的话，那么在遇到右括时

22、是将当前这个左括弧进栈的话，那么在遇到右括弧时必须分别不同情况进行判别。弧时必须分别不同情况进行判别。2和栈顶元素进行比较的前提是栈不为空。因此和栈顶元素进行比较的前提是栈不为空。因此判别当前出现的右括弧是否和相应左括弧匹配之前判别当前出现的右括弧是否和相应左括弧匹配之前有否先判别当前栈是否为空。有否先判别当前栈是否为空。3“没有等到没有等到”即为栈不空的情况。因此在算法即为栈不空的情况。因此在算法结束之前，要判别栈是否已为空了？结束之前，要判别栈是否已为空了？4 此外别忘了使用栈之前一定要进行初始化。此外别忘了使用栈之前一定要进行初始化。 注意：注意：第第2222页页下面这段程序是只检测下面

23、这段程序是只检测“（”和和“）”的；的；Static pair()inistack(s);ch=getchar();While(ch!=eof) doswitch(ch) case(: push(s,();case): if (not empty(s) pop(s); else return(false); if(empty(s) return(true); else return(false);思考：不设栈，而设一个变量思考：不设栈，而设一个变量count,count初值为初值为0，遇到，遇到“（”就加就加1，遇到，遇到“）”就减就减1，如果最后，如果最后count=0,则匹配，否则不则匹配

24、，否则不匹配，可以吗？为什么？匹配，可以吗？为什么？第第2323页页 （）的配对问题。（）的配对问题。 （5+（2-6）+10）+6 *2 （5+（2-6）+10+6）*2 （5+2-6）+10）+6） *2 判断的标准：判断的标准： 方法：见到左括号压栈，方法：见到左括号压栈， 见到右括号弹栈，并和弹出的数见到右括号弹栈，并和弹出的数 据配对。据配对。 课堂练习：课堂练习： 假设表达式结束符为假设表达式结束符为#, 试写出其算法试写出其算法第第2424页页int MatchJudge() /匹配返回匹配返回1，不匹配返回，不匹配返回0 InitStack(S); scanf(“%c”, ch

25、); while (ch!=“#”) if (ch=“(” | ch=“” | ch=“”) push (s, ch); if (ch=“)” ） pop(s,e); if (e“(”) return 0; if (ch=“” ) pop(s,e); if (e“”) return 0; if (ch=“”) pop(s,e); if (e“”) return 0; scanf(“%c”, ch); /while if StackEmpty(s) return 1 else return 0; /MatchJudge第第2525页页3.2.3 行编辑程序行编辑程序在编辑程序中，设立一个输入缓冲

26、区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。字符“#”为删节符，删除左边一个可见字符。字符“”为删行符，删除当前一行。用栈来处理一行，一行结束即用户输入n。例如：例如：用户输入：用户输入：whli#ilr#e(s#*s) outchaputchar(*s= # +);则实际有效为：则实际有效为： while(*s) putchar(*s+);第第2626页页void LineEdit( ) Initstack(S); ch=getchar( ); while(ch!=EOF) while(ch!=EOF & ch!=n) switch(

27、ch) case # : Pop(s,c); case : Clearstack(s); default : Push(S,ch); ch=getchar( ); ClearStack(s); if(ch!=eof) ch=gethar( ); DestroyStack(s); 第第2727页页3.2.5 表达式求值：表达式求值： 任何一个表达式都是由任何一个表达式都是由操作数操作数(operand)、运算符、运算符(operator)和界限符和界限符(delimiter)组成，其中，操作数可组成，其中，操作数可以是常数也可以是被说明为变量或常量的标识符；运算以是常数也可以是被说明为变量或常量

28、的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符等三符可以分为算术运算符、关系运算符和逻辑运算符等三类；基本界限符有左右括弧和表达式结束符等。为了叙类；基本界限符有左右括弧和表达式结束符等。为了叙述简洁，在此仅限于讨论只含二元运算符的算术表达式。述简洁，在此仅限于讨论只含二元运算符的算术表达式。可将这种表达式定义为：可将这种表达式定义为： 表达式表达式 = 操作数操作数 运算符运算符 操作数操作数 操作数操作数 = 简单变量简单变量 | 表达式表达式简单变量简单变量= 标识符标识符 | 无符号整数无符号整数算术运算的规则算术运算的规则是：是：先乘除后加减、先左后右和先括弧内先乘除后加

29、减、先左后右和先括弧内后括弧外后括弧外。则对表达式进行运算不能按其中运算符出现的。则对表达式进行运算不能按其中运算符出现的先后次序进行先后次序进行 第第2828页页在计算机中，对二元表达式可以有三种不同的标识方法。在计算机中，对二元表达式可以有三种不同的标识方法。假设假设 Exp = S1 + OP + S2则称则称 OP + S1 + S2 为表达式的前缀表示法（简称前缀式）为表达式的前缀表示法（简称前缀式）称称 S1 + OP + S2 为表达式的中缀表示法（简称中缀式）为表达式的中缀表示法（简称中缀式）称称 S1 + S2 + OP 为表达式的后缀表示法（简称后缀式）为表达式的后缀表示法

30、（简称后缀式） 例如：例如：若若 则它的则它的前缀式为：前缀式为： 中缀式为：中缀式为： 后缀式为：后缀式为： 后缀式：运算符放在运算数后面，运算符可没有优先级，后缀式：运算符放在运算数后面，运算符可没有优先级，式中没有括号，这种表达式叫后缀表达式，这是波兰的卢式中没有括号，这种表达式叫后缀表达式，这是波兰的卢卡。谢维奇提出的，因此这种式子又称为逆波兰式。卡。谢维奇提出的，因此这种式子又称为逆波兰式。第第2929页页1三式中的三式中的 “操作数之间的相对次序相同操作数之间的相对次序相同”；2三式中的三式中的 “运算符之间的的相对次序不同运算符之间的的相对次序不同”；3/中缀式丢失了括弧信息，致

31、使运算的次序不确定中缀式丢失了括弧信息，致使运算的次序不确定；4前缀式的运算规则为：前缀式的运算规则为：连续出现的两个操作数和在它们之连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式前且紧靠它们的运算符构成一个最小表达式；5后缀式的运算规则为：后缀式的运算规则为：运算符在式中出现的顺序恰为表达式的运算顺序；运算符在式中出现的顺序恰为表达式的运算顺序；每个运算符和在它之前出现且紧靠它的两个操作数构成每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式；一个最小表达式；方法：把每个运算符移到相应运算数后，再根据运算次序排列，方法：把每个运算符移到相应运算数后，再根据运

32、算次序排列，删除所有括号。删除所有括号。如：如：2*（5-3）/7+4 253-*7/4+写出下列中缀式的后缀式：写出下列中缀式的后缀式： 4+2*3-10/5 16-9*(4+3) 2*(x+y)/(1-x) 2*(x+y)-(1-x)423*+10 5/-16 943+*- 2xy+*1x-/2xy+1x-*第第3030页页以下就分以下就分如何按后缀式进行运算如何按后缀式进行运算和和如何将原表达式如何将原表达式转换成后缀式转换成后缀式两个问题进行讨论。两个问题进行讨论。 如何按后缀式进行运算？如何按后缀式进行运算？可以用两句话来归纳它的求值规则：先找运算符，后找操作数。 运算过程为：对后缀

33、式从左向右扫描，遇见操作数则暂时保存，遇见运算符即可进行运算；此时参加运算的两个操作数应该是在它之前刚刚碰到的两个操作数，并且先出现的是第一操作数，后出现的是第二操作数。由此可见，在运算过程中保存操作数的结构应该是个栈。 第第3131页页OperandType Cal(OperandType a) InitStack(s); i=1 ;while (ai) if (ai in opnd)Push(s,ai); elsePop(s,b);Pop(s,a); Push(s,Operate(a,ai,b) ; i=i+1; /while return GetTop(s);/program第第3232

34、页页如何由原表达式转换成后缀式？如何由原表达式转换成后缀式？ 我们先引进一个运算符的我们先引进一个运算符的优先数优先数的概念。给每个运算符的概念。给每个运算符赋以一个优先数的值，如下所列：赋以一个优先数的值，如下所列： 运算符：运算符： （ / 优先数：优先数：1 0 1 1 2 3 对原表达式中出现的每一个运算符是否即刻进对原表达式中出现的每一个运算符是否即刻进行运算取决于在它后面出现的运算符，如果它的优行运算取决于在它后面出现的运算符，如果它的优先数先数高或等于高或等于后面的运算，则它的运算先进行，后面的运算，则它的运算先进行，否则就得等待在它之后出现的所有优先数高于它的否则就得等待在它之

35、后出现的所有优先数高于它的运算运算都完成之后再进行。都完成之后再进行。显然，保存运算符的结构应该是个栈，从栈底到栈显然，保存运算符的结构应该是个栈，从栈底到栈顶的运算符的优先数是从低到高的，因此它们运算顶的运算符的优先数是从低到高的，因此它们运算的先后应是从栈顶到栈底的。的先后应是从栈顶到栈底的。第第3333页页从原表达式求得后缀式的规则为从原表达式求得后缀式的规则为： 1) 设立运算符栈；设立运算符栈；2) 设表达式的结束符为设表达式的结束符为#，预设运算符栈的栈底为，预设运算符栈的栈底为#；3) 若当前字符是操作数，则直接发送给后缀式；若当前字符是操作数，则直接发送给后缀式；4) 若当前字

36、符为运算符且优先数大于栈顶运算符，则进栈，若当前字符为运算符且优先数大于栈顶运算符，则进栈，否则退出栈顶运算符发送给后缀式；否则退出栈顶运算符发送给后缀式；5) 若当前字符是结束符，则自栈顶至栈底依次将栈中所有若当前字符是结束符，则自栈顶至栈底依次将栈中所有运算符发送给后缀式；运算符发送给后缀式；6) (对它之前后的运算符起隔离作用，则若当前运算符为对它之前后的运算符起隔离作用，则若当前运算符为(时进栈；时进栈；7) )可视为自相应左括弧开始的表达式的结束符，则从栈可视为自相应左括弧开始的表达式的结束符，则从栈顶起，依次退出栈顶运算符发送给后缀式直至栈顶字符为顶起，依次退出栈顶运算符发送给后缀

37、式直至栈顶字符为(止。止。 第第3434页页算符优先算法：利用运算优先关系的规定来实算符优先算法：利用运算优先关系的规定来实 现对表达式的编译或解释执行。现对表达式的编译或解释执行。 表达式的组成：操作数表达式的组成：操作数+算符（操作符算符（操作符+界限符）界限符）算符优先关系算符优先关系 +_*/()#+_*/(#= 将后缀式转换和求值合并到一起，有将后缀式转换和求值合并到一起，有第第3535页页算符优先算法的实现算符优先算法的实现1）置操作数栈为空栈，表达式起始符为运算符栈）置操作数栈为空栈，表达式起始符为运算符栈的栈底。的栈底。2）依次读入表达式的元素，）依次读入表达式的元素，a. 若

38、是操作数若是操作数,则进操作数栈。则进操作数栈。b. 若是运算符则同运算符栈栈顶栈元素进行优先若是运算符则同运算符栈栈顶栈元素进行优先级比较，级比较，b.1 若栈顶元素优先级高，则弹出该运算符，若栈顶元素优先级高，则弹出该运算符，取其操作数进行相应运算，之后结果进操作数栈，再取其操作数进行相应运算，之后结果进操作数栈，再将此算符和算符新的栈顶元素比较。将此算符和算符新的栈顶元素比较。 b.2 否则，将此运算符压栈。否则，将此运算符压栈。 b.3否则，则是一对括号，要脱括号否则，则是一对括号，要脱括号第第3636页页OperandType EvaluateExpression() InitSta

39、ck(OPTR);Push(OPTR,#); InitStack(OPND);c=getchar(); while (c!=# | GetTop(OPTR) !=#) if (!In(c,OP) Push(OPND,C);c=getchar(); else switch(Precede(GetTop(OPTR),c) case :Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b) ;break; /switch /while return GetTop(OPND);/program 第第3737页页步骤OP

40、TR栈OPND栈输入字符主要操作1 3*(7-2)#PUSH(OPND,3)23 *(7-2)#PUSH(OPTR,*)3*3 (7-2)#PUSH(OPTR,()4*(3 7-2)#PUSH(OPND,7)5*(-37 -2)#PUSH(OPTR,-)6*(-37 2)#PUSH(OPND,2)7*(372 )#Operate(7,-,2)8*(35 )#POP(OPTR)去括号9*35 # operate(3,#,5)1015 #RETURN(GETTOP(OPND) 第第3838页页3.3、递归函数的实现、递归函数的实现 在程序设计中，经常会碰到多个函数的嵌套调用。和汇编程序设计在程序设

41、计中，经常会碰到多个函数的嵌套调用。和汇编程序设计中主程序和子程序之间的链接和信息交换相类似，在高级语言编制的程中主程序和子程序之间的链接和信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的链接和信息交换也是由编译程序通序中，调用函数和被调用函数之间的链接和信息交换也是由编译程序通过栈来实施的。过栈来实施的。 当一个函数在运行期间调用另一个函数时，在运行该当一个函数在运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事：被调用函数之前，需先完成三件事： 1) 将所有的实在参数、返回地址等信息传递给被调用函数保存；将所有的实在参数、返回地址等信息传递给被调用函数保存；

42、2) 为被调用函数的局部变量分配存储区；为被调用函数的局部变量分配存储区；3) 将控制转移到被调用函数的入口。将控制转移到被调用函数的入口。而从被调用函数返回调用函数之前，应该完成：而从被调用函数返回调用函数之前，应该完成：1) 保存被调函数的计算结果；保存被调函数的计算结果；2) 释放被调函数的数据区；释放被调函数的数据区；3) 依照被调函数保存的返回地址将控制转移到调用函数。依照被调函数保存的返回地址将控制转移到调用函数。第第3939页页 当多个函数嵌套调用时，由于函数的运行规则是：当多个函数嵌套调用时，由于函数的运行规则是：后后调用先返回调用先返回，因此各函数占有的存储管理应实行，因此各

43、函数占有的存储管理应实行栈式管栈式管理理。 假设主函数调用函数假设主函数调用函数A，函数，函数A又调用函数又调用函数B，显然，显然，在函数在函数B运行期间主函数和函数运行期间主函数和函数A占用的存储都不能被占用的存储都不能被覆盖，反之，当函数覆盖，反之，当函数B运行结束，它所占用的存储区便运行结束，它所占用的存储区便可释放，同时因为程序控制转移到函数可释放，同时因为程序控制转移到函数A，当前程序访，当前程序访问的数据自然就是函数问的数据自然就是函数A占用的存储区了占用的存储区了 第第4040页页递归程序的执行例：例：1 void ditui(int n)2 if(n1)3 printf(n);

44、4 ditui(n-1); 5 /if6 /ditui1234561234Ditui(4)Ditui(5)1234Ditui(3)1234Ditui(2)1256Ditui(1)565656输出2输出3输出4输出5第第4141页页1 void ditui2(int n)2 if(n1)3 ditui(n-1); 4 printf(n);5 /if6 /ditui21234561234Ditui(4)Ditui(5)1234Ditui(3)1234Ditui(2)1256Ditui(1)565656输出2输出3输出4输出5第第4242页页递归函数的实现递归函数的实现 一个递归函数的运行过程类似于

45、多个函数的嵌套调一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于用，差别仅在于调用函数和被调用函数是同一个函数调用函数和被调用函数是同一个函数。为了保证为了保证每一层的递归调用每一层的递归调用都是对都是对本层本层的数据进行的数据进行操作，在执行递归函数的过程中需要一个操作，在执行递归函数的过程中需要一个递归工作栈递归工作栈。它的它的作用作用是是:1、将递归调用时的实在参数和函数返回地址传递给下将递归调用时的实在参数和函数返回地址传递给下一层执行的递归函数一层执行的递归函数；2、保存本层的参数和局部变量，以便从下一层返回时保存本层的参数和局部变量，以便从下一层返回时重新使用它们。重新使

46、用它们。 递归执行过程中所占用的数据区，称之为递归执行过程中所占用的数据区，称之为递归工作栈递归工作栈。每一层的递归参数等数据合成一个记录，称之为每一层的递归参数等数据合成一个记录，称之为递归工作记录递归工作记录。栈顶记录指示当前层的执行情况，称之为栈顶记录指示当前层的执行情况，称之为当前活动记录当前活动记录。递归工作栈的栈顶指针，称之为递归工作栈的栈顶指针，称之为当前环境指针当前环境指针。第第4343页页 在此，称调用递归函数的主函数为在此，称调用递归函数的主函数为第第0层层，则从主，则从主函数调用递归函数被称为进入递归函数的函数调用递归函数被称为进入递归函数的 第第1层层 ，从递，从递归函

47、数的归函数的第第i层层递归调用本函数被称为进入递归函数的递归调用本函数被称为进入递归函数的第第 i+1 层层。显然，当递归函数执行到第。显然，当递归函数执行到第 i 层时，从第层时，从第1层层到第到第 i-1 层的数据都必须被保存下来，以便一层一层退回层的数据都必须被保存下来，以便一层一层退回时继续使用。递归函数执行过程中每一层所占用的内存数时继续使用。递归函数执行过程中每一层所占用的内存数据区合起来就是一个据区合起来就是一个 递归工作栈递归工作栈。 下面用汉诺塔问题来说明递归程序和堆栈的使用下面用汉诺塔问题来说明递归程序和堆栈的使用设主程序中有如下的调用语句：设主程序中有如下的调用语句：in

48、t i; .10 hanoi(3,a,b,c);void hanoi (int n, char x, char y, char z);第第4444页页void hanoi (int n, char x, char y, char z)/ 将塔座将塔座 x 上按直径由小到大且至上而下编号为上按直径由小到大且至上而下编号为1至至 n/ 的的 n 个圆盘按规则搬到塔座个圆盘按规则搬到塔座 z 上，上，y 可用作辅助塔座。可用作辅助塔座。1 2if (n=1)3 move(x, 1, z); / 将编号为1的圆盘从 x 移到 z 4else 5hanoi(n-1, x, z, y); / 将 x 上编

49、号为1至 n-1 的圆盘移到 y,z 作辅助塔6move(x, n, z); / 将编号为 n 的圆盘从 x 移到 z7 hanoi(n-1, y, x, z); / 将 y 上编号为1至 n-1 的圆盘移到 z,x 作辅助塔 第第4545页页(3,a,b,c)(2,a,b,c)(1,a,b,c)ab(1,c,a,b)a c(1,b,c,a)(2,b,a,c)bc (1,a,b,c)第第4646页页v队列的定义队列的定义：一种运算受限的线性表。它只允许在表的一：一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为端进行插入，而在另一端进行删除。允许删除的一端

50、称为队队头头(front)，允许插入的一端称为，允许插入的一端称为队尾队尾(rear)。v例如：排队购物。操作系统中的作业排队。先进入队列的例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作成员总是先离开队列。因此队列亦称作先进先出先进先出(First In First Out)的线性表，简称的线性表，简称FIFO表。表。v 当队列中没有元素时称为空队列。在空队列中依次加入当队列中没有元素时称为空队列。在空队列中依次加入元素元素a1,a2,an之后，之后，a1是队头元素，是队头元素，an是队尾元素。显是队尾元素。显然退出队列的次序也只能是然退出队列的次序也只能

51、是a1,a2,an ，也就是说队列的，也就是说队列的修改是依先进先出的原则进行的。修改是依先进先出的原则进行的。 3.4 队列队列3.4 .1抽象数据类型队列的定义抽象数据类型队列的定义出队出队入队入队队头队头队尾队尾a1, a2, an第第4747页页队列的抽象数据类型定义：队列的抽象数据类型定义：ADT Queue 数据对象：数据对象：D= ai|aiElemSet,i=1,2,.n, n=0 数据关系：数据关系：R1=| a i-1,ai D,I=2,n 基本操作：基本操作：InitQueue(&Q);DestoryQueue(&Q);ClearQueue(&Q);QueueEmpty(

52、Q);QueueLength(Q);GetHead(Q,&e);EnQueue(&Q,e);DeQueue(&Q,&e);QueueTraverse(Q,visit() 第第4848页页3.4.2队列的存储表示和操作的实现队列的存储表示和操作的实现 链队列链队列 链队列是队列的链式存储结构，其结构示意图如下所示：链队列是队列的链式存储结构，其结构示意图如下所示：仅有单链表的头指针不便于在表尾做插入操作，为此再增仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针队列由一个头指针Q.

53、front和一个尾指针和一个尾指针Q.rear共同确定。共同确定。Q.front=Q.rear时，为空链队列时，为空链队列第第4949页页typedef SLink QueuePtr; / 链队列的结点结构和单链表相同 typedef struct QueuePtr front;/ 队列的头指针QueuePtr rear; / 队列的尾指针int length; / 队列元素个数 Queue; / 链队列/ 基本操作接口（函数声明）基本操作接口（函数声明） void InitQueue (Queue &Q); /构造一个空队列 Q void DestroyQueue (Queue &Q); /

54、销毁队列Q，Q 不再存在void ClearQueue (Queue &Q); /将 Q 置为空队列bool QueueEmpty (Queue Q); /若队列 Q 为空队列，则返回TRUE，否则返回FALSE int QueueLength (Queue Q); /返回队列 Q 中元素个数，即队列的长度 bool GetHead (Queue Q, ElemType &e); /若队列不空，则用 e 返回Q的队列头元素，并返回TRUE；否则返回FALSE void EnQueue (Queue &Q, ElemType e);/在当前队列的尾元素之后插入元素 e 为新的队列尾元素 bool

55、 DeQueue (Queue &Q, ElemType &e); /若队列不空，则删除当前队列Q中的头元素，用 e 返回其值，并返回TRUE；/否则返回 FALSEvoid QueueTraverse(Queue Q, void (*visit(ElemType )/依次对Q的每个元素调用函数visit( )，一旦visit( )失败，则操作失败。 链队列的类型定义：链队列的类型定义：第第5050页页void InitQueue (Queue &Q) / 构造一个空队列构造一个空队列 Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if (!

56、Q.front) exit(1);/ 存储分配失败存储分配失败Q.front-next=NULL; Q.length=0;void EnQueue(Queue &Q,ElemType e) / 在当前队列的尾元素之后，插入元素在当前队列的尾元素之后，插入元素 e 为新的队列尾元素为新的队列尾元素s =(QueuePtr)malloc(sizeof(QNode); if (!s) exit(1);/ 存储分配失败存储分配失败 s-data=e; s-next = NULL;Q.rear-next=s;/ 修改尾结点的指针修改尾结点的指针Q.rear=s; / 移动队尾指针移动队尾指针+Q.len

57、gth; / 队列长度增队列长度增1第第5151页页bool DeQueue(Queue &Q, ElemType &e) / 若队列不空，则删除当前队列若队列不空，则删除当前队列 Q 中的头元素，用中的头元素，用 e 返回其值，返回其值，/ 并返回并返回 TRUE；否则返回；否则返回 FALSE if ( Q.front = Q.rear ) / 链队列中只有一个头结点链队列中只有一个头结点return FALSE; p = Q.front-next; e = p-data;/ 返回被删元素返回被删元素Q.front-next=p-next; / 修改头结点指针修改头结点指针if(Q.rea

58、r = p) Q.rear = Q.front;delete p;/ 释放被删结点释放被删结点 - Q.length;return TRUE; / DeQueue它是否多余？能否删去？它是否多余？能否删去？ 由于一般情况下，出队列的操作只涉及队头元素，因此不需要修改队由于一般情况下，出队列的操作只涉及队头元素，因此不需要修改队尾指针，但当链队列中只有一个数据元素时，队头元素恰好也是队尾尾指针，但当链队列中只有一个数据元素时，队头元素恰好也是队尾元素，当它被删除之后，队尾指针就元素，当它被删除之后，队尾指针就悬空悬空了，待下次再做入队操作了，待下次再做入队操作时，就要产生指针的时，就要产生指针的

59、悬空访问悬空访问的错误，因此在这种情况下必须同时的错误，因此在这种情况下必须同时修改尾指针。修改尾指针。 第第5252页页和顺序栈相类似，在利用顺序分配存储结构实现队列和顺序栈相类似，在利用顺序分配存储结构实现队列时，除了用一维数组描述队列中数据元素的存储区时，除了用一维数组描述队列中数据元素的存储区域之外，尚需设立两个指针域之外，尚需设立两个指针 front 和和 rear 分别指示分别指示“队头队头”和和“队尾队尾”的位置。为了叙述方便，在此的位置。为了叙述方便，在此约定：约定：初始化建空队列时，令初始化建空队列时，令 front=rear=0，每当，每当插入一个新的队尾元素后，尾指针插入

60、一个新的队尾元素后，尾指针 front 增增1；每当；每当删除一个队头元素之后，头指针增删除一个队头元素之后，头指针增1。因此，在非因此，在非空队列中，头指针始终指向队头元素，而尾指针指空队列中，头指针始终指向队头元素，而尾指针指向队尾元素的向队尾元素的下一个下一个位置。如下图所示。位置。如下图所示。3.4.3循环队列循环队列 第第5353页页v非循环队列：非循环队列： 如何判断空队如何判断空队?v 如何判断满队如何判断满队?由于队首的移动特征，实际采用循环队列。由于队首的移动特征，实际采用循环队列。rearfront空队空队front非空非非空非满队满队1rearABCC满队满队DECfro