第三章栈和队列

《第三章栈和队列》由会员分享，可在线阅读，更多相关《第三章栈和队列（59页珍藏版）》请在金锄头文库上搜索。

1、第三章栈和队列第三章栈和队列3.1 栈栈3.2 栈的应用栈的应用3.3 栈与递归的实现栈与递归的实现3.4 队列队列3.1 栈栈stack什么是栈什么是栈?栈的操作原则是什么栈的操作原则是什么?若有栈若有栈S=(a1，a2，.，an),哪个是栈顶元哪个是栈顶元素素,哪个是栈底元素哪个是栈底元素?栈的基本操作有哪些栈的基本操作有哪些?窗口函数调用撤消undo一、一、 栈的定义栈的定义栈是限定栈是限定仅在表尾进行插入或删除操作仅在表尾进行插入或删除操作的线性表的线性表 不含元素的空表称为不含元素的空表称为空栈空栈 若有栈若有栈S=(a1，a2，.，an), 则则a1为为栈底元素栈底元素、an为为栈

2、顶元素栈顶元素操作原则：操作原则：LI FOana1a2.栈底栈顶表尾称为表尾称为栈顶（栈顶（top）表头称为表头称为栈底（栈底（bottom）火车站入站出站栈的抽象数据类型栈的抽象数据类型ADT Stack数据对象数据对象:D =a ia i ElemSet, i= 1,2,n, n0 数据关系数据关系: R = a i-1 , a i D, i = 2,n 约定a n端为栈顶端为栈顶, a 1端为栈底端为栈底. 基本操作基本操作: DestroyStack(&S)；操作结果操作结果:栈栈S被销毁被销毁ClearStack(&S)；操作结果操作结果:栈栈S清为空栈清为空栈.InitStack

3、(&S)；操作结果操作结果:构造一个空栈构造一个空栈S.StackLength(S)；操作结果操作结果操作结果操作结果: :返回返回返回返回S S的元素个数的元素个数的元素个数的元素个数GetTop(S, &e)；初始条件初始条件初始条件初始条件: :栈栈栈栈S S已存在且非空已存在且非空已存在且非空已存在且非空. .操作结果操作结果操作结果操作结果: :用用用用e e返回返回返回返回S S的栈顶元素的栈顶元素的栈顶元素的栈顶元素. .StackEmpty(S)；操作结果操作结果操作结果操作结果: :若栈若栈若栈若栈S S为空栈为空栈为空栈为空栈, ,则返回则返回则返回则返回TRUE, TRU

