数据结构：第3章栈和队列B

1、1、今晚交第、今晚交第2章作业章作业 习题集习题集2.8 2.10 2.21 2.22 2.34 2.352、实验安排、实验安排下周一晚下周一晚 18:5018:5021:3021:30上机地点：南一楼东上机地点：南一楼东205、208，中，中201、206机房机房第第1次上机次上机 下周一晚（下周一晚（18:5021:30）请各班负责人到机房办理机时卡；请各班负责人到机房办理机时卡；上机内容：上机内容：线性表的插入与删除线性表的插入与删除试用试用C语言编写一个语言编写一个算法，将一循算法，将一循环单链表就地逆置。环单链表就地逆置。运用数据结构知识自编一个运用数据结构知识自编一个软件，并撰写软

2、件，并撰写较为规范的文档较为规范的文档。微软、百度、腾微软、百度、腾讯等来招聘，都讯等来招聘，都出了此题！出了此题！至少至少20002000行代码量行代码量成绩计算：平时和考试比例为成绩计算：平时和考试比例为3 3：7 7作业作业10%10%（由助教批改作业）（由助教批改作业）上机实验上机实验10%10%（可以做可以做3 3次实验，也可以做一个课程设计次实验，也可以做一个课程设计）主动实践主动实践10%10%（特殊表现，如课堂提问（特殊表现，如课堂提问/ /练习、网上提问练习、网上提问/ /分享学习体会、参加种子杯编程分享学习体会、参加种子杯编程PKPK赛等）赛等）3.1 栈（栈（Stack）

3、 3.2 队列（队列（Queue） 第三章第三章 栈和队列栈和队列1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式第第3 3章作业章作业: : 设正整数设正整数a的前驱为的前驱为PRIOR(a)，后继为后继为NEXT(a)，用用递归递归算法计算算法计算a+b。 平常我们可以用循环来实现，但根据本题题意不能用循环，而平常我们可以用循环来实现，但根据本题题意不能用循环，而要用递归。要用递归。设计要点有二：递归算法的形式化描述；不能无限制递归，设

4、计要点有二：递归算法的形式化描述；不能无限制递归，一定要有终止条件。一定要有终止条件。 a ab ba+ba+bPRIOR(a)NEXT(b)（a a可视为一减计数器，前移过程中不断递减，而可视为一减计数器，前移过程中不断递减，而b b的后移则的后移则是不断加是不断加1 1的过程）的过程）清华考研题清华考研题解：解：首先要对加法算法进行恰当的描述。肯定不能用简单的加法首先要对加法算法进行恰当的描述。肯定不能用简单的加法语句，要考虑如何用给出的两个特定函数来实现语句，要考虑如何用给出的两个特定函数来实现a+ba+b？思路思路：若用数轴来描述：若用数轴来描述a+ba+b，是两条线段之和，也可以看作

5、是两条线段之和，也可以看作是是a a不断往不断往“0”0”移动，移动，b b不断往相反方向移动的过程。不断往相反方向移动的过程。 当当a a移到移到0 0时，时，b b指向的位置即为指向的位置即为a+ba+b。有冗余！有冗余！在递归开始之前判断一次足矣，速度会快很多。在递归开始之前判断一次足矣，速度会快很多。int add( int a , int b );if a= =0 return (b);else return( add(prior(a), next(b) );ifif（abab）abab讨论算法复杂度：讨论算法复杂度：若总以若总以a a为基准，那么当为基准，那么当a a很大而很大而b

6、 b很小时则很小时则速度会慢很多，应当用较小的数作为速度会慢很多，应当用较小的数作为a a（减减1 1计数器）才合理。计数器）才合理。应当增加语句，判断应当增加语句，判断ab?ab?但加在递归结构体内好不好？但加在递归结构体内好不好？int (int a, int b) return ( add(a, b) )上层再加一上层再加一个函数！个函数！编制递归算法要注意些什么？编制递归算法要注意些什么？递归进行是有条件的。一般常把判断语句加在递归语句以前。递归进行是有条件的。一般常把判断语句加在递归语句以前。递归的最底层应该有返回值，以供上层递归的调用。否则会递归的最底层应该有返回值，以供上层递归的

7、调用。否则会死循环。死循环。递归调用需要利用递归调用需要利用堆栈堆栈。参量的初始化应该在递归以前。参量的初始化应该在递归以前。每次调用要把本次调用的参数和局部变量保存在栈顶。每次调用要把本次调用的参数和局部变量保存在栈顶。每次从下一层调用返回到上一层调用时，从栈顶恢复本层调每次从下一层调用返回到上一层调用时，从栈顶恢复本层调用的参数和局部变量的值。用的参数和局部变量的值。顺序栈的存储表示顺序栈的存储表示（教材（教材P46)： #define STACK-INIT-SIZE 100 /存储空间初始分配量存储空间初始分配量 #define STACKINCREMENT 10 /存储空间分配增量存储

