实验五 链表

实验五 链表

实验目的和要求

  1. 理解顺序表和链表的特点
  2. 掌握顺序表和链表这两种结构的算法设计

实验环境

  1. Visual Studio 2017 Community
  2. Windows 10 Pro

实验内容

  1. 设计出一个模板顺序表和模板链表,测试线性表的各种运算
  2. 将两个线性表使用不同的算法进行合并

实验过程

任务一

设计

链表应提供一个初始化表的运算,根据 C++ 的类的特性,可以使用构造函数来实现,在创建链表对象时,对链表进行初始化。

为了能储存数据,链表还应提供一个插入运算,可以将数据插入到指定的位置,与此对应还应提供一个删除元素的运算。

此外,还可以添加一些辅助功能,如判断链表是否为空、在表中查找元素,获取表中指定位置的元素,合并两个表。

根据链表的特点,链表应具有以下属性和运算:

属性:

  • int count;
  • node* head;

运算:

  • linkedList();
  • ~linkedList();
  • bool insert(int index, const elementType& x);
  • bool deleteElement(int index);
  • bool empty();
  • bool getElement(int index, elementType&);
  • node* getElement(int index);
  • node* locate(const elementType&);
  • void ascendingSort();
  • void mergeList(const linkedList&, linkedList&);
  • void ascendingMergeList(const linkedList&, linkedList&);
  • void show();
  • int length();

比较顺序表和链表的特点可知,二者采用的储存结构不同,但是应提供相同的接口来对外提供服务。

编码实现

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

测试

测试各种运算均正常。

任务二

设计

将两个表合并为一个有序表,根据分析可知,有两种顺序:

  • 先将两个表进行合并,对合并后的表进行排序
  • 先对两个表进行排序,然后再进行合并