数据结构实验-二叉排序树应用实验报告

实 验 报 告

实验课程：数 据 结 构

实验项目：实验四二叉排序树应用

专 业：计算机科学与技术

班 级：

姓 名：

学 号：

指导教师：

目 录

一、问题定义及需求分析

（1）问题描述

（2）实验任务 （3）需求分析

二、概要设计： (1)抽象数据类型定义

(2)主程序流程 (3) 模块关系

三、详细设计

(1)数据类型及存储结构

(2)模块设计

四、调试分析

(1)调试分析 (2)算法时空分析 (3)经验体会

五、使用说明 (1)程序使用说明 六、测试结果

(1)运行测试结果截图 七、附录

(1)源代码

一、问题定义及需求分析

（1）实验目的 二叉排序树应用 问题描述

互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如cn、com等，最底层（第四层）是叶子结点，如www等。因此，域名搜索可以构造树的结构完成；

（2）实验任务

设计基于二叉排序树的搜索互联网域名的程序。

（3）需求分析：

1）采用二叉树的二叉链表存储结构。

2）完成二叉排序树的创建、插入、删除、查询操作。 3）可以考虑两棵二叉排序树的合并。

二、概要设计：

(1)抽象数据类型定义：

程序中定义了二叉排序树的节点类型；由数据域和左右孩子指针构成；指针类型为该节点类型，指向该类型的节点形成二叉排序树；数据域是由字符数组构成，用于存储节点数据信息。

(2)主程序流程：

输入域名 拆分域名并完成二叉排序树的创建 调用功能函数进入功能菜单 选择执行不同的操作(查找、插入、删除) 操作完毕后可选择返回功能函数继续执行操作或者结束程序 (3)模块间的调用关系:

创建二叉排序树

功能函数

查找 插入 删除

选择

结束

三、详细设计

采用二叉链表存储结构的二叉排序树的定义如下： typedef struct BiTNode {

ElemType data[30]; //定义数据域类型为字符数组

struct BiTNode *lchild, *rchild; //定义左右孩子节点指针 }BiTNode, *BiTree;

模块1-查找树中是否有待插入节点

算法如下：

int SearchBST(BiTree T, char *key, BiTree f, BiTree *p) {

if (!T) /* 查找不成功 */ {

*p = f; return 0; }

else if(strcmp(key,T->data)==0) /* 查找成功 */ {

*p = T; return 1; }

else if (strcmp(key,T->data)<0)

return SearchBST(T->lchild, key, T, p); /* 若该节点小于当前节点，则在左子树中继续查找 */ else

return SearchBST(T->rchild, key, T, p); /* 否则在右子树中继续查找 */ }

模块2-插入节点

算法如下：

int InsertBST(BiTree *T, char *key) {

BiTree p,s;

if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */ {

s = (BiTNode*)malloc(sizeof(BiTNode)); strcpy(s->data, key);

s->lchild = s->rchild = NULL; if (!p)

*T = s; /* 插入s为新的根结点 */ else if (strcmp(key,p->data)<0)

p->lchild = s; /* 插入s为左孩子 */