第4章 栈和队列-3

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,页,*,第,4,章 栈和队列,4.3,栈和队列算法实现的,C,语言源程序,4.3.1,栈的顺序存储结构及实现,#include,stdio.h,#include,stdlib.h,#define MAXSIZE 100,typedef,int,ElemType,;,typedef,struct,ElemType,elemMAXSIZE,;,int,top;,SqStack,;/*,顺序栈的类型标识符*,/,第,页,void,OutStack(SqStack,p);/*,此处参数必须与下边函数说明一致*,/,void,InitStack(SqStack,*,p);,void,Push(SqStack,*,p,ElemType,x);,ElemType,Pop(SqStack,*p);,ElemType,GetTop(SqStack,p);,第,页,main(),SqStack,q;,int,i,y,cord,;,ElemType,a;,do,printf(n,);,printf(,n,主菜单,n,);,printf(,n,1,初始化顺序栈,n,);,printf(,n,2,插入一个元素,n,);,printf(,n,3,删除栈顶元素,n,);,printf(,n,4,取栈顶元素,n,);,printf(,n,5,结束程序运行,n,);,printf(,n-n,);,printf,(,请输入您的选择,(1,2,3,4,5),);,scanf(%d,&cord,);,switch(cord),第,页,case 1:,InitStack(&q,);,OutStack(q,);,break;,case 2:,printf(n,请输入插入的数据,a=);,scanf(%d,&a,);,Push(&q,a,);,OutStack(q,);,break;,case 3:a=Pop(,printf(n,a=%d,a);,OutStack(q,);,break;,case 4:y=,GetTop(q,);,printf(n,y=%d,y);,OutStack(q,);,break;,第,页,case 5:exit(0);,while(cordtop=0;,void Push(,SqStack,*,p,ElemType,x),if(p-toptop=p-top+1;,p-,elemp,-top=x;,else,printf(n,Overflow!);,第,页,ElemType,Pop(SqStack,*,p),ElemType,x;,if(p-top!=0),x=p-,elemp,-top;,p-top=p-top,-,1;,return(x);,else,printf(n,Underflow!);,return(,-,1);,第,页,ElemType,GetTop,(,SqStack,p),ElemType,x;,if(p.top!=0),x=,p.elemp.top,;,return(x);,else,printf(n,Underflow!);,return(,-,1);,第,页,void,OutStack(SqStack,p),int,i,j;,if(p.top=0),printf(n,The Stack is NULL.);,for(i=p.top;i0;i,-,),printf(n%2d%6d,i,p.elemi,);,第,页,在上述程序中既包括了每个算法对应的函数代码，也包括在主函数之中对函数的调用。应该注意的是输出函数和取栈顶数据,(,但是不出栈,),函数中形参,SqStack,p,不使用指针，再看主函数的调用语句的实参,q,不用求地址。而进栈、出栈和初始化栈的函数形参,SqStack,*p,使用指针，,在主函数中调用语句的实参,&q,需将地址代入。,第,页,4.3.2,队列的链表存储结构及实现,#include,stdio.h,#include,stdlib.h,#define,ElemType,int,typedef,struct,NodeType,/*,数据元素结点的结构*,/,ElemType,data;,struct,NodeType,*next;,NodeType,;,typedef,struct,/*,队列头、尾指针被封装在一起*,/,NodeType,*front,*rear;,LinkQueue,;/*,队列头尾指针结构体*,/,第,页,NodeType,*,p,*,s,*,h;,void,outlin(LinkQueue,qq,);/*,参数要与下面的函数说明一致*,/,void,creat(LinkQueue,*,qe,);,void,insert(LinkQueue,*,qe,ElemType,x);,ElemType,delete(LinkQueue,*,qe,);,main(),LinkQueue,que,;,ElemType,y,x;,int,i,x,y,cord;,do,printf(n,主菜单,n);,printf,(1,建立链表队列,n);,printf,(2,入队一个元素,X n);,printf,(3,出队一个元素,n);,printf,(4,结束程序运行,n);,第,页,printf(-n,);,printf,(,请输入您的选择,(1,，,2,，,3,，,4);,scanf(%d,&cord,);,switch(cord),case 1:,creat(,/*,重要，这是头尾指针结点*,/,outlin(que,);,break;,case 2:,printf(n,x=?);,scanf(%d,&x,);,insert(&que,x,);,outlin(que,);,break;,case 3:y=,delete(&que,);,printf(n,x=%d,y);,outlin(que,);,break;,case 4:exit(0);,while(cordnext;/*,指向第一个数据元素结点*,/,while(p!=NULL),printf,(data=%4dn,p-data);,p=p-next;,printf(n,outend,nn);,void,insert(LinkQueue,*,qe,int,x),/*,值为,x,的结点入队*,/,s=(,NodeType,*,),malloc(sizeof(NodeType,);,s-data=x;s-next=NULL;,qe,-rear-next=s;,qe,-rear=s;,第,页,ElemType,delete(LinkQueue,*,qe,),ElemType,x;,if(,qe,-front=,qe,-rear),printf,(,队列为空。,n);x=0;,else p=,qe,-front-next;,qe,-front-next=p-next;,if(p-next=NULL),qe,-rear=,qe,-front;/*,防止尾指针丢失*,/,x=p-data;,free(p);,return(x);,第,页,void,creat(LinkQueue,*,qe,),int,i,n,x,;,h=(,NodeType,*,),malloc(sizeof(NodeType,);,h-next=NULL;/,建立一个空队列,printf(n,=);,scanf(%d,&n,);/,预先进队,n,个数据元素,for(i=1;i=n;i+),printf(n,data=);,scanf(%d,&x,);,insert(qe,x,);,第,页,在上述程序中既包括了每个算法对应的函数代码，也包括在主函数之中对函数的调用。虽然队列是链表结构，但是头、尾指针被封装在一个结构体之中，因此在主函数中代表队列的是,LinkQueue,que,，,而不是一个指针。应该注意的是输出函数中形参,LinkQueue,qq,不使用指针，所以主函数的调用语句的实参,que,不用求地址，这是传值调用。,第,页,在进队、出队和建立一个队列的函数中形参,LinkQueue,*,qe,采用指针，所以在,主函数中调用语句的实参,&,que,需要将地址代入，这是传址调用。,链表队列的实现与单链表有着明显的区别，关键在于头、尾指针组成的结构体。,第,页,习 题 四,1.,假定有编号为,A,、,B,、,C,、,D,的四辆列车，顺序开进一个栈式结构的站台，请写出开出车站站台的列车顺序有几种？,(,注：列车由站台开出的方向假设是自左向右。每一列车均可自左进栈、出栈向右开出站台，但不允许出栈后回退。列车也可以不进栈直接开出站台。,),写出每一种可能的序列。,2.,已知堆栈采用链式存储结构，初始时为空，试画出,a,、,b,、,c,、,d,四个元素依次进栈以后堆栈的状态。在此基础上出栈一个数据元素，再画出此时的栈状态。,第,页,3.,写出链栈的取栈顶元素和置栈空的算法。,4.,写出多个链表栈中取第,j,个链表栈顶元素值的算法。,5.,写出计算表达式,3+4/25*8,-,6,时操作数栈和运算符栈的变化情况。,6.,对于给定的,M,进制的正整数,(,例如十进制,),，转换为相应的,N,进制正整数,(,如二进制、八进制和十六进制,),，并且输出。,(1),写出递归算法。,(2),写出非递归算法,(,需要使用栈,),。,第,页,7.,已知,n,为大于等于零的整数，试写出计算下列递归函数,f(n),的递归算法。,f(n)=,第,页,8.,阿克曼函数,(Ackermanns function),定义如下：,akm(m,n,)=,之所以研究该函数，是因为,m,和,n,值的较小增长都会引起函数值的极快增长。设计运用,(1),递归算法的源程序，上机运行。,(2),非递归算法的源程序，上机运行，并进行比较。,第,页,9,二项式,(a+b),n,展开后，其系数构成杨辉三角形，利用队列写出打印杨辉三角形的前,n,行的程序。,10.,课文中规定：无论是循环队列还是链表队列，队头指针总是指向队头元素的前一位置，队尾指针指向队尾元素。试画出有,2,个元素,A,、,B,的不同存储结构的图示，及将这,2,个元素出队后循环队列和链表队列的状态示意图。,11.,对于一个具有,m,个单元的循环队列，写出求队列中元素个数的公式。,第,页,12.,对于一个具有,n,个单元,(n2),的循环队列，若从进入第一个元素开始，每隔,t1,个时间单位进入下一个元素，同时从进入第一个元素开始，每隔,t2(t2t1),个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。,13.,假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点,(,注意不允许设置队头指针,),，试编写出相应的置空队列，入队列和出队列的算法。,第,页,