图结构的应用：教学计划编制问题

梦里梦外; 2022-03-01 06:18 182阅读 0赞

有两种方法：一种没有学分排序，另一种考虑了学分排序，较推荐栈中排好序的方法，贪心更完全

测试数据文本：

C1 程序设计基础 # 2
    C2 离散数学 C1 3
    C3 数据结构 C1,C2 4
    C4 汇编语言 C1 3
    C5 语言的设计和分析 C3,C4 2
    C6 计算机原理 C11 3
    C7 编译原理 C3,C5 4
    C8 操作系统 C3,C6 4
    C9 高等数学 # 7 
    C10 线性代数 C9 5
    C11 普通物理 C9 2
    C12 数值分析 C1,C9,C10 3

#include<iostream>
    #include<fstream>
    #include<iomanip>
    #define XQ_num 12               //最大学期数
    #define Total_Book_num 100        //最大课程数
    #define TRUE 1
    #define ERROR 0
    using namespace std;
    struct Book                     //节点的数据类型
    {
     char Book_num[4];                                   //不能为3，因为会把后面的字符串也读取进来
     char Book_nam[20];
     int study_Score;
     int in_Degree;                   //指入度点的个数
     int state;                        //标记是否已经修过这门课程
     Book *next;                   //指先行课的地址
     char book[40];             //先修课程字符串
     int num;                      //记录是第几门课
     int n;                       //记录有几门先行课
    };
    struct Build_Graph             //用邻接表的方法构建图，数组的位置则是记录该节点邻接了所有得点
    {
     Book *graph;              
     int n;									// int *length.....length数组的长度
     void build_Graph(int n1)  //课程的门数---(注意这个不能设为构造函数，否则后面栈中的数据结构会引用这个数据结构没有构造参数)
     {
      graph=new Book [n1];			//每个数组为一门课程并且为邻接表的头节点
    										//length=new int [n1];           //指头节点每个链表的长度，同数组存储
      for(int i=0;i<n1;i++)
      {
    	  graph[i].next=NULL;
    								// length[i]=0;                     //记录每门课的先行课的门数(未修的门数),不需要，用入度决定有几门先行可
      }
      n=n1;
     }
     void Book_insert(Book p,int i)									 //插入每门要修的课程
     {
    	 graph[i]=p;
    	  graph[i].num=i+1;							//记录是第几门课,从第1门开始
    	  graph[i].in_Degree=0;
    	  graph[i].state=1;                     //如果状态为1时则是未被访问过，0则表示是访问过
    	  graph[i].n=0;
     }
     void Build_Graph_insert(Book &p,int j,int n)					//在j之后插入节点,在第n门课
     {
    	 Book *pp=&graph[n-1];
    	 for(int i=1;i<j;i++)
    		 pp=pp->next;
    	 pp->next=&p;
    	 graph[n-1].in_Degree++;							//length[n]++;
     }
     void Fu_Zhi()                               //对每个变量进行赋值
     {
    	 int i;
    	 for(i=0;i<n;i++)
    	 {
    		 Fenjie(graph[i].book,graph[i]);
    	 }
     }
     void Fenjie(char a[],Book &c)                        //为门课程建立邻接表
    {
    	char b[5];
    	int length=strlen(a);
    	int i=0,j=0,k=0;        
    	while(i<length)
    	{
    		Book *t=new Book;			 //从第1门开始记录
    		while(a[i]!=','&&a[i]!='#'&&i<length)
    		{
    			b[j]=a[i];
    			i++;j++;
    		}
    		if(a[i]=='#'){break;}           //注意这里存放的先后顺序
    		b[j]='\0';
    		*t=graph[PiPei(b)-1];               //c[k]数组记录每一门课程的先行课的数字型编号
    		(*t).next=NULL;
    		(*t).in_Degree=0;
    		k++;                                  //
    		Build_Graph_insert(*t,k,c.num);      //因为是从自己本身开始算起，所以要从k+1门课后传递指针
    		if(a[i]==','){i++;j=0;continue;}
    		i++;j=0;
    	}
    	c.n=k;
    }
    int PiPei(char a[])
    {
    	if(!strcmp(a,"C1")) return 1;
    	else
    		if(!strcmp(a,"C2")) return 2;
    		else
    			if(!strcmp(a,"C3"))return 3;
    			else
    				if(!strcmp(a,"C4"))return 4;
    				else
    					if(!strcmp(a,"C5"))return 5;
    					else
    						if(!strcmp(a,"C6"))return 6;
    						else
    							if(!strcmp(a,"C7"))return 7;
    							else
    								if(!strcmp(a,"C8"))return 8;
    								else
    									if(!strcmp(a,"C9"))return 9;
    									else
    										if(!strcmp(a,"C10"))return 10;
    										else
    											if(!strcmp(a,"C11"))return 11;
    											else
    												if(!strcmp(a,"C12"))return 12;
    }
     void display1()									//输出所有课程表的信息
     {
    	cout<<setiosflags(ios::left);
    	cout<<setw(15)<<"课程编号"<<setw(30)<<"课程名称"<<setw(20)<<"先决条件"<<"学分"<<endl;
    	cout<<"--------------------------------------------------------------------------------"<<endl;
    	for(int i=0;i<n;i++)
    	{
    		cout<<setw(15)<<graph[i].Book_num<<setw(30)<<graph[i].Book_nam<<setw(20)<<graph[i].book<<graph[i].study_Score<<endl;
    	}
     }
     void display2()									 //输出邻接表的函数
     {
    	 int i,j;
    	 Book *t;
    	 for(i=0;i<n;i++)
    	 {
    		 
    		 t=&graph[i];
    		 if(graph[i].in_Degree==0)cout<<graph[i].Book_num<<endl;
    		 else
    			 cout<<graph[i].Book_num<<"-->";
    		 for(j=1;j<=graph[i].in_Degree;j++)
    		 {
    			 t=t->next;
    			 if(j==graph[i].in_Degree)cout<<t->Book_num<<endl;
    			 else
    			 {
    				cout<<t->Book_num<<"-->";
    			 }
    		 }
    	 }
     }
     void Destory()
     {
    	 delete graph;
     }
    };
    
    struct Stack        //构造栈
    {
    	Book *base;
    	int top;
    	int length;								//记录栈中数据的长度
    	//Build_Graph graph1;
    	//int sum1;							 //学期总数
    	//int top_score;						//每个学期的学分上线
    	Stack(int n)
    	{
    		base=new Book [n];   因为有多少门课是已经在Build_Graph结构中的n变量中包含，因为最大的课程数为total_booknum
    		top=-1;
    		length=0;
    	}
    	void Destory_Stack()
    	{
    		delete base;
    	}
    	void Clear_Stack()
    	{
    		top=-1;
    		length=0;
    	}
    	bool Test_Stack_Empty()					//栈空为true，不空为false
    	{
    		if(top==-1)return true;
    		else return false;
    	}
    	Book Get_Top()							//获得栈顶元素并把栈顶元素输出栈
    	{
    		top--;
    		length--;
    		return base[top+1];
    	}
    	int Get_Top_Study_Score()
    	{
    		int t;
    		t=base[top].study_Score;
    		return t;
    	}
    	void Push(Book p)
    	{
    		top++;
    		length++;
    		base[top]=p;
    	}
    	int Length_Stack()
    	{
    		return length;
    	}
    };
    
    void Topological_Sort(Stack s,Build_Graph g,int a)          //a是总的课程数目
    {
      cout<<"--------------------------------------------------------------------------------"<<endl;
      int sum,top_score,ii,i,j,k,average;
      cout<<"                                 学期总数:";cin>>sum;
      cout<<"                             每学期的学分上线为:";cin>>top_score;
      if(sum>XQ_num){cout<<"                             输入的学期数超出了范围!"<<endl; return ;}
      if(top_score>Total_Book_num){cout<<"                             输入的课程数超出了范围!"<<endl;return ;}
      cout<<"--------------------------------------------------------------------------------"<<endl;
      cout<<"                              课程编排的结果为:"<<endl;
      cout<<"--------------------------------------------------------------------------------"<<endl;
       average=a/sum;average+=1;            //每个学期选的课数小于等于average
      int count1=0,count2=0;           //count1记录学期的个数,第几个学期,count2记录等于average学期的个数
      int sum_course=0;
      for(ii=0;ii<sum;ii++)			//有几个学期就循环多少次
      {
    	  for(i=0;i<a;i++)                //每个学期找入度为0并且没有被访问过节点进栈
    	  {
    		  if((g.graph[i].in_Degree==0)&&(g.graph[i].state==1))
    			  s.Push(g.graph[i]);
    	  }
    	  count1++;
    	  Book *pp=new Book;
    	  int sum_score=0;                  //记录每个学期
    	  int ss=0;           //记录每个学期选课的门数总的学分
    	  cout<<"第"<<count1<<"个学期所选的课程为:      ";
    	  while((!s.Test_Stack_Empty())&&(ss<average)&&((sum_score+s.Get_Top_Study_Score())<=top_score)&&(count2<average))          //安排一个学期的课程
    	  {
    		  pp=&s.Get_Top();
    		  cout<<(*pp).Book_nam<<"	";
    		  sum_course++;
    		  g.graph[(*pp).num-1].state=0;             //注意是原来的图的入读数-1
    		  ss++;
    		  sum_score+=(*pp).study_Score;
    		  Book *p;
    		  for(j=0;j<a;j++)               //入度为0的节点的后序节点的入读-1
    		  {
    			  if(j==((*pp).num-1))continue;
    			  int n=g.graph[j].in_Degree;
    			  if(n!=0)
    			  {
    				  p=&g.graph[j];
    				  for(k=0;k<(g.graph[j].n);k++)             //找一个链表中相匹配的课程
    				  {
    					  p=p->next;
    					  if((*pp).num==p->num){g.graph[j].in_Degree--;}
    				  }
    			  }
    		  }
    	  }
    	  s.Clear_Stack();
    	  if(ss==average)count2++;
    	  cout<<endl;
      }
      if(sum_course==a)cout<<"课程编排成功!"<<endl;
      else cout<<"课程编排失败!"<<endl;
      cout<<"--------------------------------------------------------------------------------"<<endl;
    }
    int main()
    {
     int total_booknum,n;
     cout<<"--------------------------------------------------------------------------------"<<endl;
     cout<<"                           欢迎进入课程编排系统                               "<<endl;
     cout<<"--------------------------------------------------------------------------------"<<endl;
    con:cout<<"                 是否开始进行课程编排，是请按1，退出请按0：";
    	cin>>n;
     while(n==1)
     {
    	 system("cls");
      cout<<"                             该专业开设的课程数:";cin>>total_booknum;
      cout<<"--------------------------------------------------------------------------------"<<endl;
      cout<<"输入每门课的课程信息(文件的读入)";
      ifstream in("课程信息.txt");
      if(!in)
      {
       cerr<<"打开文本-课程信息.txt-有误!"<<endl;
       exit(1);
      }
      Build_Graph Graph;
      Graph.build_Graph(total_booknum);
      int i;Book p;
      for(i=0;i<total_booknum;i++)
      {
    	  in>>p.Book_num>>p.Book_nam>>p.book>>p.study_Score;
    	  Graph.Book_insert(p,i);
      }
      in.close();
      cout<<"要编排的课程信息如下(没有先行课的先行课属性为#):"<<endl;
    	  Graph.display1();                                             //课程信息的输出
    	  Graph.Fu_Zhi();
    	  cout<<"--------------------------------------------------------------------------------"<<endl;
    	  cout<<"课程的邻接表(右边为该门课的先行课)为:"<<endl;
    	  Graph.display2();
    	  Stack T_sort(total_booknum);
    	  Topological_Sort(T_sort,Graph,total_booknum);
    	  goto con;
     }
     if((n!=1)&&(n!=0)){cout<<"输入的数据不符合，请重新输入!"<<endl;goto con;}
     return 0;
    }

