第四章 栈和队列(jian)

1、第四章 栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性。4.1 栈（stack）栈的定义和特点v定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈v特点：先进后出（FILO）或后进先出（LIFO）ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)栈的运算概述 对栈所施加的运算通常为：v元素进栈v元素出栈读取栈顶元素v检查栈是否为空等4.2栈的顺序存储结构和操作实现 需要使用: 一个数组-顺序存储空间 一个整数-标志栈顶元素的下标位置v实现：一维数组sMtop=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top1

2、23450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈的顺序存储结构所使用的栈数组和栈顶指针同样可以定义在一个记录类型中,假定该记录类型有StackSq表示,则定义为:(教材定义(p78) struct StackSq ElemType stackMaxSize; int top; ;若要对存储栈的数组空间采用动态分配，则struct StackSq结构类型可定义为： struct Stac

3、kSq ElemType* stack; /*存栈元素的数组指针*/ int top; /*存栈顶元素的下标位置*/ int MaxSize; /*存stack数组长度*/ ;算法描述:(演示sxzhan)v栈的初始化算法InitStack(struct StackSq *S) S-MaxSize=10; S-stack=malloc(10*sizeof(ElemType); S-top=-1; v判栈空int EmptyStack(struct StackSq *S)if(S-top=-1)return 1;else return 0;v进栈算法若top的值为-1表示栈空则: 首先使top增

4、1,用以指示新的栈顶位置,然后再把元素赋值到这个空位置上。v进栈void Push(struct StackSq* S, ElemType x) S-top+; S-stackS-top=x; v出栈ElemType Pop(struct StackSq* S) if(S-top=-1) printf(zhan is free!n); exit(1); S-top-; return S-stackS-top+1; v出栈算法 每次从栈中弹出一个元素时，首先取出栈顶元素，然后使top减1，指示出前一个元素成为新的栈顶元素。4.3 栈的链接存储结构和操作实现 与线性表的链接存储结构相同,也是通过由

5、结点构成的单链表实现的,此时表头指针称为栈顶指针,由栈顶指针指向的表头结点被称为栈顶结点,整个单链表被称为链栈,对链栈的插入与删除操作都是在单链表的表头进行的,其时间复杂度为O(1)。假定链栈的结点定义与前单链表同:struct sNode ElemType data; struct sNode* next; ;栈顶 .topdata next栈底l入栈算法 .栈底toptopxpp=malloc(sizeof(struct sNode );P-data=x;P-next=top;top=p;栈顶 .topdata next栈底l出栈算法top .栈底topqq=top;top=top-nex

6、t;free(q);l初始化算法void InitStack(struct sNode* HS)*HL=NULL;l向链栈中插入一个元素向链栈中插入一个元素void Push(struct sNode* HS, ElemType x) /*为插入元素获取动态结点*/struct sNode *newp;newp=malloc(sizeof(struct sNode); if(newp=NULL) printf(内存动态空间用完，退出运行!n); exit(1); /*给新分配的结点赋值*/ newp-data=x; /*向栈顶插入新结点*/newp-next=*HS; *HS=newp; l从

7、链栈中删除一个元素并返回它从链栈中删除一个元素并返回它ElemType Pop(struct sNode* HS) struct sNode* p; ElemType temp; /*对于空栈则退出运行*/if(*HS=NULL) printf(栈空无法删除!n); exit(1); /*暂存栈顶结点指针,并使栈顶指针指向下一结点*/p=*HS; *HS=p-next; /*暂存原栈顶元素以便返回,同时回收原栈顶结点*/temp=p-data; free(p); /*返回原栈顶元素*/ return temp; 4.4 栈的简单应用举例 例4-1:从键盘上输入一批整数,然后按照相反的次序打印出

8、来(以TC环境演示)(:lxzhany1)void main()struct StackSq a;int x;InitStack(&a);printf(input a group numbers untill -1n);scanf(%d,&x);while(x!=-1)Push(&a,x); scanf(%d,&x);while(!EmptyStack(&a)printf(%d,Pop(&a);printf(n); 例4-3:把十进制整数转换为二至九之间的任一进制输出v多进制输出：例 把十进制数159转换成八进制数(159)10=(237)815

9、981982802 3 7 余 7余 3余 2toptop7top73top732:lxjinzhizh 包括包括sxzcz.c 例例4-4 求解正整数n的阶乘（n!）。 由数学知识可知，正整数n的阶乘等于n乘以n-1的阶乘，即n!=n*(n-1)!，并且规定0的阶乘为1。设函数f(n)=n!，则f(n)可表示为： 1 (n=0) f(n)= n*f(n-1) (n0) 在这里n=0为终止条件，使函数返回1，n0实现调用，由n的值乘以f(n-1)的返回值求出f(n)的值。4.6 栈与递归用C语言编写出求解n!的函数为： long f(int n) if(n=0) return 1; else

10、return n*f(n-1); 上述调用和返回过程可形象地表示如图。递归定义: 当求解一个问题时, 是通过求解与它具有同样解法的子问题而得到的,这就是递归。递归算法： 一个递归的求解问题必然包含有终止递归的条件，当满足一定条件时就终止向下递归，从而使最小的问题得到解决，最后解决整个问题。递归算法的实现： 执行递归函数是通过自动使用栈自动使用栈来实现的，栈中的每个元素包含有递归函数的每个参数域，每个局部变量域和调用后的返回地址域。每次调用时，都把相应的值压入栈中，每次调用结束时，都按照本次返回地址返回到指定的位置执行，并且自动进行一次退栈操作。递归如何使用栈r主程序主程序srrrs子过程子过程

11、1rst子过程子过程2rst子过程子过程3例例4-6Tower of Hanoi问题v问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：l每次只能移一个圆盘l圆盘可在三个塔座上任意移动l任何时刻，每个塔座上不能将大盘压到小盘上v解决方法：ln=1时，直接把圆盘从A移到Cln1时-u先把上面n-1个圆盘从A移到Bu然后将n号盘从A移到Cu再将n-1个盘从B移到C。l即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Han

12、oi问题首先,将一个盘子从一个塔座移到另一个塔座的算法实现:void move(int h,char c,char f) printf(%d:%c-%cn,h,c,f); 其次,将n个盘子从一个塔座移到另一个塔座的递归算法实现:void hanoi(int n,char x,char y,char z) if(n=1) move(1,x,z); else hanoi(n-1,x,z,y); move(n,x,z); hanoi(n-1,y,x,z); /*Hanoi.txt*/ main() int m; printf(Input the number of disks:); scanf(%d

13、,&m); printf(The steps to moving %3d disks:n,m); hanoi(m,A,B,C);(0) v算法调用：4.7 队列队列的定义及特点v定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表l队尾(rear)允许插入的一端l队头(front)允许删除的一端v队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an) 队列的顺序存储结构可以被定义在一个结构体类型中，假定该记录类型用QueueSq表示，则定义为： struct QueueSq ElemType queueMaxSize

14、; int front, rear, len; ;若要对存储队列的数组空间采用动态分配，则QueueSq结构类型可定义为： struct QueueSq ElemType *queue; /*指向存储队列的数组空间*/ int front, rear, len; /*队首指针、队尾指针、队列长度变量*/ int MaxSize; /*queue数组长度*/ ;队列的顺序存储结构front=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示

15、队尾元素；front指示队头元素前一位置初值front=rear=-1空队列条件：front=rear 入队列： queue+rear=x; 出队列：x= queue+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfrontv存在问题设数组维数为M，则：l当front=-1,rear=M-1时，再有元素入队发生溢出真溢出l当front-1,rear=M-1时，再有元素入队发生溢出假溢出v假溢出解决方案l循环队列u基本思想：把队列设想成环形，让queue0接在queueM-1之后，若rear+1=M,则令rear=0;0M-11fr

16、ontrear.u实现：利用“模”运算u入队： rear=(rear+1)%M; queuerear=x;u出队： front=(front+1)%M; x=sqfront;u队满、队空判定条件012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear解决方案：少用一个元素空间 队空：front=rear 队满：(rear+1)%M=front1. 初始化队列算法初始化队列算法隐含分配用于存储队列的固定大小的动态存储空间，假定动

17、态存储空间的大小为10。 void InitQueue(struct QueueSq* Q) /*置队列空间初始最大长度为10*/ Q-MaxSize=10; /*动态存储空间分配*/ Q-queue=malloc(10*sizeof(ElemType); /*置队列为空*/ Q-front=Q-rear=0; 2. 向队列插入元素向队列插入元素void EnQueue(struct QueueSq* Q, ElemType x) /*当队列满时进行动态重分配*/if(Q-rear+1)%Q-MaxSize=Q-front) againMalloc(Q); /*求出队尾的下一个位置*/ Q-r

18、ear=(Q-rear+1)%Q-MaxSize; /*把item的值赋给新的队尾位置*/Q-queueQ-rear=x; 3. 从队列中删除元素并返回从队列中删除元素并返回 ElemType OutQueue(struct QueueSq* Q) /*若队列为空则终止运行*/ if(Q-front=Q-rear) printf(队列已空，无法删除!n); exit(1); /*使队首指针指向下一个位置*/ Q-front=(Q-front+1)%Q-MaxSize; /*返回队首元素*/ return Q-queueQ-front; 队列的链式存储结构 struct QueueLk stru

19、ct sNode* front; /*队首指针*/ struct sNode* rear; /*队尾指针*/ ; 其中sNode结点类型重写如下： struct sNode ElemType data; /*值域*/ struct sNode* next; /*链接指针域*/ ;frontrearx入队xfrontreary入队xyfrontrearx出队xyfront rear空队front reary出队1. 初始化链队初始化链队void InitQueue(struct QueueLk* HQ) HQ-front=HQ-rear=NULL; /*把队首和队尾指针置为空*/ 2. 向链队中插入一个元素向链队中插入一个元素 void EnQueue(struct QueueLk* HQ, ElemType x) /*得到一个由newp指针所指向的新结点*/ struct sNode* newp;newp=malloc(sizeof(struct sNode); if(newp=NULL) printf(内存动态空间用完，退出运行!n); exit(1); /*把x的值赋给新结点的值域