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