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

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

屏幕录制2023-12-27 22.28.48

课设要求

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

  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的地方改成课程数量变量）。希望本文能帮助到大家，再次感谢阅读。在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/274852.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

使用pandas处理数据的一些总结

使用pandas处理数据的一些总结

1、替换换行符等特殊符号 df df.replace({None: "", np.nan: "", "\t": "", "\n": "", "\x08": ""}, regexTrue) 2、清除DataFrame中所有数据的左右空格&#xff0c;字符串中间空格不会清…
阅读更多...
庙算兵棋推演AI开发初探（2-编写策略（上））

庙算兵棋推演AI开发初探（2-编写策略（上））

开始研读step()函数的编写方法。 这个是图灵网提供了一些基础的ai代码下载&#xff08;浏览需要注册&#xff0c;下载需要审批&#xff09;。 AI开发中心-人机对抗智能 (ia.ac.cn)http://turingai.ia.ac.cn/ai_center/show 一、代码研读(BaseAgent类) 1.step函数 这段代码定…
阅读更多...
git的常用命令以及在可视化工具中的使用方法

git的常用命令以及在可视化工具中的使用方法

一.引言 想当初在刚进公司的时候&#xff0c;对于git的使用非常不熟悉&#xff0c;特别是分支的概念&#xff0c;导致开发效率变低&#xff0c;故通过此文章&#xff0c;总结git的使用经验 二.Git 常用命令详解 2.1 git clone [url]: 克隆远程仓库到本地 刚开始时&#xff0c…
阅读更多...
机器学习深度学习面试笔记

机器学习深度学习面试笔记

机器学习&深度学习面试笔记 机器学习Q. 在线性回归中&#xff0c;如果自变量之间存在多重共线性&#xff0c;会导致什么问题&#xff1f;如何检测和处理多重共线性&#xff1f;Q. 什么是岭回归(Ridge Regression)和Lasso回归(Lasso Regression)&#xff1f;它们与普通线性回…
阅读更多...
Three.js基础入门介绍——Three.js学习三【借助控制器操作相机】

Three.js基础入门介绍——Three.js学习三【借助控制器操作相机】

在Three.js基础入门介绍——Three.js学习二【极简入门】中介绍了如何搭建Three.js开发环境并实现一个包含旋转立方体的场景示例&#xff0c;以此为前提&#xff0c;本篇将引进一个控制器的概念并使用”轨道控制器”&#xff08;OrbitControls&#xff09;来达到从不同方向展示场…
阅读更多...
Linux下安装RocketMQ

Linux下安装RocketMQ

1、创建文件夹app/rocketMQ 在xshell里可以找到这里&#xff0c;xftp可以直接创建文件夹&#xff0c;并上传文件&#xff0c;也可以使用命令创建文件夹&#xff0c; 创建文件夹命令&#xff1a;mkdir app、mkdir rocketMQ 2、上传好后解压 使用命令解压 unzip 压缩包名 3、获…
阅读更多...
基于Python的城市热门美食数据可视化分析系统

基于Python的城市热门美食数据可视化分析系统

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长 QQ 名片 :) 1. 项目简介 本项目利用网络爬虫技术从XX点评APP采集北京市的餐饮商铺数据&#xff0c;利用数据挖掘技术对北京美食的分布、受欢迎程度、评价、评论、位置等情况进行了深入分析&#xff0c;方便了解城市美食店…
阅读更多...
❀My小学习之排序算法❀

❀My小学习之排序算法❀

目录 排序算法&#xff08;Sorting algorithm&#xff09;:) 一、定义 二、分类 三、评价标准 排序算法&#xff08;Sorting algorithm&#xff09;:) 一、定义 所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的…
阅读更多...
[MySQL] MySQL 高级(进阶) SQL 语句

[MySQL] MySQL 高级(进阶) SQL 语句

一、高效查询方式 1.1 指定指字段进行查看 事先准备好两张表 select 字段1&#xff0c;字段2 from 表名; 1.2 对字段进行去重查看 SELECT DISTINCT "字段" FROM "表名"; 1.3 where条件查询 SELECT "字段" FROM 表名" WHERE "条件…
阅读更多...
Feature Prediction Diffusion Model for Video Anomaly Detection 论文阅读

Feature Prediction Diffusion Model for Video Anomaly Detection 论文阅读

Feature Prediction Diffusion Model for Video Anomaly Detection论文阅读 Abstract1. Introduction2. Related work3. Method3.1. Problem Formulation3.2. Feature prediction diffusion module 3.3. Feature refinement diffusion module4. Experiments and discussions4.1…
阅读更多...
ArcGIS Pro中Conda环境的Scripts文件解读

