文章目录
〇、前言
这两周开始跟着【MOOC-浙江大学-陈越、何钦铭-数据结构】进行数据结构与算法的学习，特此记录复习一下，虽然记不住，但是一直记一直记一直记，成为复读机就好了。
一、复习
这周主要是复习，同时有几个题，今天终于找到了自己数据结构学不懂的问题了，一个大佬说的一句话，让我恍然大悟的感觉。
其实就是C++或者C语言学的不好，基础太差，具体来说，就是代码量不够，导致没法自己解决问题，从而导致了写不出来代码，所以准备刷一下PTA。
二、哈利波特的考试
三、课后题
1、07-图4 哈利·波特的考试 (25分)
输入样例:
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
");
return;
}
if ( MinDist > MaxDist ) { /* 找到最长距离更小的动物*/
MinDist = MaxDist; Animal = i+1; /* 更新距离，记录编号*/
}
}
printf("%d %d
", 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;
}
2、07-图5 Saving James Bond - Hard Version (30分)
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:
0
#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
",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
");
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
");
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
",MinDist+1);
printf("%d %d
",C[Start].X,C[Start].Y);
Print(Start,End);
return 0;
}
3、07-图6 旅游规划 (25分)
输入样例:
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;
}
总结
刷题刷题刷题！！！
数据结构，陈越等，浙大课程原版的书，需要的可以去公众号自取。
如果想要更多的资源，欢迎关注 @我是管小亮，文字强迫症MAX~
回复【数据结构】即可获取我为你准备的大礼！！！
想看更多文（段）章（子），欢迎关注微信公众号「程序员管小亮」~