15 软专

数据结构

第一题 判断是是否为图

请设计一个算法判断无向图G是否为一棵树，若是树，返回1，否则返回0

思路

• 判断一个图是否为树需要两个条件

  • 只有一个连通图，且该连通图包含所有顶点
  • 边数与顶点数构成关系 边数等于顶点数-1 anum = vnum-1

• 实现：

  • 深度优先遍历，多添加两个参数，遍历整个图的所有顶点以及边
  • 边的遍历需要注意一下，只要有这条边便遍历，这里是唯一和深度优先遍历模板有较大差别的地方
  • 此后再判断这条边所在顶点是否访问过，未访问进行深度优先遍历的递归实现

代码：

//思路：若该图为数，则该图为连通图，且顶点数-1 = 边数，深度优先

typedef struct MGraph{
	int vex[maxsize];
	int edge[maxsize][maxsize];
	int vexnum, edgenum;
}MGraph; 


int visited[maxsize] = {0};
void DFS(MGraph *G, int v, int &vnum, int &anum){
	visited[v] = 1;
	vnum++;
	for(int i = 0; i < G->vexnum; i++){
		if(G->edge[v][i] == 1){
			anum++;
			if(visited[i] == 0){
				DFS(G,i,vnum,anum);
			}
		}
	}
} 

bool judgetree(MGraph *G){
	int vnum = 0, anum = 0;
	DFS(G,0,vnum,anum);
	if(vnum == G->vexnum && 2*(vnum-1) == anum){
		printf("是一棵树"); 
		return true;
	}
	else{
		printf("不是一棵树"); 
		return false;
	}
}
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

程序设计

第一题 输出10*10的螺旋矩阵

输出螺旋矩阵

思路：

• 把矩阵分为很多个环，双重for循环实现，第一重循环矩阵存在多少个环就遍历多少次，注意 k <= N/2 对于奇数的环，最后一个环是一个数也得考虑进去
• 第二重循环需要每次添加矩阵的一条边，依次进行模拟即可，注意下标之间的关系

代码：

void spiralMatric(int n){
	int i=0,j=0,k=0;
	int A[10][10];
	int count = 1;
	for(k = 0; k <= n/2; k++){		//每次输出一个矩阵环
		for(i = k; i < n-k; i++){	//最顶行 
			A[k][i] = count++;
		}
		for(j=k+1; j < n-k-1; j++){	//最右列
			A[j][n-k-1] = count++;
		}
		for(i=n-k-1; i > k; i--){	//最下行
			A[n-k-1][i] = count++;
		}
		for(j = n-k-1; j >k; j--){	//最左列
			A[j][k] = count++;
		}
	}
	for(i=0; i < n; i++){
		for(j=0; j < n; j++){
			printf("%-4d",A[i][j]);
		}
		printf("\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

第二题 输出子集

2、编写一个包含N个整数的几何S，编写函数求S的所有元素个数为M个的子集

思路：

• 直接套用求子集的模板，然后计数，如果子集中元素个数与题目给的相同，就输出

代码：

void findchild(int A[], int n, int m){
	int num = 1<<n;
	for(int i =0; i < num; i++){
		int sub[m];
		int count=0;
		for(int j = 0; j < n; j++){
			if(i & (1 << j)){
				sub[count] = A[j];
				count++;
			}
		}
		if(count == m){
			printf("{ %d", sub[0]);
			for(int j = 1; j < m; j++){
				printf(" ,%d ",sub[j]);
			}
			printf("}\n"); 
		}
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20