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

《c++数据结构实验链表排序.doc》由会员分享，可在线阅读，更多相关《c++数据结构实验链表排序.doc（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

5、ncy(&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 = p-next; break;QueryPerformanceCounter(&t2); /测后跳动

6、次数 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-data)/元素值小于轴点值，则将该元素插在轴点之前if (p-next = e)/若该元素为e，则将其前驱设为e

7、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); /每秒跳动次数 QueryPerformanceCounter(&t1); /测前跳动次数 node * e = front;while (e-next)e = e-next;QSZ(

8、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-next);p = p-next;node * pos = p; p = front-next;while (pos != front-next)node * b

9、ound = 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 - (double)t1.QuadPart) / (double)feq.QuadPart);/时间差秒 cout 操作时间为： d next-next)node * p = s;n

10、ode * 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.QuadPart) / (double)feq.QuadPart);/时间差秒 cout 操作时间为： d endl;5.堆排序： 利用前一趟比较的结果来减少比较次数，提高整体的效率。 其中通过链表储存了一

11、棵树。 选择使用小根堆进行排序。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;elseturn(Get(i), Get(j);i = j;j = 2 * i;void LinkList:heapsort(int n)LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳动次数 QueryPerformanc

12、eCounter(&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 = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/时间差秒 cout 操作时间为： d next;int j = 1;while (j != i&p)p

13、= 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.InsertSort();cout 排序结果：; a.print();cout 1.插入排序法： Compare： setw(3) comparef ; Move： setw(3) movef endl;comparef = 0; movef = 0;b.Bubbl

14、eSort();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) movef endl;comparef = 0; movef = 0;d.SelectSort();cout 4.简单选择排序法 Compare： setw(3) comparef ; Move： setw(3) movef endl;comparef = 0;

15、movef = 0;e.heapsort(10);cout 5.堆排序算法 Compare： setw(3) comparef ; Move： setw(3) movef endl;7.统计时间的函数：#includeLARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳动次数 QueryPerformanceCounter(&t1); /测前跳动次数 node * p = front-next;/要插入的节点的前驱QueryPerformanceCounter(&t2); /测后跳动次数 double d = (doub

16、le)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/时间差秒 cout 操作时间为： d 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 = p-next; break;问题二：如何将书上以数组方式储存的树转化为链表储存并进

17、行操作？原本打算建立一颗完全二叉树储存相应数据再进行排序，但是那样的话需要新设置结点存左孩子右孩子，比较麻烦容易出错，所以选择了利用Get(int i)函数将筛选结点的位置获得。与书上代码相比修改如下：if (jdataGet(j + 1)-data) j+;if (Get(i)-data data) break;elseturn(Get(i), Get(j);i = j;j = 2 * i;问题三：时间如何精确至微秒？需要调用函数，这个问题是上网查找解决的。总结：解决了以上的问题后代码就比较完整了，可是还是希望通过日后的学习能将算法编写得更完善，灵活，简捷。附录：完整代码如下：#includ

18、e 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), 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 ;Li

19、nkList nixu1(b, 10), nixu2(b, 10), nixu3(b, 10), nixu4(b, 10), nixu5(b, 10);cout n逆序数列：;tell(nixu1, nixu2, nixu3, nixu4, nixu5);int 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,

20、 suiji5);#include #include#include #include #include #include using namespace std;int comparef;int movef;struct nodeint data;node*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 Ins

21、ertSort();/插入排序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); /堆排序算法;LinkList:LinkList(int a, int n)front = new node;front-next = NULL;for (int i = n -

22、 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-

23、next = q;movef+;void LinkList:turn(node*p, node*s)/交换数据int temp = p-data;p-data = s-data;s-data = temp;movef += 3;void LinkList:print()/输出需要显示的内容node * p = front-next;while (p)cout data next;cout next;/要插入的节点的前驱while (p-next)node * s = front;/充分利用带头结点的单链表while (1)comparef+;if (p-next-data next-data)

24、/ 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 next = e | b = e)/排序完成return;node * qianqu = b; /轴点前驱node * p = qianqu-next;w

25、hile (p != e & p != e-next)comparef+;if (qianqu-next-data p-next-data)/元素值小于轴点值，则将该元素插在轴点之前if (p-next = e)/若该元素为e，则将其前驱设为ee = 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;QueryPerforma

26、nceFrequency(&feq); /每秒跳动次数 QueryPerformanceCounter(&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

27、 (p-data p-next-data)turn(p, p-next);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 =

28、 (double)t2.QuadPart - (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 - (d

29、ouble)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;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;elseturn(Get(i), Get(j);

30、i = j;j = 2 * i;void 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 = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/时间差秒 cout 操作时间为： d endl;void tell(LinkList &a, LinkList &b, LinkList &c, LinkList &d, LinkList &e)a.print();comparef = 0; movef = 0;a.I