搜索
实习报告一、需求分析1、问题描述利用平衡二叉树实现一个动态查找表。（1）实现动态查找表的三种基本功能：查找、插入和删除。（2）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。在查找时，如果查找的关键字不存在，则把其插入到平衡二叉树中。每次插入或删除一个结点后，应更新平衡二叉树的显示。（3）每次操作的关键字都要从文件中读取，并且关键字的集合限定为短整型数字{1，2，3······}，关键字出现的顺序没有限制，允许出现重复的关键字，并对其进行相应的提示。（4）平衡二叉树的显示采用图形界面画出图形。2、系统功能打开数据文件，用文件中的关键字来演示平衡二叉树操作的过程。3、程序中执行的命令包括：（1）(L)oadfromdatafile//在平衡的二叉树中插入关键字；（2）(A)ppendnewrecord//在平衡的二叉树中查找关键字；（3）(U)patespecialrecord//显示调整过的平衡二叉树；（4）(D)eletespecialrecord//删除平衡二叉树中的关键字；（5）(Q)uit//结束。4、测试数据：平衡二叉树为：图1插入关键字10之前的平衡二叉树插入关键字：10；调整后：图2插入关键字10之后的平衡二叉树删除关键字：14；调整后：图3删除关键字14后的平衡二叉树查找关键字：11；输出：Thedataishere!图3查找关键字11后的平衡二叉树二、概要设计本次实验目的是为了实现动态查找表的三种基本功能：查找、插入和删除。动态查找表可有不同的表示方法，在此次实验中主要是以平衡二叉树的结构来表示实现的，所以需要两个抽象数据类型：动态查找表和二叉树。1、动态查找表的抽象数据类型定义为：ADTDynamicSearchTable{数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属于一个集合。基本操作P：InitDSTable(&ST);操作结果：构造一个空的动态查找表DT。DestroyDSTable(&DT);初始条件：动态查找表DT存在。操作结果：销毁动态查找表DT。SearchDSTable(DT,key);初始条件：动态查找表DT存在，key为和关键字类型相同的给丁值。操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。InsertDSTable(&DT,e);初始条件：动态查找表DT存在，e为待插入的数据元素。操作结果：若DT中不存在其关键字等于e，key的数据元素，则插入e到DT；DeleteDSTable(&DT,key);初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。操作结果：若DT中存在其关键字等于key的数据元素，则删除之。}ADTDynamicSearchTable2、二叉树抽象数据类型的定义为：ADTBinaryTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=￠，则R=￠，称BinaryTree为空的二叉树；若D≠￠，则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D—{root}≠￠，则存在D—{root}={D1，Dr}，且D1∩Dr=￠;（3）若D1≠￠，则D1中存在唯一的元素x1，root，x1∈H，且存在D1上的关系H1∈H；若Dr≠￠，则Dr中存在唯一的元素xr，root，xr∈H，且存在Dr上的关系Hr∈H；H={root，x1，root，xr，H1，Hr}；（4）（D1，{H1}）是一棵符合本定义的二叉树，称为根的左子树，（Dr，{Hr}）是符合本定义的二叉树，称为根的右子树。基本操作P：InitBiTree(&T);操作结果：构造空的二叉树T；DestroyBiTree(&T);初始条件：二叉树T存在。操作结果：销毁二叉树T。CreateBiTree(&T,definition);初始条件：definition给出T的定义。操作结果：按definition构造二叉树T。BiTreeEmpty(T);初始条件：二叉树T存在。操作结果：若T为空二叉树，则返回TRUE，否则FALSE。LeftChild(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子，则返回“空”。RightChild(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子，则返回“空”。InsertAVL(T,e,taller);初始条件：二叉树T存在，e为要插入的结点，taller反映T长高与否。操作结果：若在平衡二叉树中不存在和e相同关键字的结点，则插入一个数据元素为e的结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则旋转处理。RightProcess(T);初始条件：二叉树T存在。操作结果：对以T为根的二叉树做右旋转处理，处理之后T指向新的树根结点。LeftProcess(T);初始条件：二叉树T存在。操作结果：对以T为根的二叉树做左旋转处理，处理之后T指向新的树根结点}3、本程序包括四个模块：（1）主程序模块：voidmain(){for(;;){switch(){接受命令；处理命令；}}}（2）二叉树单元模块：实现二叉树的抽象数据类型。（3）动态查找表单元模块：实现动态查找表的抽象数据类型。（4）结点结构模块：实现平衡二叉树的查找、插入和删除操作。各模块之间的关系：图4各模块之间的关系三、详细设计1、元素类型、结点类型和指针类型；typedefintInfoTypetypedefstructnode/*记录类型*/{主程序模块二叉树单元模块：动态查找表单元模块结点结构模块InfoTypedata;/*其他数据域*/Structnodelchild,rchild;/*左右孩子指针*/}BSTNode,*BSTree;statusMakeNode(BSTNode&p,ElemTypee){/*分配由p指向的数据元素为e、后继为空的结点,并返回TRUE,扩若分配失败,则返回FALSE*/p=(BSTNode*)malloc(sizeof(BSTNode);if(!p)returnFALSE;p-data=e;p-next=NULL;returnTRUE;}voidFreeNode(BSTNode&p){/*释放p所指结点*/}2、根据动态查找表的基本操作特点：表结构本身是在查找过程中动态产生的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。在此次试验中主要是利用平衡二叉树来实现动态查找表。平衡二叉排序树定义为：typedefintInfoTypetypedefintKeyType;/*元素类型*/typedefstructnode{KeyTypekey;/*关键字项*/intbf;/*平衡因子*/InfoTypedata;/*其他数据域*/Structnodelchild,rchild;/*左右孩子指针*/}BSTNode,*BSTree;inttaller;/*taller=0,平衡二叉数没有长高不需要调整；taller=1,二叉数长高,需要验证是否还是平衡二叉数,如果不是,则需要进行调整.*/平衡二叉树的基本操作定义如下：intInsertAVL(BSTNode*b,KeyTypee,int*m);//如果在平衡二叉排序树b中不存在e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0.如果因插入而使二叉排序树失去平衡，则做平衡处理，指针m反应b长高与否。voidLeftProcess(BSTree*p,int*m);//在插入结点时对以指针p所指结点为根的二叉树做左平衡旋转处理。voidRightProcess(BSTree*p,int*m);//在插入结点时对以指针p所指结点为根的二叉树做右平衡旋转处理。intDeleteAVL(BSTree*p,KeyTypex,int*m);///在以p为根的平衡二叉树中删除关键字为e的结点，如果因删除而使平衡二叉树失去平衡，则做平衡处理，指针m反应b树长高与否。voidLeftProcess1(BSTree*p,int*m);//由DeleteAVL()函数调用，在删除结点时进行左处理。voidRightProcess1(BSTree*p,int*m);//由DeleteAVL()函数调用，在删除结点时进行右处理。voidDelete2(BSTreeq,BSTree*r,int*m);//由DeleteAVL（）调用，用于处理被删除结点都不为空的情况。voidDrawTree(BSTreeb);//对以b为根的平衡二叉树，以括号的形式显示出来。voidOutputTree(BSTreeb,intfx,intfy,intprex,intprey);//用图形把平衡二叉树显示出来。3、本程序实现的是演示平衡二叉树的操作过程，包括插入和删除操作，以下是它们算法的设计。（1）插入数据操作，如果数据存在，输出提示信息，如果不存在，则把此数据插入到入平衡二叉树中，并做相应的调整，使之还为平衡二叉树。以下是对插入操作的设计。intInsertAVL(BSTree*b,KeyTypee,int*m)/*若在平衡的二叉排序树中b中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回0。若因插入而使二叉排序树失去平衡，则做平衡旋转处理，taller的值反应长高与否。*/{if(*b==NULL)/*原为空树，插入新结点，树长高，置taller=*m=1*/{(*b)=(BSTNode*)malloc(sizeof(BSTNode));(*b)-key=e;(*b)-lchild=(*b)-rchild=NULL;(*b)-bf=0;*m=1;}else{if(e==(*b)-key)/*树中已存在和e有相同关键字的结点，则不再进行插入*/{*m=0;/*置taller=*m=0,树没有长高，不须进行调整*/printf(\nThedataishere!\n);/*输出提示信息*/return0;}if(e(*b)-key)/*继续在*b的左子树中进行搜索*/{if((InsertAVL(&((*b)-lchild),e,&taller))==0)return0;/*存在和e有相同关键字的元素，则不需要插入*/if(taller==1)/*已插入在*b的左子树中且左子树长高*/LeftProcess(&(*b),&taller);}else/*已插入在*b的右子树中且左子树长高*/{if((InsertAVL(&((*b)-rchild),e,&taller))==0)return0;/*存在和e有相同关键字的元素则不需要插入*/if(taller==1)/*已插入在*b的右子树中且右子树长高*/RightProcess(&(*b),&taller);}}return1;}voidLeftProcess(BSTree*p,int*m)/*对以指针p所指结点为根的二叉树做左平衡旋转处理，算法结束后，指针p指向新的根结点*/{BSTNode*p1,*p2;if((*p)-bf==0)/*原本左右子树等高，现因左子树增高而使树增高*/{(*p)-bf=1;*m=1；}elseif((*p)-bf==-1)/*原本右子树比左子树高，现左右子树等高*/{(*p)-bf=0;*m=0;/*树没有长高*/}else/*原本左子树比右子树高，需做左子树的平衡处理*/{p1=(*p)-lchild;/*p1指向*p的左子树根结点*/if(p1-bf==1)/*新结点插入在*p的左孩子的右子树上，要做LL调整*/{(*p)-lchild=p1-rchild;/*p的左孩