piont3.c

排序及应用 题目一：统计成绩 1． 实验目的：掌握常用的排序方法

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<dos.h>
#include<math.h>

//------------------------------动态存储结构----------------------
#define OK			1
#define ERROR		0
#define RADIX		10

typedef int			elemtype;
typedef struct Person{
	elemtype		Chineae;
	elemtype		English;
	elemtype		Maths;
	char			name[15];
	elemtype		Rank;
	struct Person	*next;
}Person;
typedef struct {
	Person			*p;
	int				count;
	int				KeyNum;
}Class;

//-----------------------------清屏函数----------------------------
void clean(){
system("cls");
}
//=============================链表的基本操作======================
//-----------------------------创建链表----------------------------
void CreateList(Class *c){                                          //头结点为空
Person *p,*temp;

temp=c->p;
while(1){
p=(Person *)malloc(sizeof(Person));
printf("请输入学生姓名 语言 英文 数学的成绩:(0 0 0 0为结束)\n");
scanf("%s%d %d %d",p->name,&p->Chineae,&p->English,&p->Maths);
getchar();
if(p->name[0]=='0') return;
else {
	temp->next=p;
	p->next=NULL;
	temp=p;
	c->count++;
//	printf("%s\t%d\n",c->p->next->name,c->p->next->num);
	}
}//while
free(p);

}
//-----------------------------增加元素----------------------------
void ListInsert(Class *c){
Person *temp,*p;

temp=c->p;
p=(Person *)malloc(sizeof(Person));
while(temp->next!=NULL) 
	temp=temp->next;                               //查找最尾元素
printf("输入要插入的姓名 语言 英文 数学的成绩:\n");
scanf("%s%d %d %d",p->name,&p->Chineae,&p->English,&p->Maths);
if(p->name[0]=='0') return;
else {
	temp->next=p;
	p->next=NULL;
	c->count++;
	}
}
//-----------------------------删除元素----------------------------
void ListDelete(Class *c){
Person *temp,*p,q;
temp=c->p;
p=temp->next;
printf("输入要删除的学生姓名:\n");
scanf("%s",q.name);
while(p!=NULL){
	if(!strcmp(p->name,q.name)) break;
	else {
		temp=p;
		p=p->next;
	}//查找要删除的结点
}//while
if(p==NULL) return;
temp->next=p->next;
c->count--;
free(p); 
}
//-----------------------------修改元素----------------------------
void ListChange(Class *c){
Person *temp,q;
temp=c->p;
temp=temp->next;
printf("输入要修改的学生姓名:\n");
scanf("%s",q.name);
for(;(temp!=NULL)&&strcmp(temp->name,q.name);temp=temp->next);
/*
功能与上面的FOR循环一样
while(temp!=NULL){
	if(strcmp(temp->name,q.name)) break;
	else {
		temp=p;
		p=p->next;
	}//查找要修改的结点
}//while
*/
if(temp==NULL) 
	printf("没有该姓名的学生\n");
else {
	printf("输入新的姓名 语言 英文 数学的成绩:\n");
	scanf("%s%d %d %d",temp->name,&temp->Chineae,&temp->English,&temp->Maths);
	}
}
//----------------------------- 输出链表---------------------------
void print(Class *c){
Person *temp;
temp=c->p->next;
printf("姓名\t\t语言\t\t英文\t\t数学\n");
while(temp!=NULL){
	printf("%s\t\t%d\t\t%d\t\t%d\n",temp->name,temp->Chineae,temp->English,temp->Maths);
	temp=temp->next;
}
}
void print2(Class *c){
Person *temp;
temp=c->p->next;
printf("姓名\t\t语言\t\t英文\t\t数学\t\t名次\n");
while(temp!=NULL){
	printf("%s\t\t%d\t\t%d\t\t%d\t\t%d\n",temp->name,temp->Chineae,temp->English,temp->Maths,temp->Rank);
	temp=temp->next;
}
}
//-----------------------------目录--------------------------------
void menu(Class *c){
int i;
while(1){
	printf("1.创建链表 2.增加元素 3.删除元素 4.修改元素 5.输出链表 6.返回\n");
	scanf("%d",&i);
	getchar();
	switch(i){
		case 1 : clean();CreateList(c);break;
		case 2 : clean();ListInsert(c);break;
		case 3 : clean();ListDelete(c);break;
		case 4 : clean();ListChange(c);break;
		case 5 : clean();print(c);     break;
		case 6 : return;
		default : clean();printf("请输入正确操作!\n");
	}
}
}
//=============================链表操作完毕========================

//=============================链式基数排序操作====================

