IGNORANT

《学生选课系统》课程设计

<center>《学生选课系统》课程设计</center>

摘要: 面对学校庞大的课程体系,学生希望能修尽量少的课程并且又能获得满足毕业所要求的课程总学分。针对于此,我们设计出这项“学生选课系统”。系统的输入项是学校的课程体系的课程代号、先修课程代号以及课程学分,保存为CourseHierarchy.txt文件。系统然后从课程体系文件中读取数据,使用左孩子右兄弟表示法将其转换为二叉树,并对其的进行先序、中序以及后序遍历。通过查阅资料,我们判断出选课方案的求解问题,实质上是求解树形动态规划问题(简称“树形DP”),又因存储结构是二叉树,我们很容易得出了树形DP的状态转移方程,从而求解出选课方案。

关键字: 左孩子右兄弟 二叉树 选课 动态规划

<center>正文</center>

问题描述

大学的课程体系中,存在一部分课程,若要修读,须得先修完其先修课。假定每门课的直接先修课至多只有一门,两门课可能存在相同的先修课,并且课程之间不存在时间冲突。编写一个“学生选课系统”,使学生所选课程数目最少,并获得毕业所需学分,并且满足先修课程优先的原则。

基本要求

本系统实现的要求有:

1)从控制台输入课程体系数据,保存为CourseHierarchy/txt。

2)读取课程体系数据文件并创建二叉树。

3)输入毕业所需学分,输出选课方案及总学分。

算法思想

数据输入

从控制台输入数据并保存,采用C++的输入输出文件流对象

创建二叉树

创建二叉树时,使用C++标准库中的队列保存已插入的节点,当插入后续节点时,从队列中寻找后续节点的选修课程节点。再判断先修课程节点是否有“左孩子”。若有则添加新插入节点为“左孩子”;否则去判断是否存在“右兄弟”,若有则访问“右兄弟”的“右兄弟”,若仍存在,则有访问“右兄弟”,直到访问到最右的“右兄弟”,并添加新插入节点到其“右兄弟”上。

二叉树的遍历

参考了[1]中99页《遍历二叉树》。使用递归函数得出二叉树的先序、中序以及后序遍历。

选课方案的求解

定义一个二维数组F[][],Fi表示从i的父节点开始选j门课,LC[i]表示i节点的左孩子,RB[i]表示i节点的右兄弟,S[i]为课程i的学分。设毕业所需分数为CDT。

从节点i中选j门课程获得最大学分,求解思路大致如下:

  1. i不选,那么N门课程全部在RB[i]里选。
  1. i选,那么还要在LC[i]里选j-k门课,RB[i]中应选k-1门课。(k=1…j)
  2. 状态转移方程:

F[i][j]=max{F[i][j] ,F[LC[i]][j-k]+F[RB[i]][k-1]+S[i]}

  1. 最后求F0>=CDT的最小j,即是满足毕业所需学分的最少选课数。

模块划分

二叉树的创建

void BinTree::Create(const char *filename); 

二叉树的遍历

1)二叉树的先序遍历:

void BinTree::PreOrder(Node *rtNode);

2)二叉树的中序遍历:

void BinTree::InOrder(Node *rtNode);

3)二叉树的后序遍历:

void BinTree::PostOrder(Node* rtNode);

选课方案求解

1)求取从begin父节点开始选count门课的最大学分

void BinTree::CountCdt(Node* begin, int count);

2)搜索从begin父节点开始选count门课的最大学分所需要选的课程

void BinTree::SearchPath(Node *begin, int count);

3)输出满足毕业所需学分CDT条件下的选课最少的选课方案。

void BinTree::GetSolution(double CDT);

数据结构

使用的数据结构:二叉树、链表

源程序

项目已托管于https://gitee.com/julianchern/SetCourseSystem

源程序清单

SetCourseSystem:
│  BinTree.cpp
│  BinTree.h
│  main.cpp
│  Node.cpp
│  Node.h
│
└─Data:

