《C++数据结构之链表排序》由会员分享，可在线阅读，更多相关《C++数据结构之链表排序（11页珍藏版）》请在金锄头文库上搜索。
1、2009级数据结构实验报告实验名称：使用链表实现各种排序算法学生姓名：桂柯易班级：2009211120班内序号：07学号：09210580日期:2010年12月19日1. 实验要求【实验目的】通过选择实验内容中的两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法的使用的情况。【实验内容】使用链表实现下面各种排序算法，并进行比较。排序算法如下： 插入排序； 冒泡排序； 快速排序； 简单选择排序； 其他。具体要求如下。 测试数据分成三类：正序、逆序、随机数据。 对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 对于这三类数据
2、，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）。 对和的结果进行分析，验证上述各种算法的时间复杂度。 编写main（）函数测试各种排序算法的正确性。2. 程序分析2.1存储结构存储结构：链表轆表firstaoaoaianiA2.2关键算法分析【设计思想】以直接插入排序为例：首先将待排序数据建立一个带头结点的单链表。在单链表中进行直接插入排序的基本思想是：将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程，需设一个工作指针q在无序区中指向待插入的结点，为
3、了查找正确的插入位置，每趟排序前需将工作指针pre和p指向头结点和开始结点，在找到插入位置后，将结点q插在结点pre和p之间。这相当于在单链表中删除结点q,因此为了保证链表不断开，须在删除结点q之前保留结点q的后继结点的地址。【复杂度】(1) 建立链表存储数据的算法：Node*CreateSortNode(intcount,int*array)Node*p1,*p2,*head;inti;head=NULL;for(i=0;ivcount;i+)p1=newNode;p1-data=arrayi;p1-next=NULL;if(i=0)head=p1;elsep2-next=pl;p2=pl;
4、p2-next=NULL;returnhead;该算法的时间复杂度为T(N)=O(N)(2) 输出数据的算法：voidListSortNode(Node*start)Node*p;p=start;while(p!=NULL)coutvvp-datavvO;p=p-next;coutvvendl;该算法的时间复杂度T(N)=O(N)(3) 插入排序算法：Node*Insert_Sort_LinkTable(Node*head)_LARGE_INTEGERtime_start;_LARGE_INTEGERtime_over;doubledqFreq;LARGE_INTEGERf;QueryPerf
5、ormanceFrequency(&f);dqFreq=(double)f.QuadPart;QueryPerformanceCounter(&time_start);Node*s,*newhead,*p,*pre,*min;s=head;newhead=NULL;b1+=2;while(s!=NULL)a1+,b1+=3;min=s;p=newhead;while(p!=NULL&p-datavmin-data)pre=p,p=p-next;b1+=2,a1+=2;s=s-next;if(p=newhead)al+,bl+=2;newhead=min;newhead-next=p;elsea
6、1+,b1+=2;pre-next=min;min-next=p;QueryPerformanceCounter(&time_over);returnnewhead;该算法的时间复杂度T(N)=O(N2)(4) 冒泡排序算法：Node*Ebullient_Sort_LinkTable(Node*head)_LARGE_INTEGERtime_start;_LARGE_INTEGERtime_over;doubledqFreq;LARGE_INTEGERf;QueryPerformanceFrequency(&f);dqFreq=(double)f.QuadPart;QueryPerforman
7、ceCounter(&time_start);Node*q,*tail,*p,*t;q=newNode;q-next=head;head=q;b2+=3;for(tail=NULL;tail!=head;tail=p)b2+=2,a2+=2;for(p=q=head;q-next-next!=tail;q=q-next)b2+=3,a2+=2;if(q-next-dataq-next-next-data)a2+,b2+=5;t=q-next-next;q-next-next=t-next;t-next=q-next;q-next=t;p=q-next-next;q=head;head=head
8、-next;b2+=2;deleteq;QueryPerformanceCounter(&time_over);returnhead;该算法的时间复杂度T(N)=O(N2)(5) 快速排序算法：Node*Fast_Sort_LinkTable(Node*head,Node*tail)_LARGE_INTEGERtime_start;_LARGE_INTEGERtime_over;doubledqFreq;LARGE_INTEGERf;QueryPerformanceFrequency(&f);dqFreq=(double)f.QuadPart;QueryPerformanceCounter(&
9、time_start);if(head=NULLIItail=NULL)returnNULL;if(head=tail)returnNULL;Node*p,*r,*pre;pre=head;p=head-next;r=head;b3+=3;while(p&p!=tail-next)a3+=2;if(p-datadata)a3+,b3+=5;r=pre;pre=pre-next;swamp(pre-data,p-data);p=p-next;b3+;swamp(head-data,pre-data);b3+=3;Fast_Sort_LinkTable(head,r);Fast_Sort_Link
10、Table(pre-next,tail);QueryPerformanceCounter(&time_over);returnhead;该算法的时间复杂度T(N)=O(NlogN)(6) 简单选择排序算法：Node*Select_Sort_LinkTable(Node*head)_LARGE_INTEGERtime_start;_LARGE_INTEGERtime_over;doubledqFreq;LARGE_INTEGERf;QueryPerformanceFrequency(&f);dqFreq=(double)f.QuadPart;QueryPerformanceCounter(&ti
11、me_start);Node*newhead,*tail,*p,*pre,*min;newhead=NULL;b4+;while(head!=NULL)a4+;for(p=min=head;p-next!=NULL;p=p-next)a4+,b4+=3;if(p-next-datadata)a4+,b4+=2;pre=p;min=p-next;if(min=head)head=head-next;a4+,b4+;elsepre-next=min-next;a4+,b4+;if(newhead=NULL)tail=newhead=min;a4+,b4+;elsetail=tail-next=mi
12、n;a4+,b4+;if(newhead!=NULL)tail-next=NULL;a4+,b4+;QueryPerformanceCounter(&time_over);returnnewhead;该算法的时间复杂度T(N)=O(N2)2.3其他由于程序源代码在上述时间复杂度分析中已基本全部提及，此处不再附加。3. 程序运行结果1.测试主函数流程:一二一二一二-G-主卡卡讲一输A泡速单软出S冒映简4念_一二一二一二-G-入泡速叢岀插冒咲简123456r012381803曰.I;.5数数787eve1-:i庆庆曰羲动间比移.时壬舌疋77訂耳键果&庁运关关结吕试的的的的45调tyjwtz续三三三
13、-H-j-2圭主壬主壬.甜入入入入17需I一rrn一rrn一rrn一rrj1挺推推推34键2-148J9百_r牛请选择你需要进行的操作:C:User5gkyDesktop雷揭作业第四次实验ORTXDgbugsort.exeill245812293曰i:7.数数:袂袂養动间比移-时壬舌疋盪键果233=运关关结8试的的的的9调续-壬壬壬壬6甜泡泡泡泡5需2冒冒冒冒45如38FHT7也6安4青一二一二一二-G-入泡速叢岀插冒丸简请选择你需要进行的操作：123458曰習疋&-数:次次曰羲动90密间比移：最一一时壬舌疋釦盪键果67麵运关关结4tr旳囱囱.旳3I-1-.R.R.R.R2尸-1S8试一一-二
14、_-一51.一-fJ.一七.一-fJ.一-fJ.-I续选选选选&继一一单单单单#:EB連B间45如一一|C:U5ersgkyDesktop诸I据结构作业熾四次实验SORTDebugsort.exe45678224179877562347890请选择你需要进行的操作：123470660I:暑疋4曰習習習習習習習習習習羲数!3-JJ-JJ-JJ-JJ-JJ-m.-JJ-JJ-JJ-JJ-JJ-17.-1.-2.1.1.1.1.1.1.1.1.1.1.1.IT.JI寸寸寸寸寸寸寸寸寸寸寸.亠K为8HHHHH0HHHHH-T-+i9-丁-丁-丁-丁-丁-丁-丁-丁-丁-丁-丁-+:?e106360127802暑疋82.数数67:次次4曰羲动23
