数据结构3_栈和队列

《数据结构3_栈和队列》由会员分享，可在线阅读，更多相关《数据结构3_栈和队列（41页珍藏版）》请在金锄头文库上搜索。

1、第三章 栈和队列内容提要n本课主题： 栈的表示与实现，栈的应用，队列 的表示与实现，队列的应用n教学目的： 栈的数据类型定义、栈的顺序存储 表示与实现，掌握栈的应用方法，理解栈的重 要作用，掌握队列的类型定义，掌握链队列的 表示与实现方法n教学重点： 顺序栈的表示与实现，栈与递归， 顺序队列的表示与实现n教学难点： 栈的定义，栈与递归，栈的应用， 顺序队列的表示与实现3.1 栈n栈的由来n函数调用、中断的计算机实现(P56)3.1.1栈的概念n一、栈的定义n栈:限定仅在表尾进行插入或删除操作的 线性表。 n形象的例子：仓库物流，车辆进出只有 一对铁轨、一个出口的火车站，建房。n典型应用：函数调

2、用、递归调用的实现 、递归问题的非递归法求解、括号匹配 、表达式求值、语句编译、迷宫问题求 解3.1.1栈的概念n栈的表尾称为栈顶，表头称为栈底，不 含元素的空表称为空栈。栈的特点n栈的特点：后进先出(last in first out, LIFO) n提问：向某栈输入了三个元素，已知元 素输入的先后顺序是A、B、C，那么该 栈的输出序列可能有哪些？反过来， 如果输出序列是A、B、C呢？nCBA, ABC, ACB, BAC, BCA，无CAB3.1.2栈的抽象数据类型定义nADT Stack 数据对象: D=ai|aiElemSet,i=1,2,.,n,n=0 数据关系: R=|aiD,i=

