第三章 栈和队列27378_第1页
第三章 栈和队列27378_第2页
第三章 栈和队列27378_第3页
第三章 栈和队列27378_第4页
第三章 栈和队列27378_第5页
已阅读5页,还剩76页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、栈 队列 递归,第三章栈和队列,本章主要内容:,一、栈 ( Stack ),定义:是限定仅在表尾进行插入或删除操作的线性表。 允许插入和删除的一端 称为栈顶(top),另一端 称为栈底(bottom) 特点:后进先出 (LIFO),a1,top,bottom,an . . . .,进栈,出栈,抽象数据类型,1、栈的表示和实现,顺序栈:栈的顺序存储结构,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,指针top指示栈顶元素在顺序栈中的位置, base为栈底指针,指向栈底的位置。,base,(1).顺序栈存储结构:,#define STACK_INIT_SIZE 100; #define

2、 STACKINCREMENT 10; typedef char SElemType; typedef struct /顺序栈定义 SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize; /当前已分配的存储空间 SqStack;,判栈空 int StackEmpty (SqStack *S) if( S-top = S-base ) return 1 /判栈空,空则返回1 else return 0; /否则返回0 判栈满 int StackFull (SqStack *S) if( S-top- S-base = S- Stac

3、kSize ) return 1 /判栈满,满则返回1 else return 0; /否则返回0 ,(2)顺序栈的基本运算:,初始化 int InitStack ( SqStack ,入栈 int Push (SqStack S, SElemType x) /插入元素x为新的栈顶元素 if ( StackFull (S) ) S.base =( SElemType *)malloc(S.base , (S.stacksize+ STACKINCREMENT) * sizeof(SElemType); if(! S.base)return 0; S.top= S.base + S.stacks

4、ize; S.stacksize+= STACKINCREMENT; /追加存储空间 *(S.top)=x; S.top+; Return 1; ,取栈顶元素 int Gettop (SqStack S, SElemType ,出栈 int pop (SqStack ,链式栈:栈的链接表示,链式栈无栈满问题,空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作,top,2、链式栈 (LinkStack)的存储结构,typedef int SElemType; typedef struct node SElemType data; /结点 struct node *next;

5、 /链指针 StackNode; typedef struct StackNode *top; /栈顶指针 LinkStack;,链式栈操作实现,初始化 void InitStack ( LinkStack ,判栈空 int StackEmpty (LinkStack S) if(!S.top) return 1; else return 0; 出栈 int Pop ( LinkStack ,取栈顶 int GetTop ( LinkStack S, SElemType ,例 3-1 写一算法。满足下列要求:对于输入的任意一个非负十 进制整数,打印输出与其等值的八进制数。 void Conve

6、rsion ( ) / 对于输入的任意非负十进制整数,打印输出与其等值的八进制数 InitStack ( S ); / 构造空栈 scanf ( % d , / 打印输出 / while 结束 / Conversion,例 3-2 写一算法。满足下列要求:对于输入的任意括号串进行配对检测:若配对则返回“right”;若不配对则返回“error”。 Status Check ( ) InitStack ( S ); / 构造空栈 Push ( S, # ); / 表示括号串开始 ch = getchar ( ); / 读取括号串中的一个字符 bool = 1; / bool = 1 时检验正确;

7、bool = 0 时则检验出错 while ( ch ! = n / 如果 bool 为 0,则打印错误 / Check,3、栈的应用举例,一个表达式由操作数(亦称运算对象)、操作符 (亦称运算符) 和分界符组成。 算术表达式有三种表示: 中缀(infix)表示 ,如 A+B; 前缀(prefix)表示 ,如 +AB; 后缀(postfix)表示 ,如 AB+;,中缀表达式 a + b * ( c - d ) - e / f 后缀表达式 a b c d - * + e f / - 表达式中相邻两个操作符的计算次序为: 优先级高的先计算; 优先级相同的自左向右计算; 当使用括号时从最内层括号开始

8、计算。,表达式事例,应用中缀表示计算表达式的值,a + b * ( c - d ) - e / f 使用两个栈,操作符栈OPTR (operator),操作数栈OPND(operand) 为了实现这种计算,需要考虑各操作符的优先级,rst1,rst2,rst4,rst3,rst5,各个算术操作符的优先级,isp叫做栈内(in stack priority)优先数 icp叫做栈外(in coming priority)优先数。 操作符优先数相等的情况只出现在括号配对或栈底的“#”号与输入流最后的“#”号配对时。,中缀算术表达式求值,对中缀表达式求值的一般规则: (1) 建立并初始化OPTR栈和O

9、PND栈,然后在OPTR栈中压入一个“#” (2) 从头扫描中缀表达式,取一字符送入ch。 (3) 当ch != # 或OPTR栈的栈顶 != #时, 执行以下工作, 否则结束算法。此时在OPND栈的栈顶得到运算结果。, 若ch是操作数,进OPND栈,从中缀表达式取下一字符送入ch; 若ch是操作符,比较icp(ch)的优先级和isp(OPTR)的优先级: 若icp(ch) isp(OPTR),则ch进OPTR栈,从中缀表达式取下一字符送入ch; 若icp(ch) isp(OPTR),则从OPND栈退出a2和a1,从OPTR栈退出, 形成运算指令 (a1)(a2),结果进OPND栈; 若icp

10、(ch) = isp(OPTR) 且ch = ),则从OPTR栈退出(,对消括号,然后从中缀表达式取下一字符送入ch;,void EvaluateExpression ( ) SqStack OPTR, OPND; char c, op,a,b; InitStack ( OPTR ); InitStack ( OPND ); Push ( OPTR, # ); /两个栈初始化 getchar ( c ); /读入一个字符 op = # ; while ( c != # | op != # ) if ( isoperand ( c) ) /是操作数, 进栈 Push ( OPND, c); ge

11、tchar( c ); else /是操作符, 比较优先级 GetTop ( OPTR, op ); /读一个操作符,实现算法,switch(Precede(op,c) case : /退栈并将运算结果入栈 pop(OPTR,op); pop(OPND,b); pop(OPND,a); operate(a,op,b); break; return Gettop(OPND,c); 演示,二、队列,定义:只允许在表的一端进行插入,而在另一端删除元素的线性表。 在队列中,允许插入的一端叫队尾(rear) ,允许删除的一端称为对头(front)。 特点:先进先出 (FIFO),a1 ,a2, a3,a

12、n,出队列,入队列,队 头,队 尾,抽象数据类型,(一)链队列:队列的链式表示,链队列中,有两个分别指示队头和队尾的指针。 链式队列在进队时无队满问题,但有队空问题。,1、链式队列的实现 typedef int QElemType; typedef struct QNode QElemType data; /队列结点数据 struct QNode *next; /结点链指针 QNode,*QueuePtr; typedef struct QNode *rear, *front; LinkQueue;,2、链队列的主要操作,初始化 int InitQueue ( LinkQueue ,取队头元素

13、 int GetHead ( LinkQueue Q, QElemType ,入队 int EnQueue ( LinkQueue ,出队 int DeQueue ( LinkQueue Q, QElemType ,(二)、循环队列-队列的顺序表示和实现,顺序队列队列的顺序存储表示。用一组地址连续的存储单元依次存放从队列头到队列尾的元素,指针front和rear分别指示队头元素和队尾元素的下一个位置。 插入新的队尾元素,尾指针增1,rear = rear + 1, 删除队头元素,头指针增1, front = front + 1, 因此,在非空队列中,头指针始终指向队列头元素,而尾指针始终指向队

14、列尾元素的下一个位置。 队满时再进队将溢出 解决办法:将顺序队列臆造为一个环状的空间,形成循环(环形)队列,队列的进队和出队,front,rear,空队列,front,rear,A进队,A,front,rear,B进队,A B,front,rear,C, D进队,A B C D,front,rear,A退队,B C D,front,rear,B退队,C D,front,rear,E,F,G进队,C D E F G,C D E F G,front,rear,H进队,溢出,1、循环队列实现原理,队头、队尾指针加1,可用取模(余数)运算实现。 队头指针进1: front = (front+1) %m

15、axsize; 队尾指针进1: rear = (rear+1) % maxsize; 队列初始化:front = rear = 0; 队空条件:front = rear; 队满条件:(rear+1) % maxsize = front;,0,1,2,3,4,5,6,7,循环队列,front,rear,Maxsize-1,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,front,rear,B,C,D,rear,空队列,一般情况,C,0,1,2,3,4,5,6,7,队满,front,rear,D,E,F,G,A,B,A,C,front,0,1,2,3,4,5,6,7,front,

16、0,1,2,3,4,5,6,7,front,0,1,2,3,4,5,6,7,front,rear,A,A,B,C,rear,rear,空队列,A进队,B, C进队,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,A退队,B退队,0,1,2,3,4,5,6,7,D,E,F,G,H进队,front,B,C,rear,A,front,B,C,rear,front,C,rear,D,E,F,G,H,#define MAXSIZE 100 Typedef struct QElemType *base; int front; int rear; SqQueue,2、循环队列的类型定义,3、

17、循环队列操作的实现,初始化队列 int InitQueue ( SqQueue Q ) /构造空队列 Q.base=(QElemType *)malloc(MAXSIZE *sizeof(QElemType); If(! Q.data) return 0; Q.rear = Q.front = 0; Return 1 ,判队空 int QueueEmpty ( SqQueue Q ) if(Q.rear=Q.front) return 1; else reutrn 0; 判队满 int QueueFull ( SqQueue Q ) if(Q.rear+1) % MAXSIZE = Q.fro

18、nt) return 1; else return 0; ,入队 int EnQueue ( SqQueue Q, QElemType x ) if ( QueueFull (Q) ) return 0; Q.dataQ.rear = x; Q.rear = ( Q.rear+1) % MAXSIZE; return 1; ,出队 int DeQueue ( SqQueue Q, QElemType ,例 3-3假定用一个单循环链表来表示队列(也称为循环链式队列),该队列只设一个队尾指针,不设队头指针,试编写下列各种运算的算法: (1) 向循环链式队列插入一个元素值为 x 的结点。 (2) 从

19、循环链式队列中删除一个结点。 在进行插入和删除之前,首先应该构造一个带头结点的空循环链式队列,算法如下: Status InitQueue ( LinkQueue / InitQueue (1) 插入(即入队)算法。 Status Insert ( LinkQueue if ( ! p ) exit (OVERFLOW); / 为新结点分配存储空间失败 p-data = x; / 将 x 放入新结点的数据域 p-next = Q.rear-next; / 新结点指针域值为队尾指针域值 Q.rear-next = p; / 将新结点插入到队列 Q 的尾 Q.rear = p; / 修改队列 Q

20、的尾指针 return OK; / Insert (2) 删除(即出队)算法。 Status Delete ( LinkQueue / 如果队列空,则返回 ERROR,else / 如果队列非空,则进行删除 p = rear-next; / p 指向队列的头结点 x = p-next-data; / 将队列中第一个结点值取出放入 x q = p-next / q 指向队列第一个结点(队头指针) p-next = p-next-next; / 修改队头指针 / else 结束 free ( q ); / 释放队头元素所占空间 return OK; / Delete,三、递 归,定义 若一个对象部

21、分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的; 若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 三种递归情况 定义是递归的 数据结构是递归的 问题的解法是递归的,1、定义是递归的,求解阶乘函数的递归算法 long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1); ,例如,阶乘函数,求解阶乘 n! 的过程,主程序 main : fact(4),参数 4 计算 4*fact(3) 返回 24,参数 3 计算 3*fact(2) 返回 6,参数 2 计算 2*fa

22、ct(1) 返回 2,参数 1 计算 1*fact(0) 返回 1,参数 0 直接定值 = 1 返回 1,参数传递,结果返回,递归调用,回归求值,2、数据结构是递归的,有若干结点的单链表,例如,单链表结构,f,只有一个结点的单链表,例1.搜索链表最后一个结点并打印其数值 void Search ( ListNode *f ) if ( f -link = NULL ) printf (“%dn”, f -data ); else Search ( f -link ); ,f,f,f,f,f,a0,a1,a2,a3,a4,递归找链尾,例2.在链表中寻找等于给定值的结点,并打印其数值void Se

23、arch ( ListNode *f, ListData,f,f,f,f,递归找含x值的结点,x,例如,汉诺塔(Tower of Hanoi)问题的解法: 如果 n = 1,则将这一个盘子直接从 A 柱移到 C 柱上。否则,执行以下三步: 用 C 柱做过渡,将 A 柱上的 (n-1) 个盘子移到 B 柱上: 将 A 柱上最后一个盘子直接移到 C 柱上; 用 A 柱做过渡,将 B 柱上的 (n-1) 个盘子移到 C 柱上。,3、问题的解法是递归的,算法演示 #include #include strclass.h” void Hanoi (int n, char x , char y, char

24、 z) /解决汉诺塔问题的算法 if ( n = 1 ) /将编号为1的圆盘从x移到z move(x,1,z); else hanoi(n-1,x,z,y); /将编号为1到n-1的圆盘从x移到y,Z作辅助柱 move(x,n,z); /将编号为n的圆盘从x移到z hanoi(n-1,y,x,z); /将编号为1到n-1的圆盘从y移到z,x作辅助柱 ,不能无限制地调用本身,必须有一个出口,化简为非递归状况直接处理。,构成递归的条件,递归过程与递归工作栈,递归过程在实现时,需要自己调用自己。 层层向下递归,退出时的次序正好相反: 递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次

25、序 主程序第一次调用递归过程为外部调用; 递归过程每次递归调用自己为内部调用。,递归工作栈,每一次递归调用时,需要为过程中使用的参数、局部变量等另外分配存储空间。 每层递归调用需分配的空间形成递归工作记录,按后进先出的栈组织。,局部变量 返回地址 参 数,活动记录框架,递归 工作记录,函数递归时的活动记录,. ,Function() . ,调用块,函数块,返回地址(下一条指令) 局部变量 参数,long Factorial ( long n ) int temp; if ( n = 0 ) return 1; else temp = n * Factorial (n-1); RetLoc2 r

26、eturn temp; void main ( ) int n; n = Factorial (4); RetLoc1 ,计算Fact时活动记录的内容,递归调用序列,0 RetLoc2,1 RetLoc2,2 RetLoc2,3 RetLoc2,4 RetLoc1,参数 返回地址 返回时的指令,RetLoc1 return 4*6 /返回24,RetLoc2 return 3*2 /返回6,RetLoc2 return 1 /返回1,RetLoc2 return 1*1 /返回1,RetLoc2 return 2*1 /返回2,递归过程改为非递归过程,递归过程简洁、易编、易懂 递归过程效率低,

27、重复计算多 改为非递归过程的目的是提高效率 单向递归和尾递归可直接用迭代实现其非递归过程 其他情形必须借助栈实现非递归过程,计算斐波那契数列的函数Fib(n)的定义,求解斐波那契数列的递归算法 long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); ,如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5,斐波那契数列的递归调用树,Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(4),Fib(1),Fib(0),Fib(2)

28、,Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(5),Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),栈结点,n tag,tag = 1, 向左递归;tag = 2, 向右递归,Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),2 1 3 1 4 1,n=1 sum=0+1,2 2 3 1 4 1,n=2-2,3 1 4 1,n=0 sum=1+0,3 2 4 1,n=3-2,4 1,n=1 sum=1+1,4

29、 2,n=4-2,Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),2 1 4 2,n=1 sum=2+1,2 2 4 2,n=2-2,4 2,n=0 sum=3+0,long Fibnacci ( long n ) Stack S; Node *w; long sum = 0; /反复执行直到所有终端结点数据累加完 do while ( n 1 ) w-n = n; w-tag = 1; S.push ( w ); n-; /向左递归到底, 边走边进栈 sum = sum + n; /执行求和,while ( !S.IsEmpty( ) ) w = S.getTop( ); S.Pop( ); if ( w-tag = 1 ) /改为向右递归 w

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论