《数据结构与算法》实验报告
实验项目
实验一 二叉树的应用
实验目的
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、源代码部分请附加适当的注释说明；
2、打分的表格请置于实验报告最后一页的底端；
3、请遵照本实验范例的文字大小和段落格式排版；
4、实验报告双面打印；
5、每个实验20分，5个实验共100分。
实验报告雷同者均视为未做。抄袭请慎重！
第二篇：数据结构实验报告示例
《数据结构》实验报告
班级:_________ 姓 名:_______ 学 号:_________ E-mail:____________日期:________ ◎实验题目: 给定（也可自己定相关内容）
◎实验目的：给定（也可自己定相关内容）
◎实验内容：给定（也可自己定相关内容）
一、需求分析
说明程序设计的任务，强调的是程序要做什么，明确规定：
1、输入的形式和输入值的范围；
2、输出的形式；
3、程序所能达到的功能；
4、测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。
二 概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。
三 详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法；画出函数的调用关系。
四 使用说明、测试分析及结果
1、说明如何使用你编写的程序；
2、测试结果与分析；
3、调试过程中遇到的问题是如何解决提以及对设计与实现的回顾讨论和分析；
4、运行界面。
五、实验总结
1、算法的时空分析和改进设想等等，见示例。
示例：
(一) 需求分析
1．本演示程序中，人数n应为任意的，首先应输入一个值赋给初始报数上限m，程序应能自动保存出列人的序号和将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。
2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自动分配。
3．程序执行的命令包括：
（1）构造链表；（2）输入数据；（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；（4）结束。
4．测试数据
（1）n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。
(二) 概要设计
为了实现上述操作，应以单向循环链表为存储结构。
1．基本操作：
new_code( )
操作结果：构造空链表，若成功就初始化每个人的相关信息
delete_code( )
初始条件：线性链表存在
操作结果：释放指向出列的人的结点，并重新报数
2．本程序包含三个模块：
（1）主程序模块；
（2）构造链表并输入每个人信息模块；
（3）释放结点模块；
（4）模块调用图：
主程序模块
构造链表并输入每个人信息模块
释放结点模块
(三) 详细设计
1．元素类型，结点类型和指针类型：
typedef int ElemType;
typedef struct LNode
{
int num;
ElemType data;
struct LNode *next;
}LNode;
LNode *head; *this; *new;
2．每个模块的分析：
（1）主程序模块：
main()
{
int m,n,i;
printf("Enter the first code (m):"); scanf("%d",&m);
printf("\nEnter the people number (n):"); scanf("%d",&n);
getchar();
printf("\n");
new_code(n);
if(head!=NULL)
delete_code(n,m);
else
{
printf("list is empty\n");
exit();
}
for(i=0;i<n;i++)
printf("%-3d",str[i]);
printf("\n");
}
（2）构造链表并输入每个人信息模块；
new_code(int a)
{
int i=1;
char numstr[10];
new=(LNode *)malloc(sizeof(LNode)); if(new==NULL)
return ERROR;
if(head==NULL)
head=new;
this=head;
while(--a!=0) {
this->num=i;
printf("enter the %d code(data):",i); gets(numstr);
this->data=atoi(numstr);
new=(LNode *)malloc(sizeof(LNode)); this->next=new;
this=new;
i++;
}
this->num=i;
printf("enter the %d code(data):",i); gets(numstr);
this->data=atoi(numstr);
this->next=head;
return OK;
}
（3）释放结点模块
delete_code(int a,int b)
{
int i;
int j=0;
LNode *p;
while((a--)!=1)
{
for(i=1;i<=b;i++){
p=this;
this=this->next;
}
b=this->data;
str[j]=this->num;
p->next=this->next;
free(this);
j++;
}
str[j]=this->next->num;
return OK;
}
（4）函数调用关系图
main()
new_code()
delete_code（）
3．完整的程序：(见源文件).
(四) 程序使用说明及测试结果
1．程序使用说明
（1）本程序的运行环境为VC6.0。
（2）进入演示程序后即显示提示信息：
Enter the first code（m）:
输入初始报数值
Enter the people number（n）:
输入人数
enter the 1 code(data):
输入第一个人所持的密码
enter the 2 code(data):
输入第一个人所持的密码
┊
enter the n code(data):
输入第n个人所持的密码,输入完毕后就进行报数操作：
2．测试结果
当输入m＝6，n＝7，每个人所持密码一次为：3，1，7，2，4，8，4时，则输出正确的出列顺序为：6，1，4，7，2，3，5。
3．调试中的错误及解决办法。(遇到时给出)
4．运行界面
（五）、实验总结(实验心得)
你在编程过程中花时多少？
多少时间在纸上设计？
多少时间上机输入和调试？
多少时间在思考问题？
遇到了哪些难题？
你是怎么克服的？
你的收获有哪些？
教师评语：
实验成绩：
指导教师签名：
批阅日期：