链表实现排序算法

北京邮电大学信息与通信工程学院第1页数据结构实验报告实验名称：实验三排序学生姓名：班级：班内序号：15学号：日期：2016.12.19北京邮电大学信息与通信工程学院第2页1．实验要求题目2使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性2.程序分析2.1存储结构我使用了线性表的链式存储结构，通过建立双向循环链表进行顺序存取。每个节点分为data、next、previor。data域称为数据域，数据通过node结构存储待排序的信息；next为指针域，用来储存直接后继的地址；prior为指针域，用来储存直接前继的地址；structNode{intdata;structNode*next;structNode*previor;};北京邮电大学信息与通信工程学院第3页2.2程序流程(或程序结构、或类关系图等表明程序构成的内容，一般为流程图等)classLinkList{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);//构造函数:建立双向链表建立类对象结束显示菜单插入排序冒泡排序快速排序简单选择排序是否退出否是北京邮电大学信息与通信工程学院第4页voidinsertsort();//插入排序voidbubblesort();//冒泡排序voidQsort(Node*x,Node*y);//快速排序voidselectsort();//简单选择排序voidshow();//显示排序结果~LinkList();//析构函数};2.3关键算法分析构造函数：通过使用头插法建立双向链表，其关键是多设一个指针变量用于储存上一个末节点的地址，这样才能使节点指向其上一个节点。在这次排序实验中，使用双向循环链表更方便进行遍历操作。LinkList::LinkList(inta[],intn){front=newNode;front-next=NULL;front-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;}}插入排序函数：将front头节点当作哨兵。从第二个有效节点开始进行插入，进行边查找，边后移的操作。voidLinkList::insertsort(){Node*p=front-next;Node*s=p-next;while(s!=front)北京邮电大学信息与通信工程学院第5页{if(s-datap-data){comparision++;front-data=s-data;movement++;Node*x=p;Node*y=s;while(front-datax-data){comparision++;y-data=x-data;movement++;x=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=front-next;Node*y=x-next;while(x!=p){if(x-datay-data){comparision++;front-data=x-data;x-data=y-data;y-data=front-data;北京邮电大学信息与通信工程学院第6页movement=movement+3;s=x;//更新无序元素位置}comparision++;x=x-next;y=y-next;}}}快速排序函数：快速排序函数是个递归调用函数，关键在一次快速排序函数的编写。选择第一个元素作为分区的轴值，将待排序元素分成左右两个区域，左区的元素都比轴值小，右边的都更大。然后反复进行此操作，即可完成排序。而结束递归的关键便是左右分界节点有了直接前后继关系的时候。voidLinkList::Qsort(Node*x,Node*y){if(x-previor!=y){Node*pivot=partion(x,y);Qsort(x,pivot-previor);Qsort(pivot-next,y);}}Node*LinkList::partion(Node*first,Node*end){intbasic=first-data;while(first!=end){while((first!=end)&&(end-data=basic)){end=end-previor;comparision++;}comparision++;first-data=end-data;movement++;while((first!=end)&&(first-data=basic)){first=first-next;comparision++;}comparision++;end-data=first-data;北京邮电大学信息与通信工程学院第7页movement++;}first-data=basic;movement++;returnfirst;}简单选择排序函数：是将待排序中最小的元素放置序列最前面，其关键是先通过循环比较确定最小元素的位置，再进行数据交换，从而大大减少了元素交换的次数。voidLinkList::selectsort(){Node*s=front-next;while(s!=front-previor){Node*p=s-next;Node*record=s;while(p!=front){Node*x=record;if(p-datax-data){comparision++;record=p;}comparision++;p=p-next;}if(record!=s){inta=record-data;record-data=s-data;s-data=a;movement=movement+3;}s=s-next;}}北京邮电大学信息与通信工程学院第8页3.程序运行结果分析北京邮电大学信息与通信工程学院第9页北京邮电大学信息与通信工程学院第10页4.总结本次实验进行了使用链表存储结构实现插入排序、冒泡排序、快速排序、简单选择排序的编程。这使我对不同的排序方法有了更加深刻的理解和认识。从中也体会到不同的排序方式所耗费的时间复杂度实在是大相径庭，这警示我们，编写一个时间复杂度小的排序函数在进行排序操作时，起着至关重要的作用。完整代码如下：#includeiostream#includeiomanipusingnamespacestd;structNode{intdata;structNode*next;structNode*previor;};classLinkList{private:Node*partion(Node*first,Node*end);//快速排序一趟北京邮电大学信息与通信工程学院第11页public:Node*front;intcomparision;//比较次数intmovement;//移动次数LinkList()//无参构造{front=newNode;front-next=NULL;front-previor=NULL;comparision=movement=0;}LinkList(inta[],intn);//构造函数:建立双向链表voidinsertsort();//插入排序voidbubblesort();//冒泡排序voidQsort(Node*x,Node*y);//快速排序voidselectsort();//简单选择排序voidshow();//显示排序结果~LinkList();//析构函数};LinkList::LinkList(inta[],intn){front=newNode;front-next=NULL;front-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;北京邮电大学信息与通信工程学院第12页front-next=s;x-previor=s;x=s;}}Node*LinkList::partion(Node*first,Node*end){intbasic=first-data;while(first!=end){while((first!=end)&&(end-data=basic)){end=end-previor;comparision++;}comparision++;first-data=end-data;movement++;while((first!=end)&&(first-data=basic)){first=first-next;comparision++;}comparision++;end-data=first-data;movement++;}first-data=basic;movement++;returnfirst;}voidLinkList::insertsort(){Node*p=front-next;Node*s=p-next;while(s!=front){if(s-datap-data){北京邮电大学信息与通信工程学院第13页comparision++;front-data=s-data;movement++;Node*x=p;Node*y=s;while(front-datax-data){comparision++;y-data=x-data;movement++;x=x-previor;y=y-previor;}y-data=front-data;movement++;}compari