课件chap003递归的执行过程

1、第三章 栈与队列通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。 线性表线性表 栈栈 队列队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) Delete(L, i) Delete(S, n) Delete(Q, 1) 1in 1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型辅导3.1 栈的类型定义栈的类型定

2、义3.2 栈的应用举例栈的应用举例3.3 栈类型的实现栈类型的实现3.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型的实现3.1 栈的类型定义栈的类型定义 ADT Stack 数据对象：数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, aiD, i=2,.,n 约定约定an 端为栈顶，端为栈顶，a1 端为栈底。端为栈底。 基本操作：基本操作： ADT StackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackL

3、ength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit()InitStack(&S)操作结果：构造一个空栈 S。DestroyStack(&S)初始条件：栈 S 已存在。操作结果：栈 S 被销毁。StackEmpty(S)初始条件：栈 S 已存在。操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。ClearStack(&S)初始条件：栈 S 已存在。操作结果

4、：将 S 清为空栈。 GetTop(S, &e) 初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。a1 a2an Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。a1 a2an e Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1 a2anan-1 栈的表示和实现 与线性表类似，栈也有两种存储表示法： （1）顺序栈 （2）链式栈示例： 输入： 1，2，3 如何使用Push和Pop操作，使得 输出： 2，3，1 或 3，2，1 或

5、1，2，3stacksizetopbase顺序栈 ADCBATypedef struct SElemType * base; SElemType *top; int stacksize;SqStack;空栈B AtopbasetopbasetopbaseA进栈B,C,D进栈D,C出栈SqStack S/- 栈的顺序存储表示 - #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; 类似于线性表的顺序

6、映象实现，指向表尾的指针可以作为栈顶指针。 Status InitStack (SqStack &S)/ 构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;Status GetTop( SqStack S, SElemType &e ) /若栈不空，则用若栈不空，则用e返回返回S的栈顶元素，并返回的栈顶元素

7、，并返回OK;否则返回否则返回ERROR if( S.top = S.base ) return ERROR; e= *(s.top-1); return OK; Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /栈满，追加存储空间栈满，追加存储空间 S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (ElemType); if (!S.base) exit (OVERFLOW);

8、/存储分配失败存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;Status Pop (SqStack &S, SElemType &e) / 若栈不空，则删除若栈不空，则删除S的栈顶元素，的栈顶元素， / 用用e返回其值，并返回返回其值，并返回OK； / 否则返回否则返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;3.2 栈的应用举例栈的应用举例例一、例一、 数制转

9、换数制转换例二、例二、 括号匹配的检验括号匹配的检验例三、例三、 行编辑程序问题行编辑程序问题例四、例四、 迷宫求解迷宫求解例五、例五、 表达式求值表达式求值例六、例六、 实现递归实现递归例一、例一、 数制转换数制转换 算法基于原理：算法基于原理： N = (N div d)d + N mod d 例如：（例如：（1348)10 = (2504)8 ，其运算过程如下：，其运算过程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2计算顺序计算顺序输出顺序输出顺序void conversion () InitStack(S); scanf (

10、%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion书本的代码书本的代码void conversion () InitStack(S); scanf (%d,N); do Push(S, N % 8); N = N/8; while(N); while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion改进：改进：N=0也能正常显示也能正常显示例二、例二、 括号匹配的检验括号匹配

11、的检验假设在表达式中假设在表达式中（）或（）或（ ）等为正确的格式，等为正确的格式，（ ）或（）或（ ）或）或 （）（）)均为不正确的格式。均为不正确的格式。则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的不匹配的情况: 到来的右括弧并非是所“期待”的；例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8 到来的是“不速之客”； 直到结束，也没有到来所“期待”的括弧。算法的设计思想：算法的设计思想：假设输入的表达式的每个括号为假设输入的表达式的每个括号为a1,a2,.,an,for i=1 to n，对每个括号，对每个括号ai, 1）凡出现左括弧，则进

