数据结构实验课:实验八、排序算法的实现 |
您所在的位置:网站首页 › c语言对数据进行排序 › 数据结构实验课:实验八、排序算法的实现 |
实验八、排序算法的实现
一、实验目的 掌握常用的排序方法,并掌握用高级语言实现排序算法的方法;深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用;了解各种方法的排序过程及其时间复杂度的分析方法。 二、实验要求 统计成绩:给出n个学生的考试成绩表,每条信息由姓名和分数组成,试设计一个算法: (1) 按分数高低次序,打印出每个学生在考试中获得的名次,分数相同的为同一名次; (2) 按名次列出每个学生的姓名与分数。 三、实验步骤 1.定义结构体。 Typedef struct student { char name[8]; int score; } 2.定义结构体数组。 3.编写主程序,对数据进行排序。 4.要求至少采用两种排序算法实现,如直接插入排序、快速排序等算法。 4.1直接插入排序基本思想 排序过程:整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序。4.2 快速排序基本思想 基本思想:通过一趟排序,将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录进行排序,以达到整个序列有序。 排序过程:对r[s……t]中记录进行一趟快速排序,附设两个指针i和j,设rp=r[s],x=rp.key。初始时令i=s,j=t。首先从j所指位置向前搜索第一个关键字小于x的记录,并和rp交换。再从i所指位置起向后搜索,找到第一个关键字大于x的记录,和rp交换。重复上述两步,直至i=j为止。再分别对两个子序列进行快速排序,直到每个子序列只含有一个记录为止。 四、实验任务 认真阅读与理解实验内容的具体要求,参考教材相关章节,编写实验程序并上机调试与测试,完成实验报告的撰写。 代码如下 #include #include typedef struct { char name[10]; int score; } student; //========================================= void InsertSort(student a[],int n)//冒泡排序算法 { int i,j,flag; student temp; for(i=0; i if(a[j].score int i,j,k; student temp; for(i=0; i if(a[j].score>a[k].score) k=j; } if(k!=i) { temp=a[i]; a[i]=a[k]; a[k]=temp; } } } int main() { int n,i,k,t; student *a; printf("您要输入多少个学生的信息?\n"); scanf("%d",&n); a=(student *)malloc(n*sizeof(student)); printf("请输入学生姓名和成绩:\n"); for(i=0; i InsertSort(a,n); } else if(k==2) { SelectionSort(a,n); } printf("第%d名: %s %d\n",1,a[0].name,a[0].score); t=1; for(i=1; i printf("第%d名: %s %d\n",t,a[i].name,a[i].score); } else { t=i+1; printf("第%d名: %s %d\n",t,a[i].name,a[i].score); } } free(a); return 0; } |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |