数据结构讲义第3章.ppt

第三章 栈和队列 栈和队列是两种重要的数据结构。 从结构特性角度看，栈和对列也是线性 表，其特殊性在于它们的基本操作是线性表 的子集，是操作受限的线性表，可称为限定 性的数据结构。 从数据类型角度看，其操作规则与线性 表大不相同，是完全不同于线性表的抽象数 据类型。 第一节 栈 一、栈的定义 栈是限定在表的一端进行插入和删除操作的线性表。 插入：称为进栈（或压栈）。 删除：称为出栈（或退栈）。 栈顶（top）：允许进行插入和删除操作的一端。 栈底（bottom）：不允许插入和删除操作的一端。 基本操作： Initstack( SElemType *top; int stacksize; SqStack; Base指向存储空间开始地址，top指示栈顶当前位置。 若栈空间未分配，则base为NULL； top=base:栈空 top-base=stachsize:栈满 元素进栈：在top位置插入元素，top增1 元素出栈：top减1。 top指针始终指向栈顶元素的下一个位置 。 顺序栈操作的实现 1、栈初始化：分配初始存储空间，初始化各变量。 Status Initstack(Sqstack if(!b.base) exit(OVERFLOW); s.top=s.base; s.stacksize= STACK_INIT_SIZE； return Ok； 顺序栈操作的实现 2、撤消栈：释放栈空间。 status Destroystack(SqStack s.base=NULL;return OK; return ERROR; 3、置栈空：将栈设置成空栈。 status Clearstack(SqStack return OK; return ERROR; 4、取栈顶元素：返回栈顶元素的值。 status GetTop(SqStack e=*(s.top-1); return OK 顺序栈操作的实现 5、入栈操作：把元素压入栈中。 status Push(SqStack if(!b.base) exit(OVERFLOW); s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; *s.top=e; s.top+; return OK; 压栈操作 top B A base top e B A base e 顺序栈操作的实现 6、出栈操作：删除栈顶元素。 Status Pop(Sqstack e=*(-s.top) return Ok 出栈操作 top Y B A base top B A base Y 链式栈的实现 用线性链表表示栈的存储结构，称为链栈。 链表头指针始终指向栈顶，同样用top表示。 无必要加头结点，栈空时：top=NULL 入栈：每当一个元素进栈时，申请一个新结点，插入到表头。 出栈：每当一个元素出栈时，从表头释放一个结点。 链栈结点结构描述如下 typedef struct stacknode ElemType data; struct stacknode *next; StackNode; typedef struct StackNode *top; LinkStack; Data next S.top 栈顶 栈底 第二节 栈的应用 一、数制转换 将一个非负的十进制整数转换为另一个等价的进制数。 方法：不断用及其商去除以求余数直到商为为止，所得余数的 反序排列就是的进制表示。 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 余数 商 53 13 13 1 3 3 3 0 实现方法：用一个栈来存放产生 的余数，然后从栈顶到栈底依次输出 余数就是所求的进制数。 栈的应用 算法： typedef int DataType; void Comversion(int N,int B) int i; SeqStack S; InitStack( while(N) Push( N=N/B; while(!StackEmpty( printf(“%d”,i); 算法的时间时间 复杂杂度 O(logBN)。 栈的应用表达式求值 一、算术四则运算法则： 先乘除后加减 从左至右 先括号内后括号外 方法：对运算符建立优先关系矩阵，按优先关系对表达式进 行处理。 算符：运算符和界符。 根据法则1：乘除优先于加减，乘除优先级相同，加减优先 级相同。 根据法则2：相邻两个同级运算符左优先。 根据法则3：“（”前面的运算符优先级低于“（”的优先 级。“（”的优先级低于右边相邻算符。“）”左边的算符高 于“）”的优先级。 栈的应用表达式求值 +-*/ ()# + - * / ( # 取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 # 成功 第三节 栈与递归的实现 递归函数：若在一个函数内部有直接或通过调用函数又间接 调用自身，则称它们是递归函数，或者说是递归定义的。 1 n=0 n!= n*(n-1)! n0 1 n0 int f( int n) if (n next=NULL; return OK; 2、撤消队列：删除队列中所有结点（包括头结点）。 Status Destroyqueue(linkqueue free(Q.front); Q.front= p; return OK; 置空队列：保留头结 点，头、尾指针置成初 始状态。 链队列基本操作 Status Enqueue(linkqueue if(!p) exit(OVERFLLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK; 3、入队操作：为入队元素申请结点，并插入到队尾。 Q xe 链队列基本操作 Status Dequeue(linkqueue p=Q.front-next; e=p-data; Q.front-next =p-next; if (Q.rear=p) Q.rear=Q.front; free(p); return OK; 3、出队操作：删除队头结点，并返回被删结点的值。 Q xzy 队列的顺序表示及实现 四、顺序队列：队列的顺序存储分配称为顺序队列。 顺序队列存储结构描述如下 #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 Q.rear Q.front 初态 Q.front a1 a2 a3 Q.rear a1 a2 a3 进队 Q.rear a1 a2 a3 出队 Q.front a4 a5 a6 Q.rear a4 a5 a6 进队 Q.front Q.rear a4 a5 a6 出队 Q.front 再有元 素进队 会怎样 ？ 队列的顺序表示及实现 队满的三种情况： 1、所有单元都有元素； 2、部分单元有元素； 3、所有单元均无元素。 当队满时再要插入元素，称为上溢。 假上溢：队空间中还有存储单元未使用，但不能再插入元素。 假上溢原因：头、尾指针值总是不断增加，已使用过的单元无法再使用。 解决假上溢的方法： 1、将队中元素依次向队头方向移 动。 缺点：浪费时间。每移动一次 ，队中元素都要移动。 、将队空间设想成一个循环的 表，即分配给队列的个存储单元 可以循环使用，当rear为m时，若向 量的开始端空着，又可从头使用空 着的空间。当front为m时，也是一 样。 Q.front a1 a2 an Q.rear 删除 插入 循环队列 实现方法：模(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 if(!Q.base) exit(OVERFLOW); Q.front =Q.rear=0; return OK; 2、求队列长度 Status QueueLength(SqQueue Q) return (Q.rear-Q.front+Maxsise)%Maxsize; 循环队列算法 3、入队操作：在队尾插入新元素。 Status Enqueue(sqqueue Q.baseQ.rear=e; Q.rear=(Q.rear+1)%Maxsize; return OK; 循环队列算法 4、出队操作：删除队头元素，并返回队头元素的值。 Status DeQueue(SqQueue e=Q.baseQ.front; Q.front=(Q.front+1)%Maxsize; return OK; 队列的应用 二、队