首页计算机计算机基础数据结构 03 第三章 栈和队列.pptx

03 第三章 栈和队列.pptx

页数:91页文件大小:1.88 MB来源: 数据结构ppt课件

本课件为数据结构第三章栈和队列,先给出栈的顺序栈与链栈实现及进栈、出栈操作,结合数制转换、括号匹配、表达式求值等实例说明栈的应用与递归机制,随后讲解队列的顺序循环队列与链队列实现,并介绍离散事件模拟与迷宫求解等典型应用。

第三章栈和队列目录页,列出栈和队列实例、逻辑结构、存储结构与应用举例
停车场管理实例页,说明停车场的后进先出与便道的先进先出两种存储与操作特点
铁路调度网示意图,展示列车车厢经调度轨进出所形成的栈式结构
查看本课件的文字版(共 91 页,供检索与复制)

第1页:第三章栈和队列目录

实例栈队列本章小结第三章栈和队列课后作业

第2页:实例:停车场管理

1、停车场特点后进先出,便道特点先进先出2、如何存储3、数据操作:进场,出场停车场管理

第3页:实例:铁路调度网

Railway Switching Network

第4页:实例:银行业务模拟(一)

1234银行业务模拟

第5页:实例:银行业务模拟(二)

1234银行业务模拟

第6页:银行业务模拟的队列特点

12341、其特点是先进先出2、如何存储3、数据操作:到达,离开,求队长等银行业务模拟

第7页:栈和队列是操作受限的线性表

栈和队列是两种特殊的线性表是操作受限的线性表,称限定性数据结构限定插入和删除只能在表的“端点”进行的线性表ana1a2……......出栈进栈栈s=(a1,a2,…,an)a1 a2 ………….an入队出队frontrear队列Q=(a1,a2,……,an)

第8页:栈的内容框架

栈(stack)栈的逻辑结构栈的存储结构栈的应用

第9页:栈的定义和特点

栈的定义和特点 定义:限定仅在表尾进行插入或删除操作的线性表,

表尾
栈顶,
表头
栈底,不含元素的空表称空栈 特点:先进后出(FILO)或后进先出(LIFO)ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an) 栈的运算:置空栈取栈顶元素判空栈进栈出栈栈的逻辑结构

第10页:栈的抽象数据类型定义

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栈

第11页:双栈与超栈

双栈超栈双栈与超栈ana1a2……...栈顶......栈顶进栈进栈出栈出栈ana1a2……...栈顶......栈顶进栈出栈出栈栈

第12页:顺序栈与链栈

顺序栈链栈栈的存储结构栈

第13页:顺序栈的栈顶与栈底指针

base—栈底指针,始终指向栈底的位置top—栈顶指针,指向实际栈顶后的空位置,初始指向栈底,即top=basetop123450入栈Atop出栈栈满BCDEF设栈容量为stacksize栈满—toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空top123450栈空basebasebasetop栈空—栈的存储结构——顺序栈top-base>=stacksizetop==base

第14页:顺序栈存储结构定义

#defineSTACK_INIT_SIZE 100//顺序栈存储空间的初始分配量#defineSTACKINCREMENT 10//顺序栈存储空间的分配增量typedefint SElemType;//元素类型typedefstruct{ SElemType *base;//栈底位置SElemType *top;//栈顶指针int stacksize;//当前分配的存储容量}SqStack;栈的动态分配顺序存储结构栈的存储结构——顺序栈

第15页:构造一个空顺序栈

构造一个空顺序栈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)

第16页:取栈顶元素

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);?栈的基本操作在顺序栈中的实现判断是否栈空取栈顶元素

第17页:顺序栈入栈示意

顺序栈入栈入栈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;栈的基本操作在顺序栈中的实现

第18页:入栈算法Push

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栈的成员是否改变??栈的基本操作在顺序栈中的实现

第19页:顺序栈出栈

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&栈的成员是否改变??栈的基本操作在顺序栈中的实现判断是否栈空出栈栈顶元素

第20页:出栈序列判断(一)

ABCDE操作序列:出栈序列:

  • 元素A入栈AA
  • 元素B入栈BB
  • 元素C入栈CC 能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE?栈的基本操作在顺序栈中的实现

第21页:出栈序列判断(二)

DE操作序列:出栈序列:

  • 元素A入栈A
  • 元素B入栈B
  • 元素C入栈
  • 元素C出栈CC
  • 元素B出栈B 能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE?栈的基本操作在顺序栈中的实现

