#include<iostream> #include<iomanip> #include<ctime> #include<fstream> #include<string> #define radix 10 using namespace std; clock_t start,stop; //学生的结构体 typedef struct SNode{ string name; int ID; //学号 int key[4]={0}; //成绩 struct SNode *next; //指针域 }SNode,*Student; void StudentGrade(int n); //生成学生成绩信息文件new.txt,n为文件读取数据的组数 Student CreatStudent_old(Student &L,int num); //读取old.txt,尾插法建立学生成绩单链表L,num为总人数 Student CreatStudent_new(Student &L,int num); //读取new.txt,尾插法建立学生成绩单链表L,num为总人数 Student BubbleSort(Student &L,int order[]); //MSD冒泡排序，L为学生成绩链表,order[]为用户输入的次关键字顺序 Student RadixSort(Student &L,int order[]); //LSD基数排序，L为学生成绩链表,order[]为次关键字顺序 void Print(Student &L); //在屏幕上显示 void choose(Student &L); //选择功能 void Menu(); //菜单 int main(){ ofstream fout; fout.open("C:\\Out.txt",ios::app); if(!fout){ cout<<"无法打开文件！！！"<<endl; } int a; do{ Menu(); //调用菜单 cout<<" 输入0结束，输入其他则可重新生成成绩再进行排序"; cin>>a; fout<<" 输入0结束，输入其他则可重新生成成绩再进行排序"<<a; }while(a!=0) ; //a等于0停止循环 return 0; } //菜单 void Menu(){ ofstream fout; fout.open("C:\\Out.txt",ios::app); if(!fout){ cout<<"无法打开文件！！！"<<endl; } cout<<endl; cout<<endl; cout<<" --------------------------------------------------"<<endl; cout<<" |------------------学生成绩排序------------------|"<<endl; cout<<" | |"<<endl; cout<<" | 本程序可以按关键字的优先关系排序对成绩排序。 |"<<endl; cout<<" | |"<<endl; cout<<" | 学生成绩有两种方式产生 |"<<endl; cout<<" | 输入1：从old.txt文件中读取 |"<<endl; cout<<" | 输入2：随机产生数据并导入new.txt文件中 |"<<endl; cout<<" --------------------------------------------------"<<endl; cout<<endl; //输出到文件 fout<<endl; fout<<endl; fout<<" --------------------------------------------------"<<endl; fout<<" ------------------学生成绩排序------------------"<<endl; fout<<" "<<endl; fout<<" 本程序可以按关键字的优先关系排序对成绩排序。 "<<endl; fout<<" "<<endl; fout<<" 学生成绩有两种方式产生 "<<endl; fout<<" 输入1：从old.txt文件中读取 "<<endl; fout<<" 输入2：随机产生数据并导入new.txt文件中 "<<endl; fout<<" --------------------------------------------------"<<endl; fout<<endl; Student L; int a; cout<<" 选择产生成绩的方式："; cin>>a; cout<<endl; fout<<" 选择产生成绩的方式："<<a<<endl; switch (a) { case 1: int n; cout<<" 从old.txt文件中读取多少组数据："; cin>>n; fout<<" 从old.txt文件中读取多少组数据："<<n<<endl; CreatStudent_old(L,n); //调用函数创建学生成绩单链表 break; case 2: int m; cout<<" 需要随机产生多少组数据："; cin>>m; fout<<" 需要随机产生多少组数据："<<m<<endl; StudentGrade(m); CreatStudent_new(L,m); //调用函数创建学生成绩单链表 break; } Print(L); //调用打印函数将生成的学生成绩信息打印在屏幕上 int b; do{ cout<<" --------------------------------------------------"<<endl; cout<<" | 请选择： |"<<endl; cout<<" | 1.MSD策略对数据进行冒泡法排序 |"<<endl; cout<<" | 2.LSD策略对数据进行基数排序 |"<<endl; cout<<" --------------------------------------------------"<<endl; fout<<" --------------------------------------------------"<<endl; fout<<" 请选择： "<<endl; fout<<" 1.MSD策略对数据进行冒泡法排序 "<<endl; fout<<" 2.LSD策略对数据进行基数排序 "<<endl; fout<<" --------------------------------------------------"<<endl; choose(L); //调用选择函数，选择排序方式和排序次序 cout<<" 输入0结束，输入其他数则继续进行此成绩的排序"; cin>>b; cout<<endl; fout<<" 输入0结束，输入其他数则继续进行此成绩的排序"<<b<<endl; }while(b!=0); } //生成学生成绩信息文件new.txt,n为需要随机生成的数据组数 void StudentGrade(int n){ ofstream fout; fout.open("C:\\new.txt",ios::out); if(!fout){ cout<<"无法打开文件！！！"<<endl; } string name; //姓名 int id; //学号 int score[4]; //分数 //随机产生数据并写入new中 string studentname[10]={"a","b","c","d","e","f","g","h","i","j"}; srand(time(0)); for(int a=1;a<=n;a++){ name=studentname[rand()%10] + studentname[rand()%10] + studentname[rand()%10];//对字进行随机组合生成姓名 fout<<name<<" "; id=a; fout<<id<<" "; for(int c=0;c<=3;c++){ //初始化成绩 score[c]=0; } for(int b=0;b<3;b++){ score[b]=rand()%101; //随机产生成绩 fout<<score[b]<<" "; score[3]=score[3]+score[b]; //总分 } fout<<score[3]<<endl; } fout.close(); } //读取old.txt,尾插法建立学生成绩单链表L,num为人数 Student CreatStudent_old(Student &L,int num){ ifstream fin; fin.open("C:\\old.txt",ios::in); if(!fin){ cout<<"无法打开文件！！！"<<endl; } Student p,r; L=new SNode; L->next=NULL; //创建带头结点的链表L r=L; //尾指针指向头结点 for(int i=1;i<=num;i++){ p=new SNode; //生成新结点 fin>>p->name; //读取姓名 fin>>p->ID; //读取学号 for(int j=0;j<=3;j++){ fin>>p->key[j]; } p->next=NULL; r->next=p; //将新结点p插入尾结点r之后 r=p; //r指向新的尾结点p } return L; } //读取new.txt里的数据，尾插法建立学生成绩单链表L,num为人数 Student CreatStudent_new(Student &L,int num){ ifstream fin; fin.open("C:\\new.txt",ios::in); if(!fin){ cout<<"无法打开文件！！！"<<endl; } Student p,r; L=new SNode; L->next=NULL; //创建带头结点的链表L r=L; //尾指针指向头结点 for(int i=1;i<=num;i++){ p=new SNode; //生成新结点 fin>>p->name; //读取姓名 fin>>p->ID; //读取学号 for(int j=0;j<=3;j++){ fin>>p->key[j]; } p->next=NULL; r->next=p; //将新结点p插入尾结点r之后 r=p; //r指向新的尾结点p } return L; } //选择功能 void choose(Student &L){ ofstream fout; fout.open("C:\\Out.txt",ios::app); if(!fout){ cout<<"无法打开文件！！！"<<endl; } double time; //排序时间 cout<<" "; fout<<" "; int order[4]; int a; cin>>a; fout<<a<<endl; cout<<" --------------------------------------------------"<<endl; fout<<" --------------------------------------------------"<<endl; switch (a) { case 1: cout<<" 输入次关键字比较顺序，0为语文，1为数学，2为英语,3为总分，总分默认第一个"<<endl; cout<<endl; fout<<" 输入次关键字比较顺序，0为语文，1为数学，2为英语,3为总分，总分默认第一个"<<endl; fout<<endl; for(int i=0;i<=3;i++){ cout<<" 第"<<i+1<<"个次序"; cin>>order[i]; cout<<endl; fout<<" 第"<<i+1<<"个次序"; fout<<order[i]<<endl; } start=clock(); BubbleSort(L,order); //调用冒泡排序 stop=clock(); time=(double)(stop-start)/CLK_TCK; Print(L); //打印结果 cout<<" 排序所用时间："<<time<<endl;; fout<<" 排序所用时间："<<time<<endl; break; case 2: cout<<" 输入次关键字比较顺序，0为语文，1为数学，2为英语,3为总分，总分默认第一个"<<endl; cout<<endl; fout<<" 输入次关键字比较顺序，0为语文，1为数学，2为英语,3为总分，总分默认第一个"<<endl; fout<<endl; for(int i=0;i<=3;i++){ cout<<" 第"<<i+1<<"个次序"; cin>>order[i]; cout<<endl; fout<<" 第"<<i+1<<"个次序"; fout<<order[i]<<endl; } start=clock(); RadixSort(L,order); //调用基数排序 stop=clock(); time=(double)(stop-start)/CLK_TCK; Print(L); cout<<" 排序所用时间："<<time<<endl; fout<<" 排序所用时间："<<time<<endl; break; default: cout<<" 选择不存在，请输入1或者2"<<endl; fout<<" 选择不存在，请输入1或者2"<<endl; break; } } //MSD冒泡排序，L为学生成绩链表,order[]为用户输入的次关键字顺序 Student BubbleSort(Student &L,int order[]){ int flag=1; //标记，判断该趟排序是否发生交换 Student p,q,t; while(flag==1){ t=L; p=L->next; q=p->next; flag=0; while(q){ int k1=order[0]; if(p->key[k1]<q->key[k1]){ //交换数据域，指针域不变 flag=1; //发生交换，flag变成1 p->next=q->next; t->next=q; q->next=p; q=p->next; } else if(p->key[k1]==q->key[k1]){ //总分相等，比较第二次序 int k2=order[1]; if(p->key[k2]<q->key[k2]){ flag=1; p->next=q->next; t->next=q; q->next=p; q=p->next; } else if(p->key[k2]==q->key[k2]){ //第二次序相等，比较第三次序 int k3=order[2]; if(p->key[k3]<q->key[k3]){ flag=1; p->next=q->next; t->next=q; q->next=p; q=p->next; } if(p->key[k3]==q->key[k3]){ //第三次序相等，比较第四次序 int k4=order[3]; if(p->key[k4]<q->key[k4]){ flag=1; p->next=q->next; t->next=q; q->next=p; q=p->next; } else { p=p->next; q=q->next; } }//if(k2) else { p=p->next; q=q->next; } }//if(k1) else { p=p->next; q=q->next; } }//if(3) else { p=p->next; q=q->next; } t=t->next; }//while }//while return L; } //LSD基数排序，L为学生成绩链表,order[]为次关键字顺序 Student RadixSort(Student &L,int order[]){ Student front[radix],end[radix],p,t; int m,k; for(int n=3;n>=0;n--){ k=order[n]; for(int d=1;d<=3;d++){ //位数 for(int i=0;i<radix;i++){ //初始化各链队首尾指针 front[i]=end[i]=NULL; } p=L->next; while(p){ if(d==1){ m=p->key[k]%10; //第一趟取个位分配 } else if(d==2){ m=(p->key[k]%100)/10; //第二趟分配取十位 } else{ m=p->key[k]/100; //第三趟取百位分配 } if(front[m]==NULL){ //采用尾插法建立单链表 front[m]=p; end[m]=p; } else{ end[m]->next=p; end[m]=p; } p=p->next; }//while L->next=NULL; for(int j=radix-1;j>=0;j--){ //对每一个链队从大到小进行收集 if(front[j]){ if(L->next==NULL){ L->next=front[j]; //L指向链队头 t=end[j]; //t指向队尾 } else{ t->next=front[j]; //t->next指向下一个链队头 t=end[j]; } } t->next=NULL; //最后一个结点指向空 }//for } } return L; } //在屏幕上显示 void Print(Student &L){ ofstream fout; fout.open("C:\\Out.txt",ios::app); if(!fout){ cout<<"无法打开文件！！！"<<endl; } cout<<" --------------------------------------------------"<<endl; cout<<setw(8)<<"姓名"<<setw(8)<<"学号"<<setw(8)<<"语文"<<setw(8)<<"数学"<<setw(8)<<"英语"<<setw(8)<<"总分"<<endl; fout<<" --------------------------------------------------"<<endl; fout<<setw(8)<<"姓名"<<setw(8)<<"学号"<<setw(8)<<"语文"<<setw(8)<<"数学"<<setw(8)<<"英语"<<setw(8)<<"总分"<<endl; Student p; p=L->next; while(p){ cout<<setw(8)<<p->name; cout<<setw(8)<<p->ID; fout<<setw(8)<<p->name; fout<<setw(8)<<p->ID; for(int i=0;i<4;i++){ //依次输出4个数据 cout<<setw(8)<<p->key[i]; fout<<setw(8)<<p->key[i]; } cout<<endl; fout<<endl; p=p->next; } cout<<endl; fout<<endl; }