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

1．实验要求实验目的:通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。理解算法的主要思想及流程。实验内容：使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序（改进型冒泡排序）3、快速排序4、简单选择排序5、堆排序（小根堆）要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性代码要求：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);//堆排序算法};关键算法分析：1.直接插入排序：首先将待排序数据建立一个带头结点的单链表。将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程，需设一个工作指针p-next在无序区中指向待插入的结点，在找到插入位置后，将结点p-next插在结点s和p之间。void LinkList::InsertSort()//将第一个元素定为初始有序区元素，由第二个元素开始依次比较{LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(feq);//每秒跳动次数 QueryPerformanceCounter(t1);//测前跳动次数 node * p = front-next;//要插入的节点的前驱while (p-next){node * s = front;//充分利用带头结点的单链表while (1){comparef++;if (p-next-data s-next-data)// [P后继]比[S后继]小则插入{insert(p, s); break;}s = s-next;if (s == p)//若一趟比较结束，且不需要插入{p = p-next; break;}}}QueryPerformanceCounter(t2);//测后跳动次数 double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒 cout 操作时间为： d endl;}2.快速排序：主要通过轴值将数据从两端向中间进行比较，交换以实现排序。通过递归的调用来实现整个链表数据的排序。代码中选用了第一个元素作为轴值。一趟排序的代码：void LinkList::QSZ(node * b, node *e){if (b-next == e || b == e)//排序完成return;node * qianqu = b; //轴点前驱node * p = qianqu-next;while (p != e p != e-next){comparef++;if (qianqu-next-data p-next-data)//元素值小于轴点值，则将该元素插在轴点之前{if (p-next == e)//若该元素为e，则将其前驱设为ee = p;insert(p, qianqu);qianq