源程序

main.cpp

#include <iostream>
#include <fstream>
#include "BinTree.h"
using namespace std;

int main() {
    char filename[] = "Data/CourseHierarchy.txt";    //record the course hierarchy
    ofstream outfile;
    outfile.open(filename, ios::trunc);      //open and clear the file
    if (!outfile.is_open()) {
        cout << "Failed to read the file:" << filename << "!" << endl;
        exit(1);
    }
    int crs{ 0 };    //course number
    int apc{ 0 };    //pre course number
    double crdt{ 0 };    //credit
    cout << "Please Input The Course Hierarchy(end whith '-1 -1 -1'):\t" << endl;
    cout << "course number" << '\t' << "AP course" << '\t' << "Credit" << endl;
    while (crs >= 0&&apc>=0) {    //write into the file
        outfile << crs << ' ' << apc << ' ' << crdt << endl;
        cin >> crs >> apc >> crdt;
    }
    outfile.close();
    int reqCredits;    //required credit when graduating
    cout << "Please Input the Required Credits:\t" << endl;
    cin >> reqCredits;
    BinTree bt;
    bt.Create("Data/CourseHierarchy.txt");    //create binary tree
    bt.Print();    //traversal and print binary tree
    bt.GetSolution(reqCredits);    //figure out the choose solution

    return 0;
}

BinTree.h

//
// Created by julian on 12/19/18.
//

#ifndef SETCOURSESYSTEM_BINTREE_H
#define SETCOURSESYSTEM_BINTREE_H

#include "Node.h"
#include <queue>
const int MN=14;

class BinTree {
public:
    //Constructor
    BinTree();
    ~BinTree();

    //
    Node* RetNode(int crs=0,double credit=0.0,
            Node* l=nullptr,Node* r= nullptr);  //return the applied address of new node
    void InsNode(int crs,int apc, double credit);    //insert a subnode into its parent node
    void Create(const char* filename);    //create a binary tree by reading the file
    void Print();   //print the binaryNode
    void RemoveNode(Node* rtNode);  //Remove all nodes
    //traversal
    void PreOrder(Node * rtNode);
    void InOrder(Node * rtNode);
    void PostOrder(Node * rtNode);
    //count credit
    void CountCdt(Node* begin,int count);
    void GetSolution(double CDT);
    void SearchPath(Node* begin,int count);
    void InitF();  //Init the F[][]

private:
    Node* root; //root node
    int Size;    //the number of nodes in this tree
    std::queue<Node*> Q;    //needed when create binary tree
    double F[MN][MN];    //save the max credit of choose course
    int Path[MN];    //record the path of choose course
};


#endif //SETCOURSESYSTEM_BINTREE_H

BinTree.cpp

//
// Created by julian on 12/19/18.
//

#include "BinTree.h"
#include <iostream>
#include <fstream>
using namespace std;

//auxiliary function
double Max(double l,double r){
    return l>r?l:r;
}

//print all nodes in this binary tree
void BinTree::Print() {
    cout << "PreOrder:\t";
    PreOrder(root);
    cout << endl << "InOrder:\t";
    InOrder(root);
    cout << endl << "PostOrder:\t";
    PostOrder(root);
    cout << endl;
}

//Init the F[][] by zeros
void BinTree::InitF(){
    for(int i{0};i<MN;i++)
        for(int j{0};j<MN;j++)
            F[i][j]=0;
}

//remove all nodes begin whith rtNode
void BinTree::RemoveNode(Node* rtNode) {
    if (rtNode == nullptr)
        return;
    RemoveNode(rtNode->lChild);
    RemoveNode(rtNode->rSibling);
    delete rtNode;
}

//return the space applied for
Node* BinTree::RetNode(int crs,double credit, Node* l,Node* r){
    Node* newNode=new Node(crs,credit,l,r);
    return newNode;
}

//constructor
BinTree::BinTree() {
    Size=0;
    InitF();
    for(int i{0};i<MN;i++)
        Path[i]=0;
    root= nullptr;
}

