欢迎来到天天文库
浏览记录
ID:53773289
大小:336.00 KB
页数:10页
时间:2020-04-06
《数据结构实验报告之静态查找表.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(key8、loc(n+1,sizeof(ElemType));//动态生成n+1个数据元素空间(0号单元不用)if(!(*ST).elem)exit(0);fo
8、loc(n+1,sizeof(ElemType));//动态生成n+1个数据元素空间(0号单元不用)if(!(*ST).elem)exit(0);fo
此文档下载收益归作者所有