
第三章栈和队列ppt课件.ppt
59页第三章栈和队列第三章栈和队列3.1 栈栈3.2 栈的运用栈的运用3.3 栈与递归的实现栈与递归的实现3.4 队列队列3.1 栈栈stack什么是栈什么是栈?栈的操作原那么是什么栈的操作原那么是什么?假设有栈假设有栈S=(a1,,a2,,…….,,an),哪个是栈哪个是栈顶元素顶元素,哪个是栈底元素哪个是栈底元素?栈的根本操作有哪些栈的根本操作有哪些?窗口函数调用吊销undo一、一、 栈的定义栈的定义栈栈是是限限定定仅仅在在表表尾尾进进展展插插入入或或删删除除操操作作的的线线性表性表 不含元素的空表称为空栈不含元素的空表称为空栈 假设有栈假设有栈S=(a1,,a2,,…….,,an), 那么那么a1为栈底元素、为栈底元素、an为栈顶为栈顶元素元素操作原那么:操作原那么:LI FOana1a2….栈底栈顶表尾称为栈顶〔表尾称为栈顶〔top〕〕表头称为栈底〔表头称为栈底〔bottom〕〕火车站入站出站•栈的笼统数据类型栈的笼统数据类型•ADT Stack•{数数据据对对象象:D ={a i∣ ∣a i ∈∈ElemSet, i= 1,2,…,n, n≥0}• 数数据据关关系系: R = {< a i-1 , a i > ∣ ∣ a i-1 , a i ∈∈D, i = 2,…,n }• 商定商定a n端为栈顶端为栈顶, a 1端为栈底端为栈底. • 根本操作根本操作: DestroyStack(&S);;操作结果操作结果:栈栈S被销毁被销毁ClearStack(&S);;操作结果操作结果:栈栈S清为空栈清为空栈.InitStack(&S);;操作结果操作结果:构造一个空栈构造一个空栈S.StackLength(S);;操作结果操作结果:前往前往S的元素个数的元素个数GetTop(S, &e);;初始条件初始条件:栈栈S已存在且非空已存在且非空.操作结果操作结果:用用e前往前往S的栈顶元素的栈顶元素.StackEmpty(S);;操作结果操作结果:假设栈假设栈S为空栈为空栈,那么前往那么前往TRUE, 否那否那么么FALSEPush(&S, e);;操作结果操作结果:插入元素插入元素e为新的栈顶元素为新的栈顶元素. Pop(&S, &e);;初始条件初始条件:栈栈S已存在且非空已存在且非空.操作结果操作结果:删除删除S的栈顶元素的栈顶元素,并用并用e前往其前往其值值 StackTraverse(S, visit( ));;初始条件初始条件:栈栈S已存在且非空已存在且非空.操作结果操作结果:从栈底到栈顶依次对从栈底到栈顶依次对S的每个数据元素的每个数据元素调用函数调用函数visit(). 一旦一旦visit()失败失败, 那么操作失效那么操作失效.}ADT StackDestroyStack(&S);;ClearStack(&S);;InitStack(&S);;StackLength(S);;GetTop(S, &e)GetTop(S, &e);;;;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 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 StackLength(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; ∥∥ 否那么前往否那么前往ERRORStatus 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 = S.base; S.stacksize = STACK_INIT_SIZE; return OK;}∥∥InitStack100basetopStatus GetTop(SqStack S, SElemType &e){∥∥假假设设栈栈不不空空,那那么么用用e前前往往S的的栈栈顶顶元元素素,并并前前往往OK; ∥∥否那么前往否那么前往ERRORif (S ==S.base) return ERROR;e = *(S-1);return OK;}∥∥GetTopbasetopeStatus Push (SqStack &S,SElemType e){ ∥∥插入元素插入元素e为新的栈顶元素为新的栈顶元素 if(S-S.base>=S.stacksize) { ∥∥栈满栈满,追加存储空间追加存储空间 S.base = (SElemType*)realloc(S.base, (S.stacksize+ STACKINCREMENT)*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); ∥∥存存储储分分配配失失败败 S = S.base + S.stacksize; S.stacksize +=STACKINCREMENT; }*S++ = e;return OK;}∥∥PushbasetopeetopStatus Pop(SqStack &S,SElemType &e){ ∥∥假假设设栈栈不不空空,那那么么删删除除S的的栈栈顶顶元元素素,用用e前前往其值往其值,并前往并前往OK;否那么前往否那么前往ERROR;if(S==S.base) return ERROR;e = * --S;return OK;}∥∥Popbasetopeetop4 4.栈式链.栈式链.栈式链.栈式链 *top *top为首元结点,做栈顶为首元结点,做栈顶为首元结点,做栈顶为首元结点,做栈顶 链式栈是在表头进展插入删除操作的链链式栈是在表头进展插入删除操作的链链式栈是在表头进展插入删除操作的链链式栈是在表头进展插入删除操作的链a5a4a3a2a1 top头结点?base1 top1 top2 base22 2.多个栈共享空间.多个栈共享空间.多个栈共享空间.多个栈共享空间三、三、 多个栈共享空间多个栈共享空间1.两个栈共享空间.两个栈共享空间3..2栈的运用栈的运用一、数制转换一、数制转换二、二、 括号匹配括号匹配三、三、 行编辑行编辑四、迷宫求解四、迷宫求解五、五、 表达式求值表达式求值一、数制转换一、数制转换对于输入的恣意一个非负十进制整数对于输入的恣意一个非负十进制整数打印输出与其等值的八进制数打印输出与其等值的八进制数41073513164080110余余数数产产生生顺顺序序八八进进制制输输出出顺顺序序void conversion ( ){ InitStack(S); ∥∥建建空空栈栈 scanf(&N); while(N) { Push(S, N%8); N = N/8; } while(!StatckEmpty(S)) { Pop(S,e); printf("%d",e);; }}∥∥conversion二、二、 括号匹配括号匹配输入一个符号串,判别其中圆括号和方括号能否匹配输入一个符号串,判别其中圆括号和方括号能否匹配( a b [ h j ] ( f [ h ( j ) k ] g h ) )算法思想:算法思想:(1)凡出现左括号,那么进栈凡出现左括号,那么进栈(2)凡出现右括号,首先检查栈能否空凡出现右括号,首先检查栈能否空 假设栈空,阐明右括号多了假设栈空,阐明右括号多了 否那么与栈顶元素比较,假设相匹配,左括号出栈否那么与栈顶元素比较,假设相匹配,左括号出栈 否那么不匹配否那么不匹配(3)表达式检查终了时,假设栈空,那么匹配正确表达式检查终了时,假设栈空,那么匹配正确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 return ERROR;}//match三、迷宫求解三、迷宫求解墙墙通道通道入口入口出口出口墙墙通道通道入口入口出口出口算法思想算法思想: 假设当前位置可通假设当前位置可通,那么参与途径那么参与途径 假设当前位置不可通假设当前位置不可通,那么后退那么后退,换一个方换一个方向搜索向搜索 假设周围都不可通假设周围都不可通,那么从途径中删除那么从途径中删除途径中最先被删除的位置是最近搜索过的途径中最先被删除的位置是最近搜索过的利用栈存放途径利用栈存放途径设定当前位置的初值为入口位置设定当前位置的初值为入口位置;do{ 假设当前位置可通假设当前位置可通, { 将当前位置入栈将当前位置入栈; 切换当前位置的东邻方块为新的当前位置切换当前位置的东邻方块为新的当前位置; }}while(栈不空栈不空) 假设当前位置不可通假设当前位置不可通假设当前位置不可通假设当前位置不可通, , { {出栈出栈出栈出栈 找到下一个能够通的位置找到下一个能够通的位置找到下一个能够通的位置找到下一个能够通的位置 } }设定当前位置的初值为入口位置设定当前位置的初值为入口位置;do{ 假设当前位置可通假设当前位置可通, 那么那么{ 将当前位置入栈将当前位置入栈; ∥∥纳入途径纳入途径 假假设设该该位位置置是是出出口口位位置置,那那么么终终了了; ∥∥求求得得途途径径存放在栈中存放在栈中 否否那那么么切切换换当当前前位位置置的的东东邻邻方方块块为为新新的的当当前前位位置置; }}while(栈不空栈不空)否那么否那么 假设栈不空假设栈不空 { 出栈出栈e 假设假设e的周围均不可通的周围均不可通(或探求过或探求过)那么继续出那么继续出栈栈 假设假设e尚有其他方向未经探求尚有其他方向未经探求 沿顺时针方向找到新的当前位置沿顺时针方向找到新的当前位置}typedef struct{ int ord; ∥∥通通道道块块在在途途径径上上的的"序号序号" PosType seat; ∥∥通通道道块块在在迷迷宫宫中中的的"坐标位置坐标位置" int di; ∥∥从从此此通通道道块块走走向向下下一一通道块的通道块的"方向方向" }SElemType; ∥∥栈的元素类型栈的元素类型FootPrint(curpos); //FootPrint(curpos); //记录位置记录位置记录位置记录位置curposcurpos曾经搜索曾经搜索曾经搜索曾经搜索过过过过Pass(curpos) //Pass(curpos) //前往位置前往位置前往位置前往位置curposcurpos能否可通能否可通能否可通能否可通( (搜搜搜搜索过索过索过索过) )NextPos(curpos,i); //NextPos(curpos,i); //前往从位置前往从位置前往从位置前往从位置curposcurpos按方向按方向按方向按方向i i到达的到达的到达的到达的新位置新位置新位置新位置MarkPrint(curpos); //MarkPrint(curpos); //记录位置记录位置记录位置记录位置curpos4curpos4个方向都搜索过个方向都搜索过个方向都搜索过个方向都搜索过不可通不可通不可通不可通typedef struct{ int x,y; }PosType; ∥∥坐标坐标Status MazePath (MazeType maze, PosType start, PosType end){ ∥∥假假设设迷迷宫宫maze中中存存在在从从入入口口start到到出出口口end的的通通道道,那那么求得一条存放在栈中么求得一条存放在栈中 ∥∥(从栈底到栈顶从栈底到栈顶),并前往并前往TRUE;否那么前往否那么前往FALSE InitStack(S); curpos = start; ∥∥设设定定"当当前前位位置置"为为"入入口位置口位置" 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)) { ∥∥当前位置不能经过当前位置不能经过 if(!StackEmpty(S)) { Pop(S,e); while (e.di==4&&!StackEmpty(S)) {MarkPrint(e.seat); Pop(S,e)}//留留下下不不能能经经过过的的标标志志,并退回一步并退回一步 if(e.di<4) { e.di++; Push (S,e); ∥∥换换下下一一个个方方向向探探求求 curpos = NextPos(e.seat, e.di); ∥∥设设定定当当前前位位置置是是该该新新方方向向上的相邻块上的相邻块 }∥∥if }∥∥if }∥∥if(else)}while(!StackEmpty(S)); return(FALSE); }∥∥MazePath四、表达式求值四、表达式求值a+b*(c+d)+(c-d)/f栈内(1) 初始化,置初始化,置OPND为空栈,为空栈, 将将‘#’压入压入OPTR栈底栈底(2) 依次读入表达式中的每个成员:依次读入表达式中的每个成员: (a)假设是操作数,压入假设是操作数,压入OPND栈栈 (b)假设是界限符或运算符,假设是界限符或运算符, 那么与那么与OPTR栈内运算符比较优先级,栈内运算符比较优先级, 假设栈内高,假设栈内高, 那么从那么从OPTR弹出运算符,弹出运算符, 并并OPND从弹出相应个数的操作数进展运算,从弹出相应个数的操作数进展运算, 将运算结果压入将运算结果压入OPND栈栈 否那么,将读入的运算符压入否那么,将读入的运算符压入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 = getchar( ); } else }∥∥while return GetTop(OPND);}∥∥EvaluataeExpressionswitch(Precede(GetTop(OPTR),c) {case‘<’: Push(OPTR,c); c=getchar(); break; ∥∥栈顶优先权低栈顶优先权低 case'=': Pop(OPTR,x); c= getchar(); break; case'>': Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b)); break; }∥∥switch后缀表达式〔逆波兰表达式〕后缀表达式〔逆波兰表达式〕一种不需求括号的后缀表达式如: ab+d* abd+*如何利用堆栈计算后缀表达式的值?中缀表达式如何转换为后缀表达式3.3 栈与递归的实现栈与递归的实现•保管保管B的计算结果的计算结果 〔〔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){ 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;}float 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)前往地址num(4107)前往地址num(513)前往地址num(64)前往地址num(8)前往地址num(1)3..4队列队列Queue1·队列的定义队列的定义 队列是一种先进先出的线性表〔队列是一种先进先出的线性表〔FIFO〕〕 限定:只能在表的一端插入,而在另一端删除限定:只能在表的一端插入,而在另一端删除 允许插入的一端称为队尾允许插入的一端称为队尾(rear) 允许删除的一端称为队头允许删除的一端称为队头(front) 假假设设线线性性表表q=〔〔 a1,,a2,,…….,,an 〕〕是是一一个个队列,那么队列,那么a1是队头,是队头,an是队尾是队尾一、一、 队列队列a1 a2 a3 ……. an2·队列的队列的ADTADT Queue{ 数数据据对对象象:D = {ai | ai ∈∈ElemSet, i = 1,2,…,n; n≥0} 数数据据关关系系:R1 = {< ai-1, ai>∣ ∣ai-1, ai ∈∈D, i = 1,2,…n} 根本操作根本操作: InitQueue(&Q) 操作结果操作结果:构造一个空队列Q.构造一个空队列Q. DestroyQueue(&Q) 操作结果操作结果:队列队列Q被销毁被销毁,不再存在不再存在. ClearQueue(&Q) 操作结果操作结果:将将Q清为空队列清为空队列. QueueEmpty(Q) 操操作作结结果果:假假设设Q为为空空队队列列,那那么么前前往往TRUE,否那么前往否那么前往FALSE. QueueLength(Q) 操作结果操作结果:前往前往Q的元素个数的元素个数,即队列的长度即队列的长度. GetHead(Q,&e) 初始条件初始条件:Q为非空队列为非空队列. 操作结果操作结果:用用e前往前往Q的队头元素的队头元素. EnQueue(&Q,e) 操作结果操作结果:插入元素插入元素e为为Q的新的队尾元素的新的队尾元素. DeQueue(&Q,&e) 初始条件初始条件:Q为非空队列为非空队列. 操作结果操作结果:删除删除Q的队头元素的队头元素,并用并用e前往其值前往其值. QueueTraverse(Q,visit()) 初始条件初始条件:Q已存在且非空已存在且非空. 操操作作结结果果:从从对对头头到到队队尾尾,依依次次对对Q的的每每个个数数据据元素元素 调调用用函函数数visit().一一旦旦visit()失失败败,那那么么操作失败操作失败,}//ADT Queue二、二、 顺序队列顺序队列 用用一一组组地地址址延延续续的的存存储储单单元元依依次次存存放放队队列中的元素列中的元素方式一:用一维数组表示队列方式一:用一维数组表示队列typedef struct{QElemType *q; int rear; }SqQueue1;Q.q[0]Q.q[0]表示队头,表示队头,表示队头,表示队头,Q.q[Q.rear-1]Q.q[Q.rear-1]表示队尾表示队尾表示队尾表示队尾队空:队空:队空:队空:Q.rear==0Q.rear==0队满:队满:队满:队满:Q.rear>=100Q.rear>=100〔空间大小〕〔空间大小〕〔空间大小〕〔空间大小〕出队:出队:出队:出队:e=Q.q[0]; Q.q[1]e=Q.q[0]; Q.q[1]至至至至Q.q[Q.rear-1]Q.q[Q.rear-1]往前挪往前挪往前挪往前挪入队:入队:入队:入队:Q.q[Q.rear]=e; Q.rear++;Q.q[Q.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队空队空队满队满∥∥∥∥––––––––––循环队列循环队列循环队列循环队列────队列的顺序存储构造队列的顺序存储构造队列的顺序存储构造队列的顺序存储构造––––––––––#define MAXQSIZE 100 #define MAXQSIZE 100 ∥∥∥∥最大队列长度最大队列长度最大队列长度最大队列长度typedef struct typedef struct {QElemType *base; {QElemType *base; ∥∥∥∥初始化的动态分配存储空初始化的动态分配存储空初始化的动态分配存储空初始化的动态分配存储空间间间间 int front; int front; ∥∥∥∥头指针头指针头指针头指针, ,假设队列不空假设队列不空假设队列不空假设队列不空, ,指向指向指向指向队列头元素队列头元素队列头元素队列头元素 int rear; int rear; ∥∥∥∥尾指针尾指针尾指针尾指针, ,假设队列不空假设队列不空假设队列不空假设队列不空, ,指向队列尾元指向队列尾元指向队列尾元指向队列尾元素的下一个位置素的下一个位置素的下一个位置素的下一个位置}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队满队满∥∥–––––循环队列的根本操作的算法描画循环队列的根本操作的算法描画–––––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 EnQueue(SqQueue &Q,QElemType e){∥∥ 插入元素插入元素e为为Q的新的队尾元素的新的队尾元素 if((Q.rear+1)%MAXQSIZE == Q.front) return ERROR; ∥∥队列满队列满 Q.base[Q.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.base[Q.front]; Q.front = (Q.front+1)% MAXQSIZE; return OK;}∥∥∥∥––––––––––队列的链式存储构造队列的链式存储构造队列的链式存储构造队列的链式存储构造––––––––––typedef struct QNodetypedef struct QNode{QElemType data; {QElemType data; Struct QNode *next; Struct QNode *next; }QNode, *QueuePtr;}QNode, *QueuePtr;四、链式队列四、链式队列 ∧Q.frontQ.reartypedef struct{ QueuePtr front; ∥∥队头指针队头指针 QueuePtr rear; ∥∥队尾指针队尾指针}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的元素个数的元素个数,即为队列的长度即为队列的长度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;∥∥ 否那么前往否那么前往ERRORStatus QueueTraverse(LinkQueue Q,visit())∥∥ 从队头到队尾依次对队列从队头到队尾依次对队列Q中每个元素调用函中每个元素调用函数数visit().//一旦一旦visit失败失败,那么操作失败那么操作失败.Status InitQueue(LinkQueue &Q){∥∥ 构造一个空队列构造一个空队列.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if(!Q.front) exit(OVERFLOW); ∥∥存存储储分分配配失败失败Q.front->next = NULL;return OK;}∥∥∥∥––––––––––根本操作的算法描画根本操作的算法描画根本操作的算法描画根本操作的算法描画–––––––––– ∧∧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){∥∥假假设设队队列列不不空空,那那么么删删除除Q的的队队头头元元素素,用用e前前往往其值其值, ∥∥并前往并前往OK; 否那么前往否那么前往ERRORif(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;}。












