数据结构ch3栈和队列.ppt

第三章 栈和队列,教学目的与要求： 1、掌握栈和队列的特点、基本运算； 2、理解栈的队列的应用。 3、理解递归的概念、递归问题的递归求解方法 4、理解递归过程的机制 教学重点：栈和队列在两种存储结构上实现的基本运算。 教学难点：循环队列中对边界条件的处理，对递归的理解。 教学时数：4学时 教学内容： 栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。栈和队列被广泛应用于各种程序设计中。递归的应用。,栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS 3.1 栈（stack，也叫堆栈） 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO）,栈的ADT ADT Stack 数据对象：Dai |ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ,D, i=2,.,n 约定an端为栈顶，a1为栈底。 基本运算 初始化栈InitStack(S) 设置一个空栈S。 压栈Push(S,x) 将元素x插入栈S中，使x成为栈S的栈顶元素。 出栈Pop(S,x) 当栈S不空时，由x返回栈顶元素，并从栈中删除栈顶元素 取栈顶元素GetTop(S,x) 若栈S不空，则由x返回栈顶元素。 判栈空Empty(S) 若栈S为空栈，结果为1，否则结果为0。 ADT Stack,栈的存储结构 顺序栈 实现：一维数组sM,栈顶指针top,指向实际栈顶 后的空位置，初值为0,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow),栈空,#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */ #define STACKINCREMENT 2 /* 存储空间分配增量 */ typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;,顺序栈的定义:,注意： 顺序栈中元素用向量存放; 栈底位置是固定不变的，可设置在向量两端的任意一个端点; 栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置;,入栈算法,基本思路： (1) 检查栈是否已满； (2) 若满则追加一个元素的内存空间； (3) top指针向上加一位；,算法描述： ENTER,注意： “上溢“现象-当栈满时，再做进栈运算产生空间溢出的现象。上溢是一种出错状态，应设法避免。,出栈算法,基本思路： (1) 检查栈是否空； (2) 若空则返回错误值； (3) top指针向下减一位；,算法描述： ENTER,注意： S-top0表示空栈 “下溢”现象当栈空时，做退栈运算产生的溢出现 象。下溢是正常现象，常用作程序控制转移的条件。,在一个程序中同时使用两个栈,两个栈共享一段向量空间,链栈,结点定义,入栈算法,出栈算法,typedef struct node int data; struct node *next; JD;,ENTER,ENTER,栈的应用 程序运行中的函数及过程的嵌套调用,例 递归的执行情况分析,递归过程及其实现 递归：函数直接或间接的调用自身叫递归 实现：建立递归工作栈,void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i=w;+i) printf(“%3d”,w); printf(“n“); ,运行结果： 1， 2，2 ， 3，3 ，3 ，,递归调用执行情况如下：,递归的实现 采用递归算法具备的条件 所需解决的问题可以转化成一个子问题，而解决子问题的方法与原始问题的解决方法相同，只是处理的对象不同，并且它们的某些参数是有规律的变化的。 必须具备终止递归的条件。,递归的实现机制 1 在计算机中实现函数调用时，需要先完成以下任务 分配调用过程函数所需要的数据区； 保存返回地址，传递参数信息； 把控制权转移给被调用函数；,2 被调用函数执行完成，需要返回到调用函数时，需要完成以下工作： 保存返回时的有关信息（计算结果等），返回调用函数的地址 释放被调用函数占用的数据区； 把控制权按调用时保存的返回地址转移到调用函数中的调用语句的下一条语句。,3 为了保证递归过程每次调用和返回的正确执行，必须解决调用时的参数传递和返回地址问题。每一层递归调用所需保存的信息构成一个工作记录，通常包括如下内容： 返回地址：即上一层中本次调用自己的语句的后继语句处； 在本次过程调用时，与形参结合的实参值。包括函数名、引用参数与数值参数等； 本层的局部变量值。,函数递归时的活动记录,Tower of Hanoi问题 问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则： 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻，每个塔座上不能将大盘压到小盘上,解决方法： n=1时，直接把圆盘从X移到Z n1时，先把上面n-1个圆盘从X移到Y,然后将n号盘从X移到Z,再将n-1个盘从Y移到Z。 即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题。 算法：,执行情况： 递归工作栈保存内容：形参n,x,y,z和返回地址 返回地址用行编号表示,ENTER,main() int m; printf(“Input number of disks”); scanf(“%d“, (8) (9) ,main() int m; printf(“Input the number of disks scanf(“%d“, (8) (9) ,main() int m; printf(“Input the number of disks scanf(“%d“, (8) (9) ,main() int m; printf(“Input the number of disks scanf(“%d“, (8) (9) ,3.2 队列 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。 队尾(rear)允许插入的一端 队头(front)允许删除的一端 队列特点：先进先出(FIFO),双端队列,链队列 结点定义,typedef struct node int data; struct node *next; JD,*QueuePtr;,设队首、队尾指针front和rear, front指向头结点，rear指向队尾,typedef struct QueuePtr front,rear; /* 队头、队尾指针 */ LinkQueue;,入队算法,出队算法,ENTER,ENTER,队列的顺序存储结构 - 循环队列 实现：用一维数组实现sqM,J1,J2,J3,设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素前一位置 初值front=rear=-1,空队列条件：front=rear 入队列：sq+rear=x; 出队列：x=sq+front;,存在问题 设数组维数为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出真溢出 当front-1,rear=M-1时，再有元素入队发生溢出假溢出 解决方案 队首固定，每次出队剩余元素向下移动浪费时间 循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,实现：利用“模”运算 入队： rear=(rear+1)%M; sqrear=x; 出队： front=(front+1)%M; x=sqfront; 队满、队空判定条件,队空：front=rear 队满：front=rear,解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=front,入队算法：,出队算法：,ENTER,ENTER,小结： 栈和队列是两种常见的数据结构，它们都是运算受限的线性表。栈的插入与删除均在栈顶进行，它是后进先出线性表；队列的插入在队尾，而删除在队头，它是先进先出的线性表。当解决具有先进先出（或后进先出）特性的实际问题时，可以使用队列（或栈）这种数据结构来解决。,Status Push(SqStack *S,SElemType e) / 插入元素e为新的栈顶元素 if(*S).top-(*S).base=(*S).stacksize) / 栈满，追加存储空间 (*S).base=(SElemType*)realloc (*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); / 存储分配失败 (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; /赋值，并且top指针向上加一位 return OK; ,back,Status Pop(SqStack *S,SElemType *e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if(*S).top=(*S).base) /判断是否栈空 return ERROR; *e=*-(*S).top; /把栈顶元素赋值给e，top指针向下移一位 return OK; ,back,Status Pop(SqStack *S,SElemType *e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if(*S).top=(*S).base) /判断是否栈空 return ERROR; *e=*-(*S).top; /把栈顶元素赋值给e，top指针向下移一位 return OK; ,back,JD *lzjz(JD *top,int x) JD *p; p=(JD *)malloc(sizeof(JD); p-data=x; p-next=top; top=p; return(p); ,back,JD *lztz(JD *top,int *p) JD *q; if(top!=NULL) q=top; *p=top-data; top=top-link; free(q); return(top); ,back,int c=0; / 全局变量，搬动次数 void move(char x,int n,char z) / 第n个圆盘从塔座x搬到塔座z printf(“第%i步: 将%i号盘从%c移到%cn“,+c,n,x,z); void hanoi(int n,char x,char y,char z) / 将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘 / 按规则搬到塔座z上。y可用作辅助塔座 if(n=1) /递归终止条件 move(x,1,z); /将编号为1的圆盘从x移到z else hanoi(n-1,x,z,y); / 将x上编号为1至n-1的圆盘移到y，z作辅助塔 move(x,n,z); /将编号为n的圆盘从x移到z hanoi(n-1,y,x,z); / 将y上编号为1至n-1的圆盘移到z，x作辅助塔 ,back,Status EnQueue(LinkQueue *Q,QElemType e) /* 插入元素e为Q的新的队尾元素 */ /生成队尾节点 QueuePtr p=(QueuePtr)malloc(sizeof(QNode); if(!p) /存储分配失败 exit(OVERFLOW); p-data=e; p-next=NULL; (*Q).rear-next=p; /入队列 (*Q).rear=p; return OK; ,back,typedef struct node int data; struct node *next; QNode,*QueuePtr;,Status DeQueue(LinkQueue *Q,QElemType *e) /* 队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */ QueuePtr p; if(*Q).front=(*Q).rear) /判断队列是否为空 return ERROR; p=(*Q).front-next; *e=p-data; /用e来存储对头元素的数据 (*Q).front-next=p-next; /出队列 if(*Q).rear=p) /判断队列是否为空 (*Q).rear=(*Q).front; free(p); return OK; ,back,typedef struct node int data; struct node *next; QNode,*QueuePtr;,Status EnQueue(SqQueue *Q,QElemType e) /* 插入元素e为Q的新的队尾元素 */ if(*Q).rear+1)%MAXQSIZE=(*Q).front) / 队列满 return ERROR; (*Q).base(*Q).rear=e; /入队列 (*Q).rear=(*Q).rear+1)%MAXQSIZE; return OK; ,back,typedef struct QEl