页数:91页文件大小:1.88 MB来源: 数据结构ppt课件
本课件为数据结构第三章栈和队列,先给出栈的顺序栈与链栈实现及进栈、出栈操作,结合数制转换、括号匹配、表达式求值等实例说明栈的应用与递归机制,随后讲解队列的顺序循环队列与链队列实现,并介绍离散事件模拟与迷宫求解等典型应用。
实例栈队列本章小结第三章栈和队列课后作业
1、停车场特点后进先出,便道特点先进先出2、如何存储3、数据操作:进场,出场停车场管理
Railway Switching Network
1234银行业务模拟
1234银行业务模拟
12341、其特点是先进先出2、如何存储3、数据操作:到达,离开,求队长等银行业务模拟
栈和队列是两种特殊的线性表是操作受限的线性表,称限定性数据结构限定插入和删除只能在表的“端点”进行的线性表ana1a2……......出栈进栈栈s=(a1,a2,…,an)a1 a2 ………….an入队出队frontrear队列Q=(a1,a2,……,an)
栈(stack)栈的逻辑结构栈的存储结构栈的应用
栈的定义和特点 定义:限定仅在表尾进行插入或删除操作的线性表,
ADTStack{数据对象:D={ ai| ai∈ElemSet, i=1,2,...,n, n≥0 }数据关系:R1={ <ai-1,ai>|ai-1,ai∈D, i=2,...,n }(约定an端为栈顶, a1端为栈底)抽象数据类型栈的定义基本操作:InitStack( &S);构造一个空栈SDestroyStack( &S);销毁栈SStackEmpty(S);判断栈S是否为空StackLength(S);返回栈S中元素个数ClearStack(&S);将栈S清为空栈Pop(&S, &e );用e出栈S的栈顶元素值GetTop(S, &e );用e返回栈S的栈顶元素Push(&S, e );插入e为栈S的新栈顶元素}ADTStack栈
双栈超栈双栈与超栈ana1a2……...栈顶......栈顶进栈进栈出栈出栈ana1a2……...栈顶......栈顶进栈出栈出栈栈
顺序栈链栈栈的存储结构栈
base—栈底指针,始终指向栈底的位置top—栈顶指针,指向实际栈顶后的空位置,初始指向栈底,即top=basetop123450入栈Atop出栈栈满BCDEF设栈容量为stacksize栈满—toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空top123450栈空basebasebasetop栈空—栈的存储结构——顺序栈top-base>=stacksizetop==base
#defineSTACK_INIT_SIZE 100//顺序栈存储空间的初始分配量#defineSTACKINCREMENT 10//顺序栈存储空间的分配增量typedefint SElemType;//元素类型typedefstruct{ SElemType *base;//栈底位置SElemType *top;//栈顶指针int stacksize;//当前分配的存储容量}SqStack;栈的动态分配顺序存储结构栈的存储结构——顺序栈构造一个空顺序栈S栈的基本操作在顺序栈中的实现
StatusInitStack(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;returnOK;}stacksizetopbaseSqStackS;stacksize-110动态申请顺序栈设置初始栈顶指针设置顺序栈容量base判断申请是否成功topT(n)=O(1)GetTop(){
if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}123450ABC 取栈顶元素S.topS.baseT(n)=O(1)StatusSqStackS,SElemType&e栈的成员是否改变??e=*(--S.top);?栈的基本操作在顺序栈中的实现判断是否栈空取栈顶元素顺序栈入栈入栈A初始容量满BCD设栈(初始)容量为S.stacksize栈满—S.top-S.base>=S.stacksize顺序栈入栈语句:S.baseS.topS.topS.topS.topS.top1230564* S.top++ =e;追加存储空间后,设置栈顶指针:追加存储空间:S.base = (SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof (SElemType));追加空间设置栈容量:( )S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;栈的基本操作在顺序栈中的实现
Push ( ){
if ( ){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;returnOK;}若栈满,追加存储空间判断是否成功入栈设置新的栈顶指针、栈容量T(n)=O(1)StatusSqStack&S,SElemTypeeS.top-S.base>=S.stacksize栈的成员是否改变??栈的基本操作在顺序栈中的实现Pop(){
if(S.top == S.base)returnERROR;e = *--S.top ;returnOK;} 顺序栈出栈123450ABC取栈顶元素:e=*(S.top-1);S.topS.base取栈顶元素:StatusGetTop(SqStackS, SElemType&e)T(n)=O(1)StatusSqStackS,SElemType&e&栈的成员是否改变??栈的基本操作在顺序栈中的实现判断是否栈空出栈栈顶元素ABCDE操作序列:出栈序列:
DE操作序列:出栈序列:
DE操作序列:出栈序列:
E操作序列:出栈序列:
0N+M-1栈1底栈1顶栈2底栈2顶 在一个程序中同时使用两个栈0M-1栈1底栈1顶栈2底栈2顶N-1栈的基本操作在顺序栈中的实现存储结构
anan-1...a2a1顺序栈栈底栈顶…h栈的链式存储anan-1a1^a2top栈的存储结构——链栈栈顶栈底链栈通常不需要头结点
typedefstruct Snode{ SElemTypedata;//数据域struct Snode*link;//指针域}LinkStack;链栈的操作是线性表的特例,比较易于实现链栈结点结构datalink栈顶^…...topdatalink栈底栈的存储结构——链栈存储结构栈的应用——具有“后进先出”特性的问题函数的嵌套调用递归的实现回文游戏递归函数汉诺塔问题多进制转换迷宫问题地图四染色表达式求值栈
main( ){ int m,n;. ……….first(m,n);①:…………..}
void first(int s, int t){ int i;second(i);②:…………}void second(int d){ int x,y;…………}栈的应用——函数的嵌套调用main( ){ int m,n;. ……….first(m,n);①:…………..}
void first(int s, int t){ int i;second(i);②:…………}void second(int d){ int x,y;…………}目标代码区静态数据区堆区运行栈区C程序编译的内存分配程序的二进制代码静态、全局变量编译器自动分配释放,存放函数的参数,局部变量值等用户动态申请栈的应用——函数的嵌套调用
main( ){ int m,n;. ……….first(m,n);①:…………..}
void first(int s, int t){ int i;second(i);②:…………}void second(int d){ int x,y;…………}main主程序firstmainmainmainfirst函数1mainfirstsecond函数2mainfirstsecond…m,n①,s,t,i②,d,x,y栈的应用——函数的嵌套调用栈的应用递归:函数直接或间接的调用自身叫~ 实现:建立递归工作栈从前有座山,山上有座庙,庙里有个老和尚,老和尚给小和尚讲故事,讲的是:从前有座山,山上有座庙,庙里有个老和尚,老和尚给小和尚讲故事,讲的是……栈的应用——递归过程及其实现
例递归的执行情况分析
voidprint(intw){ int i;if (w!=0){print(w-1);for(i=1;i<=w;++i)printf(“%3d,”,w);printf(“\n”);}}运行结果:1,2,2,3,3,3, 递归:函数直接或间接的调用自身叫~ 实现:建立递归工作栈栈的应用——递归过程及其实现递归的实现递归调用执行情况如下:主程序(1)print(w)w=3;3print(2);(1)w=3top(2)输出:3, 3, 3w2print(1);(2)w=2(1)w=3top(3)输出:2, 2w1print(0);(3)w=1(2)w=2(1)w=3top(4)输出:1w0(4)w=0(3)w=1(2)w=2(1)w=3topw(3)输出:2, 2(2) 2(1) 3top(4)输出:1(3) 1(2) 2(1) 3top(2)输出:3, 3, 3(1 ) 3top返回(3) 1(2) 2(1) 3top(4) 0结束(1)
voidprint(intw){ int i;if (w!=0){print(w-1);for(i=1;i<=w;++i)printf(“%3d,”,w);printf(“\n”); } }ABCTower of Hanoi栈的应用——递归的实现 问题描述:有A,B,C三个塔座,A上套有n个直径不同的圆盘,按直径从小到大叠放,形如宝塔,编号1,2,3……n。要求将n个圆盘从A移到C,叠放顺序不变,移动过程中遵循下列原则: 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻,每个塔座上不能将大盘压到小盘上相传在很久很久以前,在中东地区的一个寺庙里,几个和尚整天不停地移动着64个盘子,日复一日,年复一年,移盘不止。移盘的规则是:……。据说当所有64个盘子全部移完的那一天是世界的末日
ABCTower of Hanoi栈的应用——递归的实现 解决方法: n=1时,直接把圆盘从A移到C n>1时,先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题,依次类推,直至转化成只有一个圆盘的Hanoi问题
算法:
void hanoi(intn,charx,chary,charz)(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) }void move(inth, chars, charf){printf(“%d:%c->%c\n ”,h,s,f);}xyzTower of Hanoi栈的应用——递归的实现算法:
void hanoi(intn,charx,chary,charz)(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) }Tower of Hanoi栈的应用——递归的实现 执行情况: 递归工作栈保存内容:形参n,x,y,z和返回地址 返回地址用行编号表示n x y z返回地址算法演示算法:
void hanoi(intn,charx,chary,charz)(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) }Tower of Hanoi栈的应用——递归的实现 执行情况: 递归工作栈保存内容:形参n,x,y,z和返回地址 返回地址用行编号表示n x y z返回地址算法演示n个盘子需要移动次,64个盘子大约需。假设每秒移动一次,约需一万亿年;一微秒一次,约需一百万年栈的应用顺读与逆读字符串一样dadtop1.读入字符串2.去掉空格(原串)3.压入栈4.出栈字符与原串字符依次比较若不等,非回文若直到栈空都相等,回文字符串:“madam im adam”topadamimadamtoptoptoptoptoptoptoptoptoptoptopm回文有趣的对联客上天然居居然天上客人过大钟寺寺钟大过人字符串:“madamimadam”madamimadam字符串:“dad”栈的应用——回文栈的应用
例把十进制数159转换成八进制数(159)10=(237)815981982807余7余3余232top32toptoptop7237(159)10=( )8栈的应用——多进制转换栈的应用原理:
中缀表达式求值:操作数栈和运算符栈 编译程序自左向右扫描至语句结束符:
+-*/()#+-*/()#>><<<>>>>>><>><<<<<=>>>>>><<<<<=>><<<>>>>>><>> 1 2栈顶当前若栈顶运算符优先级低,当前运算符入栈;若栈顶运算符优先级相同或较大,则栈顶运算符出栈栈的应用——表达式求值算符优先级2 + 5 + 3S.top52#+T.top当前运算符为(,一律入栈当前运算符为),一律出栈栈顶运算符当(与)或#与#相遇时,代表括号里或表达式运算完毕栈顶运算符为(时,当前运算符一律入栈栈顶运算符为)时,)一律出栈栈顶运算符为#时,当前运算符一律入栈当前运算符为#时,栈顶运算符一律出栈)与(、#与)、(与#不会相继出现,否则语法错误
例计算2*(1+3)-4/2#操作数运算符#2*(1+3)-4/2#*2(1+3T.topS.topT.topS.topT.topT.topS.topT.topS.top48-/226=6栈的应用——表达式求值
接收下一个字符=>c接收下一个字符=>c结果入操作数栈接收下一个字符=>c开始构造运算符栈和操作数栈将#入运算符栈接收表达式中的字符=>cc!=‘#’或运算符栈顶不是‘#’c是运算符?判断栈顶运算符与c的优先级将c入操作数栈出栈并运算脱括号c入运算符栈是是否结束否<=>栈的应用——表达式求值
SElemTypeEvaluateExpression( ){SqStackOPTR,OPND;S
ElemType c,x,a,b,theta;InitStack(OPTR);Push(OPTR,'#');InitStack(OPND);c=getchar();while(c!='#' ||GetTop(OPTR)!='#'){if(!InOP(c)){Push(OPND,c);c=getchar();}……定义运算符栈和操作数栈若c不是运算符当前或栈顶运算符不为#时StatusInOP(SElemType c){char Operators[]={'+','-','*','/','(',')','#','\0'};int len=strlen(Operators);for(int i=0;i<len;i++)if(c==Operators[i])returnTRUE;returnFALSE;}将c入操作数栈,取表达式中下一个字符栈的应用——表达式求值……else{switch(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;}}}returnGetTop(OPND);}判断栈顶运算符与c的优先级操作数栈顶为计算结果若c是运算符栈的应用——表达式求值栈顶运算符优先级低,当前运算符c入栈优先级相等,脱括号栈顶运算符优先级高,出栈运算符计算
SElemTypePrecede(S
ElemTypecurtop,SElemTypeinput){SElemType order;switch(input){case '+':case '-': switch(curtop){case '+': case '-': case '*':case '/':case ')':order='>';break;case '(':case '#':order='<';break;}break;……栈的应用——表达式求值case '*':case '/': switch(curtop){case '+': case '-': case '(':case '#':order='<';break;case '*':case '/':case ')':order='>';break;}break;case '(': switch(curtop){case '+':case '-':case '*':case '/':case '(':case '#':order='<';break;}break;……栈的应用——表达式求值
case ')':switch(curtop){case '+': case '-': case '*': case '/': case ‘)':order=‘>';break;case ‘(':order=‘=';break;}break;case '#': switch(curtop){case '+': case '-':case '*':case '/': case ')':order='>';break;case '#':order='=';break;}break;}returnorder;}栈的应用——表达式求值
后缀表达式:213+*42/-2S.topS.top1S.topS.top3484226=6例计算2 * ( 1 + 3 )–4 / 2 后缀表达式求值:只需要操作数栈 编译程序自左向右扫描至表达式结束:
a + b * c + ( d * e + f ) * g将表达式转换成后缀表达式 栈的应用——表达式求值(后缀表达式)课后作业d e *f+b c *d e * f +g*ab c *+a b c * +d e * f + g *+abc*+de*f+g*+中缀=>后缀操作数的顺序不变
a + b * c + ( d * e + f ) * g*a+b运算符栈后缀表达式:c*+将表达式转换成后缀表达式##
a + b * c + ( d * e + f ) * gab运算符栈后缀表达式:c*+将表达式转换成后缀表达式需要的函数de*f+g*+ 栈的应用——表达式求值(后缀表达式)结束课后作业abc*+de*f+g*+中缀=>后缀操作数的顺序不变建立顺序栈入栈出栈取栈顶元素判断是否是运算符判断栈空运算符优先级比较栈的应用
紫色黄色红色绿色栈栈的应用——地图四染色问题
R [ 7][ 7 ]1 2 3 4 5 6 71234567100 0 0 1 001 1 1 1 1 010101 1 0101 101 01 101 1001001 1 0 00 0 0 0 0 001223414334231#紫色2#黄色3#红色4#绿色回溯法ABDEFGC7654321栈的应用——地图四染色问题栈的应用
寻找一条从入口到出口的通路。8123456781234567前进方向:上(北)、下(南)、左(西)、右(东)东南北西 走步规则:首先从向下开始,按照逆时针方向搜索下一步可能前进的位置入口出口栈的应用——迷宫问题
栈8123456781234567(1,1)i(2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i东南北西栈的应用——迷宫问题
栈8123456781234567(1,1)i(2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i@@(5,2)i(5,3)i(6,3)i(6,4)i…(8,8)iiiiii东南北西栈的应用——迷宫问题
栈的应用——皇后问题栈的应用
队列(Queue)队列的逻辑结构队列的存储结构队列的应用
队列的定义及特点 定义:队列是限定只能在表的一端进行插入,在表的另一端进行删除的线性表入队出队frontreara1 a2 a3…………………….an队列Q=(a1,a2,……,an)队列的逻辑结构
ADTQueue{数据对象:D={ ai| ai∈ElemSet, i=1,2,...,n, n≥0 }数据关系:R1={ <ai-1,ai>|ai-1,ai∈D, i=2,...,n }(约定a1端为队头,an端为队尾)基本操作:InitQueue( &Q);构造一个空队列QDestroyQueue( &Q);销毁队列QQueueEmpty(Q);判断队列Q是否为空QueueLength(Q);返回队列Q中元素个数ClearQueue(&Q);将队列Q清为空队列DeQueue(&Q, &e );出队GetHead(Q, &e );取队列Q的队头元素EnQueue(&Q, e );元素e入队}ADTQueue抽象数据类型队列的定义
双端队列与超队列a1 a2 a3…………………….an端1端2入队出队出队入队双端队列a1 a2 a3…………………….an端1端2超队列入队入队出队队列
队列的存储结构链队列顺序队列队列
…a1a2an^ai…a1a2… ai… an队头front队尾rear出队入队front队头队尾设队首、队尾指针front和rear,front指向头结点,rear指向队尾rear^frontrear队列的存储结构——链队列
…a1a2an^ai…front队头队尾rear
typedefstruct Qnode{ QElemType data;//数据域struct Qnode *link;//指针域}QNode, *QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;结点结构链队列结构LinkQueueQ;Q.frontQ.rear队列的存储结构——链队列InitQueue ( ){(QueuePtr)
malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->link= NULL;returnOK;} 构造空链队列Q建立链队列头结点判断分配是否成功T(n)=O(1)Q.frontQ.rear∧StatusLinkQueue&QQ.front=Q.rear=LinkQueueQ;链队列的基本操作设置头结点指针域链队列入队^Q.frontQ.reara1p^a2p^Q.rear->link=p;Q.rear=p;EnQueue( ){QueuePtr p;p = (QueuePtr)
malloc (sizeof (QNode));if(!p)exit(OVERFLOW);p->data = e; p->link= NULL;Q.rear->link = p;Q.rear = p;returnOK;}生成新结点判断分配是否成功新结点赋值入队T(n)=O(1)StatusLinkQueue&Q,QElemTypee链队列的基本操作Q.front、Q.rear如何改变?链队列出队^Q.frontQ.reara1p^a2p^p=Q.front->link;Q.front->link=p->link;DeQueue ( ){ QueuePtr p;
if(Q.front == Q.rear)returnERROR;p = Q.front->link;Q.front->link = p->link;if (Q.rear == p) Q.rear = Q.front;free (p);returnOK;}StatusLinkQueue&Q,QElemType&e判断队列是否为空e=p->data;^链队列的基本操作Q.front、Q.rear如何改变?出队出队结点是否是最后结点T(n)=O(1)…a1a2anai…Q.frontQ.rear^^
StatusDestroyQueue (LinkQueue&Q){while(Q.front){ Q.rear= Q.front->link;free(Q.front);Q.front=Q.rear;}returnOK;}Q.rear=Q.front->link; 销毁链队列free(Q.front);Q.front=Q.rear;T(n)=O(n)当Q.front不为空时,进行销毁^链队列的基本操作每次销毁Q.front指向的结点队列存储Q.rear123450Q.front入队J1溢出J2J3J4J5J6Q.rearQ.rearQ.rearQ.rearQ.rearQ.rear真SqQueueQ;
#defineMAXQSIZE 100//最大队列长度typedefstruct{ QElemType *base;//存储空间基址intfront;//头指针,指向队头元素intrear;//尾指针,指向队尾元素的下一个位置}SqQueue;顺序队列存储结构初值:Q.front=Q.rear=0;队空:入队:真溢出条件:Q.base[Q.rear++]=e;Q.front==0;Q.rear==MAXQSIZE;Q.front==Q.rear;Q.base队列的存储结构——顺序队列SqQueueQ;顺序队列存储结构出队:假溢出条件:e=Q.base[Q.front++];123450Q.front出队J1J2J3J4J5J6Q.rearQ.frontQ.frontQ.front溢出假Q.front 0;Q.rear==MAXQSIZE;
#defineMAXQSIZE 100//最大队列长度typedefstruct{ QElemType *base;//存储空间基址intfront;//头指针,指向队头元素intrear;//尾指针,指向队尾元素的下一个位置}SqQueue;Q.base队列的存储结构——顺序队列方案一:队首固定,每次出队,剩余元素下移123450Q.frontJ1出队J1J2J3J4Q.rear真溢出条件:Q.front==0;Q.rear==MAXQSIZE;假溢出条件:Q.front 0;Q.rear==MAXQSIZE; 假溢出问题解决方案Q.rear队列的存储结构——顺序队列
123450Q.frontJ2出队J2J3J4Q.rearQ.rear缺点:浪费时间方案一:队首固定,每次出队,剩余元素下移 假溢出问题解决方案真溢出条件:Q.front==0;Q.rear==MAXQSIZE;假溢出条件:Q.front 0;Q.rear==MAXQSIZE;队列的存储结构——顺序队列
方案二:循环队列,把队列设想成环形,首尾相接,若Q.rear==MAXSIZE,则令Q.rear=0J4J5J6012345Q.rearQ.front实现:利用"模"运算 假溢出问题解决方案?真溢出条件:Q.front==0;Q.rear==MAXQSIZE;假溢出条件:Q.front 0;Q.rear==MAXQSIZE;J4J5J6123450Q.frontQ.rearQ.rear队列的存储结构——顺序队列
方案二:循环队列,把队列设想成环形,首尾相接,若Q.rear==MAXSIZE,则令Q.rear=0J4J5J6012345Q.rearQ.front实现:利用"模"运算 假溢出问题解决方案?“模”运算x%MAXSIZE——结果范围为0~(MAXSIZE-1)则,(x+1)%MAXSIZE可实现
利用"模"运算实现循环队列J8J9Q.rearQ.frontJ7Q.rearJ4J5J6450123Q.rear初始状态J7,J8,J9相继入队Q.frontJ4J5J6450123Q.rear循环队列入队:队满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;Q.rear队列的存储结构——循环队列
利用"模"运算实现循环队列J8J9Q.frontJ7J4J5J6450123初始状态J7,J8,J9相继入队Q.frontJ4J5J6450123Q.rearQ.rear队满J4,J5,J6相继出队Q.frontJ4J5J6450123Q.rearQ.frontQ.frontQ.front队空循环队列出队:e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;队列的存储结构——循环队列
利用"模"运算实现循环队列J8J9Q.frontJ7J4J5J6450123初始状态J7,J8,J9相继入队Q.frontJ4J5J6450123Q.rearQ.rear队满J4,J5,J6相继出队450123Q.rearQ.front队空循环队列中:队空条件:Q.front==Q.rear队满条件:Q.front==Q.rear?解决方案:1.设一个标志区分队空、队满2.少用一个元素空间:队列的存储结构——循环队列
利用"模"运算实现循环队列J8Q.frontJ7J4J5J6450123初始状态J7,J8,J9相继入队Q.frontJ4J5J6450123Q.rearQ.rear队满J4,J5,J6相继出队450123Q.rearQ.front队空解决方案:1.设一个标志区分队空、队满2.少用一个元素空间:队空:Q.front==Q.rear队满:(Q.rear+1)%MAXQSIZE==Q.front队列的存储结构——循环队列
构造空的循环队列Q:
#defineMAXQSIZE 100//最大队列长度typedefstruct{ QElemType *base;//存储空间基址intfront;//头指针,指向队头元素intrear;//尾指针,指向队尾元素的下一个位置}SqQueue;顺序队列存储结构循环队列的基本操作InitQueue( ){}T(n)=O(1)MAXQSIZE-110…………Q.frontQ.rearQ.base=(QElemType *)
malloc(MAXQSIZE *sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;return(OK);Q.base 构造空的循环队列Q:StatusSqQueue&Q申请存储空间判断分配是否成功设置队头和队尾指针循环队列的基本操作求循环队列中元素个数:J4J5J6450123Q.rearQ.frontJ7J4J6J5450123Q.frontQ.rearJ7T(n)=O(1)intQueueLength(SqQueueQ){}
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;循环队列的基本操作循环队列入队:EnQueue ( ){
if((Q.rear+1) % MaxQSize == Q.front)returnERROR;Q.base[Q.rear] = e;Q.rear = (Q.rear+1) % MaxQSize;returnOK;}T(n)=O(1)J8Q.rearQ.frontJ7Q.rearQ.rear队满J4J5J6450123StatusSqQueue&Q,QElemTypee是否队满入队修改队尾指针循环队列的基本操作循环队列出队:T(n)=O(1)DeQueue ( ){
if(Q.front == Q.rear)returnERROR;e = Q.base[Q.front];Q.front = (Q.front+1) % MaxQSize;returnOK;}Q.frontJ4J5J6450123Q.rearQ.frontQ.frontQ.front队空StatusSqQueue&Q,QElemType&e是否队空出队修改队头指针循环队列的基本操作队列存储划分子集问题优先级队列离散事件模拟作业调度图的广度优先遍历农夫过河问题队列的应用迷宫问题
掌握栈和队列的基本概念本章小结掌握栈和队列的顺序存储结构、链式存储结构及基本操作的实现(包括相应的算法)和栈的应用算法了解双栈、双端队列等特殊的数据结构
课后作业非编程作业:1.若进栈序列为ABCD,请给出全部可能的出栈序列和不可能的出栈序列。2.简要说明循环队列如何判断队满和队空?编程作业:1.栈采用顺序栈存储,试设计算法实现将表达式转换成后缀表达式输出。例如,输入表达式:a+b/c-(d*e+f)*g输出其后缀表达式:abc/+de*f+g*-
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}