12、栈；）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空）凡出现右括弧，首先检查栈是否空 (1)若栈空，则表明该若栈空，则表明该“右括弧右括弧”多余，多余， 表明表达式错误，表明表达式错误， (2)若栈不空，则和栈顶元素比较，若栈不空，则和栈顶元素比较， (a)若相匹配，则若相匹配，则“左括弧出栈左括弧出栈” ， (b)若不匹配，则表明表达式错误。若不匹配，则表明表达式错误。当表达式检验结束时（即当表达式检验结束时（即 i n ），）， 若栈空，则表明表达式中表达式正确，若栈空，则表明表达式中表达式正确， 若栈不空，表明若栈不空，表明“左括弧左括弧”多余多余,表明表达式错误。表明表达式

13、错误。Status matching(string& exp) int state = 1; while (i=Length(exp) & state) switch (expi) case “(”:Push(S,expi); i+; break; case”)”: if (NOT StackEmpty(S)&GetTop(S)=“(“ ) Pop(S,e); i+; else state = 0; break; default: state = 0; break; if (StackEmpty(S)&state) return OK; 例三、行编辑程序问题例三

14、、行编辑程序问题如何实现？如何实现？“每接受一个字符即存入存储器每接受一个字符即存入存储器” ? 并不恰当！ 设立一个输入缓冲区，用以接受设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存用户输入的一行字符，然后逐行存入用户数据区，并假设入用户数据区，并假设“#”为退格符为退格符，“”为退行符。为退行符。 在用户输入一行的过程中，允许在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时用户输入出差错，并在发现有误时 可以及时更正。可以及时更正。合理的作法是：假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是

15、下列两行： while (*s) putchar(*s+); while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置S为空栈 default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符 ClearStack(S); / 重置S为空栈if (ch != EOF) ch = getchar();while (ch != EOF) /EOF为全文结束符为全文结束符将从栈底到栈顶的字符传送至调用

16、过程的数据区；例四、例四、 迷宫求解迷宫求解通常用的是“穷举求解”的方法# #$# #$# $# # # # # #路径：当前已经走过的位置序列当前位置：即将试图去踩的位置，不一定能踩上，该位置还没有保存在路径中。求迷宫路径算法的基本思想是： 若当前位置“可通”，则纳入路径，继续前进; 若当前位置“不可通”，则后退，换方向继续探索; 若四周“均无通路”，则将当前位置从路径中删除出去。东东南南西西北北东东南南西西北北当前位置当前位置curpos当前位置当前位置当前已经踩上当前已经踩上的位置序列的的位置序列的最后一步最后一步设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈

17、顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为 新的当前位置； 否则 while (栈不空）；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法： 若栈不空且栈顶位置尚有其他方向未被探索，若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为则设定新的当前位置为: 沿顺时针方向旋转沿顺时针方向旋转 找到的栈顶位置的下一相邻块；找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；则删去栈顶位置；/ 从路径中删去该通道块从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，若栈不空，则

18、重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空；直至找到一个可通的相邻块或出栈至栈空；若栈空，则表明迷宫没有通路。若栈空，则表明迷宫没有通路。Typedef struct int ord; PosType seat; int di;SElemType;Status MazePath(MazeType maze, PosType start, PosType end) /若迷宫maze中存在从入口start 到出口end的通道，则求得一条存放在栈中（从栈底到栈顶），并返回TRUE；否则返回FALSE;InitStack(S); curpos = start;curstep =1;d

19、o if ( Pass( curpos) ) /当前位置可通当前位置可通 FootPrint(curpos); e = ( curstep, curpos, 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);

20、 if ( e.di4 ) e.di+; Push(S,e);/换下一个方向探索 /设定当前位置是该方向上的相邻块。 curpos= NextPos(e.seat,e.di); /if / if / else while ( !StackEmpty(S) ); return (FALSE); /MazePath 表达式 4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10 -2 = 8例五、例五、 表达式求值表达式求值表达式的组成：操作数Operand：5, 255运算符Operator：+，- ，*， /界限符delimiter：(, ), #运算符和界限符统称为：算符，它

21、们构成的集合命名为：OP。设1，2OP,在运算的每一步中，任意两个相继出现的算符1，2的优先关系至多是下面三个关系之一：12 : 1的优先权高于2算符间的优先关系： 2 211 + - * / ( ) # + - * / ( # =为了实现算符优先算法，使用两个工作栈：一个称作OPTR,用以寄存运算符；一个称作OPND,用以寄存操作数或运算结果；OperandType EvaluateExpression() / 算术表达式求值的算符优先算法。设OPTR和/OPND分别为运算符栈和运算数栈。 /OP为运算符集合。假设输入的表达式是正确的。 InitStack(OPTR); Push(OPTR,

22、 #); InitStack(OPND); c=getchar(); while( c!=# | GetTop(OPTR) !=#) if( !In( c, OP) ) Push(OPND,c); c=getchar(); else switch( Precede (GetTop(OPTR),c) ) case : /退栈并将运算结果入栈。 Pop(OPTR, theta); Pop(OPND,b); Pop(OPND,a); Push( OPND, Operate(a, theta, b) ); break; /switch /while return GetTop(OPND);int Op

23、erate( int a, char theta, int b) if( theta = + ) return a+b; if( theta =- ) return a-b; .该算法的不足之处 3 + 4 5 3 + 4 5 算法不能检查出第二个表达式的错误。 也就是说该算法对正确的表达式能计算出正确的结果。栈：仅在表尾进行插入和删除的线性表。栈：仅在表尾进行插入和删除的线性表。栈的特点：后进先出栈的特点：后进先出 Last In First Out ( LIFO)栈顶指针链栈链栈a1an注意注意: 链栈中链栈中指针的方向指针的方向an-1空栈：栈顶指针空栈：栈顶指针top=NULL不需要头

24、结点！不需要头结点！入栈操作：入栈操作：p = malloc(); p-data = e; p-next = top; top = p;栈顶指针topa1an入栈：入栈：栈顶指针topa1ean新生成的结点的指针p检验当空栈经过一次入栈后，变成有一个结点的链栈检验当空栈经过一次入栈后，变成有一个结点的链栈栈顶指针top=NULLa1栈顶指针top栈顶指针topa1an-1出栈：出栈：栈顶指针topa1 anan-1出栈操作：出栈操作：p = top; e = p-data ; top = top-next; free(p); return e; an栈的链式存储结构称为链栈， typedef

25、struct StackNode SElemType data; struct StackNode *next; StackNode; typedef struct struct StackNode *top; int len; LinkStack;栈顶指针a1a20a1920LinkStack S;S.topS.len void InitStack(LinkStack &S) S.top=NULL; S.len = 0; int StackEmpty(LinkStack S) return S.top=NULL; int StackLength( LinkStack S) retur

26、n S.len; Status Push ( LinkStack &S, SElemType e) StackNode *p; p=(StackNode*)malloc(sizeof(StackNode); if( p=NULL) exit(OVERFLOW); pdata = e; pnext=S.top; S.top=p; S.len+; return OK;Status Pop(LinkStack & S, SElemType & e) SElemType e; StackNode * p; if( S.top =NULL ) return ERROR; /Sta

27、ck underflow p = S.top; /p指向栈顶结点 e = pdata; S.top=pnext; /把栈顶元素从链表中删除 S.len -; free(p);/释放该出栈的结点 return OK; Status GetTop(LinkStack S, SElemType & e) if(S.top = NULL) return ERROR;/空栈，没有元素 e = S.topdata; return OK; 栈与递归的实现 栈还有一个重要的应用是实现函数嵌套调用 嵌套调用:调用一个函数的过程中，又调用另一个函数void first(int s, int t);void

28、 second( int d);void main() int m, n;first(m,n);3000:int first( int s, int t) int i;second(i);4000:int second( int d) int x,y; 为被调用函数的形参分配存储区； 为被调用函数的局部变量分配存储区； 将所有的函数参数、返回地址等信息传递给被调用函数保存； 将控制转移到被调用函数的入口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：int first( int s, int t) int i;second(i);4000:sti52003

29、000返回地址main() m=3; n=200; first(m+2,n); 3000: 保存被调函数的计算结果(即return的值，放在CPU的寄存器中)； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：int first( int s, int t) int i;second(i);4000:return 10;sti52003000返回地址main() m=3; n=200; first(m+2,n); 3000:first函数的数据区多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理”后调用先返回后调用

30、先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区 void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t) int i=8;3800:second(i);4000:int second( int d) int x,y;5000: 执行执行main函数前的状态函数前的状态void f

31、irst(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t) int i;second(i);4000:int second( int d) int x,y; 9000 2 1main返回地址返回地址mn执行到执行到first(m,n)前栈的状态前栈的状态启动代码void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);

32、3000:main();9000:.int first( int s, int t) int i;3800:second(i);4000:int second( int d) int x,y;5000: 3000 2 1 9000 2 1main返回地址返回地址mn执行到执行到second(i)前栈的状态前栈的状态stifirst返回地址返回地址启动代码void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t

33、) int i=8;3800:second(i);4000:int second( int d) int x,y;5000: 4000 83000 2 1 9000 2 1main返回地址返回地址mn执行到执行到second函数的函数的5000指令时的状态指令时的状态stifirst返回地址返回地址dxysecond返回地址返回地址启动代码void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t) int i

