查找和排序的应用

[问题描述]

　学生信息管理系统

[基本要求]

设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：

1.试选择一种方式存储：基于数组、链表或文件方式

2．总成绩要求自动计算；

3．查询：分别给定学生学号、姓名，能够查找到学生的基本信息（要求至少用两种查找算法实现）；

排序：分别按学生的学号、总成绩进行排序（要求至少用两种排序算法实现）。

#include<cstdio>
#include<iostream>
#define OVERFLOW -2
#include<cstring>
using namespace std;

const int MaxSize=20;

typedef struct {
	//char num[20];
	double num; 
	char name[20];
	char sex[10];
	double score[5];
	double tolscore; //自动计算 
}Student; 

//存储学生信息的顺序表的定义：
typedef struct{
  Student stu[MaxSize];  
  int length;
}SequenList;

SequenList L;

/**初始化一个空表*/ 
void InitList(){
	if(!L.stu) exit(OVERFLOW);
	L.length=0;//空表长度为0 
}

/**交换两个学生的信息*/
void Swap(int i,int j){
	double num; 
	char name[20];
	char sex[10];
	double score[5];
	double tolscore; 
  	//交换学号,姓名,性别,成绩,总成绩 
	strcpy(name,L.stu[i].name);strcpy(L.stu[i].name,L.stu[j].name);strcpy(L.stu[j].name,name);
	strcpy(sex,L.stu[i].sex);strcpy(L.stu[i].sex,L.stu[j].sex);strcpy(L.stu[j].sex,sex);
	num=L.stu[i].num;L.stu[i].num=L.stu[j].num;L.stu[j].num=num;
	score[0]=L.stu[i].score[0];L.stu[i].score[0]=L.stu[j].score[0];L.stu[j].score[0]=score[0];
	score[1]=L.stu[i].score[1];L.stu[i].score[1]=L.stu[j].score[1];L.stu[j].score[1]=score[1];
	tolscore=L.stu[i].tolscore;L.stu[i].tolscore=L.stu[j].tolscore;L.stu[j].tolscore=tolscore;
}

