菜鸟记录：c语言实现PAT甲级1004--Counting Leaves

384 0 0

作者:whf10000010

　　　　好消息：与上题的Emergency是同样的方法。坏消息：又错了&&c++真的比c方便太多太多。

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.

Input Specification:

Each input file contains one test case. Each case starts with a line containing

ID K ID[1] ID[2] ... ID[K]

where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID's of its children. For the sake of simplicity, let us fix the root ID to be 01.

The input ends with

Output Specification:

For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.

The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output 0 1 in a line.

Sample Input:

2 1
01 1 02

Sample Output:

0 1

题目分析

　　　　分析家族族谱，算出非叶子节点，就是非孩子数量。，所有的节点用两位数字表示，例如：01，02，06等，其中为了方便，令01为根节点。

　　　　输入： N（100个以内的的节点） M（非叶子节点数）

　　　　　　　【接下的M行内】 ID（非叶子节点）K（所连的叶子 / 孩子节点个数）ID[0] ID[1]...ID[K]（K个叶子节点）

　　　　输出：（每层的叶子节点个数）中间用空格隔开————>注意，pat对输出有着固定且严格的格式，所以最后结果的第一个数字前是没有空格的。

　　　　就是用广度优先或深度优先遍历每一层，同时标记每层叶子节点并记录，最后数组输出

个人想法

　　　　其实一开始，我觉得很简单，既然只看叶子节点个数，那每次输入ID[0-K]时，我进行记录不就行了吗，每次输入ID都是不同的层级，最后得到的的不就是每层孩子数，所以我在写输入的时候加了一点点变量，最后输出。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 
 5 int ID[101];
 6 int book[101];//记录输出每层叶节点个数    
 7 int b;        //每层的叶节点数
 8 
 9 int main() {
10     int N, M;
11     scanf("%d%d", &N, &M);
12     int K;
13     int a = 1;
14     for (int i = 1; i <= N; i+=K+1) {
15         scanf("%d%d", &ID[i], &K);     
16         if( K != 0)
17         for (int j = i+1; j <= i+K; j++) {
18             scanf("%d", &ID[j]);
19             b++;    //没输入一次叶节点数就增加一个
20         }
21         book[a] = b;//记录
22         b = 0;//归零进行下次计算    
23         a++;//记录数组下标移动
24     }
25     printf("%d", book[0]);//输出第一层
26     for (int i = 1; i <= M; i++) {
27         printf(" %d", book[i]);//输出接下来的每层，并于上一个数字隔开
28 
29     }
30     return 0;
31 }

View Code

　　　　最后得分13分。。。意料之中，举例思考的时候都只考虑了二叉树，编写的过程中便觉的那如果一个节点有有多个非叶节点甚至没有叶节点应该怎么填写。回过头来再看这段，更是觉得搞笑，如果这样可行，那直接记录K就好了。于是尝试着写了第二种，先构建一颗完整的树，然后深度遍历。

　　　　首先，变量的设置

1 int N, M;//同题目N，M
2 int K;
3 typedef struct NODE{
4     int nodes;//记录每个节点拥有的叶子节点数
5     int ID[101];    //记录各个叶子节点
6 };
7 struct NODE child[101];//树
8 int book[101];//保存、输出每层叶子节点数
9 int max;    //比较和更新每层的叶子节点数，因为左边的遍历完，右边的还要遍历并记录

　　　　这里使用了结构体而不是简单的数组或者二维数组记录，是因为退出递归的条件需要知道此时节点后续有无别的节点。对比之前的深度遍历我们可以知道，在每次递归的结束条件语句中，会判断后续“无路可走”后才停止并return，1003中是

 if (curlen > mindis[curcity])return;

　　，即如果所求的路径走这时变长就停止这条路。在此题则是你所谈的节点后面无节点就说明是叶子节点，那么就停止遍历，并记录数量。但是我开始在这使用二维数组，判定条件：

if(child[curnode]==0) return;

认为全局变量初始化为0，而这样判断说明此行均为0时就说明它是空的是叶子节点，但是实际运行出现了死循环，因为你在输入的for语句中都会因为默认给每一行赋值，导致你输入的值令每行都不是全为0（有点混乱）。而c++中用 child.[curnode]size()【child是vector型】判断长度，如果等于0 ，则进入叶子节点的计数。所以对c语言使用结构体记录每个节点的叶子节点数和叶子节点编号。

 1 void dfs(int curnode ,int curlevel);
 2 int main() {
 3     int a;
 4     scanf("%d%d", &N, &M);
 5     for (int i = 0; i < M; i++) {
 6         scanf("%d%d", &a, &K);
 7         child[a].node = K;//非叶节点ID，所有的叶子节点数
 8         for (int j = 0; j <K; j++) {
 9             scanf("%d", &child[a].ID[j]);  //叶子节点序号
10         }
11     }
12     dfs(1, 0);//从 1 开始是因为01为根节点，所有存放元素的是child[01]不是child[0]
13     printf("%d", book[0]);
14     for (int i = 1; i <= max; i++) {
15         printf(" %d", book[i]);
16 
17     }
18     return 0;
19 }
20 void dfs(int curnode, int curlevel) {
21     if (child[curnode].node == 0) {   //判断有无叶节点，无则进入此记录保存
22         if(max<curlevel)
23         max = curlevel;　　　　　　　　//更新当前遍历所在的叶子节点层数
24         book[curlevel]++;　　　　　　　　//没到该层，叶子节点数加 1 
25         return;
26     }
27     for (int i = 0; i < child[curnode].node; i++) {    //因为对该节点进行遍历，所以在它有的叶子节点数范围内循环
28         dfs(child[curnode].ID[i], curlevel + 1);　　　　//把当前的某个叶子节点的数值带入下一个节点的索引，层级加1.
29     }
30  }

<-----------------------------------完整代码----------------------------------->

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 
 6 
 7 int N, M;
 8 int K;
 9 typedef struct NODE{
10     int node;
11     int ID[101];
12 };
13 struct NODE child[101];
14 int book[101];
15 int max;
16 
17 void dfs(int curnode ,int curlevel);
18 int main() {
19     int a;
20     scanf("%d%d", &N, &M);
21     for (int i = 0; i < M; i++) {
22         scanf("%d%d", &a, &K);
23         child[a].node = K;
24         for (int j = 0; j <K; j++) {
25             scanf("%d", &child[a].ID[j]);
26         }
27     }
28     dfs(1, 0);
29     printf("%d", book[0]);
30     for (int i = 1; i <= max; i++) {
31         printf(" %d", book[i]);
32 
33     }
34     return 0;
35 }
36 void dfs(int curnode, int curlevel) {
37     if (child[curnode].node == 0) {
38         if(max<curlevel)
39         max = curlevel;
40         book[curlevel]++;
41         return;
42     }
43     for (int i = 0; i < child[curnode].node; i++) {
44         dfs(child[curnode].ID[i], curlevel + 1);
45     }
46  }