34、=8;3800:second(i);4000:int second( int d) int x,y;5000: 3000 2 1 9000 2 1main返回地址返回地址mn执行完执行完second函数回到函数回到4000指令时的状态指令时的状态stifirst返回地址返回地址启动代码void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t) int i=8;3800:second(i);4000:int s

35、econd( int d) int x,y;5000: 9000 2 1main返回地址返回地址mn执行完执行完first函数回到地址为函数回到地址为3000的指令时的状态的指令时的状态启动代码void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t) int i=8;3800:second(i);4000:int second( int d) int x,y;5000: 执行完执行完main函数时的状态函数

36、时的状态启动代码4000 83000 2 1 9000 2 1main返回地址返回地址mn执行到执行到second函数的函数的5000指令时的状态指令时的状态stifirst返回地址返回地址dxysecond返回地址返回地址84000123000129000一行表示：一次函数调用一行表示：一次函数调用时，栈的情况时，栈的情况栈与递归的实现 一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。Fact(n)=1 若若 n = 0n*Fact(n-1) 若若 n 0unsigned int Fact ( unsigned int n) if ( n=0) return 1;

37、return n*Fact(n-1);Fact(n)=n!Fact(n)函数直接调用自己函数直接调用自己在C语言程序设计中，递归调用也是函数嵌套调用，在编译处理上没有什么区别。 间接调用自己 int a() . b(.); void b() . count = a(); 对编译器而言，递归调用和其他的函数调用没有什么对编译器而言，递归调用和其他的函数调用没有什么区别，都采用同样的编译处理过程。区别，都采用同样的编译处理过程。 递归的特点、用途主要是针对编程人员而言的。递归的特点、用途主要是针对编程人员而言的。 对于如何编写递归程序，我们在对于如何编写递归程序，我们在“树和二叉树树和二叉树”这一

