链表实现排序算法.docx

《链表实现排序算法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告实验名称：实验三排序学生姓名：班级：班内序号：15学号：日期：2016.12.19实验要求题目2使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性2.程

2、序分析2.1存储结构我使用了线性表的链式存储结构，通过建立双向循环链表进行顺序存取。每个节点分为data、next、previor。data域称为数据域，数据通过node结构存储待排序的信息；next为指针域，用来储存直接后继的地址；prior为指针域，用来储存直接前继的地址；structNode{intdata;structNode*next;structNode*previor;};建立类对象2.2程序流程(或程序结构、或类关系图等表明程序构成的内容，一般为流程图等)显示菜单简单选择排序快速排序冒泡排序插入排序是否退出否是结束classL

3、inkList{private:Node*partion(Node*first,Node*end);//快速排序一趟public:Node*front;intcomparision;//比较次数intmovement;//移动次数LinkList()//无参构造{front=newNode;front->next=NULL;front->previor=NULL;comparision=movement=0;}LinkList(inta[],intn);//构造函数:建立双向链表voidinsertsort();//插入排序voidbubbl

4、esort();//冒泡排序voidQsort(Node*x,Node*y);//快速排序voidselectsort();//简单选择排序voidshow();//显示排序结果~LinkList();//析构函数};2.3关键算法分析构造函数：通过使用头插法建立双向链表，其关键是多设一个指针变量用于储存上一个末节点的地址，这样才能使节点指向其上一个节点。在这次排序实验中，使用双向循环链表更方便进行遍历操作。LinkList::LinkList(inta[],intn){front=newNode;front->next=NULL;front

5、->previor=NULL;comparision=movement=0;Node*x=newNode;Node*s=newNode;s->data=a[n-1];s->next=front;s->previor=front;front->next=s;front->previor=s;x=s;for(inti=n-2;i>=0;i--){Node*s=newNode;s->data=a[i];s->next=front->next;s->previor=front;front->next=s;x->previor=s;x=s;}}插入排序

6、函数：将front头节点当作哨兵。从第二个有效节点开始进行插入，进行边查找，边后移的操作。voidLinkList::insertsort(){Node*p=front->next;Node*s=p->next;while(s!=front){if(s->datadata){comparision++;front->data=s->data;movement++;Node*x=p;Node*y=s;while(front->datadata){comparision++;y->data=x->data;movement++;x

7、=x->previor;y=y->previor;}y->data=front->data;movement++;}comparision++;p=p->next;s=s->next;}}冒泡排序函数：每一次内循环边比较边交换，将无序区中最大的数放入有序区中，并记录无序元素的范围。当无序元素指向front时即整体排序完成。voidLinkList::bubblesort(){Node*s=front->previor;//初始化无序元素位置while(s!=front){Node*p=s;//本次无序元素位置s=front;Node*x=fr

8、ont->next;Node*y=x->next;while(x!=p){if(x->data>y->data){comparision++;front->data