当前位置： 首页 > article >正文

数据结构——实验二·栈

article 2025/1/23 23:36:05

海~~欢迎来到Tubishu的博客🌸如果你也是一名在校大学生，正在寻找各种变成资源，那么你就来对地方啦🌟
Tubishu是一名计算机本科生，会不定期整理和分享学习中的优质资源，希望能为你的编程之路添砖加瓦⭐🔥
当然，如果你也好的资源推荐，欢迎在评论区分享，让我们共同打造一个丰富的编程资源库！🔥
本文专栏 ➡️ 数据结构

实验目的：

  • 掌握栈的顺序/链式存储结构
  • 掌握栈的操作特性
  • 掌握基于顺序栈/链栈的基本操作的实现方法

实验内容:

（1）建立一个空栈
（2）对已建立的栈进行插入、删除、取栈顶元素等基本操作

顺序栈操作

实验产出：

1.问题分析：
栈满问题：需要预先定义栈的最大容量，并在入栈时进行检查。
栈空问题：需要在出栈时进行检查，避免栈空时弹出元素。
内存管理：顺序栈使用数组实现，不需要动态分配内存，但需要注意栈的最大容量。

2.算法设计：
初始化：创建一个顺序栈，定义栈的最大容量(1024)。
入栈（Push_Sq）：检查栈是否满，若不满则将元素压入栈顶，并更新栈顶指针。
出栈（Pop_Sq）：检查栈是否空，若不空则将栈顶元素弹出，并更新栈顶指针。
判断栈空（StackEmpty_Sq）：检查栈顶指针是否指向栈底。
判断栈满（StackFull_Sq）：检查栈顶指针是否达到栈的最大容量。

3.核心代码：

#include <stdio.h>
#include <stdlib.h>

#define ERROR 0
#define OK 1

#define MAXSIZE 4
typedef char SElemType;

typedef struct SeqStack {
    SElemType data[MAXSIZE];
    int top;
} SeqStack;

// 顺序栈的初始化
int InitStack_Sq(SeqStack *&S) {
    S = new SeqStack;
    if (!S) // 存储分配失败
        return ERROR;
    S->top = 0;
    return OK;
}

// 销毁顺序栈
int DestroyStack_Sq(SeqStack *&S) {
    if (!S) // 顺序栈为空
        return ERROR;
    delete S;
    S = NULL;
    return OK;
}

// 清空顺序栈
void ClearStack_Sq(SeqStack *&S) {
    S->top = 0;
}

// 判断顺序栈是否为空
int StackEmpty_Sq(SeqStack *S) {
    return S->top == 0;
}

// 判断顺序栈是否已满
int StackFull_Sq(SeqStack *S) {
    return S->top >= MAXSIZE;
}

// 入栈操作
int Push_Sq(SeqStack *S, SElemType e) {
    if (StackFull_Sq(S)) return ERROR; // 栈已满
    S->data[S->top++] = e;
    return OK;
}

// 出栈操作
int Pop_Sq(SeqStack *S, SElemType &e) {
    if (StackEmpty_Sq(S)) return ERROR; // 栈空
    e = S->data[--S->top];
    return OK;
}

// 取栈顶元素
int GetTop_Sq(SeqStack *S, SElemType &e) {
    if (StackEmpty_Sq(S)) return ERROR; // 栈空
    e = S->data[S->top - 1];
    return OK;
}

// 输出栈顶元素/输出顺序栈 
void DispStack_Sq(SeqStack *S) {
    if (StackEmpty_Sq(S)) {
        printf("栈空\n");
    } else {
        printf("栈顶元素为：%c\n", S->data[S->top - 1]);
        printf("顺序栈："); 
        char p = S->top;
		while(p!=0)
			printf("%c ", S->data[--p]);
		printf("\n"); 
    }
}


// 显示菜单
void showmenu() {
    printf("\n\n\n");
    printf("*       --顺序栈基本运算演示--         *\n");
    printf("****************************************\n");
    printf("*       1-------顺序栈的初始化         *\n");
    printf("*       2-------销毁顺序栈             *\n");
    printf("*       3-------清空顺序栈             *\n");
    printf("*       4-------判断顺序栈是否为空     *\n");
    printf("*       5-------判断顺序栈是否已满     *\n");
    printf("*       6-------入栈操作               *\n");
	printf("*       7-------出栈操作               *\n");
	printf("*       8-------取栈顶元素             *\n");
	printf("*                                      *\n");
    printf("*       0-------退出                   *\n");
    printf("****************************************\n");
}

void Stack_Sq() {
    char choice = 'N';
    SElemType item;
    
    SeqStack* S;
    int flag = 0; // 是否创建好了顺序栈
    
    while (choice != '0') {
    	printf("\n请选择菜单号（0--8）：");
        scanf(" %c", &choice);
        switch (choice) {
            case '1':
                printf("初始化顺序栈操作\n");
                if (InitStack_Sq(S)) {
                    printf("初始化成功!\n");
                    flag = 1; // 标志顺序栈的存在
                } else {
                    printf("初始化失败!\n");
                }
                break;
                
            case '2':
                if (flag) { // 顺序栈存在
                    DestroyStack_Sq(S);
                    flag = 0; // 顺序栈已删除
                    printf("顺序栈删除成功!\n");
                } else {
                    printf("顺序栈不存在，操作失败!\n");
                }
                break;
                
            case '3':
                if (flag) { // 顺序栈存在
                    ClearStack_Sq(S);
                    printf("顺序栈清空成功!\n");
                    DispStack_Sq(S); // 输出顺序栈 
                } else {
                    printf("顺序栈不存在,操作失败!\n");
                }
                break;
                
            case '4':
				if (flag) { // 顺序栈存在
				    printf("顺序栈%s\n", StackEmpty_Sq(S) ? "空" : "不空");
				    DispStack_Sq(S); // 输出顺序栈 
				} else {
				    printf("顺序栈不存在，操作失败!\n");
				}
				break;
				
			case '5':
				if (flag) { // 顺序栈存在
				    printf("顺序栈%s\n", StackFull_Sq(S) ? "满" : "不满");
				    DispStack_Sq(S); // 输出顺序栈 
				} else {
				    printf("顺序栈不存在，操作失败!\n");
				}
				break;	
				
			case '6':
				if (flag) { // 顺序栈存在
				    printf("请输入要入栈的元素的值:");
				    scanf(" %c", &item);
				    if (Push_Sq(S, item))
				        printf("该元素已入栈\n");
				    else {
				        printf("栈满,入栈操作失败!\n");
				    }
				    DispStack_Sq(S); // 输出顺序栈 
				} else {
				    printf("顺序栈不存在，操作失败!\n");
				}
				break;
				
			case '7':
				if (flag) { // 顺序栈存在
				    if (Pop_Sq(S, item))
				        printf("出栈元素为:%c\n", item);
				    else
				        printf("栈空!\n");
				    DispStack_Sq(S); // 输出顺序栈 
				} else {
				    printf("顺序栈不存在，操作失败!\n");
				}
				break;
				
			case '8':
				if(flag){//顺序栈存在 
					if (GetTop_Sq(S, item));
					    //printf("栈顶元素为:%c\n", item);
					else
					    printf("栈空!\n");
					DispStack_Sq(S); // 输出顺序栈 
				} else {
				    printf("顺序栈不存在,操作失败!\n");
				}
				break;
				
			case '0':
				printf("程序结束!\n");
				DestroyStack_Sq(S);
				break;
				
			default:
				printf("选择错误,请重新输入!\n");
				break;
			}
		}
	}
	
int main() {
	showmenu();
    Stack_Sq();
    return 0;
}

4.运行结果：
在这里插入图片描述在这里插入图片描述

5.调试：
栈满测试：
尝试向顺序栈中压入超过预定义的最大容量（例如，超过4个元素），验证程序是否能够正确检测到栈满并输出相应的提示信息。
预期结果：程序应提示“栈满”并阻止进一步的入栈操作。
栈空测试：
尝试从空栈中弹出元素，验证程序是否能够正确检测到栈空并输出相应的提示信息。
预期结果：程序应提示“栈空”并阻止弹出操作。
边界条件测试：
入栈一个元素后立即出栈，验证栈顶指针是否正确更新。
预期结果：栈顶指针应正确指向栈底（-1），且程序能够正确处理空栈状态。

链栈操作

实验产出：