38、章学这一章学unsigned int Fact ( unsigned int n) int x; 3000: if ( n=0) return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 35087 n x 返回地址返回地址 当调用当调用Fact(3) 刚进入刚进入Fact函数时，函数时，栈的状态栈的状态5087到到5089是把函数结果赋值给是把函数结果赋值给y的指令的指令5080：调用Fact(3);5087:把函数返回值赋值给y;unsigned int Fact ( u

39、nsigned int n) int x; 3000: if ( n=0) return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 23015 35087 n x 返回地址返回地址 当调用当调用Fact(2) 刚进入刚进入Fact函数时，函数时，栈的状态栈的状态3015到到3019是计算乘法和赋值的指令是计算乘法和赋值的指令3010：调用Fact(n-1);3015:把函数返回值*n,并赋值给x;unsigned int Fact ( unsigned int n) int

40、 x; 3000: if ( n=0) return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 13015 23015 35087 n x 返回地址返回地址 当调用当调用Fact(1) 刚进入刚进入Fact函数时，函数时，栈的状态栈的状态3015到到3019是计算乘法和赋值的指令是计算乘法和赋值的指令3010：调用Fact(n-1);3015:把函数返回值*n,并赋值给x;unsigned int Fact ( unsigned int n) int x; 3000: if

41、 ( n=0) return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 03015 13015 23015 35087 n x 返回地址返回地址 当调用当调用Fact(0) 刚进入刚进入Fact函数时，函数时，栈的状态栈的状态3015到到3019是计算乘法和赋值的指令是计算乘法和赋值的指令3010：调用Fact(n-1);3015:把函数返回值*n,并赋值给x;unsigned int Fact ( unsigned int n) int x; 3000: if ( n=0

42、) return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 13015 23015 35087 n x 返回地址返回地址 当调用当调用Fact(0) 完成返回到上一层完成返回到上一层Fact函数时，函数时，栈的状态栈的状态3015到到3019是计算乘法和赋值的指令是计算乘法和赋值的指令3010：调用Fact(n-1);3015:把函数返回值*n,并赋值给x;unsigned int Fact ( unsigned int n) int x; 3000: if ( n=0)

