数据结构实验报告之静态查找表.doc

《数据结构实验报告之静态查找表.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.数据结构实验报告题目：静态查找表的实现成绩____________________2014年6月10号静态查找表抽象数据类型的实现 一、设计任务、要求及所用的软件环境或工具： 1.设计任务及要求：用C语言实现静态查找表的抽象数据类型 2.软件环境：win7 3.开发工具：C-Free二、抽象数据类型的实现1.题目采用顺序存储和链式存储为存储结构，实现抽象数据类型StaticSearchTable。..ADTStaticSearchTable{数据对象D：D是具有相同特性的数据元素的集合。各个数据元素含有类型相同的关键字，可唯一标识元素的关键字

2、。数据关系R：数据元素同属一个集合。基本操作P：Create(&ST,n);操作结果：构造一个含n个数据元素的静态查找表ST。Destroy(&ST);初始条件：静态查找表ST存在。操作结果：销毁表ST。Search(ST,key);初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。操作结果：若ST中存在其关键字等于key的数据元素，则函数值为其值或在表中的位置，否则为“空”。Traverse(ST,Visit());初始条件：静态查找表ST存在，Visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用函数Vis

3、it()一次且仅一次。一旦Visit()失败，则操作失败。}ADTStaticSearchTable2．存储结构定义*公用头文件DS0.h:#include#include #include *预定义常量和类型//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;typedefintKeyType;typedeffloatKeyType;typedefcharKeyType;typedefintE

4、lemType;typedefElemTypeTElemType;1)顺序存储结构typedefstruct{..ElemType*elem;//数据元素存储空间基址，0号单元留空intlength;//表长}SSTable;2)二叉链表存储结构typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;3.算法设计1)顺序表的查找voidCreat_Seq(SSTable*ST,ElemTyper[],intn){inti;(

5、*ST).elem=(ElemType*)calloc(n+1,sizeof(ElemType));//动态生成n+1个数据元素空间(0号单元不用)if(!(*ST).elem)exit(0);for(i=1;i<=n;i++)(*ST).elem[i]=r[i-1];//将数组r的值依次赋给ST(*ST).length=n;}StatusDestroy_Seq(SSTable&ST){free(ST.elem);ST.elem=NULL;ST.length=0;returnOK;}intSearch_Seq(SSTableST,KeyType

6、key){inti;ST.elem[0].key=key;//哨兵for(i=ST.length;!(ST.elem[i].key==key);--i);//从后往前找returni;//找不到时，i为0}voidTraverse(SSTableST,void(*Visit)(ElemType)){ElemType*p;inti;p=++ST.elem;//p指向第一个元素for(i=1;i<=ST.length;i++)Visit(*p++);}..2)有序表的查找intSearch_Bin(SSTableST,KeyTypekey){int

7、low,high,mid;low=1;high=ST.length;//置区间初值while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid])returnmid;//找到待查元素elseif(key

8、loc(n+1,sizeof(ElemType));//动态生成n+1个数据元素空间(0号单元不用)if(!(*ST).elem)exit(0);fo