数据结构课程设计

//实习 6  查找和排序
//6．2-路归并排序
//问题描述
//某学校一个年级有M个班的学生参加某门课程的考试，每个班最多有N个学生，
//利用2-路归并排序的思想求全体考生的排名表。
//要求
//（1）	每个班的学生都是按学号顺序输入数据的，每个学生记录至少包含排列名次、学号、姓名、成绩四个域；
//（2）	输出每个学生在本年级的排名情况，具有相同成绩的名次相同；
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>


int M ;
int N ;
typedef struct{
	int order;//名次
	int no;//学号
	int score;//成绩
}rectype;
rectype students[500][500];
void gen_recs(){//学生信息
	int i,j;
	for(i=0;i<M;i++){
		printf("%d班学生\n",i+1);
		printf("请依次输入%d班学生的学号和成绩：\n",i+1);
		for(j=1;j<=N;j++){
			scanf("%4d",&students[i][j].no);
			scanf("%4d",&students[i][j].score);
		}
	}
}
void sort_one_class(rectype r[],int n){
	int i,j;
	for(i=2;i<=n;i++){
		r[0]=r[i];
		j=i-1;
		while(r[0].score>r[j].score){
			r[j+1]=r[j];
			j--;
		}
		r[j+1]=r[0];
	}
}
void merge(rectype sr[],rectype dr[],int low,int mid,int high){
	int i,j,k;
	i=low;
	j=mid+1;
	k=low;
	while((i<=mid)&&(j<=high)){
		if(sr[i].score<=sr[j].score)
			dr[k++]=sr[j++];
	}
	while(i<=mid)
		dr[k++]=sr[i++];
	while(j<=high)
		dr[k++]=sr[j++];
}
void mergeonepass(rectype sr[],rectype dr[],int d,int n){
	int i;
	i=1;
	while(i+2*d-1<n){
		merge(sr,dr,i,i+d-1,i+2*d-1);
		i=i+2*d;
	}
	if(i+d-1<n)
		merge(sr,dr,i,i+d-1,n);
	else
		merge(sr,dr,i,n,n);
}
void sort_all(rectype sr[],rectype dr[],int n){
	int d;
	d=N;
	while(d<n){
		mergeonepass(sr,dr,d,n);
		mergeonepass(dr,sr,2*d,n);
		d=4*d;
	}
}
void order_no(rectype r[],int n){
	int i;
	r[1].order=1;
	for(i=2;i<=n;i++)
		if(r[i].score==r[i-1].score)
			r[i].order=r[i-1].order;
		else
			r[i].order=i;
}
void print_list(rectype r[],int n){
	int i;
	printf("*  名次    学号    成绩  *\n");
	for(i=1;i<=n;i++){
		printf("*  %4d  %4d  %4d  *\n",r[i].order,r[i].no,r[i].score);
	}
}
void main(){
	rectype r1[12500],r2[12500];
	int i,j,k;
	//int m,n;
	printf("请输入班级数和每班人数：\n");
	scanf("%d,%d",&M,&N);
	gen_recs();
	for(i=0;i<=M;i++){
		sort_one_class(students[i],N);
		order_no(students[i],N);
	}
	k=1;
	for(i=0;i<M;i++)
		for(j=1;j<=N;j++)
			r1[k++]=students[i][j];
	sort_all(r1,r2,M*N);
	order_no(r1,M*N);
	printf("\n  全体学生成绩排名：\n");
	print_list(r1,M*N);
}