数据结构严蔚敏C语言版第三章课件.ppt

1、3.1.1 3.1.1 栈的定义及基本运算栈的定义及基本运算 3.1 3.1 栈栈( (Stack)Stack)假设栈假设栈S=(aS=(a1 1，a a2 2，a a3 3，a an n) )，则，则a a1 1称为栈底元素称为栈底元素，a an n为栈为栈顶元素顶元素。栈中元素按。栈中元素按a a1 1，a a2 2，a a3 3，a an n的次序进栈，退栈的的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为先出的原则进行的。因此，栈又称为后进先出后进先出 ( (LIFO)LIFO)表表。

2、栈是限制在表的一端进行插入和删除运算的线性表，通栈是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为常称插入、删除的这一端为栈顶栈顶( (Top)Top)，另一端为，另一端为栈底栈底( (Bottom)Bottom)。当栈中没有元素时称为空栈。当栈中没有元素时称为空栈。例、一叠书或一叠盘子。例、一叠书或一叠盘子。 a n a n-1 a2 a1栈顶 栈底抽象数据类型抽象数据类型栈栈ADT Stack 数据对象数据对象: D=a ai i |a|ai i ElemSet, i=1,2,ElemSet, i=1,2,n (n=0),n (n=0) 数据关系：数据关系：R=aR=

3、| a| ai-1i-1,a,ai i D,i=2,3,D,i=2,3,n,n 约定约定a an n端为栈顶，端为栈顶，a a1 1端为栈底。端为栈底。 基本操作基本操作: InitStack(&S)InitStack(&S) 操作结果操作结果: 建立一个空栈建立一个空栈S DestroyStack(&S)DestroyStack(&S) 初始条件：初始条件：栈栈S已存在已存在 操作结果操作结果: 栈栈S被销毁被销毁 ClearStack(&S)ClearStack(&S) 初始条件：初始条件：栈栈S已存在已存在 操作结果操作结果: 将将S栈清空栈清空StackEmpty(S)StackEmp

4、ty(S) 初始条件初始条件：栈栈S已存在已存在 操作结果操作结果：若栈：若栈S为空栈，返回为空栈，返回true,否则返回否则返回falseStackLength(S)StackLength(S) 初始条件初始条件：栈栈S已存在已存在 操作结果操作结果: 返回返回S的元素个数的元素个数GetTop(S,&e) /读栈顶元素读栈顶元素 初始条件初始条件：栈栈S已存在且非空已存在且非空 操作结果操作结果: 用用e返回栈顶元素返回栈顶元素Push(Push(&S,e) /入栈入栈 初始条件初始条件：栈栈S已存在已存在 操作结果操作结果: 将将元素元素e插入到栈顶插入到栈顶Pop(&S,&e) /出栈

5、出栈 初始条件初始条件：栈栈S已存在且非空已存在且非空 操作结果操作结果: 删除删除S的栈顶元素，用的栈顶元素，用e返回返回StackTraverse(S,visit() 初始条件初始条件：栈栈S已存在且非空已存在且非空 操作结果操作结果: 从栈底到栈顶依次对从栈底到栈顶依次对S的每个元素调用的每个元素调用visit()ADT Stack 由于栈的逻辑结构与线性表相同，因此线性表由于栈的逻辑结构与线性表相同，因此线性表的存储结构对栈也适应。的存储结构对栈也适应。3.1.2 3.1.2 栈的表示和实现栈的表示和实现v 顺序栈顺序栈v 链栈链栈栈的顺序存储结构简称为顺序栈，由于栈底位置栈的顺序存储

6、结构简称为顺序栈，由于栈底位置是固定不变的，所以可以将栈底位置设置在数组是固定不变的，所以可以将栈底位置设置在数组两端的任何一端；两端的任何一端；而栈顶位置是随着入栈和出栈而栈顶位置是随着入栈和出栈操作而变化的操作而变化的. .v顺序栈顺序栈顺序栈的类型定义如下：顺序栈的类型定义如下： #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct SElemType *base; /栈底指针，栈底指针，base=NULL表明栈不存在表明栈不存在 SElemType *top; /栈顶指针栈顶指针,top=base为栈空

7、的标志为栈空的标志 int stacksize; /栈当前可以使用的最大容量栈当前可以使用的最大容量 SqStack; 栈顶指针栈顶指针top,指向栈底指向栈底位置位置top入栈入栈Atop出栈出栈栈满栈满BCDEF设数组大小为设数组大小为stacksizetop=base,栈空，此时出栈，则栈空，此时出栈，则下溢下溢（underflow)top= stacksize,栈满，此时入栈，则栈满，此时入栈，则上溢上溢（overflow)toptoptoptoptoptoptoptoptoptoptop栈空栈空top123450栈空栈空base123450ABCDEFbase123450base顺序

