实验四邵彬彬.doc

《实验四邵彬彬.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》实验四排序学号：姓名：邵彬彬专业：10级计科2班指导教师：郭世懿实验四排序一、实验目的1．掌握插入排序（直接插入排序、Shell排序）算法的实现方法。2．掌握交换排序（冒泡排序、快速排序）算法的实现方法。3．掌握选择排序（简单的选择排序、堆排序）算法的实现方法。4．掌握二路归并排序算法的实现方法。5．通过排序算法在实际应用中的运用，增强程序设计能力。二、实验要求1．实验前做好充分准备，包括复习所学内容，事先预习好本次实验内容。2．实验时记录实验结果，按要求完成各个设计题目。3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。三、实验题目本次实验给出的选定题目如下

2、表所示。实验名称学时实验内容实验要求实验类型排序2（1）直接插入排序算法、Shell排序算法必做设计性（2）冒泡排序、快速排序算法必做设计性（3）简单选择排序算法、堆排序算法选做设计性（4）班级学生成绩管理（利用某种排序方法实现按某个或某些关键字排序）选做综合性四、实验内容与要求1、实验题目一：直接插入排序算法、SHELL排序算法要求：利用顺序表作为排序表，分别利用直接插入排序及Shell排序方法对其进行排序。2、实验题目二：冒泡排序、快速排序算法要求：利用顺序表作为排序表，分别利用冒泡排序与快速排序方法对其进行排序并加以验证。3、实验题目三：简单选择排序算法、堆排序算法要求：利用顺序

3、表作为排序表，分别利用简单选择排序与堆排序方法对其进行排序并加以验证。4、实验题目四：班级学生成绩管理要求：设计一个班级学生绩管理系统，能够存储全班同学的学号、姓名、各科考试成绩等信息，并能够实现相关查询（按姓名和学号）和排序（按总成绩）操作。五、实验内容：本程序包含了9个函数，它们分别是：（1）、直接插入排序的算法函数InsertSort（）。（2）、希尔排序的算法函数ShellSort（）。（3）、冒泡排序算法函数BubbleSort（）。（4）、快速排序的算法函数Partition（）。（5）、选择排序算法函数SelectSort（）。（6）、堆排序算法函数HeapAdjust（

4、）。（7）、对存储数字的遍历函数Visit（）。（8）、初始化函数InitSqList（）。（9）、主函数main（）。具体设计：一、直接插入排序voidInsertSort(SqList&L){inti,j;for(i=2;i<=L.length;i++){if(L.r[i].key

5、j;intdk=1;//增量while(dk<=L.length/3)dk=3*dk+1;//增大增量while(dk>0){dk/=3;//减小增量for(i=dk;i<=L.length;i++){L.r[0].key=L.r[i].key;j=i;while((j>=dk)&&(L.r[j-dk].key>L.r[0].key)){L.r[j].key=L.r[j-dk].key;j-=dk;}L.r[j].key=L.r[0].key;}}}三、冒泡排序voidBubbleSort(SqList&L){inti,j;for(i=0;i

6、ag=1;for(j=0;jL.r[j+1].key){flag=0;inttemp;temp=L.r[j].key;L.r[j].key=L.r[j+1].key;L.r[j+1].key=temp;}//若无交换说明已经有序if(flag==1)break;}}四、快速排序intPartition(SqList&L,intlow,inthigh){//分割区域函数L.r[0]=L.r[low];intpivotkey=L.r[low].key;//一般将顺序表第一个元素作为支点while(low

7、(low=pivotkey)high--;L.r[low]=L.r[high];while(low