1.问题分析：
内存分配和释放：需要在入栈时动态分配内存，在出栈时释放内存，避免内存泄漏。
栈空问题：需要在出栈时进行检查，避免栈空时删除结点。
指针操作：需要注意指针的正确使用，避免出现野指针或内存泄漏。

2.算法设计：
初始化：创建一个头结点，初始化栈顶指针。
入栈：创建一个新结点，将其插入到链表的头部，并更新栈顶指针。
出栈：检查栈是否空，若不空则删除链表的头部结点，并更新栈顶指针。
判断栈空：检查栈顶指针是否指向头结点。

3.核心代码：

#include <stdio.h>
#include <stdlib.h>

#define ERROR 0
#define OK 1

typedef char SElemType;

// 定义链栈节点
typedef struct Node {
    SElemType data; // 数据域
    struct Node *next; // 指针域
} STackNode, *LinkStack;

// 初始化链栈
int InitStack_L(LinkStack &top) {
    top = new STackNode;
    if (!top) return ERROR; // 内存分配失败
    top->next = NULL;
    return OK;
}

// 销毁链栈
int DestroyStack_L(LinkStack &top) {
    LinkStack p;
    while (top) {
        p = top;
        top = top->next;
        delete p;
    }
    return OK;
}

// 清空链栈
void ClearStack_L(LinkStack top) {
    LinkStack p, q;
    p = top->next;
    while (p) {
        q = p->next;
        delete p;
        p = q;
    }
    top->next = NULL; // 头结点指针域为空，表示空栈
}

// 判断链栈是否为空
int StackEmpty_L(LinkStack top) {
    return (top->next == NULL);
}

// 入栈操作
int Push_L(LinkStack top, SElemType e) {
    LinkStack q = new STackNode;
    if (!q) return ERROR; // 内存分配失败
    q->data = e;
    q->next = top->next;
    top->next = q;
    return OK;
}

// 出栈操作
int Pop_L(LinkStack top, SElemType &e) {
    LinkStack p;
    if (StackEmpty_L(top)) return ERROR; // 栈空，返回 ERROR
    p = top->next; // p指向栈顶元素
    e = p->data; // 栈顶元素值存入e中
    top->next = p->next; // 将p所指结点从栈中删除，即出栈操作
    delete p; // 释放p所指结点占用的空间
    return OK;
}

// 取栈顶元素
int GetTop_L(LinkStack top, SElemType &e) {
    LinkStack p;
    if (StackEmpty_L(top)) return ERROR; // 栈空，返回 ERROR
    p = top->next; // p指向栈顶元素
    e = p->data; // 栈顶元素值存入e中
    return OK;
}

