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

其中堆排序中需要知道孩子节点和父亲节点处的值，故设置了函数获取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.统计时间的函数： #include {

LARGE_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(log2n) ~O(n) O(nlog2n) O(nlog2n) O(n2) 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 (jdata>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 #include #include #include

#include #include 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 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 (jdata>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; }