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

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