实验四 链栈和链队列

实验四 链栈和链队列

实验目的和要求

  1. 理解链栈和链队列的特点
  2. 掌握链栈和链队列这种结构的算法设计
  3. 学会运用链栈和链队列来储存数据和求解相关问题

实验环境

  1. Visual Studio 2017 Community
  2. Windows 10 Pro

实验内容

  1. 设计出链栈,测试链栈的各种运算
  2. 设计出链队列,测试链队列的各种运算
  3. 使用模板链栈设计出一个计算器
  4. 利用模板链队列打印出杨辉三角形

实验过程

任务一

设计

根据栈的特点,栈应具有以下属性和功能:

属性:

  • 栈顶的指针
  • 栈中元素的数量

功能:

  • 入栈
  • 出栈
  • 获取栈顶元素
  • 判断栈是否为空

本次实验采用 C++ 作为编程语言,可用 C++ 中的模板类来封装栈,以实现储存不同类型的数据。

编码实现

通过 C++ 的模板知识来编写模板类的代码。

测试

通过测试,各种功能均正常。

任务二

设计

根据链队列的特点,链队列应具有以下属性和功能:

属性:

  • 队列头的指针
  • 队列尾的指针
  • 队列中元素的数量

功能:

  • 进入队列
  • 移出队列
  • 获取队头元素
  • 判断队列是否为空

编码实现

通过 C++ 的模板知识来编写模板类的代码。

测试

通过测试,各种功能均正常。

任务三

设计

想要计算一个表达式,第一步应该是录入需要的表达式。将表达式录入后,可以将表达式储存在 string 中。对于输入的表达式,考虑到不同的用户的习惯,表达式中是否存在空格是不能确定的,而且用户输入的表达式是否合法也不确定,因此在计算前应将表达式格式化并进行检验,若表达式不合法,应提示用户重新输入。

获取到表达式后,将运算符与运算数分离开,分别储存在两个栈中。对于如何进行计算,若使用优先级的方法,则对应关系将会很复杂,可以换个角度进行思考。

本次实验中只用到了六种运算符(+、-、*、/、(、))。在扫描格式化后的表达式时,进行以下讨论:

  1. 先考虑 “(“,若遇到此运算符,应直接压入栈中继续扫描表达式
  2. 若遇到 “)”,那么应该将运算符栈中的运算符依次取出进行计算,直到栈顶运算符为 “(“,将 “(“ 弹出并继续扫描表达式
  3. 如果是 “+” 或 “-“,那么应考虑栈顶的运算符,如果栈顶运算符为 “(“ 则应该将扫描到的运算符压入栈,如果栈顶运算符为 “+”、”-“、”*”、”/“则应该将栈顶运算符取出并进行计算
  4. 如果扫描到的运算符为 ““ 或 “/“,那么应考虑栈顶的运算符,如果栈顶运算符为 “(“、”+”、”-“ 则应该将扫描到的运算符压入栈,如果遇到 ““、”/“ 则应该将栈顶运算符取出并进行计算
    至此,所有的可能都被讨论完毕。
    用户输入的表达式中可能含有除法运算,受到 C++ 中的整数除法运算限制,其结果只能为整数,这样会导致计算的结果出错。对此,可以设计一个 Rational 类(有理数类),将用户输入的表达式中的数字使用自己编写的 stringToRational 函数来转换为 Rational 对象,同时重载 Rational 类的 +、-、*、/ 运算符,这样就能将结果保留为分数形式或带有小数点的形式。

编码实现

通过已有的模板栈和以上设计思路进行编写代码。

测试

经过测试,所有功能均正常。

任务四

设计

根据杨辉三角形的特点:

  1. 第 N 行有 N 个数字
  2. 每一行的开头和结尾均为 “1”
  3. 除了数字 “1” 以外的数字都等于其上方两个数字之和。也就是说,除了 “1” 以外的每一个数字都是由之前的数字计算而来,这样,只需将打印出的数字储存起来,根据由上往下打印的规律,应将数字储存在队列中

编码实现

通过已有的模板队列和以上设计思路进行编写代码。

测试

经过测试,所有功能均正常。

实验收获

通过本次实验,掌握了栈的设计方法,体会到了栈的先进后出的特点。利用这一特点实现了简单的计算器。实际上,在解决实际问题时,若某种现象满足先进后出的规律,都可以考虑到使用栈来作为管理数据的方式,在本次实验中,计算表达式时,从左向右扫描表达式根据后面的操作符来计算操作数,未计算的操作数将被放在一边等待计算,明显符合栈的特点,故可以采用栈来解决问题。

掌握了链栈和链队列的设计方法,体会到了队列的先进先出的特点
利用这一特点来储存数据,打印出了杨辉三角形。实际上,在解决实际问题时,若某种现象满足先进先出的规律,都可以考虑到使用队列来作为管理数据的方式。在本次实验中,打印数据时,每个被打印的数据都应该被储存起来用于之后计算数字,明显符合队列的特点,故可以采用队列来解决问题。