BinTree::~BinTree() {
    while (!Q.empty())
        Q.pop();
    RemoveNode(root);
    root= nullptr;
}

void BinTree::InsNode(int crs, int apc, double credit) {
    Size++;
    if(root==nullptr) {
        root = RetNode(crs, credit);
        Q.push(root);
    }else {
        while (Q.front()->crsNum != apc)    //look for its pre course
            Q.pop();
        Node *tN = Q.front();
        Node *newNode;
        if (tN->lChild == nullptr) {    //if no left child, take this as left
            newNode = RetNode(crs, credit);
            tN->lChild = newNode;
            Q.push(newNode);
        } else {        //if exsit left child, take this as sibling
            tN = tN->lChild;
            while (tN->rSibling != nullptr)
                tN = tN->rSibling;
            tN->rSibling = RetNode(crs, credit);
            Q.push(tN->rSibling);
        }
    }
}

//Build this binary tree
void BinTree::Create(const char *filename) {
    int csr{};    //save the course read from the file
    int apc{};    //save the pre course ...
    double crdt{};    //save the course credit ...
    //file operation
    ifstream infile(filename);
    if (!infile.is_open()) {
        cout << "Failed to read the file:" << filename << "!" << endl;
        exit(1);
    }
    //reading the data and processing
    while (infile >> csr && infile >> apc && infile >> crdt)    
        InsNode(csr, apc, crdt);
    infile.close();
}

//Traversal this tree
void BinTree::PreOrder(Node *rtNode) {
    if (rtNode == nullptr)
        return;
    cout << rtNode->crsNum << " ";
    PreOrder(rtNode->lChild);
    PreOrder(rtNode->rSibling);
}

void BinTree::InOrder(Node *rtNode) {
    if (rtNode == nullptr)
        return;
    InOrder(rtNode->lChild);
    cout << rtNode->crsNum << " ";
    InOrder(rtNode->rSibling);
}

void BinTree::PostOrder(Node* rtNode) {
    if (rtNode == nullptr)
        return;
    PostOrder(rtNode->lChild);
    PostOrder(rtNode->rSibling);
    cout << rtNode->crsNum << " ";
}

//get the max credit and save into F[][]
void BinTree::CountCdt(Node* begin, int count) {
    if (begin == nullptr || count == 0)    //if no course choosed, return
        return;
    else
        CountCdt(begin->rSibling, count);    //choose all in rsibling first
    Node *L = begin->lChild;
    Node *R = begin->rSibling;
    double tm = {0}, tp = {0};
    if (R)
        tm = F[R->crsNum][count];
    for (int k{1}; k <= count; k++) {    //must choose root node
        CountCdt(R, k - 1);    //choose from sibling
        CountCdt(L, count - k);    //choose from child
        if (L && R)    //update the F[][]
            tp = Max(tp, F[R->crsNum][k - 1] + F[L->crsNum][count - k] + begin->cdt);
    }
    //update the F[][]
    if (L && !R)
        tp = Max(tp, F[L->crsNum][count - 1] + begin->cdt);
    else if (!L && R)
        tp = Max(tp, F[R->crsNum][count - 1] + begin->cdt);
    if(count==1)
        tp = begin->cdt;
    F[begin->crsNum][count] = Max(tp, tm);
    return;
}

