course_data_structures/Data Structure Class 2/hw3

数据结构 作业3
2020年春

目标：本次作业练习单链表（注：本作业所涉及的单链表均带头结点），体会数据结构课程的学习目标。

下载hw3.rar文件到你的电脑中。

开始：

第一步：解压hw3.rar，得到hw3文件夹。在hw3文件夹中，包含LinearList.h、LinkedList.h、AlgPerf.h和hw3_LinkedListTest.cpp文件。

LinearList.h实现线性表基类。

LinkedList.h头文件实现单链表数据结构。其中包含（你的）Uniquify（）算法实现剔除有序单链表的重复元素，Uniquify(int &,int &,int &)算法实现剔除有序单链表的重复元素的同时，分别合计并返回算法中元素移动总次数、元素值比较总次数和辅助空间字节总数，Merge(LinkNode<T>*,LinkNode<T>*)算法实现将两个有序单链表归并到当前操作对象*this单链表中。

AlgPerf.h文件获取并输出算法的性能数据，包括测试数据的生成、所耗时间的统计等。具体测试方法是分别对随机生成的大小为 5 - 600 （间隔为 5）的200个数组进行操作，累加200次所耗的时间、元素移动次数、元素值比较次数和辅助空间字节数。程序会自动输出测试数据统计结果在Uniquify.txt中，请你将其中的数据分别粘贴在 https://docs.qq.com/sheet/DTGFPa01Ccm9PelFQ 中四个汇总表你的姓名位置相应处（耗费总时间、元素移动总次数、元素移动总次数、辅助空间总字节数）。

hw3_LinkedListTest.cpp源文件中的main（）函数实现对单链表类的测试。其中前半部分测试单链表类，帮助掌握基本的单链表使用。后半部分是作业测试，第一部分实现测试Uniquify()操作的功能测试和高效性测试，第二部分实现测试有序表归并Merge()操作的功能测试。

第二步：建立一个空项目，添加LinearList.h、LinkedList.h、AlgPerf.h和hw3_LinkedListTest.cpp文件到项目中。

第三步：LinkedList.h文件实现单链表类，欲增加以下函数功能，请你添加代码实现以下任务，并完成测试：

任务1、实现剔除有序单链表中的重复元素。要求有序单链表的每个结点被访问一次，且仅被访问一次。
任务1.1、Uniquify( )函数实现剔除有序单链表中重复元素。分析时间复杂度和空间复杂度。
例如，有序线性表L=<9,9,9,9,19,19,19,19,19,20,20,20,30,30,30,30>,执行Uniquify( )操作后L=<9,19,20,30>。

任务1.2、Uniquify(int &,int &,int &) )函数实现剔除有序单链表的重复元素的同时，分别合计并返回算法性能数据，包括算法中元素移动总次数、元素值比较总次数和辅助空间字节总数。

性能统计说明：
算法中如果结点的data域或link域被改变，则movenum需累加一次。
凡出现两个结点的数据域的值比较大小，则compnum需累加一次。
凡出现定义辅助变量或数组，则bytesnum需累加相应的字节数。C++中sizeof(LinkNode<T>*)为4个字节。


任务2、Merge( )函数实现将两个有序单链表La和lb归并到当前操作对象*this表中，要求La、Lb、*this三个单链表的每个结点被访问一次，且仅被访问一次。分析时间复杂度和空间复杂度。

第四步、编写你自己的readme.txt文件：按照结构体程序设计方法或面向对象程序设计方法 展示你的算法以及设计过程，分析Uniquify()的时间复杂度和空间复杂度，Merge()函数的时间复杂度和空间复杂度。

第五步、压缩   .h+.cpp+.exe+.dsw/.dsp+readme.txt+你的测试数据.txt 成包(.zip\.rar)。命名规则：班级-序号+姓名+作业1，提交到datastructurecp@163.com。

说明：
1、程序都在Visual Studio 2013 编译通过。
2、鼓励大家多思考多分析，做出自己想要的优化的程序和系统。
3、鼓励大家多查找学习网上资料、程序，并将它们整理、分享到群里。
4、鼓励大家勤交流、勤分享、勤讨论，以设计并实现出优化的程序和系统（但不分享代码！）。