《数据结构第3章栈和队.ppt》由会员分享，可在线阅读，更多相关《数据结构第3章栈和队.ppt（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3章 栈和队列本章主要内容n 栈的概念、存储结构及其基本操作栈的概念、存储结构及其基本操作n 栈的应用栈的应用n 栈与递归栈与递归n 队列的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作n 队列的应用队列的应用3.1 3.1 栈栈n栈的定义n栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。n进行插入和删除的称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，称为栈底。a1,a2,a3,.,an 插入和删除端插入和删除端图图 3-1栈的操作入栈演示abcSP单击标题单击标题开始演示！开始演示！下一页栈的操作出栈演示abcSP单击标题单击标题开
2、始演示！开始演示！下一页栈的特点栈的特点n后进先出（后进先出（Last In First Out），简称为），简称为LIFO线性表。线性表。n举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。n举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。栈的基本操作n1、栈初始化：Init_Stack(S)n 初始条件：栈S不存在n操作结果：构造了一个空栈。n 2、销毁栈：Destroy_Stack(S)n初始条件：栈S已存在n操作结果：销毁一个已存在的栈。n 3、判栈空：
3、Empty_Stack(S)n操作结果：若S为空栈返回为1，否则返回为0。栈的基本操作n4、入栈：Push_Stack(S，x)n 初始条件：栈S已存在 n 操作结果：在栈s的顶部插入一个新元素x，x成为新的栈顶元素。栈发生变化n 5、出栈：Pop_Stack(S)n 初始条件：栈S存在且非空n 操作结果：栈S的顶部元素从栈中删除，栈中少了一个元素。栈发生变化n 6、取栈顶元素：GetTop_Stack(S)n 初始条件：栈S存在且非空n 操作结果：栈顶元素作为结果返回，栈不变化栈的顺序存储n栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。n 类型定义如下
4、所示：#define MAXSIZE 100 typedef struct DataType dataMAXSIZE;int top;SeqStack,*PSeqStack;定义一个指向顺序栈的指针：PSeqStack S;S=(PSeqStack)malloc(sizeof(SeqStack);n1、初始化栈PSeqStack Init_SeqStack(void)/*创建一顺序栈，入口参数无，返回一个指向顺 序栈的指针，为零表示分配空间失败*/PSeqStack S;S=(PSeqStack)malloc(sizeof(SeqStack);if(S)S-top=-1;return S;初始
5、化后内存的存储映象如下页所示顺序存储的栈的基本操作算法n2、销毁栈、销毁栈n顺序栈的销毁操作是初始化操作的逆运算。由于要修改栈的指针变量，所以要将指针地址传给该函数。void Destroy_ SeqStack(PSeqStack*SeqStackPoint)/*销毁顺序栈，入口参数：为要销毁的顺序栈指针地址*/if(*SeqStackPoint)free(*SeqStackPoint);*SeqStackPoint=NULL;return;主程序中如何调用，思考，请看下页顺序存储的栈的基本操作算法 main()PSeqStack S;S=Init_SeqStack();Destroy_ Se
6、qStack(&S);顺序存储的栈的基本操作算法顺序存储的栈的基本操作算法n3 3、判栈空、判栈空n判断栈中是否有元素，只需判断top是否等于-1int Empty_SeqStack(PSeqStack S)/*判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，0表示非空*/if(S-top=-1)return 1;else return 0;n4、入栈、入栈n入栈操作是在栈的顶部进行插入一个元素。首先判断栈是否已满，若满退出，否则，由于栈的top指向栈顶，只要将入栈元素赋到top+1的位置同时top+即可 int Push_SeqStack(PSeqStack S,DataType x)
7、/*入口参数：顺序栈，返回值：1表示入栈成功，0 表示失败。*/if(S-top=MAXSIZE-1)return 0;/*栈满不能入栈*/else S-top+;S-dataS-top=x;return 1;顺序存储的栈的基本操作算法n5、出栈、出栈 出栈操作是在栈的顶部进行删除操作，首先判断栈是否为空，若空退出，否则，由于栈的top指向 栈顶，只要修改top为top-1即可。int Pop_SeqStack(PSeqStack S,DataType*x)/*入口参数：顺序栈，返回值：1表示出栈成功，0表示失败。*/if(Empty_SeqStack(S)return 0;/*栈空不能出栈*
8、/else *x=S-dataS-top;S-top-;return 1;顺序存储的栈的基本操作算法n6、取栈顶元素、取栈顶元素n取栈顶元素操作是取出栈顶指针top所指的元素值。先判断栈是否为空，若空退出，否则返回top 所指单元的值int GetTop_SeqStack(PSeqStack S,DataType*x)/*取出栈顶元素，取出栈顶元素，入口参数：顺序栈，被取出的元素指针，这里用入口参数：顺序栈，被取出的元素指针，这里用 指针带出栈顶值返回值：指针带出栈顶值返回值：1表示成功，表示成功，0表示失败。表示失败。*/if(Empty_SeqStack(S)return 0;/*栈空栈空
9、*/else *x=S-dataS-top;/*栈顶元素存入栈顶元素存入*x中中*/return(1);顺序存储的栈的基本操作算法n若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构“链栈”。链栈通常用一个无头结点的单链表表示。n对于单链表，在首端插入删除结点要比尾端相对地容易一些，所以，将单链表的首端作为栈顶端，即将头指针作为栈顶指针。下页给出链栈的存储示意图栈的链式存储栈的链式存储结构C定义 定义栈的节点元素：typedef struct node DataType data;struct node *next;StackNode,*PStackNode;定义栈
10、：定义栈：typedef struct PStackNode top;LinkStack,*PLinkStack;PLinkStack S;S=(PLinkStack)malloc(sizeof(LinkStack);n1、初始化空栈 PLinkStack Init_LinkStack（void）/*初始化链栈，入口参数：空，返回值：链栈指针，null表示初始化失败*/PLinkStack S;S=(PLinkStack)malloc(sizeof(LinkStack);if(S)S-top=null;return(S);链栈各项基本操作的算法n2、销毁栈、销毁栈void Destroy_Li
11、nkStack(PLinkStack *LS)/*销毁链栈，入口参数：为要销毁的链栈指针地址，无返回值*/PStackNode p,q；if(*LS)p=*LS-top;while(p)q=p;p=p-next;free(q);free(*LS);*LS=null;链栈各项基本操作的算法n3、判栈空int Empty_LinkStack（PLinkStack S）/*判断链栈是否为空，入口参数：链栈指针，返回值：1表示栈空，0表示栈非空*/return(S-top=null);链栈各项基本操作的算法n4、入栈 int LinkStack Push_LinkStack（PLinkStack S,
12、DataType x）PStackNode p;p=(PStackNode)malloc(sizeof（StackNode）);if(!p)printf(“内存溢出”);return(0);p-data=x;p-next=S-top;S-top=p;return(1);链栈各项基本操作的算法n5、出栈int Pop_LinkStack(PLinkStack S,DataType*x)PStackNode p;if(Empty_LinkStack(S)printf(“栈空，不能出栈”);return(0);*x=S-top-data;p=S-top;S-top=S-top-next;free(p
13、);return(1);链栈各项基本操作的算法n6、取栈顶元素int GetTop_LinkStack(PLinkStack S,DataType *x)/*返回值：1表示出栈成功，0表示失败*/if(Empty_LinkStack(S)printf(“栈空”);return(0);*x=S-top-data;return(1);返回返回链栈各项基本操作的算法3.2 栈的应用举例n数制转换问题n将十进制数N转换为r进制的数，其转换方法利用辗转相除法n算法思想如下：n（1）初始化栈，初始化N为要转换的数，r为进制数n（2）判断N的值，为0转（4），否则N%r 压入栈s中n（3）用N/r 代替 N
14、转（2）n（4）出栈，出栈序列即为结果数制转换算法typedef int DataType;int conversion(int N，int r)PSeqStack S;DataType x;/*定义一个顺序栈定义一个顺序栈*/if(!r)printf(“基数不能为基数不能为0”);return(0);S=Init_SeqStack();/*初始化栈初始化栈*/if(!S)printf(“栈初始化失败栈初始化失败”);return(0);while(N)Push_SeqStack(S，N%r);/*余数入栈余数入栈*/N=N/r;/*商作为被除数继续商作为被除数继续*/while(!Empty
15、_SeqStack(S)/*直到栈空退出循环直到栈空退出循环*/Pop_SeqStack(S,&x);/*弹出栈顶元素弹出栈顶元素*/printf(“%d”，x);/*输出栈顶元素输出栈顶元素*/Destroy_ SeqStack(&S);/*销毁栈销毁栈*/3.3 栈与递归n递归定义n递归是程序设计中最常用的设计方法之一n递归的定义：若一个对象部分地包括它自己，或用它自己给自己定义，则称这个对象是递归的n递归分为直接递归和间接递归n递归的程序思路清晰，编程简化递归的例子求n的阶乘：-数值计算 int fact(int n)if(n=1)return 1;else return(n*fact(
16、n-1);汉诺塔问题：-非数值求解 void Hanio(int n,char a,char b,char c)if(n=1)move(n,a,c);else Hanio(n-1,a,c,b);move(n,a,c);Hanio(n-1,b,a,c);非数值计算的递归n对数值计算而言：有递推公式的可直接写成递归算法如：求xn、费波那契数列、阿克曼函数等n对非数值问题而言：如果问题是递归定义的可用递归算法，如广义表、树等，但具有递归定义的问题毕竟有限，对于一般问题求解，如果具有下列三个性质，就能采用递归算法。1）大问题能分解成若干个子问题；2）子问题或者是一个定值（直接解）或者是与 大问题具有同
17、样性质的问题；3）子问题经过不断分解在最小尺度上有直接 解，即分解过程最终能结束也就是递归有结 束条件。递归过程的调用和返回n递归函数的递归过程：在递归进层（ii+1层）时系统需要做三件事：n 保留本层参数与返回地址（将所有的实在参 数、返回地址等信息传递给被调用函数保存）；n 给下层参数赋值（为被调用函数的局部变量 分配存储区）；n 将程序转移到被调函数的入口。递归过程的调用和返回n从被调用函数返回调用函数之前，递归退层（ii+1层）系统也应完成三件工作：n 保存被调函数的计算结果；n 恢复上层参数（释放被调函数的数据区）；n 依照被调函数保存的返回地址，将控制转 移回调用函数。下页给出下页
18、给出N!递归调用过程示意图递归调用过程示意图递归函数的非递归化（略）n递归算法具有两个特性：n递归算法是一种分而治之、把复杂问题分 解为简单问题的求解方法，对求解某些复杂 问题，递归算法是有效的。n递归算法的时间效率差，因为需要不断地 进栈和出栈。人们常常将递归改写成非递归，可机械地改写。递归设计举例1）用递归写出求数组中n个元素之和n求n个元素的和与求n1个元素的和 是相同的过程 int sum(int a,int n)/*求数组a中的n个元素之和*/if(n=0)/*最小尺度当n1时，时，Perm(R)由由(r1)Perm(R1),(r2)Perm(R2)，(rn)Perm(Rn)构成。构
19、成。算法如下页所示算法如下页所示全排列算法产生产生Perm(R)的递归算法如下，设的递归算法如下，设R为一整型数组为一整型数组int listN void Perm(int list,int k,int m)/*求下标求下标k 至至m元素的全排列元素的全排列*/int i;if(km)for(i=0;i=m;i+)printf(%d,listi);printf(n);else for(i=k;i=m;i+)Swap(list,k,i);/*依次将依次将(ri)移至待排数组第一位置移至待排数组第一位置*/Perm(list,k+1,m);/*递归求递归求Perm(Ri),构成构成(ri)Perm
20、(Ri),*/Swap(list,k,i);/*将将(ri)换回原位置换回原位置*/递归设计举例3）用递归写出字符串倒置的算法n分析：将字符串倒置，可以将第一个元素和最后一个元素调换，再把剩下的字符串倒置，而剩下的字符串长度就在原来的长度上减2,如果字符串的串长1则无需倒置直接返回 字符串倒置算法void ConverseStrt(char *Str，int start，int end)/*将字符串倒置，Str为字符串，strat和end为字符数 组的首尾下标*/if(end-start1)return;/*Str的串长=1*/else Strstart Strend /*交换字符*/Conv
21、erseStrt(Str,start+1,end-1);/*Str的串长1，字符串的首尾元素调换，再将去掉 首尾元素的字符串调换*/递归设计举例4）火车进站问题 编号为A1，A2，A3，,An（A1 A2A30 (1)F(i,0)=F(i-1,1),i0 (2)F(i,j)=F(i-1,j+1)+F(i,j-1),i0,j0 (3)其中：F(i,j)表示站台外有i列火车，站台内有j列火车F(0,j)表示站台外没有火车，站台内有j列火车F(i,0)表示站台内没有火车，有i列火车在站台外火车进站问题int Train_into_PlatForm(int i,int j)if(i=0)return
22、1;/*火车没有，或者全部在站台内*/else if(j=0)return Train_into_PlatForm(i-1,1);else return Train_into_PlatForm(i-1,j+1)+Train_into_PlatForm(i,j-1);调用Train_into_PlatForm(4,0)得到的计算结果为14；取i5，j0，调用算法Train_into_PlatForm(5,0)得到的计算结果为42，与理论计算公式C2nn/n+1是一致的。3.4 队列n队列的定义n队列特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。如下图所示：n先进先出（Firs
23、t In First Out），简称为FIFO线性表。n举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。n举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。队列的特点n初始化队列 n销毁队列n入队 n出队 获取队头元素内容 n判断队列是否为空队列的基本操作n顺序存储顺序存储n链式存储链式存储我们介绍顺我们介绍顺序存储序存储队列的存储结构队列的顺序存储结构如下图所示，顺序存储的队列在内存的中的映像：如下图所示，顺序存储的队列在内存的中的映像：下页给出它的下页给出它的C语言定义：语言定义：定义队列#define MAXSIZE 100 /*队列的最大容量*/typedef
24、struct DataType dataMAXSIZE;/*队列的存储空间*/int front,rear;/*队头队尾指针*/SeqQueue,*PSeqQueue;定义一个指向队列的指针：SeqQueue *Q;Q=(PSeqQueue)malloc(sizeof(SeqQueue);队列的数据区为：队列的数据区为：Q-data0Q-dataMAXSIZE-1队头指针：队头指针：Q-front（0Q-frontMAXSIZE 1）队尾指针：队尾指针：Q-rear（0Q-rearMAXSIZE 1）队列的假溢出？问会出现？问会出现什么问题什么问题一般不采一般不采用用n如何解决顺序存储下队列满
25、的问题如何解决顺序存储下队列满的问题n入队、出队有两种方式：入队、出队有两种方式：n入队时，入队时，Q-rear加加1，Q-rear=MAZXSIZE时时队满队满；出队时，所有的队列元素向前移一位，；出队时，所有的队列元素向前移一位，Q-rear减减1，Q-front始终指向始终指向0位置不变位置不变n入队时，入队时，Q-rear加加1，Q-rear=MAZXSIZE时时队满队满；出队时；出队时Q-fonnt加加1 如何解决假溢出的问题？如何解决假溢出的问题？队列的假溢示意图队列的假溢示意图构造循环队列构造循环队列高地址高地址低地址低地址入队：入队：Q-rear=(Q-rear+1)%MAXS
26、IZE出队：出队：Q-front=(Q-front+1)%MAXSIZE如何判断队列如何判断队列满和空满和空请看下页请看下页判断队列满和空n牺牲一个存储空间，如本书采用队头指针指向的位置不存储元素(也可采用牺牲队尾指针指向的空间)队列空：队列空：Q-front=Q-rear 队列满：队列满：(rear+1)%MAXSIZE=front 通常采用的通常采用的接下来，给出顺序存储的循环队接下来，给出顺序存储的循环队列操作算法：列操作算法：队列基本操作算法n1、队列初始化PSeqQueue Init_SeqQueue()/*返回值：新顺序队列指针，返回值：新顺序队列指针，null表示失败表示失败*/
27、PSeqQueue Q;Q=(PSeqQueue)malloc(sizeof(SeqQueue);if(Q)Q-front=0;Q-rear=0;return Q;n2、销毁队列void Destroy_SeqQueue(PSeqQueue*Q)if(*Q)free(*Q);*Q=null;注意主程序的注意主程序的调用方式调用方式main()PSeqQueue Q;Q=Init_ SeqQueue();Destroy_ SeqQueue(&Q);队列基本操作算法n3、判断队空int Empty_SeqQueue(PSeqQueue Q)/*返回值：1表示为空，0表示非空*/if(Q&Q-fro
28、nt=Q-rear)return(1);else return(0);队列基本操作算法n4、入队 int In_SeqQueue(PSeqQueue Q,DataType x)/*返回值：1表示成功，1表示队满溢出*/if(Q-rear+1)%MAXSIZE=Q-front)printf(队满);return 1;/*队满不能入队*/else Q-rear=(Q-rear+1)%MAXSIZE;Q-dataQ-rear=x;return 1;/*入队完成*/队列基本操作算法n5、出队 int Out_SeqQueue(PSeqQueue Q，DataType*x)/*返回值：1表示成功，1表示
29、队空,出队的元素保存到*x */if(Empty_SeqQueue(Q)printf(队空)；return 1;/*队空不能出队*/else Q-front=(Q-front+1)%MAXSIZE;*x=Q-dataQ-front;return 1;/*出队完成*/队列基本操作算法n6、读队头元素 int Front_SeqQueue(PSeqQueue Q,DataType*x)/*返回值：1表示成功，1表示队空*/if (Q-front=Q-rear)printf(队空)；return 1;/*队空不能得到队头元素*/else *x=Q-data(Q-front+1)%MAXSIZE;re
30、turn 1;/*取队头元素操作完成*/队列的应用：队列的应用：返回返回队列基本操作算法n例1：有n个元素存储在数组An中，设计一个算法，实现将这n个元素循环左移动k（0kn）位。思路：思路：利用队列，将数组的利用队列，将数组的A0至至Ak-1元素事先顺序元素事先顺序放入一个队列中放入一个队列中 然后将数组然后将数组Ak至至An-1元素依次左移元素依次左移k位位再将队列中的保存的数组元素再将队列中的保存的数组元素A0至至Ak-1顺序顺序出队列，依次放入数组的出队列，依次放入数组的An-k至至An-1位置位置3.5 队列的应用循环左移动k位void Array_LeftCircle_Move(i
31、nt A,int n,int k)/*参数参数n代表数组中存储的元素个数，代表数组中存储的元素个数，k代表循环左移动代表循环左移动k位。位。*/int i;PSeqQueue Q=Init_SeqQueue();for(i=0;ik;i+)In_SeqQueue(Q,Ai);/*A0至至Ak-1元素事先元素事先顺序放入队列顺序放入队列*/for(i=k;i=2）的系数值时，可以由i-1行的系数值来获得打印杨辉三角打印杨辉三角 用一个队列，先将上一行的系数值入队列，包括缺用一个队列，先将上一行的系数值入队列，包括缺省的行末尾的系数省的行末尾的系数0（行首的缺省系数（行首的缺省系数0预存在一个预存
32、在一个变量变量s中），中），出队列，每出一个系数出队列，每出一个系数t，用它的值和前面刚出队值，用它的值和前面刚出队值s之和得到下一行相应位置的数值，把刚得到的值之和得到下一行相应位置的数值，把刚得到的值进队列，并把进队列，并把t的值赋给的值赋给s，循环下去，可以得到所需指定行数的杨辉三角循环下去，可以得到所需指定行数的杨辉三角 C算法打印杨辉三角打印杨辉三角void YangHui_trangle(int n)int s=0;int i;int t;PSeqQueue sq=Init_SeqQueue();In_SeqQueue(sq,1);In_SeqQueue(sq,1);for(i=1
33、;i=n;i+,s=0)printf(n);for(int k=0;k=40-4*i;k+=2)printf();/*输出格式控制输出格式控制*/In_SeqQueue(sq,0);for(int j=1;j=i+2;j+)Out_SeqQueue(sq,&t);In_SeqQueue(sq,s+t);s=t;if(j!=i+2)printf(%4d,s);printf(n);Destroy_SeqQueue(&sq);关于队列的链式存储（补充）n队列用链式存储能克服顺序存储的一些不足。n队列既有头指针（删除的位置），又有尾指针 （插入的位置）。n一般情况下，不存在队列满，但存在队列空的情况。n在队列空的情况下插入一个结点，需要同时修改队列头和队列尾指针，同样，当删除只有一个结点的队列时，也需要同时修改队列头和队列尾指针。n一般情况下，链式队列的插入和删除算法比单链表操作简单。返回返回