【2020-MOOC-浙江大学-陈越、何钦铭-数据结构】图（第七周的笔记和编程作业）

爱被打了一巴掌 2023-07-24 02:26 0阅读 0赞

### 文章目录 ###

*  〇、前言
 *  一、复习
 *  二、哈利波特的考试
 *  三、课后题
 *   *   *  1、07-图4 哈利·波特的考试 (25分)
         *  2、07-图5 Saving James Bond - Hard Version (30分)
         *  3、07-图6 旅游规划 (25分)
 *  总结

# 〇、前言 #

这两周开始跟着【MOOC-浙江大学-陈越、何钦铭-数据结构】进行数据结构与算法的学习，特此记录复习一下，虽然记不住，但是一直记一直记一直记，成为复读机就好了。  
![在这里插入图片描述][20200314162146148.png_pic_center]

# 一、复习 #

这周主要是复习，同时有几个题，今天终于找到了自己数据结构学不懂的问题了，一个大佬说的一句话，让我恍然大悟的感觉。

其实就是C++或者C语言学的不好，基础太差，具体来说，就是代码量不够，导致没法自己解决问题，从而导致了写不出来代码，所以准备刷一下PTA。

# 二、哈利波特的考试 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]

# 三、课后题 #

![在这里插入图片描述][20200408182218350.png]

### 1、07-图4 哈利·波特的考试 (25分) ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]  
**输入样例:**

6 11  
3 4 70  
1 2 1  
5 4 50  
2 6 50  
5 6 60  
1 3 70  
4 6 60  
3 6 80  
5 1 100  
2 4 60  
5 2 80

**输出样例:**

4 70

--------------------

#include <stdio.h>
    #include <stdlib.h>
    
    #define MaxVertexNum 100 /* 最大顶点数设为100 */
    #define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/
    
    typedef int Vertex; /* 用顶点下标表示顶点,为整型*/
    typedef int WeightType; /* 边的权值设为整型*/
    /* 边的定义*/
    typedef struct ENode *PtrToENode;
    struct ENode{ 
    	Vertex V1, V2; /* 有向边<V1, V2> */
    	WeightType Weight; /* 权重*/
    };
    typedef PtrToENode Edge;
    /* 图结点的定义*/
    typedef struct GNode *PtrToGNode;
    struct GNode{ 
    	int Nv; /* 顶点数*/
    	int Ne; /* 边数*/
    	WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵*/
    };
    typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型*/
    
    void FindAnimal( MGraph Graph ){ 
    	WeightType D[MaxVertexNum][MaxVertexNum], MaxDist, MinDist;
    	Vertex Animal, i;
    	
    	Floyd( Graph, D );
    	
    	MinDist = INFINITY;
    	for ( i=0; i<Graph->Nv; i++ ) { 
    		MaxDist = FindMaxDist( D, i, Graph->Nv );
    		if ( MaxDist == INFINITY ) {  /* 说明有从i无法变出的动物*/
    			printf("0\n");
    			return;
    		}
    		if ( MinDist > MaxDist ) {  /* 找到最长距离更小的动物*/
    			MinDist = MaxDist; Animal = i+1; /* 更新距离，记录编号*/
    		}
    	}
    	printf("%d %d\n", Animal, MinDist);
    }
    
    WeightType FindMaxDist( WeightType D[][MaxVertexNum],Vertex i, int N ){ 
    	WeightType MaxDist;
    	Vertex j;
    	MaxDist = 0;
    	for( j=0; j<N; j++ ) /* 找出i到其他动物j的最长距离*/
    		if ( i!=j && D[i][j]>MaxDist )
    			MaxDist = D[i][j];
    	return MaxDist;
    }
    
    MGraph CreateGraph( int VertexNum ){ 
    	/* 初始化一个有VertexNum个顶点但没有边的图*/
    	Vertex V, W;
    	MGraph Graph;
    	Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图*/
    	Graph->Nv = VertexNum;
    	Graph->Ne = 0;
    	/* 初始化邻接矩阵*/
    	/* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
    	for (V=0; V<Graph->Nv; V++)
    		for (W=0; W<Graph->Nv; W++)
    			Graph->G[V][W] = INFINITY;
    	return Graph;
    }
    
    void InsertEdge( MGraph Graph, Edge E ){ 
    	/* 插入边<V1, V2> */
    	Graph->G[E->V1][E->V2] = E->Weight;
    	/* 若是无向图，还要插入边<V2, V1> */
    	Graph->G[E->V2][E->V1] = E->Weight;
    }
    
    MGraph BuildGraph(){ 
    	MGraph Graph;
    	Edge E;
    	int Nv, i;
    	scanf("%d", &Nv); /* 读入顶点个数*/
    	Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图*/
    	scanf("%d", &(Graph->Ne)); /* 读入边数*/
    	if ( Graph->Ne != 0 ) {  /* 如果有边*/
    		E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点*/
    		/* 读入边，格式为"起点终点权重"，插入邻接矩阵*/
    		for (i=0; i<Graph->Ne; i++) { 
    			scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
    			E->V1--; E->V2--;
    			/* 注意：如果权重不是整型，Weight的读入格式要改*/
    			InsertEdge( Graph, E );
    		}
    	}
    	return Graph;
    }
    
    void Floyd( MGraph Graph, WeightType D[][MaxVertexNum] ){  
    	Vertex i, j, k;
    	/* 初始化*/
    	for ( i=0; i<Graph->Nv; i++ )
    		for( j=0; j<Graph->Nv; j++ ) { 
    			D[i][j] = Graph->G[i][j];
    		}
    	for( k=0; k<Graph->Nv; k++ )
    		for( i=0; i<Graph->Nv; i++ )
    			for( j=0; j<Graph->Nv; j++ )
    				if( D[i][k] + D[k][j] < D[i][j] ) { 
    					D[i][j] = D[i][k] + D[k][j];
    	}
    }
    
    int main(){ 
    	MGraph G = BuildGraph();
    	FindAnimal( G );
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]

