顺序栈与链队列
实验内容
(1)建立顺序栈，并将元素(8，9，5，4)入栈，实现顺序栈的建立及入栈的基本操作；
(2)实现元素(8，9)的出栈，实现顺序栈的出栈操作；
(3)建立链队列，并将元素(4,5,7,6,8)入队,实现链队列的建立和入队的基本操作;
(4)实现元素(4，5)出队，实现链队列的出队操作:
(5)菜单操作。
1.顺序栈（不用指针版
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
#include <stdio.h>
#include <stdlib.h> //用malloc时要声明，引入stdlib.h以使用malloc和realloc
typedef int SElemType; // 定义栈元素类型为整型
typedef int Status; // 定义状态类型为整型
typedef struct{
SElemType *base; //在栈构造之前和销毁之后，base的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack;
//构造一个空栈S
Status InitStack(SqStack &S){
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base)exit(OVERFLOW); //存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}//InitStack
//取栈顶元素
Status GetTop(SqStack S,SElemType &e){
//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
if(S.top==S.base)return ERROR;
e=*(S.top-1); //返回非空栈中栈顶元素
return OK;
}//GetTop
//进栈操作
Status Push(SqStack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize){ //栈满，追加存储空间
S.base=(SElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));
if(!S.base)exit(OVERFLOW); // 存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e; //插入新元素，栈顶指针后移
return OK;
} //Push
//出栈操作
Status Pop(SqStack &S,SElemType &e){
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回ok，否则返回error
if(S.top==S.base)return ERROR;
e=*--S.top; //返回非空栈中的栈顶元素，栈顶指针后移
//相当于e=*(S.top-1)
return OK;
} //Pop
// 销毁栈
void DestroyStack(SqStack *S) {
if (S->base) {
free(S->base); // 释放栈空间
S->base = NULL; // 设置为NULL
}
S->top = NULL;
S->stacksize = 0;
}
// 测试主函数
int main() {
SqStack S;
SElemType e; //非常注意！这里是一个变量，不是指针
if (InitStack(S) != OK) {
printf("初始化栈失败！\n");
return -1;
}
// 进栈操作
Push(S, 8);
Push(S, 9);
Push(S, 5);
Push(S, 4);
//出栈操作
if (Pop(S, e) == OK) {
//当前面 Pop 引用参数时以&打头，除可提供输入值外，还将返回操作结果
//所以这里 S 和 e 不用加 &
printf("出栈元素: %d\n", e); //应该是4
}
if (Pop(S, e) == OK) {
printf("出栈元素: %d\n", e); // 应该是5
}
// 输出栈顶元素
if (GetTop(S, e) == OK) {
printf("栈顶元素: %d\n", e); // 应该是9
}
DestroyStack(&S); // 销毁栈
return 0;
}
顺序栈（加上菜单版
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
#include <stdio.h>
#include <stdlib.h> //用malloc时要声明，引入stdlib.h以使用malloc和realloc
typedef int SElemType; // 定义栈元素类型为整型
typedef int Status; // 定义状态类型为整型
typedef struct{
SElemType *base; //在栈构造之前和销毁之后，base的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack;
//构造一个空栈S
Status InitStack(SqStack &S){
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base)exit(OVERFLOW); //存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}//InitStack
//取栈顶元素
Status GetTop(SqStack S,SElemType &e){
//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
if(S.top==S.base)return ERROR;
e=*(S.top-1); //返回非空栈中栈顶元素
return OK;
}//GetTop
//进栈操作
Status Push(SqStack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize){ //栈满，追加存储空间
S.base=(SElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));
if(!S.base)exit(OVERFLOW); // 存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e; //插入新元素，栈顶指针后移
return OK;
} //Push
//出栈操作
Status Pop(SqStack &S,SElemType &e){
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回ok，否则返回error
if(S.top==S.base)return ERROR;
e=*--S.top; //返回非空栈中的栈顶元素，栈顶指针后移
//相当于e=*(S.top-1)
return OK;
} //Pop
// 销毁栈
void DestroyStack(SqStack *S) {
if (S->base) {
free(S->base); // 释放栈空间
S->base = NULL; // 设置为NULL
}
S->top = NULL;
S->stacksize = 0;
}
// 显示菜单
void ShowMenu() {
printf("\n----- 顺序栈操作菜单 -----\n");
printf("1. 入栈\n");
printf("2. 出栈\n");
printf("3. 查看栈顶元素\n");
printf("4. 销毁栈\n");
printf("0. 退出\n");
printf("--------------------------\n");
}
// 测试主函数
int main() {
SqStack S;
SElemType e; //非常注意！这里是一个变量，不是指针
int choice;
if (InitStack(S) != OK) {
printf("初始化栈失败！\n");
return -1;
}
while (1) {
ShowMenu();
printf("请输入您的选择: ");
scanf("%d", &choice);
switch (choice) {
case 1: // 入栈
printf("请输入要入栈的元素: ");
scanf("%d", &e);
if (Push(S, e) == OK) {
printf("%d 入栈成功。\n", e);
} else {
printf("入栈失败，存储溢出！\n");
}
break;
case 2: // 出栈
if (Pop(S, e) == OK) {
//当前面 Pop 引用参数时以&打头，除可提供输入值外，还将返回操作结果
//所以这里 S 和 e 不用加 &
printf("出栈元素: %d\n", e);
} else {
printf("出栈失败，栈为空！\n");
}
break;
case 3: // 查看栈顶元素
if (GetTop(S, e) == OK) {
printf("栈顶元素: %d\n", e);
} else {
printf("栈为空，无法查看栈顶元素！\n");
}
break;
case 4: // 销毁栈
DestroyStack(&S);
printf("栈已销毁。\n");
return 0; // 退出程序
case 0: // 退出
DestroyStack(&S);
printf("退出程序。\n");
return 0;
default:
printf("无效的选择，请重新输入。\n");
break;
}
}
return 0;
}
2.链队列
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#include <stdio.h>
#include <stdlib.h> //用malloc时要声明，引入stdlib.h以使用malloc和realloc
typedef int QElemType; // 定义队列元素类型为整型
typedef int Status; // 定义状态类型为整型
typedef struct QNode{
QElemType data;
struct QNode *next;
}Qnode, *QueuePtr;
typedef struct{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
Status InitQueue(LinkQueue &Q){
//构造一个空队列Q
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW); //存储分配失败
Q.front->next = NULL;
return OK;
}
Status DestroyQueue(LinkQueue &Q){
//销毁队列Q
QueuePtr p;
//在 EnQueue 和 DeQueue 函数中，变量 p 没有声明
//应在函数开始时声明 QueuePtr p;
while(Q.front){
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
}
Status EnQueue(LinkQueue &Q,QElemType e){
//插入元素e为Q的新的队尾元素
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if(!p)exit(OVERFLOW); //存储分配失败
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e){
//若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK；
//否则返回ERROR；
QueuePtr p;
if (Q.front == Q.rear)return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p)Q.rear=Q.front;
free(p);
return OK;
}
// 显示菜单
void ShowMenu() {
printf("\n----- 链式队列操作菜单 -----\n");
printf("1. 入队\n");
printf("2. 出队\n");
printf("3. 销毁队列\n");
printf("0. 退出\n");
printf("--------------------------\n");
}
// 主函数
int main() {
LinkQueue Q;
QElemType e;
Status status;
// 初始化队列
if (InitQueue(Q) != OK) { //不用&
printf("初始化队列失败！\n");
return -1;
}
int choice;
while (1) {
ShowMenu();
scanf("%d", &choice);
switch (choice) {
case 1: // 入队
printf("请输入入队元素: ");
scanf("%d", &e);
status = EnQueue(Q, e); //不用&
if (status == OK) {
printf("元素 %d 入队成功。\n", e);
} else {
printf("入队失败，内存溢出！\n");
}
break;
case 2: // 出队
status = DeQueue(Q, e); //不用&
if (status == OK) {
printf("元素 %d 出队成功。\n", e);
} else {
printf("出队失败，队列为空！\n");
}
break;
case 3: // 销毁队列
status = DestroyQueue(Q); //不用&
if (status == OK) {
printf("队列已销毁。\n");
}
break;
case 0: // 退出
DestroyQueue(Q); // 确保退出前销毁队列
return 0;
default:
printf("无效的选项，请重试。\n");
}
}
return 0;
}
3.合并版
为了实现结束顺序栈或链队列的基本操作后能返回主菜单的功能，需要在相应的子菜单操作循环中增加对返回上一级（即主菜单）的处理。这可以通过在接收到特定指令（例如输入0）时跳出当前子菜单的循环来实现。
增加了一个名为inSubMenu的变量来跟踪当前是否处于子菜单中。当用户选择0来退出子菜单时，inSubMenu被设置为0，从而跳出子菜单的循环并返回到主菜单。如果用户选择退出程序（即主菜单中的0），则程序将销毁栈和队列并退出。
下面是修改后的代码，其中增加了返回主菜单的功能：
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量
#include <stdio.h>
#include <stdlib.h> // 用malloc时要声明，引入stdlib.h以使用malloc和realloc
typedef int SElemType; // 定义栈元素类型为整型
typedef int QElemType; // 定义队列元素类型为整型
typedef int Status; // 定义状态类型为整型
// 顺序栈定义
typedef struct {
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
} SqStack;
// 链队列定义
typedef struct QNode {
QElemType data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LinkQueue;
// 栈操作函数
//构造一个空栈S
Status InitStack(SqStack &S) {
S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base) exit(OVERFLOW); // 存储分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}//InitStack
//取栈顶元素
Status GetTop(SqStack S,SElemType &e){
//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
if(S.top==S.base)return ERROR;
e=*(S.top-1); //返回非空栈中栈顶元素
return OK;
}//GetTop
//进栈操作
Status Push(SqStack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top - S.base >= S.stacksize){ //栈满，追加存储空间
S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) *sizeof(SElemType));
if(!S.base) exit(OVERFLOW); // 存储分配失败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e; //插入新元素，栈顶指针后移
return OK;
} //Push
//出栈操作
Status Pop(SqStack &S,SElemType &e){
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回ok，否则返回error
if(S.top == S.base) return ERROR;
e= *--S.top; //返回非空栈中的栈顶元素，栈顶指针后移
//相当于e=*(S.top-1)
return OK;
} //Pop
// 销毁栈
void DestroyStack(SqStack *S) {
if (S->base) {
free(S->base); // 释放栈空间
S->base = NULL; // 设置为NULL
}
S->top = NULL;
S->stacksize = 0;
}
// 队列操作函数
Status InitQueue(LinkQueue &Q){
//构造一个空队列Q
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW); //存储分配失败
Q.front->next = NULL;
return OK;
}
Status DestroyQueue(LinkQueue &Q){
//销毁队列Q
QueuePtr p;
//在 EnQueue 和 DeQueue 函数中，变量 p 没有声明
//应在函数开始时声明 QueuePtr p;
while(Q.front){
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
}
Status EnQueue(LinkQueue &Q,QElemType e){
//插入元素e为Q的新的队尾元素
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if(!p)exit(OVERFLOW); //存储分配失败
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e){
//若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK；
//否则返回ERROR；
QueuePtr p;
if (Q.front == Q.rear)return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p)Q.rear=Q.front;
free(p);
return OK;
}
// 显示菜单
void ShowStackMenu() {
printf("\n----- 顺序栈操作菜单 -----\n");
printf("1. 入栈\n");
printf("2. 出栈\n");
printf("3. 查看栈顶元素\n");
printf("4. 销毁栈\n");
printf("0. 返回上一级\n");
printf("--------------------------\n");
}
void ShowQueueMenu() {
printf("\n----- 链式队列操作菜单 -----\n");
printf("1. 入队\n");
printf("2. 出队\n");
printf("3. 销毁队列\n");
printf("0. 返回上一级\n");
printf("--------------------------\n");
}
// 主函数
int main() {
SqStack S;
LinkQueue Q;
SElemType e;
QElemType q_elem;
int choice;
int inSubMenu = 0; // 用于标记是否在子菜单中
// 初始化栈和队列
InitStack(S);
InitQueue(Q);
// 入栈元素(8, 9, 5, 4)
Push(S, 8);
Push(S, 9);
Push(S, 5);
Push(S, 4);
printf("顺序栈初始化并入栈了元素(8, 9, 5, 4)\n");
// 入队元素(4, 5, 7, 6, 8)
EnQueue(Q, 4);
EnQueue(Q, 5);
EnQueue(Q, 7);
EnQueue(Q, 6);
EnQueue(Q, 8);
printf("链队列初始化并入队了元素(4, 5, 7, 6, 8)\n");
while (1) {
printf("\n----- 主菜单 -----\n");
printf("1. 顺序栈操作\n");
printf("2. 链式队列操作\n");
printf("0. 退出\n");
printf("------------------\n");
printf("请输入您的选择: ");
scanf("%d", &choice);
switch (choice) {
case 1: // 顺序栈操作
inSubMenu = 1; // 进入子菜单
while (inSubMenu) {
ShowStackMenu();
printf("请输入您的选择: ");
scanf("%d", &choice);
switch (choice) {
case 1: // 入栈
printf("请输入要入栈的元素: ");
scanf("%d", &e);
Push(S, e);
printf("%d 入栈成功。\n", e);
break;
case 2: // 出栈
if (Pop(S, e) == OK) {
//当前面 Pop 引用参数时以&打头，提供输入值,返回操作结果
//所以这里 S 和 e 不用加 &
printf("出栈元素: %d\n", e);
} else {
printf("出栈失败，栈为空！\n");
}
break;
case 3: // 查看栈顶元素
if (GetTop(S, e) == OK) {
printf("栈顶元素: %d\n", e);
} else {
printf("栈为空，无法查看栈顶元素！\n");
}
break;
case 4: // 销毁栈
DestroyStack(&S);
printf("栈已销毁。\n");
inSubMenu = 0; // 退出子菜单，返回主菜单
break;
case 0: // 返回上一级(主菜单）
inSubMenu = 0; //退出子菜单，返回主菜单
break;
default:
printf("无效的选择，请重新输入。\n");
break;
}
}
break;
case 2: // 链式队列操作
inSubMenu = 1; //进入子菜单
while (inSubMenu) {
ShowQueueMenu();
printf("请输入您的选择: ");
scanf("%d", &choice);
switch (choice) {
case 1: // 入队
printf("请输入入队元素: ");
scanf("%d", &q_elem);
EnQueue(Q, q_elem); //不用&
printf("元素 %d 入队成功。\n", q_elem);
break;
case 2: // 出队
if (DeQueue(Q, q_elem) == OK) {
printf("元素 %d 出队成功。\n", q_elem);
} else {
printf("出队失败，队列为空！\n");
}
break;
case 3: // 销毁队列
DestroyQueue(Q);
printf("队列已销毁。\n");
inSubMenu = 0; // 退出子菜单，返回主菜单
case 0: // 返回上一级（主菜单）
inSubMenu = 0; //退出子菜单，返回主菜单
break;
default:
printf("无效的选项，请重试。\n");
}
}
break;
case 0: // 退出
DestroyStack(&S);
DestroyQueue(Q);
printf("退出程序。\n");
return 0;
default:
printf("无效的选择，请重新输入。\n");
break;
}
}
return 0;
}
原文地址：https://blog.csdn.net/2301_79012058/article/details/142878700
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！