第22页:出栈序列判断(三)

DE操作序列:出栈序列:

  • 元素A入栈A
  • 元素B入栈
  • 元素C入栈
  • 元素C出栈C
  • 元素B出栈B
  • 元素D入栈DD
  • 元素D出栈D
  • 元素A出栈A 能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE?栈的基本操作在顺序栈中的实现

第23页:出栈序列判断(四)

E操作序列:出栈序列:

  • 元素A入栈
  • 元素B入栈
  • 元素C入栈
  • 元素C出栈C
  • 元素B出栈B
  • 元素D入栈
  • 元素D出栈D
  • 元素A出栈A
  • 元素E入栈EE
  • 元素E出栈E 能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE?可以得到按1,2,3,4顺序进栈,有几种出栈序列?栈的基本操作在顺序栈中的实现

第24页:两个栈共享存储空间

0N+M-1栈1底栈1顶栈2底栈2顶 在一个程序中同时使用两个栈0M-1栈1底栈1顶栈2底栈2顶N-1栈的基本操作在顺序栈中的实现存储结构

第25页:链栈的存储示意

anan-1...a2a1顺序栈栈底栈顶…h栈的链式存储anan-1a1^a2top栈的存储结构——链栈栈顶栈底链栈通常不需要头结点

第26页:链栈的结点定义

typedefstruct Snode{ SElemTypedata;//数据域struct Snode*link;//指针域}LinkStack;链栈的操作是线性表的特例,比较易于实现链栈结点结构datalink栈顶^…...topdatalink栈底栈的存储结构——链栈存储结构

第27页:栈的应用:后进先出问题

栈的应用——具有“后进先出”特性的问题函数的嵌套调用递归的实现回文游戏递归函数汉诺塔问题多进制转换迷宫问题地图四染色表达式求值栈

第28页:函数的嵌套调用

main( ){ int m,n;. ……….first(m,n);①:…………..}

void first(int s, int t){ int i;second(i);②:…………}void second(int d){ int x,y;…………}栈的应用——函数的嵌套调用

第29页:函数调用与栈的信息传递

  • 当函数调用另一函数时,编译系统需要:①将返回地址及实参等信息,传递给被调用函数保存;②为被调用函数局部变量分配存储区;③将控制权转移到被调用函数入口;栈的应用——函数的嵌套调用
  • 从被调用函数返回到调用函数时,编译系统需要:①保存被调用函数计算结果;②释放被调用函数的数据区;③依照保存的返回地址将控制权转移到调用函数。
  • 函数之间信息传递和控制转移必须通过“栈”来实现。

第30页: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;…………}目标代码区静态数据区堆区运行栈区C程序编译的内存分配程序的二进制代码静态、全局变量编译器自动分配释放,存放函数的参数,局部变量值等用户动态申请栈的应用——函数的嵌套调用

第31页:函数调用栈的变化

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栈的应用——函数的嵌套调用栈的应用

第32页:递归的定义与实现

递归:函数直接或间接的调用自身叫~ 实现:建立递归工作栈从前有座山,山上有座庙,庙里有个老和尚,老和尚给小和尚讲故事,讲的是:从前有座山,山上有座庙,庙里有个老和尚,老和尚给小和尚讲故事,讲的是……栈的应用——递归过程及其实现

第33页:递归执行情况分析

例递归的执行情况分析

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, 递归:函数直接或间接的调用自身叫~ 实现:建立递归工作栈栈的应用——递归过程及其实现递归的实现

第34页:递归调用执行过程

递归调用执行情况如下:主程序(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”); } }

第35页:汉诺塔问题描述

ABCTower of Hanoi栈的应用——递归的实现 问题描述:有A,B,C三个塔座,A上套有n个直径不同的圆盘,按直径从小到大叠放,形如宝塔,编号1,2,3……n。要求将n个圆盘从A移到C,叠放顺序不变,移动过程中遵循下列原则: 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻,每个塔座上不能将大盘压到小盘上相传在很久很久以前,在中东地区的一个寺庙里,几个和尚整天不停地移动着64个盘子,日复一日,年复一年,移盘不止。移盘的规则是:……。据说当所有64个盘子全部移完的那一天是世界的末日

第36页:汉诺塔问题的解决方法

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问题

第37页:汉诺塔算法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栈的应用——递归的实现

