c++数据结构实验链表排序

c++数据结构实验链表排序(43 页)Good is good, but better carries it.精益求精，善益求善。1．实验要求i.实验目的:通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。理解算法的主要思想及流程。ii.实验内容：使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序（改进型冒泡排序）3、快速排序4、简单选择排序5、堆排序（小根堆）要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为 3 次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对 2 和 3 的结果进行分析，验证上述各种算法的时间复杂度编写测试 main()函数测试线性表的正确性iii.代码要求：1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出2. 程序分析通过排序算法将单链表中的数据进行由小至大（正向排序）2.1 存储结构单链表存储数据：struct node{int data;node*next;};单链表定义如下：class LinkList{private:node * front;public:LinkList(int a[], int n);//构造~LinkList();void insert(node*p, node*s);//插入……void turn(node*p, node*s);//交换数据void print();//输出void InsertSort();//插入排序void BubbleSort();//pos冒泡void QSort();//快速排序void SelectSort();//简单选择排序node* Get(int i); //查找位置为i的结点void sift(int k, int m); //一趟堆排序void LinkList::QSZ(node * b, node *e); //快速排序的递归主体void heapsort(int n); //堆排序算法};2.2 关键算法分析：1.直接插入排序：首先将待排序数据建立一个带头结点的单链表。将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程，需设一个工作指针p->next 在无序区中指向待插入的结点，在找到插入位置后，将结点 p->next 插在结点 s 和p 之间。void LinkList::InsertSort()//将第一个元素...