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

..数据构造实验报告题目：静态查找表的实现成绩____________________2014年6月10号静态查找表抽象数据类型的实现一、设计任务、要求及所用的软件环境或工具：1.设计任务及要求：用C语言实现静态查找表的抽象数据类型2.软件环境：win73.开发工具：C-Free二、抽象数据类型的实现1.题目采用顺序存储和链式存储为存储构造，实现抽象数据类型StaticSearchTable。ADTStaticSearchTable{数据对象D：D是具有一样特性的数据元素的集合。各个数据元素含有类型一样的关键字，可唯一标识元素的关键字。数据关系R：数据元素同属一个集合。根本操作P：Create(&ST,n);操作结果：构造一个含n个数据元素的静态查找表ST。Destroy(&ST);初始条件：静态查找表ST存在。操作结果：销毁表ST。Search(ST,key);初始条件：静态查找表ST存在，key为和关键字类型一样的给定值。操作结果：假设ST中存在其关键字等于key的数据元素，那么函数值为其值或在表中的位置，否那么为"空〞。Traverse(ST,Visit());初始条件：静态查找表ST存在，Visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一次。一旦Visit()失败，那么操作失败。}ADTStaticSearchTable2．存储构造定义*公用头文件DS0.h:#include<stdio.h>#include<malloc.h>#include<math.h>*预定义常量和类型//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;typedefintKeyType;typedeffloatKeyType;typedefcharKeyType;typedefintElemType;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;(*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,KeyTypekey){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){intlow,high,mid;low=1;high=ST.length;//置区间初值while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid])returnmid;//找到待查元素elseif(key<ST.elem[mid])high=mid-1;/*继续在前半区间查找*/elselow=mid+1;//继续在后半区间查找}return0;//查找失败}3)静态树表的查找StatusCreat_Seq(SSTable*ST,intn){inti;(*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;returnOK;}voidAscend(SSTable*ST){//重建静态查找表为按关键字非降序排序inti,j,k;for(i=1;i<(*ST).length;i++){k=i;(*ST).elem[0]=(*ST).elem[i];//待比拟值存[0]单元for(j=i+1;j<=(*ST).length;j++)if((*ST).elem[j].key<(*ST).elem[0].key){k=j;(*ST).elem[0]=(*ST).elem[j];}if(k!=i)//有更小的值那么交换{(*ST).elem[k]=(*ST).elem[i];(*ST).elem[i]=(*ST).elem[0];}}}StatusCreat_Ord(SSTable*ST,intn){Statusf;f=Creat_Seq(ST,n);if(f)Ascend(ST);returnf;}StatusSecondOptimal(BiTree*T,ElemTypeR[],intsw[],intlow,inthigh){inti,j;doublemin,dw;i=low;min=fabs(sw[high]-sw[low]);dw=sw[high]+sw[low-1];for(j=low+1;j<=high;++j)//选择最小值if(fabs(dw-sw[j]-sw[j-1])<min){i=j;min=fabs(dw-sw[j]-sw[j-1]);}*T=(BiTree)malloc(sizeof(BiTNode));if(!*T)returnERROR;(*T)->data=R[i];//生成结点if(i==low)(*T)->lchild=NULL;//左子树空elseSecondOptimal(&(*T)->lchild,R,sw,low,i-1);//构造左子树if(i==high)(*T)->rchild=NULL;elseSecondOptimal(&(*T)->rchild,R,sw,i+1,high);returnOK;}StatusTraverse(SSTableST,void(*Visit)(ElemType)){ElemType*p;inti;p=++ST.elem;//p指向第一个元素for(i=1;i<=ST.length;i++)Visit(*p++);returnOK;}voidFindSW(intsw[],SSTableST){inti;sw[0]=0;for(i=1;i<=ST.length;i++)sw[i]=sw[i-1]+ST.elem[i].weight;}typedefBiTreeSOSTree;StatusCreateSOSTree(SOSTree*T,SSTableST){if(ST.length==0)*T=NULL;else{FindSW(sw,ST);SecondOptimal(T,ST.elem,sw,1,ST.length);}returnOK;}StatusSearch_SOSTree(SOSTree*T,KeyTypekey){while(*T)if((*T)->data.key==key)returnOK;elseif((*T)->data.key>key)*T=(*T)->lchild;else*T=(*T)->rchild;returnFALSE;}测试：1〕顺序表的查找typedefstruct{//数据元素longnumber;//号charname[9];intpolitics;intChinese;intEnglish;intmath;intphysics;intchemistry;intbiology;inttotal;//总分}ElemType;//以教科书图9.1高考成绩为例voidprint(ElemTypec){printf("%-8ld%-8s%4d%5d%5d%5d%5d%5d%5d%5d\n",c.number,,c.politics,c.Chinese,c.English,c.math,c.physics,c.chemistry,c.biology,c.total);}SSTablehead;intmain(){ElemTyper[N]={{179325,"红",85,86,88,100,92,90,45},{179326,"陆华",78,75,90,80,95,88,37}, {179327,"平",82,80,78,98,84,96,40}};SSTablest;inti;longs;for(i=0;i<N;i++)//计算总分r[i].total=r[i].politics+r[i].Chinese+r[i].English+r[i].math+r[i].physics+r[i].chemistry+r[i].biology;Creat_Seq(&st,r,N);printf("号政治语文外语数学物理化学生物总分\n");Traverse(st,print);printf("请输入待查找人的考号:");scanf("%ld",&s);i=Search_Seq(st,s);if(i)print(st.elem[i]);elseprintf("查找失败\n");}结果截图如下：<1>查找成功：<2>查找失败：2〕有序表的查找SSTbalehead;intmain(){ intj,k,t,w; SSTableST; inti;ST.length=LENGTH;printf("请按大小顺序输入一个顺序表共%d个元素!\n",ST.length); ST.elem=(ElemType*)malloc((ST.length+1)*sizeof(ElemType)); for(i=1;i<=ST.length;i++) scanf("%d",&ST.elem[i]); printf("请输入要查找的元素："); scanf("%d",&k); w=Search_Bin(ST,k); if(w)printf("您要查找的%d是第%d个元素\n",k,w); elseprintf("查找失败\n");}结果截图如下：<1>查找成功：<2>查找失败：3〕静态树链表的查找typedefstruct{//数据元素类型 KeyTypekey;intweight;}ElemType;ElemTyper[M]={{'A',1},{'B',1},{'C',2},{'D',5},{'E',3},{'F',4},{'G',4},{'H',3},{'I',5}};//以教科书例9-1为例voidprint(ElemTypec)/*Traverse()调用的函数*/{printf("(%c%d)",c.key,c.wei