实验7:动态查找表的设计与实现

实验7:动态查找表的设计与实现

ID:35342186

大小:69.95 KB

页数:9页

时间:2019-03-23

实验7:动态查找表的设计与实现_第1页
实验7:动态查找表的设计与实现_第2页
实验7:动态查找表的设计与实现_第3页
实验7:动态查找表的设计与实现_第4页
实验7:动态查找表的设计与实现_第5页
资源描述:

《实验7:动态查找表的设计与实现》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、指导教师:2009秋季学期【实验题目】实验7:动态查找表的设计与实现【问题描述】实现抽象数据类型:二叉查找树。【基本要求】实现下列操作:构造空表、销毁表、搜索指定关键字的元素、插入新元素、删除指定关键字的元素、遍历表中所有元素.一、【概要设计】1•抽象数据类型的功能规格说明:ADTDynamicSearchTabIe{数据对象:D是具有相同特性的数据元素的集合,各个数据元素均含有类型相同,可唯一标识数据元素的关键字。数据关系:数据元素同属一个集合。基本操作:BSPInitBST(BiTree&T)操作结果:构造一棵空树BSPcreateBst(key)操作结果:建立一个二

2、叉树结点voidtraverseBST(BSPT)操作结果:中序遍历(递归〉动态查找表(二叉链表〉,并打印结点值BSPFindMin(BSPT)操作结果:找到关键字最小的结点,即最左边的节点intSearchBST(BiTreeT,intkey,BiTreef,BiTree&p)操作结果:在根指针T所指的二叉树中递归地查找其关键字等于key的元素,查找成功:指针p指向该结点,并返回TRUE,否则:p指向查找路径上访问的最后一个结点,即插入位置,并返回FALSEintInsertBST(BiTree&T,TEIemTypee)当二叉树T中不存在关键字等于e.key的数据元素

3、事,插入e并返回TRUE,否则返回FLASEintDeIeteBST(BiTree&T,intkey)操作结果:查找树T中是否存在关键字等于key的数据元素,存在:删除,并返回TRUE,不存在:返回FALSEvoidDestoryBST(BiTree&T)操作结果:销毁二叉树}ADTDynamicSearchTabIe2.主程序模块与各子程序模块间的调用关系:intmain()wNTeOswitch()createBst(key)InsertBST(T,S)traverseBST(T)Search(T,key)DeleteBST(T,key)DestroyBST(T)二、

4、【详细设计】1.抽象数据类型具体实现的函数原型说明:typedefintkeytype;〃定义关键字类型typedefstructBnode{keytypedata;structBnode*Ichild,*rchild;JBSVBSP;//定义树节点类型2•函数的调用关系:(在main函数中〉intselect=O,flag=l,a;〃操作选择字符,循环控制字符,查找函数返回值接受符T=NULL;while(flag){〃操作选择printf(Hl—创建2叉查找树十);printf(**2…插入元素H);printf(n3…查找元素H);printf(u4…删除

5、元素H);printf(n5…删除表H);printf(n6…退出H);printfC1请选择操做十);scanf(n%dM,&select);switch(select){case1:{〃创建二叉查找表printf(M请输入关键字,0结束M);scanf(n%dM,&key);while(key!=0){S=createBst(key);T=InsertBST(T,S);printf(n请继续输入:”);scanf(n%dn,&key);}printf(M查找表为n);traverseBST(T);printf(nM);break;}cas

6、e2:{〃插入元素printf(M请输入要插入的元素;n);scanf(H%dM,&key);S=createBst(key);T=InsertBST(T,S);printf(H插入成功n);printf(M插入的元素为:M);traverseBST(S);printf(nM);break;}case3:{〃查找元素printf(n请输入要查找的元素:n);scanf(H%dn,&key);a=Search(T,key);printf(HM);break;case4:{〃删除元素printf(n请输入要删除的元素:M);scanf(

7、H%dn,&key);DeleteBST(T,key);printf(MH);break;}case5:{//销毁二叉查找表DestroyBST(T);printf(u删除成功”);}case6:{〃退出flag=0;break;}}}}3、其中部分操作的伪码算法如下:1)BSPInitBST(){BSPT;T->data=0;T->Ichild=T->rchild=NULL;returnT;}2)voidDestroyBST(BSPT){if(T){〃中序删除各结点DestroyBST(T->lchild);T->d

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。