链表实现排序算法

1、数 据 结 构实验报告实验名称： 实验三 排序 学生姓名： 班 级： 班内序号： 15 学 号： 日 期： 2016.12.19 1 实验要求题目2使用链表实现下面各种排序算法，并进行比较。排序算法： 1、插入排序 2、冒泡排序3、快速排序4、简单选择排序5、其他要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性2. 程序分析

2、 2.1 存储结构我使用了线性表的链式存储结构，通过建立双向循环链表进行顺序存取。每个节点分为data、next、previor。data域称为数据域，数据通过node结构存储待排序的信息；next为指针域，用来储存直接后继的地址；prior为指针域，用来储存直接前继的地址； struct Nodeint data;struct Node*next;struct Node*previor;建立类对象 2.2 程序流程 (或程序结构、或类关系图等表明程序构成的内容，一般为流程图等) 显示菜单简单选择排序快速排序冒泡排序插入排序是否退出否是结束class LinkListprivate:Node*

3、 partion(Node*first,Node*end); /快速排序一趟public:Node*front;int comparision; /比较次数int movement; /移动次数LinkList() /无参构造front = new Node;front-next = NULL;front-previor = NULL;comparision = movement = 0;LinkList(int a,int n); /构造函数:建立双向链表void insertsort(); /插入排序void bubblesort(); /冒泡排序void Qsort(Node*x,Nod

4、e*y); /快速排序void selectsort(); /简单选择排序void show(); /显示排序结果LinkList(); /析构函数; 2.3 关键算法分析构造函数：通过使用头插法建立双向链表，其关键是多设一个指针变量用于储存上一个末节点的地址，这样才能使节点指向其上一个节点。在这次排序实验中，使用双向循环链表更方便进行遍历操作。LinkList:LinkList(int a,int n)front = new Node;front-next = NULL;front-previor = NULL;comparision = movement = 0;Node*x = new

5、Node;Node*s = new Node;s-data = an - 1;s-next = front;s-previor = front;front-next = s;front-previor = s;x = s;for (int i = n - 2; i = 0; i-)Node*s = new Node;s-data = ai; s-next = front-next;s-previor = front; front-next = s;x-previor = s;x = s;插入排序函数：将front头节点当作哨兵。从第二个有效节点开始进行插入，进行边查找，边后移的操作。void

6、LinkList:insertsort()Node*p = front-next;Node*s = p-next;while (s!=front)if (s-data data)comparision+;front-data = s-data;movement+;Node*x = p;Node*y = s;while (front-data data)comparision+;y-data = x-data;movement+;x = x-previor;y = y-previor;y-data = front-data;movement+;comparision+;p = p-next;s

7、= s-next;冒泡排序函数：每一次内循环边比较边交换，将无序区中最大的数放入有序区中，并记录无序元素的范围。当无序元素指向front时即整体排序完成。void LinkList:bubblesort()Node*s = front-previor; /初始化无序元素位置while (s != front)Node*p = s; /本次无序元素位置s = front;Node*x = front-next;Node*y = x-next;while (x != p)if (x-data y-data)comparision+;front-data = x-data;x-data = y-da

8、ta;y-data = front-data;movement = movement + 3;s = x; /更新无序元素位置comparision+;x = x-next;y = y-next; 快速排序函数：快速排序函数是个递归调用函数，关键在一次快速排序函数的编写。选择第一个元素作为分区的轴值，将待排序元素分成左右两个区域，左区的元素都比轴值小，右边的都更大。 然后反复进行此操作，即可完成排序。而结束递归的关键便是 左右分界节点有了直接前后继关系的时候。void LinkList:Qsort(Node*x,Node*y)if (x-previor != y)Node*pivot = pa