/**打印学生信息*/ 
void PrintStuMes(){
	printf(\"--------------------------------------------------------------------------------------\\n\");
	printf(\"学号\\t\\t  姓名\\t\\t性别\\t   英语\\t      C语言\\t   总成绩\\n\");
	for(int i=1;i<=L.length;i++){
		printf(\"%.0lf\\t  %s\\t %s\\t   %.2lf      %.2lf\\t   %.2lf\\n\",L.stu[i].num,
		L.stu[i].name,L.stu[i].sex,L.stu[i].score[0],L.stu[i].score[1],L.stu[i].tolscore);
	}
	printf(\"--------------------------------------------------------------------------------------\\n\");
}

/**从文件中读取学生信息并输出*/
void ReadStuMes(){
	//char num[20];
	double num; 
	char name[10];
	char sex[5];
	double score[2];  
	FILE *fp;
	if((fp=fopen(\"C:\\\\Users\\\\xiaowei\\\\Desktop\\\\in1.txt\",\"r\"))==NULL){
		printf(\"文件读取发生错误,无法进行读入!\");
		exit(0);
	}
	while(!feof(fp)){
		fscanf(fp,\"%lf%s%s%lf%lf\",&num,name,sex,&score[0],&score[1]); 
		L.length++;//0号单元不使用 
		//strcpy(L.stu[L.length].num,num);
		L.stu[L.length].num=num; 
		strcpy(L.stu[L.length].name,name);strcpy(L.stu[L.length].sex,sex);
		L.stu[L.length].score[0]=score[0],L.stu[L.length].score[1]=score[1];
		L.stu[L.length].tolscore=L.stu[L.length].score[0]+L.stu[L.length].score[1];
		if(L.length==MaxSize)
			break;
	}
	printf(\"从数据文件中读取的学生信息为:\\n\"); 
	PrintStuMes(); 
	printf(\">>任意键进入主界面\");
	system(\"pause\");
	system(\"cls\");
} 

/**按照学号排序(冒泡排序)*/
void BubbleSort(){
	for(int i=1;i<=L.length-1;i++){
		for(int j=1;j<=L.length-i;j++)
			if(L.stu[j].num>L.stu[j+1].num)
				Swap(j,j+1);
	}
}

/**按照学生学号查找某位同学的基本信息(先排序在二分)*/
void BinarySearch(){
	BubbleSort();
	printf(\"请输入您要查找的学生的学号:\");
	double num;
	scanf(\"%lf\",&num);
	int index=-1;
	int left=1,right=L.length;
	while(left<=right){
		int mid=left+(right-left)/2;
		if(L.stu[mid].num==num){
			index=mid;
			break;
		}
			
		else if(num<L.stu[mid].num)
			right=mid-1;
		else
			left=mid+1;
	}
	if(index==-1){
		printf(\"您查找的学生不存在,请重新输入!\\n\");
		BinarySearch();
	} 
	else{
		printf(\"---------------------------------------------------------------------------------------------------------\\n\");
		printf(\"学号:%.0lf\\t姓名:%s\\t性别:%s\\t\\t英语:%.2lf\\tC语言:%.2lf\\t总成绩:%.2lf\\n\",
		L.stu[index].num,L.stu[index].name,L.stu[index].sex,L.stu[index].score[0],
		L.stu[index].score[1],L.stu[index].tolscore);	
		printf(\"---------------------------------------------------------------------------------------------------------\\n\");
		printf(\">>Enter键返回主界面\\n\");
		system(\"pause\");
		system(\"cls\"); 	
	}
	
} 

/**按照学生姓名查询学生的基本信息(顺序查找)*/ 
void Search_seq(){
	printf(\"请输入您要查询的学生的姓名:\");
	char name[20];
	scanf(\"%s\",name);
	int index=-1;
	for(int i=1;i<=L.length;i++){
		if(strcmp(name,L.stu[i].name)==0)
			index=i;
	}
	if(index==-1){
		printf(\"您查找的学生不存在,请重新输入!\\n\");
		Search_seq();  
	} 
	else{
		printf(\"---------------------------------------------------------------------------------------------------------\\n\");
		printf(\"学号:%.0lf\\t姓名:%s\\t性别:%s\\t\\t英语:%.2lf\\tC语言:%.2lf\\t总成绩:%.2lf\\n\",
		L.stu[index].num,L.stu[index].name,L.stu[index].sex,L.stu[index].score[0],
		L.stu[index].score[1],L.stu[index].tolscore);	
		printf(\"---------------------------------------------------------------------------------------------------------\\n\");
		printf(\">>Enter键返回主界面\\n\");
		system(\"pause\");
		system(\"cls\");	
	}
}

/**进行一次排序,返回枢轴位置*/
int Partition(int left,int right){//对顺序表进行一次排序,返回枢轴位置
	L.stu[0]=L.stu[left];//将枢轴信息放在0号位置
	int pivotkey=L.stu[left].tolscore;//记录枢轴的总成绩 
	while(left<right){
		while(left<right&&L.stu[right].tolscore>=pivotkey) right--;//右移,直到小于枢轴的销售量
		L.stu[left]=L.stu[right];//覆盖
		while(left<right&&L.stu[left].tolscore<=pivotkey) left++;//左移,直到大于枢轴的销售量
		L.stu[right]=L.stu[left];//覆盖
	}
	L.stu[left]=L.stu[0];
	return left;
}

/**对顺序表进行排序*/
void QSort(int left,int right){
	if(left<right){//长度大于1
		int pivotloc=Partition(left,right);//记录返回的枢轴的位置
		QSort(left,pivotloc-1); //左子表排序
		QSort(pivotloc+1,right);//右子表排序
	}
}

/**按照总成绩排序(快速排序)*/
void QuickSort(){//对L进行快速排序
	QSort(1,L.length);
	printf(\"按照总成绩排序(快速排序)后的结果为:\\n\");
	PrintStuMes();
	printf(\">>Enter键返回主界面\");
	system(\"pause\");
	system(\"cls\");
}
/**主界面*/
void Menu(){
	printf(\"-----------------欢迎进入学生管理系统-----------------\\n\"); 
	printf(\"1.打印全部学生的基本信息\\n\");
	printf(\"2.按照学生学号查询学生的基本信息(折半查找)\\n\");
	printf(\"3.按照学生姓名查询学生的基本信息(顺序查找)\\n\");
	printf(\"4.按照学生学号排序(冒泡排序)\\n\");
	printf(\"5.按照学生总成绩排序(快速排序)\\n\");
	printf(\"6.退出\\n\");
	printf(\"------------------------------------------------------\\n\"); 
	printf(\">>请输入您的选择:\");
	int chose;
	scanf(\"%d\",&chose);
	switch(chose){
		case 1:{
			PrintStuMes();
			printf(\">>Enter键返回主界面\\n\");
			system(\"pause\");
			system(\"cls\");
			Menu();
		}
		case 2: {
			BinarySearch(); 
			Menu();
		}
		case 3: {
			Search_seq();
			Menu();
		}
		case 4: {
			BubbleSort(); 
			printf(\"按照学生学号排序(冒泡排序)后的学生信息为:\\n\");
			PrintStuMes();
			printf(\">>Enter键返回主界面\");
			system(\"pause\");
			system(\"cls\");
			Menu(); 
		}
		case 5: {
			QuickSort();
			Menu();
		}
		case 6: {
			printf(\"您输入的信息有误,请重新输入!\");
			printf(\">>Enter键返回主界面\\n\");
			system(\"pause\");
			system(\"cls\"); 
			Menu(); 
		}
	} 
} 
int main(){
	InitList(); 
	ReadStuMes(); //从文件读入学生信息 
	Menu();
	return 0;
}