《栈与队列操作的实现完整版数据结构版.doc》由会员分享，可在线阅读，更多相关《栈与队列操作的实现完整版数据结构版.doc（14页珍藏版）》请在三一办公上搜索。
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(pause);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