第38页:汉诺塔递归工作栈

算法:

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返回地址算法演示

第39页:汉诺塔的移动次数

算法:

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个盘子大约需。假设每秒移动一次,约需一万亿年;一微秒一次,约需一百万年栈的应用

第40页:回文判断

顺读与逆读字符串一样dadtop1.读入字符串2.去掉空格(原串)3.压入栈4.出栈字符与原串字符依次比较若不等,非回文若直到栈空都相等,回文字符串:“madam im adam”topadamimadamtoptoptoptoptoptoptoptoptoptoptopm回文有趣的对联客上天然居居然天上客人过大钟寺寺钟大过人字符串:“madamimadam”madamimadam字符串:“dad”栈的应用——回文栈的应用

第41页:多进制转换

例把十进制数159转换成八进制数(159)10=(237)815981982807余7余3余232top32toptoptop7237(159)10=( )8栈的应用——多进制转换栈的应用原理:

第42页:表达式的三种标识方法

中缀表达式
运算符放在两个运算对象之间; 程序设计语言编译中的一个基本问题 表达式的三种标识方法:a*b+ca+b*ca+(b*c+d)/eab*c+abc*+abc*d+e/+中缀表达式后缀表达式
后缀表达式
不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先级);
前缀表达式
同后缀表达式一样,不包含括号,运算符在两个运算对象前面。后缀表达式中操作数的顺序不变栈的应用——表达式求值

第43页:中缀表达式求值

中缀表达式求值:操作数栈和运算符栈 编译程序自左向右扫描至语句结束符:

  • 凡遇到操作数,一律进操作数栈;
  • 遇到运算符时,将当前运算符与栈顶运算符的优先级相比。若当前运算符的优先级相同或较小,取出栈顶运算符,并在操作数栈中连续取出两个操作数进行运算,将结果存入操作数栈;反之(当前运算符优先级较大),则进栈。例计算2+4-3*6S.top4S.topS.top2T.topT.top+6-3*T.top6S.top18-12=-12-+-××+栈的应用——表达式求值

第44页:算符优先级表

+-*/()#+-*/()#>><<<>>>>>><>><<<<<=>>>>>><<<<<=>><<<>>>>>><>> 1 2栈顶当前若栈顶运算符优先级低,当前运算符入栈;若栈顶运算符优先级相同或较大,则栈顶运算符出栈栈的应用——表达式求值算符优先级2 + 5 + 3S.top52#+T.top当前运算符为(,一律入栈当前运算符为),一律出栈栈顶运算符当(与)或#与#相遇时,代表括号里或表达式运算完毕栈顶运算符为(时,当前运算符一律入栈栈顶运算符为)时,)一律出栈栈顶运算符为#时,当前运算符一律入栈当前运算符为#时,栈顶运算符一律出栈)与(、#与)、(与#不会相继出现,否则语法错误

第45页:中缀表达式求值示例

例计算2*(1+3)-4/2#操作数运算符#2*(1+3)-4/2#*2(1+3T.topS.topT.topS.topT.topT.topS.topT.topS.top48-/226=6栈的应用——表达式求值

第46页:表达式求值流程

接收下一个字符=>c接收下一个字符=>c结果入操作数栈接收下一个字符=>c开始构造运算符栈和操作数栈将#入运算符栈接收表达式中的字符=>cc!=‘#’或运算符栈顶不是‘#’c是运算符?判断栈顶运算符与c的优先级将c入操作数栈出栈并运算脱括号c入运算符栈是是否结束否<=>栈的应用——表达式求值

第47页:表达式求值算法(一)

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入操作数栈,取表达式中下一个字符栈的应用——表达式求值

第48页:表达式求值算法(二)

……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入栈优先级相等,脱括号栈顶运算符优先级高,出栈运算符计算

第49页:优先级比较函数Precede(一)