9、rtion(x, y);Qsort(x, pivot-previor);Qsort(pivot-next, y);Node* LinkList:partion(Node*first, Node*end)int basic = first-data;while (first != end)while (first != end) & (end-data = basic)end = end-previor;comparision+;comparision+;first-data = end-data;movement+;while (first != end) & (first-data next

10、;comparision+;comparision+;end-data = first-data;movement+;first-data = basic;movement+;return first;简单选择排序函数：是将待排序中最小的元素放置序列最前面，其关键是先通过循环比较确定最小元素的位置，再进行数据交换，从而大大减少了元素交换的次数。void LinkList:selectsort()Node*s = front-next;while (s != front-previor)Node*p = s-next;Node*record = s;while (p != front)Node*

11、x = record;if (p-data data)comparision+;record = p;comparision+;p = p-next;if (record != s)int a = record-data;record-data = s-data;s-data = a;movement = movement + 3;s = s-next;3. 程序运行结果分析4. 总结本次实验进行了使用链表存储结构实现插入排序、冒泡排序、快速排序、简单选择排序的编程。这使我对不同的排序方法有了更加深刻的理解和认识。从中也体会到不同的排序方式所耗费的时间复杂度实在是大相径庭，这警示我们，编写一个

12、时间复杂度小的排序函数在进行排序操作时，起着至关重要的作用。完整代码如下：#include#includeusing namespace std;struct Nodeint data;struct Node*next;struct Node*previor;class LinkListprivate:Node* partion(Node*first,Node*end); /快速排序一趟public:Node*front;int comparision; /比较次数int movement; /移动次数LinkList() /无参构造front = new Node;front-next =

13、NULL;front-previor = NULL;comparision = movement = 0;LinkList(int a,int n); /构造函数:建立双向链表void insertsort(); /插入排序void bubblesort(); /冒泡排序void Qsort(Node*x,Node*y); /快速排序void selectsort(); /简单选择排序void show(); /显示排序结果LinkList(); /析构函数;LinkList:LinkList(int a,int n)front = new Node;front-next = NULL;fro

14、nt-previor = NULL;comparision = movement = 0;Node*x = new Node;Node*s = new Node;s-data = an - 1;s-next = front;s-previor = front;front-next = s;front-previor = s;x = s;for (int i = n - 2; i = 0; i-)Node*s = new Node;s-data = ai;s-next = front-next;s-previor = front;front-next = s;x-previor = s;x =

15、s;Node* LinkList:partion(Node*first, Node*end)int basic = first-data;while (first != end)while (first != end) & (end-data = basic)end = end-previor;comparision+;comparision+;first-data = end-data;movement+;while (first != end) & (first-data next;comparision+;comparision+;end-data = first-data;moveme

16、nt+;first-data = basic;movement+;return first;void LinkList:insertsort()Node*p = front-next;Node*s = p-next;while (s!=front)if (s-data data)comparision+;front-data = s-data;movement+;Node*x = p;Node*y = s;while (front-data data)comparision+;y-data = x-data;movement+;x = x-previor;y = y-previor;y-dat

17、a = front-data;movement+;comparision+;p = p-next;s = s-next;void LinkList:bubblesort()Node*s = front-previor; /初始化无序元素位置while (s != front)Node*p = s; /本次无序元素位置s = front;Node*x = front-next;Node*y = x-next;while (x != p)if (x-data y-data)comparision+;front-data = x-data;x-data = y-data;y-data = front

18、-data;movement = movement + 3;s = x; /更新无序元素位置comparision+;x = x-next;y = y-next;void LinkList:Qsort(Node*x,Node*y)if (x-previor != y)Node*pivot = partion(x, y);Qsort(x, pivot-previor);Qsort(pivot-next, y);void LinkList:selectsort()Node*s = front-next;while (s != front-previor)Node*p = s-next;Node*r

19、ecord = s;while (p != front)Node*x = record;if (p-data data)comparision+;record = p;comparision+;p = p-next;if (record != s)int a = record-data;record-data = s-data;s-data = a;movement = movement + 3;s = s-next;void LinkList:show()Node*x = new Node;x = front-next;while (x != front)cout data next;cou

20、t endl 比较次数： comparision endl;cout 移动次数： movement endl;cout next;delete a;delete p;void showmenu();int main()showmenu();cin.get();cin.get();return 0;void showmenu()int jay17 = 2,6,7,9,15,24,29 ;int jay27 = 54,40,38,37,29,24,12 ;int jay37 = 16,45,81,1,4,69,100 ;LinkList zzj1(jay1, 7);LinkList zzj2(ja

21、y2, 7);LinkList zzj3(jay3, 7);cout 正序数据：; zzj1.show();cout 逆序数据：; zzj2.show();cout 乱序数据：; zzj3.show();int choice;cout choice;int count = 0;Node*x, *y, *z;while (choice != 5)switch (choice)case 1:if (count != 0)x = zzj1.front-next;y = zzj2.front-next;z = zzj3.front-next;for (int i = 0; i data = jay1i

22、;y-data = jay2i;z-data = jay3i;x = x-next;y = y-next;z = z-next;parision = zzj1.movement = 0;parision = zzj2.movement = 0;parision = zzj3.movement = 0;cout next;y = zzj2.front-next;z = zzj3.front-next;for (int i = 0; i data = jay1i;y-data = jay2i;z-data = jay3i;x = x-next;y = y-next;z = z-next;parision = zzj1.movement = 0;parision = zzj2.movement = 0;parision = zzj3.movement = 0;zzj1.bubblesort();zzj2.bubblesort();zzj3.bubblesort();cout next;y = zzj2.front-next;z = zzj3.front-next;for (