注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

教学计划编制——数据结构--拓扑排序应用--有向无环图  

2014-12-01 21:48:47|  分类: 数据结构---严老 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

(一)实验目的:掌握图的基本操作

(二)基本要求:实现必要的图的基本操作,编写教学计划编制程序,输出正确结果。

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

(1)输入参数包括:学期总数,一学期的学分上限,每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。

(2)允许用户指定下列两种编排策略之一:一是使学生在各学期中的学习负担尽量均匀;二是使课程尽可能地集中在前几个学期中。

(3)若根据给定的条件问题无解,则报告适当的信息;否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。

(4)测试数据:学期总数6;学分上限10;共开设12门课,课程号从C1-C12,学分顺序为 2,3,4,3,2,3,4,4,7,5,2,3。先修关系见教材(严蔚敏-数据结构-C语言版)图7.26.但程序不能仅局限于该测试数据。

二、要点分析

题目中涉及的主要知识点有:

(1)栈。用到有关栈的操作有初始化栈、判断栈是否为空、入栈和出栈。其中栈主要用来存放入度为零的顶点,即当前无先修关系可以编排的课程。

(2)图。用到有关图的操作有创建图、统计图中各顶点的入度。利用邻接表作为有向图的存储结构,且在头结点中增加一个存放顶点入度的数组(indegree)。入度为零的顶点即为没有前驱的顶点,删除顶点及以它为尾的弧的操作,则可换以弧头顶点入度减一来实现。

(3)拓扑排序。

  (a)在有向图中选一个没有前驱的顶点且输出之。

  (b)从图中删除该顶点和所有以它为尾的弧。

重复上述两步,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止,后一种情况则说明有向图中存在环。

1.图的定义的结构——邻接表

"GraphStruct.h"

#define Max_Num 100
struct ArcNode
{
int Adjarc;
ArcNode *nextarc;
};
typedef struct VexNode
{
char name[25];
int CourseId;
int State;
int degree;
int Credit;
ArcNode *firstarc;
}Adjlist[Max_Num];
struct AlGraph
{
Adjlist Vertexs;
int ArcNum;
int VexNum;
};

2.对于拓扑排序的应用;

@1.寻找度为1的点;

@2.删掉度为一的点(其实没有),相应的度增减。

@3直到最后的时候。

#include"GraphStruct.h"
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<vector>
#define USEFILE 1
void CreateGraph(AlGraph &G)
{
printf("请输入总的课程的数目");
scanf("%d",&G.VexNum);
int i;
FILE *fp,*fp1;
fp=fopen("test.txt","r");
fp1=fopen("test1.txt","r");
if(fp1==NULL)
printf("Cant");
#ifdef USEFILE
printf("已经输入%d个课程的课程名,课程号,课程的学分\n",G.VexNum);
for(int i=1;i<=G.VexNum;i++)
{
fscanf(fp,"%s",G.Vertexs[i].name);
fscanf(fp,"%d",&G.Vertexs[i].CourseId);
fscanf(fp,"%d",&G.Vertexs[i].Credit);
G.Vertexs[i].degree=0;
G.Vertexs[i].firstarc=NULL;
G.Vertexs[i].State=0;
}
fclose(fp);
printf("请输入课程的先修关系的总数");
scanf("%d",&G.ArcNum);
//printf("输入课程ID的先修的关系,用逗号隔开\n");
//printf("列如:1,2\n");
int x,y;
ArcNode *p;
printf("已经输入%d存在先修关系的两个课程的序号:\n",G.ArcNum);
for(i=1;i<=G.ArcNum;i++)
{
fscanf(fp1,"%d",&x);
fscanf(fp1,"%d",&y);
p=(ArcNode *)malloc(sizeof(ArcNode));
if(p==NULL)
{
printf("分配错误");
}

p->Adjarc=y;
p->nextarc=G.Vertexs[x].firstarc;
G.Vertexs[x].firstarc=p;
}
fclose(fp1);

#else
for(int i=1;i<=G.VexNum;i++)
{
printf("请输入%d个课程的课程名\n",i);
scanf("%s",G.Vertexs[i].name);
printf("输入课程号\n");
scanf("%d",&G.Vertexs[i].CourseId);
printf("输入该课程的学分\n");
scanf("%d",&G.Vertexs[i].Credit);
G.Vertexs[i].degree=0;
G.Vertexs[i].firstarc=NULL;
G.Vertexs[i].State=0;
}
printf("请输入课程的先修关系的总数");
scanf("%d",&G.ArcNum);
printf("输入课程ID的先修的关系,用逗号隔开\n");
printf("列如:1,2\n");
int x,y;
ArcNode *p;
for(i=1;i<=G.ArcNum;i++)
{
printf("请输入存在先修关系的两个课程的序号:\n");
scanf("%d,%d",&x,&y);
while(x<0||y<0||x>G.VexNum||y>G.VexNum)
{
printf("对不起您的输入有误,请重新输入");
scanf("%d,%d",&x,&y);
}
p=(ArcNode *)malloc(sizeof(ArcNode));
if(p==NULL)
{
printf("分配错误");
}

p->Adjarc=y;
p->nextarc=G.Vertexs[x].firstarc;
G.Vertexs[x].firstarc=p;
}
#endif
}
void PlayAdjVex(AlGraph G)
{
printf("已经建立好的邻接表为如下\n");
ArcNode *p;
for(int i=1;i<=G.VexNum;i++)
{
printf("%s:",G.Vertexs[i].name);
for(p=G.Vertexs[i].firstarc;p!=NULL;p=p->nextarc)
{
printf("%s->",G.Vertexs[p->Adjarc].name);
}
printf("NULL\n");
}
}

