《数据结构 教学课件 ppt 作者 晋良颖 3》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 晋良颖 3（47页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈和队列 31栈 栈的主要操作如下： （1）、建立一个空栈 （2）、进栈 （3）、出栈： ( 4 ) 、判断一个栈是否为空？ （5）、判断栈是否已满？ （6）、获得栈顶元素值,退出,图3-1,312栈的表示和操作的实现 1、顺序存储的栈 #define MAXSIZE 50 typedef struct elemtype elemMAXSIZE; int top; SQSTACK; （1）、建立一个空栈 void initstack(SQSTACK *s) (*s).top=-1; ( 2 ) 、判断一个栈是否为空 int stackempty(SQSTACK s) if (s.top
2、=-1) return 1; else return 0; ,( 3 )、让一个数据元素为e的结点进栈。 算法 3.1 如书第42页所示 ( 4 )、出栈一个结点并得到栈顶数据元素值 算法 3.2 如书第42页所示 （5）、获取栈顶元素值 void getelm(SQSTACK s, elemtype *e) if (s.top=-1) printf(“栈空n”); return; *e=s.elems.top; ,1、接存储的栈 (1)、建立一个空栈 NODEPTR top; top=NULL; (2)、让一个数据元素为e的结点进栈 算法 33 如书第43页所示,(3)、出栈一个结点并得到栈
3、顶数据元素值 算法 34 如书第43页所示,313栈的应用举例 1、子程序的调用和返回,图3-2,1、算术表达式求值 表31 算符的栈内、外优先级,例1 计算：2+3*222*5-2;,图3-3,例2 计算3*2(4+2*2-6)-5;,图34,算法 35 如书第47页所示,例2的算式的三种形式为： 中辍式：3*2（4+2*2-6）-5； 前辍式：-*32-+4*2 2 6 5； 后辍式：3 2 4 2 2*+6-*5-；,图3-5,把输入的中辍表达式化成后辍式的算法 算法 36 如书第49页所示,将算式“2+3*222*5-2;”化为拓辍式的过程：,图3-6,1、栈与递归 1 n=0|n=1
4、 n!= n*(n-1)! n=2 例如，我们要计算5！，按定义有： 5！=5*4！ =5*4*3！ =5*4*3*2！ =5*4*3*2*1！ =120,例3 Ackermann函数A（n,x,y）的计算 x+1 n=0 x n=1,y=0 0 n=2,y=0 A(n,x,y)= 1 n=3,y=0 2 n=4,y=0 A(n-1,A(n,x,y-1),x) n!=0,y!=0,A(3,1,2) =A(2,A(3,1,1),1) =A(2,A(2,A(3,1,0),1),1) =A(2,A(2,1,1),1) =A(2,A(1,A(2,1,0),1),1) =A(2,A(1,0,1),1)
5、=A(2,A(0,A(1,0,0),0),1) =A(2,A(0,0,0),1) =A(2,1,1) =A(1,A(2,1,0),1) =A(1,0,1) =A(0,A(1,0,0),0) =A(0,0,0),图3-7,计算Ackermann函数A(n,x,y)的算法思想可以描述如下： 反复执行： (1)、递归：只要有n!=0 若栈空则结束算法，否则 出栈一组值，作新参数(n,y)；v赋给x；构造出一个新函数A(n,x,y)，再递归。,定义递归出口，即n=0或y=0时的Ackermann函数如下 算法 37 如书第52页所示,定义栈中元素类型为一个结构类型： typedef struct in
6、t n; int x; elemtype; 算法 38 如书第53页所示,定义栈中元素类型为一个结构类型： typedef struct int n; int x; elemtype; 算法 39 如书第53页所示,另一种处理算法： 定义栈中元素类型为： typedef struct int n; int x; int y; elemtype ;,图3-8,算法 39 如书第53页所示,例4 迷宫问题,图3-9,定义栈中元素类型为： typdef struct int x; /*行下标*/ int y; /*列下标*/ int v; /*方向号*/ elemtype;,算法 310 如书第56
7、页所示,例5 n阶汉诺塔（Hanoi）问题 ( 1 )、每次只能移动一个圆盘； ( 2 )、圆盘可以插在x、y、z中任一塔座上； ( 3 )、任何时刻都不能将一个大盘压在小盘上。,图3-10,算法 311 如书第58页所示,图3-11,定义栈中元素类型为： typdef struct int n; /*盘子数目（返回时代表编号）*/ char x,y,z; /*起始针座、辅助针座和目标针座*/ elemtype; 算法 312 如书第59页所示,将n个盘子从x座移到z座的一项任务可以分为三项任务来完成： (1)、将n-1个盘子由x座移到y座； (2)、把第n号盘子从x座移到z座； (3)、将n
8、-1个盘子由y座移到z座。,图3-12,算法 313 如书第61页所示,3.2队列,图3-13 队的示意图,321队列定义和操作 队列的主要操作如下： （1）、建立一个空队列 （2）、进队 （3）、出队 （4）、判断一个队列是否为空？ （5）、判断队列是否已满？ （6）、获得队头元素值,322队列的表示和操作的实现 1、顺序存储的队列 循环队的定义： #define MAXSIZE 50 typedef struct elemtype elemMAXSIZE; int front,rear; /*队头、队尾指针*/ int len; /*队中实际元素个数*/ SQQUEUE;,图3-14,（1
9、）、建立一个空队 void initqueue(SQQUEUE *q) (*q).front=(*q).rear=-1; (*q).len=0; ( 2 )、判断一个队是否为空 int queueempty(SQQUEUE q) if (q.len=0) return 1; else return 0; ( 3 ) 、让一个数据元素为e的结点进队 算法3.14 如书第64页所示,(4)、出队一个结点并得到队头数据元素值 算法3.15 如书第64页所示 5）、获取队头元素值 void getfrontelm(SQQUEUE q, elemtype *e) if (q.len) *e=q.elem
10、q.front; else printf(“队空n”);,1、链接存储的队 定义链队的类型为： typedef struct NODEPTR front，rear； LINKQUEUE； （1）、建立一个空队 void initqueue(LINKQUEUE *q) (*q).front=(*q).rear=NULL; (2)、判断一个队是否为空 int queueempty(LINKQUEUE q) if (q.front=NULL) return 1; else return 0; ,(3)、让一个数据元素为e的结点进队 算法 3.16 如书第65页所示 (4)、出队一个结点并得到队头数据元素值 算法 3.17 如书第65页所示 （5）、获取队头元素值 void get_frontelm(LINKQUEUE q, elemtype *e) if (q.front) *e=q.front-data; else printf(“队空n”); ,323队列的应用举例,图3-15,算法 318 如书第67页所示,
