PTA数据结构与算法 7-27 家谱处理
如有不对，不吝赐教
我在解决这个问题的过程中耗时较长。最终发现问题源于一个初始化设置上的不同选择。这一特殊点我没有及时检验清楚导致了一些混乱。让我感到有些沮丧的是这段时间里几乎每天都在调试代码中度过。这段经历或许会让其他人也会遇到类似的困扰。
人类学家对家族结构表现出浓厚的研究兴趣，并因此开始收集相关数据来源
在实验过程中，研究人员还对家庭文件进行了采集，并从家谱中提取了关于两人关系的断言实例。以下列举了家谱中关于两人关系的断言实例：
- John是罗伯特的父亲
- 罗伯特与南希是兄妹关系
- 大卫是罗伯特的后代
研究人员需要确定每个断言是否真实，请开发程序以生成相应的逻辑判断模型
具体来说，在家谱研究中，输入数据由两个参数确定：两个正整数N和M。具体来说：
- N表示家族成员名称的数量；
- M表示家族陈述语句的条数。
需要注意的是， - N的具体范围是2到100；
- M的具体范围是小于等于100。
此外， - 每一行输入数据不应超过70个字符。
名称的字符串最多由十个英文字母构成。位于家谱的第一行给出的名字前面没有缩进空白。其余名称最少占用两个空白字符的位置。这些名称均表示家庭树系图中最先出现在第一行给出的名字之下的后代成员。若家庭树图上某个名称前有k个空白字符，则其后一行中的相应名称最多可占k加二个空白字符的位置。
同一个家庭档案里不会有重复的姓名出现，并且那些未记载的家庭成员也不会在描述性语句里显现出来。对于每一句话的结构来说，在描述性语句里只会涉及两个不同的家庭成员X和Y。
X is the son or daughter of Y
X is the father or mother of Y
X is a sibling (brother/sister) of Y
X is the progeny (descendant) of Y
X has the ancestral relationship to Y
输出格式:
针对测试案例中的每个声明性语句，在一行中将结果以字符串形式呈现：若该声明成立，则返回True；否则返回False。
6 5
John
Robert
Frank
Andrew
Nancy
David
罗伯特是约翰的儿子
罗伯特是安德鲁的祖先
罗伯特与南希是兄妹
南希是弗兰克的母亲
约翰是安德鲁的后代
输出样例:
True
True
True
False
False
在本题中涉及的家谱关系本质上等同于树结构，在这种情况下单纯地构建一棵多分支树并非最佳选择。因此我们可以采用静态链表的方式来记录节点间的关系，并且这种方法的具体实现就是建立一个father数组其中father[i]表示第i个节点的父节点信息从而完整地展现出家谱之间的血缘联系接下来我们需要将节点编号与实际名称对应起来这可以通过数组或者二叉树等方式来实现其中数组方法的时间复杂度为O(N)，而二叉树方法则能够达到O(logN)的时间效率此外我们还可以考虑利用哈希表来提升查找操作的速度达到常数阶的时间复杂度O(1)
下面给出我用树的代码：
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<stdbool.h>
struct NameTree{
char name[12]; //名字
short index; //编号
struct NameTree *left; //左节点
struct NameTree *right; //右节点
};
struct PackageTree{
struct NameTree *root; //编号树的节点
short number; //当前最大人员编号
};
struct PackageTree *Add(struct PackageTree *tree,char *name);
short GetIndex(char *name,struct NameTree *root);
void FreeTree(struct NameTree *root);
void DealString(char *name1,char *name2,char *relation);
bool Judge(char *name1,char *name2,char *relation,struct NameTree *root,short *father);
bool IsChild(short index1,short index2,short *father);
bool IsAncestor(short index1,short index2,short *father);
bool IsSibling(short index1,short index2,short *father);
int main(void)
{
struct PackageTree *tree;
char name[11];
char get[71];
tree=(struct PackageTree *)malloc(sizeof(struct PackageTree));
tree->root=(struct NameTree *)malloc(sizeof(struct NameTree));
tree->root=NULL;
tree->number=0; //Tree树初始化
short N,M;
short i,j,k;
scanf("%hd %hd",&N,&M);
short father[N]; //存储父亲是谁 人员编号从0到N-1
short space[N];
for(i=0;i<N;i++){
father[i]=i;
space[i]=0;
} //在寻找父亲的时候 为最近的空格数小于2的
getchar();
for(i=0;i<N;i++){
fgets(get,70,stdin);
for(j=0,k=0;get[j]&&'\n'!=get[j];j++){
while(' '==get[j]||'\t'==get[j]){
if(' '==get[j])
space[i]++;
else
space[i]+=8;
j++;
}
name[k++]=get[j];
} //将输入的名字进行处理
name[k]='\0';
k=i-1;
while(k&&i){
if(space[k]<space[i]) //父亲和孩子的关系式：space[k]==space[i]-2||space[k]==space[i]-1 同级的时候二者相等
break;
k--;
} //找到父节点
if(i)
father[i]=k; //填入父节点编号
tree=Add(tree,name);
} //输入信息处理
bool result[M]; //结果
for(i=0;i<M;i++){
char name1[11],name2[11]; //待判断的名字
char relation[11]; //待判断的关系
DealString(name1,name2,relation); //字符串分离
result[i]=Judge(name1,name2,relation,tree->root,father);
}
for(i=0;i<M;i++)
if(result[i])
printf("True\n");
else
printf("False\n");
FreeTree(tree->root);
free(tree); //释放空间
tree=NULL;
return 0;
}
struct PackageTree *Add(struct PackageTree *tree,char *name)
{
struct NameTree *cur=tree->root; //当前节点
struct NameTree *newNode;
newNode=(struct NameTree *)malloc(sizeof(struct NameTree));
newNode->index=tree->number;
tree->number++;
strcpy(newNode->name,name);
newNode->left=NULL;
newNode->right=NULL;
if(1==tree->number){
tree->root=newNode;
return tree;
} //操作完之后只有一个节点 即原来为空树
while(1){
while(strcmp(cur->name,name)>0&&cur->left)
cur=cur->left;
if(strcmp(cur->name,name)>0){
cur->left=newNode;
break;
}
while(strcmp(cur->name,name)<0&&cur->right)
cur=cur->right;
if(strcmp(cur->name,name)<0){
cur->right=newNode;
break;
}
}
return tree;
} //添加节点
short GetIndex(char *name,struct NameTree *root)
{
struct NameTree *cur=root;
int res;
while(1){
res=strcmp(cur->name,name);
if(res>0)
cur=cur->left;
else if(res<0)
cur=cur->right;
else
break;
}
return cur->index;
} //找到名字对应的编号
void FreeTree(struct NameTree *root)
{
if(root->left)
FreeTree(root->left);
if(root->right)
FreeTree(root->right);
free(root);
root=NULL;
return ;
}
void DealString(char *name1,char *name2,char *relation)
{
scanf("%s",name1); //第零个字符串是第一个名字
scanf("%s",relation);
scanf("%s",relation);
scanf("%s",relation); //第三个字符串才是关系
scanf("%s",name2);
scanf("%s",name2); //第五个字符串是第二个名字
return ;
}
bool Judge(char *name1,char *name2,char *relation,struct NameTree *root,short *father)
{
short index1=GetIndex(name1,root);
short index2=GetIndex(name2,root); //判断的成员的编号
if(index1==index2)
return false;
if('c'==relation[0])
return IsChild(index1,index2,father);
else if('a'==relation[0])
return IsAncestor(index1,index2,father);
else if('s'==relation[0])
return IsSibling(index1,index2,father);
else if('p'==relation[0])
return IsChild(index2,index1,father);
else
return IsAncestor(index2,index1,father); //利用5个关系的第一个字符不同来判断
}
bool IsChild(short index1,short index2,short *father)
{
if(father[index1]==index2)
return true;
else
return false;
} //index1 is the child of index2
bool IsAncestor(short index1,short index2,short *father)
{
while(index2!=father[index2]){ //直到找到根
if(father[index2]==index1)
return true;
index2=father[index2];
}
if(index2==index1) //刚好是所有人的祖先的时候
return true;
else
return false;
} //index1 is the ancestor of index2
bool IsSibling(short index1,short index2,short *father)
{
if(father[index1]==index1||father[index2]==index2)
return false;
if(father[index1]==father[index2])
return true;
else
return false;
} //equals that they have the same father在这里说一下我遇到的坑：
我的静态数组初始化选择填入自己：
father[i]=i;这将导致一个问题，在判断这种语句时（如题目所示）：
John and Robert之间的关系为sibling关系
实际上该语句应为false
所以在IsSibling中的开头要加上：
if(father[index1]==index1||father[index2]==index2)
return false;为了避免重复出现具有相同父代关系的条目以保证数据的一致性 我在其中加入了这条逻辑判断规则
if(index1==index2)
return false;下面给出结果：
