964-栈与队列.ppt
《964-栈与队列.ppt》由会员分享,可在线阅读,更多相关《964-栈与队列.ppt(113页珍藏版)》请在三一文库上搜索。
1、1,4.1 栈 4.2 栈的实现 4.3 栈的应用 4.4 队列 4.5 队列的实现 4.6 队列的应用,栈和队列是运算 受限的线性表。,第四章 栈与队列,2,3.1 栈,3.1.1 栈的概念及运算 3.1.2 顺序栈 3.1.3 链栈,3,3.1.1 栈的概念及运算,栈,限制仅在一端进行 插入和删除运算的线性 表,栈顶,进行插入、删除的 一端,栈底,栈顶,栈底,进栈,退栈,a2,a1,an,.,栈是后进先出表( LIFO 表),4,(1)置空栈 createEmptyStack(void):空栈; (2)判栈空 isEmptytack(st):这是一个布尔函数。 若st为空栈,则函数值为“真
2、”, 否则为“假”。 (3)进栈 push(st,x):在st的顶部插入(亦称压入) 元素 x。 (4)退栈 pop(st):删除(亦称弹出)栈st的顶部元素。 (5)取栈顶 top(st):取栈st的顶部元素。,栈的五种基本运算,3.1.1 栈的概念及运算,5,3.1.2 顺序栈,栈的顺序存储结构简称为顺序栈,它是运算受限 的顺序表。,#define MAXNUM 100 /* 栈中能达到的最大容量*/ typedef int DataType; /* 定义栈元素的数据类型* / struct SeqStack /* 顺序栈类型定义 */ DataType sMAXNUM; int t; /
3、*栈顶*/ ; typedef struct SeqStack, *PSeqStack; PSeqStack pastack; /*指向顺序栈的指针变量*/,6,注意:,t是 int型简单变量 ,指向栈顶元素在栈中的位置(序号),约定:,1、栈空时,t=-1 2、栈满时,t=MAXNUM-1 3、栈顶元素:St 4、若t=-1时,执行pop,产生“下溢” 5、若t=MAXNUM-1时,执行push,产生“上溢”,7,6 5 4 3 2 1 0 -1,A,B,C,D,进栈和退栈,3.1.2 顺序栈,8,3.1.2 顺序栈,(1)置空栈 (2)判栈空 (3)进栈 (4)退栈 (5)取栈顶,在顺序栈
4、下实现栈的五种基本运算,当程序中同时使用两个栈时, 可共享存储空间。,9,1. 置空栈(算法4.1),PSeqStack createEmptyStack_seq(void) PSeqStack pastack; pastack=malloc(sizeof(struct SeqStack); if(pastack=NULL) printf(“out of space!n”); else pastack-t= -1; return pastack; /*SETNULL*/,10,2. 判栈空(算法4.2),int isEmptyStack_seq(pastack) PSeqStack pasta
5、ck; if (pastack-t=0) return FALSE; else return TRUE; ,11,3. 进栈(算法4.3),先修改 t 值,再放入数据,t+,st=x,(*pastack).t+,(*pastack).s(*pastack).t=x,push_seq(pastack,x),12,push_seq(pastack,x) PSeqStack pastack; datatype x; if (pastack-t=MAXNUM-1) print(“overflow”); else pastack-t+; pastack-spastack-t=x; /* push_seq
6、 */,3. 进栈(算法4.3),13,4. 退栈(算法4.4),pop_seq(pastack),修改 t 值,t-,pastack-t - -,14,pop_seq(pastack) PSeqStack pastack; if (pastack-t=-1 ) print(“underflow”); else pastack-t-; /* pop_seq */,4. 退栈(算法4.4),15,5. 取栈顶元素(算法4.5),datatype top_seq(pastack) PSeqStack pastack; if (pastack-t=-1 ) print(“stack is empty
7、”); return NULL; else return(pastack-spastack-t; /* top_seq */,16,多个栈共享存储空间, .,栈1,栈2,栈1底,栈1顶,栈2底,栈2顶,让多个栈共享存储空间,可以相互调节余缺, 节约存储空间,降低发生上溢的概率。,17,多个栈共享存储空间,多栈共享:采用链栈,Typedef struct datatype sMAXNUM; int top1,top2; DStack; Push(x,i) Pop(i),18,3.1.3 链栈,栈的链式存储结构称为链栈。它是运算受限的 单链表。,由于只能在链表头部进行操作,故链栈没有必 要象单链表
8、那样需附加头结点。栈顶指针top就是 链表的头指针head。,19,typedef int DataType; struct Node; typedef struct Node *pNode; struct Node /* 单链表结点结构 */ DataType info; pNode link; ; struct LinkStack /* 链接栈类型定义 */ pNode top; /* 指向栈顶结点 */ ; typedef struct LinkStack *PLinkStack;,3.1.3 链栈,pLinkstack plstack; /*变量声明*/,plstack,top,inf
9、o,link,栈的链接表示,21,3.1.3 链栈,相当于链表在 top 结点前插入,出栈,相当于链表在将top 结点删除,进栈,22,void push_link( PLinkStack plstack, DataType x ) /* 在栈中压入一元素x */ PNode p; p = (PNode)malloc( sizeof( struct Node ) ); if ( p = NULL ) printf(“Out of space!n“); else p-info = x; p-link = plstack-top; plstack-top = p; ,进栈算法(算法4.8),23,
10、void pop_link( PLinkStack plstack ) PNode p; if( isEmptyStack_link( plstack ) ) printf( “Empty stack pop.n“ ); else p = plstack-top; plstack-top = plstack-top-link; free(p); ,退栈算法(算法4.9),24,3.2 栈的应用,栈的应用非常之广,只要问题满足LIFO 原则, 均可使用栈做数据结构。我们先看几个例子。 例3.1 文字编辑器 例3.2 栈与递归 例3.3 数制转换 例3.4 括号匹配的检验 例3.5 表达式求值,2
11、5,例3.1 设计一个简单的文字编辑器,使其具有删除打 错字符的功能。,# 删除前面一个字符 删除前面所有字符 * 输入结束,“abc#defg*”,我们用栈来实现这种功能的文字编辑器,每读入一个字符,退栈,置空栈,编辑结束,26,PSeqStack str; /*顺序栈 str 是全程变量*/ EDIT( ) /*编辑好的字符串在 str 中*/ char c; str=createEmptyStack(); c=getchar( ); while(c!=*) /*字符*为编辑结束符*/ if (c=#) POP(str); else if (c=) str=createEmptyStack
12、(); else PUSH(str,c); c=getchar( ); /*EDIT*/,例3.1 设计一个简单的文字编辑器,使其具有删除打 错字符的功能。,27,如果一个对象部分的由自己组成,或者是按它自己定义的,则称为递归的。 一个递归定义必须一步比一步简单,最后是有终结的,决不能无限循环下去。在n阶乘的定义中,当n为0时定义为1,它不再用递归来定义,称为递归定义的出口,简称为递归出口。,例3.2 栈与递归,递归的定义,28,例3.2 栈与递归,递归函数的特点:在函数内部可以直接或间接地 调用函数自身。如阶乘函数:,阶乘的递归计算(算法4.11 ) int fact (int n) if
13、(n = = 0) return 1; else return(n*fact(n-1); ; r2 main( ) int n; scanf(“%dn”, r1,3,3,r1,2,r2,1,r2,0,r2,1,1,2,6,30,调用前: (1)为被调用函数的局部变量分配存储区; (活动记录, 数据区) (2)将所有的实参、返回地址传递给被调用函数; 实参和形参的结合,传值。 (3)将控制转移到被调用函数入口。 调用后返回: (1)保存被调用函数的计算结果; (2)释放被调用函数的存储区; (3)依照被调用函数保存的返回地址将控制转 移到调用函数。,递归函数到非递归函数的转换,函数嵌套调用时,按
14、照“后调用先返回”的原则进行。,int main() int m,n; . first(m,n); 1: ,int first(int s, int t) int i; second(i); 2: ,int second(int d) int x,y; 3: ,int main() int m,n; . int i; int x,y; 3: 2: 1: ,函数嵌套结构,算法4.12 阶乘的非递归计算 程序员自己管理一个栈,并模拟函数调用的执行过程。 int nfact(int n); int res; pSeqStack st; st=createEmptyStack-seq(); while
15、 (n0) while (!isEmptyStack-seq(st) ) push-seq(st,n); res=res*top-seq(st); n=n-1; pop-seq(st); res=1; free(st); return(res); ,阶乘递归算法: int fact (int n) if (n = = 0) return 1; else return(n*fact(n-1); ;,34,例3.3 数制转换,十进制数N和其它d进制数的转换基于下列 原理: N=( N div d ) x d + N mod d,N N div 8 mod 8,1348 168 4,168 21 0
16、,21 2 5,2 0 2,4,0,5,2,35,程序要求:对于输入的任意一个非负十进制整 数,打印输出与其等值的八进制数。,由于上述计算过程是从低位到高位顺序产生八 进制数的各个数位,而打印输出,一般来说应从高 位到低位进行,恰好与计算过程相反。,例3.3 数制转换,因此,若将计算过程中得到的八进制数的各位 顺序进栈,则按出栈序列打印输出的即为与输入对 应的八进制数。,36,PSeqStack str; void CONVERSION( ) str=createEmptyStack(); scanf(“%d”,X); while(X) PUSH(str,X%8); X=X/8; while(
17、!EMPTY(str) printf(“%d”,TOP(str); POP(str); /*CONVERSION*/,例3.3 数制转换,37,例3.3 数制转换,void CONVERSION(int X ) If (X/8!=0) conversion(X/8); Printf(“%d”,X%8);,用递归函数实现:,用递归编程时,不需要用户自行定义栈。 它是由编译程序加以设立和处理的。,38,例3.4 括号匹配的检验,假设表达式中允许三种括号:()、 和 , 其嵌套的顺序随意。,检验括号是否匹配的方法可用“期待的急迫程度” 这个概念来描述。,在算法中设置一个栈,每读入一个括号,若是右括
18、号,则或者使置于栈顶的最急迫的期待得以消解,或者 是不合法的情况;若是左括号,则作为一个新的更急迫 的期待压入栈中,自然使原有的在栈中的所有未消解的 期待的急迫性都降了一级。, ( ) 1 2 3 4 5 6 7 8,39,Judgement() /*判断表达式是否配对,表达式以#结束*/ PSeqStack sta; char ch,chpop; int valid; SETNULL( /*valid为FALSE表示括号配对失败*/,例3.4 括号匹配的检验,40,例3.4 括号匹配的检验,while(ch!=#) /*当读入字符为左括号时进栈*/ if (ch=()|(ch=)|(ch=)
19、 ) PUSH(,41,例3.4 括号匹配的检验,if (!(ch=)/*读入下一字符*/ /*while*/,42,if (POP( /*左括号多于右括号*/ if (valid) printf(“括号配对成功“); else printf(“括号配对不成功”); ,例3.4 括号匹配的检验,43,表达式求值是程序设计语言编译中的一个最基本 问题。它的实现是栈应用的一个典型例子。下面我们 介绍一种简单直观、广为使用的算法,通常称为“算 符优先法”。,例3.5 表达式求值,要把一个表达式翻译成正确求值的机器指令序列, 或者直接对表达式求值,首先要能够正确解释表达式。 算符优先法就是根据算符优先
20、关系的规定来实现对表达 式的编译或解释执行的。,44,任何一个表达式都是由操作数(operand)、运算 符(operator)和界限符组成的,我们称它们为单词。,我们仅讨论简单表达式的求值问题,这种表达式 只含加、减、乘、除、乘方、括号等运算。,例3.5 表达式求值,我们把运算符和界限符统称为算符。,45,对于两个相继出现的算符Q1和Q2,其优先关系:,例3.5 表达式求值,46,界限符 # 优先级别最低,设置两个工作栈:运算符栈OPTR 操作数栈OPND,算法的基本思想,1)首先置操作数栈为空栈,表达式起始符#为运算符 栈的栈底元素。,2)依次读入表达式中每个字符,若是操作数则进OPND
21、栈,若是运算符则和 OPTR 栈的栈顶运算符比较优先权 后作相应操作,直至整个表达式求值完毕。,例3.5 表达式求值,输入:,3,*,(,7,+,3,*,6,/,2,-,5,#,),操作数栈,运算符栈,3,#,*,(,7,+,3,*,6,18,/,2,9,16,-,5,11,33,48,例3.5 表达式求值,datatype evaluate() PSeqStack optr,opnd; char ch; SETNULL( ,49,else switch(Precede(TOP(,例3.5 表达式求值,50,例3.5 表达式求值,case 1: /* :退栈并将运算结果入栈*/ theta=P
22、OP( /*evalate*/,51,若进栈序列为3,5,7,9,进栈过程中可以出栈,则不可能的一个出栈次序是( )。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3,d,练习题,52,用一维数组设计栈,初态是栈空,top=0。现有输入序列是 a、b、c、d,经过 push、push、pop、push、pop、push操作后,输出序列是( ),栈顶指针是( ),b、c,2,练习题,53,对于下面的程序调用过程,请问入栈序列是 ( ),出栈次序是( )。,BCD,CBD,练习题,54,4.4 队列,队列的概念及运算(逻辑结构),55,队列,只允许在
23、表的一端进行插入,而在另一端 进行删除。,队头,允许删除的一端,队尾,允许插入的一端,队列的概念,出队,入队,队头,队尾,a1,a2,an,.,队列是先进先出表,56,队列的基本运算: 创建一个空队列 Queue createEmptyQueue ( void ) 判队列是否为空队列 int isEmptyQueue ( Queue qu ) 往队列中插入一个元素 void enQueue ( Queue qu, DataType x ) 从队列中删除一个元素 void deQueue ( Queue qu ) 求队列头部元素的值 DataType frontQueue ( Queue qu
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 964 队列
链接地址:https://www.31doc.com/p-3025891.html