实验四 链栈和链队列
实验四 链栈和链队列
实验目的和要求
- 理解链栈和链队列的特点
- 掌握链栈和链队列这种结构的算法设计
- 学会运用链栈和链队列来储存数据和求解相关问题
实验环境
- Visual Studio 2017 Community
- Windows 10 Pro
实验内容
- 设计出链栈，测试链栈的各种运算
- 设计出链队列，测试链队列的各种运算
- 使用模板链栈设计出一个计算器
- 利用模板链队列打印出杨辉三角形
实验过程
任务一
设计
根据栈的特点，栈应具有以下属性和功能：
属性：
- 栈顶的指针
- 栈中元素的数量
功能：
- 入栈
- 出栈
- 获取栈顶元素
- 判断栈是否为空
本次实验采用 C++ 作为编程语言，可用 C++ 中的模板类来封装栈，以实现储存不同类型的数据。
编码实现
通过 C++ 的模板知识来编写模板类的代码。
测试
通过测试，各种功能均正常。
任务二
设计
根据链队列的特点，链队列应具有以下属性和功能：
属性：
- 队列头的指针
- 队列尾的指针
- 队列中元素的数量
功能：
- 进入队列
- 移出队列
- 获取队头元素
- 判断队列是否为空
编码实现
通过 C++ 的模板知识来编写模板类的代码。
测试
通过测试，各种功能均正常。
任务三
设计
想要计算一个表达式，第一步应该是录入需要的表达式。将表达式录入后，可以将表达式储存在 string 中。对于输入的表达式，考虑到不同的用户的习惯，表达式中是否存在空格是不能确定的，而且用户输入的表达式是否合法也不确定，因此在计算前应将表达式格式化并进行检验，若表达式不合法，应提示用户重新输入。
获取到表达式后，将运算符与运算数分离开，分别储存在两个栈中。对于如何进行计算，若使用优先级的方法，则对应关系将会很复杂，可以换个角度进行思考。
本次实验中只用到了六种运算符（+、-、*、/、(、)）。在扫描格式化后的表达式时，进行以下讨论：
- 先考虑 “(“，若遇到此运算符，应直接压入栈中继续扫描表达式
- 若遇到 “)”，那么应该将运算符栈中的运算符依次取出进行计算，直到栈顶运算符为 “(“，将 “(“ 弹出并继续扫描表达式
- 如果是 “+” 或 “-“，那么应考虑栈顶的运算符，如果栈顶运算符为 “(“ 则应该将扫描到的运算符压入栈，如果栈顶运算符为 “+”、”-“、”*”、”/“则应该将栈顶运算符取出并进行计算
- 如果扫描到的运算符为 ““ 或 “/“，那么应考虑栈顶的运算符，如果栈顶运算符为 “(“、”+”、”-“ 则应该将扫描到的运算符压入栈，如果遇到 ““、”/“ 则应该将栈顶运算符取出并进行计算
至此，所有的可能都被讨论完毕。
用户输入的表达式中可能含有除法运算，受到 C++ 中的整数除法运算限制，其结果只能为整数，这样会导致计算的结果出错。对此，可以设计一个 Rational 类（有理数类），将用户输入的表达式中的数字使用自己编写的 stringToRational 函数来转换为 Rational 对象，同时重载 Rational 类的 +、-、*、/ 运算符，这样就能将结果保留为分数形式或带有小数点的形式。
编码实现
通过已有的模板栈和以上设计思路进行编写代码。
测试
经过测试，所有功能均正常。
任务四
设计
根据杨辉三角形的特点：
- 第 N 行有 N 个数字
- 每一行的开头和结尾均为 “1”
- 除了数字 “1” 以外的数字都等于其上方两个数字之和。也就是说，除了 “1” 以外的每一个数字都是由之前的数字计算而来，这样，只需将打印出的数字储存起来，根据由上往下打印的规律，应将数字储存在队列中
编码实现
通过已有的模板队列和以上设计思路进行编写代码。
测试
经过测试，所有功能均正常。
实验收获
通过本次实验，掌握了栈的设计方法，体会到了栈的先进后出的特点。利用这一特点实现了简单的计算器。实际上，在解决实际问题时，若某种现象满足先进后出的规律，都可以考虑到使用栈来作为管理数据的方式，在本次实验中，计算表达式时，从左向右扫描表达式根据后面的操作符来计算操作数，未计算的操作数将被放在一边等待计算，明显符合栈的特点，故可以采用栈来解决问题。
掌握了链栈和链队列的设计方法，体会到了队列的先进先出的特点
利用这一特点来储存数据，打印出了杨辉三角形。实际上，在解决实际问题时，若某种现象满足先进先出的规律，都可以考虑到使用队列来作为管理数据的方式。在本次实验中，打印数据时，每个被打印的数据都应该被储存起来用于之后计算数字，明显符合队列的特点，故可以采用队列来解决问题。