排序后：

#include<iostream>
    #include<fstream>
    #include<iomanip>
    #define XQ_num 12               //最大学期数
    #define Total_Book_num 100        //最大课程数
    #define TRUE 1
    #define ERROR 0
    using namespace std;
    struct Book                     //节点的数据类型
    {
     char Book_num[4];                                   //不能为3，因为会把后面的字符串也读取进来
     char Book_nam[20];
     int study_Score;
     int in_Degree;                   //指入度点的个数
     int state;                        //标记是否已经修过这门课程
     Book *next;                   //指先行课的地址
     char book[40];             //先修课程字符串
     int num;                      //记录是第几门课
     int n;                       //记录有几门先行课
    };
    struct Build_Graph             //用邻接表的方法构建图，数组的位置则是记录该节点邻接了所有得点
    {
     Book *graph;              
     int n;									// int *length.....length数组的长度
     void build_Graph(int n1)  //课程的门数---(注意这个不能设为构造函数，否则后面栈中的数据结构会引用这个数据结构没有构造参数)
     {
      graph=new Book [n1];			//每个数组为一门课程并且为邻接表的头节点
    										//length=new int [n1];           //指头节点每个链表的长度，同数组存储
      for(int i=0;i<n1;i++)
      {
    	  graph[i].next=NULL;
    								// length[i]=0;                     //记录每门课的先行课的门数(未修的门数),不需要，用入度决定有几门先行可
      }
      n=n1;
     }
     void Book_insert(Book p,int i)									 //插入每门要修的课程
     {
    	 graph[i]=p;
    	  graph[i].num=i+1;							//记录是第几门课,从第1门开始
    	  graph[i].in_Degree=0;
    	  graph[i].state=1;                     //如果状态为1时则是未被访问过，0则表示是访问过
    	  graph[i].n=0;
     }
     void Build_Graph_insert(Book &p,int j,int n)					//在j之后插入节点,在第n门课
     {
    	 Book *pp=&graph[n-1];
    	 for(int i=1;i<j;i++)
    		 pp=pp->next;
    	 pp->next=&p;
    	 graph[n-1].in_Degree++;							//length[n]++;
     }
     void Fu_Zhi()                               //对每个变量进行赋值
     {
    	 int i;
    	 for(i=0;i<n;i++)
    	 {
    		 Fenjie(graph[i].book,graph[i]);
    	 }
     }
     void Fenjie(char a[],Book &c)                        //为门课程建立邻接表
    {
    	char b[5];
    	int length=strlen(a);
    	int i=0,j=0,k=0;        
    	while(i<length)
    	{
    		Book *t=new Book;			 //从第1门开始记录
    		while(a[i]!=','&&a[i]!='#'&&i<length)
    		{
    			b[j]=a[i];
    			i++;j++;
    		}
    		if(a[i]=='#'){break;}           //注意这里存放的先后顺序
    		b[j]='\0';
    		*t=graph[PiPei(b)-1];               //c[k]数组记录每一门课程的先行课的数字型编号
    		(*t).next=NULL;
    		(*t).in_Degree=0;
    		k++;                                  //
    		Build_Graph_insert(*t,k,c.num);      //因为是从自己本身开始算起，所以要从k+1门课后传递指针
    		if(a[i]==','){i++;j=0;continue;}
    		i++;j=0;
    	}
    	c.n=k;
    }
    int PiPei(char a[])
    {
    	if(!strcmp(a,"C1")) return 1;
    	else
    		if(!strcmp(a,"C2")) return 2;
    		else
    			if(!strcmp(a,"C3"))return 3;
    			else
    				if(!strcmp(a,"C4"))return 4;
    				else
    					if(!strcmp(a,"C5"))return 5;
    					else
    						if(!strcmp(a,"C6"))return 6;
    						else
    							if(!strcmp(a,"C7"))return 7;
    							else
    								if(!strcmp(a,"C8"))return 8;
    								else
    									if(!strcmp(a,"C9"))return 9;
    									else
    										if(!strcmp(a,"C10"))return 10;
    										else
    											if(!strcmp(a,"C11"))return 11;
    											else
    												if(!strcmp(a,"C12"))return 12;
    }
     void display1()									//输出所有课程表的信息
     {
    	cout<<setiosflags(ios::left);
    	cout<<setw(15)<<"课程编号"<<setw(30)<<"课程名称"<<setw(20)<<"先决条件"<<"学分"<<endl;
    	cout<<"--------------------------------------------------------------------------------"<<endl;
    	for(int i=0;i<n;i++)
    	{
    		cout<<setw(15)<<graph[i].Book_num<<setw(30)<<graph[i].Book_nam<<setw(20)<<graph[i].book<<graph[i].study_Score<<endl;
    	}
     }
     void display2()									 //输出邻接表的函数
     {
    	 int i,j;
    	 Book *t;
    	 for(i=0;i<n;i++)
    	 {
    		 
    		 t=&graph[i];
    		 if(graph[i].in_Degree==0)cout<<graph[i].Book_num<<endl;
    		 else
    			 cout<<graph[i].Book_num<<"-->";
    		 for(j=1;j<=graph[i].in_Degree;j++)
    		 {
    			 t=t->next;
    			 if(j==graph[i].in_Degree)cout<<t->Book_num<<endl;
    			 else
    			 {
    				cout<<t->Book_num<<"-->";
    			 }
    		 }
    	 }
     }
     void Destory()
     {
    	 delete graph;
     }
    };
    
    struct Stack        //构造栈
    {
    	Book *base;
    	int top;
    	int length;								//记录栈中数据的长度
    	//Build_Graph graph1;
    	//int sum1;							 //学期总数
    	//int top_score;						//每个学期的学分上线
    	Stack(int n)
    	{
    		base=new Book [n];   因为有多少门课是已经在Build_Graph结构中的n变量中包含，因为最大的课程数为total_booknum
    		top=-1;
    		length=0;
    	}
    	void Destory_Stack()
    	{
    		delete base;
    	}
    	void Clear_Stack()
    	{
    		top=-1;
    		length=0;
    	}
    	bool Test_Stack_Empty()					//栈空为true，不空为false
    	{
    		if(top==-1)return true;
    		else return false;
    	}
    	Book Get_Top()							//获得栈顶元素并把栈顶元素输出栈
    	{
    		top--;
    		length--;
    		return base[top+1];
    	}
    	int Get_Top_Study_Score()
    	{
    		int t;
    		t=base[top].study_Score;
    		return t;
    	}
    	void Push(Book p)
    	{
    		top++;
    		length++;
    		base[top]=p;
    	}
    	int Length_Stack()
    	{
    		return length;
    	}
    	void PX_MAX_MIN()       //排序，从小到大
    	{
    		int i,j;Book t;
    		for(i=0;i<(length-1);i++)
    		{
    			int max=base[i].study_Score;
    			for(j=i+1;j<length;j++)
    			{
    				if(max<base[j].study_Score)
    				{
    					t=base[i];
    					base[i]=base[j];
    					base[j]=t;
    				}
    			}
    		}
    	}
    };
    
    void Topological_Sort(Stack s,Build_Graph g,int a)          //a是总的课程数目
    {
      cout<<"--------------------------------------------------------------------------------"<<endl;
      int sum,top_score,ii,i,j,k,average;
      cout<<"                                 学期总数:";cin>>sum;
      cout<<"                             每学期的学分上线为:";cin>>top_score;
      if(sum>XQ_num){cout<<"                             输入的学期数超出了范围!"<<endl; return ;}
      if(top_score>Total_Book_num){cout<<"                             输入的课程数超出了范围!"<<endl;return ;}
      cout<<"--------------------------------------------------------------------------------"<<endl;
      cout<<"                              课程编排的结果为:"<<endl;
      cout<<"--------------------------------------------------------------------------------"<<endl;
       average=a/sum;average+=1;            //每个学期选的课数小于等于average
      int count1=0,count2=0;           //count1记录学期的个数,第几个学期,count2记录等于average学期的个数
      int sum_course=0;
      for(ii=0;ii<sum;ii++)			//有几个学期就循环多少次
      {
    	  for(i=0;i<a;i++)                //每个学期找入度为0并且没有被访问过节点进栈
    	  {
    		  if((g.graph[i].in_Degree==0)&&(g.graph[i].state==1))
    			  s.Push(g.graph[i]);
    	  }
    	  count1++;
    	  Book *pp=new Book;
    	  int sum_score=0;                  //记录每个学期
    	  int ss=0;           //记录每个学期选课的门数总的学分
    	  cout<<"第"<<count1<<"个学期所选的课程为:      ";
    	  s.PX_MAX_MIN();
    	  while((!s.Test_Stack_Empty())&&(ss<average)&&((sum_score+s.Get_Top_Study_Score())<=top_score)&&(count2<average))          //安排一个学期的课程
    	  {
    		  s.PX_MAX_MIN();
    		  pp=&s.Get_Top();
    		  cout<<(*pp).Book_nam<<"	";
    		  sum_course++;
    		  g.graph[(*pp).num-1].state=0;             //注意是原来的图的入读数-1
    		  ss++;
    		  sum_score+=(*pp).study_Score;
    		  Book *p;
    		  for(j=0;j<a;j++)               //入度为0的节点的后序节点的入读-1
    		  {
    			  if(j==((*pp).num-1))continue;
    			  int n=g.graph[j].in_Degree;
    			  if(n!=0)
    			  {
    				  p=&g.graph[j];
    				  for(k=0;k<(g.graph[j].n);k++)             //找一个链表中相匹配的课程
    				  {
    					  p=p->next;
    					  if((*pp).num==p->num){g.graph[j].in_Degree--;}
    				  }
    			  }
    		  }
    	  }
    	  s.Clear_Stack();
    	  if(ss==average)count2++;
    	  cout<<endl;
      }
      if(sum_course==a)cout<<"课程编排成功!"<<endl;
      else cout<<"课程编排失败!"<<endl;
      cout<<"--------------------------------------------------------------------------------"<<endl;
    }
    int main()
    {
     int total_booknum,n;
     cout<<"--------------------------------------------------------------------------------"<<endl;
     cout<<"                           欢迎进入课程编排系统                               "<<endl;
     cout<<"--------------------------------------------------------------------------------"<<endl;
    con:cout<<"                 是否开始进行课程编排，是请按1，退出请按0：";
    	cin>>n;
     while(n==1)
     {
    	 system("cls");
      cout<<"                             该专业开设的课程数:";cin>>total_booknum;
      cout<<"--------------------------------------------------------------------------------"<<endl;
      cout<<"输入每门课的课程信息(文件的读入)";
      ifstream in("课程信息.txt");
      if(!in)
      {
       cerr<<"打开文本-课程信息.txt-有误!"<<endl;
       exit(1);
      }
      Build_Graph Graph;
      Graph.build_Graph(total_booknum);
      int i;Book p;
      for(i=0;i<total_booknum;i++)
      {
    	  in>>p.Book_num>>p.Book_nam>>p.book>>p.study_Score;
    	  Graph.Book_insert(p,i);
      }
      in.close();
      cout<<"要编排的课程信息如下(没有先行课的先行课属性为#):"<<endl;
    	  Graph.display1();                                             //课程信息的输出
    	  Graph.Fu_Zhi();
    	  cout<<"--------------------------------------------------------------------------------"<<endl;
    	  cout<<"课程的邻接表(右边为该门课的先行课)为:"<<endl;
    	  Graph.display2();
    	  Stack T_sort(total_booknum);
    	  Topological_Sort(T_sort,Graph,total_booknum);
    	  goto con;
     }
     if((n!=1)&&(n!=0)){cout<<"输入的数据不符合，请重新输入!"<<endl;goto con;}
     return 0;
    }