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

《c++大数据结构实验链表排序.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1．实验要求i.实验目的:通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。理解算法的主要思想及流程。ii.实验容：使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序（改进型冒泡排序）3、快速排序4、简单选择排序5、堆排序（小根堆）要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试m

2、ain()函数测试线性表的正确性iii.代码要求：1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程，防止栈溢出2.程序分析通过排序算法将单链表中的数据进行由小至大（正向排序）2.1存储结构……单链表存储数据：structnode{intdata;nodenext;};单链表定义如下：classLinkList{private:nodefront;public:LinkList(inta[],intn);/

3、/构造~LinkList();voidinsert(nodep,nodes);//插入voidturn(nodep,nodes);//交换数据voidprint();//输出voidInsertSort();//插入排序voidBubbleSort();//pos冒泡voidQSort();//快速排序voidSelectSort();//简单选择排序nodeGet(inti);//查找位置为i的结点voidsift(intk,intm);//一趟堆排序voidLinkList::QSZ(nodeb,nodee);//快速排序的递归主体voidheapsort(intn);/

4、/堆排序算法};2.2关键算法分析：1.直接插入排序：首先将待排序数据建立一个带头结点的单链表。将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程，需设一个工作指针p->next在无序区中指向待插入的结点，在找到插入位置后，将结点p->next插在结点s和p之间。voidLinkList::InsertSort()//将第一个元素定为初始有序区元素，由第二个元素开始依次比较{LARGE_INTEGERt1,t2,feq;QueryPerforma

5、nceFrequency(&feq);//每秒跳动次数QueryPerformanceCounter(&t1);//测前跳动次数nodep=front->next;//要插入的节点的前驱while(p->next){nodes=front;//充分利用带头结点的单链表while(1){comparef++;if(p->next->datanext->data)//[P后继]比[S后继]小则插入{insert(p,s);break;}s=s->next;if(s==p)//若一趟比较结束，且不需要插入{p=p->next;break;}}}QueryPerformanc

6、eCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒cout<<"操作时间为："<next==eb==e)//排序完成return;nodeqianqu=b;//轴点前驱nodep

7、=qianqu->next;while(p!=e&&p!=e->next){comparef++;if(qianqu->next->data>p->next->data)//元素值小于轴点值，则将该元素插在轴点之前{if(p->next==e)//若该元素为e，则将其前驱设为ee=p;insert(p,qianqu);qianqu=qianqu->next;}elsep=p->next;}QSZ(b,qianqu);//继续处理轴点左侧链表QSZ(qianqu->next,e);//继续处理轴点右侧链表