数据结构实验-二叉排序树应用实验报告.doc_第1页
数据结构实验-二叉排序树应用实验报告.doc_第2页
数据结构实验-二叉排序树应用实验报告.doc_第3页
数据结构实验-二叉排序树应用实验报告.doc_第4页
数据结构实验-二叉排序树应用实验报告.doc_第5页
已阅读5页,还剩10页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

实 验 报 告 实验课程:数 据 结 构 实验项目:实验四二叉排序树应用 专 业:计算机科学与技术 班 级: 姓 名: 学 号: 指导教师: 目 录1、 问题定义及需求分析 (1)问题描述 (2)实验任务 (3)需求分析二、概要设计: (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系3、 详细设计 (1)数据类型及存储结构 (2)模块设计4、 调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会5、 使用说明 (1)程序使用说明6、 测试结果 (1)运行测试结果截图7、 附录 (1)源代码1、 问题定义及需求分析(1)实验目的 二叉排序树应用 问题描述 互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域,如cn、com等,最底层(第四层)是叶子结点,如www等。因此,域名搜索可以构造树的结构完成;(2)实验任务 设计基于二叉排序树的搜索互联网域名的程序。(3)需求分析: 1)采用二叉树的二叉链表存储结构。 2)完成二叉排序树的创建、插入、删除、查询操作。 3)可以考虑两棵二叉排序树的合并。2、 概要设计:(1)抽象数据类型定义: 程序中定义了二叉排序树的节点类型;由数据域和左右孩子指针构成;指针类型为该节点类型,指向该类型的节点形成二叉排序树;数据域是由字符数组构成,用于存储节点数据信息。(2) 主程序流程: 输入域名 拆分域名并完成二叉排序树的创建 调用功能函数进入功能菜单 选择执行不同的操作(查找、插入、删除) 操作完毕后可选择返回功能函数继续执行操作或者结束程序 (3) 模块间的调用关系: 创建二叉排序树 功能函数 查找 插入 删除 选择 结束 三、详细设计 采用二叉链表存储结构的二叉排序树的定义如下: typedef struct BiTNodeElemType data30; /定义数据域类型为字符数组 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)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)lchild = s; /* 插入s为左孩子 */ else p-rchild = s; /* 插入s为右孩子 */ return 1; else return 0; /* 树中已有关键字相同的结点,不再插入 */模块3-删除节点算法如下:int Delete(BiTree *p) BiTree q,s; if(*p)-rchild=NULL) /* 右子树空则只需重接它的左子树(待删结点是叶子也走此分支) */ q=*p;*p=(*p)-lchild;free(q); else if(*p)-lchild=NULL) /* 只需重接它的右子树 */ q=*p; *p=(*p)-rchild; free(q); else /* 左右子树均不空 */ q=*p; s=(*p)-lchild; while(s-rchild) /* 转左,然后向右到尽头(找待删结点的前驱) */ q=s; s=s-rchild; strcpy(*p)-data,s-data); /* s指向被删结点的直接前驱(将被删结点前驱的值取代被删结点的值) */ if(q!=*p) q-rchild=s-lchild; /* 重接q的右子树 */ else q-lchild=s-lchild; /* 重接q的左子树 */ free(s); return 1;模块4-查找待删除节点的位置算法如下:int DeleteBST(BiTree *T,char *key) if(!*T) /* 不存在关键字等于key的数据元素 */ return 0; else if (strcmp(key,(*T)-data)=0) /* 找到关键字等于key的数据元素 */ return Delete(T); else if (strcmp(key,(*T)-data)lchild,key);/* 若待删除节点大于当前节点,则递归访问其左子树 */ else return DeleteBST(&(*T)-rchild,key);/* 否则访问右子树 */ 模块5-功能函数包括查找、插入和删除算法如下:void Gongneng(BiTNode *A)/ 执行操作需将此树的根节点传入到此函数里面int k;char a30,c30,d30;printf(请选择你的操作:n);printf(1-查找n);printf(2-删除n);printf(3-插入n);printf(输入:);scanf(%d,&k);switch(k)/通过switch语句执行不同的操作case 1 :system(cls);printf(请输入你要查找的节点:);scanf(%s,c); Search(A, c); /调用查找函数 break;case 2:system(cls);printf(请输入你要删除的节点:);scanf(%s,a);if(!DeleteBST(&A,a)printf(n不存在此节点!n);elseprintf(n删除节点成功!nn删除后树的中序遍历结果如下:n);InOrder(A); break;case 3:system(cls);printf(请输入要插入的节点:);scanf(%s,d);if(!InsertBST(&A,d)printf(插入失败!要插入的节点已存在!n);elseprintf(n插入成功!nn插入后树的中序遍历结果如下:n); InOrder(A);break; default : printf(输入数值错误!n);四、调试分析 问题及解决方法: 在编写功能函数时,在参数的传递上出现了问题;无法正确的将根节点传入到功能函数里,导致功能函数无法正常运行;解决方法为:void Gongneng(BiTNode *A); 时空分析: 由于采用二叉链表的存储结构,所以在插入和删除算法的时间复杂度较低;而对于较多的数据元素形成的树时,查找算法在时间复杂度上不算简便;而存储方面,二叉链表构成的二叉排序树存储较为方便且空间利用率高; 经验体会: 二叉链表存储结构的存储密度较高,使用起来较为方便;而且在处理数据方面,二叉链表存储结构的处理性比较好,尤其是对插入和删除算法;五、使用说明第一步:点击运行按钮;第二步: 输入待输入的域名个数k;第三步:依次输入k个域名;第四步:回车,程序跳转至功能界面,根据提示输入想要执行的功能选项序号;第五步:回车后,针对各功能项有提示药查找、插入或者删除的节点;第六步: 执行功能后,选择结束运行还是继续操作;第七步:若选择继续操作,则程序进入功能界面,可继续选择执行的功能;第八步:循环执行第四到七步;第九步:可在第六步选择退出程序;六、测试结果七、附录源代码:#include#include#include#define ElemType chartypedef struct BiTNodeElemType data30; /定义数据域类型为字符数组 struct BiTNode *lchild, *rchild; /定义左右孩子节点指针BiTNode, *BiTree;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; /p指向查找到的节点 return 1; else if (strcmp(key,T-data)lchild, key, T, p); / 在左子树中继续查找 else return SearchBST(T-rchild, key, T, p); / 在右子树中继续查找 int InsertBST(BiTree *T, char *key) BiTree p,s; if (!SearchBST(*T, key, NULL, &p) / 查找不成功 s = (BiTNode*)malloc(sizeof(BiTNode);/s作为插入节点strcpy(s-data, key); s-lchild = s-rchild = NULL; if (!p) *T = s; / 插入s为新的根结点 else if (strcmp(key,p-data)lchild = s; / 插入s为左孩子 else p-rchild = s; / 插入s为右孩子 return 1; else return 0; / 树中已有关键字相同的结点,不再插入int Search(BiTNode *N,char *key) / 查找树中是否存在要插入的节点 BiTNode *M; M=N; while(M!=NULL&strcmp(M-data,key)!=0) / 查找终止条件为树为空或者查找的节点数据与待查找的数据相同 if(strcmp(M-data,key)rchild; / 继续查找左子树 else M=M-lchild; / 继续查找右子树 if(!M) printf(查找失败!n); else printf(查找成功!n);/* 从二叉排序树中删除结点p,并重接它的左或右子树。 */int Delete(BiTree *p) BiTree q,s; if(*p)-rchild=NULL) / 右子树空则只需重接它的左子树(待删结点是叶子也走此分支) q=*p;*p=(*p)-lchild;free(q); / 释放该节点 else if(*p)-lchild=NULL) / 只需重接它的右子树 q=*p; *p=(*p)-rchild; free(q); / 释放该节点 else / 左右子树均不空 q=*p; s=(*p)-lchild; while(s-rchild) / 转左,然后向右到尽头(找待删结点的前驱) q=s; s=s-rchild; strcpy(*p)-data,s-data); / s指向被删结点的直接前驱(将被删结点前驱的值取代被删结点的值) if(q!=*p) q-rchild=s-lchild; / 重接q的右子树 else q-lchild=s-lchild; /重接q的左子树 free(s); return 1;int DeleteBST(BiTree *T,char *key) if(!*T) /不存在关键字等于key的数据元素 return 0; else if (strcmp(key,(*T)-data)=0) /找到关键字等于key的数据元素 return Delete(T); /调用Delete函数删除该节点 else if (strcmp(key,(*T)-data)lchild,key);/ 继续访问左子树 else return DeleteBST(&(*T)-rchild,key);/继续访问右子树 void InOrder (BiTNode *root) /中序遍历该二叉排序树if (!root) return ; /递归结束条件InOrder (root-lchild); /递归访问左子树printf (%sn, root-data);/访问根节点信息InOrder (root-rchild);/递归访问右子树void Gongneng(BiTNode *A)int k;char a30,c30,d30;printf(请选择你的操作:n);printf(1-查找n);printf(2-删除n);printf(3-插入n);printf(输入:);scanf(%d,&k);switch(k)case 1 :system(cls);printf(请输入你要查找的节点:);scanf(%s,c); Search(A, c);/调用查找函数 break;case 2:system(cls);printf(请输入你要删除的节点:);scanf(%s,a);if(!DeleteBST(&A,a)printf(n不存在此节点!n);elseprintf(n删除节点成功!nn删除后树的中序遍历结果如下:n);InOrder(A);/删除后,进行一次遍历检查删除后的二叉排序树 break;case 3:system(cls);printf(请输入要插入的节点:);scanf(%s,d);if(!InsertBST(&A,d)printf(插入失败!要插入的节点已存在!n);elseprintf(n插入成功!nn插入后树的中序遍历结果如下:n); InOrder(A);/插入成功后,中序遍历该

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论