数据结构(C语言版) 课件第3章.ppt

《数据结构(C语言版) 课件第3章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈和队列1本章学习目的、要求、重点、难点目的：介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求：在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈和队列。重点：掌握栈和队列在两种存储结构上实现的基本运算。难点：循环队列重对边界条件的处理。2栈和队列是两种重要的线性结构。从数据结构的角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，他们是操作受限的线性表，因此，可称为限定性的数据结构；但从数据类型的角度看，它们是和线性表大不相同的两类重要的抽象数据类型。由于它们广泛的应用在各种软件系统中，因此

2、在面向对象的程序设计中，它们是多型数据类型。引言33.1栈3.2栈的应用举例*3.3栈与递归的实现（略）3.4队列*3.5离散事件模拟（略）主要内容43.1栈栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。通常称其表尾为栈顶（top），表头端称为栈底（bottom）。假设栈S={ai

3、ai∈ElemSet,i=1,2,...,n,n≥0}，则称a1为栈底元素，an为栈顶元素，栈中元素按a1,a2,…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（lastinfirstout）的线性表（简

4、称LIFO表）。3.1.1抽象数据类型栈的定义5ADTStack{数据对象：D＝{ai

5、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{

6、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStack栈的抽象数据类型定义：6数据对象：D={ai

7、ai∈ElemSet,i=1,2,···,n,n≥0}数据关系：R1={

8、ai-1,ai∈D,i=1,2,···,n}约定an端为栈顶，a1端为栈底基本操作：InitStack(&S)操作结果：构造一个空栈S。Destro

9、yStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ADTStack{7StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。8GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。a1a2ane……9Pop(&

10、S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值a1a2anan-1……StackTraverse(S,visit())初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。}ADTStack103.1.2栈的表示和实现typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;}SqStack其中，stacksize指示栈的当前可使用的最大容量。Top为栈顶指针，其初值指向栈底，

11、每当插入新元素，指针top加1，删除栈顶元素时，指针top减1。非空栈中，top始终指向栈顶元素的下一个位置。顺序栈的定义：11以下是顺序栈的模块说明。//-----ADTStack的表示与实现-----//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前

12、已分配的存储空间，以元素为单位}SqStack12-----基本操作的函数原型说明-----StatusInitStack(SqStack&S);//构造一个空栈SStatusDestroyStack(SqStack&S);//销毁栈S，S不再存在StatusClearStack(SqStack&S);//重置S为空栈StatusStackEmpty(SqStackS);//若栈为空栈，则返回TRUE，否则返回FALSEintStackLength(SqStackS);//返回S的元素个数，即栈的长度13StatusGetTop(SqStackS,SElemTy

13、pe&e)//若栈不空，