数据结构(C语言版)第3章__栈和队列.pptVIP

gfhgfhgf 数据结构(Data Structures)(C语言版) 主讲教师： 吴让仲 Instructor: WU, RANGZHONG E-mail: wurangzhong@163.com 第三章 栈和队列 本 章 重 点 1. 栈和队列的定义、特征、运算。 2. 栈的两种存储结构的描述方法以及基本操作（主要是入栈和出栈）。 3. 队列的两种存储结构的描述方法以及基本操作（主要是入队和出队）。 栈示意图 栈的抽象数据类型定义 ADT Stack{ 数据对象：D={ai|ai?ElemSet,i=1,2,...,n，n=0} 数据关系：R={ai-1,ai|ai-1,ai?D,i=2,...,n} 基本操作: 栈初始化：StackInit() 判栈空：StackEmpty(S) 入栈：Push(S，x) 出栈：Pop(S) 取栈顶元素：StackGetTop(S) 清空栈： StackClear (S) 求栈长：StackLength(S) }ADT Stack 栈的表示和实现 顺序存储结构：顺序栈(Sequential Stacks )； 链式存储结构：链栈(Linked Stacks)； 双向栈 两个栈共享一个向量空间，栈底分别设在两端，写出进栈和退栈操作 双向栈的类型定义 #define m 64 typedef struct { ElemType data[m]; int top[2]; // top[0],top[1]分别是两个 // 栈的栈顶指针 }TStack; 链栈图示 迷宫算法 do{ 若当前位置可通， 则{将当前位置插入栈顶； 若该位置是出口位置，则结束； 否则切换当前位置的东邻快为新的当前位置； } 否则， 若栈不空且栈顶位置尚有其他方向未经探索， 则设定新的当前位置为顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则{ 删除栈顶位置； 若栈不空，则重新测试新的栈顶位置， 直到找到一个可通的相邻块或出栈至栈空； } } 作业(每次作业下周交，各班学习委员统一给我，电子档形式) 实践P50页的迷宫 要求： 算法说明 ADT描述 源程序 文档 将文档和代码放在一个文件夹中 班号学号+下划线+姓名 队列的抽象数据类型 ADT Queue{ 数据对象：D={ai | ai ? ElemSet ， i=1，2，... ，n，n=0} 数据关系：R={ai-1,ai|ai-1,ai?D,i=2,...,n} 基本操作： 队列初始化： QueueInit () 入队： QueueIn (Q , x) 出队：　 QueueOut (Q ) 读队头元素： QueueGetHead(Q ) 判队空： QueueEmpty (Q) 求队列长： QueueLength(Q) }ADT Queue 队列的表示和实现 顺序存储结构：循环队列； 链式存储结构：链队列； 3.4.2 循环队列－队列的顺序表示和实现 　　队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值在队列初始化时均应置为０。 下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。 #define QueueSize 100 typedef char DataType; typedef Struct{ int front; int rear; int count; datatype data[queuesize] }cirqueue; 链队示意图 (1)链队列的初始化 创建一个带头结点的空队 (2)链队列的入队 (3)链队列的