ArcGIS Pro中Conda环境的Scripts文件解读

Scripts中包含的文件如下 1. propy.bat 用于在 ArcGIS Pro 外部运行 Python 脚本&#xff08;扩展名为 .py 的文件&#xff09;。使用的conda环境是与ArcGIS pro环境同步。propy.bat原理是代替各自python环境下的python.exe&#xff0c;主要区别是propy.bat使用的是与Pro同的…
阅读更多...
比起 Pandas, 你更需要 Polars：详细指南

比起 Pandas, 你更需要 Polars：详细指南

在数据分析领域&#xff0c;Python 由于其多功能性和广泛的库生态系统而成为一种流行的语言。数据处理和分析在提取见解和做出明智决策方面发挥着至关重要的作用。然而&#xff0c;随着数据集的规模和复杂性不断增长&#xff0c;对高性能解决方案的需求变得至关重要。 有效地处…
阅读更多...
JMeter控制器之While控制器

JMeter控制器之While控制器

1. 背景 存在一些使用场景&#xff0c;比如&#xff1a;某个请求必须等待上一个请求正确响应后才能开始执行。或者&#xff0c;不断去请求某个接口的响应结果&#xff0c;当它达到某个状态时才开始后续请求。&#xff08;例如&#xff1a;某系统中存在一个功能&#xff1a;判断…
阅读更多...
Android : 画布的使用 简单应用

Android : 画布的使用 简单应用

示例图&#xff1a; MyView.java&#xff1a; package com.example.demo;import android.content.Context; import android.graphics.BitmapFactory; import android.graphics.Canvas; import android.graphics.Color; import android.graphics.Paint; import android.view.Vi…
阅读更多...
Linux内核定时器-模块导出符号表

Linux内核定时器-模块导出符号表

Linux内核定时器 定时器的当前时间如何获取&#xff1f; jiffies:内核时钟节拍数 jiffies是在板子上电这一刻开始计数&#xff0c;只要 板子不断电&#xff0c;这个值一直在增加&#xff08;64位&#xff09;。在 驱动代码中直接使用即可。 定时器加1代表走了多长时间&#xff…
阅读更多...
一.windows2012搭建fpt服务器和常见端口介绍

一.windows2012搭建fpt服务器和常见端口介绍

一.windows2012搭建fpt服务器和常见端口介绍 1.打开防火墙2.创建组2.1打开计算机管理2.2创建组并且设置名称和描述 3.创建用户3.1设置用户密码和名称3.2把用户归属于组3.3把user删除掉3.4点击添加然后点高级3.5点击立即查找选择之前设定的组 4.安装ftp服务器4.1点击添加角色和功…
阅读更多...
重生奇迹mu中玩家之间的交易操作

重生奇迹mu中玩家之间的交易操作

重生奇迹mu游戏中的直接交易 在重生奇迹mu中的交易总共有四种方式。第一种就是玩家之间直接进行交易&#xff0c;具体操作就是点击你所要交易的玩家&#xff0c;这个点击的意思是指你把鼠标移动到这名玩家的角色身上&#xff0c;然后你就锁定了此玩家&#xff0c;同时游戏界面…
阅读更多...
每日一题 2735. 收集巧克力（中等）

每日一题 2735. 收集巧克力（中等）

暴力枚举&#xff0c;真难甭 class Solution:def minCost(self, nums: List[int], x: int) -> int:n len(nums)f nums[:]ans sum(f)for k in range(1, n):for i in range(n):f[i] min(f[i], nums[(i k) % n])ans min(ans, k * x sum(f))return ans
阅读更多...
深入探索MongoDB集群模式：从高可用复制集

深入探索MongoDB集群模式：从高可用复制集

MongoDB复制集概述 MongoDB复制集主要用于实现服务的高可用性&#xff0c;与Redis中的哨兵模式相似。它的核心作用是数据的备份和故障转移。 复制集的主要功能 数据复制&#xff1a;数据写入主节点&#xff08;Primary&#xff09;时&#xff0c;自动复制到一个或多个副本节…
阅读更多...
【头歌实训】Spark 完全分布式的安装和部署（新）

【头歌实训】Spark 完全分布式的安装和部署（新）

文章目录 第1关&#xff1a; Standalone 分布式集群搭建任务描述相关知识课程视频Spark分布式安装模式主机映射免密登录准备Spark安装包配置环境变量修改 spark-env.sh 配置文件修改 slaves 文件分发安装包启动spark验证安装 编程要求测试说明答案代码 第1关&#xff1a; Stand…
阅读更多...
最新文章

Copyright @ 2022~2023