c数据结构实验链表排序

if (Get(i)->data < Get(j)->data) break; else { turn(Get(i), Get(j)); i = j; j = 2 * i; }

问题三：

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

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

写得更完善，灵活，简捷。 附录： 完整代码如下：

#include \ #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 << \逆序数列：\; 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 << \随机数列：\; 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; }