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