--------------------

### 2、07-图5 Saving James Bond - Hard Version (30分) ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]  
**Sample Input 1:**

17 15  
10 -21  
10 21  
\-40 10  
30 -50  
20 40  
35 10  
0 -10  
\-25 22  
40 -40  
\-30 30  
\-10 22  
0 11  
25 21  
25 10  
10 10  
10 35  
\-30 10

**Sample Output 1:**

4  
0 11  
10 21  
10 35

**Sample Input 2:**

4 13  
\-12 12  
12 12  
\-12 -12  
12 -12

**Sample Output 2:**

--------------------

#include<stdio.h>
    #include<stdbool.h>
    #include<math.h>
    #define MaxVertexNum 101
    #define INFINITE 65535
    typedef int Vertex;
    struct Corcodile
    { 
    	int X,Y;
    };
    struct Corcodile C[200];
    int G[200][200];
    int Visitied[200];
    int dis[200][200];
    int path[200][200];
    int Min(int a,int b)
    { 
    	return (a<b?a:b);
    }
    bool JudgeQulified(Vertex V)
    { 
    	double x,y;
    	x=C[V].X; y=C[V].Y;
    	double distance = sqrt(pow(x,2)+pow(y,2));
    	if(distance<=7.5||x==50||x==-50||y==50||y==-50)
    		return false;
    	else
    		return true;
    }
    bool JumpToBank(Vertex V,int D)
    { 
    	int x,y;
    	int dis;
    	x = C[V].X; y = C[V].Y;
    	if(x>=0&&y>=0)
    		dis = Min(50-x,50-y);
    	else if(x<=0&&y>=0)
    		dis = Min(50+x,50-y);
    	else if(x<=0&&y<=0)
    		dis = Min(50+x,50+y);
    	else if(x>=0&&y<=0)
    		dis = Min(50-x,50+y);
    	if(D>=dis) return true;
    	else return false;
    }
    bool JumpToFirst(Vertex V,int D)
    { 
    	double x,y;
    	x=C[V].X; y=C[V].Y;
    	double dis = sqrt(pow(x,2)+pow(y,2));
    	if(D+7.5>=dis) return true;
    	else return false;
    }
    double CalFirst(Vertex V)
    { 
    	double x,y;
    	x=C[V].X; y=C[V].Y;
    	double dis = sqrt(pow(x,2)+pow(y,2));
    	return dis;
    }
    void Floyd(int N)
    { 
    	int i,j,k;
    	for(i=0;i<=N+1;i++)
    		for(j=0;j<=N+1;j++)
    		{ 
    			dis[i][j]=G[i][j];
    			path[i][j]=-1;
    		}
    	for(k=0;k<=N+1;k++)
    		for(i=0;i<=N+1;i++)
    			for(j=0;j<=N+1;j++)
    			{ 
    				if(dis[i][k]+dis[k][j]<dis[i][j])
    				{ 
    					dis[i][j]=dis[i][k]+dis[k][j];
    					path[i][j]=k;
    				}
    			}
    }
    void Print(Vertex Start,Vertex End)
    { 
    	if(path[Start][End]==-1) return;
    	else
    	{ 
    		Vertex k = path[Start][End];
    		Print(Start,k);
    		printf("%d %d\n",C[k].X,C[k].Y);
    		Print(k,End);
    	}
    }
    int main()
    { 
    	Vertex V;
    	int N;
    	int D;
    	int i,j;
    	double distance;
    	scanf("%d %d",&N,&D);
    	if(D>=42.5)//如果能一步上岸的话
    	{ 
    		printf("1\n");
    		return 0;
    	}
    	for(i=0;i<=N+1;i++)
    		for(j=0;j<=N+1;j++)
    		{ 
    			G[i][j]=INFINITE;
    			if(i==j) G[i][j]=0;
    		}
    	for(V=1;V<=N;V++)
    	{ 
    		scanf("%d %d",&C[V].X,&C[V].Y);
    		double x=C[V].X; double y=C[V].Y;
    		distance = sqrt(pow(x,2)+pow(y,2));
    		if(JudgeQulified(V))
    		{ 
    			if(7.5+D*1.0>=distance)
    			{ 
    				G[0][V]=1;
    				G[V][0]=1;
    			}
    			if(JumpToBank(V,D))
    			{ 
    				G[V][N+1]=1;
    				G[N+1][V]=1;
    			}
    		
    		}
    	}
    	for(i=1;i<N;i++)
    	{ 
    		if(JudgeQulified(i))
    		{ 
    			for(j=i+1;j<=N;j++)
    			{ 
    				if(JudgeQulified(j))
    				{ 
    					double x1,x2,y1,y2;
    					x1=C[i].X; y1=C[i].Y;
    					x2=C[j].X; y2=C[j].Y;
    					distance = sqrt(pow(x1-x2,2)+pow(y1-y2,2));
    					if(distance<=D)
    					{ 
    						G[i][j]=1;
    						G[j][i]=1;
    					}
    				}
    			}
    		}
    	}
    	Floyd(N);
    	if(dis[0][N+1]>=INFINITE)
    	{ 
    		printf("0\n");
    		return 0;
    	}
    	int Num=-1;Vertex First[200];
    	for(V=1;V<=N;V++)
    	{ 
    		if(JudgeQulified(V)&&JumpToFirst(V,D))
    			{ 
    			    Num++;
    				First[Num]=V;
    			}
    	}
    	Vertex tmpV;
    	for(i=0;i<Num;i++)//把第一跳的距离进行排序
    		for(j=i+1;j<=Num;j++)
    		{ 
    			if(CalFirst(First[j])<CalFirst(First[i]))
    			{ 
    				tmpV = First[i];
    				First[i] = First[j];
    				First[j] = tmpV;
    			}
    		}
    	int MinDist=65535; Vertex Start,End;
    	for(i=0;i<=Num;i++)
    	{ 
    		if(dis[First[i]][N+1]<MinDist)
    		{ 
    			MinDist=dis[First[i]][N+1];
    			Start = First[i];
    			End = N+1;
    		}
    	}
    	printf("%d\n",MinDist+1);
    	printf("%d %d\n",C[Start].X,C[Start].Y);
    	Print(Start,End);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 4]

