数据结构课程设计

福 建 工 程 学 院

课程设计

课 程： 数据结构课程设计 题 目： 1.综合应用 2.折半查找

3.快速排序

专 业： 软件工程 班 级： 1101 座 号： 3110305129 姓 名： 潘聪

2012 年 6 月 26 日

设计题目1：综合应用

一、问题描述

有N名学生，每名学生含有如下信息：学号、姓名、某四门课的成绩，并计算其总分，用一结构数组表示之。然后实现以下功能： （1） 将这些数据存放至文件stuf.dat中；

（2）将文件中的数据读出至结构数组中，并显示之； （3）输出总分最高分和最低分的名字；

（4）输出总分在340分，单科成绩不低于80分的名单； （5）求出各科平均分数； （6）按总分排名； （7）输出补考名单。

二、解决问题的算法思想描述

（1）子函数：首先确定需要的子函数，总共7个，对应的功能分别是题目要求的七项 （2）主函数：主函数中，要设计出易于使用的人机界面，就必须要用到 switch 。 （3）文件的存放读取，必须要用到文件的函数，fopen，fread，fclose等。 （4）把每个学生的信息定义在一个结构数组中，利用结构数组更加方便。 （5）各科成绩排名用冒泡排序即可。

（6）输出总分，补考名单，各科的平均分都比较简单。

三、设计

1. 数据结构的设计和说明

//定义结构体 typedef struct {

int num; //学号 char name[10]; //姓名 int score1; //语文 int score2; //数学 int score3; //物理 int score4; //化学 }student;

student stu[MAX]; //结构数组

2．模块结构图及各模块的功能：

学生成绩管理系统 将这将文输出些数件中总分据存的数最高放至据读分和文件出至最低stuf.da结构分的t中； 数组名字； 中；

3. 关键算法的设计（必须画出流程图）总分在340分，单科成绩不低于80分的； 求出各科平均分数； 按总分排名； 输出补考名单

开始 定义 整型 i，字符p 输入 i 判断 i 0 将这些数据存放至文件stuf.dat中； 1 将文件中的数据读出至结构数组中； 2 输出总分最高分和最低分的名字； 3 总分在340分，单科成绩不低于80分的； 4求出各科平均分数； 5 按总分排名； 6 输出补考名单； 7 退出； 输入 p 判断 p Y N 结束

按总分排名算法流程：图： 开始 读取文件 定义变量sum[4],i,j,m,n 求出四门总分sum[4] i++; isum[m]； Y N n++; m++; Y sum[n]与sum[m]交换； stu[n]与stu[m]交换； m

打印最高成绩和最低成绩的名单算法流程图：

开始

定义变量

sum[MAX]

求出各人分数总和

并保存到数组

sum[]中

min=max=sum[0];

sum[i]>=max sum[i]<=min

Y Y N

max与sum[i]交换 min与sum[i]交换

传递下表给传递下表给

stu[MAX]; stu[MAX];

i

输出

结束 i++

四、测试数据及测试结果：

五、课程设计总结

注意细节方面，任何一个小问题都不能忽视，才能最终解决问题。

六、关键源程序的清单

关键算法一：

按照总成绩排名：

void paiming() {

read(); student x;

int sum[MAX],t=0,i,m,n,j; for(i=0;i

sum[i]=stu[i].score1+stu[i].score2+stu[i].score3+stu[i].score4; }

for(m=0;m

if(sum[n]>sum[m]) { t=sum[n];

sum[n]=sum[m]; //总成绩交换 sum[m]=t; x=stu[n];

stu[n]=stu[m]; //总成绩对应的学生也要同时交换 stu[m]=x; }

printf(\学号\\t姓名\\t语文\\t数学\\t英语\\t物理\\t总分\\t名次\\n\ for(j=0;j

printf(\ore2,stu[j].score3,stu[j].score4,sum[j],j+1); } }

关键算法二：

打印出最高成绩和最低成绩的姓名： void maxmin() {

int sum[MAX],i,j,m=0,n=0,max,min; read();

for(i=0;i

sum[i]=stu[i].score1+stu[i].score2+stu[i].score3+stu[i].score4;

} //求书每个人的总分

max=min=sum[0]; //用一维数组保存成绩，并且先令第一位学生的成绩作为最高分和最低分

for(j=0;j

if(sum[j]>max) {

m=j;

max=sum[j]; //定义变量m，n分别保存最高分和最低分的下标 }

else if(sum[j]

n=j;

min=sum[j]; }

}

printf(\最高分： %s 总分%d\\n\ printf(\最低分： %s 总分%d\\n\\n\}

设计题目2：折半查找

一、问题描述

用折半查找法，实现对任意一组数据的查找。（任意一组数据，意味着需要先对数据列

进行排序，然后才能用折半方法查找）

二、解决问题的算法思想描述

任意一组数据，意味着需要先对数据列进行排序，然后才能用折半方法查找，所以先用快速排序将数据从小到大排序，在运用折半查找方法。

三、设计

1. 数据结构的设计和说明

（1）快速排序； （2）折半查找；

在有序表中，取中间元素作为比较的对象，若给定值与中间元素的关键码相等，则查找成功；若给定值小于中间元素的关键码，则在中间元素的左半区急速查找；若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复，直到查找成功。

2. 关键算法的设计（必须画出流程图）

快速排序的流程图： 开始 high,low,r[n]; 定义 high=n,low=0; N high>low high=low Y Y return low; low=high t=low; t++; r[t]>r[high] N Y r[low]与r[high]交换 low++;

N return 0; m=high; r[m]

折半查找流程图： 开始 输入要查找的数kx; int low,high,r[n]; low=1,high=n; mid=(high+low)/2 low

Y kx>r[mid] Y low=mid+1; N high=mid-1;

四、测试数据及测试结果：

五、课程设计总结

折半查找必须要先排序。

六、关键源程序的清单

int binsearch(Sq_Table st,KeyType kx) { int mid,low=1,high=st.length; while(low<=high) { mid=(low+high)/2; if(kx==st.r[mid].key) return mid; if(kx>st.r[mid].key) low=mid+1; else high=mid-1; } return 0; }

设计题目3：快速排序

一、问题描述

实现对任意一组数据的快速排序。

二、解决问题的算法思想描述

运用快速排序的算法就可解决问题。

三、设计

1. 数据结构的设计和说明

快速排序：快速排序是交换排序的一种，实际上是冒泡排序的一种改进。快速排序的基本思想是：以某个记录（一般去第一个记录）为标准，也就是支点，通过划分，将待排序序列分成两组，其中一组中所有记录的关键码均大于等于记录的关键码，另一组中的左右记录的关键码均小于支点记录的关键码。

2. 关键算法的设计（必须画出流程图）

快速排序流程图见上面一题。

四、测试数据及测试结果：

六、关键源程序的清单

int Partition(RecNode r[],int low,int high)

/*r[low..high]存放待排记录，算法返回支点最终位置*/ {

if(low>high) return 0; if(low==high) return low;

r[0]=r[low]; /*缓存支点记录*/ while(low=r[0].key) high--; //查看high记录 if(low

r[low]=r[0]; /*支点记录最终位置*/ return low; }

void Quick_sort(RecNode r[], int m, int n) /*对顺序表r[m..n]作快速排序，m初值为1*/ { int i;

i= Partition(r,m,n); if(m

Quick_sort(r,m,i-1); if(i

Quick_sort(r,i+1,n); }

本文来源：https://www.bwwdw.com/article/l74a.html