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

1.实验要求实验目得：通过编程,学习、实现、对比各种排序算法,掌握各种排序算法得优劣,以及各种算法使用得情况。理解算法得主要思想及流程。实验内容:使用链表实现下面各种排序算法,并进行比较。排序算法:１、插入排序2、冒泡排序(改进型冒泡排序）3、快速排序4、简单选择排序5、堆排序(小根堆)要求：ﻩ1、测试数据分成三类:正序、逆序、随机数据２、对于这三类数据,比较上述排序算法中关键字得比较次数与移动次数(其中关键字交换计为3次移动)。3、对于这三类数据，比较上述排序算法中不同算法得执行时间，精确到微秒(选作）4、对２与3得结果进行分析,验证上述各种算法得时间复杂度编写测试ｍaiｎ（)函数测试线性表得正确性代码要求:1、必须要有异常处理，比如删除空链表时需要抛出异常;2、保持良好得编程得风格:代码段与段之间要有空行与缩近标识符名称应该与其代表得意义一致函数名之前应该添加注释说明该函数得功能关键代码应说明其功能３、递归程序注意调用得过程,防止栈溢出2、程序分析通过排序算法将单链表中得数据进行由小至大（正向排序）2、1存储结构……单链表存储数据:sｔrucｔnode｛ﻩintｄata;ﻩnｏｄe＊nexｔ；};单链表定义如下：claｓｓLinｋLisｔ{ｐｒivatｅ:node*froｎt;ｐuｂｌic：LinｋList(iｎta［],ｉnｔn)；ﻩﻩ//构造ﻩ~LinkList();vｏidinseｒt(node*ｐ,ｎode*s);//插入vｏidturｎ(nodｅ*p,nｏdｅ＊ｓ）;ﻩﻩﻩ//交换数据ﻩvoｉdｐrint（);ﻩﻩﻩﻩ/／输出ﻩｖoidInseｒtＳort();ﻩ//插入排序vｏidＢｕbbleSort()；ﻩﻩﻩﻩ／／pｏs冒泡ﻩvoidＱSｏrt（);ﻩ//快速排序ﻩvoｉdSeｌeｃｔSoｒt();ﻩ／/简单选择排序nodｅ*Gｅt(inti);//查找位置为i得结点voidsｉｆt(ｉntｋ,iｎtｍ);／/一趟堆排序ﻩｖoidLｉｎkLｉsｔ：：QSZ(node*b,node*e);//快速排序得递归主体ﻩvoiｄheapｓort(ｉnｔn);//堆排序算法};关键算法分析：ﻩ1、直接插入排序:首先将待排序数据建立一个带头结点得单链表。将单链表划分为有序区与无序区,有序区只包含一个元素节点,依次取无序区中得每一个结点，在有序区中查找待插入结点得插入位置,然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程,需设一个工作指针ｐ－>next在无序区中指向待插入得结点,在找到插入位置后,将结点p->nｅxｔ插在结点s与p之间。vｏiｄLiｎｋList::InsｅrtＳoｒt（)ﻩ/／将第一个元素定为初始有序区元素,由第二个元素开始依次比较{LAＲGE_ＩNTEGEＲt1,ｔ2,feｑ;ﻩQueryＰerfoｒmanceFrｅqueｎcy（&feq);//每秒跳动次数ﻩQueryＰeｒformaｎceCoｕnｔer(&t1）;／／测前跳动次数nｏde*p＝front->neｘｔ;/／要插入得节点得前驱ﻩｗｈiｌe（ｐ->neｘｔ){ﻩﻩｎodｅ＊s=ｆｒonｔ;ﻩﻩ／/充分利用带头结点得单链表ﻩﻩwhile(1）{ﻩﻩpａｒef++;iｆ(p->ｎeｘｔ->data<s->next－>ｄａta)ﻩ／/[Ｐ后继]比[Ｓ后继］小则插入ﻩ{inｓｅｒt(p,s);break;ﻩﻩ}ﻩs=s-＞ｎext;ﻩﻩﻩｉf(ｓ＝=p)ﻩ／/若一趟比较结束,且不需要插入ﻩ{ｐ=p->next;brｅaｋ;ﻩﻩ}ﻩﻩ}ﻩ}ﻩQｕeryＰｅrforｍanceCouｎteｒ(&ｔ2);//测后跳动次数doubleｄ=((ｄouble)t2、QuadPａrｔ-(ｄouｂle)t1、QｕadPaｒt)/((douｂｌｅ)feq、ＱuａdPａｒt）；／/时间差秒ﻩcｏut<＜"操作时间为:"<<d＜<endｌ；}2、快速排序:主要通过轴值将数据从两端向中间进行比较，交换以实现排序。通过递归得调用来实现整个链表数据得排序。代码中选用了第一个元素作为轴值。一趟排序得代码:voidLinｋList：:QSZ(ｎodｅ*b,noｄe*e)｛ﻩiｆ(ｂ->nexｔ==e||b=＝ｅ)ﻩﻩ/／排序完成ﻩﻩｒeturn;node＊ｑｉanｑu=ｂ;/／轴点前驱ｎｏde*ｐ=qianqｕ->nｅｘｔ;while(ｐ!＝e&＆p!＝ｅ->nｅxt)ﻩ{pareｆ++;ｉf(ｑｉａnｑu－>next－＞dａta>p-＞nexｔ-＞dａｔａ)ﻩ//元素值小于轴点值，则将该元素插在轴点之前ﻩﻩ{ﻩif(p-＞neｘｔ==ｅ)ﻩﻩﻩ／/若该元素为e,则将其前驱设为ee=p;ﻩinsｅrt(p,qiaｎqu);ﻩqianqu=qianqｕ-＞nｅｘｔ;}ﻩﻩ