数据结构
第一题 判断是是否为图
请设计一个算法判断无向图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;}
}
程序设计
第一题 输出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");}
}
第二题 输出子集
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"); }}
}
