18 计专

数据结构

1、自由数（无环连通图），T = (V,E)的直径是书中所有顶点之间最短路径的最大值，设计一个一个时间复杂度尽可能第的算法求T的直径

思路：

1. 先从任意一个顶点找到该顶点最短路径中最长的一个，这个点为直径的某个端点
2. 然后再从这个顶点出发，再进行一次BFS,求出距离该顶点最短路径最长的一个，该顶点为直径的另一端
3. 返回两个顶点的路径长度，就是自由树的直径

代码：

typedef struct ArcNode{		//边节点 
	int adjvex;
	struct ArcNode *next;
}ArcNode;
 
typedef struct VNode{		//顶点节点 
	int data;
	struct ArcNode *firstarc;
}VNode;

typedef struct AGraph{		//领接表 
	VNode adjlist[maxsize];
	int vexnum, edgenum;
}AGraph; 

int MaxLenBFS(AGraph *G, int v, int dist[]){
	int visited[maxsize] = {0};
	int queue[maxsize];
	int front = -1, rear = -1,i,k,temp,max=0;
	ArcNode *p = G->adjlist[v].firstarc;
	
	for(i = 0; i < G->vexnum; i++){
		dist[i] = -1;
	}
	
	queue[++rear] = v;
	visited[v] = 1;
	dist[v] = 0;
	
	while(rear != front){
		k = queue[++front];
		p = G->adjlist[k].firstarc;
		while(p!=NULL){
			temp = p->adjvex;
			if(visited[temp]==0){
				queue[++rear] = temp;
				visited[temp] = 1;
				dist[temp] = dist[k] + 1; 
 			}
 			p = p->next;
		}
	}
	
	for(i=0; i < G->vexnum; i++){
		if(dist[i]>dist[max]){
			max = i;
		}
	} 
	return max;			//返回端点 
} 

int Diameter(AGraph *G){
	int dist[maxsize];
	int first = MaxLenBFS(G,0,dist);
	int last = MaxLenBFS(G,first,dist);
	printf("直径为：%d",dist[last]); 
	return dist[last];					//返回直径长度 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

程序设计

1、已知数组ax[100]和ay[100]中分别保存了平面上100个点的横坐标和纵坐标，假定其中任意三个点均可以构成三角形
编写代码，求100个点组成的所有三角形中面积最大三角形以及面积，输出面积最大的三角形的各顶点坐标以及面积值，满足条件的面积可能有多组

思路：

1. 需要一个函数求两点之间的长度
2. 需要一个函数求三条边的所围成三角形面积
3. 需要一个三维数组保存多个最大值面积
4. 需要三重for循环找到三个不一样的顶点
5. 需要一个max保存当前的最大值

代码：

double dist(int x1, int y1, int x2, int y2){		//求两点之间的距离 
	return (double)sqrt((x1-x2)*(x1-x2)+(y2-y1)*(y2-y1));
} 

double area(int x1, int x2, int x3, int y1, int y2, int y3){		//求三条边所围成的面积 
	double a,b,c,s;
	a = dist(x1,y1,x2,y2);
	b = dist(x1,y1,x3,y3);
	c = dist(x2,y2,x3,y3);
	s = (a+b+c)/2;
	return (double)sqrt(s*(s-a)*(s-b)*(s-c));
}

void maxtri(int ax[100], int ay[100]){
	int i,j,k;
	int maxt[100][3][2];			//三维数组保存可能的多个最大值 
	int size=0;						//size是当前面积最大值的个数 
	double max=0;					//max是当前面积最大值 
	double S;
	for(i=0; i <= 97; i++){
		for(j=i+1; j <= 98; j++){
			for(k=j+1; k <= 99; k++){		//三重for循环找到三个不同顶点 
				S = area(ax[i],ax[j],ax[k],ay[i],ay[j],ay[k]);
				if(S>=max){			//面积变大或者相等需要更新maxt数组 
					if(S>max){
						size = 0;
					}
					max = S;
					maxt[size][0][0] = ax[i];
					maxt[size][0][1] = ay[i];
					maxt[size][1][0] = ax[j];
					maxt[size][1][1] = ay[j];
					maxt[size][2][0] = ax[k];
					maxt[size][2][1] = ay[k];
					size++;
				}
			}
		}
	}
	printf("最大面积为%f\n",max);
	for(i = 0; i < size; i++){
		for(j =0;j < 3; j++){		//三重for循环输出当前最大值，以及对应的下标 
			for(k=0; k < 2; k++){
				printf("%d  ",maxt[i][j][k]);
			}
			printf("\n");
		}
		printf("\n\n");
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50