8、空间分配增量 typedef struct SElemType *base; /栈的基址即栈底指针栈的基址即栈底指针 SElemType *top; /栈顶指针栈顶指针 int stacksize; /当前分配的空间当前分配的空间 ;动态数组动态数组栈的抽象数据类型定义栈的抽象数据类型定义: :(教材教材P44-45）ADT Stack数据对象：数据对象：D=数据关系：数据关系：R=基本操作：基本操作： ADT Stack入栈、出栈、入栈、出栈、建栈初始化、建栈初始化、判断栈满或栈空、判断栈满或栈空、读栈顶元素值等。读栈顶元素值等。顺序栈的入栈操作顺序栈的入栈操作例如用堆栈存放（例如用堆栈存放

9、（A A，B B，C C，D D）AACBABAtop核心语句：核心语句：top=L; 顺序栈顺序栈入栈入栈函数函数PUSHPUSH（）（）status status Push(ElemTypePush(ElemType e) e) if(topM) if(topM)上溢上溢 else s else stop+top+=e;=e; Push (B);Push (C);Push (D);toptoptoptop低低地址地址LPush (A);高地址高地址MBCD顺序栈出栈操作顺序栈出栈操作例如从栈中取出例如从栈中取出 DCBAtoptopDCABDCBAtopDCBAtop低低地址地址L高地址高

10、地址MD核心语句：核心语句：Pop ( );顺序栈出栈函数顺序栈出栈函数POP()POP()status Pop( )status Pop( ) if(top=L) if(top=L) 下溢下溢 else e=selse e=s-top-top; ; return(e); return(e); Pop ( );Printf( Pop () );链栈的入栈操作和出栈操作链栈的入栈操作和出栈操作（教材省略，教师补充）(1) 链栈的构造方式链栈的构造方式以头指针为栈顶，以头指针为栈顶，在头指针处在头指针处插入或删除插入或删除.Node *st, *p;int m=sizeof(Node); 栈顶栈顶

11、栈底栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈链栈 a1 a2an-1 annextdata链栈中每个结点由两个域构成：链栈中每个结点由两个域构成：datadata域和域和nextnext域，其定义为：域，其定义为：typedef Struct SNode SElemType data; Struct SNode * next; Node;1)1) 链栈链栈不必设头结点不必设头结点，因为栈顶（表头）操作频繁；，因为栈顶（表头）操作频繁；2)2) 链栈一般链栈一般不会出现栈满不会出现栈满情况，除非没有空间导致情况，除非没有空间导致

12、mallocmalloc( )( )分配失败。分配失败。3)3) 链栈的入栈、出栈操作就是栈顶的插入与删除操作，链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成修改指针即可完成。4)4) 采用链栈存储方式的优点是，可使采用链栈存储方式的优点是，可使多个栈共享空间多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。链栈是栈的首选存储方式。几点说明几点说明:Push (SElemType e) p=(Node*)malloc(m); if(!p)上溢上溢else p-data=e; p-link=st;

13、st=p; Status Pop( ) if(st=NULL)下溢下溢elsee=st-data;p=st;st=st-link; free(p); return(e); 插入插入表头表头从表头从表头删除删除(2) 操作操作由此可以看出：一个链栈由其由此可以看出：一个链栈由其栈顶指针唯一指定。栈顶指针唯一指定。 设设指向栈顶元素，当指向栈顶元素，当=NULL=NULL时表示栈空时表示栈空例例1 1：汉诺（：汉诺（HanoiHanoi）塔）塔见教材见教材P55P55 设计思路：用栈实现递归调用设计思路：用栈实现递归调用例例2 2： 见教材见教材P52P52 设计思路：用栈暂存运算符设计思路：用栈

14、暂存运算符例例3： 数制转换（十转数制转换（十转N） 见教材见教材P48P48 设计思路：用栈暂存低位值设计思路：用栈暂存低位值例例4：括号匹配的检验：括号匹配的检验 见教材见教材P49P49 设计思路：用栈暂存左括号设计思路：用栈暂存左括号例例1 1 汉诺（汉诺（ HanoiHanoi）塔）塔传说在创世纪时，在一个叫传说在创世纪时，在一个叫BrahmaBrahma的寺庙里，有三个柱子，其中的寺庙里，有三个柱子，其中一柱上有一柱上有6464个盘子从小到大依次叠放，僧侣的工作是将这个盘子从小到大依次叠放，僧侣的工作是将这6464个盘个盘子从一根柱子移到另一个柱子上。子从一根柱子移到另一个柱子上。