8、栈的入栈与出栈顺序栈的入栈与出栈0M-1栈栈1底底栈栈1顶顶栈栈2底底栈栈2顶顶在一个程序中同时使用两个栈在一个程序中同时使用两个栈1、构造一个空栈、构造一个空栈 Status InitSatck(SqStack &S) S.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize= STACK_INIT_SIZE; /end InitSatck 基本操作的算法描述基本操作的算法描述2、返回栈顶元素、返回栈顶元素 Status

9、 GetTop(SqStack S，SElemTtype &e) if (S.top=S.base) return ERROR; e=*(S.top-1); return OK; /end GetTop 3 3、入栈、入栈Status Push(SqStack &S，SElemType e) if(S.top-S.base=S.stacksize) S.base=(SElemType*)realloc(S.base,(S. stacksize + STACKINCREMENT)* sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.ba

10、se+S.stacksize; S.stacksize+= STACKINCREMENT; *S.top+=e;/end Push4 4、出栈、出栈 Status Pop(SqStack &S，SElemType &e) if(S.top=S.base) return ERROR; e=*-S.top; return OK;/end Pop 栈顶栈顶.topdata next栈底栈底v链栈链栈其操作与线性链表类似其操作与线性链表类似 3.2.1 3.2.1 数制转换数制转换 3.2.2 3.2.2 括号匹配的检验括号匹配的检验 3.2.3 3.2.3 行编辑程序行编辑程序 3.2.5 3.2.

11、5 表达式求值表达式求值3.2 栈的应用举例栈的应用举例十进制十进制n n和其它进制数和其它进制数d d的转换是计算机实现计算的的转换是计算机实现计算的基本问题基本问题, ,其解决方法很多其解决方法很多, ,其中一个简单算法基于其中一个简单算法基于下列原理下列原理: : n=(n div d)n=(n div d)* *d + n mod dd + n mod d ( ( 其中其中: :divdiv为整除运算为整除运算, ,modmod为求余运算为求余运算) ) 例如例如 ( (1348)1348)1010=(2504)=(2504)8 8，其运算过程如下：其运算过程如下：3.2.1 数制转换

12、数制转换 例如：例如：（1348)10 = (2504)8 ， 其运算过程如下：其运算过程如下： 计算顺序计算顺序输出顺序输出顺序 n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2算法算法3.1 void conversion( ) /十进制转换为等值的八进制十进制转换为等值的八进制 Initstack(S); scanf (“%d”,N); while(N) Push(S,N%8); N=N/8; while(! StackEmpty(S) Pop(S,e); printf(“%d”,e); /end conversion假设表达式中充许括

13、号嵌套假设表达式中充许括号嵌套, ,则检验括号是否匹配的方法则检验括号是否匹配的方法可用可用“期待的急迫程度期待的急迫程度”这个概念来描述。例：这个概念来描述。例： ( ) ( ) 1 2 3 4 5 6 7 83.2.2 括号匹配的检验括号匹配的检验分析出现的分析出现的不匹配不匹配的情况的情况:到来的右括号到来的右括号不是所不是所“期待期待”的的;1）凡出现凡出现左括号，则入栈；左括号，则入栈；2）凡出现凡出现右括号，右括号，首先检查首先检查栈是否空栈是否空. . 若若栈空，栈空，则表明该则表明该“右括号右括号”多余多余, , 否则否则和栈顶元素和栈顶元素比较比较， 若若相匹配，相匹配，则则

14、“左括号出栈左括号出栈”, ,否则表明否则表明括号不匹括号不匹配配. .3）表达式检验结束时，表达式检验结束时， 若若栈空栈空，则表明表达式中，则表明表达式中括号匹配括号匹配, , 否则表明否则表明“左括号左括号”有余有余算法的设计思想：算法的设计思想：Status matching(string &exp) int state = 1; InitStack(S);while (i=StrLength(exp) & state) switch of expi case “(” : Push(S,expi); i+; break; case “)”: if(!StackEmpty(S) & Ge

15、tTop(S)=“(”) Pop(S,e); i+; else state = 0; break; if (StackEmpty(S) & state) return OK;检验括号匹配的算法：检验括号匹配的算法：在用户输入程序或数据时，允许用户输入出差错，当发现在用户输入程序或数据时，允许用户输入出差错，当发现有误时，可以及时更正。方法是：有误时，可以及时更正。方法是：设立一个输入缓冲区，用于接受用户输入的一行字符，然设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。后逐行存入用户数据区。假设退格符假设退格符“#”“#”表示前一个字符无效；表示前一个字符无效；退行符退行

16、符“”“”表示当前行中的字符全无效。表示当前行中的字符全无效。3.2.3 行编辑程序行编辑程序假设从终端接受了这样两行字符假设从终端接受了这样两行字符 whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行： while (*s) putchar(*s+);void LineEdit( ) InitStack(S); /栈栈S设为输入缓冲区设为输入缓冲区 ch=getchar( ); while(ch!=eof) while(ch!=eof & ch!=n) switch(ch) case # : Pop(S,ch); /书上

17、为书上为c case : ClearStack(S); default : Push(S,ch); /end switch ch=getchar( ); /end while将从栈底到栈顶内的字符传送到用户数据区；将从栈底到栈顶内的字符传送到用户数据区； ClearStack(s); if(ch!=eof) ch=gethar( ); /end whileDestroyStack(s);/end LineEdit行编辑程序算法：行编辑程序算法： 3.2.5 表达式求值表达式求值例如：例如：3*（7 2 ） （1）算术四则运算的规则：）算术四则运算的规则： a. 从左算到右从左算到右 b. 先乘

18、除，后加减先乘除，后加减 c. 先括号内，后括号外先括号内，后括号外 由此，此表达式的计算顺序为：由此，此表达式的计算顺序为： 3*（7 2 ）= 3 * 5 = 15（2）根据上述三条运算规则，在运算的每一步中，对）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符任意相继出现的算符 1和和 2 ，都要比较优先权关系。，都要比较优先权关系。算符优先法所依据的算符间的优先关系算符优先法所依据的算符间的优先关系见教材见教材P53表表3.1由表可看出，右括号由表可看出，右括号 ) 和井号和井号 # 作为作为 2时时级别最低；级别最低； 由由c规则规则得出：得出： * ，/， + ，-为为

19、 1时的优先权低于时的优先权低于（，高于，高于） 由由a规则规则得出：得出：（=） 表明括号内运算，已算完。表明括号内运算，已算完。 # = # 表明表达式求值完毕。表明表达式求值完毕。令令OP=+，-，*，/，（，），（，），# 3.2.5 表达式求值表达式求值（3）算法思想：）算法思想：设两个栈：操作符栈设两个栈：操作符栈 OPTR ，操作数栈，操作数栈 OPND栈初始化：设操作数栈栈初始化：设操作数栈 OPND 为空；操作符栈为空；操作符栈 OPTR 的栈底的栈底 元素为表达式起始符元素为表达式起始符 #；依次读入字符：是操作数则入依次读入字符：是操作数则入OPND栈，是操作符则要判断：

20、栈，是操作符则要判断： if 操作符操作符( 1) 栈顶元素，压入栈顶元素，压入OPTR栈。栈。 3.2.5 表达式求值表达式求值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)#1

