工学数据结构第三章课件

《工学数据结构第三章课件》由会员分享，可在线阅读，更多相关《工学数据结构第三章课件（72页珍藏版）》请在装配图网上搜索。

1、福州大学至诚学院n3.1 3.1 栈栈3.1.13.1.1抽象数据类型栈的定义抽象数据类型栈的定义3.1.23.1.2栈的表示与实现栈的表示与实现n3.2 3.2 栈的应用举例栈的应用举例3.2.1 3.2.1 数制转换数制转换3.2.2 3.2.2 括号配对问题括号配对问题3.2.4 3.2.4 迷宫求解迷宫求解*3.3 3.3 栈和递归的实现栈和递归的实现n3.4 3.4 队列队列3.4.1 3.4.1 抽象数据类型队列的定义抽象数据类型队列的定义3.4.2 3.4.2 链队列链队列 -队列的链式表示与实现队列的链式表示与实现3.4.3 3.4.3 循环队列循环队列 -队列的顺序表示与实现

2、队列的顺序表示与实现第三章第三章 栈和队列栈和队列福州大学至诚学院题目：将十进制数题目：将十进制数N N转换为其他进制数输出转换为其他进制数输出基本原理：基本原理：N=(n div d)*d+n mod dN=(n div d)*d+n mod d“divdiv”是整除运算，是整除运算，modmod为求余运算。为求余运算。数制转换数制转换福州大学至诚学院toptoptoptop4 4toptop4 40 0toptop4 40 05 5 例如：例如：(1348)(1348)1010=(2504)=(2504)8 8，其运算过程如下：，其运算过程如下：N N div 8 N mod 8N N d

