PTA数据结构与算法 7 |
您所在的位置：网站首页 › 家族最新家谱人员照片介绍大全 › PTA数据结构与算法 7 |
PTA数据结构与算法 7
|
如有不对，不吝赐教 这个题目的最后一个点搞了我好几天，最后发现是一个初始化的不同选择导致了有一个特殊的点忘了检验，搞得我心态有点崩，这几天就过着那种看代码找错误的生活，这个痛苦大家懂懂…… 进入正题： 人类学研究对于家族很感兴趣，于是研究人员搜集了一些家族的家谱进行研究。实验中，使用计算机处理家谱。为了实现这个目的，研究人员将家谱转换为文本文件。下面为家谱文本文件的实例： John Robert Frank Andrew Nancy David 家谱文本文件中，每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代，而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例，John这个家族最早的祖先，他有两个子女Robert和Nancy，Robert有两个子女Frank和Andrew，Nancy只有一个子女David。 在实验中，研究人员还收集了家庭文件，并提取了家谱中有关两个人关系的陈述语句。下面为家谱中关系的陈述语句实例： 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为家谱中的不同名字： 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，如果陈述为假。 输入样例: 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 输出样例: True True True False False 这个题目中的家谱关系实际上就相当于树的关系，但是真的去建一棵多叉树就过分了点了，所以我们可以使用静态链表的思想来记录节点之间的关系，也就是搞一个father数组，father[i]表示第i号人的父亲，这样树的关系就出来了，然后就是将名字和序号对上号，这里可以使用数组（访问时间复杂度为O（N）），也可以使用二叉树（访问时间复杂度为O（logN）），还可以使用Hash表（访问时间复杂度为O（1））。 下面给出我用树的代码： #include #include #include #include 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;inumber; 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)right) cur=cur->right; if(strcmp(cur->name,name)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(resright; 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 is sibling of Rober 这个语句为true，实际上这个语句为false 所以在IsSibling中的开头要加上： if(father[index1]==index1||father[index2]==index2) return false;还有为了防止这样S13的语句： John is sibling of John 我在Judge中加上了这条语句： if(index1==index2) return false;下面给出结果： |
【本文地址】
今日新闻 |
推荐新闻 |