数据结构试验哈希表优质资料

数据结构试验哈希表优质资料(可以直接使用，可编辑优质资料，欢迎下载）

第10章实验数据结构试验哈希表优质资料(可以直接使用，可编辑优质资料，欢迎下载）实验名称：考试日程安排与成绩统计实验类型：综合性性实验班级：20210611学号：2021061118姓名：郭鑫问题描述=1\*GB3①问题描述现要安排考试的考表（即考试日程表），假设共有10个班的学生，要安排10门必修课程的考试，必修课程是以班级来确定的，每个班各有3门必修课，因此各班的考试科目是不相同的；安排考表的原则是：相同课程采用统一的试卷，因此同一门课程的考试必须在相同时间进行，同一个班所修的科目必须安排在不同的时间进行考试，以避免考试时间的冲突。并要求全部考试的日程尽可能短。要求对考试结果做统计和排序。假设分别以编号0,1,2,3,4,5,6,7,8,9代表10门要考试的课程，以B1，B2，B3，B4，B5，B6，B7，B8，B9，B10代表10个班，每个人的信息包括学号、姓名、班级、各门考试课程成绩、三门课程总成绩，每个班的学生人数自行设定。要求设计一个简单的考试成绩的查询统计系统实现以下功能：显示学生考试情况-按考试总分从高到底输出全体学生的信息。-按照从B1到B10的班级顺序，分班级按照考试总分从高到底的顺序输出各班学生的信息。-输出指定班的学生考试成绩信息。统计学生考试成绩-按总成绩统计出90分以上、80~89分、70~79分、60~69分、60分以下各分数段的人数，并按总分从高到低分段输出。-根据指定的某们课程的成绩，统计出上述各分数段的人数，并按分数从高到低分段输出。-统计并输出指定班级中总成绩或某一门课成绩的各分数段人数和每个人具体的信息。查找学生成绩-查找总分或某一门课程成绩的指定分数段的人数及学生的详细信息。-查找指定班级中总分或某一门课程成绩属于某分数段的学生详细信息。-查找指定学生（例如给定学号）的具体信息，包括：姓名、班级、各科分数、总分数等。=2\*GB3②求解方法说明考试日程安排问题。该问题实际上是对若干元素进行子集划分的问题，要求所划分的每个子集中的元素没有“考试冲突”关系。假设各个班的考试课程分别为：(1,4,8),(1,3,7),(8,2,4),(1,0,5),(2,6,9),(3,0,8),(4,5,9),(2,9,7),(6,0,3),(5,6,9)。根据题中考试安排原则，各个班要进行的考试课程可以抽象为“考试冲突关系”，归纳各个班的考试课程可以整理得到考试冲突关系：R={(1,4),(1,8),(4,8),(1,3),(1,7),(3,7),(8,2),(2,4),(1,0),(1,5),(0,5),(2,6),(2,9),(6,9),(3,0),(0,8),(3,8),(4,5),(5,9),(4,5),(2,7),(9,7),(6,0),(6,3),(5,6)}。显然，“考试冲突”关系R的每个有序对中的两门课程不能安排在同一时间考试，据此可以将10门课划分为若干个考试时间没有冲突的子集，并且使考场的场次尽量少，使得整个考试时间尽可能短。上述子集划分问题可以用对集合中的元素逐个“筛选”的办法来解决。首先将集合的第1个元素置为第1个子集，再逐个检查集合中的其余元素是否和第1个元素有考试冲突，若不存在考试冲突，则将其加入到第1个子集中，继续检查集合中的其余元素，凡是不与第1个子集中的元素冲突的元素都逐个将其加入到其中；接着按同样的方法“筛选”出若干没有考试冲突的元素构成第2个子集，…，该过程一直到集合中的全部元素都分到某个子集中结束。得到的每一个子集中的课程就是可以安排在同一时间考试的课程。不同子集的课程则要安排在不冲突的时间考试。考试分数的统计与排序考试成绩输出每个学生的信息记录数据项应包括：学号、姓名、班级、课程1、课程2、…、课程10、总成绩。按总分高低输出所有学生信息时，应该以总成绩为关键字从高分到低分对所有的学生记录进行排序，排序方法自行选定，然后依次输出各个记录。按照班级顺序和总分高低输出各班学生信息时，要对学生记录进行多关键字排序，首先以总成绩为关键字从高分到低分对所有的学生记录进行排序，然后再以班号为关键字对全部学生记录排序，再输出结果。统计成绩统计各分数段的人数，要求由用户输入，具体要求可以有：按照总成绩统计各分数段的人数，并输出各分数段的学生记录，即在统计一个分数段的人数过程中，要输出满足查找条件的学生记录，再输出统计的结果。指定某一门课程，统计各分数段的人数并输出各分数段的学生记录。对指定班级中总成绩或指定课程成绩做各分数段人数的统计，也要输出各分数段的学生记录。查找成绩查找要求由用户输入，可以输入以下条件：查找指定分数项（总分或某一门课程）的某分数段的学生信息，输出查找结果。查找指定班级、指定分数项的某分数段的学生信息，输出查找结果。查找指定学生（给定学号）的具体信息，输出查找结果。③算法提示考试场次的划分——“无考试冲突”子集划分的算法思路。为了把10门课程划分为时间上不冲突的若干场考试，可以利用一个循环队列来实现求解方法中说明的“筛选”过程。首先定义一个循环队列，再把10门课程的编号从小到大依次加入到循环队列中，然后重复下列步骤：队头元素出队并作为当前子集的第1个元素。队头元素继续依次出队，每出队一个队头元素都要检查与当前子集中的元素是否有“考试冲突”；如果没有冲突，则将其加入到当前子集中，否则将其重新加入队列中，等待以后加入新子集的机会。比较刚出队元素与前一出队元素编号。因为队列中原有的元素是以编号从小到大的顺序排列的，重新入队的元素编号一定小于它的前一元素，所以一旦发现目前出队的元素编号小于前一个出队的元素，就可以断定当前的“考试冲突”子集已经构建完，队列中剩余元素应该构建新的子集。为此，在当前的队头元素出队前，要先记下刚刚出队的元素，以便判断当前出队的元素是否要开始构建一个新子集。重复上述步骤一直到队列空，则“无考试冲突”子集划分完成。由上述算法思路可以知道，“无考试冲突”子集的划分过程是一个循环的执行过程，循环中的主要操作是元素出队和判断的操作。判断操作包括出队元素是否可以加入当前子集和是否要开始构建一个新子集两个方面，对后一个判断如前所述，通过比较出队元素与前一个出队元素编号大小可以确定。为了判断出队元素与当前子集中的元素是否有“考试冲突”，可以定义一个二维数组conf[n][n]来表示课程的考试冲突关系矩阵，矩阵中各元素的值根据以下规则确定，若编号为i的课程和编号为j的课程有考试冲突，则置conf[i][j]=1，否则置conf[i][j]=0，考试冲突关系矩阵如图1所示。0101011010100111011000001011111100001110011001001111001010011011010001011100000111111000000010111100图1考试冲突关系矩阵利用“考试冲突”关系矩阵可以检查出队元素i是否与当前子集中的元素有考试冲突，其方法是：当课程号为j1，j2，…，jk的元素已经在当前子集S中，要判断目前出队的元素i是否可以加入子集S，只要检查“考试冲突”关系矩阵中第i行的元素conf[i][j1]，conf[i][j2]，…conf[i][jk]的值是否为0即可。如果这些元素的值都为0，表示课程i与子集中的课程没有考试冲突，可以加入其中，否则说明表示课程i与子集中的某些课程有考试冲突，它不能加入该子集中。为了减少在二维数组conf中查找元素的操作，可以定义一个一维数组clash[n]来方便出队元素i是否要加入当前子集的判断，数组clash[n]用于记录出队元素i与当前子集中的元素是否存在考试冲突的信息。每当开始构建一个新子集时，先将数组clash[n]的各元素初始化为0，当有编号为i的课程加入子集时，将“考试冲突”关系矩阵中第i行的各列的值与数组clash的各对应元素的值相加，因而使得数组clash中和编号为i的元素有考试冲突的相应元素的值不再是0，当下一个队头元素j出队时，只要检查数组clash中第j个元素的值是否为0，就可以判断其是否与当前子集中的元素有考试冲突；若数组clash中第j个元素的值不为0，则说明元素j与当前子集中元素存在考试冲突，应将其重新加入队列；若数组clash中第j各元素的值为0，则说明它与当前子集中元素不存在考试冲突，应该将它加入当前子集中，同时要将“考试冲突”关系矩阵中第j行的各列的值与数组clash的各对应元素的值相加，这个过程一直到队列空，则划分无考试冲突子集完成。划分结果可以用一个二维数组来记录各子集中的元素的方式来表示，也可以用一个一维数组来记录每个元素其所属的子集号的方式来表示。上述算法的思路可以描述如下：建立表示课程考试冲突关系矩阵的二维数组conf[n][n]；定义用于检查当前子集的课程考试冲突信息的数组clash[n]；定义用于记录子集划分结果的数组result[n]；pre=n;//pre用于记录前一个出队元素的编号，初始值置为n以新建第1个子集k=0；//k用于记录子集序号0~9(课程编号)依次入队；while（队列不空）{队头元素i出队；if(i<pre)//刚出队元素小于前一个出队元素，生成一个新子集{k++;数组clash初始化；}if(i可以加入当前子集)//如果刚出队元素与当前子集中的元素无考试冲突，将其加入当前子集{将i加入当前子集，记录i所属子集的序号；将conf数组第i行各列的值与clash数组对应列的值相加并记入clash中；}else//如果刚出队元素与当前子集中的元素有考试冲突，将其重新入队将i重新加入队列；pre=i;}考试成绩统计和排序的实现按总成绩或按某一门课的成绩统计并输出人数时，应该使各分数段的人数和每个学生的信息清晰的分开。对全体学生或对某一个班的学生的成绩进行排序时，排序方法可以任意选择。就本实验问题而言，因表长不大采用简单的排序方法就可以达到目的，但为了比较各种常用排序方法性能和适用场合，还可以采用不同的排序方法实现排序。对多关键字的排序要求，要注意排序方法的稳定性问题。例如，在按总成绩从高分到低分对全体学生进行排序后，再按班级从高分到低分进行排序，此时要求分班级排序时采用的排序方法其动态性能必须是稳定的。同样地，如果在按总成绩从高分到低分排序的基础上，再要求按某一门课的成绩从高分到低分排序，也要求第2层排序一定注意选择动态性能稳定的排序方法。在实现查找或排序功能时，其查找或排序的依据（指定项）和目标（输出结果）通过提示用户输入来确定。数据结构设计typedefintKeyType;typedefcharInfoType[10];typedefstruct/*记录类型*/{KeyTypekey;/*关键字项*/InfoTypedata;/*其他数据项,类型为InfoType*/}RecType算法设计#include<iostream>usingnamespacestd;#defineMAXE20/*线性表中最多元素个数*/typedefintKeyType;typedefcharInfoType[10];typedefstruct/*记录类型*/{KeyTypekey;/*关键字项*/InfoTypedata;/*其他数据项,类型为InfoType*/}RecType;voidSelectSort(RecTypeR[],intn)/*直接选择排序算法*/{inti,j,k,l;RecTypetemp;for(i=0;i<n-1;i++)/*做第i趟排序*/{k=i;for(j=i+1;j<n;j++)/*在当前无序区R[i..n-1]中选key最小的R[k]*/if(R[j].key<R[k].key)k=j;/*k记下目前找到的最小关键字所在的位置*/if(k!=i)/*交换R[i]和R[k]*/{temp=R[i];R[i]=R[k];R[k]=temp;}printf("i=%d",i);/*输出每一趟的排序结果*/for(l=0;l<n;l++)printf("%2d",R[l].key);printf("\n");}}intmain(){inti,k,n=10,m=5;KeyTypea[]={6,8,7,9,0,1,3,2,4,5};RecTypeR[MAXE];for(i=0;i<n;i++)R[i].key=a[i];printf("\n");printf("初始关键字");/*输出初始关键字序列*/for(k=0;k<n;k++)printf("%2d",R[k].key);printf("\n");SelectSort(R,n);printf("最后结果");/*输出初始关键字序列*/for(k=0;k<n;k++)printf("%2d",R[k].key);printf("\n\n");system("pause");}4.界面设计程序包含有多个功能，所以，采用菜单，以方便用户进行功能选择。菜单如下：1：1：直接插入排序算法验证2：快速排序算法验证。3:直接选择排序算法验证。4:退出运行、测试与分析1）直接插入排序算法验证快速排序算法验证。3）直接选择排序算法验证。实验收获及思考这次实验我对选择拍循序，插入排序，快速排序有了更好的理解，以及时间复杂度的问题分析，通过这次实验，我对排序的内容有了更深入的了解。编程技术有了很大的提高1．实验要求实验目的:通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。理解算法的主要思想及流程。实验内容：使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序（改进型冒泡排序）3、快速排序4、简单选择排序5、堆排序（小根堆）要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性代码要求：1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程，防止栈溢出2.程序分析通过排序算法将单链表中的数据进行由小至大（正向排序）2.1存储结构……单链表存储数据：……structnode{intdata;node*next;};单链表定义如下：classLinkList{private:node*front;public: LinkList(inta[],intn);//构造 ~LinkList();voidinsert(node*p,node*s);//插入voidturn(node*p,node*s);//交换数据voidprint();//输出voidInsertSort();//插入排序voidBubbleSort();//pos冒泡voidQSort();//快速排序voidSelectSort();//简单选择排序node*Get(inti);//查找位置为i的结点voidsift(intk,intm);//一趟堆排序voidLinkList::QSZ(node*b,node*e);//快速排序的递归主体voidheapsort(intn);//堆排序算法};关键算法分析：1.直接插入排序：首先将待排序数据建立一个带头结点的单链表。将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程，需设一个工作指针p->next在无序区中指向待插入的结点，在找到插入位置后，将结点p->next插在结点s和p之间。voidLinkList::InsertSort()//将第一个元素定为初始有序区元素，由第二个元素开始依次比较{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->next;//要插入的节点的前驱while(p->next) {node*s=front;//充分利用带头结点的单链表while(1) { comparef++;if(p->next->data<s->next->data)//[P后继]比[S后继]小则插入 { insert(p,s);break; } s=s->next;if(s==p)//若一趟比较结束，且不需要插入 { p=p->next;break; } } } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}2.快速排序：主要通过轴值将数据从两端向中间进行比较，交换以实现排序。通过递归的调用来实现整个链表数据的排序。代码中选用了第一个元素作为轴值。一趟排序的代码：voidLinkList::QSZ(node*b,node*e){if(b->next==e||b==e)//排序完成return;node*qianqu=b;//轴点前驱node*p=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);//继续处理轴点右侧链表}整个快速排序的实现:voidLinkList::QSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*e=front;while(e->next) { e=e->next; } QSZ(front,e); QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}3.改进版的冒泡排序：通过设置pos来记录无序边界的位置以减少比较次数。将数据从前向后两两比较，遇到顺序不对是直接交换两数据的值。每交换一次movef+3；voidLinkList::BubbleSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->next;while(p->next)//排序查找无序边界 { comparef++;if(p->data>p->next->data) turn(p,p->next); p=p->next; }node*pos=p;p=front->next;while(pos!=front->next) {node*bound=pos; pos=front->next;while(p->next!=bound) { comparef++;if(p->data>p->next->data) { turn(p,p->next);pos=p->next; } p=p->next; } p=front->next; } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}4.选择排序：每趟排序再待排序的序列中选择关键码最小的元素，顺序添加至已排好的有序序列最后，知道全部记录排序完毕。voidLinkList::SelectSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*s=front;while(s->next->next) {node*p=s;node*index=p;while(p->next) { comparef++;if(p->next->data<index->next->data) index=p; p=p->next; } insert(index,s); s=s->next; } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}5.堆排序：利用前一趟比较的结果来减少比较次数，提高整体的效率。其中通过链表储存了一棵树。选择使用小根堆进行排序。voidLinkList::sift(intk,intm){inti=k,j=2*i;while(j<=m) { comparef++;if(j<m&&(Get(j)->data>Get(j+1)->data))j++;if(Get(i)->data<Get(j)->data)break;else { turn(Get(i),Get(j)); i=j; j=2*i; } }}voidLinkList::heapsort(intn){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数for(inti=n/2;i>=1;i--) sift(i,n);for(inti=1;i<n;i++) { turn(Get(1),Get(n-i+1)); sift(1,n-i); } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}其中堆排序中需要知道孩子节点和父亲节点处的值，故设置了函数获取i出的指针。node*LinkList::Get(inti){node*p=front->next;intj=1;while(j!=i&&p) { p=p->next; j++; }if(!p)throw"查找位置非法";elsereturnp;};6.输出结果的函数：voidtell(LinkList&a,LinkList&b,LinkList&c,LinkList&d,LinkList&e){a.print(); comparef=0;movef=0;a.InsertSort(); cout<<"排序结果：";a.print(); cout<<"1.插入排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;b.BubbleSort(); cout<<"2.改进型冒泡排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;c.QSort(); cout<<"3.快速排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;d.SelectSort(); cout<<"4.简单选择排序法Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;e.heapsort(10); cout<<"5.堆排序算法Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl;}7.统计时间的函数：#include<windows.h>{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->next;//要插入的节点的前驱QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;};2.3其他算法的时间复杂度：排序方法随机序列的平均情况最好情况最坏情况辅助空间直接插入排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)~O(n)改进版冒泡排序O(n2)O(n)O(n2)O(1)选择排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)3.程序运行结果1.流程图开始：开始初始化正序链表，调用初始化正序链表，调用各类排序，并输出运行结果初始化逆序链表初始化逆序链表，调用各类排序，并输出运行结果初始化顺序随机的链表，调用初始化顺序随机的链表，调用各类排序，并输出运行结果结束结束2.测试条件：如果需要对不同的正序，逆序随机序列进行排序，则需要在main函数中进行初始化设置。3.测试结论：4.总结通过这次实验我再次复习了链表的建立及相应的操作，对各类排序算法的实现也有了新的理解，在调试过程中出现了许多问题也花费了很多时间和精力去逐步解决，最后程序运行成功的瞬间真的很开心。问题一：直接插入排序中若是使用从后向前比较插入的话（即书上的办法）难以找到该节点的前驱节点，不方便进行操作，所以最后采用了从前向后进行比较。voidLinkList::InsertSort()//将第一个元素定为初始有序区元素，由第二个元素开始依次比较{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->next;//要插入的节点的前驱while(p->next) {node*s=front;//充分利用带头结点的单链表while(1) { comparef++;if(p->next->data<s->next->data)//[P后继]比[S后继]小则插入 { insert(p,s);break; } s=s->next;if(s==p)//若一趟比较结束，且不需要插入 { p=p->next;break; } } }问题二：如何将书上以数组方式储存的树转化为链表储存并进行操作？原本打算建立一颗完全二叉树储存相应数据再进行排序，但是那样的话需要新设置结点存左孩子右孩子，比较麻烦容易出错，所以选择了利用Get(inti)函数将筛选结点的位置获得。与书上代码相比修改如下：if(j<m&&(Get(j)->data>Get(j+1)->data))j++;if(Get(i)->data<Get(j)->data)break;else { turn(Get(i),Get(j)); i=j; j=2*i; }问题三：时间如何精确至微秒？需要调用函数，这个问题是上网查找解决的。总结：解决了以上的问题后代码就比较完整了，可是还是希望通过日后的学习能将算法编写得更完善，灵活，简捷。附录：完整代码如下：#include"lianbiaopaixu.h"#include<windows.h>usingnamespacestd;voidmain(){inta[10]={1,2,3,4,5,6,7,8,9,10};LinkListzhengxu1(a,10),zhengxu2(a,10),zhengxu3(a,10),zhengxu4(a,10),zhengxu5(a,10); cout<<"正序数列："; tell(zhengxu1,zhengxu2,zhengxu3,zhengxu4,zhengxu5);intb[10]={10,9,8,7,6,5,4,3,2,1};LinkListnixu1(b,10),nixu2(b,10),nixu3(b,10),nixu4(b,10),nixu5(b,10); cout<<"\n逆序数列："; tell(nixu1,nixu2,nixu3,nixu4,nixu5);intc[10]={2,6,10,5,8,3,9,1,4,7};LinkListsuiji1(c,10),suiji2(c,10),suiji3(c,10),suiji4(c,10),suiji5(c,10); cout<<"\n随机数列："; tell(suiji1,suiji2,suiji3,suiji4,suiji5);}#include<iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>#include<iomanip>#include<windows.h>usingnamespacestd;intcomparef;intmovef;structnode{intdata;node*next;};classLinkList{private:node*front;public: LinkList(inta[],intn);//构造 ~LinkList();voidinsert(node*p,node*s);//插入voidturn(node*p,node*s);//交换数据voidprint();//输出voidInsertSort();//插入排序voidBubbleSort();//pos冒泡voidQSort();//快速排序voidSelectSort();//简单选择排序node*Get(inti);//查找位置为i的结点voidsift(intk,intm);//一趟堆排序voidLinkList::QSZ(node*b,node*e);//快速排序的递归主体voidheapsort(intn);//堆排序算法};LinkList::LinkList(inta[],intn){ front=newnode; front->next=NULL;for(inti=n-1;i>=0;i--) {node*p=newnode;//新节点 p->data=a[i]; p->next=front->next; front->next=p;//头插法建立单链表，最先加入的被不断后移 }}LinkList::~LinkList(){node*q=front;while(q) { front=q; q=q->next;deletefront; }}voidLinkList::insert(node*p,node*s)//将p->next插入s和s->next之间{node*q=p->next;p->next=p->next->next; q->next=s->next;s->next=q; movef++;}voidLinkList::turn(node*p,node*s)//交换数据{inttemp=p->data;p->data=s->data;s->data=temp; movef+=3;}voidLinkList::print()//输出需要显示的内容{node*p=front->next;while(p) { cout<<p->data<<''; p=p->next; } cout<<endl;}voidLinkList::InsertSort()//将第一个元素定为初始有序区元素，由第二个元素开始依次比较{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->next;//要插入的节点的前驱while(p->next) {node*s=front;//充分利用带头结点的单链表while(1) { comparef++;if(p->next->data<s->next->data)//[P后继]比[S后继]小则插入 { insert(p,s);break; } s=s->next;if(s==p)//若一趟比较结束，且不需要插入 { p=p->next;break; } } } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}voidLinkList::QSZ(node*b,node*e){if(b->next==e||b==e)//排序完成return;node*qianqu=b;//轴点前驱node*p=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);//继续处理轴点右侧链表}voidLinkList::QSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*e=front;while(e->next) { e=e->next; } QSZ(front,e); QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}voidLinkList::BubbleSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->next;while(p->next)//排序查找无序边界 { comparef++;if(p->data>p->next->data) turn(p,p->next); p=p->next; }node*pos=p;p=front->next;while(pos!=front->next) {node*bound=pos; pos=front->next;while(p->next!=bound) { comparef++;if(p->data>p->next->data) { turn(p,p->next);pos=p->next; } p=p->next; } p=front->next; } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}voidLinkList::SelectSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*s=front;while(s->next->next) {node*p=s;node*index=p;while(p->next) { comparef++;if(p->next->data<index->next->data) index=p; p=p->next; } insert(index,s); s=s->next; } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}node*LinkList::Get(inti){node*p=front->next;intj=1;while(j!=i&&p) { p=p->next; j++; }if(!p)throw"查找位置非法";elsereturnp;}voidLinkList::sift(intk,intm){inti=k,j=2*i;while(j<=m) { comparef++;if(j<m&&(Get(j)->data>Get(j+1)->data))j++;if(Get(i)->data<Get(j)->data)break;else { turn(Get(i),Get(j)); i=j; j=2*i; } }}voidLinkList::heapsort(intn){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数for(inti=n/2;i>=1;i--) sift(i,n);for(inti=1;i<n;i++) { turn(Get(1),Get(n-i+1)); sift(1,n-i); } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}voidtell(LinkList&a,LinkList&b,LinkList&c,LinkList&d,LinkList&e){a.print(); comparef=0;movef=0;a.InsertSort(); cout<<"排序结果：";a.print(); cout<<"1.插入排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;b.BubbleSort(); cout<<"2.改进型冒泡排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;c.QSort(); cout<<"3.快速排序法：Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;d.SelectSort(); cout<<"4.简单选择排序法Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl; comparef=0;movef=0;e.heapsort(10); cout<<"5.堆排序算法Compare："<<setw(3)<<comparef<<";Move："<<setw(3)<<movef<<endl;}数据结构实验报告-顺序表的创建、遍历及有序合并操作二、实验内容与步骤实现顺序表的创建、遍历及有序合并操作，基本数据结构定义如下：typedefintElemType;#defineMAXSIZE100#defineFALSE0#defineTRUE1typedefstruct{ElemTypedata[MAXSIZE];intlength;}seqlist;创建顺序表，遍历顺序表#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100#defineIcreament20#defineFALSE0#defineTRUE1typedefintElemType;//用户自定义数据元素类型//顺序表结构体的定义typedefstruct{ElemType*elem;//顺序表的基地址intlength;//顺序表的当前长度intlistsize;//预设空间容量}SqList;//线性表的顺序存储结构SqList*InitList()//创建空的顺序表{SqList*L=(SqList*)malloc(sizeof(SqList));//定义顺序表Lif(!L){printf("空间划分失败，程序退出\n");returnNULL;}L->elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));if(!L->elem){printf("空间划分失败，程序退出\n");returnNULL;}L->length=0;L->listsize=MAXSIZE;returnL;}intCreateList(SqList*L)//创建顺序表（非空）{intnumber;//顺序表中元素的个数inti;//循环变量printf("请输入顺序表中元素的个数：");scanf("%d",&number);if(number>MAXSIZE)//一定要判断输入的个数是否大于顺序表的最大长度{printf("输入个数大于顺序表的长度\n");return0;}for(i=0;i<number;i++){printf("输入第%d个数:",i+1);scanf("%d",L->elem+i);//L->elem+i：每次的输入都保存在顺序表元素中的下一个地址，而不是一直放在元素的首地址}//给顺序表中每个数据元素赋值L->length=number;//当前顺序表的长度return1;}voidprint(SqList*L)//遍历顺序表{inti; printf("\n开始遍历顺序表\n");