栈与队列操作的实现完整版数据结构版

1、#include stdio.h#include stdlib.h#include string.htypedef int status; /定义函数类型为int型#define ok 1 /定义ok为1#define error 0 /定义error为0/*栈的顺序式存储*/typedef char selemtype20; /定义selemtype类型为char型数组#define stack_init_size 100 /栈的存储空间初始分配量#define stackincrement 10 /栈的存储空间分配增量typedef structselemtype *base; /在栈构造

2、之前和销毁之后,base的值为null selemtype *top; /栈顶指针int stacksize; /当前已分配的储存空间,以元素为单位sqstack;status initstack(sqstack &s)/构造一个空战s.base=(selemtype *)malloc(stack_init_size * sizeof(selemtype);if(!s.base) printf(储存分配失败!nn);exit(error);s.top=s.base; s.stacksize=stack_init_size;printf(nt建栈成功!nn);return ok;/initsta

3、ckstatus stacklength(sqstack s)/返回s的元素个数return s.top-s.base;/stacklengthstatus stacktraverse(sqstack s)/若栈不为空,输出栈中的所有元素if(s.top=s.base)printf(栈目前为空!nn);return error;printf(栈中目前的数据如下所示:n);printf(ttop-n);while(s.top!=s.base)s.top-;if(s.top=s.base)printf(t%-7s%snn,base-,*s.top);elseprintf(t%7s%sn, ,*s.

4、top);return ok;/stacktraversestatus push(sqstack &s,selemtype e)/插入元素e为新的栈顶元素char str10; /中间变量while(strcmp(str,n)!=0) /用作连续入栈if(s.top-s.base=s.stacksize) /栈满,追加储存空间s.base=(selemtype *)realloc(s.base,(s.stacksize+stackincrement) * sizeof(selemtype);if(!s.base)printf(储存分配失败!nn);exit(error);s.top=s.bas

5、e+s.stacksize; /改变栈顶s.stacksize+=stackincrement; /当前已分配的储存空间增加 printf(请输入元素: ); scanf(%s,e);strcpy(*s.top+,e); /将新的元素赋给栈顶,栈顶上移printf(入栈成功nn);printf(继续入栈/退出:y/n: );while(1) /选择是否继续入栈,若否,则入栈结束scanf(%s,str);if(strcmp(str,y)=0|strcmp(str,n)=0)break;elseprintf(选择错误,请重新选择: );return ok;/pushstatus pop(sqst

6、ack &s,selemtype &e)/若栈不空,则删除s的栈顶元素,用e返回其值,并返回ok;否则返回errorif(s.top=s.base)printf(its empty!nn);return error;strcpy(e,*-s.top);printf(出栈成功n);printf(出栈元素为: %snn,e);return ok;/popstatus clearstack(sqstack &s)/把s置为空栈,让栈顶和栈底相等,当前已分配的储存空间等于初始储存空间s.top=s.base;s.stacksize=stack_init_size;printf(栈已初始化为空栈!nn)

7、;return ok;/clearstack/*栈的链式存储*/typedef struct snodechar data20; /栈中的元素为字符型数组struct snode *next; /指向下一个节点int stacklength;snode,*linkstack;status initstack_l(linkstack &t)/建立空战,申请一个头,并将头的下一个节点赋为空(头节点下一结点即为栈顶)t=(linkstack)malloc(sizeof(snode);if(!t) printf(空间申请失败!nn);exit(error);t-next=null;t-stacklen

8、gth=0;printf(nt建栈成功!nn);return ok;/initstack_lstatus stacktraverse_l(linkstack t)/若栈不空,输出栈中的所有元素linkstack p;if(t-next=null)printf(栈目前为空!n);return error;printf(栈中目前的数据如下所示:n);p=t-next; /从头下一结点(栈顶)开始printf(t栈顶-n);while(p)if(p-next=null)printf(t栈底- %sn,p-data);p=p-next;elseprintf(t%8s%sn,p-data);p=p-ne

9、xt;return ok;/stacktraverse_lstatus push_l(linkstack &t)/入栈,将新的栈的元素存在头的下一结点linkstack p,q;char str10; while(strcmp(str,n)!=0)printf(请输入元素: );p=(linkstack)malloc(sizeof(snode);if(!p) printf(空间申请失败!nn);exit(error);scanf(%s,p-data);q=t-next;t-next=p;t-next-next=q;t-stacklength+;printf(入栈成功nn);printf(继续入

10、栈/退出:y/n: );while(1)scanf(%s,str);if(strcmp(str,y)=0|strcmp(str,n)=0)break;elseprintf(选择错误,请重新选择: );return ok;/push_lstatus pop_l(linkstack &t,selemtype &e)/若栈不空,则删除栈顶元素(头结点下一结点),用e返回其值,并返回ok;否则返回errorlinkstack p;if(t-next=null)printf(its empty!nn);return error; p=t-next;strcpy(e,t-next-data);t-next

11、=p-next;free(p);t-stacklength-;printf(出栈成功n);printf(出栈元素为: %snn,e);return ok;/pop_lstatus clearstack_l(linkstack &t)/把栈置为空栈,将头以后节点摘掉linkstack p;p=t-next;t-next=null;free(p);t-stacklength=0;return ok;/clearstack_lstatus stacklength_l(linkstack t)/返回栈的元素个数return t-stacklength; /返回栈的长度/stacklength_l/*循

12、环队列队列的顺序式存储*/int numjudge(char ch110) /输入的ch1必须为非负整数char ch210; /定义ch2字符型数组存放一个整型数据int a; /用于保存ch1转换为整型的数据while(1) /无限循环使用户可以无限输入直到输入正确scanf(%s,ch1); /输入ch1a=atoi(ch1); /将ch1转换为整型itoa(a,ch2,10); /将ch1转换为整型后的数据再存放到ch2当中if(strcmp(ch1,ch2)=0&a=0)|strcmp(ch1,0)=0)break; /当输入的数据为非负整数时跳出死循环elseprintf(请输入一

13、个正整数: ); /输入数据有误return a; /返回输入的非负整数/numjudgetypedef int qelemtype; /定义qelemtype类型为int型#define maxqsize 100 /最大队列长度typedef structqelemtype *base; /初始化的动态分配存储空间int front; /头指针,若队列不空,指向队列头元素int rear; /尾指针,若队列不空,指向队列尾元素的下一位置sqqueue;status initqueue(sqqueue &q)/构造一个空队列q,此时让队头等于队尾q.base=(qelemtype *)mall

14、oc(maxqsize * sizeof(qelemtype);if(!q.base)printf(储存分配失败!nn);exit(error);q.front=q.rear=0; printf(nt构建队列成功!nn);return ok;/initqueuestatus queuetraverse(sqqueue q)/若队列为空,返回erroe,否则输出队列中的所有队员,并返回okif(q.front=q.rear)printf(队列为空!nn);return error;printf(队列中目前的数据如下所示:nn);printf(front-);while(q.front!=q.re

15、ar)printf(%-4d,q.baseq.front);q.front=(q.front+1) % maxqsize;printf(%4s%-6s,next=null;q-data=0; q-rear=q;printf(nt构建队列成功!nn);return ok;/initqueue_lstatus queuetraverse_l(linkqueue q)/若队列不为空,输出队列中的所有队员linkqueue p;if(q-data=0)printf(队列为空!nn);return error;printf(队列中目前的数据如下所示:n);p=q-next;printf(队头-);whi

16、le(p)printf(%-4d,p-data);p=p-next;printf(data;/queuelength_lstatus enqueue_l(linkqueue &q,qelemtype e)/插入元素e为q的新的队尾元素linkqueue p,p1;char ch10,str10;while(strcmp(str,n)!=0)p=(linkqueue)malloc(sizeof(qnode);if(!p)printf(空间申请失败!nn);exit(error);printf(请输入队列成员: ); e=numjudge(ch); /输入的队员必须为非负整数p-data=e;q-

17、rear-next=p;q-rear=p;p-next=null;q-data+; /将新的队员插入至队尾printf(入队成功nn);printf(继续入队/退出:y/n: );while(1) /选择是否继续入栈,若否,则入栈结束scanf(%s,str);if(strcmp(str,y)=0|strcmp(str,n)=0)break;elseprintf(选择错误,请重新选择: );return ok;/enqueue_lstatus dequeue_l(linkqueue &q,qelemtype e)/若队列不空,则删除q的队头元素(头结点下一节点),用e返回其值,并返回ok.否则

18、返回erroeif(q-data=0)printf(its empty!nn);return error;linkqueue p;p=q-next;e=p-data;q-next=p-next;free(p);q-data-; /队员个数减1printf(出队成功nn);printf(出队成员为: %dnn,e);return ok;/dequeue_lstatus clearqueue_l(linkqueue &q)/将q清为空队列,摘除头结点的下一结点,并将队员个数赋为0linkqueue p;p=q-next;q-next=null;free(p);q-data=0;return ok;

19、/clearqueue/*菜单函数及主函数*/int mainmenu() /主界面菜单函数char ch10;int choose;system(cls);printf(ntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n);printf(tt 计本102 卢荣盼 1018014052n);printf(tt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n);printf(ttt(1)栈的顺序式存储nn);printf(ttt(2)栈的链式存储nn);printf(ttt(3)队列的顺序式存储nn);printf(ttt(4)队列的链式存储n

20、n);printf(ttt(0)退出程序);printf(ntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n);printf(tt请输入你的选择: );while(1) /只有输入数字0,1,2,3,4时跳出死循环,否则选择scanf(%s,ch);if(strcmp(ch,0)=0|strcmp(ch,1)=0|strcmp(ch,2)=0|strcmp(ch,3)=0|strcmp(ch,4)=0)choose=atoi(ch);break;elseprintf(tt选择错误,请重新选择: );return choose; /返回选择的序号int stack

21、menu() /栈的菜单函数char ch10;int choose;printf(ntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n);printf(ttt(1)建立空栈nn);printf(ttt(2)入栈nn);printf(ttt(3)出栈nn);printf(ttt(4)初始化栈nn);printf(ttt(5)查看当前栈中的元素nn);printf(ttt(0)返回主菜单n);printf(tt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n);printf(tt请输入你的选择: );while(1) /只有输入数字0,1,2

22、,3,4,5时跳出死循环,否则选择scanf(%s,ch);if(strcmp(ch,0)=0|strcmp(ch,1)=0|strcmp(ch,2)=0|strcmp(ch,3)=0|strcmp(ch,4)=0|strcmp(ch,5)=0)choose=atoi(ch);break;elseprintf(tt选择错误,请重新选择: );return choose; /返回选择的序号int queuemenu() /队列的菜单函数char ch10;int choose;printf(ntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n);printf(ttt(1

23、)建立空队列nn);printf(ttt(2)入队nn);printf(ttt(3)出队nn);printf(ttt(4)初始化队列nn);printf(ttt(5)查看当前队列中的成员nn);printf(ttt(0)返回主菜单n);printf(tt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n);printf(tt请输入你的选择: );while(1)scanf(%s,ch);if(strcmp(ch,0)=0|strcmp(ch,1)=0|strcmp(ch,2)=0|strcmp(ch,3)=0|strcmp(ch,4)=0|strcmp(ch,5)=0

24、)choose=atoi(ch);break;elseprintf(tt选择错误,请重新选择: ); return choose;void main()int choose; /用于保存选择的序号sqstack s; /顺序栈ss.stacksize=0; /栈储存空间为0,当建立了栈后,它的值变为初始分配的储存空间selemtype e; /e为selemtype(字符型数组)型 linkstack t=null; /链式栈的头,将它赋为空,当建立了栈后,头不为空sqqueue q; /顺序式队列qq.base=null; /顺序栈的初始分配空间为空,当建立了队列后,它变为队列的最大长度qe

25、lemtype e; /e为qelemtype(整型)型linkqueue q=null; /链式队的头,将它赋为空,当建立了栈后,头不为空system(color f0); /改变运行窗口颜色,背景为淡绿色,字体颜色为黑色while(choose=mainmenu()!=5) switch(choose) /用主菜单选择的序号控制此switch,若选择0则程序终止case 1:while(choose!=0)/当选择栈菜单上的0时，退回到主菜单system(cls); /运行前清屏printf(ntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*);printf(nttt

26、 栈的顺序式存储);switch(stackmenu() /用栈菜单上的序号控制此switch语句case 1:initstack(s);system(pause);break; /建立空栈后程序暂停,之后按任意键继续case 2:if(s.stacksize=0)printf(nt还没有建栈,请先建栈!nn);/还未建立栈elsesystem(cls);stacktraverse(s);printf(栈中当前有%d个元素nn,stacklength(s);/显示栈中元素并输出栈的长度push(s,e); /入栈stacktraverse(s);printf(n栈中当前有%d个元素nn,sta

27、cklength(s);system(pause);break; /程序暂停,之后按任意键继续case 3:if(s.stacksize=0)printf(nt还没有建栈,请先建栈!nn);elseif(s.base=s.top)printf(n空栈,无元素可出栈!nn);/空栈elsesystem(cls);stacktraverse(s);printf(n栈中当前有%d个元素nn,stacklength(s);pop(s,e); /出栈stacktraverse(s);printf(n栈中当前有%d个元素nn,stacklength(s);system(pause);break;case

28、4:if(s.stacksize=0)printf(nt还没有建栈,请先建栈!nn);elseclearstack(s); /初始化栈为空stacktraverse(s);printf(n栈中当前有%d个元素nn,stacklength(s);system(pause);break;case 5:if(s.stacksize=0)printf(nt还没有建栈,请先建栈!nn);elseif(s.base!=s.top)system(cls);stacktraverse(s);printf(n栈中当前有%d个元素nn,stacklength(s);system(pause);break;case

29、 0:choose=0;break;default:printf(程序运行错误!);exit(error);/此开关的值在菜单函数中已控制,如出现其他值,则说明程序出错 break;case 2:while(choose!=0)system(cls);printf(ntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*);printf(nttt 栈的链式存储);switch(stackmenu()case 1:initstack_l(t);system(pause);break;case 2:if(t=null)printf(nt还没有建栈,请先建栈!nn);elsesyst

30、em(cls);stacktraverse_l(t);printf(n栈中当前有%d个元素nn,stacklength_l(t);push_l(t);stacktraverse_l(t);printf(n栈中当前有%d个元素nn,stacklength_l(t);system(pause);break;case 3:if(t=null)printf(nt还没有建栈,请先建栈!nn);elseif(t-next=null)printf(n空栈,无元素可出栈!nn);elsesystem(cls);stacktraverse_l(t);printf(n栈中当前有%d个元素nn,stacklengt

31、h_l(t);pop_l(t,e);stacktraverse_l(t);printf(n栈中当前有%d个元素nn,stacklength_l(t);system(pause);break;case 4:if(t=null)printf(nt还没有建栈,请先建栈!nn);elseclearstack_l(t);stacktraverse_l(t);printf(n栈中当前有%d个元素nn,stacklength_l(t); system(pause);break;case 5:if(t=null)printf(nt还没有建栈,请先建栈!nn);elseif(t-next!=null)syste

32、m(cls);stacktraverse_l(t);printf(n栈中当前有%d个元素nn,stacklength_l(t);system(pause);break;case 0:choose=0;break;default:printf(程序运行错误!);exit(error); break;case 3:while(choose!=0)system(cls);printf(ntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*);printf(nttt 队列的顺序式存储);switch(queuemenu()case 1:initqueue(q);system(paus

33、e);break;case 2:if(!q.base)printf(nt还没有建立队列,请先建立队列!nn);elsesystem(cls);queuetraverse(q);printf(队列中当前有%d个队员nn,queuelength(q);enqueue(q,e);queuetraverse(q);printf(队列中当前有%d个队员nn,queuelength(q);system(pause);break;case 3:if(!q.base)printf(nt还没有建立队列,请先建立队列!nn);elseif(q.front=q.rear)printf(n空队列,无队员可出队!nn)

34、;elsesystem(cls);queuetraverse(q);printf(队列中当前有%d个队员nn,queuelength(q);dequeue(q,e);queuetraverse(q);printf(队列中当前有%d个队员nn,queuelength(q);system(pause);break;case 4:if(!q.base)printf(nt还没有建立队列,请先建立队列!nn);elseclearqueue(q);queuetraverse(q);printf(队列中当前有%d个队员nn,queuelength(q);system(pause);break;case 5:if(!q.base)printf(nt还没有建立队列,请先建立队列!nn);elseif(q.front!=q.rear)system(cls);queuetraverse(q);printf(队列中当前有%d个队员nn