数据结构讲义第3章.ppt

第三章 栈和队列,栈和队列是两种重要的数据结构。 从结构特性角度看，栈和对列也是线性表，其特殊性在于它们的基本操作是线性表的子集，是操作受限的线性表，可称为限定性的数据结构。 从数据类型角度看，其操作规则与线性表大不相同，是完全不同于线性表的抽象数据类型。,第一节 栈,一、栈的定义 栈是限定在表的一端进行插入和删除操作的线性表。 插入：称为进栈（或压栈）。 删除：称为出栈（或退栈）。 栈顶（top）：允许进行插入和删除操作的一端。 栈底（bottom）：不允许插入和删除操作的一端。,基本操作： Initstack(&s): 栈初始化 Destroystack(&s)：撤消栈 Clearstack(&s)：置栈空 Stackempty(s) ：判栈空 Stacklength(S)：求栈中元素个数 Gettop(S,&e)： 取栈顶元素 Push(&S,e)： 入栈 Pop(&S,&e)： 出栈,特点：后进先出-LIFO Last In First Out,栈的表示与实现,三、栈的顺序存储结构-顺序栈 利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。 顺序栈存储结构定义： #define STACK_INIT_SIZE 100 /存储空间初始分配量； #define STACKINCREMENT 10 /存储空间分配增量 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; Base指向存储空间开始地址，top指示栈顶当前位置。 若栈空间未分配，则base为NULL； top=base:栈空 top-base=stachsize:栈满 元素进栈：在top位置插入元素，top增1 元素出栈：top减1。 top指针始终指向栈顶元素的下一个位置 。,顺序栈操作的实现,1、栈初始化：分配初始存储空间，初始化各变量。 Status Initstack(Sqstack s.stacksize= STACK_INIT_SIZE； return Ok； ,顺序栈操作的实现,2、撤消栈：释放栈空间。 status Destroystack(SqStack return OK ,顺序栈操作的实现,5、入栈操作：把元素压入栈中。 status Push(SqStack ,压栈操作,顺序栈操作的实现,6、出栈操作：删除栈顶元素。 Status Pop(Sqstack e=*(-s.top) return Ok ,出栈操作,链式栈的实现,用线性链表表示栈的存储结构，称为链栈。 链表头指针始终指向栈顶，同样用top表示。 无必要加头结点，栈空时：top=NULL 入栈：每当一个元素进栈时，申请一个新结点，插入到表头。 出栈：每当一个元素出栈时，从表头释放一个结点。 链栈结点结构描述如下 typedef struct stacknode ElemType data; struct stacknode *next; StackNode; typedef struct StackNode *top; LinkStack;,第二节 栈的应用,一、数制转换 将一个非负的十进制整数转换为另一个等价的进制数。 方法：不断用及其商去除以求余数直到商为为止，所得余数的反序排列就是的进制表示。,5310的二进制表示 (53)10(110101)2 N 余数 商 53 26 26 0 13 13 1 6 6 0 3 3 1 1 1 1 0,5310的八进制表示 (53)10(65)8 N 余数 商 53 5 6 6 6 0,5310的四进制表示 (53)10(311)4 N 余数 商 13 1 3 3 3 0,实现方法：用一个栈来存放产生的余数，然后从栈顶到栈底依次输出余数就是所求的进制数。,栈的应用,算法： typedef int DataType; void Comversion(int N,int B) int i; SeqStack S; InitStack( 算法的时间复杂度 O(logBN)。,栈的应用表达式求值,一、算术四则运算法则： 先乘除后加减 从左至右 先括号内后括号外 方法：对运算符建立优先关系矩阵，按优先关系对表达式进行处理。 算符：运算符和界符。 根据法则1：乘除优先于加减，乘除优先级相同，加减优先级相同。 根据法则2：相邻两个同级运算符左优先。 根据法则3：“（”前面的运算符优先级低于“（”的优先级。“（”的优先级低于右边相邻算符。“）”左边的算符高于“）”的优先级。,栈的应用表达式求值,栈的应用表达式求值,处理过程： 设置两个栈：操作数栈OPND和运算符栈OPTR。 设“#”表示表达式的开始和结束（作为界符），即 #表达式# 1、首先置操作数栈为空栈，把“#”移进运算符栈。 2、从左至右扫描表达式，凡遇到操作数一律进OPND栈；若遇到运算符，则把栈顶运算符与扫描运算符的优先数进行比较：若 取OPND栈顶操作数与OPTR栈顶算符进行运算，参与运算的操作数和运算符出栈，运算结果进OPND栈 若表达式处理完，OPTR栈为#，OPND栈中只剩一项，表示表达式的运算结果，则分析成功。若达不到这种状态，表明表达式有错。,栈的应用表达式求值,例：3+5*(7-2) 步数 OPTR OPND 表达式 主要操作 1 # 3+5*（7-2）# push(OPND, 3) 2 # 3 +5*(7-2)# push(OPTR,+) 3 #+ 3 5*(7-2)# push(OPND, 5) 4 #+ 3,5 *(7-2)# push(OPTR,*) 5 #+* 3,5 (7-2)# push(OPTR,() 6 #+*( 3,5 7-2)# push(OPND,7) 7 #+*( 3,5,7 -2)# push(OPTR,-) 8 #+*(- 3,5,7 2)# push(OPND,2) 9 #+*(- 3,5,7,2 )# opreate(7,-,2) 10 #+*( 3,5,5 )# pop(OPTR,(),去掉） 11 #+* 3,5,5 # opreate(5,*,5) 12 #+ 3，25 # opreate(3,+,25) 13 # 28 # 成功,第三节 栈与递归的实现,递归函数：若在一个函数内部有直接或通过调用函数又间接调用自身，则称它们是递归函数，或者说是递归定义的。,int f( int n) if (n =1) then return (1) else return (n *f(n-1); ,递归函数的执行：递归调用通过栈实现;系统每调用一次函数, 系统就在栈顶分配该函数所需空间。,Y=f(5);,return(1),return(2),return(6),return(24),return(120),栈与递归的实现,递归算法设计一般分两步 ： 将规模较大的原问题分解为一个或多个规模更小，但具有类似于原问题特性的子问题，即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题。 确定一个或多个无须分解、可直接求解的最小子问题。 第一步称为递归步骤，第二步称为递归的终止条件。 在递归步骤里分解问题时，应使子问题相对于原问题更接近于递归终止条件，从而保证经过有限次递归步骤后达到递归终止条件而结束递归。,第四节 队列,一、队列的定义： 队列是限定在表的一端进行插入，在另一端进行删除的线性表。 队头（Front）：允许删除的一端。 队尾(Rear)：允许插入的一端。,基本操作： InitQueue (&Q): 队列初始化 DestroyQueue (&Q)：撤消队列 ClearQueue (&Q)：置队列空 QueueEmpty(Q) ：判队列空 Queuelength(Q)：求队列元素个数 Gethead(Q,&e)： 取队列头元素 EnQueue (&Q,e)： 入队列 DeQueue (&Q,&e)：出队列,特点：先入队列的元素总是先离开队列，所以称队列为先进先出（First In First Out）的线性表，简称FIFO。,队列的链式表示及实现,二、链队列：用线性链表表示队列的存储结构。 头指针-指向删除的一端 尾指针-指向插入的一端 链队列结点结构描述如下 typedef struct QNode QElemType data; Struct QNode *next; Qnode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; LinkQueue Q;,链队列基本操作,1、队列初始化：建立链队列头结点，初始化头、尾指针。 Status Initqueue(linkqueue ,置空队列：保留头结点，头、尾指针置成初始状态。,链队列基本操作,Status Enqueue(linkqueue ,3、入队操作：为入队元素申请结点，并插入到队尾。,链队列基本操作,Status Dequeue(linkqueue ,3、出队操作：删除队头结点，并返回被删结点的值。,队列的顺序表示及实现,四、顺序队列：队列的顺序存储分配称为顺序队列。 顺序队列存储结构描述如下 #define MAXQSIZE 100 typedef struct QElemType *base; int front; int rear; SqQueue; SqQueue Q; 操作： 初 始：Q.front=Q.rear=0 元素进队：Q.baseQ.rear=x;Q.rear+; 元素出队：e=Q.baseQ.front;Q.front+; 队 列 空：Q.front=Q.rear 队 列 满：Q.rear=MAXQSIZE,队列的顺序表示及实现,四、顺序队列操作可能出现的问题 设MAXQSIZE=6,再有元素进队会怎样？,队列的顺序表示及实现,队满的三种情况： 1、所有单元都有元素； 2、部分单元有元素； 3、所有单元均无元素。 当队满时再要插入元素，称为上溢。 假上溢：队空间中还有存储单元未使用，但不能再插入元素。 假上溢原因：头、尾指针值总是不断增加，已使用过的单元无法再使用。,解决假上溢的方法： 1、将队中元素依次向队头方向移动。 缺点：浪费时间。每移动一次，队中元素都要移动。 、将队空间设想成一个循环的表，即分配给队列的个存储单元可以循环使用，当rear为m时，若向量的开始端空着，又可从头使用空着的空间。当front为m时，也是一样。,循环队列,实现方法：模(mod) 运算。 插入元素： Q.baseQ.rear=x; Q.rear=(Q.rear+1) MAXQSIZE; 删除元素: x=Q.bases.front Q.front=(Q.front+1) MAXQSIZE 循环队列：循环使用为队列分配的存储空间。 问题：队空队满都有：Q.front=Q.rear 区分队空队满的方法： 1、设置一个标志字段Q.tag区分队空队满（初值：tag=0 ） Q.tag=0 Q.front=Q.rear 队空 Q.tag=1 Q.front=Q.rear 队满 若进队操作前tag=0,进队操作后有Q.front=Q.rear，则置tag=1. 2、少用一个元素空间，个元素单元最多只存放个元素，且 front=rear -队空 在入队时，若（Q.rear+1）MAXQSIZE=Q.front，则为队满。 、设置一个计数器记录队列中元素的个数。,循环队列算法,1、循环队列初始化：为队列分配存储空间，头尾指针赋初值。 Status InitQueue(SqQueue ,循环队列算法,3、入队操作：在队尾插入新元素。 Status Enqueue(sqqueue ,循环队列算法,4、出队操作：删除队头元素，并返回队头元素的值。 Status DeQueue(SqQueue