数据结构课程实验报告该如何撰写？

数据结构课程实验报告

实验目的

1. 掌握[核心数据结构，栈]的基本概念、存储结构和主要操作（如入栈、出栈、判空等）的算法实现。
2. 理解[核心数据结构，栈]的“后进先出”（LIFO）特性，并能够将其应用于解决实际问题。
3. 熟练运用[编程语言，C++/Java]实现[核心数据结构]的定义、初始化、插入、删除、遍历等基本功能。
4. 通过本次实验，加深对[相关算法，递归、表达式求值]原理的理解，培养分析问题和解决问题的能力。
5. 学习规范的程序设计方法，养成良好的编程风格和调试习惯。

实验环境

• 硬件环境： Intel Core i5-8250U CPU, 8GB RAM
• 操作系统： Windows 11 / macOS Monterey
• 开发环境：
  • 编程语言： C++ / Java / Python
  • 编译器/解释器： g++ (version 11.2.0) / JDK (version 17) / Python 3.9
  • 集成开发环境： Visual Studio Code / Dev-C++ / IntelliJ IDEA
• 相关库： (如果用到，C++的 STL <stack>, <queue>)

实验原理

核心数据结构理论

本次实验主要基于 [栈] 的数据结构。

• 定义： 栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素操作，允许插入和删除的一端称为 栈顶，另一端称为 栈底。
• 特性： 栈遵循 后进先出 的原则，最后被压入栈中的元素,将是第一个被弹出的元素。
• 基本操作：
  • InitStack(S): 初始化一个空栈 S。
  • Push(S, x): 元素 x 进栈（插入栈顶）。
  • Pop(S, &x): 元素 x 出栈（删除栈顶元素，并用 x 返回其值）。
  • GetTop(S, &x): 获取栈顶元素,但不出栈。
  • StackEmpty(S): 判断栈 S 是否为空，若为空，则返回 true，否则返回 false。

算法原理

本次实验实现了 [表达式求值] 算法,其基本原理如下：

• 算术表达式： 包含操作数（如 2, 3.14）、运算符（如 +, -, *, /）和界限符（如括号）的式子。
• 逆波兰表达式（后缀表达式）： 将运算符置于操作数之后的表达式形式，如 (2 + 3) * 4 的后缀表达式为 2 3 + 4 *，后缀表达式不需要括号,且计算过程非常方便。
• 中缀转后缀： 使用栈来处理运算符的优先级和括号。
  1. 从左到右扫描中缀表达式。
  2. 遇到操作数,直接输出。
  3. 遇到运算符，将其与栈顶运算符比较优先级：
     • 若栈为空或栈顶为左括号,则当前运算符入栈。
     • 若当前运算符优先级高于栈顶运算符,则入栈。
     • 否则，将栈顶运算符出栈并输出，直到满足入栈条件,再将当前运算符入栈。
  4. 遇到左括号 ,直接入栈。
  5. 遇到右括号 ，将栈顶运算符出栈并输出，直到遇到左括号 ，并将左括号出栈（但不输出）。
  6. 扫描结束后,将栈中剩余的所有运算符依次出栈并输出。
• 后缀表达式求值： 同样使用栈。
  1. 从左到右扫描后缀表达式。
  2. 遇到操作数,将其压入栈中。
  3. 遇到运算符，从栈中弹出两个操作数（注意顺序），进行计算,并将结果压回栈中。
  4. 扫描结束后,栈中唯一剩下的元素即为最终计算结果。

实验内容与设计

系统功能设计

本实验设计并实现了一个基于栈的表达式求值系统,主要功能包括：

• 中缀表达式转后缀表达式。 用户输入一个合法的中缀表达式,系统能够正确地将其转换为后缀表达式并显示。
• 后缀表达式求值。 用户输入一个合法的后缀表达式,系统能够计算出其结果并显示。
• 综合功能。 用户输入一个中缀表达式，系统能够自动完成“中缀转后缀”和“后缀求值”两个步骤,并直接输出最终结果。

数据结构设计

为了实现上述功能,本程序主要使用以下数据结构：

• 栈： 用于存储运算符，其存储结构采用 链式存储（或 顺序存储）。

  • （链式存储示例）

    // 定义栈中结点的结构
    typedef struct StackNode {
        char data; // 存储运算符
        struct StackNode *next;
    } StackNode;
    // 定义栈的结构
    typedef struct {
        StackNode *top; // 栈顶指针
        int count;      // 栈中元素个数
    } Stack;

  • （顺序存储示例 - 使用数组）

    #define MAXSIZE 100
    typedef struct {
        char data[MAXSIZE];
        int top;
    } SqStack;

• 辅助数据结构： 为了处理多位数和小数点,还需要一个字符串或字符数组来临时存放扫描到的操作数。

函数模块设计

程序主要划分为以下几个函数模块,各模块之间通过函数调用相互协作。

实现与测试

核心算法代码实现（示例）