void FindDegree(AlGraph G,int Degree[])
{
int i;
for(i=1;i<=G.VexNum;i++)
{
Degree[i]=0;
}
ArcNode *p;
for(i=1;i<=G.VexNum;i++)
{
p=G.Vertexs[i].firstarc;
while(p!=NULL)
{
Degree[p->Adjarc]++;
p=p->nextarc;
}
}
}
void SortBySpeed(AlGraph G,int TermNum,int TopCredit)
{
ArcNode *p;
std::stack<int> s;
int OneTermCredit=0;
int ALLCourseCount=0;
int TermCount=0;
int Degree[Max_Num];
FindDegree(G,Degree);
for(int i=1;i<=G.VexNum;i++)
{
G.Vertexs[i].degree=Degree[i];
}

while(ALLCourseCount<G.VexNum&&TermCount< TermNum)
{
OneTermCredit=0;
for(int i=1;i<=G.VexNum;i++)
{
if(G.Vertexs[i].degree==0&&G.Vertexs[i].State==0)
{
s.push(i);
G.Vertexs[i].State=1;
}
}
if(!s.empty()&&OneTermCredit<=TopCredit)
{
TermCount++;
printf("第%d学期的课程为\n",TermCount);
while(!s.empty()&&OneTermCredit<=TopCredit)
{
int now=s.top();
s.pop();
OneTermCredit+=G.Vertexs[now].Credit;
p=G.Vertexs[now].firstarc;
if(OneTermCredit<=TopCredit)
{
ALLCourseCount++;
printf(" %s ",G.Vertexs[now].name);
for(;p!=NULL;p=p->nextarc)
{
G.Vertexs[p->Adjarc].degree--;
}
}
else
{
s.push(now);//超出了边界,下一学期继续修炼;
}
}
}
printf("\n");

}
if(ALLCourseCount<G.VexNum)
{
printf("分配课程的计划失败\n");
}
else
{
printf("分配课程的计划成功\n");
}
}

void SortByCourse(AlGraph G,int TermNum,int TopCredit)
{
ArcNode *p;
std::stack<int> s;
int OneTermCredit=0;
int OneTermCourse=0;
int ALLCourseCount=0;
int TermCount=0;
int Degree[Max_Num];
int MaxCourse=G.VexNum/TermNum+1;
FindDegree(G,Degree);
for(int i=1;i<=G.VexNum;i++)
{
G.Vertexs[i].degree=Degree[i];
}

while(ALLCourseCount<G.VexNum&&TermCount< TermNum)
{
OneTermCredit=0;
OneTermCourse=0;
for(int i=1;i<=G.VexNum;i++)
{
if(G.Vertexs[i].degree==0&&G.Vertexs[i].State==0)
{
s.push(i);
G.Vertexs[i].State=1;

}
}
if(!s.empty()&&OneTermCredit<TopCredit&&OneTermCourse<MaxCourse)
{
TermCount++;
printf("第%d学期的课程为\n",TermCount);

while(!s.empty()&&OneTermCredit<TopCredit&&OneTermCourse<MaxCourse)
{
int now=s.top();
s.pop();
OneTermCredit=OneTermCredit+G.Vertexs[now].Credit;
OneTermCourse++;
if(OneTermCredit<=TopCredit&&OneTermCourse<=MaxCourse)
{
ALLCourseCount++;
printf(" %s ",G.Vertexs[now].name);

for(p=G.Vertexs[now].firstarc;p!=NULL;p=p->nextarc)
{
if(p)
{
int k=p->Adjarc;
G.Vertexs[k].degree--;
}//这里为什么没有直接把度为0 的结点加入到我们的栈中去呢?主要是,我们有的先修的课程都还没有修完,这样会造成不好的影响!必须把所有度为0的都修完了之后才可以继续的进行我们的课程,即,
当栈为空的时候,才可以继续的进行下学期的课程
}
}
else
{
s.push(now);
}

}
printf("\n");
}

}
if(ALLCourseCount<G.VexNum)
{
printf("分配课程的计划失败\n");
}
else
{
printf("分配课程的计划成功\n");
}
}

text  放置我们的课程的名字,id,学分

程序设计基础 1 2
离散数学 2 3
数据结构 3 4
汇编语言 4 3
语言的设计和分析 5 2
计算机原理 6 3
编译原理 7 4
操作系统 8 4
高等数学 9 7
线性代数 10 5
普通物理 11 2
数值分析 12 3

test1  先修->后修

只有先把度为1的节点的修完了之后,才可以进行下一学期的课程,这个是一个关键的地方!

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



main函数

#include "stdafx.h"
#include"function.h"
void play()
{
printf("**********************\n");
printf("* 请选择编排策略 *\n");
printf("* 1.集中学分排列 *\n");
printf("* 2.均匀的分布 *\n");
printf("* 0.退出 *\n");
printf("**********************\n");
}

int main()
{
AlGraph G;
CreateGraph(G);
PlayAdjVex(G);
int numterm;//学期总数
int uplcredit; //一个学期的学分上限
int Choice;
printf("请输入学期总数:\n");
scanf("%d",&numterm);
printf("请输入一个学期的学分上限:\n");
scanf("%d",&uplcredit);
play();
scanf("%d",&Choice);
while(Choice!=0)
{
switch(Choice)
{
case 1:
SortBySpeed(G,numterm,uplcredit);
break;
case 2:
SortByCourse(G,numterm,uplcredit);
break;
default:
exit(1);

}
play();
scanf("%d",&Choice);

}

}

教学计划编制——数据结构--拓扑排序应用--有向无环图 - 983433479 -  告别迷茫
 
教学计划编制——数据结构--拓扑排序应用--有向无环图 - 983433479 -  告别迷茫
 
  评论这张
 
阅读(16)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017