4、E, 否则否则否则否则FALSEFALSEPush(&S, e)；操作结果操作结果操作结果操作结果: :插入元素插入元素插入元素插入元素e e为新的栈顶元素为新的栈顶元素为新的栈顶元素为新的栈顶元素. . Pop(&S, &e)；初始条件初始条件初始条件初始条件: :栈栈栈栈S S已存在且非空已存在且非空已存在且非空已存在且非空. .操作结果操作结果操作结果操作结果: :删除删除删除删除S S的栈顶元素的栈顶元素的栈顶元素的栈顶元素, ,并用并用并用并用e e返回其值返回其值返回其值返回其值 StackTraverse(S, visit( )；初始条件初始条件初始条件初始条件: :栈栈栈栈S

5、S已存在且非空已存在且非空已存在且非空已存在且非空. .操作结果操作结果操作结果操作结果: :从栈底到栈顶依次对从栈底到栈顶依次对从栈底到栈顶依次对从栈底到栈顶依次对S S的每个数据元素调用函数的每个数据元素调用函数的每个数据元素调用函数的每个数据元素调用函数visit().visit(). 一旦一旦一旦一旦visit()visit()失败失败失败失败, , 则操作失效则操作失效则操作失效则操作失效. .ADT StackDestroyStack(&S)；ClearStack(&S)；InitStack(&S)；StackLength(S)；GetTop(S, &e)GetTop(S, &e)

6、；StackEmpty(S)；Push(&S, e)； Pop(&S, &e)； StackTraverse(S, visit( )；二、栈的表示和实现二、栈的表示和实现1顺序栈顺序栈 利用一组地址连续的空间存放栈底到栈顶的元素利用一组地址连续的空间存放栈底到栈顶的元素 用指针用指针top指出栈顶元素的位置指出栈顶元素的位置2顺序栈定义顺序栈定义typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;3 顺序栈的实现顺序栈的实现 栈的顺序存储表示栈的顺序存储表示 #define STACK_INIT_SIZE

7、100 存储空间初始分配存储空间初始分配#define STACKINCREMENT 10 存储空间分配增量存储空间分配增量 基本操作的函数原型说明基本操作的函数原型说明 Status InitStack(SqStack &S); 构造一个空栈构造一个空栈SStatus DestroyStack(SqStack &S); 销毁栈销毁栈S,S不在存在不在存在Status ClearStack(SqStack &S); 把把S置为空栈置为空栈Status StackEmpty(SqStack S); 若栈若栈S为空栈为空栈,则返回则返回TRUE,否则返回否则返回FALSEint StackLeng

8、th(SqStack S); 返回返回S的元素个数的元素个数,即栈的长度即栈的长度Status GetTop(SqStack S, SElemType &e); 若栈不空若栈不空,则用则用e返回返回S的栈顶元素的栈顶元素,并返回并返回OK; 否则返回否则返回ERRORStatus Push(SqStack &S, SElemType e); 插入元素插入元素e为新的栈顶元素为新的栈顶元素Status Pop(SqStack &S, SElemType &e); 若栈不空若栈不空,则删除则删除S的栈顶元素的栈顶元素,用用e返回其值返回其值,并返回并返回OK; 否则返回否则返回ERRORStatu

9、s StackTraverse(SqStack S, Status(*visit)(); 从栈底到栈顶依次对栈中每个元素调用函数从栈底到栈顶依次对栈中每个元素调用函数visit(). 一旦一旦visit()失败失败,则操作失败则操作失败. 基本操作的算法描述基本操作的算法描述(部分部分)Status InitStack(SqStack &S) 构造一个空栈构造一个空栈S S.base=(SElemType*) malloc(STACK_INIT_SIZE *sizeof(SElemType); if (!S.base) exit(OVERFLOW); 存储分配失败存储分配失败 S.top =

10、S.base; S.stacksize = STACK_INIT_SIZE; return OK;InitStack100basetopStatus GetTop(SqStack S, SElemType &e)若栈不空若栈不空,则用则用e返回返回S的栈顶元素的栈顶元素,并返回并返回OK; 否则返回否则返回ERRORif (S.top =S.base) return ERROR;e = *(S.top-1);return OK;GetTopbasetopeStatus Push (SqStack &S,SElemType e) 插入元素插入元素e为新的栈顶元素为新的栈顶元素 if(S.top-

11、S.base=S.stacksize) 栈满栈满,追加存储空间追加存储空间 S.base = (SElemType*)realloc(S.base, (S.stacksize+ STACKINCREMENT)*sizeof(SElemType); if(!S.base)exit(OVERFLOW); 存储分配失败存储分配失败 S.top = S.base + S.stacksize; S.stacksize +=STACKINCREMENT; *S.top+ = e;return OK;PushbasetopeetopStatus Pop(SqStack &S,SElemType &e) 若栈

12、不空若栈不空,则删除则删除S的栈顶元素的栈顶元素,用用e返回其值返回其值,并返回并返回OK;否则返回否则返回ERROR;if(S.top=S.base) return ERROR;e = * -S.top;return OK;Popbasetopeetop4 4栈式链栈式链栈式链栈式链 *top为首元结点，做栈顶为首元结点，做栈顶 链式栈是在表头进行插入删除操作的链链式栈是在表头进行插入删除操作的链a5a4a3a2a1 top头结点?base1 top1 top2 base22 2多个栈共享空间多个栈共享空间多个栈共享空间多个栈共享空间三、三、 多个栈共享空间多个栈共享空间1两个栈共享空间两个

13、栈共享空间32栈的应用栈的应用一、数制转换一、数制转换二、二、 括号匹配括号匹配三、三、 行编辑行编辑四、迷宫求解四、迷宫求解五、五、 表达式求值表达式求值一、数制转换一、数制转换对于输入的任意一个非负十进制整数对于输入的任意一个非负十进制整数打印输出与其等值的八进制数打印输出与其等值的八进制数41073513164080110余余数数产产生生顺顺序序八八进进制制输输出出顺顺序序void conversion ( ) InitStack(S); 建空栈建空栈 scanf(&N); while(N) Push(S, N%8); N = N/8; while(!StatckEmpty(S) Pop

14、(S,e); printf(%d,e)； conversion二、二、 括号匹配括号匹配输入一个符号串，判断其中圆括号和方括号是否匹配输入一个符号串，判断其中圆括号和方括号是否匹配( a b h j ( f h ( j ) k g h ) )算法思想：算法思想：(1)凡出现左括号，则进栈凡出现左括号，则进栈(2)凡出现右括号，首先检查栈是否空凡出现右括号，首先检查栈是否空 如果栈空，表明右括号多了如果栈空，表明右括号多了 否则与栈顶元素比较，若相匹配，左括号出栈否则与栈顶元素比较，若相匹配，左括号出栈 否则不匹配否则不匹配(3)表达式检查结束时，若栈空，则匹配正确表达式检查结束时，若栈空，则匹

15、配正确Status match( )InitStack(S); scanf(ch); while (ch!= n) if (ch= ( | ch= ) Push(S,ch); else if (ch= ) if(StackEmpty(S) return ERROR; Pop(S, t); if (t!= ( ) return ERROR; else if (ch= ) if(StackEmpty(S) return ERROR; Pop(S, t); if (t!= ) return ERROR; scanf(ch); if(StackEmpty(S) return OK; else retu

16、rn ERROR;/match三、迷宫求解三、迷宫求解墙墙通道通道入口入口出口出口墙墙通道通道入口入口出口出口算法思想算法思想: 若当前位置可通若当前位置可通,则加入路径则加入路径 若当前位置不可通若当前位置不可通,则后退则后退,换一个方向搜索换一个方向搜索 若四周都不可通若四周都不可通,则从路径中删除则从路径中删除路径中最先被删除的位置是最近搜索过的路径中最先被删除的位置是最近搜索过的利用栈存放路径利用栈存放路径设定当前位置的初值为入口位置设定当前位置的初值为入口位置;do 若当前位置可通若当前位置可通, 将当前位置入栈将当前位置入栈; 切换当前位置的东邻方块为新的当前位置切换当前位置的东邻

17、方块为新的当前位置; while(栈不空栈不空) 若当前位置不可通若当前位置不可通若当前位置不可通若当前位置不可通, , 出栈出栈出栈出栈 找到下一个找到下一个找到下一个找到下一个可可可可能能能能通通通通的位置的位置的位置的位置 设定当前位置的初值为入口位置设定当前位置的初值为入口位置;do 若当前位置可通若当前位置可通, 则则 将当前位置入栈将当前位置入栈; 纳入路径纳入路径 若该位置是出口位置若该位置是出口位置,则结束则结束; 求得路径存放在栈中求得路径存放在栈中 否否则则切切换换当当前前位位置置的的东东邻邻方方块块为为新新的的当当前前位位置置; while(栈不空栈不空)否则否则 若栈不

18、空若栈不空 出栈出栈e 若若e的四周均不可通的四周均不可通(或探索过或探索过)则继续出栈则继续出栈 若若e尚有其他方向未经探索尚有其他方向未经探索 沿顺时针方向找到新的当前位置沿顺时针方向找到新的当前位置typedef struct int ord; 通道块在路径上的通道块在路径上的序号序号 PosType seat; 通道块在迷宫中的通道块在迷宫中的坐标位置坐标位置 int di; 从此通道块走向下一通道块的从此通道块走向下一通道块的方向方向 SElemType; 栈的元素类型栈的元素类型FootPrint(curpos); FootPrint(curpos); / /记录位置记录位置记录位

19、置记录位置curposcurpos已经搜索过已经搜索过已经搜索过已经搜索过Pass(curpos) Pass(curpos) / /返回位置返回位置返回位置返回位置curposcurpos是否可通是否可通是否可通是否可通( (搜索过搜索过搜索过搜索过) )NextPos(curpos,i); NextPos(curpos,i); / /返回从位置返回从位置返回从位置返回从位置curposcurpos按方向按方向按方向按方向i i到达的新位置到达的新位置到达的新位置到达的新位置MarkPrint(MarkPrint(curposcurpos); ); / /记录位置记录位置记录位置记录位置cur

20、pos4curpos4个方向都搜索过不可通个方向都搜索过不可通个方向都搜索过不可通个方向都搜索过不可通typedef struct int x,y; PosType; 坐标坐标Status MazePath (MazeType maze, PosType start, PosType end) 若迷宫若迷宫maze中存在从入口中存在从入口start到出口到出口end的通道的通道,则求得一条存放在栈中则求得一条存放在栈中 (从栈底到栈顶从栈底到栈顶),并返回并返回TRUE;否则返回否则返回FALSE InitStack(S); curpos = start; 设定设定当前位置当前位置为为入口位置

21、入口位置 curstep = 1; 探索第一步探索第一步 do if(Pass(curpos) 当前位置可以通过当前位置可以通过,即是未曾走到过的通道块即是未曾走到过的通道块 FootPrint(curpos); 留下足迹留下足迹 e = (curstep,curpos,1); Push(S,e); 加入路径加入路径 if(curpos=end) return(TRUE); 到达终点到达终点(出口出口) curpos = NextPos(curpos,1); 一位置是当前位置的东邻一位置是当前位置的东邻 curstep +; 探索下一步探索下一步else /if(!Pass(curpos) 当

22、前位置不能通过当前位置不能通过 if(!StackEmpty(S) Pop(S,e); while (e.di=4&!StackEmpty(S) MarkPrint(e.seat); Pop(S,e)/留下不能通过的标记留下不能通过的标记,并退回一步并退回一步 if(e.di4) e.di+; Push (S,e); 换下一个方向探索换下一个方向探索 curpos = NextPos(e.seat, e.di); 设定当前位置是该新方向上的相邻块设定当前位置是该新方向上的相邻块 if if if(else)while(!StackEmpty(S); return(FALSE); MazePat

23、h四、表达式求值四、表达式求值a+b*(c+d)+(c-d)/f栈内(1) 初始化，置初始化，置OPND为空栈，为空栈， 将将#压入压入OPTR栈底栈底(2) 依次读入表达式中的每个成员：依次读入表达式中的每个成员： (a)若是操作数，压入若是操作数，压入OPND栈栈 (b)若是界限符或运算符，若是界限符或运算符， 则与则与OPTR栈内运算符比较优先级，栈内运算符比较优先级， 若栈内高，若栈内高， 则从则从OPTR弹出运算符，弹出运算符， 并并OPND从弹出相应个数的操作数进行运算从弹出相应个数的操作数进行运算， 将运算结果压入将运算结果压入OPND栈栈 否则，将读入的运算符压入否则，将读入的

24、运算符压入OPTR栈栈(3) 重复重复(2)，直到读入，直到读入#且栈顶为且栈顶为#为止为止操作数操作数运算符运算符OperandType EvaluateExpression( ) 算术表达式求值的算符优先算法算术表达式求值的算符优先算法, OP为运算符集合为运算符集合 /设设OPTR和和OPND分别为运算符栈和运算数栈分别为运算符栈和运算数栈 InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c = getchar( ); while(c!=#GetTop(OPTR)!=#) if (!In(c,OP) Push(OPND,c);c = get

25、char( ); else while return GetTop(OPND);EvaluataeExpressionswitch(Precede(GetTop(OPTR),c) case: Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; switch后缀表达式（逆波兰表达式）后缀表达式（逆波兰表达式）一种不需要括号的后缀表达式如： ab+d* abd+*如何利用堆栈计算后缀表达式的值？中缀表达式如何转换为后缀表达式3.3 栈与递归的实现栈与递归的实现保存保存B的计算结果的计算结果

26、（return.）释放释放B的数据区的数据区按返回地址返回按返回地址返回A继续执行继续执行B(int x)int a, b; . return (.)A( )int m,n;.B(m);.当函数当函数A调用调用B，在执行，在执行B之前之前保存实参信息、返回地址保存实参信息、返回地址为为B的局部变量分配存储区的局部变量分配存储区将控制转移到将控制转移到B入口入口从从B返回返回A之前之前：int first(int s, int t);int second(int d);int main( ) int m, n; . first(m, n);1: .int first(int s, int t)

27、int i; . second(i); 2: . int second(int d)int x,y; .返回地址返回地址s,t(m,n)im,n返回地址返回地址d(i)x,y调用调用second时栈内时栈内的数据的数据调用函数前：调用函数前： 返回地址入栈返回地址入栈 实参入栈实参入栈 (形参形参)调用函数时先：调用函数时先： 局部变量入栈局部变量入栈返回调用函数前：返回调用函数前： 局部变量出栈局部变量出栈 形参出栈形参出栈 返回地址出栈返回地址出栈float fac(int n)float f; if(n=0 |n=1) f=1; else f=fac(n-1)*n; return f;f

28、loat fac(int n)float f; if(n=0 |n=1) f=1; else f=fac(n-1)*n; return f;float fac(int n)float f; if(n=0 |n=1) f=1; else f=fac(n-1)*n; return f;3n2n1n6f2f1fn3fn3fn2n3fn2fn3fn2fn1n3fn2fn1f 数制问题数制问题void f1(int num) if(num=8) f1(num/8); printf(%d,num%8);int main() int x=4107; f1(x); return 0;x(4107)返回地址nu

29、m(4107)返回地址num(513)返回地址num(64)返回地址num(8)返回地址num(1)34队列队列Queue1队列的定义队列的定义 队列是一种先进先出的线性表（队列是一种先进先出的线性表（FIFO） 限定：限定：只能在表的一端插入，而在另一端删除只能在表的一端插入，而在另一端删除只能在表的一端插入，而在另一端删除只能在表的一端插入，而在另一端删除 允许插入的一端称为允许插入的一端称为队尾队尾队尾队尾(rear)(rear) 允许删除的一端称为允许删除的一端称为队头队头队头队头(front)(front) 若若线线性性表表q=（ a1，a2，.，an ）是是一一个个队队列列，则则a

30、1是队头，是队头，an是队尾是队尾一、一、 队列队列a1 a2 a3 . an2队列的队列的ADTADT Queue 数据对象数据对象:D = ai | ai ElemSet, i = 1,2,n; n0 数据关系数据关系:R1 = ai-1, ai D, i = 1,2,n 基本操作基本操作: InitQueue(&Q)InitQueue(&Q) 操作结果操作结果:构造一个空队列构造一个空队列 DestroyQueue(&Q)DestroyQueue(&Q) 操作结果操作结果:队列队列Q被销毁被销毁,不再存在不再存在. ClearQueue(&Q)ClearQueue(&Q) 操作结果操作结

31、果:将将Q清为空队列清为空队列. QueueEmpty(Q)QueueEmpty(Q) 操作结果操作结果:若若Q为空队列为空队列,则返回则返回TRUE,否则返回否则返回FALSE. QueueLength(Q)QueueLength(Q) 操作结果操作结果:返回返回Q的元素个数的元素个数,即队列的长度即队列的长度. GetHead(Q,&e) GetHead(Q,&e) 初始条件初始条件:Q为非空队列为非空队列. 操作结果操作结果:用用e返回返回Q的队头元素的队头元素. EnQueue(&Q,e)EnQueue(&Q,e) 操作结果操作结果:插入元素插入元素e为为Q的新的队尾元素的新的队尾元素

32、. DeQueue(&Q,&e)DeQueue(&Q,&e) 初始条件初始条件:Q为非空队列为非空队列. 操作结果操作结果:删除删除Q的队头元素的队头元素,并用并用e返回其值返回其值. QueueTraverse(Q,visit()QueueTraverse(Q,visit() 初始条件初始条件:Q已存在且非空已存在且非空. 操作结果操作结果:从对头到队尾从对头到队尾,依次对依次对Q的每个数据元素的每个数据元素 调用函数调用函数visit().一旦一旦visit()失败失败,则操作失败则操作失败,/ADT Queue二、二、 顺序队列顺序队列 用一组地址连续的存储单元依次存放队列中的元素用一组

33、地址连续的存储单元依次存放队列中的元素方式一：用一维数组表示队列方式一：用一维数组表示队列typedef structQElemType *q; int rear; SqQueue1;Q.q0Q.q0表示队头，表示队头，表示队头，表示队头，Q.qQ.rear-1Q.qQ.rear-1表示队尾表示队尾表示队尾表示队尾队空：队空：队空：队空：Q.rear=0Q.rear=0队满：队满：队满：队满：Q.rear=100Q.rear=100（空间大小）（空间大小）（空间大小）（空间大小）出队：出队：出队：出队：e=Q.q0; Q.q1e=Q.q0; Q.q1至至至至Q.qQ.rear-1Q.qQ.re

34、ar-1往前挪往前挪往前挪往前挪入队：入队：入队：入队：Q.qQ.rear=e; Q.rear+;Q.qQ.rear=e; Q.rear+;方式二：方式二： #define Queue_SIZE 100 typedef struct QElemType *Q; int front; int rear; SqQueue2;frontrear三、三、 循环队列循环队列a1a2a3a4a5Q.frontQ.rearQ.frontQ.reara1a2a3a4a5Q.frontQ.reara6a7a8队空队空队满队满循环队列循环队列循环队列循环队列队列的顺序存储结构队列的顺序存储结构队列的顺序存储结构队

35、列的顺序存储结构#define MAXQSIZE 100 #define MAXQSIZE 100 最大队列长度最大队列长度最大队列长度最大队列长度typedef struct typedef struct QElemType QElemType *base; 初始化的动态分配存储空间初始化的动态分配存储空间初始化的动态分配存储空间初始化的动态分配存储空间 int int front; 头指针头指针头指针头指针, ,若队列不空若队列不空若队列不空若队列不空, ,指向队列头元素指向队列头元素指向队列头元素指向队列头元素 int int rear; 尾指针尾指针尾指针尾指针, ,若队列不空若队列不

36、空若队列不空若队列不空, ,指向队列尾元素的下一个位置指向队列尾元素的下一个位置指向队列尾元素的下一个位置指向队列尾元素的下一个位置SqQueue;SqQueue;解决方法：解决方法：（1）专设一个表示队满队空的标记）专设一个表示队满队空的标记full 一开始，一开始，full=0 当入队时出现当入队时出现Q.rear=Q.front，队满，队满full=1 当出队时出现当出队时出现Q.rear=Q.front，队空，队空full=0（2）专门空出一个位置不用）专门空出一个位置不用Q.rearQ.front队空队空a1a2a3a4a5Q.frontQ.reara6a7队满队满循环队列的基本操作

37、的算法描述循环队列的基本操作的算法描述Statue InitQueue(SqQueue &Q) 构造一个空队列构造一个空队列Q Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType); if (!Q.base) exit(OVERFLOW); 存储分配失败存储分配失败 Q.front = Q.rear = 0; return OK;int QueueLength(SqQueue Q)返回返回Q的元素个数的元素个数,即队列的长度即队列的长度 return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;Status

38、 EnQueue(SqQueue &Q,QElemType e) 插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 if(Q.rear+1)%MAXQSIZE = Q.front) return ERROR; 队列满队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1)% MAXQSIZE; return OK;Status DeQueue(SqQueue &Q, QElemType &e) 删除队头元素，送给变量删除队头元素，送给变量e if( Q.front=Q.rear ) return ERROR; 队列空队列空 e=Q.baseQ.front; Q.f

39、ront = (Q.front+1)% MAXQSIZE; return OK;队列的链式存储结构队列的链式存储结构队列的链式存储结构队列的链式存储结构typedef struct QNodetypedef struct QNodeQElemType data; QElemType data; Struct QNode *next; Struct QNode *next; QNode, *QueuePtr;QNode, *QueuePtr;四、链式队列四、链式队列 Q.frontQ.reartypedef struct QueuePtr front; 队头指针队头指针 QueuePtr rea

40、r; 队尾指针队尾指针LinkQueueStatus InitQueue(LinkQueue &Q) 构造一个空队列构造一个空队列QStatus DestroyQueue(LinkQueue &Q) 销毁空队列销毁空队列Q,队列队列Q不再存在不再存在Status ClearQueue(LinkQueue &Q) 将将Q清为空队列清为空队列Status QueueEmpty(LinkQueue Q) 若队列若队列Q为空队列为空队列,则返回则返回TRUE,否则返回否则返回FALSE .int QueueLength(LinkQueue Q) 返回返回Q的元素个数的元素个数,即为队列的长度即为队列的

41、长度Status GetHead(LinkQueue Q,QElemType &e) 若队列不为空若队列不为空,则用则用e返回返回Q的队头元素的队头元素,并返回并返回OK;否则返回否则返回ERRORStatus EnQueue(LinkQueue &Q,QElemType e) 插入元素插入元素e为为Q的新的队尾元素的新的队尾元素基本操作的函数原型说明基本操作的函数原型说明Status DeQueue(LinkQueue &Q,QElemType &e) 若队列不为空若队列不为空,则删除则删除Q的队头元素的队头元素,用用e返回其值返回其值,并返回并返回OK; 否则返回否则返回ERRORStat

42、us QueueTraverse(LinkQueue Q,visit() 从队头到队尾依次对队列从队头到队尾依次对队列Q中每个元素调用函数中每个元素调用函数visit()./一旦一旦visit失败失败,则操作失败则操作失败.Status InitQueue(LinkQueue &Q) 构造一个空队列构造一个空队列QQ.front = Q.rear = (QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW); 存储分配失败存储分配失败Q.front-next = NULL;return OK;基本操作的算法描述基本操作的算法描述基本操

43、作的算法描述基本操作的算法描述 Q.frontQ.rearStatus DestroyQueue(LinkQueue &Q) 销毁队列销毁队列Qwhile(Q.front) Q.rear = Q.front-next; free(Q.front); Q.front = Q.rear; return OK;Status DeQueue(LinkQueue &Q, QElemType &e) 若队列不空若队列不空若队列不空若队列不空, ,则删除则删除则删除则删除QQ的队头元素的队头元素的队头元素的队头元素, ,用用用用e e返回其值返回其值返回其值返回其值, , 并返回并返回并返回并返回OK; O

44、K; 否则返回否则返回否则返回否则返回ERRORERRORif(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); return OK;Status EnQueue(LinkQueue &Q, QElemType e) 插入元素插入元素e为为Q的新的队尾元素的新的队尾元素p = (QueuePtr)malloc(sizeof(QNode);if(!p) exit(OVERFLOW); 存储分配失败存储分配失败p-data = e; p-next = NULL;Q.rear-next = p; Q.rear = p;return OK;