关于数据结构Mooc后的每一道答案
基本我都已经给出了详解
希望能对大家有所帮助
收藏一下也是方便大家查找吧
希望大家一起进步！
(c语言)浙大数据结构Mooc作者答案集
原图题目
闲谈
之前在学数据结构的时候感觉学的还可以
现在发现其实真的学计算机厉害的人有很多很多
自己的路还太长 还需要脚踏实地的慢慢走
在CSDN都能看见很多个真的很厉害的人 一直在前进
所以我也要继续前进：）
此题思路
老规矩 一步一步来分析嘛
由于我上道题是用邻接链表做的
现在才知道有多后悔
上次还觉得省了空间
因为确实是省了空间 可是这道题还要你计算
机动时间 相当于你还要再返回来求一次
如果用邻接表来做的话 你还要再设置一个相同的邻接表
而且邻接表的表示比邻接矩阵更复杂
哎
之后只能重新用邻接矩阵来存有没有边
储存每个点的值（结构体存储）
这里是借鉴了一下其他博主的思路
其实这道题我拿着也没怎么看懂题意
尤其是最后一句话更是没看懂
//用结构体来存储相对应的值
//注意出度 入度 出度在返回来计算最晚时间才有用
//入度在计算最早时间有用
typedef struct
{
int earlytime;int lasttime;int indegree;int outdegree;
} Point;Point Points[MAXN];
int checkpoints,activities;
int G[MAXN][MAXN],totaltime = 0;//totaltime是记录工程总时间//初始化图
void InitGraph()
{
int i,j;for(i=1;i<=checkpoints;i++)for(j=1;j<=checkpoints;j++)G[i][j] = 0;return;
}//这里是对点初始化
void InitPoints()
{
int i;for(i=1;i<=checkpoints;i++){
Points[i].earlytime = 0;//这里设置为INF的原因是//最后要进行比较才能记录时间 看到后面的代码你就懂了Points[i].lasttime = INF;Points[i].indegree = 0;Points[i].outdegree = 0;}return;
}//插入数据 活动时间
void InsertActivities()
{
int i,point1,point2,time;for(i=1;i<=activities;i++){
scanf("%d %d %d",&point1,&point2,&time);G[point1][point2] = time;//记录出度入度Points[point1].outdegree++;Points[point2].indegree++;}return;
}//主函数
int main()
{
scanf("%d %d",&checkpoints,&activities);InitGraph();//初始化图InitPoints();//初始化点InsertActivities();//插入数据//下面的函数后面会涉及totaltime = EarlytimeCheck();//记录最早工程总时间if(totaltime == 0)printf("0");else{
printf("%d\n",totaltime);LasttimeCheck();//输出关键任务}return 0;
}
最大工程时间计算
上次的题如果做出来的话
这里无论是用
邻接表 还是邻接矩阵
问题都不是很大
How Long Does It Take (25分)
如果对工程总时间的计算不是很清楚的话
可以重新再去看看上面的博客
先给出计算最大工程的代码（优化版）
int EarlytimeCheck()
{
int i,Queue[MAXN],top = 0,rear = 0,point,maxtime = 0;//先对第一波入度为0的压入队列中for(i=1;i<=checkpoints;i++){
if(!Points[i].indegree){
Points[i].indegree--;Queue[++top] = i;}}//拓扑排序思想while(top != rear){
point = Queue[++rear];for(i=1;i<=checkpoints;i++){
if(G[point][i]){
Points[i].indegree--;//如果入度为0 压入栈中if(!Points[i].indegree) Queue[++top] = i;if(Points[i].earlytime < Points[point].earlytime + G[point][i]){
Points[i].earlytime = Points[point].earlytime + G[point][i];//如果更改后的时间比当前最大时间大 则进行覆盖if(Points[i].earlytime > maxtime)maxtime = Points[i].earlytime;}}}}//如果top位置不是checkpoints的位置 就说明存在回路//有的点没有被访问到if(top != checkpoints)return 0;elsereturn maxtime;
}
关键活动的输出
其实我认为这道题对我来说真没有那么简单。。
但其实思想也没有那么难，有点绕
1、首先因为我们先求出工程最大的时间中
我们顺带求了每个点的earlytime 最早时间
通过我们的最早时间的反推
当前点的最晚时间 减去 活动时间 等于 上个点的最晚时间
如果存在一个点同时被两个点指向 就比如反推时
上图的 4点被 6 和 7 同时反推最晚时间
我们则取6 7 反推最晚时间的最小值即可
2、我们确定关键活动的唯一证据就是
当前点的最早时间和最晚时间相同 且
它所指向的点最早时间和最晚时间也相同
并且 当前点的最晚时间 = 上个点的最晚时间 减去 活动时间的
3、题目的意思
是我们从最刚开始最小的序号作为起点
挨个挨个输出关键活动
而且当起点相同时 我们需要从大到小输出下一个点
算法就变成了
for(i=1;i<=checkpoints;i++){
if(Points[i].lasttime == Points[i].earlytime){
for(j=checkpoints;j>=1;j--){
if(G[i][j] && Points[j].lasttime == Points[j].earlytime && Points[i].lasttime == Points[j].lasttime - G[i][j])printf("%d->%d\n",i,j);}}}
下面给出反推最晚时间代码和 输出代码
void LasttimeCheck()
{
int i,j,Queue[MAXN],top = 0,rear = 0,check,point,maxtime = 0;//先把第一波出度为0的给收入篮子中for(i=1;i<=checkpoints;i++){
//因为第一波出度为0的就是工程结束了//所以全部最晚时间赋值为工程总时间if(!Points[i].outdegree){
Queue[++top] = i;Points[i].lasttime = totaltime;Points[i].outdegree--;}}//把所有的点最晚时间求了出来while(top != rear){
point = Queue[++rear];for(i=1;i<=checkpoints;i++){
if(G[i][point]){
Points[i].outdegree--;if(!Points[i].outdegree) Queue[++top] = i;if(Points[point].lasttime - G[i][point] < Points[i].lasttime)Points[i].lasttime = Points[point].lasttime - G[i][point];}}}//输出关键路径for(i=1;i<=checkpoints;i++){
if(Points[i].lasttime == Points[i].earlytime){
//注意这里是从大到小for(j=checkpoints;j>=1;j--){
if(G[i][j] && Points[j].lasttime == Points[j].earlytime && Points[i].lasttime == Points[j].lasttime - G[i][j])printf("%d->%d\n",i,j);}}}return;
}
代码实现
#include <stdio.h>
#define MAXN 100
#define INF 99999999int checkpoints,activities;
int G[MAXN][MAXN],totaltime = 0;typedef struct
{
int earlytime;int lasttime;int indegree;int outdegree;
} Point;Point Points[MAXN];void InitGraph()
{
int i,j;for(i=1;i<=checkpoints;i++)for(j=1;j<=checkpoints;j++)G[i][j] = 0;return;
}void InitPoints()
{
int i;for(i=1;i<=checkpoints;i++){
Points[i].earlytime = 0;Points[i].lasttime = INF;Points[i].indegree = 0;Points[i].outdegree = 0;}return;
}void InsertActivities()
{
int i,point1,point2,time;for(i=1;i<=activities;i++){
scanf("%d %d %d",&point1,&point2,&time);G[point1][point2] = time;Points[point1].outdegree++;Points[point2].indegree++;}return;
}int EarlytimeCheck()
{
int i,Queue[MAXN],top = 0,rear = 0,point,maxtime = 0;for(i=1;i<=checkpoints;i++){
if(!Points[i].indegree){
Points[i].indegree--;Queue[++top] = i;}}while(top != rear){
point = Queue[++rear];for(i=1;i<=checkpoints;i++){
if(G[point][i]){
Points[i].indegree--;if(!Points[i].indegree) Queue[++top] = i;if(Points[i].earlytime < Points[point].earlytime + G[point][i]){
Points[i].earlytime = Points[point].earlytime + G[point][i];if(Points[i].earlytime > maxtime)maxtime = Points[i].earlytime;}}}}if(top != checkpoints)return 0;elsereturn maxtime;
}void LasttimeCheck()
{
int i,j,Queue[MAXN],top = 0,rear = 0,check,point,maxtime = 0;for(i=1;i<=checkpoints;i++){
if(!Points[i].outdegree){
Queue[++top] = i;Points[i].lasttime = totaltime;Points[i].outdegree--;}}while(top != rear){
point = Queue[++rear];for(i=1;i<=checkpoints;i++){
if(G[i][point]){
Points[i].outdegree--;if(!Points[i].outdegree) Queue[++top] = i;//这里就是为什么INF要设置的原因//思考一下就懂了嗷if(Points[point].lasttime - G[i][point] < Points[i].lasttime)Points[i].lasttime = Points[point].lasttime - G[i][point];}}}for(i=1;i<=checkpoints;i++){
if(Points[i].lasttime == Points[i].earlytime){
for(j=checkpoints;j>=1;j--){
if(G[i][j] && Points[j].lasttime == Points[j].earlytime && Points[i].lasttime == Points[j].lasttime - G[i][j])printf("%d->%d\n",i,j);}}}return;
}int main()
{
scanf("%d %d",&checkpoints,&activities);InitGraph();InitPoints();InsertActivities();totaltime = EarlytimeCheck();if(totaltime == 0)printf("0");else{
printf("%d\n",totaltime);LasttimeCheck();}return 0;
}
结束语
其实做这道题的时候
主要没有理解题目的意思
就导致 确实算法思路有点难的想
但是在借鉴了他人优秀的代码后
还是一步一步做出来了
还是慢慢积累吧