3、iv 8 N mod 8 1348 168 4 1348 168 4 168 21 0 168 21 0 21 2 5 21 2 5 2 0 2 2 0 2计计算算顺顺序序输输出出顺顺序序toptop4 40 05 52 2福州大学至诚学院栈栈n栈的定义：操作受限制的线性表，只能在线性表的一端进行插入栈的定义：操作受限制的线性表，只能在线性表的一端进行插入和删除运算。和删除运算。n栈栈S=(aS=(a1 1，a a2 2，a a3 3，a an n)按照按按照按a a1 1a an n的次序进栈，如图：的次序进栈，如图：n栈顶栈顶TopTop：插入、删除的这一端。：插入、删除的这一端。n栈底栈

4、底Bottom:Bottom:不做任何操作的另一端。不做任何操作的另一端。n空栈：表中没有元素。空栈：表中没有元素。nLIFOLIFO：栈的修改是按后进先出的原：栈的修改是按后进先出的原则进行的。则进行的。福州大学至诚学院栈的抽象数据类型定义栈的抽象数据类型定义ADT Stack 数据对象：数据对象：D=ai|ai属于属于Elemset,(i=1,2,n,n0)数据关系：数据关系：R1=ai-1,ai|ai-1,ai属于属于D,(i=2,3,n)约定约定an为栈顶为栈顶,a1为栈底。为栈底。基本操作：基本操作：InitStack(&S);DestroyStack(&S);ClearStack(

5、&S);StackEmpty(S);StackLength(S);GetTop(S,&e);Push(&S,e);Pop(&S,&e);StackTraverse(S,visit()ADT Stack福州大学至诚学院栈的基本操作栈的基本操作nInitStack(&SInitStack(&S)操作结果操作结果:构造一个空的栈构造一个空的栈S S。nDestroyStack(&SDestroyStack(&S)初始条件初始条件:栈栈S S已经存在。已经存在。操作结果操作结果:销毁栈销毁栈S S。福州大学至诚学院栈的基本操作栈的基本操作nStackEmpty(SStackEmpty(S)初始条件初始

6、条件:栈栈S S已经存在。已经存在。操操作作结结果果:若若栈栈S S为为空空栈栈，则则返返回回TURE;TURE;否否则则返回返回FALSEFALSE。nStackLength(SStackLength(S)初始条件初始条件:栈栈S S已经存在。已经存在。操作结果操作结果:返回栈返回栈S S中的数据元素个数。中的数据元素个数。nGetTop(S,&eGetTop(S,&e)初始条件初始条件:栈栈S S已经存在且非空。已经存在且非空。操作结果操作结果:用用e e返回栈返回栈S S中栈顶元素的值。中栈顶元素的值。福州大学至诚学院nStackTraverse(S,visitStackTraverse

7、(S,visit()()初始条件初始条件:栈栈S S已经存在且非空。已经存在且非空。操操作作结结果果:从从栈栈底底到到栈栈顶顶依依次次对对S S的的每每个个元元素素调调用用函函数数visit visit()()。一一旦旦visit visit()()失失败败，则则操操作作失败。失败。福州大学至诚学院栈的基本操作栈的基本操作nPush(&S,ePush(&S,e)初始条件初始条件:栈栈S S已经存在。已经存在。操作结果操作结果:插入元素插入元素e e为新的栈顶元素。为新的栈顶元素。nPop(&S,&ePop(&S,&e)初始条件初始条件:栈栈S S已经存在且非空。已经存在且非空。操作结果操作结果

8、:删除删除S S的栈顶元素并用的栈顶元素并用e e返回其值。返回其值。nClearStack(&SClearStack(&S)初始条件初始条件:栈栈S S已经存在。已经存在。操作结果操作结果:将栈将栈S S重置为空栈。重置为空栈。福州大学至诚学院栈的顺序表示与实现栈的顺序表示与实现-(-(顺序栈顺序栈)#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct SElemType*base;/*/*在栈构造之前和销毁之后，在栈构造之前和销毁之后，basebase的值为的值为NULL*/NULL*/SElemType*to

9、p;/*/*栈顶指针栈顶指针*/int stacksize;/*/*当前已分配的存储空间，以元素为单位当前已分配的存储空间，以元素为单位*/SqStack;福州大学至诚学院顺序栈示意图顺序栈示意图*base*topstacksize初始初始空空栈栈*top=*base;stacksize=STACK_INIT_SIZE*base*topstacksize.a1.aian顺序栈顺序栈n空栈的栈顶指针指向栈底空栈的栈顶指针指向栈底 n非空栈中的栈顶指针始终在栈顶元素的下一个位置非空栈中的栈顶指针始终在栈顶元素的下一个位置福州大学至诚学院top123450进栈进栈A栈满栈满BCDEF设数组维数为设数

10、组维数为设数组维数为设数组维数为M M M Mtop=base,top=base,top=base,top=base,栈空栈空栈空栈空，此时出栈，此时出栈，此时出栈，此时出栈，则下溢（则下溢（则下溢（则下溢（underflow)underflow)underflow)underflow)top=M,top=M,top=M,top=M,栈满栈满栈满栈满，此时入栈此时入栈此时入栈此时入栈则上溢（则上溢（则上溢（则上溢（overflow)overflow)overflow)overflow)toptoptoptoptop123450空栈空栈topbasebasetop出栈出栈toptop栈空栈空ba

11、se栈底指针栈底指针base,base,始终始终指向栈底位置；栈顶指向栈底位置；栈顶指针指针top,top,其初值指向其初值指向栈底，始终在栈顶元栈底，始终在栈顶元素的下一个位置素的下一个位置123450ABtop福州大学至诚学院顺序栈的操作实现-InitStackInitStack/构造一个空的栈构造一个空的栈S SStatus InitStack(SqStack*s)s-base=(SElemType*)malloc (STACK_INIT_SIZE*sizeof(SElemType);if(!s-base)return(OVERFLOW);s-top=s-base;s-stacksize

12、=STACK_INIT_SIZE;return OK;福州大学至诚学院顺序栈的操作实现顺序栈的操作实现-GetTop/返回栈返回栈S中栈顶元素中栈顶元素Status GetTop(SqStack s,SElemType*e)if(s.top=s.base)return ERROR;*e=*(s.top-1);return OK;se*base*topstacksize.a1.aian*e=*(s.top-1);福州大学至诚学院*base*topstacksize.a1.aians*base*topstacksize.a1.aians栈满时，追加存储空间e*s-top+=e;顺序栈的操作实现顺序

13、栈的操作实现PushPush/插入元素插入元素e e为新的栈顶元素为新的栈顶元素福州大学至诚学院status Push(SqStack*s,SElemType e)if(s-top s-base=s-stacksize)temp=(SElemType*)realloc (s-base,(s-stacksize+STACKINCREMENT)*sizeof(SElemType);if(!temp)return(OVERFLOW);s-base=temp;s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;return OK

14、;福州大学至诚学院顺序栈的操作实现顺序栈的操作实现-删除删除S S的栈顶元素的栈顶元素status Pop(SqStack*s,SElemType*e)if(s-top=s-base)return ERROR;*e=*-s-top;return OK;*base*topstacksize.a1.aianse*e=*-s-top;福州大学至诚学院栈的链式表示栈的链式表示n链栈链栈:栈的链式存储结构称为链栈，它是运算是受限的单栈的链式存储结构称为链栈，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行链表，插入和删除操作仅限制在表头位置上进行.由于只由于只能在链表头部进行操作，故链表没有

15、必要附加头结点。能在链表头部进行操作，故链表没有必要附加头结点。指指向栈顶表元素的指针就是链表的头指针向栈顶表元素的指针就是链表的头指针，链式栈无栈满的，链式栈无栈满的问题，空间可扩充问题，空间可扩充a(n)a(n-1)a(1)栈顶栈底top福州大学至诚学院栈的链式表示栈的链式表示typedef struct snode*slink;typedef struct snode stackItem data;slink next;stackNode;typedef struct lstack slink top;/栈顶结点指针栈顶结点指针 int stackSize;Lstack;福州大学至诚学院

16、 .栈底栈底toptopxptop .栈底栈底topqp-next=top;top=p q=top;top=top-next 福州大学至诚学院作业：设将整数作业：设将整数1 1、2 2、3 3、4 4依次进栈，但只要出栈时栈非空，依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：则可将出栈操作按任何次序夹入其中，请回答下有问题：（1 1）若入栈次序为）若入栈次序为push(1)push(1)，pop()pop()，push(2push(2），），push(3)push(3)，pop()pop()，pop()pop()，push(4)push(4)，pop()pop

17、()，则出栈的数，则出栈的数字序列为什么？字序列为什么？（2 2）请分析）请分析1 1、2 2、3 3、4 4的的2424种排列中，哪些序列可以种排列中，哪些序列可以通过相应的入出栈得到。通过相应的入出栈得到。福州大学至诚学院题目：将十进制数题目：将十进制数N N转换为其他进制数输出转换为其他进制数输出基本原理：基本原理：N=(n div d)*d+n mod dN=(n div d)*d+n mod d“divdiv”是整除运算，是整除运算，modmod为求余运算。为求余运算。栈的应用举例栈的应用举例-数制转换数制转换福州大学至诚学院toptoptoptop4 4toptop4 40 0to

18、ptop4 40 05 5 例如：例如：(1348)(1348)1010=(2504)=(2504)8 8，其运算过程如下：，其运算过程如下：N N div 8 N mod 8N N div 8 N mod 8 1348 168 4 1348 168 4 168 21 0 168 21 0 21 2 5 21 2 5 2 0 2 2 0 2计计算算顺顺序序输输出出顺顺序序toptop4 40 05 52 2福州大学至诚学院栈的应用举例栈的应用举例void conversion()int n;SqStack s;InitStack(&s);scanf(“%d”,&n);while(n)Push(

19、&s,n%8);n=n/8;while(!StackEmpty(s)Pop(&s,&e);printf(“%d”,e);福州大学至诚学院假设在表达式中检测括号是否匹配假设在表达式中检测括号是否匹配(x*(x+y)-z)(x+y)*z)(Stack)malloc(sizeof(*S)栈的应用举例栈的应用举例-括号匹配的检测括号匹配的检测（）或（）或（）等为正确的格式，）等为正确的格式，（）或（）或（）或）或（）（）)均为不正确的格式均为不正确的格式。基本原理：假设表达式中允许括号嵌套，则检测括号是否基本原理：假设表达式中允许括号嵌套，则检测括号是否匹配可用，匹配可用，“期待的迫切程度期待的迫切程

20、度”这个概念来描述，每个右这个概念来描述，每个右括号应与最近遇到的尚未匹配的左括号相匹配。括号应与最近遇到的尚未匹配的左括号相匹配。福州大学至诚学院分析可能出现的分析可能出现的不匹配不匹配的情况的情况:到来的右括弧到来的右括弧并非是所并非是所“期待期待”的；的；例如：例如：考虑下列括号序列：考虑下列括号序列：()()1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8直到结束，也没有到来直到结束，也没有到来所所“期待期待”的括弧的括弧；到来的是不速之客；到来的是不速之客；福州大学至诚学院算法的设计思想：算法的设计思想：1 1）凡出现左括弧，则进栈；）凡出现左括弧，则进栈；2 2）凡出

21、现右括弧，首先检查栈是否空）凡出现右括弧，首先检查栈是否空 若栈空，则表明该若栈空，则表明该“右括弧右括弧”多余，多余，否则和栈顶元素比较，否则和栈顶元素比较，若相匹配，则若相匹配，则“左括弧出栈左括弧出栈”，否则表明不匹配。否则表明不匹配。3 3）表达式检验结束时，）表达式检验结束时，若栈空，则表明表达式中匹配正确，若栈空，则表明表达式中匹配正确，否则表明否则表明“左括弧左括弧”有余。有余。福州大学至诚学院void Parenthis(char*expr)int i,n;Stack s=StackInit();n=strlen(expr);for(i=0;in;i+)if(expri=()P

22、ush(i,s);else if(expri=)if(StackEmpty(s)printf(“位置位置%d处的右括号不匹配处的右括号不匹配n”,i);else Pop(s);/弹出最近遇到的左括号弹出最近遇到的左括号福州大学至诚学院while(!StackEmpty(s)printf(“位置位置%d处的右括号不匹配处的右括号不匹配n”,Pop(s);福州大学至诚学院栈的应用举例栈的应用举例-迷宫求解迷宫求解福州大学至诚学院求迷宫路径算法的基本思想是（穷举求解法）：求迷宫路径算法的基本思想是（穷举求解法）：v若当前位置若当前位置“可通可通”,则纳入路径则纳入路径,继续前进继续前进;v若当前位置

23、若当前位置“不可通不可通”，则后退，则后退,换方向继续探换方向继续探索索;v若四周若四周“均无通路均无通路”，则将当前位置从路径中，则将当前位置从路径中删除出去。删除出去。需要用一个后进先出的结构来保存从入口到当前位置的需要用一个后进先出的结构来保存从入口到当前位置的路径，保证在任何位置上都能沿着原路退回。路径，保证在任何位置上都能沿着原路退回。福州大学至诚学院算法思想算法思想设定当前位置的初值为入口位置设定当前位置的初值为入口位置;do do 若当前位置可通若当前位置可通,则则 将当前位置插入栈顶将当前位置插入栈顶;若该位置是出口位置、则结束若该位置是出口位置、则结束;否则切换当前位置的否则

24、切换当前位置的东邻东邻方块为新的当前位置方块为新的当前位置;否则否则 若栈不空且栈顶位置尚有其它方向未经探索若栈不空且栈顶位置尚有其它方向未经探索,则设定新的当前位置为顺时针方向旋转找到的栈顶则设定新的当前位置为顺时针方向旋转找到的栈顶 位置的下一相邻块位置的下一相邻块;若栈不空但栈顶位置的四周均不可通若栈不空但栈顶位置的四周均不可通,则则 删去栈顶位置删去栈顶位置;若栈不空若栈不空,则重新测试新的栈顶位置则重新测试新的栈顶位置,直至找到一个可通的相邻块或出栈至空栈直至找到一个可通的相邻块或出栈至空栈;while(while(栈不空栈不空););福州大学至诚学院迷宫求解的算法实现迷宫求解的算法

25、实现typedef struct int ord;/通道块在路径上的序号通道块在路径上的序号PosType seat;/通道块在迷宫中的坐标位置通道块在迷宫中的坐标位置int di;/从此通道走向下一通道的方向从此通道走向下一通道的方向SElemType;福州大学至诚学院Status MazePath(MazeType maze,PosType start,PosType end)InitStack(s);curpos=start;curstep=1;do if(Pass(curpos)/当前位置可通当前位置可通 FootPrint(curpos);/留下足迹留下足迹 e=(curstep,c

26、urpos,1);Push(s,e);/加入路径加入路径 if(curpos=end)return(TRUE);/到达终点到达终点(出口出口)curpos=NextPos(curpos,1);/下一个位置是当前位置的东邻方块下一个位置是当前位置的东邻方块 curstep+;/探索下一步探索下一步 福州大学至诚学院else /当前位置不能通过当前位置不能通过 if(!StackEmpty(s)Pop(s,e);While(e.di=4&!StackEmpty(s)MarkPrint(e.seat);/留下不能通过的足迹留下不能通过的足迹 Pop(s,e);/退回一步退回一步 if(e.di -*

27、/(#=nPrecede:Precede:判定运算符栈的栈顶运算符1与读入的运算符2之间的优先关系的函数nOperate:Operate:进行二元运算ab的函数.算术表达式求值OperandType EvaluateExpression()InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();While(c!=#|GetTop(OPTR)!=#)/不是运算符则进栈不是运算符则进栈 if(!In(c,OP)Push(OPND,c);c=getchar();else switch(Precede(GetTop(OPTR),c)case:/

28、退栈并将运算结果入栈退栈并将运算结果入栈 Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;default:printf(“Expression error!”);return(ERROR);/switch /else /while return GetTop(OPND);对算术表达式3*(7-2)求值n步骤 OPTR栈 OPND栈 输入字符 主要操作n1#3*(7-2)#Push(OPND,3)n2#3 *(7-2)#Push(OPTR,*)n3#*3 (7-2)#Push(OPTR,()n4

29、#*(3 7-2)#Push(OPND,7)n5#*(3 7 -2)#Push(OPTR,-)n6#*(-3 7 2)#Push(OPND,2)n7#*(-3 7 2 )#Operate(7,-,2)n8#*(3 5 )#POP(OPTR)n9#*3 5#Operate(3,*,5)n10#15#Return(GetTop(OPND)福州大学至诚学院栈的应用举例栈的应用举例函数调用函数调用n当在一个函数的运行期间调用另一函数时，在运行被调用当在一个函数的运行期间调用另一函数时，在运行被调用函数之前，系统需要函数之前，系统需要(1)(1)将所有的实参、返回地址等信息将所有的实参、返回地址等信息传

30、递给被调用函数保存传递给被调用函数保存;(2);(2)为被调用函数的局部变量分为被调用函数的局部变量分配存储区配存储区;(3);(3)将控制转移到被调函数的入口将控制转移到被调函数的入口n从被调用函数返回调用函数之前，系统需要完成以下工作从被调用函数返回调用函数之前，系统需要完成以下工作(1)(1)保存被调函数的计算结果保存被调函数的计算结果;(2);(2)释放被调函数的数据区释放被调函数的数据区;(3);(3)依照被调函数保存的返回地址将控制转移到调用函数。依照被调函数保存的返回地址将控制转移到调用函数。福州大学至诚学院n当有多个函数构成嵌套调用时，按照后调用先返回的原则，当有多个函数构成嵌

31、套调用时，按照后调用先返回的原则，函数之间的信息传递和控制转移通过函数之间的信息传递和控制转移通过“栈栈”来实现，系统来实现，系统将整个程序运行时所需的数据空间安排在一个栈中，每当将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，为该函数在栈顶分配一个存储区，每当调用一个函数时，为该函数在栈顶分配一个存储区，每当一个函数退出时，就释放它的存储区，则当前正在运行的一个函数退出时，就释放它的存储区，则当前正在运行的函数的数据区必在栈顶。函数的数据区必在栈顶。福州大学至诚学院n递归递归:直接或间接调用自身的算法称为递归算法，用函数自直接或间接调用自身的算法称为递归算法，用函数自身给出

32、定义的函数称为递归函数。身给出定义的函数称为递归函数。n递归函数的执行过程：在递归函数的执行函数中，需多次递归函数的执行过程：在递归函数的执行函数中，需多次进行自我调用。调用函数和被调用函数之间的链接和信息进行自我调用。调用函数和被调用函数之间的链接和信息交换需通过栈来进行。递归函数的运行过程类似于多个函交换需通过栈来进行。递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要概念时递归函数运行的因此，和每次调用相关的一个重要概念时递归函数运行的层次。层次。n假设调用该递归函数的主函数

33、时第假设调用该递归函数的主函数时第0 0层，则从主函数调用递层，则从主函数调用递归函数为进入第归函数为进入第1 1层，从第层，从第i i层递归调用本函数为进入层递归调用本函数为进入“下下一层一层”，即第，即第i+1i+1层，反之，退出第层，反之，退出第i i层递归应返回上一层，层递归应返回上一层，即第即第i-1i-1层。为保证递归函数正确执行，系统设立一个层。为保证递归函数正确执行，系统设立一个“递递归工作栈归工作栈”作为整个递归函数运行期间使用的数据存储区。作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个每一层递归所需信息构成一个“工作记录工作记录”，其中包括所，其中包括

34、所有的实参、所有的局部变量以及上一层的返回地址，每进有的实参、所有的局部变量以及上一层的返回地址，每进入一层递归，就产生一个新的工作记录压入栈顶，每退出入一层递归，就产生一个新的工作记录压入栈顶，每退出一层递归，就从栈顶弹出一个工作记录。一层递归，就从栈顶弹出一个工作记录。福州大学至诚学院n递归问题举例递归问题举例 Hanoi Hanoi塔问题：设塔问题：设a,b,ca,b,c是三个塔座，开始时在塔座是三个塔座，开始时在塔座a a上有一上有一叠共叠共n n个圆盘，这些圆盘自下而上，由大到小叠在一起，各个圆盘，这些圆盘自下而上，由大到小叠在一起，各圆盘从小到大编号为圆盘从小到大编号为1,2,1,

35、2,n,n,现要求将塔座现要求将塔座a a上的这一叠圆上的这一叠圆盘移到塔座盘移到塔座c c上，并按同样顺序叠置。移动圆盘需遵循如下上，并按同样顺序叠置。移动圆盘需遵循如下规则：规则：(1)(1)每次只能移动一个圆盘每次只能移动一个圆盘(2)(2)任何时刻都不能允许将较大的圆盘压在较小的圆盘上任何时刻都不能允许将较大的圆盘压在较小的圆盘上(3)(3)在满足移动规则在满足移动规则(1)(1)和和(2)(2)的前提下，可将圆盘移至的前提下，可将圆盘移至a,b,ca,b,c中中任一塔座上。任一塔座上。福州大学至诚学院void main()hanoi(3,a,b,c);/将将n个棋盘从个棋盘从x移到移

36、到zvoid hanoi(int n,char x,char y,char z)1 2 if(n=1)3 move(x,1,z);4 else 5 hanoi(n-1,x,z,y);/将编号将编号1.n-11.n-1的圆盘从的圆盘从x x移到移到y,y,利用利用z z作为辅助圆盘作为辅助圆盘 /将编号为将编号为n n的圆盘从的圆盘从x x移到移到z z6 move(x,n,z);/将编号将编号1.n-11.n-1的圆盘从的圆盘从y y移到移到z,z,利用利用x x为辅助圆盘为辅助圆盘7 hanoi(n-1,y,x,z);8 9 福州大学至诚学院福州大学至诚学院福州大学至诚学院福州大学至诚学院队

37、列队列n队列（队列（QueueQueue）:仅在队尾进行插入和队头进行删除操仅在队尾进行插入和队头进行删除操作的线性表，先进先出线性表作的线性表，先进先出线性表(FIFO)(FIFO)n队头（队头（frontfront）:线性表的表头端，即可删除端。线性表的表头端，即可删除端。n队尾（队尾（rearrear）:线性表的表尾端，即可插入端。线性表的表尾端，即可插入端。队头队头队尾队尾.a1a2a3an-1an入队列入队列(Enqueue)出队列出队列(Dequeque)福州大学至诚学院抽象数据类型队列的定义抽象数据类型队列的定义ADT Queue ADT Queue 数据对象：数据对象：D=D=

38、a ai i|a|ai i属于属于Elemset,(iElemset,(i=1,2,=1,2,n,n0),n,n0)数据关系：数据关系：R R1 1=a ai-1i-1,a,ai i|a|ai-1i-1,a,ai i属于属于D,(iD,(i=2,3,=2,3,n),n)约定约定a an n为队尾为队尾,a,a1 1为队头。为队头。基本操作：基本操作：InitQueue(&Q);DestroyQueue(&Q);ClearQueue(&Q);QueueEmpty(Q);QueueLength(Q);GetHead(Q,&e);EnQueue(&Q,e);DeQueue(&Q,&e);QueueT

39、raverse(Q,visit()ADT Queue队列队列福州大学至诚学院队列的基本操作队列的基本操作(之一之一)nInitQueueInitQueue(&Q)(&Q)操作结果操作结果:构造一个空的队列构造一个空的队列Q Q。nDestroyQueueDestroyQueue(&Q)(&Q)初始条件初始条件:队列队列Q Q已经存在。已经存在。操作结果操作结果:销毁队列销毁队列Q Q。nClearQueueClearQueue(&Q)(&Q)初始条件初始条件:队列队列Q Q已经存在。已经存在。操作结果操作结果:将队列将队列Q Q重置为空队列。重置为空队列。福州大学至诚学院队列的基本操作队列的基

40、本操作(之二之二)nQueueEmpty(Q)初始条件初始条件:队列队列Q Q已经存在。已经存在。操作结果操作结果:若队列若队列Q Q为空队列为空队列,则返回则返回TURE;TURE;否则返回否则返回FALSEFALSE。nQueueLength(Q)初始条件初始条件:队列队列Q Q已经存在。已经存在。操作结果操作结果:返回队列返回队列Q Q中的数据元素个数中的数据元素个数,即队列即队列Q Q的的长度。长度。nGetHead(Q,&e)初始条件初始条件:队列队列Q Q已经存在且非空。已经存在且非空。操作结果操作结果:用用e e返回队列返回队列Q Q中队头元素的值。中队头元素的值。福州大学至诚学

41、院队列的基本操作队列的基本操作(之三之三)nEnQueue(&Q,e)初始条件初始条件:队列队列Q Q已经存在。已经存在。操作结果操作结果:插入元素插入元素e e为新的队尾元素。为新的队尾元素。nDeQueue(&Q,&e)初始条件初始条件:队列队列Q Q已经存在且非空。已经存在且非空。操作结果操作结果:删除队列删除队列Q Q 的队头元素并用的队头元素并用e e返回其值。返回其值。nQueueTraverse(Q,visit()初始条件初始条件:队列队列Q Q已经存在且非空。已经存在且非空。操操作作结结果果:从从队队头头到到队队尾尾依依次次对对队队列列Q Q的的每每个个元元素素调调用用函函数数

42、visit()visit()。一旦。一旦visit()visit()失败，则操作失败。失败，则操作失败。福州大学至诚学院链队列链队列-队列的链式表示与实现队列的链式表示与实现n链队列：队列的链式存储结构简称为链队列，它是限制仅链队列：队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指在表头删除和表尾插入的单链表。显然仅有单链表的头指针针(front)(front)不便于在表尾做插入操作，为此再增加一个尾不便于在表尾做插入操作，为此再增加一个尾指针指针(rear)(rear)，指向链表的最后一个结点。链队列无队列满，指向链表的最后一个结点。链队列无队列满

43、的问题，空间可扩充。的问题，空间可扩充。a1anQ.frontQ.rearQ.frontQ.rear空队列空队列福州大学至诚学院typedef struct QNode QElemType data;struct QNode*next;Qnode,*QueuePtr;typedef struct QueuePtr front;/队头指针队头指针 QueuePtr rear;/队尾指针队尾指针 LinkQueue;data*nextfrontrearfrontx x入入队队xfrontreary y入入队队xyfrontreary y出出队队Q.rear-next=pQ.rear=pp=Q.fr

44、ont-nextQ.front-next=p-next free(p)prearrearpfrontrearx x出出队队xyIf(Q.rear=p)Q.rear=Q.front福州大学至诚学院链队列的操作实现链队列的操作实现InitQueueInitQueue/构造一个空的队列构造一个空的队列Q QStatus InitQueue(LinkQueue&Q)Q.rear=(QueuePtr)malloc(sizeof(QNode);Q.front=Q.rear;if(!Q.front)return(OVERFLOW);Q.front-next=NULL;return OK;/InitQueue

45、福州大学至诚学院链队列的操作实现链队列的操作实现 DestroyQueueDestroyQueue/销毁队列销毁队列Q QStatus DestroyQueue(LinkQueue&Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;福州大学至诚学院链队列的操作实现链队列的操作实现 EnQueueEnQueue/插入元素插入元素e e为新的队尾元素为新的队尾元素Status EnQueue(LinkQueue&Q,QelemType e)p=(QueuePtr)malloc(sizeof(QNod

46、e);if(!p)return(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;福州大学至诚学院链队列的操作实现链队列的操作实现DeQueueDeQueue/删除队列删除队列Q Q 的队头元素并用的队头元素并用e e返回其值返回其值Status DeQueue(LinkQueue&Q,QelemType&e)if(Q.front=Q.rear)retrun ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;fre

47、e(p);return OK;福州大学至诚学院循环队列队列的顺序表示和实现循环队列队列的顺序表示和实现#define MAXQSIZE 100 /最大队列长度最大队列长度 typedef struct QElemType *base;/动态分配存储空间动态分配存储空间 int front;/头指针，若队列不空，指向队列头元素头指针，若队列不空，指向队列头元素 int rear;/尾指针尾指针,若队列不空指向若队列不空指向 队列尾元素的下一个位置队列尾元素的下一个位置 SqQueue;福州大学至诚学院123450空队列空队列rear=0 front=0J1J2J3rearrear123450J4

48、,J5,J6入队J4J5J6frontrearrear123450frontJ1,J1,J3入队rear123450J1,J2,J3出队J1J2J3frontfrontfrontfrontv存在问题：存在问题：l当当front=0,rear=Mfront=0,rear=M时再有元素入队发生溢出时再有元素入队发生溢出真溢出真溢出l当当front0,rear=Mfront0,rear=M时再有元素入队发生溢出时再有元素入队发生溢出假溢出假溢出rear福州大学至诚学院n解决方案解决方案队首固定，每次出队剩余元素向下移动队首固定，每次出队剩余元素向下移动浪费时间浪费时间循环队列循环队列n 基本思想：把

49、队列基本思想：把队列设想成环形设想成环形，让，让sq0sq0接在接在sqM-1sqM-1之之后，若后，若rear+1=M,rear+1=M,则令则令rear=0;rear=0;实现：利用实现：利用“模模”运算运算入队入队:baserearbaserear=x;=x;rear=(rear+1)%M;rear=(rear+1)%M;出队：出队：x=x=basefrontbasefront;front=(front+1)%M;front=(front+1)%M;队满、队空判定条件队满、队空判定条件福州大学至诚学院012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4

50、,J5,J6出队出队J7,J8,J9入队入队队空：队空：front=rearfront=rear队满：队满：front=rearfront=rearJ5J6012345rearfront初始状态J4福州大学至诚学院解决方案解决方案n设一个布尔变量以区别队列的空和满设一个布尔变量以区别队列的空和满n使用一个计数器记录队列中元素的总数使用一个计数器记录队列中元素的总数n少用一个元素空间，约定当循环数组中元素个数达到少用一个元素空间，约定当循环数组中元素个数达到maxsize-1maxsize-1时队列为满，即以队列头指针指向队列尾指针的下时队列为满，即以队列头指针指向队列尾指针的下一位置（指环的下

51、一位置一位置（指环的下一位置)上作为队列呈上作为队列呈”满满“的标志的标志 队空：队空：front=rear front=rear 队满：队满：(rear+1)%M=frontrear+1)%M=front福州大学至诚学院循环队列空或满的判断循环队列空或满的判断012345J3J4J5Q.rearQ.front(a)一般队列一般队列012345Q.rearQ.front(c)空队列空队列J6J3J4J5012345J7Q.rearQ.front(b)满队列满队列福州大学至诚学院循环队列实现循环队列实现#define MAXSIZE 100typedef struct QElemType *ba

52、se;/存储空间基地址存储空间基地址 int front;/队头指针队头指针 int rear;/队尾指针队尾指针 SqQueue;福州大学至诚学院循环队列实现循环队列实现 InitQueueInitQueue/初始化空队列初始化空队列Status InitQueue(SqQueue&Q)Q.base=(QElemType*)malloc(sizeof(QElemType)*MAXSIZE);if(!Q.base)return(OVERFLOW);Q.front =Q.rear=0;return OK;福州大学至诚学院循环队列实现循环队列实现 EnQueueEnQueue/入队列入队列Stat

53、us EnQueue(SqQueue&Q,QelemType e)if(Q.rear+1)%MAXSIZE=Q.front)return(ERROR);Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK;福州大学至诚学院循环队列实现循环队列实现 DeQueueDeQueue/出队列出队列Status DeQueue(SqQueue&Q,QelemType&e)if(Q.front=Q.rear)retrun ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXSIZE;return OK;福州大学至诚学院3.2 写出以下程序段的输出结果（队列中的元素类型QElemType 为char）。void main()Queue Q;InitQueue(Q);Char x=e,y=c;EnQueue(Q,h);EnQueue(Q,r);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,a);While(!QueueEmpty(Q)DeQueue(Q,y);Printf(y);Printf(x);