以下为中缀转后缀算法的核心 C++ 代码片段：

#include <iostream>
#include <string>
#include <stack>
#include <map>
using namespace std;
// 定义运算符优先级
map<char, int> priority = {
    {'+', 1}, {'-', 1},
    {'*', 2}, {'/', 2},
    {'(', 0} // 括号在栈内优先级最低
};
// 中缀转后缀
string InfixToPostfix(string infix) {
    stack<char> op_stack;
    string postfix = "";
    for (int i = 0; i < infix.length(); ++i) {
        char c = infix[i];
        if (c == ' ') continue; // 跳过空格
        if (isdigit(c) || c == '.') { // 处理操作数（包括小数）
            postfix += c;
            // 处理多位数
            while (i + 1 < infix.length() && (isdigit(infix[i+1]) || infix[i+1] == '.')) {
                postfix += infix[++i];
            }
            postfix += " "; // 用空格分隔操作数
        } else if (c == '(') {
            op_stack.push(c);
        } else if (c == ')') {
            while (!op_stack.empty() && op_stack.top() != '(') {
                postfix += op_stack.top();
                postfix += " ";
                op_stack.pop();
            }
            op_stack.pop(); // 弹出 '('
        } else { // 处理运算符
            while (!op_stack.empty() && priority[op_stack.top()] >= priority[c]) {
                postfix += op_stack.top();
                postfix += " ";
                op_stack.pop();
            }
            op_stack.push(c);
        }
    }
    // 将栈中剩余运算符弹出
    while (!op_stack.empty()) {
        postfix += op_stack.top();
        postfix += " ";
        op_stack.pop();
    }
    return postfix;
}

实验测试与结果分析

为了验证程序的正确性，我们设计了多组测试用例,覆盖了不同边界情况。

测试用例 1：简单整数运算

测试用例 2：含括号的运算

测试用例 3：含负数和小数的复杂运算

测试用例 4：边界情况测试

经过上述多组测试，程序在各种情况下均能给出正确结果，表明算法实现正确,程序健壮性良好。

实验总结与心得

实验总结

本次实验成功实现了基于栈的表达式求值系统，通过实践,我：

1. 深化了对栈数据结构的理解： 不再停留在理论层面，亲手实现了栈的创建、入栈、出栈等基本操作，并深刻体会到其“后进先出”的特性在解决实际问题（如表达式处理、函数调用）中的核心作用。
2. 掌握了关键算法的实现： 详细分析了中缀表达式转后缀表达式以及后缀表达式求值的算法流程，并将其转化为可执行的代码,这让我对算法的逻辑和细节有了更清晰的认识。
3. 提升了编程与调试能力： 在实现过程中，遇到了诸如运算符优先级判断错误、多位数/小数处理不当、括号匹配逻辑错误等问题，通过查阅资料、单步调试和逻辑分析，最终成功定位并修复了这些 Bug,极大地锻炼了解决问题的能力。
4. 认识到数据结构选择的重要性： 选择合适的数据结构是解决问题的关键，在本实验中，栈是处理运算符和操作数顺序最自然、最高效的数据结构。

遇到的问题及解决方案

• 多位数和小数的处理。

  • 描述： 最初的设计是逐个字符处理，导致输入 123 时，被识别为三个独立的操作数 1, 2, 3。
  • 解决方案： 修改扫描逻辑，当遇到数字或小数点时，持续向后扫描，直到遇到非数字非小数点的字符,将整个连续的子串作为一个操作数处理。

• 运算符优先级混淆。

  • 描述： 在实现中缀转后缀时，错误地认为 和 的优先级相同，导致 3+4*2 被错误地转换为 3 4 + 2 *。
  • 解决方案： 明确定义了运算符优先级表，并在比较栈顶运算符和当前运算符时,严格按照优先级高低进行判断。

• 空格的处理。

  • 描述： 用户输入的表达式可能包含空格，如 ( 3 + 4 ),直接按空格分割会导致逻辑错误。
  • 解决方案： 在扫描字符串时，增加一个判断，如果当前字符是空格，则直接跳过,继续处理下一个字符。

心得体会与展望

数据结构是计算机科学的基石，本次实验让我真切地感受到，一个看似简单的数学问题，背后蕴含着精巧的数据结构和算法思想，将理论知识转化为代码实现,是一个充满挑战但收获巨大的过程。

展望未来,我计划：

1. 功能扩展： 可以增加对一元运算符（如负号 ）的支持，以及对更复杂数学函数（如 sin, cos）的扩展。
2. 性能优化： 对于超长表达式的处理,可以探索更高效的数据结构或算法。
3. 界面优化： 可以开发一个带有图形用户界面的计算器,使交互更加友好。

这次实验不仅巩固了我的理论知识，更重要的是培养了我的工程实践能力和创新思维,为我后续的学习和工作打下了坚实的基础。

标签： 实验设计 算法实现 结果分析