好消息：與上題的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
題目分析
分析家族族譜，算出非葉子節(jié)點，就是非孩子數(shù)量。，所有的節(jié)點用兩位數(shù)字表示，例如：01，02，06等，其中為了方便，令01為根節(jié)點。
輸入： N（100個以內(nèi)的的節(jié)點） M（非葉子節(jié)點數(shù)）
【接下的M行內(nèi)】 ID（非葉子節(jié)點）K（所連的葉子 / 孩子節(jié)點個數(shù)）ID[0] ID[1]...ID[K]（K個葉子節(jié)點）
輸出：（每層的葉子節(jié)點個數(shù)）中間用空格隔開————>注意，pat對輸出有著固定且嚴格的格式，所以最后結(jié)果的第一個數(shù)字前是沒有空格的。
就是用廣度優(yōu)先或深度優(yōu)先遍歷每一層，同時標記每層葉子節(jié)點并記錄，最后數(shù)組輸出
個人想法
其實一開始，我覺得很簡單，既然只看葉子節(jié)點個數(shù)，那每次輸入ID[0-K]時，我進行記錄不就行了嗎，每次輸入ID都是不同的層級，最后得到的的不就是每層孩子數(shù)，所以我在寫輸入的時候加了一點點變量，最后輸出。
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 5 int ID[101]; 6 int book[101];//記錄輸出每層葉節(jié)點個數(shù) 7 int b; //每層的葉節(jié)點數(shù) 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++; //沒輸入一次葉節(jié)點數(shù)就增加一個 20 } 21 book[a] = b;//記錄 22 b = 0;//歸零進行下次計算 23 a++;//記錄數(shù)組下標移動 24 } 25 printf("%d", book[0]);//輸出第一層 26 for (int i = 1; i <= M; i++) { 27 printf(" %d", book[i]);//輸出接下來的每層，并于上一個數(shù)字隔開 28 29 } 30 return 0; 31 }
最后得分13分。。。意料之中，舉例思考的時候都只考慮了二叉樹，編寫的過程中便覺的那如果一個節(jié)點有有多個非葉節(jié)點甚至沒有葉節(jié)點應(yīng)該怎么填寫。回過頭來再看這段，更是覺得搞笑，如果這樣可行，那直接記錄K就好了。于是嘗試著寫了第二種，先構(gòu)建一顆完整的樹，然后深度遍歷。
首先，變量的設(shè)置
1 int N, M;//同題目N，M 2 int K; 3 typedef struct NODE{ 4 int nodes;//記錄每個節(jié)點擁有的葉子節(jié)點數(shù) 5 int ID[101]; //記錄各個葉子節(jié)點 6 }; 7 struct NODE child[101];//樹 8 int book[101];//保存、輸出每層葉子節(jié)點數(shù) 9 int max; //比較和更新每層的葉子節(jié)點數(shù)，因為左邊的遍歷完，右邊的還要遍歷并記錄
這里使用了結(jié)構(gòu)體而不是簡單的數(shù)組或者二維數(shù)組記錄，是因為退出遞歸的條件需要知道此時節(jié)點后續(xù)有無別的節(jié)點。對比之前的深度遍歷我們可以知道，在每次遞歸的結(jié)束條件語句中，會判斷后續(xù)“無路可走”后才停止并return，1003中是
if (curlen > mindis[curcity])return;
，即如果所求的路徑走這時變長就停止這條路。在此題則是你所談的節(jié)點后面無節(jié)點就說明是葉子節(jié)點，那么就停止遍歷，并記錄數(shù)量。但是我開始在這使用二維數(shù)組，判定條件：
if(child[curnode]==0) return;
認為全局變量初始化為0，而這樣判斷說明此行均為0時就說明它是空的是葉子節(jié)點，但是實際運行出現(xiàn)了死循環(huán)，因為你在輸入的for語句中都會因為默認給每一行賦值，導(dǎo)致你輸入的值令每行都不是全為0（有點混亂）。而c++中用 child.[curnode]size()【child是vector型】判斷長度，如果等于0 ，則進入葉子節(jié)點的計數(shù)。所以對c語言使用結(jié)構(gòu)體記錄每個節(jié)點的葉子節(jié)點數(shù)和葉子節(jié)點編號。
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;//非葉節(jié)點ID，所有的葉子節(jié)點數(shù) 8 for (int j = 0; j <K; j++) { 9 scanf("%d", &child[a].ID[j]); //葉子節(jié)點序號 10 } 11 } 12 dfs(1, 0);//從 1 開始是因為01為根節(jié)點，所有存放元素的是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) { //判斷有無葉節(jié)點，無則進入此記錄保存 22 if(max<curlevel) 23 max = curlevel; //更新當前遍歷所在的葉子節(jié)點層數(shù) 24 book[curlevel]++; //沒到該層，葉子節(jié)點數(shù)加 1 25 return; 26 } 27 for (int i = 0; i < child[curnode].node; i++) { //因為對該節(jié)點進行遍歷，所以在它有的葉子節(jié)點數(shù)范圍內(nèi)循環(huán) 28 dfs(child[curnode].ID[i], curlevel + 1); //把當前的某個葉子節(jié)點的數(shù)值帶入下一個節(jié)點的索引，層級加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 }
?
總結(jié)
其實掌握深度遍歷總體大概的流程，結(jié)合題目改變判定條件寫出總體的框架基本都能得分，然后調(diào)試以后進行修改就大差不差了。
文章來源：http://www.zghlxwxcb.cn/news/detail-416431.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-416431.html
到了這里，關(guān)于菜鳥記錄：c語言實現(xiàn)PAT甲級1004--Counting Leaves的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
