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

数据结构与算法实验报告专业班级姓名学号实验项目 实验一 二叉树的应用实验目的1、进一步掌握指针变量的含义及应用。2、掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3、掌握用指针类型描述、访问和处理二叉树的运算。实验内容题目1:编写一个程序，采用一棵二叉树表示一个家谱关系。要求程序具有如下功能：（1）用括号表示法输出家谱二叉树，（2）查找某人的所有儿子，（3）查找某人的所有祖先。算法设计分析（一）数据结构的定义为了能够用二叉树表示配偶、子女、兄弟三种关系，特采用以下存储关系，则能在二叉树上实现家谱的各项运算。二叉树型存储结构定义为：typedef struct SNODEchar nameMAX; /人名 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 #include #include #define MAX 20typedef struct SNODEchar nameMAX; /人名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,无 0n,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,无 0n,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);elseprintf(不存在你要查找的人!n);/*祖先查找函数*/int FindAncestor(FNODE *head,char son)FNODE *p,*s;FNODE *stackMAX;int tagMAX;int top=-1,i;p=findnode(head,son); /定位结点if(p=NULL) printf(不存在你要查找的人!n); return 0;s=head;dowhile(s!=NULL) /将其所有左结点进栈top+;stacktop=s;tagtop=0;s=s-left;if(top-1)if(tagtop=1) /被访问过时if(stacktop=p) /如果为所查找结点时输出祖先printf(%s祖先为:n,son); for(i=0;iright=stacki+1) /将其兄弟结点删除,只保留父母结点 i+; if(iname); i+; if(iname); break; top-; else /未访问过则访问其右结点并置访问标志 s=stacktop; if(top0) s=s-right; tagtop=1; while(s!=NULL|top!=-1);if(top=-1) printf(查找不到%s的祖先!n,p);else printf(n);return 1;/*选择界面函数部分：*/void PRINT(int &n) doprintf(请选择:n); printf(1:建立家谱n); printf(2:输出家谱n); printf(3:查找某人所有儿子n); printf(4:查找某人所有的祖先n);scanf(%d,&n);while(n4);/*主函数部分：调用选择界面函数，再依据用户的选择，调用相应函数，实现相关功能*/void main() FNODE *head; int n=0; char nameMAX; 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