【c++、数据结构课设】拓扑序列的应用

再贡献一篇课设，希望能帮助到正在做课设的小伙伴。

课设要求

题目描述 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满 足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学 期。试在这样的前提下设计一个教学计划编制系统。
? 系统功能要求
该程序满足以下主要功能:

1. 完成课程进修目录信息的读取，其中输入参数应包括:学期总数，一学期的学分上限;每门课:
   课程号(可以是固定占 3 位的字母数字串)、学分、直接先修课的课程号表，是否基础课，是否
   专业核心课。至少提供 30 门课程信息，通过文件读入。
2. 按下列策略进行课程计划编排:
3. 在各学期中的学习负担尽量均匀，即确定学分最大上限值。
4. 在没有超学分时尽可能优先安排基础课和核心专业课程。
5. 若根据所给的所有课程，无法构造拓扑序列则报告适当的信息，建议报告适当信息，并修改开
   设的课程;否则给出构造的拓扑序列作为一种教学安排计划，并将该教学计划输出到用户指定的文件中。 5. 可设学期总数不超过 12，课程总数不超过 60。
6. 要求分别输出 6 学期、8 学期制和 12 学期制的一个计划。输出这两种学制下每一学期的课程选
   择(这些课程在本学期开课时其先修课程已经修完)，且满足学分及基础、核心课优先开设的要求。

数据结构

typedef struct {
    //学期总数
    int term;
    //每学期学分上限
    int score;

} coursePlan;
typedef struct {
    //课程编号
    int num;
    //学分
    int score;
    //先修课数量
    int size;
    //先修课
    int *pre;
    //是否为基础课 0：不是 1：是
    int basic;
    //是否为专业课 不是 1：是
    int major;
    //是否已排课
    bool flag = false;
} course;
//顶点数组
course *e[10000];

//第一个结点
int h[10000];

//下一个结点
int ne[10000];

//如果ne[i]被重复使用了
int Ne[10000];

//如果ne[i]重复使用了，后面就用Ne[IDX]代替ne[i]
int IDX = 30;
//入度
int p[10000];

//已排课程
course *q[1000000];

//已排课程数量
int cnt;

过程

初始化

创建邻节表，对数组进行初始化

void init(){
    memset(h,-1,sizeof h);
    memset(ne,-1,sizeof ne);

}

读文件

从文件读取课程信息，表头按照：课程编号、学分、先修课数量、先修课课程编号、是否基础课和专业课

void read(course *c, int *totalScore) {
    cout << "正在努力读取课程信息中ing" << endl;
    sleep(1);
    ifstream in;
    in.open("/Users/yuwei/Desktop/c++/practice/course.txt", ios::in);
    for (int i = 0; i < 30; i++) {
        course *tem = new course;

        //读入课程编号、学分、先修课数量、是否为基础课、专业课
        in>>tem->num>>tem->score>>tem->size;

        *totalScore+=tem->score;

        tem->pre = new int[tem->size];
        for(int i =0;i<tem->size;i++){
            in>>tem->pre[i];
        }
        //先修课数量等于入度
        p[i]=tem->size;
        in>>tem->basic>>tem->major;
        e[tem->num-100] = tem;

    }
    cout << "读取完成！！！" << endl;

}

输入

输入学期信息和学期学分上限，并检查是否合理（要满足课程总学分不超过总学分上限）

void input(coursePlan *c, int *totalScore) {
    cout << "-----------------------------------------------------------------------" << endl;
    cout << "请输入学期总数： " << endl;
    cin >> c->term;
    cout << endl << "请输入每学分上限： " << endl;
    cin >> c->score;
    cout << endl;

    check(c, totalScore);

}

void check(coursePlan *c, int *totalScore) {
    cout << "-----------------------------------------------------------------------" << endl;

    if (*totalScore > c->score * c->term) {
        cout << "-----------------------------------------------------------------------" << endl;
        cout << "                         排 课 失 败                                     " << endl;
        cout << "-----------------------------------------------------------------------" << endl;
        cout << "课程总学分超过学分上限！！！" << endl;
        input(c,totalScore);
    } else {
        cout << "-----------------------------------------------------------------------" << endl;
        cout << "                         排 课 成 功                                    " << endl;
        cout << "-----------------------------------------------------------------------" << endl;

    }

}

构造有向图

