数据结构3栈和队列.ppt

第三章 栈和队列 内容提要 n本课主题： 栈的表示与实现，栈的应用，队列 的表示与实现，队列的应用 n教学目的： 栈的数据类型定义、栈的顺序存储 表示与实现，掌握栈的应用方法，理解栈的重 要作用，掌握队列的类型定义，掌握链队列的 表示与实现方法 n教学重点： 顺序栈的表示与实现，栈与递归， 顺序队列的表示与实现 n教学难点： 栈的定义，栈与递归，栈的应用， 顺序队列的表示与实现 3.1 栈 n栈的由来 n函数调用、中断的计算机实现(P56) 3.1.1栈的概念 n一、栈的定义 n栈:限定仅在表尾进行插入或删除操作的 线性表。 n形象的例子：仓库物流，车辆进出只有 一对铁轨、一个出口的火车站，建房。 n典型应用：函数调用、递归调用的实现 、递归问题的非递归法求解、括号匹配 、表达式求值、语句编译、迷宫问题求 解 3.1.1栈的概念 n栈的表尾称为栈顶，表头称为栈底，不 含元素的空表称为空栈。 栈的特点 n栈的特点：后进先出(last in first out, LIFO) n提问：向某栈输入了三个元素，已知元 素输入的先后顺序是A、B、C，那么该 栈的输出序列可能有哪些？反过来， 如果输出序列是A、B、C呢？ nCBA, ABC, ACB, BAC, BCA，无CAB 3.1.2栈的抽象数据类型定义 nADT Stack 数据对象: D=ai|aiElemSet,i=1,2,.,n,n=0 数据关系: R=|aiD,i=2,.,n 基本操作: InitStack( /栈底指针，指向栈底元素，也即数组 基地址。 ElemType *top; /栈顶指针，指向栈顶元素的下一个位 置(有的书上表示的是当前栈顶元素的位置)，便于判断 栈空、栈满和计算表长 int stacksize; /栈当前可使用的最大容量。 ; 顺序栈的类C语言实现 n栈底元素：*base，栈顶元素：*(top-1) n栈空判断条件： ntop=base;或top-base=0; n栈满判断条件： ntop-base=stacksize; n栈的长度： ntop-base n注意不同的课本上top的含义略有不同，导致 判断条件也略有不同！ 初始化 Status InitStack(SqStack if(S.base=NULL) exit(OVERFLOW); S.top=S.base; /不是S.top=0或S.length=0 S.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; /Push 删除 Status Pop(SqStack /一定要 先判断栈是否为空栈 e=*(-S.top); /先-S.top，使其指向栈顶 ，然后再e=*S.top return OK; /Pop 销毁、栈空 Status DestroyStack(SqStack else return FALSE; /StackEmpty 该函数可简化! 获取栈顶元素 Status GetTop(SqStack S, ElemType /栈空 e=*(S.top-1); /注意不是S.top- return OK; /GetTop 3.1.4链栈：栈的链式存储及其实现 n注意base指向链栈的头结点而非首元素 ，top指向尾结点，而非其“下一个”元素 。 栈空判断条件？ base=top base-next=NULL top-next=NULL错误 3.2 栈的应用:数制转换 n一、栈的应用之一：数制转换（P48） n将十进制数转换成其它进制数的方法： 66/8=8 余 2 8/8=1 余 0 结果：(66)10=(102)8 1/8=0 余 1 n结论：后求出的余数先写，先求得的余数后 写，符合栈的后入先出性质，故可用栈来实 现数制转换。 3.2 栈的应用:行编辑程序 n二、栈的应用之二：行编辑程序（P49） n用户在终端输入字符不可能不出错，例如： 用户在终端上输入whli#ilr#e(s#*s)，其中 ： #为退格符，为退行符。 n则实际输入的数据应为 while(*s) n行编辑程序的功能：接受用户从终端输入的 数据，并存入缓冲区，然后程序把缓冲区信 息转换为正确的数据存入数据区。 3.2 栈的应用:表达式求值 n三、栈的应用之三：括号匹配（P49） n四、栈应用之四：表达式求值（P52） n高级语言(如C+)允许程序中含表达式，编译器应 能分析表达式并求出结果。如：a=1+2*(3-4/5); n表达式的要素：运算符、操作数、优先级、界限符 n算法基本思想： 1.算法需要两个栈：操作数栈和运算符栈。 2.首先置操作数栈为空栈，表达式起始符#为运算符 栈的栈底元素； 3.依次读入表达式中每个字符，若是操作数则进操作 数栈；若是运算符，则和运算符栈的栈顶运算符比 较优先权并作相应操作，直至整个表达式求值完毕 3.2 栈的应用:递归问题 n五、栈应用子五：迷宫求解（P50） n六、栈应用之六：递归问题的非递归算法 n递归(本章下一节) n第六章中二叉树遍历的非递归算法 3.3 栈与递归 n递归问题举例：阶乘函数、数列递推函数、汉 诺塔问题 n递归函数：直接或间接调用自己的函数。 n本质：根据小规模结论探讨大规模问题的解。 n注意：递归函数一定要有退出条件，其时间复杂度 、空间复杂度的计算方法也很特殊（参见第一章） 。 n递归问题求解： n利用递归函数很容易求解递归问题，如阶乘函数。 n利用栈可以实现递归问题的非递归算法栈的一 个重要用途就是在程序设计语言中通过非递归算法 求解递归问题。 递归的用途与栈 n递归的用途： n实现递归问题 n实现“非递归”问题：如顺序表、链表的处理 （逻辑上链表可看作是首元素和剩下的元素 组成的链表组成的，这是一个递归形式的定 义，因此算法上就可以用递归函数实现，但 效率不一定会提高）。参见recursion.cpp n提问：该程序相当于实现了那种线性结构？ 如何通过递归函数实现load()函数？ 3.4 队列 n一、队列的定义: n队列：只允许在表的一端插入元素，在 另一端删除元素的线性表。 n形象的例子：日常生活中的排队，最早 入队的最早离开；车辆进站；任务安排 ；进程管理；网络数据传输；离散事件 模拟。 3.4.1 队列的概念 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 InitQueue(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; /暂存首元素指针p e=p-data; Q.front-next=p-next; if(Q.front-next=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采用循环结构以节省空间，其中： 实际存储位置理论存储位置 % MAXQSIZE n少用一个元素空间，以便区分空队和满队 循环队列的类C语言实现 #define MAXQSIZE 100 /最大队列长度 struct SqQueue QElemType *base; /应当定义为静态数组结 构baseMAXQSIZE，可简化操作(P64) int front; /队头指针(游标)，指向队头元素 int rear; /队尾指针(游标)，指向队尾元素的 下一个位置。 ; 循环队列的类C语言实现 n队头元素(注意不是Q.base0) ： nQ.basefront n队尾元素(注意不是Q.baseQ.rear-1，更不是Q.baseQ.rear)： nQ.base (Q.rear-1+MAXQSIZE) % MAXQSIZE n队空判断条件： nfront=rear n队满判断条件： n(rear+1) % MAXQSIZE=front n(rear+1-front) % MAXQSIZE=0 n表长(注意不是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 EnQueue(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) % MAXQS