21、5#GetTop(opnd) 例例 求表达式求表达式3*(7-2)Status EvaluateExpression( OperandType &result) InitStack(OPND); InitStack(OPTR); Push(OPTR ,#); c=getchar( ); while(c!=#)&(GetTop(OPTR)!=#) if (!In(c,OP) Push(OPND,c); c=getchar( ); else switch(compare(c,GetTop(OPTR) case : Push(OPTR , c); c=getchar( ); break; case

22、=: Pop(OPTR,x); c=getchar( ); break; case : Pop(OPTR,tem); Pop(OPND,b ); a=Pop(OPND,a ); c=getchar( ); break; /switch /while result=GetTop(OPND);/End EvaluateExpression3.2.4 迷宫求解迷宫求解 入口入口出口求迷宫路径算法的基本思想是：求迷宫路径算法的基本思想是：v若当前位置若当前位置“可通可通”，则纳入路径，继续前进，则纳入路径，继续前进; 若当前位置若当前位置“不可通不可通”，则后退，换方向继续，则后退，换方向继续探索探索

23、; 若四周若四周“均无通路均无通路”，则将当前位置从路径中，则将当前位置从路径中删除出去。删除出去。设当前位置为入口位置设当前位置为入口位置do if(当前位置可通当前位置可通) 当前位置插入栈顶当前位置插入栈顶; if(该位置是出口位置该位置是出口位置) 结束结束 else 切换当前位置的东邻方块为新的当前位置切换当前位置的东邻方块为新的当前位置; else if(栈不空栈顶位置尚有其它方向未经探索栈不空栈顶位置尚有其它方向未经探索) 设定新的当前位置为顺时针方向旋转找到的顶点设定新的当前位置为顺时针方向旋转找到的顶点 位置的下一个邻块位置的下一个邻块; if(栈不空且栈顶位置的四周均不通栈

24、不空且栈顶位置的四周均不通) 删去栈顶元素位置删去栈顶元素位置,直至找到一个可通的相邻块或直至找到一个可通的相邻块或 出栈或栈空出栈或栈空; while(栈不空栈不空);求迷宫中一条从入口到出口的路径的算法思想：求迷宫中一条从入口到出口的路径的算法思想：Type struct int ord; /通道块在路径上的序号通道块在路径上的序号 PosType seat; /通道块在迷宫中的通道块在迷宫中的“坐标位置坐标位置” int di; /从此通道块走向下一通道块的方向从此通道块走向下一通道块的方向SElemType; /栈元素类型栈元素类型Status MazePath(MazeType ma

25、ze, PosType start, PosType end) InitStack(S); curpos=start; /当前位置为入口位置当前位置为入口位置 curstep=1; /探索第一步探索第一步 do if(Pass(curpos) /当前位置可以通过当前位置可以通过 footprint(curpos); /留下足印留下足印 e=(curstep,curpos,1); Push(S,e); /加入路径加入路径 if(curpos=end) return(TRUE); /到达终点到达终点 curpose=NextPos(curpos,1); /下一个位置是当前位置的东邻下一个位置是当前

26、位置的东邻 curstep+; else /当前位置不通当前位置不通 if(!StackEmpty(S) Pop(S,e); while(e.di=4 & !StackEmpty(S) MarkPrint(e.seat); Pop(S,e);/留下不能通过的标记并后退留下不能通过的标记并后退 /end while if(e.di1时，先把上面时，先把上面n-1个圆盘从个圆盘从A移到移到B,然后将然后将n号盘从号盘从A移到移到C,再将再将n-1个盘从个盘从B移到移到C。即把求解。即把求解n个圆盘的个圆盘的Hanoi问题转化为求解问题转化为求解n-1个圆盘的个圆盘的Hanoi问题，依次类问题，依次

27、类推，直至转化成只有一个圆盘的推，直至转化成只有一个圆盘的Hanoi问题问题执行情况执行情况 递归工作栈保存内容：形参递归工作栈保存内容：形参n,x,y,z和返回地址和返回地址 返回地址用行编号表示返回地址用行编号表示n x y z 返回地址 main() int m; printf(Input number of disks ); scanf(%d,&n); printf( Steps : %3d disks ,n); hanoi(n,A,B,C);(0) void hanoi(int n,char X,char Y,char Z)(1) (2) if(n=1)(3) move(1,X,Z)

28、;(4) else(5) hanoi(n-1,X,Z,Y);(6) move(n,X,Z);(7) hanoi(n-1,Y,X,Z);(8) (9) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 6 main() int n; printf(Input the number of disks scanf(%d,&n); printf(The steps to moving %3d hanoi(n,X,Y,Z);(0) void hanoi(int n,char X,char Y,c

29、har Z)(1) (2) if(n=1)(3) move(1,X,Z);(4) else(5) hanoi(n-1,X,Z,Y);(6) move(n,X,Z);(7) hanoi(n-1,Y,X,Z);(8) (9) ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 6 main() int n; printf(Input the number of disks scanf(%d,&n); printf(The steps to moving %3d hanoi(n,X,Y,Z);(0)

30、 void hanoi(int n,char X,char Y,char Z)(1) (2) if(n=1)(3) move(1,X,Z);(4) else(5) hanoi(n-1,X,Z,Y);(6) move(n,X,Z);(7) hanoi(n-1,Y,X,Z);(8) (9) ABC3 A B C 02 B A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C 02 B A C 83 A B C 0 main() int n; printf(Input the number of disks scanf(%d,&n); printf(The steps

31、 to moving %3d hanoi(n,X,Y,Z);(0) void hanoi(int n,char X,char Y,char Z)(1) (2) if(n=1)(3) move(1,X,Z);(4) else(5) hanoi(n-1,X,Z,Y);(6) move(n,X,Z);(7) hanoi(n-1,Y,X,Z);(8) (9) ABC3 A B C 02 B A C 81 A B C 8ABC3 A B C 02 B A C 83 A B C 0栈空3 A B C 02 B A C 83.4 3.4 队列队列3.4.1 3.4.1 抽象数据类型队列的定义抽象数据类型队列

32、的定义v队列的定义及特点队列的定义及特点v定义定义：队列是限定只能在表的一端进行插入，：队列是限定只能在表的一端进行插入， 而在表的另一端进行删除的线性表。而在表的另一端进行删除的线性表。v队尾队尾(rear)允许插入的一端允许插入的一端v队头队头(front)允许删除的一端允许删除的一端v队列特点：先进先出队列特点：先进先出(FIFO) ADT Queue 数据对象：数据对象： D= a ai i|a|ai i QElemSet, i=1,2,QElemSet, i=1,2,n ,n=0,n ,n=0 数据关系：数据关系： R=|ai-1,ai D,i=2,n 基本操作基本操作:InitQu

33、eue(&Q) 操作结果操作结果:构造一个空队列构造一个空队列Q DestroyQueue(&Q) 初始条件初始条件:队列已存在队列已存在 操作结果操作结果:队列队列Q被销毁，不再存在被销毁，不再存在抽象数据类型队列的定义抽象数据类型队列的定义ClearQueue(&Q) 初始条件初始条件:队列已存在队列已存在 操作结果操作结果:将将Q清为空队列清为空队列QueueEmpty(Q) 初始条件初始条件:队列已存在队列已存在 操作结果操作结果:若若Q为空队列，返回为空队列，返回true,否则返回否则返回falseQueueLength(Q) 初始条件初始条件:队列已存在队列已存在 操作结果操作结果

34、:返回返回Q的元素个数的元素个数GetHead(Q,&e) 初始条件初始条件:队列队列Q非空非空 操作结果操作结果:用用e返回队头元素返回队头元素EnQueue(&Q,e)/入队入队 初始条件初始条件: 队列已存在队列已存在 操作结果操作结果: 插入元素插入元素e为为Q的新队尾元素的新队尾元素DeQueue(&Q,&e) /出队出队 初始条件初始条件: 队列队列Q非空非空 操作结果操作结果: 删除删除Q的队头元素，用的队头元素，用e返回返回QueueTraverse(Q,visit() 初始条件初始条件: 队列队列Q非空非空 操作结果操作结果: 从队头到队尾，依次对从队头到队尾，依次对Q的每个

35、数据元素的每个数据元素调调 用函数用函数visit().一旦一旦visit()失败，则操作失败失败，则操作失败ADT Queue 队列的链式存储结构简称为链队列，队列的链式存储结构简称为链队列，它是限制仅在表头删除它是限制仅在表头删除和表尾插入的单链表。和表尾插入的单链表。显然仅有单链表的头指针不便于在表显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾做插入操作，为此再增加一个尾指针尾指针，指向链表的最后一，指向链表的最后一个结点。于是，将链队列的类型个结点。于是，将链队列的类型LinkQueueLinkQueue定义为一个结构类定义为一个结构类型：型：3.4.2 链队列链队列t

36、ypedef struct QNode QElemType data; struct QNode *next; QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear; LinkQueue;头5836 frontrearQ.头frontrearQ.LinkQueue Q ;队列：队列：出队端出队端入队端入队端空队列：空队列：1.构造一个空队列构造一个空队列 void InitQueue(LinkQueue &Q) Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); /if(!Q.fron

37、t) exit(OVERFLOW); Q.front-next=NULL;/end InitQueue 链队列上实现的基本运算：链队列上实现的基本运算：2.销毁队列销毁队列void DestoryQueue(LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; /end while/end DestoryQueue3.入队入队void EnQueue(LinkQueue &Q, QElemType e) p=(QueuePtr )malloc(sizeof(QNode); pdata=e

38、; pnext=null; Q.rear-next=p; Q.rear=p; / end EnQueue 队首队尾frontrear队首队尾frontrear4. 出队出队Status DeQueue(LinkQueue &Q, QElemType &e) if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p);/end DeQueue注意：在出队算法中，注意：在出队算法中，一般只需修改队头指针。一般只需修改队头指针。

39、但当原队中只有一个结但当原队中只有一个结点时，该结点既是队头点时，该结点既是队头也是队尾，故删去此结也是队尾，故删去此结点时亦需修改尾指针，点时亦需修改尾指针，且删去此结点后队列变且删去此结点后队列变空。空。队首队尾frontrear队首front队尾rear 1 2 3 4 5 0frontJ1,J2,J3入队rearJ1,J2,J3出队J1J2J3rear123450front3.4.3 循环队列的顺序存储结构和实现循环队列的顺序存储结构和实现 （用一维数组实现（用一维数组实现sqM）J1J2J3rearJ4,J5,J6入队rear123450J4J5J6front设两个指针设两个指针fr

40、ont,rear, 约定：约定：front指示队头元素；指示队头元素；rear指示队尾元素的下一个指示队尾元素的下一个位置；位置；初值初值front=rear=0入队列：入队列：sqrear+=x;rearrearfrontfront空队列条件：空队列条件：front=rearfront=0rear=0123450队空出队列：出队列：x=sqfront+;frontv存在问题存在问题设数组维数为设数组维数为M，则：，则：v当当front=0,rear=M时，再有元素入队发生溢出时，再有元素入队发生溢出真溢出真溢出v当当front 0,rear=M时，再有元素入队发生溢出时，再有元素入队发生溢出

41、假溢出假溢出v解决方案解决方案v队首固定，每次出队后剩余元素向下移动队首固定，每次出队后剩余元素向下移动浪费时间浪费时间v循环队列循环队列v基本思想：把队列基本思想：把队列设想成环形设想成环形，让，让sq0接在接在sqM-1之后，之后，若若rear+1=M, 则令则令rear=0;0M-11frontrear. 实现：利用实现：利用“模模”运算运算 入队：入队： rear=(rear+1)%M; sqrear=x; 出队：出队： front=(front+1)%M; x=sqfront;012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345

42、rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear解决方案：解决方案：1.另外另外设一个标志设一个标志以区别队空、队满以区别队空、队满2.少用一个元素空间少用一个元素空间 队空：队空：front=rear 队满：队满：(rear+1)%M=front队尾指针加队尾指针加1追上队头，队列中有追上队头，队列中有一个空额，但避免判断标志的时一个空额，但避免判断标志的时间上的损失间上的损失队满：front=rear循环队列类型说明：循环队列类型说明：#define QueueSize 100 typedef Struct int front; int rear

43、; QElemType *base; 或或QElemType dataQueueSize; SqQueue;基本操作的算法描述基本操作的算法描述1. 构造空队列构造空队列void InitQueue(SqQueue &Q) Q.base=(QElemType*)malloc(QueueSize*sizeof(QElemType); if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; 2. 返回队列长度返回队列长度int QueueLength(SqQueue Q) Return (Q.rear-Q.front+ QueueSize )% QueueSiz

44、e;基本操作的算法描述基本操作的算法描述3. 入队入队Status EnQueue(SqQueue &Q,QElemType e) if(Q.rear+1)% QueueSize =Q.front ) return ERROR; Q.baseQ.rear=e; Q.rear=(Q.rear+1)% QueueSize; return OK;基本操作的算法描述基本操作的算法描述4. 出队出队 Status DeQueue(SqQueue &Q,QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.baseQ.front; Q.front=(Q.fr

45、ont+1)% QueueSize; return OK; void menu() printf(n* * * * * * * * * * * * * * * * * * * * nn); printf( 1 - EnQueue a data in the Queue.n); printf( 2 - DeQueue the Queuefront data in the Queue.n); printf( 3 - PrintFront.n); printf( 6 - Exit.n); printf(* * * * * * * * * * * * * * * * * * * * nn);void

46、menuselect(SqQueue *Q) int k,done=1; ET e; while (done) menu(); printf(please choose:); scanf(%d,&k); getchar(); switch(k) case 1: printf(Input the data you want to Insert:); e=getchar(); printf(n); EnQueue(Q,e); break; case 2:DeQueue(Q,&e);printf(e = %cn,e); break; case 3:if(GetHead(Q,&e)=ERROR) pr

47、intf(It is empty!n); else printf(e = %cn,e);break; case 6:done=0; void main() SqQueue Q; int i,j; ET e;InitQueue(&Q); printf(Input the number of the Queue data:); scanf(%d,&i); getchar(); printf(n); printf(Input the data of the Queue:n); for (j=1;j=i;j+) e=getchar(); EnQueue(&Q,e); menuselect(&Q);必须

48、熟练掌握这些算法必须熟练掌握这些算法.InitQueue(&Q)DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)EnQueue(&Q, e)DeQueue(&Q,&e)循环队列的基本操作循环队列的基本操作本章小结本章小结 理解理解栈栈和和队列队列这两种抽象数据类型的特点及这两种抽象数据类型的特点及与线性与线性表的异同表的异同 熟悉熟悉顺序栈顺序栈和和链栈链栈的组织方法以及基本运算的实现的组织方法以及基本运算的实现 理解递归算法理解递归算法掌握掌握链队列链队列和和循环队列循环队列的组织方法、简单算法实现的组织方法、简单算法实现队满、队空的判断条件及其描述队满、队空的判断条件及其描述上机作业上机作业 1 利用栈实现数制转换，能够实现利用栈实现数制转换，能够实现10进制到进制到2，4，8进制的转换，要求进制的转换，要求C代码能够运行，严格实现的基本代码能够运行，严格实现的基本操作。操作。 2 编程实现循环队列的基本操作，队列的大小为编程实现循环队列的基本操作，队列的大小为10，验证队列的正确性，设队列元素是字符。要求验证队列的正确性，设队列元素是字符。要求C代码能代码能够运行，严格实行队列的基本操作。够运行，严格实行队列的基本操作。