数据结构与算法题目集（中文）
7 分鐘 閱讀文 (大約 1045 個字)

7-27 家谱处理 (30 分)

7-27 家谱处理 (30 分)

人类学研究对于家族很感兴趣，于是研究人员搜集了一些家族的家谱进行研究。实验中，使用计算机处理家谱。为了实现这个目的，研究人员将家谱转换为文本文件。下面为家谱文本文件的实例：

1
2
3
4
5
6
John
  Robert
    Frank
    Andrew
  Nancy
    David

家谱文本文件中，每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代，而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例，John这个家族最早的祖先，他有两个子女Robert和Nancy，Robert有两个子女Frank和Andrew，Nancy只有一个子女David。

在实验中，研究人员还收集了家庭文件，并提取了家谱中有关两个人关系的陈述语句。下面为家谱中关系的陈述语句实例：

1
2
3
John is the parent of Robert
Robert is a sibling of Nancy
David is a descendant of Robert

研究人员需要判断每个陈述语句是真还是假，请编写程序帮助研究人员判断。

输入格式:

输入首先给出2个正整数N（2≤N≤100）和M（≤100），其中N为家谱中名字的数量，M为家谱中陈述语句的数量，输入的每行不超过70个字符。

名字的字符串由不超过10个英文字母组成。在家谱中的第一行给出的名字前没有缩进空格。家谱中的其他名字至少缩进2个空格，即他们是家谱中最早祖先（第一行给出的名字）的后代，且如果家谱中一个名字前缩进k个空格，则下一行中名字至多缩进k+2个空格。

在一个家谱中同样的名字不会出现两次，且家谱中没有出现的名字不会出现在陈述语句中。每句陈述语句格式如下，其中X和Y为家谱中的不同名字：

1
2
3
4
5
X is a child of Y
X is the parent of Y
X is a sibling of Y
X is a descendant of Y
X is an ancestor of Y

输出格式:

对于测试用例中的每句陈述语句，在一行中输出True，如果陈述为真，或False，如果陈述为假。

输入样例:

1
2
3
4
5
6
7
8
9
10
11
12
6 5
John
  Robert
    Frank
    Andrew
  Nancy
    David
Robert is a child of John
Robert is an ancestor of Andrew
Robert is a sibling of Nancy
Nancy is the parent of Frank
John is a descendant of Andrew

输出样例:

1
2
3
4
5
True
True
True
False
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct Node
{
    char name[15];
    char father[15];
    int num;  //空格数
} people[102];