--------------------

### 3、07-图6 旅游规划 (25分) ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 5]  
**输入样例:**

4 5 0 3  
0 1 1 20  
1 3 2 30  
0 3 4 10  
0 2 2 20  
2 3 1 20

**输出样例:**

3 40

--------------------

#include <stdio.h>
    #define INFINITY 100000000
    #define ERROR -1
    
    typedef int Vertex;
    struct Gnode{ 
    	int weight;
    	int expenses;
    };
    struct Gnode G[500][500];
    int Nv, Ne;//边数控制输入行数,顶点数控制for循环范围
    int strpos, despos;//起点，终点
    int visited[500] = {  0 };
    int dist[500],cost[500];//最短路径以及最小花费
    
    void buildgraph(){ 
    	int v1, v2, w,ex;
    	int i,j;
    	//初始化图
    	for (i = 0; i < Nv; i++){ 
    		for (j = 0; j < Nv; j++){ 
    			G[i][j].weight = INFINITY;
    			G[i][j].expenses = INFINITY;
    		}
    		G[i][i].weight = 0;
    		G[i][i].expenses = 0;
    		dist[i] = INFINITY;
    		cost[i] = INFINITY;
    	}
    	for (i = 0; i < Ne; i++){ 
    		scanf("%d %d %d %d",&v1,&v2,&w,&ex);
    		G[v1][v2].weight = w;
    		G[v1][v2].expenses = ex;
    		G[v2][v1].weight = w;
    		G[v2][v1].expenses = ex;
    	}
    }
    
    /* 邻接矩阵存储 - 有权图的单源最短路算法 */
     
    Vertex FindMinDist(){ 
    	/* 返回未被收录顶点中dist最小者 */
        int MinV, V;
        int MinDist = INFINITY;
     
        for (V=0; V<Nv; V++){ 
            if (!visited[V] && dist[V]<MinDist) { 
                /* 若V未被收录，且dist[V]更小 */
                MinDist = dist[V]; /* 更新最小距离 */
                MinV = V; /* 更新对应顶点 */
            }
        }
        if (MinDist < INFINITY) /* 若找到最小dist */
            return MinV; /* 返回对应的顶点下标 */
        else 
    		return ERROR;  /* 若这样的顶点不存在，返回错误标记 */
    }
     
    int Dijkstra(){ 
        Vertex V, W;
     
        /* 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示 */
        for ( V=0; V<Nv; V++ ){ 
            dist[V] = G[strpos][V].weight;
            cost[V] = G[strpos][V].expenses;
        }
        /* 先将起点收入集合 */
        dist[strpos] = cost[strpos] = 0;
        visited[strpos] = 1;//对起点进行初始化
     
        while (1){ 
            /* V = 未被收录顶点中dist最小者 */
            V = FindMinDist();
            if ( V==ERROR ) /* 若这样的V不存在 */
                break;      /* 算法结束 */
            visited[V] = 1;  /* 收录V */
            for( W=0; W<Nv; W++ ) /* 对图中的每个顶点W */
                /* 若W是V的邻接点并且未被收录 */
                if ( !visited[W] && G[V][W].weight<INFINITY ) { 
                    if (dist[V] + G[V][W].weight < dist[W]){ 
    					dist[W] = dist[V] + G[V][W].weight;
    					cost[W] = cost[V] + G[V][W].expenses;
    				}
    				else if ((dist[V] + G[V][W].weight == dist[W])&&(cost[V]+G[V][W].expenses<cost[W]))
    					cost[W] = cost[V] + G[V][W].expenses;
                }
        } /* while结束*/
        return 1; /* 算法执行完毕，返回正确标记 */
    }
    
    int main(){ 
    	scanf("%d %d %d %d",&Nv,&Ne,&strpos,&despos);
    	buildgraph();
    	Dijkstra();
    	printf("%d %d",dist[despos],cost[despos]);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 6]

# 总结 #

刷题刷题刷题！！！

数据结构，陈越等，浙大课程原版的书，需要的可以去公众号自取。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center]  
***如果想要更多的资源，欢迎关注 @我是管小亮，文字强迫症MAX~***

***回复【数据结构】即可获取我为你准备的大礼！！！***

***想看更多文（段）章（子），欢迎关注微信公众号「程序员管小亮」~***

[20200314162146148.png_pic_center]: /images/20230528/b395a296a1444001b9cce890ec35bf70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]: /images/20230528/13782f8f219c447e9077a97a3375f345.png
[20200408182218350.png]: /images/20230528/ba8d24e8ae20499ba477e788b1529bf2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]: /images/20230528/75fe3380900c4c1b9e04aa6753fd611b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]: /images/20230528/41195780a39b47acb8aeb6745ff2d2f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]: /images/20230528/cad76095e61b4a48aa1c829b603d8876.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 4]: /images/20230528/1702fe0c204647edaff8ed3048bb0cb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 5]: /images/20230528/41fb4496e26644c2894b85ff8e83d1ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 6]: /images/20230528/130dcf8a04284d5aa7fb7794349f0d6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/6b314add2c49479aa0cccdbd0b477397.png