//Search the path of choose course
void BinTree::SearchPath(Node *begin, int count) {
    if (begin == nullptr || count == 0)    //if no course choosed, return
        return;
    Node *L = begin->lChild;
    Node *R = begin->rSibling;
    if (R && F[begin->crsNum][count] == F[R->crsNum][count])    //if courses choosed all are in sibling
        SearchPath(R, count);
    else {    //if courses are from child node and sibling node
        for (int k{1}; k <= count; k++) {
            if (L && R && F[begin->crsNum][count] ==
                          (F[R->crsNum][k - 1] + F[L->crsNum][count - k] + begin->cdt)) {
                SearchPath(R, k - 1);
                SearchPath(L, count - k);
                Path[begin->crsNum] = 1;
                return;
            }
        }
        if (L && !R && F[begin->crsNum][count] == F[L->crsNum][count - 1] + begin->cdt) {
            SearchPath(L, count - 1);
            Path[begin->crsNum] = 1;
            return;
        }
        if (!L && R && F[begin->crsNum][count] == F[R->crsNum][count - 1] + begin->cdt) {
            SearchPath(R, count - 1);
            Path[begin->crsNum] = 1;
            return;
        }
        if (F[begin->crsNum][count] == begin->cdt) {
            //if (count == 1) {
            Path[begin->crsNum] = 1;
            return;
        }
    }
}

//print out the choosing solution
void BinTree::GetSolution(double CDT) {
    Node* begin = root->lChild;
    int n{ 0 };
    for (int k{ 1 }; k < Size; k++) {
        CountCdt(begin, k);
        if (F[begin->crsNum][k] >= CDT) {
            n = k;
            break;
        }
        else
            InitF();
    }
    SearchPath(begin, n);
    cout << "Need to choose " << n << " course(s):\t" << endl;
    for (int i{ 1 }; i < MN; i++)
        if (Path[i] == 1)
            cout << '\t' << i << endl;
    cout << "Credit:\t" << F[begin->crsNum][n] << endl;
}

Node.h

//
// Created by julian on 12/19/18.
//

#ifndef SETCOURSESYSTEM_NODE_H
#define SETCOURSESYSTEM_NODE_H


class Node {
    friend class BinTree;
public:
    //Constructor
    Node(int crs=0,double credit=0.0,Node* l=nullptr,Node* r= nullptr);
    ~Node();

private:
    int crsNum; //course number
    double cdt; //course credit
    Node* lChild;   //left child node
    Node* rSibling;     //right sibling node
};


#endif //SETCOURSESYSTEM_NODE_H

Node.cpp

//
// Created by julian on 12/19/18.
//

#include "Node.h"

Node::Node(int crs,double credit,Node* l,Node* r){
    crsNum=crs;
    cdt=credit;
    lChild=l;
    rSibling=r;
}

Node::~Node() {
    crsNum=0;
    cdt=0.0;
    lChild= nullptr;
    rSibling= nullptr;
}

程序测试

测试环境

测试数据

1 0 2
2 0 1
3 0 3
4 0 2
5 1 4
6 1 2
7 2 1
8 3 3
9 3 2
10 4 2
11 6 4
12 6 3
13 9 5


<center>课程体系多叉树</center>


<center>左孩子右兄弟表示后的二叉树</center>

测试情况

此次测试假定毕业所需学分13学分,选课方案计算出最少选4门课程,分别为3号、8号、9号、13号课程。经验证,满足要求。

<center>总结</center>

通过对“学生选课系统”的编写,更加熟悉了链表的使用,加深了对二叉树这种数据结构的认识,以及其应用便利。在求解“选课方案”问题中,若非我们将多叉树转换为二叉树,由此大大简化了动态规划的转移方程,否则求解将会成为巨大的难题。
不足
1.输入课程体系时,必须按照一定顺序输入,否则导致二叉树的创建失败。
2.选课给出的方案只是其中一种方案,没有列出所有满足要求的选课方案。
3.探寻ing...

<center>参考文献</center>

[1]Clifford A.Shaffer著. 张铭,刘晓丹等译.《数据结构与算法分析(第三版)》.电子工业出版社,2013.10.
[2]Thomas H.Cormen / Charles E.Leiserson / Ronald L.Rivest / Clifford Stein著. 殷建平 / 徐云 / 王刚 / 刘晓光 / 苏明 / 邹恒明 / 王宏志译.《算法导论(原书第3版)》.机械工业出版社, 2012.12.
[3]《树的左孩子 右兄弟表示法的建立过程 (后序遍历)》

当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »