if (Get(i)->data < Get(j)->data) break; else { turn(Get(i), Get(j)); i = j; j = 2 * i; }
问题三:
时间如何精确至微秒?需要调用函数,这个问题是上网查找解决的。
总结:解决了以上的问题后代码就比较完整了,可是还是希望通过日后的学习能将算法编
写得更完善,灵活,简捷。 附录: 完整代码如下:
#include \ #include
#include
#include
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
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; }
c数据结构实验链表排序
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)