《数据结构与算法》实验报告
专业
班级
姓名
学号
实验项目
实验一 二叉树的应用
实验目的
1、进一步掌握指针变量的含义及应用。
2、掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。
实验内容
题目1:编写一个程序，采用一棵二叉树表示一个家谱关系。要求程序具有如下功能： （1）用括号表示法输出家谱二叉树， （2）查找某人的所有儿子， （3）查找某人的所有祖先。
算法设计分析
（一）数据结构的定义
为了能够用二叉树表示配偶、子女、兄弟三种关系，特采用以下存储关系，则能在二叉树上实现家谱的各项运算。
父 妻 子1 子妻1 孙1 子妻2 孙2 子2
二叉树型存储结构定义为： typedef struct SNODE {char name[MAX]; //人名
struct SNODE *left; //指向配偶结点
struct SNODE *right; //指向兄弟或子女结点 }FNODE; （二）总体设计
实验由主函数、家谱建立函数、家谱输出函数、儿子查找函数、祖先查找函数、结点定位函数、选择界面函数七个函数共同组成。其功能描述如下： （1）主函数：统筹调用各个函数以实现相应功能 void main()
（2）家谱建立函数：与用户交互建立家族成员对应关系 void InitialFamily(FNODE *&head) //家谱建立函数 （3）家谱输出函数：用括号表示法输出家谱 输出形式为：父和母（子1和子妻1（孙1），子2和子妻2（孙2）） void PrintFamily(FNODE *head) //家谱输出函数
2
（4）儿子查找函数：在家谱中查找到某人所有的子女并输出，同时也能辨别出其是否为家族成员与是否有子女
void FindSon(FNODE *b,char p[]) //儿子查找函数
（5）祖先查找函数：在家谱中查找到某人所有的祖先并输出，同时也能辨别出其是否为家族中成员。
int FindAncestor(FNODE *head,char son[ ]) //祖先查找函数 （6）结点定位函数：在家谱中找到用户输入人名所对应的结点。 FNODE *findnode(FNODE *b,char p[]) //结点定位函数
（7）选择界面函数：为便于编写程序，将用户选择部分独立为此函数。 void PRINT(int &n) （三）各函数的详细设计：
void InitialFamily(FNODE *&head) //家谱建立函数
1：首先建立当前人的信息，将其左右结点置为空，
2：然后让用户确定其是否有配偶，如果没有配偶，则当前程序结束， 3：如果有则建立其配偶信息，并将配偶结点赋给当前人的左结点；
4：再让用户确定其是否有子女，如果有则递归调用家谱建立函数建立子女结点，并将其赋给配偶结点的下一个右结点。 5：如无，则程序结束
void PrintFamily(FNODE *head) //家谱输出函数
1：首先判断当前结点是否为空，如果为空则结束程序； 2：如果不为空，则输出当前结点信息，
3：然后判断其左结点（配偶结点）是否为空，如不为空则输出“和配偶信息。
4：再判断配偶结点的右结点是否为空，如不为空则递归调用输出其子女信息，最后输出“）”；
5：当配偶结点为空时，则判断其右结点（兄弟结点）是否为空 6：如果不为空，则输出“，”，并递归调用输出兄弟信息 7程序结束
FNODE *findnode(FNODE *b,char p[]) //结点定位函数 1：当前结点是否为空，为空则返回空； 2：如果和查找信息相同，则返回当前结点；
3：如不然，则先后递归访问其左结点，再不是则递归访问右结点 void FindSon(FNODE *b,char p[]) //儿子查找函数
1：在家谱中定位到要查找的结点，如无则输出“查找不到此人” 2：判断其配偶结点与子女结点是否为空，为空则输出“无子女” 3：不为空则输出其配偶结点的所有右结点（子女结点）。 int FindAncestor(FNODE *head,char son[ ]) //祖先查找函数
1：先在家谱中定位到要查找的结点，如为空输出“不存在此人”，程序结束 2：先将父母结点入栈，当栈为空时程序结束， 3：栈不为空时，判断栈顶元素是否已访问过，
4：访问过，再判断是否为查找结点，如是则输出栈中保存的其祖先结点，并滤过其兄弟结点不输出；不是查找结点，则退栈一个元素
5：未访问过，则取当前栈顶元素，置访问标志——1，同时取其右结点 6：栈不为空或当前所取结点不为空时，转到2；
实验测试结果及结果分析
3
（一）测试结果
（二）结果分析 （略）
4
实验总结
（略）
附录 实验程序代码(该部分请加注释)
/*程序定义部分：*/ #include
typedef struct SNODE {
char name[MAX]; //人名
struct SNODE *left; //指向配偶结点
struct SNODE *right; //指向兄弟或子女结点
}FNODE;
/*家谱建立函数*/
void InitialFamily(FNODE *&head) {
FNODE *s,*r,*q; int tag;
q=(FNODE *)malloc(sizeof(FNODE)); q=NULL;
s=(FNODE *)malloc(sizeof(FNODE)); printf(\输入姓名:\\n\ scanf(\，,s->name); s->left=s->right=NULL; head=r=s; printf(\是否有配偶?有 1,无 0\\n\ //建立配偶结点 scanf(\ if(tag) { s=(FNODE *)malloc(sizeof(FNODE)); printf(\输入其配偶姓名:\\n\ scanf(\ s->left=s->right=NULL; r->left=s; r=s; do{ //递归调用建立孩子结点 printf(\是否还有子女?有 1,无 0\\n\ scanf(\ if(tag) { InitialFamily(q);
5
r->right=q; r=q; } }while(tag); } }
/*家谱输出部分*/
void PrintFamily(FNODE *head) {
FNODE *s; if(head!=NULL) { printf(\ //不为空时输出当前结点 if(head->left!=NULL) //输出配偶结点 {
s=head->left; printf(\和%s(\ PrintFamily(s->right); //递归调用输出孩子结点 printf(\ } if(head->right!=NULL) //递归调用输出兄弟结点 {
printf(\ PrintFamily(head->right); } } }
/*结点定位函数*/
FNODE *findnode(FNODE *b,char p[]) //在家谱中定位所要查找结点 { FNODE *q; if(b==NULL) return NULL; else if(!strcmp(b->name,p)) //如果与查找人名相同则返回该结点 return b; else { q=findnode(b->left,p); //否则递归调用其左结点 if(q!=NULL) return q; else return(findnode(b->right,p)); //递归调用右结点 }
6