实训八排序_实验八排序

2020-02-27 其他范文下载本文

实训八排序由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“实验八排序”。

数据结构实训教案

实训八

吉首大学物理信息学院

周小清

实训八

排序

一、实训目的1、掌握简单插入排序、快速排序、堆排序的算法并加以应用

2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；

3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。

二、实训重点：简单插入排序

三、实训难点：堆排序

四、实训内容：

实现下述三种算法，并用以下无序序列加以验证： 49，38，65，97，76，13，27，49

一、简单插入排序

二、快速排序

三、堆排序

例程1

一、简单插入排序,二、快速排序,三、堆排序 */

#define MAXSIZE 20 #define LT(a,b)((a)

数据结构实训教案

实训八

吉首大学物理信息学院

周小清

RedType r[MAXSIZE+1];int length;}SqList;

void InsertSort(SqList *L){ int i,j;for(i=2;ilength;++i)if(LT(L->r[i].key,L->r[i-1].key)){ L->r[0]=L->r[i];for(j=i-1;LT(L->r[0].key,L->r[j].key);--j)L->r[j+1]=L->r[j];L->r[j+1]=L->r[0];} }

void BInsertSort(SqList *L){ int i,j;int low,high,m;for(i=2;ilength;++i){ L->r[0]=L->r[i];low=1;high=i-1;while(lowr[0].key,L->r[m].key))high=m-1;else low=m+1;} for(j=i-1;j>=high+1;--j)L->r[j+1]=L->r[j];L->r[high+1]=L->r[0];} }

/* QuickSort related function */ int Partition(SqList *L,int low,int high){ int pivotkey;L->r[0]=L->r[low];pivotkey=L->r[low].key;while(lowr[high].key>=pivotkey)--high;L->r[low]=L->r[high];数据结构实训教案

实训八

吉首大学物理信息学院

周小清

while(lowr[low].keyr[high]=L->r[low];} L->r[low]=L->r[0];return low;} void QSort(SqList *L,int low,int high){ int pivotloc;if(lowlength);} /* End QuickSort related function*/

/*SelectSort related function */ int SelectMinKey(SqList L,int i){ int k;int j;k=i;for(j=i;jL.r[j].key)k=j;return k;} void SelectSort(SqList *L){ RedType t;int i,j;for(i=1;ilength;++i){ j=SelectMinKey(*L,i);if(i!=j){ t=L->r[i];L->r[i]=L->r[j];L->r[j]=t;} } } /*End SelectSort related function */ 数据结构实训教案

实训八

吉首大学物理信息学院

周小清

typedef SqList HeapType;void HeapAdjust(HeapType *H,int s,int m){ RedType rc;int j;rc=H->r[s];for(j=2*s;jr[j].key,H->r[j+1].key))++j;if(!LT(rc.key,H->r[j].key))break;H->r[s]=H->r[j];s=j;} H->r[s]=rc;} void HeapSort(HeapType *H){ RedType t;int i;for(i=H->length/2;i>0;--i)HeapAdjust(H,i,H->length);for(i=H->length;i>1;--i){ t=H->r[1];H->r[1]=H->r[i];H->r[i]=t;HeapAdjust(H,1,i-1);} }

main(){ int a[]={49,38,65,97,76,13,27,49};int i,k;SqList s;printf(“nThe record to be sort:n”);for(i=1;i

实训八

吉首大学物理信息学院

周小清

printf(“nt1,InsertSortnt2,BInsertSortnt3,QuickSortnt4,SelectSortn”);printf(“t5,HeapSortntPre 1..5 to select a functionn”);scanf(“%d”,&k);switch(k){ case 1: InsertSort(&s);break;case 2: BInsertSort(&s);break;case 3: QuickSort(&s);break;case 4: SelectSort(&s);break;case 5: HeapSort(&s);break;default:printf(“No function which you select.n”);} printf(“nThe records be sorted:n”);for(i=1;i

例程2：

统计成绩

[问题描述]给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：

（1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；

（2）按名次列出每个学生的姓名与分数。

[基本要求]学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出数据结构实训教案

实训八

吉首大学物理信息学院

周小清

进行格式控制。

[算法实现]下面给出的是用直接选择排序算法实现的C语言程序。

#define n 30 typedef struct student { char name[8];