HUNAN UNIVERSITY
课程实习报告
题 目： 实验3 BST
学生姓名
学生学号
专业班级
指导老师 李晓鸿
完 成 日 期 2014年12月2日
一、需求分析
1． 本程序要求利用二叉查找树（BST）实现动态查找。
2． 二叉树（BST）使用链式结构（二叉链表）实现。
3． 实现 BST 的构建，查找两个功能。
4． 输入输出要求：
（1）输入要求：输入存储元素的个数 n 为正整数；假设所输入的 n 个元素的值全部为正整数；所要查找元素的值为正整数；
（2）输出要求：输出是否找到（查找成功\不成功）和查找时比较的次数（正整数）；
5． 输入：
8 //BST 的节点个数
34, 76, 45, 18, 26, 54, 92, 65 //8 个数据，存储在节点
45 //查找 45
34 //查找 34
100 //查找 100
输出：
查找成功 3 //返回是否查找成功和查找时比较的次数
查找成功 1 //返回是否查找成功和查找时比较的次数
查找不成功 3 //返回是否查找成功和查找时比较的次数
二、概要设计
抽象数据类型
在本次实验中，并未给出数据的具体个数，所以使用链表来存储输入的数据。由于题目的最终要求是实现一个动态查找表，对于构建和检索，利用BST来查找时能将时间复杂度降到最低，故使用BST来实现动态查找表，实现任意个数的数据的增删和查找。
抽象数据类型定义如下：
// 二叉树
数据：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n }
基本操作： Node()
{
//用来初始化二叉树节点
}
BST()
{
//构建空二叉树
}
bool insert(const int& e)
{
//将数据不断插入到二叉树中
}
bool inserthelp(Node<*inserthelp(Node*, const int&);
{
//将元素存储到二叉树节点
)
bool searchTree(Node*subroot,int searchData)
{
//查找数据
}
算法的基本思想
首先创建二叉树，将键入的数据全部存储到树的节点中。同时设置变量 count 用来计数比较次数，并初始化为 0。然后遍历二叉树，和所要查找的数比较，每比较一次，count 加 1。如果相同，则停止遍历，输出查找成功及比较次数 count。如果不相同，则继续遍历二叉树。直至所访问的节点为叶子节点且该叶子节点所存储的值与查找数不同，可判定在二叉树中不存在与查找数相同的数据，则输出查找不成功及比较次数 count。
程序的流程
1. 输入模块：输入二叉树的元素个数、元素的值，以及要查找的数。并且将所输入的 元素插入到二叉树中。
2. 操作模块：通过二叉树的基本操作，检索该元素是否在二叉树中。
3. 输出模块：输出查找结果及比较次数。
三、详细设计
物理数据类型
因为要实现一个动态查找表，对一个数进行查找，用线性表实现所用的时间代
价比较高，而用二叉树来实现的话时间代价明显降低，同时输入数据的数量由用户决定，所以可以使用二叉链表来实现数据的动态查找。
具体步骤伪代码：
1. 二叉查找树节点的定义
class Node {
public
int data； //二叉树节点存储的值
Node *leftchild，*rightchild； //左右孩子指针
Node() //初始化节点
{
leftchild=NULL;
rightchild=NULL:
data=0;
}
}
2. 二叉树的定义
class BST :
{
public:
Node*subroot; // Root of the BST
Node<*inserthelp(Node*, const int&);
BST()
{
subroot = NULL;
}
bool insert(const int& e)
{
subroot = inserthelp(subroot, e); //调用inserthelp插入节点
return true;
}
Node*inserthelp(Node* subroot,const int& val)
{
if (subroot== NULL)
{
//将数据直接插入该节点
subroot->data=val;
}
else // (subroot!=NULL)
{
if(val<(*subroot)->data)
{
subroot->leftchild(inserthelp(subroot->leeftchild,val));
}
else{
subroot->rightchild(inserthelp(subroot->rightchild,val));
}
}
return subroot;
}
bool searchTree(Node*subroot,int searchData)
{
if(subroot!=NULL){
count++; //比较一次，计数器加 1
if(searchData<subroot->data)
return search(subroot->leftchild,searchData);
else if(searchData>subroot->data)
return search(subroot->rightchild,searchData);
else
cout<<”查找成功 ” <<count<<endl;
}
else{
cout<<”查找不成功 ”<<count；
return 0;
}
}
};
2. 二叉查找树的构建
在构建二叉查找树的时候主要使用的是递归的方法。
首先构建空树BSTree
for(int i=0;i<n;i++)
{
cin>>data;
BSTree.inert();
}
3. 二叉查找树的查找
bool searchTree(Node*subroot,int searchData)
{
if(subroot!=NULL){
count++; //比较一次，计数器加 1
if(searchData<subroot->data)
return search(subroot->leftchild,searchData);
else if(searchData>subroot->data)
return search(subroot->rightchild,searchData);
else
cout<<”查找成功 ” <<count<<endl;
}
else{
cout<<”查找不成功 ”<<count；
return 0;
}
}
4. 数据的插入
//当查找不成功时，插入所查找的数据
void insertNewdata(Node*subroot,int searchData)
{
if(searchData<subroot->data)
inset(subroot->leftchild,searchData);
else
inset(subroot->rightchild,searchData);
}
算法的具体步骤：
(1) 首先定义节点类型，
(2) 构建二叉查找树。在构建过程中，主要使用递归的方法。
a. 判断根结点是否为空。若为空，则输入的数据插入到该根结点。
b. 若不为空，则判断是否输入数据小于根结点。若小于根结点，则返回根结点的左孩子，否则返回根结点的右孩子。
c. 判断所返回的结点是否为空。若为空，则输入的数据插入到该结点。
d. 若不为空，则判断是否输入数据小于该结点。若小于该结点，则返回该结点的左孩子，否则返回该结点的右孩子。
e. 重复 c、d 步骤，直到 n 个元素均被存储。
(3) 查找数据。在查找的过程中主要使用递归的方法。
a. 判断根结点是否为空，若为空，则返回查找不成功。
b. 若不为空，则判断查找数是否小于根结点。若小于，则返回根结点的左孩子。若大于，则返回根结点的右孩子。若相等，则输出“查找成功”，同时输出查找次数 count++，并结束查找。
c. 判断所返回的结点是否为空。若为空，则输出“查找不成功”及查找次数 count++。
d. 若不为空，则判断查找数是否小于该结点。若小于，则返回该结点的左孩子。若大于，则返回该结点的右孩子。若相等，则输出“查找成功”，同时输出查找次数 count++，并结束查找。
e. 重复 c、d 步骤。
(4) 插入数据。当查找不成功时，所查找的根节点一定是叶子节点，则判断查找数是否小于该结点。若小于，插入新数据到左孩子，否则插入右孩子。
算法的时空分析
在构建 BST 的时候，每次插入操作为 O(1)，构建二叉树完成时操作次数为n;查找时，最差情况遍历次数为二叉树的深度，所以每次操作次数为logn；即该算法的复杂度为 O(n)。
四、输入输出格式
输入：
8 //BST 的节点个数
34, 76, 45, 18, 26, 54, 92, 65 //8 个数据，存储在节点
45 //查找 45
34 //查找 34
100 //查找 100
输出：
查找成功 3 //返回是否查找成功和查找时比较的次数
查找成功 1 //返回是否查找成功和查找时比较的次数
查找不成功 3 //返回是否查找成功和查找时比较的次数
五、调试结果及分析
第二篇：数据结构实验(3)
数据结构实验
实验三 实验3.4
班级：信安1002
学号：0705100228
姓名：余丹
一、 实验题目 编写一个程序algo3-4.cpp，实现双链队的各种基本运算，并在此基础上设计一个主程序完成如下功能：
（1） 初始化链队q；
（2） 判断链队q是否为空；
（3） 依次进队元素a,b,c；
（4） 出队一个元素，输出该元素；
（5） 输出链队q的元素个数；
（6） 依次进链队元素d,e,f；
（7） 输出链队q的元素个数；
（8） 输出出队序列；
（9） 释放链队。
二、 实验目的 通过实验巩固对链队的各种基本运算的操作。
三、 实验过程
#include<stdio.h>
#include<malloc.h>
typedef struct qnode
{
char data;
struct qnode *next;
}QNode;
typedef struct
{
QNode *front;
QNode *rear;
}LiQueue;
void InitQueue(LiQueue *&q)//初始化队列
{
q=(LiQueue *)malloc(sizeof(LiQueue));
q->front=q->rear=NULL;
}
void ClearQueue(LiQueue *q)//销毁队列
{
QNode *p=q->front,*r;
if(p!=NULL)
{
r=p->next;
while(r!=NULL)
{
free(p);
p=r;
r=p->next;
}
}
free(p);
}
int QueueEmpty(LiQueue *q)//判断队列是否为空
{
if(q->rear==NULL)
return 1;
else
return 0;
}
void enQueue(LiQueue *&q,char e)//入队列
{
QNode *s;
s=(QNode *)malloc(sizeof(QNode));
s->data=e;
s->next=NULL;
if(q->rear==NULL)
q->front=q->rear=s;
else
{
q->rear->next=s;
q->rear=s;
}
}
int deQueue(LiQueue *&q,char &e)//出队列
{
QNode *t;
if(q->rear==NULL)
return 0;
t=q->front;
if(q->front==q->rear)
q->front=q->rear=NULL;
else
q->front=q->front->next;
e=t->data;
free(t);
return 1;
}
int QueueLength(LiQueue *q)//输出链队长度
{
QNode *r=q->front;
int i=1;
if(q->rear!=NULL)
{
while(q->front!=q->rear)
{
i++;
q->front=q->front->next;
}
}
q->front=r;
return (i);
return (0);
}
void main()
{
LiQueue *q;
char a,e;
int N,i;
FILE *fp;
fp=fopen("D://out.txt","w+");
FILE *op;
op=fopen("D://push.txt","r+");
fprintf(fp,"(1)初始化链队\n");
printf("(1)初始化链队\n");
InitQueue(q);
fprintf(fp,"(2)判断链队是否为空:");
printf("(2)判断链队是否为空:");
if(QueueEmpty(q))
{
fprintf(fp,"YES\n");
printf("YES\n");
}
else
{
fprintf(fp,"NO\n");
printf("NO\n");
}
printf("从文件中读入几个元素:");
fprintf(fp,"从文件中读入几个元素:");
fscanf(op,"%d",&N);
printf("%d",N);
fprintf(fp,"%d",N);
fprintf(fp,"\n(3)依次进队元素:");
printf("\n(3)依次进队元素:");
fscanf(op,"\n");
for(i=1;i<=N;i++)
{
fscanf(op,"%c",&a);
printf("%c",a);
fprintf(fp,"%c",a);
enQueue(q,a);
}
fprintf(fp,"\n(4)出队一个元素：");
printf("\n(4)出队一个元素：");
deQueue(q,e);
fprintf(fp,"%c\n",e);
printf("%c\n",e);
fprintf(fp,"(5)链队的元素个数:%d\n",QueueLength(q));
printf("(5)链队的元素个数:%d\n",QueueLength(q));
fscanf(op,"\n");
printf("从文件中读入几个元素:");
fprintf(fp,"从文件中读入几个元素:");
fscanf(op,"%d",&N);
printf("%d\n",N);
fprintf(fp,"%d\n",N);
fprintf(fp,"(6)依次进队元素:");
printf("(6)依次进队元素:");
fscanf(op,"\n");
for(i=1;i<=N;i++)
{
fscanf(op,"%c",&a);
printf("%c",a);
fprintf(fp,"%c",a);
enQueue(q,a);
}
fprintf(fp,"\n(7)链队的元素个数:%d\n",QueueLength(q));
printf("\n(7)链队的元素个数:%d\n",QueueLength(q));
fprintf(fp,"(8)输出出队序列:");
printf("(8)输出出队序列:");
while(q->front!=NULL)
{
deQueue(q,e);
fprintf(fp,"%c",e);
printf("%c",e);
}
fprintf(fp,"\n");
printf("\n");
fprintf(fp,"(9)释放链队\n");
printf("(9)释放链队\n");
}
进队
出队
四、 实验结果
