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

1、c+数据结构实验链表排序1实验要求i.实验目的:通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。理解算法的主要思想及流程。ii.实验容：使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序（改进型冒泡排序）3、快速排序4、简单选择排序5、堆排序（小根堆）要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编

2、写测试main()函数测试线性表的正确性iii.代码要求：1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出2. 程序分析通过排序算法将单链表中的数据进行由小至大（正向排序）2.1 存储结构单链表存储数据：struct node int data; node*next;单链表定义如下：class LinkListprivate: node * front;public: LinkList(int a, int

3、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);

4、 /快速排序的递归主体 void heapsort(int n); /堆排序算法;2.2关键算法分析： 1.直接插入排序：首先将待排序数据建立一个带头结点的单链表。将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程，需设一个工作指针p-next在无序区中指向待插入的结点，在找到插入位置后，将结点p-next插在结点s和p之间。void LinkList:InsertSort() /将第一个元素定为初始有序区元素，由第二个元素开始依次比较 LARGE_INTEGER

5、 t1, t2, feq; QueryPerformanceFrequency(&feq); /每秒跳动次数 QueryPerformanceCounter(&t1); /测前跳动次数 node * p = front-next; /要插入的节点的前驱 while (p-next) node * s = front; /充分利用带头结点的单链表 while (1) comparef+; if (p-next-data next-data) / P后继比S后继小则插入 insert(p, s); break; s = s-next; if (s = p) /若一趟比较结束，且不需要插入 p =

6、p-next; break; QueryPerformanceCounter(&t2); /测后跳动次数 double d = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/时间差秒 cout 操作时间为： d 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-

7、data) /元素值小于轴点值，则将该元素插在轴点之前 if (p-next = e) /若该元素为e，则将其前驱设为e e = p; insert(p, qianqu); qianqu = qianqu-next; else p = p-next; QSZ(b, qianqu); /继续处理轴点左侧链表 QSZ(qianqu-next, e); /继续处理轴点右侧链表整个快速排序的实现:void LinkList:QSort() LARGE_INTEGER t1, t2, feq; QueryPerformanceFrequency(&feq); /每秒跳动次数 QueryPerforman

8、ceCounter(&t1); /测前跳动次数 node * e = front; while (e-next) e = e-next; QSZ(front, e); QueryPerformanceCounter(&t2); /测后跳动次数 double d = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/时间差秒 cout 操作时间为： d next; while (p-next) / 排序查找无序边界 comparef+; if (p-data p-next-data) turn(p, p-nex

9、t); p = p-next; node * pos = p; p = front-next; while (pos != front-next) node * bound = pos; pos = front-next; while (p-next != bound) comparef+; if (p-data p-next-data) turn(p, p-next); pos = p-next; p = p-next; p = front-next; QueryPerformanceCounter(&t2); /测后跳动次数 double d = (double)t2.QuadPart -

10、 (double)t1.QuadPart) / (double)feq.QuadPart);/时间差秒 cout 操作时间为： d next-next) node * p = s; node * index = p; while (p-next) comparef+; if (p-next-data next-data) index = p; p = p-next; insert(index, s); s = s-next; QueryPerformanceCounter(&t2); /测后跳动次数 double d = (double)t2.QuadPart - (double)t1.Qua