//-----------------------------第I位取余---------------------------
int Residue(int i,int num){
int j,n,m;
m=(int)pow(10.0,i-1);
n=(int)pow(10.0,i);
j=num%n;
if(i>1) j=j/m;
return j;
}
//-----------------------------拷贝结构体--------------------------
void StructCopy(Person *n,Person *m){
n->Chineae=m->Chineae;
n->English=m->English;
n->Maths=m->Maths;
strcpy(n->name,m->name);
n->next=NULL;
}
//-----------------------------选择菜单-----------------------------
int RadixMenu(){
int i;
printf("1.按语文成绩排名 2.按数学成绩排名 3.按英文成绩排名\n");
scanf("%d",&i);
return i;
}
//-----------------------------第I趟分配----------------------------
void Distribute(Person *p,int i,Person **f,Person **e,int kind){
int m,n;
Person *buff;
buff=p->next;
p->next=NULL;                                                       
for(n=0;n<RADIX;n++) 
	f[n]->next=NULL;																//初始化链表
while(buff!=NULL){
	if(kind==1)      m=Residue(i,buff->Chineae);
	else if(kind==2) m=Residue(i,buff->English);
	else             m=Residue(i,buff->Maths);
	if(f[m]->next==NULL) 
		{
		f[m]->next=buff;
		e[m]=buff;
		}
	else {
		e[m]->next=buff;		
		e[m]=buff;	
		}	
	buff=buff->next;
	e[m]->next=NULL;
	}//while
}
//-----------------------------第I趟收集返回给Person---------------
void Collect(Person *p,Person **f){
int i;
Person *buff,**temp;
buff=p;
temp=f;
for(i=RADIX-1;i>=0;i--){
	while(temp[i]->next!=NULL) {		
		p->next=temp[i]->next;	
		temp[i]=temp[i]->next;
		p=p->next;
		}
	}
p=NULL;
p=buff;
}
//-----------------------------进行排名----------------------------
void Rank(Person *p,int kind){
int i=0,n,m=0;
Person *buff;
buff=p->next;
while(buff!=NULL){
	if(kind==1)      n=buff->Chineae;
	else if(kind==2) n=buff->English;
	else             n=buff->Maths;
    if(m==n) buff->Rank=i;
	else buff->Rank=++i;
//	else if(n>m)
//	printf("%d",buff->Rank);
	buff=buff->next;
	m=n;
	}
}
//-----------------------------基数排序---------------------------- 
void RadixSort(Class *c){
int i,j,kind;
Person **f,**e;
kind=RadixMenu();
f=(Person **)malloc(RADIX*sizeof(Person*));
e=(Person **)malloc(RADIX*sizeof(Person*));
for(i=1;i<=c->KeyNum;i++){
for(j=0;j<RADIX;j++){ 
	f[j]=(Person *)malloc(sizeof(Person));
	e[j]=(Person *)malloc(sizeof(Person));
	}
	Distribute(c->p,i,f,e,kind);
	Collect(c->p,f);
//	if(j==RADIX-1) 										//进行排名
	}
Rank(c->p,kind);
print2(c);
printf("链式基数排序完成\n");
}
//=============================完毕================================

//============================= 文件基本操作=======================
//-----------------------------保存--------------------------------
void Save(Class *c){
Person *p;
FILE *fp;
p=c->p->next;
if((fp=fopen("Point.txt","wb+"))==NULL)
	printf("Point.txt OPEN ERROR!\n");
while(p!=NULL){
	fwrite(p,sizeof(Person),1,fp);
	p=p->next;
	}
printf("%d条记录保存成功!\n",c->count);
fclose(fp);
}
//-----------------------------读取--------------------------------
void Load(Class *c){
Person *p,*temp;
FILE *fp;
c->count=0;
p=c->p;
if((fp=fopen("Point.txt","rb"))==NULL)
	printf("Point.txt OPEN ERROR!\n");
while(!feof(fp)){
	temp=(Person *)malloc(sizeof(Person));
	fread(temp,sizeof(Person),1,fp);
	if(!feof(fp)){
		p->next=temp;
		temp->next=NULL;
		p=temp;
		c->count++;
	}
}
printf("%d条记录导入成功!\n",c->count);
fclose(fp);
}
//=============================完毕================================
//-----------------------------主函数------------------------------
void main(){
int i;
Class c;
c.p=(Person *)malloc(sizeof(Person));
c.count=0;
c.KeyNum=3;															//成绩最多为3位数
while(1){
	printf("1,编辑链表 2,链式基数排序 3,保存文件 4,读取文件 5,退出\n");
	scanf("%d",&i);
	switch(i){
	case 1 : clean();menu(&c);break;
	case 2 : clean();RadixSort(&c);break;
	case 3 : clean();Save(&c);break;
	case 4 : clean();Load(&c);break;
	case 5 : exit(0);break;
	default: clean();printf("请输入正确操作!\n");break;
	}
	}
}