// 输出链栈
void DispStack_L(LinkStack top) {
    LinkStack p = top->next;
    if (StackEmpty_L(top)) {
        printf("栈空\n");
    } else {
        printf("栈元素为：");
        while (p) {
            printf("%c ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}

// 显示菜单
void showmenu() {
    printf("\n\n\n");
    printf("*        --链栈基本运算演示--          *\n");
    printf("****************************************\n");
    printf("*       1-------链栈的初始化           *\n");
    printf("*       2-------销毁链栈               *\n");
    printf("*       3-------清空链栈               *\n");
    printf("*       4-------判断链栈是否为空       *\n");
    printf("*       5-------入栈操作               *\n");
	printf("*       6-------出栈操作               *\n");
	printf("*       7-------取栈顶元素             *\n");
	printf("*                                      *\n");
    printf("*       0-------退出                   *\n");
    printf("****************************************\n");
}

void Stack_L() {
    char choice = 'N';
    SElemType item;
    
    LinkStack top; //定义栈顶指针;
    int flag = 0; //是否创建好了链栈
    
    while (choice != '0') {
    	printf("\n请选择菜单号（0--7）："); 
        scanf(" %c", &choice);
        
        switch (choice) {
            case '1':
                printf("初始化链栈操作\n");
                if (InitStack_L(top)){
                    printf("初始化成功!\n");
                    flag = 1; //标志链栈的存在
                } else
                    printf("初始化失败!\n");
                break;
            case '2':
                if (flag) { //链栈存在
                    DestroyStack_L(top);
                    flag = 0; //链栈已删除
                    printf("链栈删除成功!\n");
                } else {
                    printf("链栈不存在,操作失败!\n");
                }
                break;
			case '3':
           		if (flag) { //链栈存在
                    ClearStack_L(top);
                    printf("链栈清空成功!\n");
                    DispStack_L(top);
                } else {
                    printf("链栈不存在,操作失败!\n");
                }
                break;
                
            case '4':
			    if (flag) { //链栈存在
			        printf("链栈%s\n", StackEmpty_L(top) ? "空" : "不空");
			        DispStack_L(top); //输出线性表
			    } else {
			        printf("链栈不存在，操作失败!\n");
			    }
			    break;
			
			case '5':
			    if (flag) { //链栈存在
			        printf("请输入要入栈的元素的值:");
			        scanf(" %c", &item);
			        Push_L(top, item);
			        printf("该元素已入栈\n");
			        DispStack_L(top); //输出线性表
			    } else {
			        printf("链栈不存在，操作失败!\n");
			    }
			    break;
			
			case '6':
			    if (flag) { //链栈存在
			        if (Pop_L(top, item))
			            printf("出栈元素为:%c\n", item);
			        else
			            printf("栈空!\n");
			        DispStack_L(top); //输出线性表
			    } else {
			        printf("链栈不存在，操作失败!\n");
			    }
			    break;
			
			case '7':
			    if (flag) { //链栈存在
			        if (GetTop_L(top, item))
			            printf("栈顶元素为:%c\n", item);
			        else
			            printf("栈空!\n");
			        DispStack_L(top); //输出线性表
			    } else {
			        printf("链栈不存在，操作失败!\n");
			    }
			    break;
			
			case '0':
			    printf("\n\t程序结束!\n");
			    DestroyStack_L(top);
			    break;
			
			default:
			    printf("\n\t选择错误,请重新输入!\n");
			    break;
        }
    }
}


int main() {
	showmenu();
    Stack_L();
    return 0;
}

4.运行结果：
在这里插入图片描述在这里插入图片描述

5.调试：
栈空测试：
尝试从空栈中弹出元素，验证程序是否能够正确检测到栈空并输出相应的提示信息。
预期结果：程序应提示“栈空”并阻止弹出操作。

总结

（1）顺序栈：
顺序栈实现简单，但需要预先定义栈的最大容量。
在栈满时，需要扩展栈的容量，可能导致性能下降。
（2）链栈：
链栈实现灵活，不需要预先定义栈的最大容量。
内存分配和释放需要注意，避免内存泄漏。
（3）实验收获：
通过本次实验，加深了对栈的理解和掌握。
学会了如何设计和实现栈的基本操作，并进行调试和测试。
认识到不同实现方式的优缺点，以及在实际应用中如何选择合适的实现方式。


http://www.kler.cn/a/515539.html

相关文章：

  • Java实现简易银行账户管理系统
  • 7.8 ChatGPT 开发者模式实战：第三方天气查询平台对接，如何打造爆款天气应用？
  • ARM-V9 CCA/RME QEMU环境搭建
  • 汇编与逆向（二）-汇编基础
  • python创建一个httpServer网页上传文件到httpServer
  • AI守护煤矿安全生产：基于视频智能的煤矿管理系统架构解析
  • 2025美赛倒计时，数学建模五类模型40+常用算法及算法手册汇总
  • 【2024年华为OD机试】 (E卷,100分) - 整数编码（JavaScriptJava PythonC/C++）
  • 4.C++中的循环语句
  • 【Mac】Python相关知识经验
  • 什么是网络爬虫？Python爬虫到底怎么学？
  • TDengine 与上海电气工业互联网平台完成兼容性认证
  • PySide6的简单介绍
  • elk 安装
  • 深度学习-91-大语言模型LLM之基于langchain的模型IO的提示模板
  • 【测开】利用界面化操作存储步骤数据，为 Selenium 自动化测试提效赋能（一）
  • ubuntu k8s 1.31
  • 学习ASP.NET Core的身份认证（基于JwtBearer的身份认证9）
  • WPF5-x名称空间
  • 数据结构基础之《（16）—链表题目》
  • Spring中BeanFactory和ApplicationContext的区别
  • [Qt]系统相关-网络编程-TCP、UDP、HTTP协议
  • idea新增java快捷键代码片段
  • 基于 Python 的深度学习的车俩特征分析系统，附源码
  • 基于springboot的考研资讯平台
  • Windows的docker中安装gitlab