文档详情

数据结构 栈和队列教程.ppt

发布:2017-04-27约1.98千字共40页下载文档
文本预览下载声明
第3章 栈和队列 ;3.1.1 栈的定义 3.1.2 栈的顺序存储结构及其基本运算的实现 3.1.3 栈的链式存储结构及其基本运算的实现 3.1.4 栈的应用; 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。 栈顶的当前位置是动态的,由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。 当栈中没有数据元素时,称为空栈。 栈的插入操作通常称为压栈或进栈,栈的删除操作通常称为退栈或出栈。 栈的主要特点是“后进先出”。也称为后进先出表。;a1;后进先出;【例3.3】设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是 。 (A) A,B,C,D (B) D,C,B,A (C) A,C,D,B (D) D,A,B,C ;抽象数据类型栈的定义:《教材P65》;3.1.2 栈的顺序存储结构及其基本运算的实现 假设栈的元素个数最大不超过正整数MaxSize,所有元素都具有同一数据类型ElemType,则可用下列方式来定义顺序栈类型SqStack: typedef struct{ ElemType data[MaxSize]; int top; //栈顶指针 } SqStack;; 栈空条件:top==-1 栈满条件:top==MaxSize-1 进栈操作:top++; 再将元素放在top处 退栈操作:从top处取出元素,再将top--;;在顺序栈中实现栈的基本运算算法:;【例3.4】编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。;;在链栈中的基本运算算法:;【例3.5】编写一个算法判断输入的表达式中的括号是否正确配对。(假设只含有左、右圆括号);3.1.4 栈的应用;1. 表达式求值;中缀表达式 a + b * ( c - d ) - e / f;假设用exp字符数组存储算术表达式,其对应后缀表达式存放在字符数组postexp中。在将算术表达式转换成后缀表达式的过程中用一个字符数组op作为运算符栈。具体步骤如下: ;a + b ? c ? d / e ? f `\0`;表达式“(56-20)/(4+2)”转换成后缀表达式的过程:;后缀表达式求值;【问题描述】给定一个M×N的迷宫图,求一条从指定入口到出口的路径。;3.2 队列 ; 队列(Queue)简称队,它也是一种运算受限的线性表,其限制为仅允许在表的一端进行插入,在另一端进行删除。把进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。 向队列中插入新元素称为进队或入队,新元素进队后就成为新的队尾元素;从队列中删除元素称为出队或离队,元素出队后,其后继元素就成为队首元素。 ;队列的基本运算:; 3.2.2 队列的顺序存储结构及其基本运算的实现;1.基于顺序存储的队列的基本运算;基于顺序存储队列的基本运算;;环形队列首尾相连,当队首指针front满足 front==MaxSize-1后,再前进一个位置就自动到0,可以利用求余运算(%)来实现。 队首指针进1:front=(front+1)%MaxSize 队尾指针进1:rear=(rear+1)%MaxSize 指针初始化: front=rear=0 队满条件: (q-rear+1) % MaxSize==q-front 队空条件: q-rear==q-front; 已知front、rear,求count:     已知front、count,求rear:     已知rear、count,求front:    ;解: 已知队头指针front和队列中元素个数count。;3.2.3 队列的链式存储结构及其基本运算的实现;链队的入队和出队操作示意图;链队存储中的基本运算算法;【例3.8】 采用一个不带头节点只有一个尾节点指针rear的循环单链表存储队列,设计队列的初始化、进队和出队算法。;3.2.4 队列的应用;3.2.5 双端队列; 输出受限的双端队列(即一个端点允许插入和删除,另一个端点只允许插入的双端队列);本章小结 本章基本学习要点如下: (1) 理解栈和队列的特性以及它们之间的差异,知道在何时使用哪种数据结构。 (2) 重点掌握在顺序栈和链栈上实现栈的基本运算算法,注意栈满和栈空的条件。 (3) 重点掌握在顺序队(环形队)和链队上实现队列的基本运算算法,注意队满和队空的条件。 (4) 灵活运用栈和队列两种数据结构解决一些综合应用问题。
显示全部
相似文档