实验五 链表

实验目的和要求

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++ 的模板知识来编写模板类的代码。

测试

测试各种运算均正常。

任务二

设计

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

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