#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;
}