SElemTypePrecede(S

ElemTypecurtop,SElemTypeinput){SElemType order;switch(input){case '+':case '-': switch(curtop){case '+': case '-': case '*':case '/':case ')':order='>';break;case '(':case '#':order='<';break;}break;……栈的应用——表达式求值

第50页:优先级比较函数Precede(二)

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;……栈的应用——表达式求值

第51页:优先级比较函数Precede(三)

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;}栈的应用——表达式求值

第52页:后缀表达式求值步骤

  • 读入表达式一个字符
  • 若是操作数,入栈,转
  • 若是运算符,从栈中出栈2个操作数进行运算,将运算结果入栈,转
  • 若表达式未输入完,转
  • ;若表达式输入完毕,栈顶即表达式值 后缀表达式求值:只需要操作数栈 编译程序自左向右扫描至表达式结束:例计算2 * ( 1 + 3 )–4 / 221 3 +*-4 2 /1 3 +2 1 3 + *4 2 /栈的应用——表达式求值

第53页:后缀表达式求值示例

后缀表达式:213+*42/-2S.topS.top1S.topS.top3484226=6例计算2 * ( 1 + 3 )–4 / 2 后缀表达式求值:只需要操作数栈 编译程序自左向右扫描至表达式结束:

  • 读入表达式一个字符
  • 若是操作数,入栈,转
  • 若是运算符,从栈中出栈2个操作数进行运算,将运算结果入栈,转
  • 若表达式未输入完,转
  • ;若表达式输入完毕,栈顶即表达式值栈的应用——表达式求值

第54页:中缀转后缀示例

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*+中缀=>后缀操作数的顺序不变

第55页:中缀转后缀算法步骤

a + b * c + ( d * e + f ) * g*a+b运算符栈后缀表达式:c*+将表达式转换成后缀表达式##

若当前字符是操作数
则直接发送给后缀式
若当前字符是运算符
若当前运算符的优先数高于栈顶运算符,则进栈否则,出栈栈顶运算符发送给后缀式转换算法步骤:依次读入中缀表达式字符+(de**+f+*g*+# 栈的应用——表达式求值(后缀表达式)结束课后作业abc*+de*f+g*+中缀=>后缀操作数的顺序不变

第56页:中缀转后缀所需函数

a + b * c + ( d * e + f ) * gab运算符栈后缀表达式:c*+将表达式转换成后缀表达式需要的函数de*f+g*+ 栈的应用——表达式求值(后缀表达式)结束课后作业abc*+de*f+g*+中缀=>后缀操作数的顺序不变建立顺序栈入栈出栈取栈顶元素判断是否是运算符判断栈空运算符优先级比较栈的应用

第57页:地图四染色:颜色

紫色黄色红色绿色栈栈的应用——地图四染色问题

第58页:地图四染色:回溯法

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栈的应用——地图四染色问题栈的应用

第59页:迷宫问题

寻找一条从入口到出口的通路。8123456781234567前进方向:上(北)、下(南)、左(西)、右(东)东南北西 走步规则:首先从向下开始,按照逆时针方向搜索下一步可能前进的位置入口出口栈的应用——迷宫问题

第60页:迷宫求解过程(一)

栈8123456781234567(1,1)i(2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i东南北西栈的应用——迷宫问题

第61页:迷宫求解过程(二)

栈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东南北西栈的应用——迷宫问题

第62页:皇后问题

栈的应用——皇后问题栈的应用

第63页:队列的内容框架

队列(Queue)队列的逻辑结构队列的存储结构队列的应用

第64页:队列的定义及特点

队列的定义及特点 定义:队列是限定只能在表的一端进行插入,在表的另一端进行删除的线性表入队出队frontreara1 a2 a3…………………….an队列Q=(a1,a2,……,an)队列的逻辑结构

队尾(rear)
允许插入的一端
队头(front)
允许删除的一端 队列特点:先进先出(FIFO)

第65页:队列的抽象数据类型定义

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抽象数据类型队列的定义

第66页:双端队列与超队列

双端队列与超队列a1 a2 a3…………………….an端1端2入队出队出队入队双端队列a1 a2 a3…………………….an端1端2超队列入队入队出队队列

第67页:队列的存储结构

队列的存储结构链队列顺序队列队列

第68页:链队列的存储示意

…a1a2an^ai…a1a2… ai… an队头front队尾rear出队入队front队头队尾设队首、队尾指针front和rear,front指向头结点,rear指向队尾rear^frontrear队列的存储结构——链队列

第69页:链队列的结点定义

…a1a2an^ai…front队头队尾rear

typedefstruct Qnode{ QElemType data;//数据域struct Qnode *link;//指针域}QNode, *QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;结点结构链队列结构LinkQueueQ;Q.frontQ.rear队列的存储结构——链队列

第70页:构造空链队列

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;链队列的基本操作设置头结点指针域

第71页:链队列入队

链队列入队^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如何改变?

第72页:链队列出队

链队列出队^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)

第73页:销毁链队列

…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指向的结点队列存储

第74页:顺序队列的存储结构

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队列的存储结构——顺序队列

第75页:顺序队列的出队与假溢出

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队列的存储结构——顺序队列

第76页:假溢出解决方案一

方案一:队首固定,每次出队,剩余元素下移123450Q.frontJ1出队J1J2J3J4Q.rear真溢出条件:Q.front==0;Q.rear==MAXQSIZE;假溢出条件:Q.front 0;Q.rear==MAXQSIZE; 假溢出问题解决方案Q.rear队列的存储结构——顺序队列

第77页:方案一的缺点

123450Q.frontJ2出队J2J3J4Q.rearQ.rear缺点:浪费时间方案一:队首固定,每次出队,剩余元素下移 假溢出问题解决方案真溢出条件:Q.front==0;Q.rear==MAXQSIZE;假溢出条件:Q.front 0;Q.rear==MAXQSIZE;队列的存储结构——顺序队列

第78页:假溢出解决方案二:循环队列

方案二:循环队列,把队列设想成环形,首尾相接,若Q.rear==MAXSIZE,则令Q.rear=0J4J5J6012345Q.rearQ.front实现:利用"模"运算 假溢出问题解决方案?真溢出条件:Q.front==0;Q.rear==MAXQSIZE;假溢出条件:Q.front 0;Q.rear==MAXQSIZE;J4J5J6123450Q.frontQ.rearQ.rear队列的存储结构——顺序队列

第79页:模运算实现循环队列

方案二:循环队列,把队列设想成环形,首尾相接,若Q.rear==MAXSIZE,则令Q.rear=0J4J5J6012345Q.rearQ.front实现:利用"模"运算 假溢出问题解决方案?“模”运算x%MAXSIZE——结果范围为0~(MAXSIZE-1)则,(x+1)%MAXSIZE可实现

  • x加1
  • 满足范围要求J4J5J6123450Q.frontQ.rear队列的存储结构——顺序队列

第80页:循环队列入队

利用"模"运算实现循环队列J8J9Q.rearQ.frontJ7Q.rearJ4J5J6450123Q.rear初始状态J7,J8,J9相继入队Q.frontJ4J5J6450123Q.rear循环队列入队:队满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;Q.rear队列的存储结构——循环队列

第81页:循环队列出队

利用"模"运算实现循环队列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;队列的存储结构——循环队列

第82页:队空与队满的判断

利用"模"运算实现循环队列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.少用一个元素空间:队列的存储结构——循环队列

第83页:队空队满的解决方案

利用"模"运算实现循环队列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队列的存储结构——循环队列

第84页:循环队列存储结构定义

构造空的循环队列Q:

#defineMAXQSIZE 100//最大队列长度typedefstruct{ QElemType *base;//存储空间基址intfront;//头指针,指向队头元素intrear;//尾指针,指向队尾元素的下一个位置}SqQueue;顺序队列存储结构循环队列的基本操作

第85页:构造空的循环队列

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申请存储空间判断分配是否成功设置队头和队尾指针循环队列的基本操作

第86页:求循环队列长度

求循环队列中元素个数:J4J5J6450123Q.rearQ.frontJ7J4J6J5450123Q.frontQ.rearJ7T(n)=O(1)intQueueLength(SqQueueQ){}

return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;循环队列的基本操作

第87页:循环队列入队算法

循环队列入队: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是否队满入队修改队尾指针循环队列的基本操作

第88页:循环队列出队算法

循环队列出队: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是否队空出队修改队头指针循环队列的基本操作队列存储

第89页:队列的应用

划分子集问题优先级队列离散事件模拟作业调度图的广度优先遍历农夫过河问题队列的应用迷宫问题

第90页:本章小结

掌握栈和队列的基本概念本章小结掌握栈和队列的顺序存储结构、链式存储结构及基本操作的实现(包括相应的算法)和栈的应用算法了解双栈、双端队列等特殊的数据结构

第91页:课后作业

课后作业非编程作业:1.若进栈序列为ABCD,请给出全部可能的出栈序列和不可能的出栈序列。2.简要说明循环队列如何判断队满和队空?编程作业:1.栈采用顺序栈存储,试设计算法实现将表达式转换成后缀表达式输出。例如,输入表达式:a+b/c-(d*e+f)*g输出其后缀表达式:abc/+de*f+g*-

顶部目录