43、return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 23015 35087 n x 返回地址返回地址 当调用当调用Fact(1) 完成返回到上一层完成返回到上一层Fact函数时，函数时，栈的状态栈的状态3015到到3019是计算乘法和赋值的指令是计算乘法和赋值的指令3010：调用Fact(n-1);3015:把函数返回值*n,并赋值给x;unsigned int Fact ( unsigned int n) int x; 3000: if ( n=0) return 1

44、; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 35087 n x 返回地址返回地址 当调用当调用Fact(2) 完成返回到上一层完成返回到上一层Fact函数时，函数时，栈的状态栈的状态3015到到3019是计算乘法和赋值的指令是计算乘法和赋值的指令5080：调用Fact(3);5087:把函数返回值赋值给y;unsigned int Fact ( unsigned int n) int x; 3000: if ( n=0) return 1; 3010: x = n*Fact(n

45、-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); n x 返回地址返回地址 当调用当调用Fact(3) 完成返回到地址为完成返回到地址为5087的指令时，的指令时，栈的状态栈的状态3015到到3019是计算乘法和赋值的指令是计算乘法和赋值的指令5080：调用Fact(3);5087:把函数返回值赋值给y;3.4 队列的类型定义队列的类型定义 队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。a1 a2an 出队列出队列入队列入队列队头队头队尾队尾双端队列：限定插入和删除操作在表的

46、两端进行的线性表。几种受限的双端队列：（1）队列（2）输出受限的双端队列：一个端点允许插入和删除，另一个端点只允许插入；（3）一个端点允许插入和删除，另一个端点只允许删除;（4）双栈：限定双端队列从某个端点插入的元素只能从该端点删除（蜕变为两个栈底相邻接的栈）。a1 a2 a3 an-1 an插入插入删除删除插入插入删除删除ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中约定其中a1 端为队列头，端为队列头， an 端为队列尾端为队列尾基本操作：基本操作： A

47、DT Queue队列的基本操作：队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()InitQueue(&Q) 操作结果：构造一个空队列操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列初始条件：队列Q已存在。已存在。 操作结果：队列操作结果：队列Q被销毁，被销毁，

48、 不再存在。不再存在。 ClearQueue(&Q)初始条件：队列Q已存在。 操作结果：将Q清为空队列。 QueueEmpty(Q)初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。 GetHead(Q, &e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。a1 a2an EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。a1 a2an e DeQueue(&Q, &a

49、mp;e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。a1 a2an 3.5 队列类型的实现队列类型的实现链队列链队列链式映象链式映象循环队列循环队列顺序映象顺序映象 typedef struct QNode / 结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;链队列链队列链式映象链式映象typedef struct / 链队列类型链队列类型 QueuePtr front; / 队头指针队头指针 QueuePtr rear; / 队尾指针队尾指针 LinkQueue;a1anQ.frontQ.rea

50、rQ.frontQ.rear空队列空队列 Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK;Q.frontQ.rear空队列空队列 Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (size

51、of (QNode); if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;a1Q.frontQ.rearana1Q.frontQ.reareanp Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回OK；否则返回ERROR 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); r