巨坑，懒得填了。上个学期的数据结构课设，没用到的算法。
// // main.cpp // 教学计划编制系统 // // Created by 郭子睿 on 2017/3/6. // Copyright © 2017年 郭子睿. All rights reserved. // #include "CourseGraph.hpp" int main(int argc, const char * argv[]) { Course A,B,C,D,E,F,G,H,I,J,K,L; A.No=1;B.No=2;C.No=3;D.No=4;E.No=5; F.No=6;G.No=7;H.No=8; I.No=9;J.No=10; K.No=11; L.No=12; A.Credit=2; B.Credit=3; C.Credit=4; D.Credit=3; E.Credit=2; F.Credit=3; G.Credit=4; H.Credit=4; I.Credit=7; J.Credit=5; L.Credit=2; A.Name="高等数学"; B.Name="大学物理"; C.Name="数据库"; D.Name="C++"; E.Name="数据结构"; F.Name="计算机组成原理"; G.Name="计算机图形学"; H.Name="大学英语"; I.Name="计算机体系结构"; J.Name="操作系统"; K.Name="Java"; L.Name="人工智能"; B.DirectNo.push_back(1); C.DirectNo.push_back(1); C.DirectNo.push_back(2); D.DirectNo.push_back(1); E.DirectNo.push_back(3); E.DirectNo.push_back(4); F.DirectNo.push_back(11); G.DirectNo.push_back(3); H.DirectNo.push_back(3); H.DirectNo.push_back(6); J.DirectNo.push_back(9); K.DirectNo.push_back(9); L.DirectNo.push_back(9); L.DirectNo.push_back(10); L.DirectNo.push_back(1); CourseGraph AI; AI.add_course(&A); AI.add_course(&B); AI.add_course(&C); AI.add_course(&D); AI.add_course(&E); AI.add_course(&F); AI.add_course(&G); AI.add_course(&H); AI.add_course(&I); AI.add_course(&J); AI.add_course(&K); AI.add_course(&L); bool FUCK=AI.build_graph(); if(FUCK){ AI.build_tree(); Term T(6,10); AI.build_path(T,9); AI.arrange_loose(); cout<<endl<<endl; AI.arrange_tight(); } return 0; } // // CourseGraph.hpp // 教学计划编制系统 // // Created by 郭子睿 on 2017/3/10. // Copyright © 2017年 郭子睿. All rights reserved. // #ifndef CourseGraph_hpp #define CourseGraph_hpp #include <stdio.h> #include <fstream> #include <iostream> #include <vector> #include <stack> using namespace std; //课程——————————————————————————————————————————————————————————————————————————— struct Course{ int No=0;//课程编号 string Name="";//课程名字 int Credit=0;//学分 vector<int> DirectNo;//直接先修课程编号 Course* Link=NULL;//用于建立图的链表存储 Course* LChild=NULL; Course* RChild=NULL; Course* Parent=NULL; Course(){} Course(const Course& A){ Parent=A.Parent; No=A.No; Name=A.Name; Credit=A.Credit; for(int i=0;i<A.DirectNo.size();++i) DirectNo.push_back(A.DirectNo[i]); } void operator=(const Course& A){ No=A.No; Name=A.Name; Credit=A.Credit; for(int i=0;i<A.DirectNo.size();++i) DirectNo.push_back(A.DirectNo[i]); } }; //学期——————————————————————————————————————————————————————————————————————————— struct Term{ int Credit;//每学期学分 int CurrentTerm;//当前学期 int M;//当前学期所剩学分 Term(int Credit_,int SumTerm_){ Credit=Credit_; M=Credit; CurrentTerm=SumTerm_; } Term(const Term& tl){ Credit=tl.Credit; M=Credit; CurrentTerm=tl.CurrentTerm; } }; //安排——————————————————————————————————————————————————————————————————————————— class CourseGraph{ vector<Course*> Courses;//用于存储课程信息；并用于存储有向图 Course* Tree=NULL;//用于存储有向图 vector<vector<int>> Arrange; ofstream Save; public: CourseGraph(){ Save.open("/Users/guozirui/Desktop/arrangement.txt"); } ~CourseGraph(){ Save.close(); for (int i=0; i<Courses.size(); ++i){//删除 Courses Course* temp=Courses[i]->Link; while(Courses[i]->Link!=NULL){ while(temp!=NULL) temp=temp->Link; delete temp; temp=Courses[i]->Link; } delete Courses[i]; } destroy(Tree);//删除 Tree } void add_course(Course* temp);//增加课程 bool build_graph();//建图 void build_tree(); void build_tree_part1(Course* Root); void build_tree_part2(Course* Root,stack<Course*>& TEMP_); Course* operator[](int i);//按课程编号搜索，返回课程 int return_no(int i);//按课程编号搜索，返回课程在 Courses 里的位置 vector<stack<Course>> caculate_path(); void find_leaf(Course* Root,vector<stack<Course*>>& Way); void build_path(const Term& T,int Wanted); void show_arrange(vector<int> C,bool X); void rank(bool A);//A 为假，升序排列；A 为真，降序排列。 void arrange_tight();//紧密安排 void arrange_loose();//均匀安排 //其他操作—————————————————————————————————————————————————————————————————————————————————————————————————————————————————————— void destroy(Course* Root){ if(Root==NULL) return; if(Root->LChild==NULL&&Root->RChild==NULL){ delete Root; Root=NULL; } else{ if(Root->LChild!=NULL) destroy(Root->LChild); if(Root->RChild!=NULL) destroy(Root->RChild); } } void swap(vector<int>* a,vector<int>* b){ vector<int> temp; temp=*a; *a=*b; *b=temp; } }; #endif /* CourseGraph_hpp */ // // CourseGraph.cpp // 教学计划编制系统 // // Created by 郭子睿 on 2017/3/10. // Copyright © 2017年 郭子睿. All rights reserved. // #include "CourseGraph.hpp" void CourseGraph::rank(bool A){ if(A){//升序排列；松散安排（因为比较的是剩余学期数，所以剩余学期数越小的安排得越松散） for(int i=0;i<Arrange.size();++i){ for(int j=(int)Arrange.size()-1;j>i;j--){ if(Arrange[j].back()<Arrange[j-1].back()){ swap(&Arrange[j], &Arrange[j-1]); } } } } else{//降序排列；紧密安排 for(int i=0;i<Arrange.size();++i){ for(int j=(int)Arrange.size()-1;j>i;j--){ if(Arrange[j][Arrange[j].size()-2]>Arrange[j-1][Arrange[j].size()-2]){ swap(&Arrange[j], &Arrange[j-1]); } } } } } void CourseGraph::add_course(Course *temp){ Courses.push_back(temp); } bool CourseGraph::build_graph(){ for(int i=0;i<Courses.size();++i){//建图 if(Courses[i]->DirectNo.size()==0)//如果该课程没有先决课程 continue;//那么继续 else{//如果该课程有先决课程 for(int j=0;j<Courses[i]->DirectNo.size();++j){ Course* temp=new Course(*Courses[i]); if(return_no(Courses[i]->DirectNo[j])==-1){ cout<<"课程设置错误！"; return false; } Course* temp1=Courses[return_no(Courses[i]->DirectNo[j])]; while(temp1->Link!=NULL) temp1=temp1->Link; temp1->Link=temp; } } } Course* temp=NULL; for(int i=0;i<Courses.size();++i){ if(Tree==NULL&&Courses[i]->DirectNo.size()==0){ Tree=new Course(*Courses[i]); temp=Tree; continue; } if(Courses[i]->DirectNo.size()==0){ while(temp->RChild!=NULL) temp=temp->RChild; temp->RChild=new Course(*Courses[i]); } } return true; } Course* CourseGraph::operator[](int i){ for(int j=0;j<Courses.size();++j) if(Courses[j]->No==i) return Courses[j]; return NULL; } int CourseGraph::return_no(int i){ for(int j=0;j<Courses.size();++j) if(Courses[j]->No==i) return j; return -1; } void CourseGraph::build_tree(){ stack<Course*> TEMP; for(int L=0;L<Courses.size();++L){ build_tree_part2(Tree,TEMP); while(!TEMP.empty()){ build_tree_part1(TEMP.top()); TEMP.pop(); } } } void CourseGraph::build_tree_part1(Course *Root){ Course* temp=NULL; Course* temp1=NULL; Course* temp2=NULL; if(Root==NULL) return; bool* Ava=new bool[Courses.size()]{false};//用于保存已经安排的课程个数 temp=Root->Parent; while(temp!=NULL){//用于计算已经选过的课程 Ava[return_no(temp->No)]=true;//将已经选过的课程置为已选 temp=temp->Parent; } if(Root->Parent==NULL){//如果该课程没有父母结点 temp=Tree; while(temp!=NULL){ if(temp!=Root){ if(Root->LChild==NULL){ Ava[return_no(temp->No)]=true; Root->LChild=new Course(*temp); Root->LChild->Parent=Root; temp2=Root->LChild; } else{ Ava[return_no(temp->No)]=true; temp2->RChild=new Course(*temp); temp2->RChild->Parent=Root; temp2=temp2->RChild; } } temp=temp->RChild; } temp1=Courses[return_no(Root->No)]->Link; if(temp1==NULL) return; while(temp1!=NULL){ if(Root->LChild==NULL){ temp=new Course(*temp1); if(Ava[return_no(temp->No)]==false){ Ava[return_no(temp->No)]=true; Root->LChild=temp; temp->Parent=Root; temp2=Root->LChild; } } else{ temp=new Course(*temp1); if(Ava[return_no(temp->No)]==false){ Ava[return_no(temp->No)]=true; temp2->RChild=temp; temp2=temp2->RChild; temp2->Parent=Root; } } temp1=temp1->Link; } return; } else{ temp1=NULL; temp2=NULL; temp=Root->Parent->LChild;//让 temp 指针指向第一个孩子 while(temp==Root) temp=temp->RChild;//找到 Root 的父母的第一个不是 Root 的孩子 if(temp!=NULL){ temp1=new Course(*temp);//temp1 用于新建结点 Root->LChild=temp1; Ava[return_no(temp1->No)]=true; Root->LChild->Parent=Root; temp=temp->RChild; temp2=Root->LChild; while(temp!=NULL){ if(temp==Root){ temp=temp->RChild; continue; } temp1=new Course(*temp); temp2->RChild=temp1; temp2->RChild->Parent=Root; Ava[return_no(temp1->No)]=true; temp=temp->RChild; temp2=temp2->RChild; } } temp=Courses[return_no(Root->No)]->Link; while (temp!=NULL){ if(Root->LChild==NULL){ if(Ava[return_no(temp->No)]!=true){ temp1=new Course(*temp); Root->LChild=temp1; Root->LChild->Parent=Root; temp2=Root->LChild; } temp=temp->Link; } else{ if(Ava[return_no(temp->No)]!=true){ temp1=new Course(*temp); temp2->RChild=temp1; temp2->RChild->Parent=Root; temp2=temp2->RChild; } temp=temp->Link; } } } } void CourseGraph::build_tree_part2(Course* Root,stack<Course*>& TEMP_){ if(Root->LChild==NULL) TEMP_.push(Root); if(Root->LChild!=NULL) build_tree_part2(Root->LChild,TEMP_); if(Root->RChild!=NULL) build_tree_part2(Root->RChild,TEMP_); return; } void CourseGraph::find_leaf(Course* Root,vector<stack<Course*>>& Way){ if(Root->LChild==NULL&&Root->RChild==NULL){ stack<Course*> temp; Course* temp1=new Course(*Root); temp.push(temp1); Way.push_back(temp); return; } else{ if(Root->LChild!=NULL) find_leaf(Root->LChild,Way); if(Root->RChild!=NULL) find_leaf(Root->RChild,Way); return; } } void CourseGraph::build_path(const Term& T,int Wanted){ vector<stack<Course*>> Way; find_leaf(Tree,Way); int Plus; if(Wanted>Way.size()) Plus=1; else Plus=(int)((float)Way.size()/Wanted+0.5); for(int i=0;i<Way.size();i=i+Plus){//求出所有路径 Course* temp=Way[i].top(); while(temp->Parent!=NULL){ Course* temp1=new Course(*temp->Parent); Way[i].push(temp1); temp=temp->Parent; } } for(int i=0;i<Way.size();i=i+Plus){ Term TL(T); for(int j=0;j<Way[i].size();j++){ vector<int> C; C.push_back(0); while(Way[i].size()!=0){ if(TL.M>=Way[i].top()->Credit){//如果该学期学分还够的话 TL.M-=Way[i].top()->Credit;//就减去该课程学分 C.push_back(Way[i].top()->No); delete Way[i].top(); Way[i].pop(); } else{ TL.CurrentTerm--; if(TL.CurrentTerm==0&&Way[i].size()!=0) break; C.push_back(0); TL.M=TL.Credit; TL.M-=Way[i].top()->Credit; C.push_back(Way[i].top()->No); delete Way[i].top(); Way[i].pop(); } } if(Way[i].size()!=0) continue; C.push_back(TL.CurrentTerm); C.push_back(TL.CurrentTerm); Arrange.push_back(C); } } for(int i=0;i<Way.size();++i){ while(!Way[i].empty()){ delete Way[i].top(); Way[i].pop(); } Way.pop_back(); } for(int i=0;i<Arrange.size();++i){ for(int j=1;j<Arrange[i].size()-2;++j){ if(Arrange[i].back()<2) break; if(Arrange[i][j]==0||Arrange[i][j]==-1) continue; else if(Arrange[i][j-1]!=0&&Arrange[i][j-1]!=-1){ Arrange[i].insert(Arrange[i].begin()+j,-1); Arrange[i].back()--; } } } } void CourseGraph::arrange_tight(){ cout<<"！！！！！！！！！！！！！！！！！！紧密安排！！！！！！！！！！！！！！！！！！！！！！！！！！！！"<<endl; Save<<"！！！！！！！！！！！！！！！！！！紧密安排！！！！！！！！！！！！！！！！！！！！！！！！！！！！"<<endl; for(int i=0;i<Arrange.size();++i){ cout<<"第"<<i+1<<"种方法"; Save<<"第"<<i+1<<"种方法"; show_arrange(Arrange[i],0); cout<<endl<<endl; Save<<endl<<endl; } } void CourseGraph::arrange_loose(){ cout<<"！！！！！！！！！！！！！！！！！！松散安排！！！！！！！！！！！！！！！！！！！！！！！！！！！！"<<endl; Save<<"！！！！！！！！！！！！！！！！！！松散安排！！！！！！！！！！！！！！！！！！！！！！！！！！！！"<<endl; for(int i=0;i<Arrange.size();++i){ cout<<"第"<<i+1<<"种方法"; Save<<"第"<<i+1<<"种方法"; show_arrange(Arrange[i],1); cout<<endl<<endl; Save<<endl<<endl; } } void CourseGraph::show_arrange(vector<int> C,bool X){ if(X){ int k=1; for(int i=0;i<C.size()-2;++i){ if(C[i]==0||C[i]==-1){ cout<<endl<<"第"<<k<<"学期"<<endl; Save<<endl<<"第"<<k<<"学期"<<endl; k++; } else{ cout<<"课程编号："<<Courses[return_no(C[i])]->No<<" "<<"学分："<<Courses[return_no(C[i])]->Credit<<endl; Save<<"课程编号："<<Courses[return_no(C[i])]->No<<" "<<"学分："<<Courses[return_no(C[i])]->Credit<<endl; cout<<"课程名称："<<Courses[return_no(C[i])]->Name<<endl; Save<<"课程名称："<<Courses[return_no(C[i])]->Name<<endl; } } } else{ int k=1; for(int i=0;i<C.size()-2;++i){ if(C[i]==0){ cout<<endl<<"第"<<k<<"学期"<<endl; Save<<endl<<"第"<<k<<"学期"<<endl; k++; } else if(C[i]==-1) continue; else{ cout<<"课程编号："<<Courses[return_no(C[i])]->No<<" "<<"学分："<<Courses[return_no(C[i])]->Credit<<endl; Save<<"课程编号："<<Courses[return_no(C[i])]->No<<" "<<"学分："<<Courses[return_no(C[i])]->Credit<<endl; cout<<"课程名称："<<Courses[return_no(C[i])]->Name<<endl; Save<<"课程名称："<<Courses[return_no(C[i])]->Name<<endl; } } } }