菜鸟记录:c语言实现PAT甲级1004–Counting Leaves

    好消息:与上题的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 0<N<100, the number of nodes in a tree, and M (<N), the number of non-leaf nodes. Then M lines follow, each in the format:

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 N being 0. That case must NOT be processed.

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都是不同的层级,最后得到的的不就是每层孩子数,所以我在写输入的时候加了一点点变量,最后输出。

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

 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  }

 

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

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

 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  }

View Code

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

 

总结

    其实掌握深度遍历总体大概的流程,结合题目改变判定条件写出总体的框架基本都能得分,然后调试以后进行修改就大差不差了。

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

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

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

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

原文链接:https://www.cnblogs.com/whf10000010/p/17325936.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:菜鸟记录:c语言实现PAT甲级1004–Counting Leaves - Python技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月18日

相关文章

  • ASP.NET MVC异常处理模块详解

    ASP.NET MVC异常处理模块是一种用来处理系统中出现的错误和异常的模块,可以有效降低系统的错误率和提供系统的稳定性。本文将从以下几个方面介绍ASP.NET MVC异常处理模块的详细攻略: 1. 异常处理的原理和流程 通常情况下,ASP.NET MVC系统中的异常处理流程如下: 1)异常发生时:程序运行过程中,如果出现了错误和异常,将会被.NET平台捕获…

    C 2023年5月23日
    00
  • C++临时性对象的生命周期详细解析

    C++临时性对象的生命周期详细解析 在C++中,临时性对象是在表达式求值结束后自动被销毁的对象。临时性对象的生命周期是很短暂的,因此对于理解临时性对象的生命周期和使用方式非常重要。 临时性对象的创建 C++中的临时性对象通常由以下几种情况创建: 函数返回值:当函数返回一个非引用类型的对象时,会创建一个临时性对象来存储返回值。 类型转换:当进行类型转换时,会创…

    C 2023年5月22日
    00
  • socket多人聊天程序C语言版(一)

    下面是“socket多人聊天程序C语言版(一)”的完整攻略。 一、前置知识 在学习本文前,需要掌握以下C语言知识:- socket编程基础- 线程基础- 指针基础 二、程序结构 本程序主要分为四个模块:客户端、服务端、公共头文件和Makefile。 1. 公共头文件 common.h:包含了各种结构体和宏定义,以及客户端和服务端公共使用的函数的声明。 2. …

    C 2023年5月23日
    00
  • GoLang函数与面向接口编程全面分析讲解

    下面我来详细讲解一下“GoLang函数与面向接口编程全面分析讲解”的完整攻略。 GoLang函数与面向接口编程全面分析讲解 一、GoLang函数的基本概念与使用 1.1 GoLang函数的定义 GoLang函数定义格式如下: func functionName(parameter1 parameter1Type, parameter2 parameter2T…

    C 2023年5月23日
    00
  • C语言实现页面置换算法(FIFO、LRU)

    C语言实现页面置换算法 在操作系统中,进程访问内存时,若访问的物理页不在内存中,就会出现缺页调度现象。为了解决这个问题,就需要使用页面置换算法。常用的页面置换算法包括FIFO和LRU,下面将详细讲解如何用C语言实现这两种算法。 一、使用FIFO算法实现页面置换 FIFO算法是一种最简单的内存置换算法,它是根据页面装入内存的时间先后次序决定淘汰的页面。先进先出…

    C 2023年5月22日
    00
  • C语言如何实现可变参数详解

    下面我将详细讲解如何在C语言中实现可变参数。 可变参数的实现方式 在C语言中,可变参数的实现方式是使用stdarg.h头文件中的宏和函数。该头文件包含的是可变参数列表,一些宏和函数的定义,可以实现对参数的操作。 该头文件中常用的宏有: va_start:用于初始化可变参数列表,获取第一个可变参数值的地址。 va_arg:用于获取可变参数列表的下一个参数值。 …

    C 2023年5月23日
    00
  • Objective-C基础 自定义对象归档详解及简单实例

    Objective-C基础:自定义对象归档详解及简单实例 1. 什么是归档? 归档是将对象保存到文件中,以便以后可以恢复对象时使用的一种技术。在iOS开发中,归档通常用于将自定义对象保存到本地,如用户数据、游戏进度等。 2. 归档的分类 归档分为两种:文件归档和系统归档。 文件归档:将对象保存到指定的文件中。 系统归档:将对象保存到系统的偏好设置、键值存储、…

    C 2023年5月22日
    00
  • 华为k662c光猫怎么样? 华为K662c拆机技巧

    华为k662c光猫怎么样? 华为K662c是一款具备家庭网关功能的光纤猫,可以直接连接光纤上网并接入路由器,同时支持IPv6、IPv4双协议栈,具有宽带业务传输和无线网络扩展等功能。总的来说,华为K662c光猫具备以下特点: 支持最高1Gbps的宽带接入 支持IPv6和IPv4双协议栈 支持4个千兆以太网端口和2个POTS电话接口 支持2.4GHz和5GHz…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部