实验五 链表
实验五 链表
实验目的和要求
- 理解顺序表和链表的特点
- 掌握顺序表和链表这两种结构的算法设计
实验环境
- Visual Studio 2017 Community
- Windows 10 Pro
实验内容
- 设计出一个模板顺序表和模板链表,测试线性表的各种运算
- 将两个线性表使用不同的算法进行合并
实验过程
任务一
设计
链表应提供一个初始化表的运算,根据 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++ 的模板知识来编写模板类的代码。
测试
测试各种运算均正常。
任务二
设计
将两个表合并为一个有序表,根据分析可知,有两种顺序:
- 先将两个表进行合并,对合并后的表进行排序
- 先对两个表进行排序,然后再进行合并