资源描述:
《数据结构实验报告动态查找表》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、数据结构实验报告题目:动态查找表学院计算机学院专业计算机科学与技术年级班别2010级计科4班学号3110006015学生姓名张法光指导教师张巍成绩____________________2012年6月1.题目动态查找表的设计与实现实现下列操作:构造空表、销毁表、查找关键字的元素、插入新元素、删除指定关键字的元素、遍历表中所有元素.抽象数据类型定义:ADTDynamicSearchTable{数据对象D:D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同,可唯一标识数据元素的关键字数据关系R:数据元素同属一个集合。基本
2、操作P:InitDSTable(&DT);操作结果:构造一个空的动态查找表DT。DestroyDSTable(&DT)初始条件:动态查找表DT存在。操作结果:销毁动态查找表DT。SearchDSTable(DT,key);初始条件:动态查找表DT存在,key为和关键字类型相同的给定值。操作结果:若DT中存在其关键字等于key的数据元素,则函数值为该元素的值或在表中的位置,否则为“空”。InsertDSTable(&DT,e);初始条件:动态查找表DT存在,e为待插入的数据元素。操作结果:若DT中不存在其关键字等于e.key的数
3、据元素,则插入e到DT。DeleteDSTable(&DT,key);初始条件:动态查找表DT存在,key为和关键字类型相同的给定值。操作结果:若DT中存在其关键字等于key的数据元素,则删除之。TraverseDSTable(DT,visit());初始条件:动态查找表DT存在,visit是对结点操作的应用函数。操作结果:按某种次序对DT的每个结点调用函数visit()一次且至多一次,一旦visit()失败,则操作失败。}ADTDynamicSearchTable2.存储结构定义:公用头文件DS0.h和宏定义:#includ
4、e#include#defineTRUE1/*TRUE函数值为1*/#defineFALSE0#defineN10/*数据元素个数*/typedefintStatus;/*Status为函数类型*/typedefintKeyType;/*关键字域为整型*/#defineEQ(a,b)((a)==(b))/*定义等于*/#defineLT(a,b)((a)<(b))/*定义小于*/二叉排序树存储结构:二叉排序树的类型BiTree定义如下:typedefintKeyType;/*关键字域为整型
5、*/typedefstruct{KeyTypekey;intothers;}ElemType;/*数据元素类型*/typedefElemTypeTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;/*左右孩子指针*/}BiTNode,*BiTree;3.算法设计/*操作结果:构造一个空的动态查找表DT*/StatusInitDSTable(BiTree*DT){*DT=NULL;returnTRUE;}/*初始条件:动态查找表DT存
6、在。操作结果:销毁动态查找表DT*/voidDestroyDSTable(BiTree*DT){if(*DT){if((*DT)->lchild)DestroyDSTable(&(*DT)->lchild);/*销毁左孩子子树*/if((*DT)->rchild)DestroyDSTable(&(*DT)->rchild);/*销毁右孩子子树*/free(*DT);*DT=NULL;}}/*在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素,*//*若查找成功,则返回指向该数据元素结点的指针,否则返回空指针。*/
7、BiTreeSearchBST(BiTreeT,KeyTypekey){if((!T)
8、
9、EQ(key,T->data.key))returnT;/*查找结束*/elseifLT(key,T->data.key)/*在左子树中继续查找*/returnSearchBST(T->lchild,key);elsereturnSearchBST(T->rchild,key);/*在右子树中继续查找*/}/*在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素,若查找*//*成功,则指针p指向该数据元素结点,并返回TRUE,
10、否则指针p指向查找路径上*//*访问的最后一个结点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL*/voidSearchBST1(BiTree*T,KeyTypekey,BiTreef,BiTree*p,Status*flag){if(!*T)/*查找不成功*/