一章栈和队列.ppt
《一章栈和队列.ppt》由会员分享,可在线阅读,更多相关《一章栈和队列.ppt(61页珍藏版)》请在三一文库上搜索。
1、第三章 栈和队列,本章内容 3.1 栈 3.1.1 栈的定义及基本运算 3.1.2 栈的存储结构和实现 3.1.3 栈的应用 3.2 队列 3.2.1 队列的定义及基本运算 3.2.2 队列的存储结构和实现 3.2.3 队列的应用,3.1.1 栈的定义及基本运算,栈(Stack)的定义 栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(top),另一端为栈底(bottom)。当表中没有元素时称为空栈。,入栈,出栈,栈的特点 栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。,3.1.1 栈的定义及基本运算,栈的运算演示 (1)A、B
2、、C、D四个元素依次进入一个栈,再依次出栈,得到一个输出序列DCBA。,ABCD,DCBA,3.1.1 栈的定义及基本运算,栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈,再依次出栈,得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE?,ABCDE,操作序列:,出栈序列:, 元素A入栈,A,A, 元素B入栈,B,B, 元素C入栈,C,C,3.1.1 栈的定义及基本运算,栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈,再依次出栈,得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE?,DE,操作序列:,
3、出栈序列:, 元素A入栈,A, 元素B入栈,B, 元素C入栈, 元素C出栈,C,C, 元素B出栈,B,3.1.1 栈的定义及基本运算,栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈,再依次出栈,得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE?,DE,操作序列:,出栈序列:, 元素A入栈,A, 元素B入栈, 元素C入栈, 元素C出栈,C, 元素B出栈,B, 元素D入栈,D,D, 元素D出栈,D, 元素A出栈,A,3.1.1 栈的定义及基本运算,栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈,再依次出栈,得到一个输出序列DCBA。 (2
4、)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE?,E,操作序列:,出栈序列:, 元素A入栈, 元素B入栈, 元素C入栈, 元素C出栈,C, 元素B出栈,B, 元素D入栈, 元素D出栈,D, 元素A出栈,A, 元素E入栈,E,E, 元素E出栈,E,栈的基本运算 InitStack(&S): 初始化栈S StackEmpty(): 判断栈是否为空 Push(e): 将元素e放入栈顶 Pop(e): 移走栈顶的元素,同时由e带回该元素的值 Gettop(): 获取栈顶的元素,但不从栈中移走,3.1.1 栈的定义及基本运算,3.1.2 栈的存储结构和实现,栈, 栈的表示和实现 假设栈S=(a
5、1,a2,a3,an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,,an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(Last In First Out,LIFO),3.1.2 栈的存储结构和实现, 顺序栈 由于栈是运算受限的线性表,因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈,它是运算受限的线性表。因此,可用数组来实现顺序栈。,3.1.2 栈的存储结构和实现,顺序栈的类型定义 / -栈的顺序存储表示- # define STACK_INIT_SIZE 100; # define STACKI
6、NCREMENT 10; typedef struct SElemType *base; /栈底指针,栈构造前和销毁后为空 SElemType *top; /栈顶指针,指向栈顶元素的下一位置 int stacksize; /当前分配的栈的存储空间数 SqStack;, 顺序栈 设S是SqStack类型的指针变量。base是栈底指针。Top是栈顶指针。 栈不存在条件S.base=NULL 栈空条件S.top=S.base 插入栈顶元素,栈顶指针S.top=S.top+1 删除栈顶元素,栈顶指针S.top=S.top-1 栈满条件S.top-S.base=S.stacksize,3.1.2 栈的存
7、储结构和实现,3.1.2 栈的存储结构和实现,顺序栈的C语言实现 (1) 初始化 Status InitStack(SqStack /InitStack,(2)判断栈空 int StackEmpty(SqStack *S) return(S.base=S.top); (3)判断栈满 int StackFull(SqStack *S) return(S.top-S.base=S.stacksize); ,3.1.2 栈的存储结构和实现,3.1.2 栈的存储结构和实现,(4) 元素入栈 Status Push(SqStack /Push,(5) 出栈 void Pop(SqStack *S, SE
8、lemType ,3.1.2 栈的存储结构和实现,3.1.2 栈的存储结构和实现, 链栈 栈的链式存储结构称为链栈,它是运算是受限的单链表,插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作,故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 链栈的类型说明如下: typedef struct stacknode SElemType data; struct stacknode *next; stacknode,*linkstack;,3.1.2 栈的存储结构和实现,链栈,栈,思考 链栈是否需要另外设置头指针? 建立链栈适合用哪种插入法? 链栈的基本操作的实现。,
9、链栈的基本操作 置空栈 void InitStack(linkStack ,3.1.2 栈的存储结构和实现, 链栈的基本操作 进栈 void Push(linkstack /设置栈顶指针 ,3.1.2 栈的存储结构和实现, 链栈的基本操作 退栈 SElemType Pop(linkstack ,3.1.2 栈的存储结构和实现, 链栈的基本操作 取栈顶元素 SElemType GetTop(linkstack p) if(p=NULL) error(“stack is empty.”); return pdata; ,3.1.2 栈的存储结构和实现,3.2 栈的应用举例,根据栈的FILO特性,用
10、作某些处理问题的工具。 3.2.1 数制转换 例: 4310 = 1010112,输出,void conversion( ) InitStack(S); /构造空栈 scanf (“%d”, ,3.2 栈的应用举例,3.2.2 括号匹配 设一个表达式中可以包含三种括号:“(”和“)”、“”和“”、“”和“”,并且这三种括号可以按照任意的次序嵌套使用,考查表达式中的括号是否匹配。例如: .(.).). 例: a=b+(c-d)*(e-f); while (m(a8+t) m=m+1; t=t-1; 实现方法利用栈进行表达式中的括号匹配 自左至右扫描表达式,若遇左括号,则将左括号入栈,若遇右括号,
11、则将其与栈顶的左括号进行匹配,若配对,则栈顶的左括号出栈,否则出现括号不匹配错误。 思考:匹配的充要条件?,3.2 栈的应用举例,3.2.3 迷宫问题 寻找一条从入口到出口的通路。,前进方向: 上(北)、下(南)、左(西)、右(东),走步规则: 首先从向下开始,按照逆时针方向搜索下一步可能前进的位置,3.2 栈的应用举例,迷宫问题,(1,1),3.2 栈的应用举例,迷宫问题,3.2 栈的应用举例,迷宫问题 迷宫的表示 const int N=8; struct PosType int x, y; ; char mazeNN; /位置上的标识,是否可通过 迷宫初始化 用二层嵌套循环对迷宫赋值 迷
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一章栈 队列
链接地址:https://www.31doc.com/p-3247560.html