15、分析：分析： 设三根柱子分别为设三根柱子分别为 x, y, z , 盘子在盘子在 x 柱上，要移到柱上，要移到 z 柱上。柱上。1、当、当 n=1 时，盘子直接从时，盘子直接从 x 柱移到柱移到 z 柱上；柱上；2、当、当 n1 时时, 则则: 设法将设法将 前前 n 1 个盘子个盘子 从从 x 移到移到 y 柱上柱上（借助（借助z z），则，则 盘子盘子 n 就能从就能从 x 移到移到 z 柱上；柱上； 再设法把再设法把n 1 个盘子个盘子 从从 y 移到移到 z 柱上柱上( (这又是一个与原来相同这又是一个与原来相同的问题，只是规模少了）的问题，只是规模少了） 。x y zx y znn

16、1移动时的规则：移动时的规则： v 每次只能移动一个盘子；每次只能移动一个盘子；v 只能小盘子在大盘子上面；只能小盘子在大盘子上面；v 可以使用任一柱子。可以使用任一柱子。当工作做完之后，就标志着世界末日到来。当工作做完之后，就标志着世界末日到来。四川科技馆展项梵天之塔四川科技馆展项梵天之塔原创：邓新荣原创：邓新荣( (2002级通信3班)改进：改进：万万珺珺之之(2005级通信6班)前几届同学曾画出前几届同学曾画出P57-58P57-58图图3.73.7所所示示HanoiHanoi塔的递归函数运行示意图塔的递归函数运行示意图递归运算！递归运算！Void Hanoi ( int n, char

17、 x, char y, char z ) /将将n n个编号从上到下为个编号从上到下为1 1n n的盘子从的盘子从x x柱，借助柱，借助y y柱移到柱移到z z柱柱 if ( n = = 1 ) move ( x , 1 , z ) ; /将编号为将编号为1 1的盘子从的盘子从x x柱移到柱移到z z柱柱 else Hanoi ( n-1 , x , z , y ) ;/;/先将先将n-1n-1个盘从个盘从x x柱借助柱借助z z柱移到柱移到y y柱柱 move ( x , n, z) ; /将编号为将编号为n n的盘子从的盘子从x x柱移到柱移到z z柱柱 Hanoi (/再将再将n-1n-

18、1个编号从上到下为个编号从上到下为1 1n-1n-1的盘的盘子从子从y y柱借助柱借助x x柱移到柱移到z z柱柱 /Hanoi/Hanoi程序设计如下：程序设计如下：FLASH:FLASH: 汤新宜汤新宜（20022002级通信级通信5 5班）班）例例2 编写算法，用栈实现表达式编写算法，用栈实现表达式求值。求值。一个算术表达式是由一个算术表达式是由操作数操作数（x，y，z）和）和算符算符（* ，/， + ，-，（，），（，），# ）组成。）组成。教材教材P53P53中表中表3.13.1给出了算符之间的优先级给出了算符之间的优先级表达式的表达式的起止符号起止符号(1) 表达式求值必须满足算术

19、四则运算规则：表达式求值必须满足算术四则运算规则： a. 从左算到右从左算到右 b. 先乘除，后加减先乘除，后加减 c. 先括号内，后括号外先括号内，后括号外表达式求值表达式求值是是栈应用的典型栈应用的典型例子例子, , 见见P52P52为了实现算符优先算法，可以设定两个工作栈：为了实现算符优先算法，可以设定两个工作栈：存放运算符号，存放运算符号， 存放操作数或运算结果存放操作数或运算结果 。o operatorperator & & operandoperand 注：本例采用注：本例采用 “算符优先法算符优先法”。例例2的表达式输入计算机时：的表达式输入计算机时： 1）首先让

20、表达式的起始符）首先让表达式的起始符 为为运算符栈运算符栈的栈底元素，并置的栈底元素，并置为空栈为空栈 ；2）依次读入表达式中的每个字符）依次读入表达式中的每个字符 （# # 3 3* *（7 72 2）# #）若运算符是若运算符是# #且栈顶是且栈顶是# #，则结束计算，返回，则结束计算，返回栈顶值。栈顶值。 if（是操作数）（是操作数） 则则PUSH（ ，操作数）；，操作数）； if（是运算符）（是运算符） 则与则与栈顶元素进行比较，按优先级栈顶元素进行比较，按优先级( (详见详见P53P53表表3.13.1的规定）的规定）进行操作；进行操作；3）直到整个表达式求值完毕（当前读入的字符和）

21、直到整个表达式求值完毕（当前读入的字符和栈的栈顶栈的栈顶元素均为元素均为 ） if栈顶元素栈顶元素 运算符运算符则退栈则退栈, ,并按栈顶计算，将结果压入并按栈顶计算，将结果压入栈。栈。且未入栈的那个运算符要保留，继续与下一个栈顶元素比较！且未入栈的那个运算符要保留，继续与下一个栈顶元素比较！P54 表达式求值过程的描述：表达式求值过程的描述：OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#, *3(7-2)#Push(optr,()#, *, (37-2)#Push(opnd,7)#, *, (3, 7-2)#Push(optr,-)#, *, (, 3, 72)#Push(opnd,2)#, *, (, 3, 7, 2)#Operate(7-2)#, *, (3, 5)#Pop(optr)#, *3, 5#Operate(3*5)#15#GetTop(opnd)# 3 *（7 2 ）#程序见程序见P53P53Status EvaluateExpression( OperandType &result) InitStack(OPND); InitStack(OPTR);Push(OPTR ,#); =getchar(); while(c!=#)|(Get