11、dPart) / (double)feq.QuadPart);/时间差秒 cout 操作时间为： d endl;5.堆排序： 利用前一趟比较的结果来减少比较次数，提高整体的效率。 其过链表储存了一棵树。 选择使用小根堆进行排序。void LinkList:sift(int k, int m) int i = k, j = 2 * i; while (j = m) comparef+; if (jdataGet(j + 1)-data) j+; if (Get(i)-data data) break; else turn(Get(i), Get(j); i = j; j = 2 * i; voi

12、d LinkList:heapsort(int n) LARGE_INTEGER t1, t2, feq; QueryPerformanceFrequency(&feq); /每秒跳动次数 QueryPerformanceCounter(&t1); /测前跳动次数 for (int i = n / 2; i = 1; i-) sift(i, n); for (int i = 1; i n; i+) turn(Get(1), Get(n - i + 1); sift(1, n - i); QueryPerformanceCounter(&t2); /测后跳动次数 double d = (doub

13、le)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/时间差秒 cout 操作时间为： d next; int j = 1; while (j != i&p) p = p-next; j+; if (!p) throw 查找位置非法; else return p;6.输出结果的函数：void tell(LinkList &a, LinkList &b, LinkList &c, LinkList &d, LinkList &e) a.print(); comparef = 0; movef = 0; a.InsertSor

14、t(); cout 排序结果：; a.print(); cout 1.插入排序法： Compare： setw(3) comparef ; Move： setw(3) movef endl; comparef = 0; movef = 0; b.BubbleSort(); cout 2.改进型冒泡排序法： Compare： setw(3) comparef ; Move： setw(3) movef endl; comparef = 0; movef = 0; c.QSort(); cout 3.快速排序法： Compare： setw(3) comparef ; Move： setw(3)

15、movef endl; comparef = 0; movef = 0; d.SelectSort(); cout 4.简单选择排序法 Compare： setw(3) comparef ; Move： setw(3) movef endl; comparef = 0; movef = 0; e.heapsort(10); cout 5.堆排序算法 Compare： setw(3) comparef ; Move： setw(3) movef endl;7.统计时间的函数：#includeLARGE_INTEGER t1, t2, feq; QueryPerformanceFrequency(

16、&feq); /每秒跳动次数 QueryPerformanceCounter(&t1); /测前跳动次数 node * p = front-next; /要插入的节点的前驱QueryPerformanceCounter(&t2); /测后跳动次数 double d = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/时间差秒 cout 操作时间为： d next; /要插入的节点的前驱 while (p-next) node * s = front; /充分利用带头结点的单链表 while (1) comp

17、aref+; if (p-next-data next-data) / P后继比S后继小则插入 insert(p, s); break; s = s-next; if (s = p) /若一趟比较结束，且不需要插入 p = p-next; break; 问题二：如何将书上以数组方式储存的树转化为链表储存并进行操作？原本打算建立一颗完全二叉树储存相应数据再进行排序，但是那样的话需要新设置结点存左孩子右孩子，比较麻烦容易出错，所以选择了利用Get(int i)函数将筛选结点的位置获得。与书上代码相比修改如下：if (jdataGet(j + 1)-data) j+; if (Get(i)-data

18、 data) break; else turn(Get(i), Get(j); i = j; j = 2 * i; 问题三：时间如何精确至微秒？需要调用函数，这个问题是上网查找解决的。总结：解决了以上的问题后代码就比较完整了，可是还是希望通过日后的学习能将算法编写得更完善，灵活，简捷。附录：完整代码如下：#include lianbiaopaixu.h#include using namespace std;void main() int a10 = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ; LinkList zhengxu1(a, 10), zhengxu2(a, 10

19、), zhengxu3(a, 10), zhengxu4(a, 10), zhengxu5(a, 10); cout 正序数列：; tell(zhengxu1, zhengxu2, zhengxu3, zhengxu4, zhengxu5); int b10 = 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ; LinkList nixu1(b, 10), nixu2(b, 10), nixu3(b, 10), nixu4(b, 10), nixu5(b, 10); cout n逆序数列：; tell(nixu1, nixu2, nixu3, nixu4, nixu5); int

20、 c10 = 2, 6, 10, 5, 8, 3, 9, 1, 4, 7 ; LinkList suiji1(c, 10), suiji2(c, 10), suiji3(c, 10), suiji4(c, 10), suiji5(c, 10); cout n随机数列：; tell(suiji1, suiji2, suiji3, suiji4, suiji5);#include #include#include #include #include #include using namespace std;int comparef;int movef;struct node int data; n

21、ode*next;class LinkListprivate: 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

22、的结点 void sift(int k, int m); /一趟堆排序 void LinkList:QSZ(node * b, node *e); /快速排序的递归主体 void heapsort(int n); /堆排序算法;LinkList:LinkList(int a, int n) front = new node; front-next = NULL; for (int i = n - 1; i = 0; i-) node * p = new node; /新节点 p-data = ai; p-next = front-next; front-next = p; /头插法建立单链表，最先加入的被不断后移 LinkList:LinkList() node * q = front; while (q) front = q; q = q-next; delete front; void LinkList:insert(node*p, node*s) /将p-next插入s和s-next之间 node * q = p-next; p-next = p-next-next; q-next = s-next; s