数据结构”课程设计报告。
二叉排序树的查找与性能分析。
学生姓名： 段晓宣，张静。
指导教师： 陈少军。
所在系： 电子信息系。
所学专业： 计算机科学与技术
年级： 2010级计算机（1）班。
目录。第一章需求分析。
1.1选题要求 3
1.2选题的背景与意义 3
1.3本组课程设计的目标 3
1.4人员组成和分工 3
第2章概要分析 4
2.1 系统数据流图 4
2.2 原始数据 4
2.3 输出数据 4
2.4 对数据的处理 5
2.5 数据结构 5
2.6 模块划分 5
第3章详细设计 6
3.1二叉排序树的创建 6
3.2二叉排序树的插入 7
3.3二叉排序树的查找 7
3.4计算多数据的平均查找长度 9
3.5主函数 9
第4章用户手册 10
4.1 用户须知10
第5章系统测试 11
项目总结 12
参考文献 13
摘要：21世纪是信息化的时代，计算机深入到生活的各个领域。随着计算机的发展，许多高科技产品如雨后春笋应运而生。但究其本质而言，无非。
是以前的理论加以包装。对于数据控制、管理及处理等方面也可见一斑。在如今应用的计算机的数据存储方式仍然主要以线性，树型，图型等为主要的及结构。
因此了解并掌握数据结构的知识是很有必要的。
在此次实训期间，本组人员通过运用所学数据结构的知识，进行以二叉排序树的查找与性能分析为题的课程设计，在同组人员的共同努力下，基本实现了：
1. 创建二叉排序树。
2. 利用文件存储二叉排序树。
3. 二叉排序树的插入。
4. 二叉排序树的查找。
5. 二叉排序树平均查找长度的算法。
1.1选题要求。
1）根据输入的先序及递归建立二叉排序树；
2）通过文件，向二叉排序树插入结点，并生成二叉树；
3）设置报名号为关键字，可以根据关键字进行查找；
5）查找的同时可以判断比较的次数；
6）根据查找的算法计算出10000个数据平均查找长度；
1） 树型存储结构数据存储结构中重要的组成部分，二叉树由是树的重点。
2） 在考研的应用题当中考到树及二叉树的算法的概率也是相当高的，所以熟练掌握有关二叉树的算法对于今后的学习和工作也是十分重要的。
3） 掌握二叉排序树建立的递归算法并通过文件生成二叉排序树。
4） 掌握二叉排序树的查找及平均查找长度的算法。
5） 通过实验对二叉树及其相关的知识有一个整体的认识。
6） 旨在锻炼学生的思考问题的方法与思路。
（1）简单输入先序创建二叉排序树并能新建二叉排序树。
（2）能够实现通过文件生成二叉排序树。
（3）实现二叉排序树的插入。
（4）实现二叉排序树的查找。
（5）实现计算多个数据平均查找长度的算法。
1.4 人员组成和分工。
同组人员有：段晓宣，张静。
人员分工：段晓宣负责：
1） 新建二叉排序树。
2） 二叉排序树的生成。
3） 实现二叉排序树的查找。
张静负责：1） 实现二叉排序树的插入。
2） 程序的整合及检查。
3） 程序的运行。
1) 2024年考试参加学生信息作为文件，以报名号为关键字构建二叉排序树。
2) 任意输入报名号查找此学生信息是否存在。
1） 将输入的报名号与二叉树进行比较，1000个数据平均查找长度为：xxx
存在则输出。
find successed!
the value :报名号：xxx
若不存在则输出。
find unsuccessed!
若要停止查询输入0，则输出。
exit!（2）此外输出查找次数time:
1） 文件输入的信息建立二叉排序树。
2） 对建立好的二叉排序树进行查询及插入。
3） 计算多个数据平均查找长度。
typedef int keytype假定关键字类型为整数。
typedef struct
keytype key;
int num;
char name[12];
elemtype;
typedef struct bstnode结点类型。
elemtype *data;
int length;
struct bstnode *lchild,*rchild;//左右孩子指针。
bstnode;
typedef bstnode *bstree;
1）二叉排序树的建立。
2）二叉排序树的插入。
3）二叉排序树的查询。
4）平均查找长度的算法。
函数声明：status createbst(bstree &t);
status insertbst(bstree *t,keytype key,int num,char name[12]);
status searchbst(bstree t, keytype key, bstree &p);
double analysebst(bstree b);
系统定义为：
#define true 1
#define false 0
#define ok 1
typedef int status;
各操作函数及主函数如下：
头文件如下：
#include <>
#include <>
#include <>
#include <>
#include ""
#include "系统定义。h"
static int i=0;
status createbst(bstree &t)
t=null
keytype k;
int tnum;
char tname[12];
int length=0;
file *fp;
fp=fopen("c:\");
fscanf(fp,"%d %d %s",&k,&tnum,tname);
//t->data->key=k;
while(k)
insertbst(&t,k,tnum,tname);
t->length=++length;
fscanf(fp,"%d %d %s",&k,&tnum,tname);
fclose(fp);
return ok;
status insertbst(bstree *t,keytype key,int num,char name[12])
bstnode *f,*p=*t
while(p)
if(p->data->key==key) return ok;
f=pp=(keydata->key)? p->lchild:p->rchild;
p=(bstnode *)malloc(sizeof(bstnode));
p->data=(elemtype *)malloc(sizeof(elemtype));
p->data->key=key;
p->data->num=num;
strcpy(p->data->name,name);
p->lchild=p->rchild=null;
if(*t==null
*t=pelse
if(keydata->key)
f->lchild=p;
else f->rchild=p;
*二叉排序树的查找*/
status searchbst(bstree t, keytype key, bstree &p)
//t->data->key=key;
if (!t) else
//return i;
//searchbst
double analysebst(bstree b)
keytype k;
数据结构课程设计
课程设计说明书 题目哈夫曼编码问题的设计和实现。课程名称数据结构课程设计。院 系 部 中心。专业。班级。学生姓名。学号。设计地点。指导教师。设计起止时间 2008 年6月 2日至 2008 年 6月 6 日。目录。1 问题描述 2 1.1 题目内容 2 1.2 基本要求 2 1.3 测试数据 2 2...
数据结构课程设计
数据结构 课程设计。实验报告。学院 信息工程学院。班级 姓名 学号 指导老师 题目2 一元多项式的计算。1 实验目的。1 掌握链表的灵活运用 2 学习链表初始化和建立一个新的链表 3 知道怎样去实现链表删除结点操作与插入结点 4 理解链表的基本操作 包括数据域数据的相加 并能灵活运用。2 实验内容。...
数据结构课程设计
班级 信计 1102 姓名 李娜娜。学号 1108060209 设计日期 2013.07.15 西安科技大学计算机学院 1.实验题目 编制一个演绎扫雷游戏的程序。2.问题描述。做一个n x m的扫雷游戏，每个方格包含两种状态 关闭 closed 和打开 opened 初始化时每个方格都是关闭的，一个...