这里要考虑ne[i]会被重复使用而覆盖上次的结果，这里采用曲线救国法，用ne[IDX]（IDX大于课程数量）代替ne[i],Ne[IDX] = i;(通过Ne找到i）

//a--->b (a是b的先修课)
void add(int a,int b){

    if(ne[b]==-1){
        ne[b] = h[a];
        h[a] = b;
    }
    else {
        ne[IDX] = h[a];
        h[a] = IDX;
        Ne[IDX++] = b;
    }

}


//构造图
void generateMap(){
    for(int i =0;i<30;i++){

        if(e[i]->size){

            for(int j =0;j<e[i]->size;j++){

                //先修课 ----> 该课程
                add(e[i]->pre[j]-100,e[i]->num-100);

            }
        }
    }
}

查找基础课和专业课

int find(int *t,int size){
    //如果为基础课或者专业课返回id；
    int i=0;
    for( i =0;i<size;i++)if(e[t[i]]->major||e[t[i]]->basic)return i;
    return i;
}

拓扑排序

拓扑排序原理就是找入度为0的结点，应为入度为零（没有结点指向你）代表你没有先修课，或者先修课已经被选了

void topSort(coursePlan*c,int *totalScore,int* nowScore){
    //平均每学期要修够的学分(向上取整)
    int score = (*totalScore+c->term-1)/c->term;
    //还需要修的学分
    int s = *totalScore - *nowScore;
    if(s<score) score = s;
    //本轮已经排课的课程总学分
    int temScore=0;
    //本轮选课第一节课id
    int start = cnt;

    while (temScore<score){

        //找度为零的结点，度为零的结点：没有先修课或者先修课已经排课了

        //备选课程
        int tem[100],idx=0;
        for(int i =0;i<30;i++){
            if(!p[i]&&!e[i]->flag) tem[idx++]=i;
        }
       int id= find(tem,idx);

        //没有基础课程和专业课程 随便选
        if(id==idx&&idx){

            if(temScore+e[tem[0]]->score<=score){
                q[cnt++] =e[tem[0]];
                e[tem[0]]->flag=true;
                temScore+=e[tem[0]]->score;
                // 更新以该课程为先修课的课程的 入度
                for(int i =h[tem[0]];i!=-1;i=ne[i]){
                    //i大于30 ne[i] 已经用过一次了 p[Ne[i]]--才对
                    if(i<30)
                    p[i]--;
                    else p[Ne[i]]--;
                }
            }
            else break;

        }
        else if (idx){
            if(temScore+e[tem[0]]->score<=score){

                q[cnt++] =e[tem[id]];
                e[tem[id]]->flag=true;
                temScore+=e[tem[id]]->score;
                // 更新以该课程为先修课的课程的 入度
                for(int i =h[tem[id]];i!=-1;i=ne[i]){
                    if(i<30)
                        p[i]--;
                    else p[Ne[i]]--;

                }
            }
            else break;

        }
        else break;


    }

    *nowScore += temScore;
    //本学期选课最后一节课id
    int end = cnt-1;
    if(end>start)
    print(start,end);

}

完整代码

#include <iostream>
#include <unistd.h>
#include <cstdio>
#include <fstream>
#include <string>

using namespace std;

typedef struct {
    //学期总数
    int term;
    //每学期学分上限
    int score;

} coursePlan;
typedef struct {
    //课程编号
    int num;
    //学分
    int score;
    //先修课数量
    int size;
    //先修课
    int *pre;
    //是否为基础课 0：不是 1：是
    int basic;
    //是否为专业课 不是 1：是
    int major;
    //是否已排课
    bool flag = false;
} course;
//顶点数组
course *e[10000];

//第一个结点
int h[10000];

//下一个结点
int ne[10000];

//如果ne[i]被重复使用了
int Ne[10000];

//如果ne[i]重复使用了，后面就用Ne[IDX]代替ne[i]
int IDX = 30;
//入度
int p[10000];

//已排课程
course *q[1000000];

//已排课程数量
int cnt;


void check(coursePlan *c, int *totalScore);
void print(int start,int end);

void welcome() {
    cout << "-----------------------------------------------------------------------" << endl;
    cout << "|                                                                      |" << endl;
    cout << "|                            欢 迎 回 来                                 |" << endl;
    cout << "|                                                                      |" << endl;
    cout << "-----------------------------------------------------------------------" << endl;
    cout << endl;

}
void init(){
    memset(h,-1,sizeof h);
    memset(ne,-1,sizeof ne);

}
void read(course *c, int *totalScore) {
    cout << "正在努力读取课程信息中ing" << endl;
    sleep(1);
    ifstream in;
    in.open("/Users/yuwei/Desktop/c++/practice/course.txt", ios::in);
    for (int i = 0; i < 30; i++) {
        course *tem = new course;

        //读入课程编号、学分、先修课数量、是否为基础课、专业课
        in>>tem->num>>tem->score>>tem->size;

        *totalScore+=tem->score;

        tem->pre = new int[tem->size];
        for(int i =0;i<tem->size;i++){
            in>>tem->pre[i];
        }
        //先修课数量等于入度
        p[i]=tem->size;
        in>>tem->basic>>tem->major;
        e[tem->num-100] = tem;

    }
    cout << "读取完成！！！" << endl;

}

void input(coursePlan *c, int *totalScore) {
    cout << "-----------------------------------------------------------------------" << endl;
    cout << "请输入学期总数： " << endl;
    cin >> c->term;
    cout << endl << "请输入每学分上限： " << endl;
    cin >> c->score;
    cout << endl;

    check(c, totalScore);

}

void check(coursePlan *c, int *totalScore) {
    cout << "-----------------------------------------------------------------------" << endl;

    if (*totalScore > c->score * c->term) {
        cout << "-----------------------------------------------------------------------" << endl;
        cout << "                         排 课 失 败                                     " << endl;
        cout << "-----------------------------------------------------------------------" << endl;
        cout << "课程总学分超过学分上限！！！" << endl;
        input(c,totalScore);
    } else {
        cout << "-----------------------------------------------------------------------" << endl;
        cout << "                         排 课 成 功                                    " << endl;
        cout << "-----------------------------------------------------------------------" << endl;

    }

}
//a--->b (a是b的先修课)
void add(int a,int b){

    if(ne[b]==-1){
        ne[b] = h[a];
        h[a] = b;
    }
    else {
        ne[IDX] = h[a];
        h[a] = IDX;
        Ne[IDX++] = b;
    }

}
//构造图
void generateMap(){
    for(int i =0;i<30;i++){

        if(e[i]->size){

            for(int j =0;j<e[i]->size;j++){

                //先修课 ----> 该课程
                add(e[i]->pre[j]-100,e[i]->num-100);

            }
        }
    }
}
int find(int *t,int size){
    //如果为基础课或者专业课返回id；
    int i=0;
    for( i =0;i<size;i++)if(e[t[i]]->major||e[t[i]]->basic)return i;
    return i;
}

void topSort(coursePlan*c,int *totalScore,int* nowScore){
    //平均每学期要修够的学分(向上取整)
    int score = (*totalScore+c->term-1)/c->term;
    //还需要修的学分
    int s = *totalScore - *nowScore;
    if(s<score) score = s;
    //本轮已经排课的课程总学分
    int temScore=0;
    //本轮选课第一节课id
    int start = cnt;

    while (temScore<score){

        //找度为零的结点，度为零的结点：没有先修课或者先修课已经排课了

        //备选课程
        int tem[100],idx=0;
        for(int i =0;i<30;i++){
            if(!p[i]&&!e[i]->flag) tem[idx++]=i;
        }
       int id= find(tem,idx);

        //没有基础课程和专业课程 随便选
        if(id==idx&&idx){

            if(temScore+e[tem[0]]->score<=score){
                q[cnt++] =e[tem[0]];
                e[tem[0]]->flag=true;
                temScore+=e[tem[0]]->score;
                // 更新以该课程为先修课的课程的 入度
                for(int i =h[tem[0]];i!=-1;i=ne[i]){
                    //i大于30 ne[i] 已经用过一次了 p[Ne[i]]--才对
                    if(i<30)
                    p[i]--;
                    else p[Ne[i]]--;
                }
            }
            else break;

        }
        else if (idx){
            if(temScore+e[tem[0]]->score<=score){

                q[cnt++] =e[tem[id]];
                e[tem[id]]->flag=true;
                temScore+=e[tem[id]]->score;
                // 更新以该课程为先修课的课程的 入度
                for(int i =h[tem[id]];i!=-1;i=ne[i]){
                    if(i<30)
                        p[i]--;
                    else p[Ne[i]]--;

                }
            }
            else break;

        }
        else break;


    }

    *nowScore += temScore;
    //本学期选课最后一节课id
    int end = cnt-1;
    if(end>start)
    print(start,end);

}
void print(int start,int end){
    for(int i =start;i<=end;i++){
        cout<<q[i]->num<<"\t\t"<<q[i]->score<<"\t\t"<<q[i]->basic<<"\t\t"<<q[i]->major<<endl;
    }
}

int main() {

    welcome();
    init();
    course *c =new course ;
    coursePlan *P = new coursePlan ;
    int totalScore=0;
    int nowScore = 0;
    read(c,&totalScore);
    input(P,&totalScore);
    generateMap();
    cout << "-----------------------------------------------------------------------" << endl;
    cout << "                         排 课 结 果                                    " << endl;
    cout << "-----------------------------------------------------------------------" << endl;
    cnt = 0;

    cout<<"课程编号  "<<"学分   "<<"基础课 "<<" 选修课"<<endl;
    for(int i =1;i<=P->term;i++){

        cout<<"第 "<<i<<" 学期"<<endl;

        topSort(P,&totalScore,&nowScore);
    }


}

总结

核心功能已经完成，其实应该再加入课程信息的增删改查，留个读者自己完成。（记住将课程数量由固定的30变成变量，还要代码中的用到30的地方改成课程数量变量）。希望本文能帮助到大家，再次感谢阅读。