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

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(） //将第一个元素定为初始有序区元素，由第二个元素开始依次比较 ｛ 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 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，则将其前驱设为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)； //每秒跳动次数 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 〈〈 endl; ｝

3.改进版的冒泡排序：

通过设置pos来记录无序边界的位置以减少比较次数.

将数据从前向后两两比较，遇到顺序不对是直接交换两数据的值. 每交换一次movef+3； void LinkList::BubbleSort(） ｛ LARGE_INTEGER t1， t2, feq； QueryPerformanceFrequency(＆feq）； //每秒跳动次数 QueryPerformanceCounter(＆t1）; //测前跳动次数 node * p = front-〉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 ＊ 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 — （double)t1。QuadPart） / （（double)feq.QuadPart)；//时间差秒 cout <〈 ”操作时间为:\" 〈< d 〈< endl； }

4。选择排序：

每趟排序再待排序的序列中选择关键码最小的元素,顺序添加至已排好的有序序列最后，知道全部记录排序完毕。 void LinkList:：SelectSort() ｛ LARGE_INTEGER t1, t2, feq; QueryPerformanceFrequency(＆feq）； //每秒跳动次数 QueryPerformanceCounter（＆t1）; //测前跳动次数 node ＊ s = front； while （s-〉next->next) { node ＊ p = s; node * index = p; while (p->next） { comparef++； if （p—〉next—〉data 〈 index-〉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。堆排序：

利用前一趟比较的结果来减少比较次数,提高整体的效率。

其中通过链表储存了一棵树。 选择使用小根堆进行排序. void LinkList:：sift（int k, int m） { int i = k, j = 2 ＊ i； while （j 〈= m) ｛ comparef++； if (jdata)) j++; if （Get（i)—>data 〈 Get(j)—〉data) break； else ｛ turn(Get(i）, Get(j）); 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; ｝

其中堆排序中需要知道孩子节点和父亲节点处的值,故设置了函数获取i出的指针。 node*LinkList::Get（int i) ｛ node＊p = front->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。InsertSort（); 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） << 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（＆feq）; //每秒跳动次数

QueryPerformanceCounter(&t1); //测前跳动次数 node * p = front—>next; //要插入的节点的前驱

QueryPerformanceCounter（&t2）； //测后跳动次数 double d = (（double）t2。QuadPart — （double）t1。QuadPart) / ((double)feq.QuadPart)；//时间差秒

cout 〈〈 \"操作时间为：” 〈< d << endl; ｝；

2。3 其他

算法的时间复杂度： 排序方法 直接插入排序 快速排序 改进版冒泡排序 选择排序 堆排序 随机序列的平均情况 O(n2） 最好情况 O（n） 最坏情况 O（n2) 辅助空间 O(1) O（nlog2n） O（nlog2n） O(n2) O(log2n) ～O（n） O（n2) O （n） O（n2） O（1） O(n2) O（n2） O（n2) O(1) O(nlog2n） O（nlog2n） O (nlog2n) O（1） 3. 程序运行结果

1。流程图：

开始 初始化正序链表，调用各类排序，并输出运行结果 初始化逆序链表，调用各类排序，并输出运行结果 初始化顺序随机的链表，调用各类排序，并输出运行结果 结 束

2.测试条件：

如果需要对不同的正序，逆序随机序列进行排序，则需要在main函数中进行初始化设置。3.测试结论：

4。 总结

通过这次实验我再次复习了链表的建立及相应的操作，对各类排序算法的实现也有了新的理解，在调试过程中出现了许多问题也花费了很多时间和精力去逐步解决，最后程序运行成功的瞬间真的很开心. 问题一:

直接插入排序中若是使用从后向前比较插入的话（即书上的办法）难以找到该节点的前驱节点，不方便进行操作，所以最后采用了从前向后进行比较.

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 next->data) // ［P后继]比［S后继］小则插入 ｛ insert(p, s）； break； ｝ s = s—〉next； if （s == p) //若一趟比较结束，且不需要插入 { p = p->next; break； } } ｝ 问题二：

如何将书上以数组方式储存的树转化为链表储存并进行操作？

原本打算建立一颗完全二叉树储存相应数据再进行排序，但是那样的话需要新设置结点存左孩子右孩子,比较麻烦容易出错，所以选择了利用Get(int i)函数将筛选结点的位置获得。 与书上代码相比修改如下：

if （j〈m ＆& (Get（j）—〉data>Get(j + 1）—>data)) j++;

if （Get(i)—〉data 〈 Get(j)-〉data） break； else { turn(Get(i)， Get（j））; i = j; j = 2 * i； ｝

问题三：

时间如何精确至微秒？需要调用函数，这个问题是上网查找解决的。

总结：解决了以上的问题后代码就比较完整了，可是还是希望通过日后的学习能将算法编

写得更完善,灵活，简捷. 附录:

完整代码如下：

#include ”lianbiaopaixu。h\" ＃include using namespace std; void main（） ｛ int a［10］ = { 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 b[10］ = { 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 c[10] = ｛ 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 〈iostream〉 ＃include〈stdio。h> ＃include

#include 〈windows。h> using namespace std； int comparef; int movef； 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）; //堆排序算法 ｝;

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 = a[i］; 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->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 << p—〉data << ’ '; p = p->next; } cout << endl; }

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; ｝

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，则将其前驱设为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)； //每秒跳动次数 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 <〈 endl; }

void LinkList:：BubbleSort() { LARGE_INTEGER t1， t2, feq； QueryPerformanceFrequency(&feq); //每秒跳动次数 QueryPerformanceCounter(＆t1）; //测前跳动次数 node ＊ p = front—>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 * 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 — （double）t1.QuadPart） / （（double）feq。QuadPart)；//时间差秒 cout 〈< ”操作时间为：” << d 〈< endl； ｝

void LinkList:：SelectSort(） ｛ LARGE_INTEGER t1, t2， feq; QueryPerformanceFrequency（＆feq）; //每秒跳动次数 QueryPerformanceCounter(&t1）; //测前跳动次数 node * s = front; while (s—〉next-〉next） { node ＊ p = s； node * index = p； while （p->next） { comparef++; if (p-〉next—>data < index->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； }

node*LinkList::Get(int i) ｛ node＊p = front—>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 （j〈m ＆＆ （Get（j)—>data〉Get（j + 1)—>data)) j++； if (Get(i)->data 〈 Get（j）—〉data) break; else { turn（Get(i）， Get（j）)； 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.InsertSort()； 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) 〈〈 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; }