3、2,.,n 基本操作: InitStack( /栈底指针，指向栈底元素，也即数组 基地址。ElemType *top; /栈顶指针，指向栈顶元素的下一个位 置(有的书上表示的是当前栈顶元素的位置)，便于判断 栈空、栈满和计算表长int stacksize; /栈当前可使用的最大容量。 ; 顺序栈的类C语言实现n栈底元素：*base，栈顶元素：*(top-1)n栈空判断条件：ntop=base;或top-base=0;n栈满判断条件：ntop-base=stacksize;n栈的长度：ntop-basen注意不同的课本上top的含义略有不同，导致 判断条件也略有不同！初始化Status Init

4、Stack(SqStack if(S.base=NULL) exit(OVERFLOW);S.top=S.base; /不是S.top=0或S.length=0S.stacksize=STACK_INI_SIZE;return OK; /InitStack 插入Status Push(SqStack if(S.base=NULL)exit(OVERFLOW);S.top=S.base+S.stacksize; /栈长不变，但栈顶指针会变S.stacksize+=STACKINCREMENT;*S.top+=e; /先*S.top=e,再S.top+,使其指向栈顶下一个元素return OK;

5、/Push 删除Status Pop(SqStack /一定要 先判断栈是否为空栈e=*(-S.top); /先-S.top，使其指向栈顶 ，然后再e=*S.topreturn OK; /Pop销毁、栈空Status DestroyStack(SqStack else return FALSE; /StackEmpty 该函数可简化!获取栈顶元素Status GetTop(SqStack S, ElemType /栈空e=*(S.top-1); /注意不是S.top-return OK; /GetTop3.1.4链栈：栈的链式存储及其实现n注意base指向链栈的头结点而非首元素 ，top指向尾

6、结点，而非其“下一个”元素 。栈空判断条件？ base=top base-next=NULL top-next=NULL错误3.2 栈的应用:数制转换n一、栈的应用之一：数制转换（P48）n将十进制数转换成其它进制数的方法：66/8=8 余 28/8=1 余 0 结果：(66)10=(102)81/8=0 余 1n结论：后求出的余数先写，先求得的余数后 写，符合栈的后入先出性质，故可用栈来实 现数制转换。3.2 栈的应用:行编辑程序n二、栈的应用之二：行编辑程序（P49）n用户在终端输入字符不可能不出错，例如： 用户在终端上输入whli#ilr#e(s#*s)，其中 ： #为退格符，为退行符。

7、n则实际输入的数据应为 while(*s)n行编辑程序的功能：接受用户从终端输入的 数据，并存入缓冲区，然后程序把缓冲区信 息转换为正确的数据存入数据区。3.2 栈的应用:表达式求值n三、栈的应用之三：括号匹配（P49）n四、栈应用之四：表达式求值（P52）n高级语言(如C+)允许程序中含表达式，编译器应 能分析表达式并求出结果。如：a=1+2*(3-4/5);n表达式的要素：运算符、操作数、优先级、界限符n算法基本思想： 1.算法需要两个栈：操作数栈和运算符栈。 2.首先置操作数栈为空栈，表达式起始符#为运算符 栈的栈底元素； 3.依次读入表达式中每个字符，若是操作数则进操作 数栈；若是运算

8、符，则和运算符栈的栈顶运算符比 较优先权并作相应操作，直至整个表达式求值完毕3.2 栈的应用:递归问题n五、栈应用子五：迷宫求解（P50）n六、栈应用之六：递归问题的非递归算法n递归(本章下一节)n第六章中二叉树遍历的非递归算法3.3 栈与递归n递归问题举例：阶乘函数、数列递推函数、汉 诺塔问题n递归函数：直接或间接调用自己的函数。n本质：根据小规模结论探讨大规模问题的解。n注意：递归函数一定要有退出条件，其时间复杂度 、空间复杂度的计算方法也很特殊（参见第一章） 。n递归问题求解：n利用递归函数很容易求解递归问题，如阶乘函数。n利用栈可以实现递归问题的非递归算法栈的一 个重要用途就是在程序设

9、计语言中通过非递归算法 求解递归问题。递归的用途与栈n递归的用途：n实现递归问题n实现“非递归”问题：如顺序表、链表的处理 （逻辑上链表可看作是首元素和剩下的元素 组成的链表组成的，这是一个递归形式的定 义，因此算法上就可以用递归函数实现，但 效率不一定会提高）。参见recursion.cppn提问：该程序相当于实现了那种线性结构？ 如何通过递归函数实现load()函数？3.4 队列n一、队列的定义:n队列：只允许在表的一端插入元素，在 另一端删除元素的线性表。n形象的例子：日常生活中的排队，最早 入队的最早离开；车辆进站；任务安排 ；进程管理；网络数据传输；离散事件 模拟。3.4.1 队列的

10、概念n在队列中，允许插入的的一端叫队尾， 允许删除的一端称为队头。n队列的特点：先进先出(first in first out, FIFO)。3.4.2 队列的抽象数据类型定义ADT Queue 数据对象:D=ai|aiElemSet,i=1,2,.,n,n=0 数据关系:R=|aiD,i=2,.,n 基本操作： InitQueue( /元素的数据信息QNode *next; /后继元素的指针 ;struct LinkQueue /定义队列类型 QNode *front; /队头指针，指向链队头结点，即首元素前驱结点QNode *rear; /队尾指针，指向队尾元素。 ;初始化Status I

11、nitQueue(LinkQueue if(Q.front=NULL) exit(OVERFLOW);Q.front-next=NULL;return OK; 插入Status EnQueue(LinkQueue if(p=NULL) exit(OVERFLOW);p-data=e; p-next=NULL;Q.rear-next=p;Q.rear=p;return OK; 删除(略修改P62程序)Status DeQueue(LinkQueue /空队列p=Q.front-next; /暂存首元素指针pe=p-data;Q.front-next=p-next;if(Q.front-next=

12、NULL) Q.rear=Q.front; /表长为1时rear变化free(p);return OK; 销毁(修改P62程序)Status DestroyQueue(LinkQueue while(p!=NULL) q=p-next; free(p); p=q; Q.front=Q.rear=NULL; return OK; 3.4.4 循环队列队列的顺序 表示和实现n顺序队列：使用连续内存空间表示队列n所存在的问题：顺序队列的问题和解决办法n改进办法：循环队列n采用循环结构以节省空间，其中： 实际存储位置理论存储位置 % MAXQSIZEn少用一个元素空间，以便区分空队和满队循环队列的类C

13、语言实现#define MAXQSIZE 100 /最大队列长度 struct SqQueue QElemType *base; /应当定义为静态数组结 构baseMAXQSIZE，可简化操作(P64)int front; /队头指针(游标)，指向队头元素int rear; /队尾指针(游标)，指向队尾元素的 下一个位置。 ;循环队列的类C语言实现n队头元素(注意不是Q.base0) ：nQ.basefrontn队尾元素(注意不是Q.baseQ.rear-1，更不是Q.baseQ.rear)：nQ.base (Q.rear-1+MAXQSIZE) % MAXQSIZE n队空判断条件：nfro

14、nt=rearn队满判断条件：n(rear+1) % MAXQSIZE=frontn(rear+1-front) % MAXQSIZE=0n表长(注意不是rear-front)：n(rear-front+MAXQSIZE) % MAXQSIZE 注意：不同的课本上front、rear的含义略 有不同，会导致判断条件略有不同！初始化Status InitQueue(SqQueue /如采用静态内存无需该语句if(Q.base=NULL) exit(OVERFLOW);Q.front=Q.rear=0; /队头、队尾的游标，初始值为数 组下标0。return OK; 插入Status EnQueu

15、e(SqQueue /队满，无法插入。也可改为追加空间Q.baseQ.rear=e; /此处采用游标结构，且游标值为 数组下标。如采用位序，该处语句将有所不同Q.rear=(Q.rear+1) % MAXQSIZE; /循环结构，不是 简单的Q.rear+return OK; 删除Status DeQueue(SqQueue /队空e=Q.baseQ.front; /此处采用游标结构，且游标值为 数组下标。如采用位序，该处语句将有所不同Q.front=(Q.front+1) % MAXQSIZE; /循环结构，不 是简单的Q.front+return OK; 获取队列长度int QueueLength(SqQueue Q) return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; Status QueueEmpty(SqQueue Q) if (Q.rear = Q.front) return TRUE; else return FALSE; 该函数可简化!3.4.5 队列的应用n1.任务安排n2.进程管理n3.离散事件模拟n4.二叉树的层次遍历算法(第六章)总结n1.栈的定义、特点、主要操作n2.栈的顺序存储结构和链式存储结构n3.栈与递归、栈的应用n4.队列的定义、特点、主要操作n5.队列的顺序存储结构(循环队列)和链 式存储结构