数据结构实验报告范例.doc

《数据结构与算法》实验报告
专业

班级

姓名

学号

实验项目
实验一 二叉树的应用
实验目的
1、进一步掌握指针变量的含义及应用.
2、掌握二叉树的结构特征，以及各种存储结构的特点及使用范围.
3、掌握用指针类型描述、访问和处理二叉树的运算.
实验内容
题目1：编写一个程序，采用一棵二叉树表示一个家谱关系。要求程序具有如下功能：
（1）用括号表示法输出家谱二叉树,
（2)查找某人的所有儿子,
(3)查找某人的所有祖先。
算法设计分析
（一)数据结构的定义
为了能够用二叉树表示配偶、子女、兄弟三种关系，特采用以下存储关系，则能在二叉树上实现家谱的各项运算。

二叉树型存储结构定义为：
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) //家谱输出函数
（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；
实验测试结果及结果分析
（一）测试结果

（二）结果分析
（略）
实验总结
（略）

附录 实验程序代码（该部分请加注释)
/*程序定义部分：＊/
＃include <stdio。h>
＃include <stdlib.h>
#include 〈string.h>
＃define MAX 20
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"，，s—〉name）;
s-〉left=s->right=NULL;
head=r=s;
printf（"%s是否有配偶?有 1,无 0\n”,head-〉name)； //建立配偶结点
scanf（"%d”，＆tag)；
if(tag）
{
s=(FNODE ＊）malloc（sizeof(FNODE）);
printf("输入其配偶姓名：\n”)；
scanf（”％s"，s—〉name）;
s—>left=s-〉right=NULL;
r—〉left=s;
r=s;
do{ //递归调用建立孩子结点
printf("%s是否还有子女？有 1,无 0\n"，head->name)；
scanf(”%d”,&tag);
if(tag)
{
InitialFamily（q）；
r->right=q;
r=q;
｝
}while(tag)；
｝
}

/＊家谱输出部分*/
void PrintFamily(FNODE ＊head)
{
FNODE ＊s；
if(head!=NULL）
{
printf（”%s”，head—>name）; //不为空时输出当前结点
if(head—>left！=NULL) //输出配偶结点
{
s=head—>left;
printf（”和%s(",s—〉name)；
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)）; //递归调用右结点
｝
｝
/*儿子查找函数*/
void FindSon(FNODE ＊b,char p[])
｛
FNODE *q;
q=findnode(b,p);
if(q!=NULL） //存在孩子结点时输出
｛
q=q-〉left;
if（q==NULL｜｜q—〉right==NULL） //判断有无子女
printf（"%s没有子女！\n",p）;
else
｛ //输出则配偶结点的所有子女结点
q=q->right；
printf（”%s子女为:”,p）;
while(q！=NULL）
{
printf(”％s ”,q-〉name）;
q=q—>right；
｝
printf（”\n");
｝
｝
else
printf("不存在你要查找的人!\n");
｝
/＊祖先查找函数＊/
int FindAncestor（FNODE ＊head，char son[]）
{
FNODE ＊p,＊s;
FNODE *stack［MAX］；
int tag［MAX］；
int top=—1,i;
p=findnode(head,son); //定位结点
if（p==NULL）
｛ printf（"不存在你要查找的人!\n");
return 0；
}
s=head；
do｛
while(s！=NULL) //将其所有左结点进栈
{
top++;
stack［top］=s;
tag［top］=0;
s=s—>left；
}
if（top>—1)
｛
if(tag[top］==1） //被访问过时
｛
if（stack［top］==p) //如果为所查找结点时输出祖先
{
printf（"%s祖先为：\n"，son)；
for(i=0；i〈top;i++）
{
if(stack[i］—>right==stack[i+1］） //将其兄弟结点删除，只保留父母结点
i++;
if(i〈top) //依次输出夫妻结点
printf(”％s"，stack［i]—〉name）;
i++;
if（i<top)
printf（"和％s ",stack[i］->name);
｝
break；
}
top-—；
}
else //未访问过则访问其右结点并置访问标志
{
s=stack［top］;
if(top>0）
｛
s=s->right；
tag［top］=1;
}
｝
｝
}while(s！=NULL｜｜top！=-1）；
if(top==-1）
printf("查找不到％s的祖先！\n”,p）;
else printf（"\n");
return 1；
｝
/*选择界面函数部分：＊/
void PRINT（int &n）
｛
do｛
printf（"请选择：\n”）；
printf（"1：建立家谱\n”)；
printf(”2：输出家谱\n")；
printf(”3：查找某人所有儿子\n”);
printf（”4:查找某人所有的祖先\n"）;
scanf（"％d”，&n）;
｝while（n〈0|｜n〉4）;
｝
/＊主函数部分：调用选择界面函数，再依据用户的选择，调用相应函数，实现相关功能＊/
void main(）
｛
FNODE ＊head；
int n=0；
char name[MAX];
head=NULL；
do{
PRINT(n）;
switch（n)
｛
case 1: InitialFamily（head）；break;
case 2： PrintFamily（head)；printf（"\n"）;break;
case 3: printf(”请输入要查找的姓名:\n");
scanf(”%s”，name）；
FindSon(head,name）；
break；
case 4： printf(”请输入要查找的姓名:\n”)；
scanf（”％s”,name);
n=FindAncestor（head,name);
printf（”\n"）；
break;
default: break；
｝
printf（"是否继续？是 1，否 0\n")；
scanf（”％d”,＆n）；
}while(n==1）;
｝
序号
项目
得分
总分
1
实验报告排版（3分）

2
算法思想分析(6分)

3
源代码（6分)

4
实验结果及分析（5分）

另注:
1、 源代码部分请附加适当的注释说明;
2、 打分的表格请置于实验报告最后一页的底端;
3、 请遵照本实验范例的文字大小和段落格式排版;
4、 实验报告双面打印;
5、 每个实验20分，5个实验共100分。
实验报告雷同者均视为未做。抄袭请慎重！