数据结构 树的应用.doc

《数据结构》实验报告

实验三、树结构的应用

一、实验目的
熟练掌握二叉树的存储结构以及进行遍历的各种算法，并根据实际问题的要求灵活运用。

二、实验内容
本次实验仍以班级学生信息作为管理对象，以学生信息中的学生成绩为关键字，生成一棵二叉排序树，查找特定结点。

三、完成情况
typedef int KeyType;
typedef struct node
{
KeyType score;
char num[8];
char name[8];
char gender[3];
struct node *lchild,*rchild;
}BSTNode;

typedef BSTNode *BSTree;
void InsertBST(BSTree *q,BSTNode *student)
{
BSTNode *f,*p=*q;
while(p)
{f=p;
p=((student->score)<=(p->score))?p->lchild:p->rchild;
}
p=(BSTNode *)malloc(sizeof(BSTNode));
p->score=student->score;
strcpy(p->num,student->num);
strcpy(p->name,student->name);
strcpy(p->gender,student->gender);
p->lchild=p->rchild=NULL;
if(*q==NULL)
*q=p;
else
if(student->score<=f->score) f->lchild=p;
else f->rchild=p;
}

BSTree CreateBST(void)
{
BSTree T=NULL;
BSTNode *student;
int a=1;
student=(BSTNode *)malloc(sizeof(BSTNode));
printf("请输入学生信息：\n");
while (a)
{ printf("学号\t姓名\t性别\t成绩\n");
scanf("%s%s%s%d",student->num,student->name,student->gender,&student->score);
InsertBST(&T,student);
printf("继续? 1=是 0=否\n");
scanf("%d",&a);
}
return T;
}

void InOrder(BSTree root)
{
if (root!=NULL)
{
InOrder(root->lchild);
printf("%s\t%s\t%s\t%d\n",root->num,root->name,root->gender,root->score);
InOrder(root->rchild);
}
}

BSTNode *SearchBST(BSTree T,KeyType stuScore)
{
if(T==NULL || stuScore==T->score)
return T;
if(stuScore<=T->score)
return SearchBST(T->lchild,stuScore);
if(stuScore>T->score)
return SearchBST(T->rchild,stuScore);
}

void main()
{
BSTree root;
BSTNode *student;
KeyType stuScore;
printf("\n生成二叉排序树：\n");
root=CreateBST();
printf("\n中序遍历二叉排序树，输出结果\n");
printf("\n学号(8) 姓名(8) 性别(3) 成绩\n");
printf("-------------------------------------------\n");

InOrder(root);
printf("\n利用二叉排序树进行查找：\n");
printf("\n请输入要查询的学生成绩：\n");
scanf("%d",&stuScore);
student=SearchBST(root,stuScore);
if(!student)
printf("没有查找到成绩为%d的学生");
else
{
printf("成绩为%d的学生信息:");
printf("%s,%s,%s,%d\n",student->num,student->name,student->gender,student->score);
}
getchar();
}

四、实验结果

五、问题与解决
BSTree CreateBST函数中的循环部分起初总是执行出错，设置的循环判断语句没有起到作用，用的是字符型的，最后换成整形1、0对应是否判断得以解决。
六、实验总结
通过编程更深刻了解了中序遍历的具体过程，以及程序内部的执行方法
实验成绩
评价项目
评分等级
独立完成完整的实验内容，结果完全正确，报告内容完整，排版整洁美观，能真实体现实际操作过程及遇到的问题。
A
完成实验，实验内容较为完整，结果正确，报告内容较为完整，排版较为整洁美观，能体现实际操作过程及遇到的问题。
B
基本完成实验，结果正确，报告内容欠缺，排版较为整洁美观，能体现实际操作过程及遇到的问题。
C
不能独立完成完整的实验内容，结果不真实，报告内容欠缺，排版欠整洁美观，不能体现实际操作过程及遇到的问题。
D

- 4 -