#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef int Status; //定义函数类型为int 型
#define OK 1 //定义OK 为1
#define ERROR 0 //定义ERROR 为0
/***************************************************************************** *****************************栈的顺序式存储**********************************/ typedef char SElemType[20]; //定义SElemType 类型为char 型数组
#define STACK_INIT_SIZE 100 //栈的存储空间初始分配量
#define STACKINCREMENT 10 //栈的存储空间分配增量
typedef struct{
SElemType *base; //在栈构造之前和销毁之后,base 的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的储存空间, 以元素为单位
}SqStack;
Status InitStack(SqStack &S){
//构造一个空战
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base) {printf("储存分配失败!\n\n");exit(ERROR);} S.top=S.base; S.stacksize=STACK_INIT_SIZE; printf("\n\t建栈成功!\n\n"); return OK;
}//InitStack
Status StackLength(SqStack S){
//返回S 的元素个数
return S.top-S.base;
}//StackLength
Status StackTraverse(SqStack S){
//若栈不为空, 输出栈中的所有元素
if(S.top==S.base){printf("栈目前为空!\n\n");return ERROR;} printf("栈中目前的数据如下所示:\n"); printf("\ttop->\n"); while(S.top!=S.base){ S.top--; if(S.top==S.base){ printf("\t%-7s%s\n\n","base->",*S.top);} else{
printf("\t%7s%s\n"," ",*S.top);}
}
return OK;
}//StackTraverse
Status Push(SqStack &S,SElemType e){
//插入元素e 为新的栈顶元素
char str[10]; //中间变量 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("储存分配失败!\n\n");exit(ERROR);} S.top=S.base+S.stacksize; //改变栈顶 S.stacksize+=STACKINCREMENT; //当前已分配的储存空间增加 } printf("请输入元素: ");
scanf("%s",e);
strcpy(*S.top++,e); //将新的元素赋给栈顶, 栈顶上移
} printf("入栈成功\n\n"); printf("继续入栈/退出:y/n: "); while(1){ //选择是否继续入栈, 若否, 则入栈结束 } scanf("%s",str); if(strcmp(str,"y")==0||strcmp(str,"n")==0){break;} else{printf("选择错误, 请重新选择: ");}
return OK;
}//Push
Status Pop(SqStack &S,SElemType &e){
//若栈不空, 则删除S 的栈顶元素, 用e 返回其值, 并返回OK; 否则返回ERROR
if(S.top==S.base){printf("It's Empty!\n\n");return ERROR;} strcpy(e,*--S.top); printf("出栈成功\n"); printf("出栈元素为: %s\n\n",e); return OK;
}//Pop
Status ClearStack(SqStack &S){
//把S 置为空栈, 让栈顶和栈底相等, 当前已分配的储存空间等于初始储存空间
S.top=S.base; S.stacksize=STACK_INIT_SIZE; printf("栈已初始化为空栈!\n\n");
return OK;
}//ClearStack
/***************************************************************************** *****************************栈的链式存储************************************/ typedef struct SNode{
char data[20]; //栈中的元素为字符型数组
struct SNode *next; //指向下一个节点 int stacklength;
}SNode,*LinkStack;
Status InitStack_L(LinkStack &T){
//建立空战, 申请一个头, 并将头的下一个节点赋为空(头节点下一结点即为栈顶) T=(LinkStack)malloc(sizeof(SNode));
if(!T) {printf("空间申请失败!\n\n");exit(ERROR);}
Status 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栈底-> %s\n",p->data);p=p->next;} else{ printf("\t%8s%s\n","",p->data); p=p->next;} T->next=NULL; T->stacklength=0; printf("\n\t建栈成功!\n\n"); return OK; }//InitStack_L } return OK;
}//StackTraverse_L
Status Push_L(LinkStack &T){
//入栈, 将新的栈的元素存在头的下一结点
LinkStack p,q;
char str[10];
while(strcmp(str,"n")!=0){
printf("请输入元素: ");
if(!p) {printf("空间申请失败!\n\n");exit(ERROR);} scanf("%s",p->data); q=T->next;T->next=p;T->next->next=q; T->stacklength++; printf("入栈成功\n\n"); printf("继续入栈/退出:y/n: "); while(1){ scanf("%s",str); } if(strcmp(str,"y")==0||strcmp(str,"n")==0){break;} else{printf("选择错误, 请重新选择: ");} } return OK;
}//Push_L
Status Pop_L(LinkStack &T,SElemType &e){
//若栈不空, 则删除栈顶元素(头结点下一结点), 用e 返回其值, 并返回OK; 否则返回ERROR
LinkStack p; if(T->next==NULL){printf("It's Empty!\n\n");return ERROR;}
p=T->next;
strcpy(e,T->next->data);
T->next=p->next;
free(p);
T->stacklength--; printf("出栈成功\n"); printf("出栈元素为: %s\n\n",e);
return OK;
}//Pop_L
Status ClearStack_L(LinkStack &T){
//把栈置为空栈, 将头以后节点摘掉
LinkStack p;
p=T->next;T->next=NULL; free(p); T->stacklength=0;
return OK;
}//ClearStack_L
Status StackLength_L(LinkStack T){
//返回栈的元素个数
return T->stacklength; //返回栈的长度
}//StackLength_L
/***************************************************************************** *********************循环队列——队列的顺序式存储****************************/ int NumJudge(char ch1[10]){
//输入的ch1必须为非负整数
char ch2[10]; //定义ch2字符型数组存放一个整型数据 int a; //用于保存ch1转换为整型的数据 while(1){ //无限循环使用户可以无限输入直到输入正确 scanf("%s",ch1); //输入ch1 a=atoi(ch1); //将ch1转换为整型 itoa(a,ch2,10); //将ch1转换为整型后的数据再存放到ch2当中 if((strcmp(ch1,ch2)==0&&a>=0)||strcmp(ch1,"0")==0){break;} //当输入的数据为非负整数时跳出死循环
else{printf("请输入一个正整数: ");} //输入数据有误
} return a; //返回输入的非负整数
}//NumJudge
typedef int QElemType; //定义QElemType 类型为int 型
#define MAXQSIZE 100 //最大队列长度
typedef struct{
QElemType *base; //初始化的动态分配存储空间
int front; //头指针, 若队列不空, 指向队列头元素
int rear; //尾指针, 若队列不空, 指向队列尾元素的下一位置
}SqQueue;
Status InitQueue(SqQueue &Q){
//构造一个空队列Q, 此时让队头等于队尾
Q.base=(QElemType *)malloc(MAXQSIZE * sizeof(QElemType)); if(!Q.base){printf("储存分配失败!\n\n");exit(ERROR);} Q.front=Q.rear=0; printf("\n\t构建队列成功!\n\n"); return OK;
}//InitQueue
Status QueueTraverse(SqQueue Q){
//若队列为空, 返回ERROE, 否则输出队列中的所有队员, 并返回OK
if(Q.front==Q.rear){
printf("队列为空!\n\n");return ERROR;}
printf("队列中目前的数据如下所示:\n\n");
printf("front->"); while(Q.front!=Q.rear){ printf("%-4d",Q.base[Q.front]);
Q.front=(Q.front+1) % MAXQSIZE;}
printf("%4s%-6s","","
printf("\n");
return OK;
}//QueueTraverse
Status QueueLength(SqQueue Q){
//返回Q 的元素个数, 即队列的长度
return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE;
}//QueueLength
Status EnQueue(SqQueue &Q,QElemType e){
//插入元素e 为Q 的新的队尾元素
char ch[10],str[10];
while(strcmp(str,"n")!=0){ if((Q.rear+1) % MAXQSIZE==Q.front){ //队列满 printf("队列已满!\n\n");return ERROR;} printf("请输入队列成员: "); e=NumJudge(ch); Q.base[Q.rear]=e; Q.rear=(Q.rear+1) % MAXQSIZE; //Q.rear下移 printf("入队成功\n\n"); printf("继续入队/退出:y/n: "); while(1){ //选择是否继续入队, 若否, 则入队结束 scanf("%s",str); if(strcmp(str,"y")==0||strcmp(str,"n")==0){break;} else{printf("选择错误, 请重新选择: ");} } } return OK;
}//EnQueue
Status DeQueue(SqQueue &Q,QElemType e){
//若队列不空, 则删除Q 的队头元素, 用e 返回其值, 并返回OK. 否则返回ERROE
if(Q.front==Q.rear){ printf("队列为空!\n\n");return ERROR;} e=Q.base[Q.front]; Q.front=(Q.front+1) % MAXQSIZE; //队头后移 printf("出队成功\n"); printf("出队队员为: %d\n\n",e); return OK;
}//DeQueue
Status ClearQueue(SqQueue &Q){
//将Q 清为空队列, 让队尾等于队头
Q.front=Q.rear;
return OK;
}//ClearQueue
/***************************************************************************** *****************************队列的链式存储**********************************/ typedef struct QNode{
QElemType data;
struct QNode *next;
struct QNode *rear;
}QNode,*LinkQueue;
Status InitQueue_L(LinkQueue &q){
//构造一个空队列q, 带有头结点, 头节点用于存放队列中队员的个数
q=(LinkQueue)malloc(sizeof(QNode)); if(!q){printf("空间申请失败!\n\n");exit(ERROR);} q->next=NULL; q->data=0;
q->rear=q;
printf("\n\t构建队列成功!\n\n");
return OK;
}//InitQueue_L
Status QueueTraverse_L(LinkQueue q){
//若队列不为空, 输出队列中的所有队员
LinkQueue p; if(q->data==0){printf("队列为空!\n\n");return ERROR;} printf("队列中目前的数据如下所示:\n"); p=q->next; printf("队头->"); while(p){ printf("%-4d",p->data);p=p->next; } printf("
}//QueueTraverse_L
int QueueLength_L(LinkQueue q){
//返回队列的长度, 即头结点存放的数据
return q->data;
}//QueueLength_L
Status EnQueue_L(LinkQueue &q,QElemType e){
//插入元素e 为q 的新的队尾元素
LinkQueue p,p1; char ch[10],str[10]; while(strcmp(str,"n")!=0){ p=(LinkQueue)malloc(sizeof(QNode)); if(!p){printf("空间申请失败!\n\n");exit(ERROR);} printf("请输入队列成员: "); e=NumJudge(ch); //输入的队员必须为非负整数 } p->data=e; q->rear->next=p;q->rear=p;p->next=NULL;q->data++; //将新的队员插入至队尾 printf("入队成功\n\n"); printf("继续入队/退出:y/n: "); while(1){ //选择是否继续入栈, 若否, 则入栈结束 } scanf("%s",str); if(strcmp(str,"y")==0||strcmp(str,"n")==0){break;} else{printf("选择错误, 请重新选择: ");} return OK;
}//EnQueue_L
Status DeQueue_L(LinkQueue &q,QElemType e){
//若队列不空, 则删除q 的队头元素(头结点下一节点), 用e 返回其值, 并返回OK. 否则返回ERROE
if(q->data==0){printf("It's Empty!\n\n");return ERROR;} LinkQueue p; p=q->next;e=p->data; q->next=p->next; free(p); q->data--; //队员个数减1 printf("出队成功\n\n"); printf("出队成员为: %d\n\n",e); return OK;
}//DeQueue_L
Status ClearQueue_L(LinkQueue &q){
//将q 清为空队列, 摘除头结点的下一结点, 并将队员个数赋为0
LinkQueue p;
p=q->next;q->next=NULL; free(p);
q->data=0;
return OK;
}//ClearQueue
/***************************************************************************** *****************************菜单函数及主函数********************************/
int MainMenu(){ //主界面菜单函数
}
int StackMenu(){ //栈的菜单函数
char ch[10]; int choose; printf("\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t\t(1)建立空栈\n\n"); printf("\t\t\t(2)入栈\n\n"); printf("\t\t\t(3)出栈\n\n"); printf("\t\t\t(4)初始化栈\n\n"); printf("\t\t\t(5)查看当前栈中的元素\n\n"); printf("\t\t\t(0)返回主菜单\n"); printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t请输入你的选择: "); while(1){ //只有输入数字0,1,2,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){ char ch[10]; int choose; system("cls"); printf("\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t 计本102 卢荣盼 1018014052\n"); printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t\t(1)栈的顺序式存储\n\n"); printf("\t\t\t(2)栈的链式存储\n\n"); printf("\t\t\t(3)队列的顺序式存储\n\n"); printf("\t\t\t(4)队列的链式存储\n\n"); printf("\t\t\t(0)退出程序"); printf("\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t请输入你的选择: "); 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;} else{printf("\t\t选择错误, 请重新选择: ");} } return choose; //返回选择的序号
} else{printf("\t\t选择错误, 请重新选择: ");} } return choose; //返回选择的序号
int QueueMenu(){ //队列的菜单函数
char ch[10]; int choose; printf("\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t\t(1)建立空队列\n\n"); printf("\t\t\t(2)入队\n\n"); printf("\t\t\t(3)出队\n\n"); printf("\t\t\t(4)初始化队列\n\n"); printf("\t\t\t(5)查看当前队列中的成员\n\n"); printf("\t\t\t(0)返回主菜单\n"); printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t请输入你的选择: "); 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){ choose=atoi(ch);break;} else{printf("\t\t选择错误, 请重新选择: ");}
return choose;
}
void main(){
int choose; //用于保存选择的序号
度
QElemType 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"); //运行前清屏 SqStack S; //顺序栈S S.stacksize=0; //栈储存空间为0, 当建立了栈后, 它的值变为初始分配的储存空间 SElemType e; //e为SElemType(字符型数组) 型 LinkStack T=NULL; //链式栈的头, 将它赋为空, 当建立了栈后, 头不为空 SqQueue Q; //顺序式队列Q Q.base=NULL; //顺序栈的初始分配空间为空, 当建立了队列后, 它变为队列的最大长
意键继续
printf("\n\t\t*=*=*=*=*=**=*=*=*=*=**=*=*=*=*=*=*"); printf("\n\t\t\t 栈的顺序式存储"); switch(StackMenu()){ //用栈菜单上的序号控制此switch 语句 case 1:InitStack(S);system("pause");break; //建立空栈后程序暂停, 之后按任case 2:if(S.stacksize==0){printf("\n\t还没有建栈, 请先建栈!\n\n");}//还未建立栈 else{system("cls"); StackTraverse(S);printf("栈中当前有%d个元素\n\n",StackLength(S)); //显示栈中元素并输出栈的长度 Push(S,e); //入栈 StackTraverse(S);printf("\n栈中当前有%d个元素\n\n",StackLength(S));} system("pause");break; //程序暂停, 之后按任意键继续 case 3:if(S.stacksize==0){printf("\n\t还没有建栈, 请先建栈!\n\n");} else{ if(S.base==S.top){printf("\n空栈, 无元素可出栈!\n\n");}//空栈 else{system("cls"); StackTraverse(S);printf("\n栈中当前有%d个元素\n\n",StackLength(S));
Pop(S,e); //出栈
StackTraverse(S);printf("\n栈中当前有%d个元素\n\n",StackLength(S));} } system("pause");break; case 4:if(S.stacksize==0){printf("\n\t还没有建栈, 请先建栈!\n\n");} else{ ClearStack(S); //初始化栈为空 StackTraverse(S);printf("\n栈中当前有%d个元素\n\n",StackLength(S));}
system("pause");break;
case 5:if(S.stacksize==0){printf("\n\t还没有建栈, 请先建栈!\n\n");}
else{if(S.base!=S.top)system("cls"); StackTraverse(S);printf("\n栈中当前有%d个元素\n\n",StackLength(S));} system("pause");break; case 0:choose=0;break; default:printf("程序运行错误!!");exit(ERROR); //此开关的值在菜单函数中已控制, 如出现其他值, 则说明程序出错 } }break; case 2:while(choose!=0){ system("cls"); printf("\n\t\t*=*=*=*=*=**=*=*=*=*=**=*=*=*=*=*=*"); printf("\n\t\t\t 栈的链式存储"); switch(StackMenu()){ case 1:InitStack_L(T);system("pause");break;
case 2:if(T==NULL){printf("\n\t还没有建栈, 请先建栈!\n\n");} else{system("cls"); StackTraverse_L(T);printf("\n栈中当前有%d个元素\n\n",StackLength_L(T));
Push_L(T);
StackTraverse_L(T);printf("\n
\n\n",StackLength_L(T));}
栈中当前有%d个元素 system("pause");break; case 3:if(T==NULL){printf("\n\t还没有建栈, 请先建栈!\n\n");} else{ if(T->next==NULL){printf("\n空栈, 无元素可出栈!\n\n");}
栈中当前有%d个元素 else{system("cls"); StackTraverse_L(T);printf("\n
\n\n",StackLength_L(T));
Pop_L(T,e); StackTraverse_L(T);printf("\n栈中当前有%d个元素\n\n",StackLength_L(T));}
}
system("pause");break;
case 4:if(T==NULL){printf("\n\t还没有建栈, 请先建栈!\n\n");}
else{ ClearStack_L(T);StackTraverse_L(T); printf("\n栈中当前有%d个元素\n\n",StackLength_L(T));} system("pause");break; case 5:if(T==NULL){printf("\n\t还没有建栈, 请先建栈!\n\n");} else{if(T->next!=NULL)system("cls"); StackTraverse_L(T);printf("\n栈中当前有%d个元素\n\n",StackLength_L(T));}
system("pause");break;
case 0:choose=0;break;
default:printf("程序运行错误!!");exit(ERROR);
} }break; case 3:while(choose!=0){ system("cls"); printf("\n\t\t*=*=*=*=*=**=*=*=*=*=**=*=*=*=*=*=*"); printf("\n\t\t\t 队列的顺序式存储"); switch(QueueMenu()){ case 1:InitQueue(Q);system("pause");break; case 2:if(!Q.base){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{system("cls"); QueueTraverse(Q);printf("队列中当前有%d个队员\n\n",QueueLength(Q)); EnQueue(Q,E); QueueTraverse(Q);printf("队列中当前有%d个队员\n\n",QueueLength(Q));}
system("pause");break; case 3:if(!Q.base){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{ if(Q.front==Q.rear){printf("\n空队列, 无队员可出队!\n\n");} else{system("cls"); QueueTraverse(Q);printf("队列中当前有%d DeQueue(Q,E); QueueTraverse(Q);printf("队列中当前有%d个队员\n\n",QueueLength(Q)); 个队员\n\n",QueueLength(Q));} } system("pause");break; case 4:if(!Q.base){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{ ClearQueue(Q); QueueTraverse(Q);printf("队列中当前有%d个队员\n\n",QueueLength(Q));}
system("pause");break;
case 5:if(!Q.base){printf("\n\t还没有建立队列, 请先建立队列!\n\n");}
else{if(Q.front!=Q.rear)system("cls"); QueueTraverse(Q);printf("队列中当前有%d个队员\n\n",QueueLength(Q));} system("pause");break; case 0:choose=0;break; default:printf("程序运行错误!!");exit(ERROR); } }break; case 4:while(choose!=0){ system("cls"); printf("\n\t\t*=*=*=*=*=**=*=*=*=*=**=*=*=*=*=*=*"); printf("\n\t\t\t 队列的链式存储"); switch(QueueMenu()){ case 1:InitQueue_L(q);system("pause");break; case 2:if(!q){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{system("cls"); QueueTraverse_L(q);printf("队列中当前有%d个队员\n\n",QueueLength_L(q));
EnQueue_L(q,E);
QueueTraverse_L(q);printf("队列中当前有%d
\n\n",QueueLength_L(q));}
system("pause");break; case 3:if(!q){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{ if(q->next==NULL){printf("\n空队列, 无队员可出队!\n\n");} else{system("cls"); 个队员
QueueTraverse_L(q);printf("队列中当前有%d个队员\n\n",QueueLength_L(q));
DeQueue_L(q,E);
QueueTraverse_L(q);printf("队列中当前有%d
\n\n",QueueLength_L(q));}
} system("pause");break; case 4:if(!q){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{ ClearQueue_L(q); QueueTraverse_L(q);printf("队列中当前有%d个队员个队员\n\n",QueueLength_L(q));} system("pause");break; case 5:if(!q){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{if(q->data!=0)system("cls"); QueueTraverse_L(q);printf("队列中当前有%d个队员\n\n",QueueLength_L(q));}
system("pause");break;
case 0:choose=0;break;
default:printf("程序运行错误!!");exit(ERROR);
} }break; case 0: printf("\n\n\t谢谢使用本程序!\n\n");exit(ERROR); default:printf("程序运行错误!!");exit(ERROR);
}
}
}
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef int Status; //定义函数类型为int 型
#define OK 1 //定义OK 为1
#define ERROR 0 //定义ERROR 为0
/***************************************************************************** *****************************栈的顺序式存储**********************************/ typedef char SElemType[20]; //定义SElemType 类型为char 型数组
#define STACK_INIT_SIZE 100 //栈的存储空间初始分配量
#define STACKINCREMENT 10 //栈的存储空间分配增量
typedef struct{
SElemType *base; //在栈构造之前和销毁之后,base 的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的储存空间, 以元素为单位
}SqStack;
Status InitStack(SqStack &S){
//构造一个空战
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base) {printf("储存分配失败!\n\n");exit(ERROR);} S.top=S.base; S.stacksize=STACK_INIT_SIZE; printf("\n\t建栈成功!\n\n"); return OK;
}//InitStack
Status StackLength(SqStack S){
//返回S 的元素个数
return S.top-S.base;
}//StackLength
Status StackTraverse(SqStack S){
//若栈不为空, 输出栈中的所有元素
if(S.top==S.base){printf("栈目前为空!\n\n");return ERROR;} printf("栈中目前的数据如下所示:\n"); printf("\ttop->\n"); while(S.top!=S.base){ S.top--; if(S.top==S.base){ printf("\t%-7s%s\n\n","base->",*S.top);} else{
printf("\t%7s%s\n"," ",*S.top);}
}
return OK;
}//StackTraverse
Status Push(SqStack &S,SElemType e){
//插入元素e 为新的栈顶元素
char str[10]; //中间变量 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("储存分配失败!\n\n");exit(ERROR);} S.top=S.base+S.stacksize; //改变栈顶 S.stacksize+=STACKINCREMENT; //当前已分配的储存空间增加 } printf("请输入元素: ");
scanf("%s",e);
strcpy(*S.top++,e); //将新的元素赋给栈顶, 栈顶上移
} printf("入栈成功\n\n"); printf("继续入栈/退出:y/n: "); while(1){ //选择是否继续入栈, 若否, 则入栈结束 } scanf("%s",str); if(strcmp(str,"y")==0||strcmp(str,"n")==0){break;} else{printf("选择错误, 请重新选择: ");}
return OK;
}//Push
Status Pop(SqStack &S,SElemType &e){
//若栈不空, 则删除S 的栈顶元素, 用e 返回其值, 并返回OK; 否则返回ERROR
if(S.top==S.base){printf("It's Empty!\n\n");return ERROR;} strcpy(e,*--S.top); printf("出栈成功\n"); printf("出栈元素为: %s\n\n",e); return OK;
}//Pop
Status ClearStack(SqStack &S){
//把S 置为空栈, 让栈顶和栈底相等, 当前已分配的储存空间等于初始储存空间
S.top=S.base; S.stacksize=STACK_INIT_SIZE; printf("栈已初始化为空栈!\n\n");
return OK;
}//ClearStack
/***************************************************************************** *****************************栈的链式存储************************************/ typedef struct SNode{
char data[20]; //栈中的元素为字符型数组
struct SNode *next; //指向下一个节点 int stacklength;
}SNode,*LinkStack;
Status InitStack_L(LinkStack &T){
//建立空战, 申请一个头, 并将头的下一个节点赋为空(头节点下一结点即为栈顶) T=(LinkStack)malloc(sizeof(SNode));
if(!T) {printf("空间申请失败!\n\n");exit(ERROR);}
Status 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栈底-> %s\n",p->data);p=p->next;} else{ printf("\t%8s%s\n","",p->data); p=p->next;} T->next=NULL; T->stacklength=0; printf("\n\t建栈成功!\n\n"); return OK; }//InitStack_L } return OK;
}//StackTraverse_L
Status Push_L(LinkStack &T){
//入栈, 将新的栈的元素存在头的下一结点
LinkStack p,q;
char str[10];
while(strcmp(str,"n")!=0){
printf("请输入元素: ");
if(!p) {printf("空间申请失败!\n\n");exit(ERROR);} scanf("%s",p->data); q=T->next;T->next=p;T->next->next=q; T->stacklength++; printf("入栈成功\n\n"); printf("继续入栈/退出:y/n: "); while(1){ scanf("%s",str); } if(strcmp(str,"y")==0||strcmp(str,"n")==0){break;} else{printf("选择错误, 请重新选择: ");} } return OK;
}//Push_L
Status Pop_L(LinkStack &T,SElemType &e){
//若栈不空, 则删除栈顶元素(头结点下一结点), 用e 返回其值, 并返回OK; 否则返回ERROR
LinkStack p; if(T->next==NULL){printf("It's Empty!\n\n");return ERROR;}
p=T->next;
strcpy(e,T->next->data);
T->next=p->next;
free(p);
T->stacklength--; printf("出栈成功\n"); printf("出栈元素为: %s\n\n",e);
return OK;
}//Pop_L
Status ClearStack_L(LinkStack &T){
//把栈置为空栈, 将头以后节点摘掉
LinkStack p;
p=T->next;T->next=NULL; free(p); T->stacklength=0;
return OK;
}//ClearStack_L
Status StackLength_L(LinkStack T){
//返回栈的元素个数
return T->stacklength; //返回栈的长度
}//StackLength_L
/***************************************************************************** *********************循环队列——队列的顺序式存储****************************/ int NumJudge(char ch1[10]){
//输入的ch1必须为非负整数
char ch2[10]; //定义ch2字符型数组存放一个整型数据 int a; //用于保存ch1转换为整型的数据 while(1){ //无限循环使用户可以无限输入直到输入正确 scanf("%s",ch1); //输入ch1 a=atoi(ch1); //将ch1转换为整型 itoa(a,ch2,10); //将ch1转换为整型后的数据再存放到ch2当中 if((strcmp(ch1,ch2)==0&&a>=0)||strcmp(ch1,"0")==0){break;} //当输入的数据为非负整数时跳出死循环
else{printf("请输入一个正整数: ");} //输入数据有误
} return a; //返回输入的非负整数
}//NumJudge
typedef int QElemType; //定义QElemType 类型为int 型
#define MAXQSIZE 100 //最大队列长度
typedef struct{
QElemType *base; //初始化的动态分配存储空间
int front; //头指针, 若队列不空, 指向队列头元素
int rear; //尾指针, 若队列不空, 指向队列尾元素的下一位置
}SqQueue;
Status InitQueue(SqQueue &Q){
//构造一个空队列Q, 此时让队头等于队尾
Q.base=(QElemType *)malloc(MAXQSIZE * sizeof(QElemType)); if(!Q.base){printf("储存分配失败!\n\n");exit(ERROR);} Q.front=Q.rear=0; printf("\n\t构建队列成功!\n\n"); return OK;
}//InitQueue
Status QueueTraverse(SqQueue Q){
//若队列为空, 返回ERROE, 否则输出队列中的所有队员, 并返回OK
if(Q.front==Q.rear){
printf("队列为空!\n\n");return ERROR;}
printf("队列中目前的数据如下所示:\n\n");
printf("front->"); while(Q.front!=Q.rear){ printf("%-4d",Q.base[Q.front]);
Q.front=(Q.front+1) % MAXQSIZE;}
printf("%4s%-6s","","
printf("\n");
return OK;
}//QueueTraverse
Status QueueLength(SqQueue Q){
//返回Q 的元素个数, 即队列的长度
return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE;
}//QueueLength
Status EnQueue(SqQueue &Q,QElemType e){
//插入元素e 为Q 的新的队尾元素
char ch[10],str[10];
while(strcmp(str,"n")!=0){ if((Q.rear+1) % MAXQSIZE==Q.front){ //队列满 printf("队列已满!\n\n");return ERROR;} printf("请输入队列成员: "); e=NumJudge(ch); Q.base[Q.rear]=e; Q.rear=(Q.rear+1) % MAXQSIZE; //Q.rear下移 printf("入队成功\n\n"); printf("继续入队/退出:y/n: "); while(1){ //选择是否继续入队, 若否, 则入队结束 scanf("%s",str); if(strcmp(str,"y")==0||strcmp(str,"n")==0){break;} else{printf("选择错误, 请重新选择: ");} } } return OK;
}//EnQueue
Status DeQueue(SqQueue &Q,QElemType e){
//若队列不空, 则删除Q 的队头元素, 用e 返回其值, 并返回OK. 否则返回ERROE
if(Q.front==Q.rear){ printf("队列为空!\n\n");return ERROR;} e=Q.base[Q.front]; Q.front=(Q.front+1) % MAXQSIZE; //队头后移 printf("出队成功\n"); printf("出队队员为: %d\n\n",e); return OK;
}//DeQueue
Status ClearQueue(SqQueue &Q){
//将Q 清为空队列, 让队尾等于队头
Q.front=Q.rear;
return OK;
}//ClearQueue
/***************************************************************************** *****************************队列的链式存储**********************************/ typedef struct QNode{
QElemType data;
struct QNode *next;
struct QNode *rear;
}QNode,*LinkQueue;
Status InitQueue_L(LinkQueue &q){
//构造一个空队列q, 带有头结点, 头节点用于存放队列中队员的个数
q=(LinkQueue)malloc(sizeof(QNode)); if(!q){printf("空间申请失败!\n\n");exit(ERROR);} q->next=NULL; q->data=0;
q->rear=q;
printf("\n\t构建队列成功!\n\n");
return OK;
}//InitQueue_L
Status QueueTraverse_L(LinkQueue q){
//若队列不为空, 输出队列中的所有队员
LinkQueue p; if(q->data==0){printf("队列为空!\n\n");return ERROR;} printf("队列中目前的数据如下所示:\n"); p=q->next; printf("队头->"); while(p){ printf("%-4d",p->data);p=p->next; } printf("
}//QueueTraverse_L
int QueueLength_L(LinkQueue q){
//返回队列的长度, 即头结点存放的数据
return q->data;
}//QueueLength_L
Status EnQueue_L(LinkQueue &q,QElemType e){
//插入元素e 为q 的新的队尾元素
LinkQueue p,p1; char ch[10],str[10]; while(strcmp(str,"n")!=0){ p=(LinkQueue)malloc(sizeof(QNode)); if(!p){printf("空间申请失败!\n\n");exit(ERROR);} printf("请输入队列成员: "); e=NumJudge(ch); //输入的队员必须为非负整数 } p->data=e; q->rear->next=p;q->rear=p;p->next=NULL;q->data++; //将新的队员插入至队尾 printf("入队成功\n\n"); printf("继续入队/退出:y/n: "); while(1){ //选择是否继续入栈, 若否, 则入栈结束 } scanf("%s",str); if(strcmp(str,"y")==0||strcmp(str,"n")==0){break;} else{printf("选择错误, 请重新选择: ");} return OK;
}//EnQueue_L
Status DeQueue_L(LinkQueue &q,QElemType e){
//若队列不空, 则删除q 的队头元素(头结点下一节点), 用e 返回其值, 并返回OK. 否则返回ERROE
if(q->data==0){printf("It's Empty!\n\n");return ERROR;} LinkQueue p; p=q->next;e=p->data; q->next=p->next; free(p); q->data--; //队员个数减1 printf("出队成功\n\n"); printf("出队成员为: %d\n\n",e); return OK;
}//DeQueue_L
Status ClearQueue_L(LinkQueue &q){
//将q 清为空队列, 摘除头结点的下一结点, 并将队员个数赋为0
LinkQueue p;
p=q->next;q->next=NULL; free(p);
q->data=0;
return OK;
}//ClearQueue
/***************************************************************************** *****************************菜单函数及主函数********************************/
int MainMenu(){ //主界面菜单函数
}
int StackMenu(){ //栈的菜单函数
char ch[10]; int choose; printf("\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t\t(1)建立空栈\n\n"); printf("\t\t\t(2)入栈\n\n"); printf("\t\t\t(3)出栈\n\n"); printf("\t\t\t(4)初始化栈\n\n"); printf("\t\t\t(5)查看当前栈中的元素\n\n"); printf("\t\t\t(0)返回主菜单\n"); printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t请输入你的选择: "); while(1){ //只有输入数字0,1,2,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){ char ch[10]; int choose; system("cls"); printf("\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t 计本102 卢荣盼 1018014052\n"); printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t\t(1)栈的顺序式存储\n\n"); printf("\t\t\t(2)栈的链式存储\n\n"); printf("\t\t\t(3)队列的顺序式存储\n\n"); printf("\t\t\t(4)队列的链式存储\n\n"); printf("\t\t\t(0)退出程序"); printf("\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t请输入你的选择: "); 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;} else{printf("\t\t选择错误, 请重新选择: ");} } return choose; //返回选择的序号
} else{printf("\t\t选择错误, 请重新选择: ");} } return choose; //返回选择的序号
int QueueMenu(){ //队列的菜单函数
char ch[10]; int choose; printf("\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t\t(1)建立空队列\n\n"); printf("\t\t\t(2)入队\n\n"); printf("\t\t\t(3)出队\n\n"); printf("\t\t\t(4)初始化队列\n\n"); printf("\t\t\t(5)查看当前队列中的成员\n\n"); printf("\t\t\t(0)返回主菜单\n"); printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\t\t请输入你的选择: "); 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){ choose=atoi(ch);break;} else{printf("\t\t选择错误, 请重新选择: ");}
return choose;
}
void main(){
int choose; //用于保存选择的序号
度
QElemType 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"); //运行前清屏 SqStack S; //顺序栈S S.stacksize=0; //栈储存空间为0, 当建立了栈后, 它的值变为初始分配的储存空间 SElemType e; //e为SElemType(字符型数组) 型 LinkStack T=NULL; //链式栈的头, 将它赋为空, 当建立了栈后, 头不为空 SqQueue Q; //顺序式队列Q Q.base=NULL; //顺序栈的初始分配空间为空, 当建立了队列后, 它变为队列的最大长
意键继续
printf("\n\t\t*=*=*=*=*=**=*=*=*=*=**=*=*=*=*=*=*"); printf("\n\t\t\t 栈的顺序式存储"); switch(StackMenu()){ //用栈菜单上的序号控制此switch 语句 case 1:InitStack(S);system("pause");break; //建立空栈后程序暂停, 之后按任case 2:if(S.stacksize==0){printf("\n\t还没有建栈, 请先建栈!\n\n");}//还未建立栈 else{system("cls"); StackTraverse(S);printf("栈中当前有%d个元素\n\n",StackLength(S)); //显示栈中元素并输出栈的长度 Push(S,e); //入栈 StackTraverse(S);printf("\n栈中当前有%d个元素\n\n",StackLength(S));} system("pause");break; //程序暂停, 之后按任意键继续 case 3:if(S.stacksize==0){printf("\n\t还没有建栈, 请先建栈!\n\n");} else{ if(S.base==S.top){printf("\n空栈, 无元素可出栈!\n\n");}//空栈 else{system("cls"); StackTraverse(S);printf("\n栈中当前有%d个元素\n\n",StackLength(S));
Pop(S,e); //出栈
StackTraverse(S);printf("\n栈中当前有%d个元素\n\n",StackLength(S));} } system("pause");break; case 4:if(S.stacksize==0){printf("\n\t还没有建栈, 请先建栈!\n\n");} else{ ClearStack(S); //初始化栈为空 StackTraverse(S);printf("\n栈中当前有%d个元素\n\n",StackLength(S));}
system("pause");break;
case 5:if(S.stacksize==0){printf("\n\t还没有建栈, 请先建栈!\n\n");}
else{if(S.base!=S.top)system("cls"); StackTraverse(S);printf("\n栈中当前有%d个元素\n\n",StackLength(S));} system("pause");break; case 0:choose=0;break; default:printf("程序运行错误!!");exit(ERROR); //此开关的值在菜单函数中已控制, 如出现其他值, 则说明程序出错 } }break; case 2:while(choose!=0){ system("cls"); printf("\n\t\t*=*=*=*=*=**=*=*=*=*=**=*=*=*=*=*=*"); printf("\n\t\t\t 栈的链式存储"); switch(StackMenu()){ case 1:InitStack_L(T);system("pause");break;
case 2:if(T==NULL){printf("\n\t还没有建栈, 请先建栈!\n\n");} else{system("cls"); StackTraverse_L(T);printf("\n栈中当前有%d个元素\n\n",StackLength_L(T));
Push_L(T);
StackTraverse_L(T);printf("\n
\n\n",StackLength_L(T));}
栈中当前有%d个元素 system("pause");break; case 3:if(T==NULL){printf("\n\t还没有建栈, 请先建栈!\n\n");} else{ if(T->next==NULL){printf("\n空栈, 无元素可出栈!\n\n");}
栈中当前有%d个元素 else{system("cls"); StackTraverse_L(T);printf("\n
\n\n",StackLength_L(T));
Pop_L(T,e); StackTraverse_L(T);printf("\n栈中当前有%d个元素\n\n",StackLength_L(T));}
}
system("pause");break;
case 4:if(T==NULL){printf("\n\t还没有建栈, 请先建栈!\n\n");}
else{ ClearStack_L(T);StackTraverse_L(T); printf("\n栈中当前有%d个元素\n\n",StackLength_L(T));} system("pause");break; case 5:if(T==NULL){printf("\n\t还没有建栈, 请先建栈!\n\n");} else{if(T->next!=NULL)system("cls"); StackTraverse_L(T);printf("\n栈中当前有%d个元素\n\n",StackLength_L(T));}
system("pause");break;
case 0:choose=0;break;
default:printf("程序运行错误!!");exit(ERROR);
} }break; case 3:while(choose!=0){ system("cls"); printf("\n\t\t*=*=*=*=*=**=*=*=*=*=**=*=*=*=*=*=*"); printf("\n\t\t\t 队列的顺序式存储"); switch(QueueMenu()){ case 1:InitQueue(Q);system("pause");break; case 2:if(!Q.base){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{system("cls"); QueueTraverse(Q);printf("队列中当前有%d个队员\n\n",QueueLength(Q)); EnQueue(Q,E); QueueTraverse(Q);printf("队列中当前有%d个队员\n\n",QueueLength(Q));}
system("pause");break; case 3:if(!Q.base){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{ if(Q.front==Q.rear){printf("\n空队列, 无队员可出队!\n\n");} else{system("cls"); QueueTraverse(Q);printf("队列中当前有%d DeQueue(Q,E); QueueTraverse(Q);printf("队列中当前有%d个队员\n\n",QueueLength(Q)); 个队员\n\n",QueueLength(Q));} } system("pause");break; case 4:if(!Q.base){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{ ClearQueue(Q); QueueTraverse(Q);printf("队列中当前有%d个队员\n\n",QueueLength(Q));}
system("pause");break;
case 5:if(!Q.base){printf("\n\t还没有建立队列, 请先建立队列!\n\n");}
else{if(Q.front!=Q.rear)system("cls"); QueueTraverse(Q);printf("队列中当前有%d个队员\n\n",QueueLength(Q));} system("pause");break; case 0:choose=0;break; default:printf("程序运行错误!!");exit(ERROR); } }break; case 4:while(choose!=0){ system("cls"); printf("\n\t\t*=*=*=*=*=**=*=*=*=*=**=*=*=*=*=*=*"); printf("\n\t\t\t 队列的链式存储"); switch(QueueMenu()){ case 1:InitQueue_L(q);system("pause");break; case 2:if(!q){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{system("cls"); QueueTraverse_L(q);printf("队列中当前有%d个队员\n\n",QueueLength_L(q));
EnQueue_L(q,E);
QueueTraverse_L(q);printf("队列中当前有%d
\n\n",QueueLength_L(q));}
system("pause");break; case 3:if(!q){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{ if(q->next==NULL){printf("\n空队列, 无队员可出队!\n\n");} else{system("cls"); 个队员
QueueTraverse_L(q);printf("队列中当前有%d个队员\n\n",QueueLength_L(q));
DeQueue_L(q,E);
QueueTraverse_L(q);printf("队列中当前有%d
\n\n",QueueLength_L(q));}
} system("pause");break; case 4:if(!q){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{ ClearQueue_L(q); QueueTraverse_L(q);printf("队列中当前有%d个队员个队员\n\n",QueueLength_L(q));} system("pause");break; case 5:if(!q){printf("\n\t还没有建立队列, 请先建立队列!\n\n");} else{if(q->data!=0)system("cls"); QueueTraverse_L(q);printf("队列中当前有%d个队员\n\n",QueueLength_L(q));}
system("pause");break;
case 0:choose=0;break;
default:printf("程序运行错误!!");exit(ERROR);
} }break; case 0: printf("\n\n\t谢谢使用本程序!\n\n");exit(ERROR); default:printf("程序运行错误!!");exit(ERROR);
}
}
}