int main()
{
    int n,m;
    char temp[75];
    int i,j,k;
    scanf("%d %d",&n,&m);
    getchar();  

    for( i=0; i<n; i++)
    {
        people[i].num = 0; //空格数初始化为0
        gets(temp);
        int L = strlen(temp);
        for( j=0; j<L; j++)
        {
            if( temp[j]==' ')
                people[i].num++;
            else
            {
                strcpy( people[i].name, temp+j);  //复制空格以后的字符
                break;
            }
        }

        if( !people[i].num )
            strcpy( people[i].father,"root");  //如果空格数为0则表示根
        else
        {
            for( k=i-1; k>=0; k--)
            {
                if( people[i].num> people[k].num)
                {
                    //从后往前寻找父节点
                    strcpy( people[i].father,people[k].name);
                    break;
                }
            }
        }
    }

    char a[15],b[15],c[15],d[15];
    char temp1[15],temp2[15];
    for( i=0; i<m; i++)
    {
        scanf("%s %s %s %s %s %s",a,d,d,b,d,c);
        if( b[0] == 'c')
        {
            //X is a child of Y
            for( k=0; k<n; k++)
            {
                if( !strcmp( people[k].name,a))
                {
                    if( !strcmp( people[k].father,c))
                        printf("True\n");
                    else printf("False\n");
                    break;
                }
            }
        }

        else if( b[0] == 'p')
        {
            //X is the parent of Y
            for( k=0; k<n; k++)
            {
                if( !strcmp( people[k].name,c))
                {
                    if( !strcmp( people[k].father,a))
                        printf("True\n");
                    else printf("False\n");
                    break;
                }
            }
        }
        else if( b[0] == 's')
        {
            // X is a sibling of Y
            for( k=0; k<n; k++)
            {
                //寻找两个结点的父节点
                if( !strcmp( people[k].name,a))
                    strcpy(temp1,people[k].father);
                if( !strcmp( people[k].name,c))
                    strcpy(temp2,people[k].father);
            }
            if( !strcmp(temp1,temp2)) printf("True\n");
            else printf("False\n");
        }
        else if( b[0] == 'd')
        {
            //X is a descendant of Y
            for( k=0; k<n; k++)
            {
                if( !strcmp( people[k].name,a))

                    strcpy(temp1,people[k].father);
            }
            while( strcmp(temp1,c) && strcmp( temp1,"root"))
            {
                for( k=0; k<n; k++)
                    if( !strcmp(people[k].name,temp1))
                        strcpy( temp1,people[k].father);

            }
            if( !strcmp(temp1,"root"))
                printf("False\n");
            else printf("True\n");
        }
        else if( b[0] == 'a')
        {
            //X is an ancestor of Y
            for( k=0; k<n; k++)
            {
                if( !strcmp( people[k].name,c))

                    strcpy(temp1,people[k].father);
            }
            while( strcmp(temp1,a) && strcmp( temp1,"root"))
            {
                for( k=0; k<n; k++)
                    if( !strcmp(people[k].name,temp1))
                        strcpy( temp1,people[k].father);

            }
            if( !strcmp(temp1,"root"))
                printf("False\n");
            else printf("True\n");
        }
    }
    getchar();
    return 0;
}
# 数据结构与算法题目集（中文）

喜歡這篇文章嗎? 贊助一下作者吧!

7-28 搜索树判断 (25 分)
7-26 Windows消息队列 (25 分)
追蹤

連結

分類

標籤雲

Hexo Hibernate MinGW bugs cpp findbugs java java面试 leetcode leetcode Array BinarySearch leetcode Array TwoPointers leetcode Easy Array HashTable leetcode Easy Math leetcode LinkedList leetcode Stack leetcode Stack Queue leetcode TwoPointers leetcode TwoPointers String markdown maven mysql oracle 个人简历 个人观点 基础编程题目集 数据结构与算法题目集（中文） 浙大版《C语言程序设计实验与习题指导（第3版）》题目集 浙大版《C语言程序设计（第3版）》题目集 簡歷 編譯原理

最新文章

彙整

標籤

Hexo 1
Hibernate 1
MinGW 1
bugs 1
cpp 1
findbugs 1
java 3
java面试 1
leetcode 13
leetcode Array BinarySearch 1
leetcode Array TwoPointers 1
leetcode Easy Array HashTable 1
leetcode Easy Math 1
leetcode LinkedList 6
leetcode Stack 1
leetcode Stack Queue 2
leetcode TwoPointers 1
leetcode TwoPointers String 1
markdown 1
maven 1
mysql 1
oracle 2
个人简历 1
个人观点 1
基础编程题目集 51
数据结构与算法题目集（中文） 65
浙大版《C语言程序设计实验与习题指导（第3版）》题目集 179
浙大版《C语言程序设计（第3版）》题目集 116
簡歷 1
編譯原理 1

最新文章

彙整

標籤

Hexo 1
Hibernate 1
MinGW 1
bugs 1
cpp 1
findbugs 1
java 3
java面试 1
leetcode 13
leetcode Array BinarySearch 1
leetcode Array TwoPointers 1
leetcode Easy Array HashTable 1
leetcode Easy Math 1
leetcode LinkedList 6
leetcode Stack 1
leetcode Stack Queue 2
leetcode TwoPointers 1
leetcode TwoPointers String 1
markdown 1
maven 1
mysql 1
oracle 2
个人简历 1
个人观点 1
基础编程题目集 51
数据结构与算法题目集（中文） 65
浙大版《C语言程序设计实验与习题指导（第3版）》题目集 179
浙大版《C语言程序设计（第3版）》题目集 116
簡歷 1
編譯原理 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×