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

发布时间 : 2024/6/16 20:47:06 星期日 文章c++数据结构实验链表排序更新完毕开始阅读

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 \ #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() {