静态查找表实验报告

PAGE101.题目采用长整型、整型、字符型为元素类型和顺序存储为存储结构，实现抽象数据类型静态查找表。软件环境为VisualC++2010Express。抽象数据类型定义以及各基本操作的简要描述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()失败，则操作失败。 }ADTStaticSearchTable3．存储结构定义公用头文件DS0.h:#include<string.h>#include<ctype.h>#include<malloc.h>#include<limits.h>#include<stdio.h>#include<stdlib.h>#include<io.h>#include<math.h>#include<process.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;typedefintBoolean;（1）顺序表#defineN5/*数据元素为5个*/typedefintKeyType;/*设关键字域为整型*/typedefstruct/*数据元素类型（教科书9.1）*/{ longnumber;/*准考证号*/ charname[9];/*姓名*/ intpolitics;/*政治*/ intChinese;/*语文*/ intEnglish;/*英语*/ intmath;/*数学*/ Intphysics;/*物理*/ intchemistry;/*化学*/ intbiology;/*生物*/ KeyTypekey;}ElemType;ElemTyper[N]={{179324,"何芳",85,89,98,100,93,80,47}, {179325,"陈红",85,86,88,100,92,90,45}, {179326,"陆华",78,75,90,80,95,88,37}, {179327,"张平",82,80,78,98,84,96,40}, {179328,"赵怡",76,85,94,57,77,69,44} };#definetotalkey/*定义总分(total)为关键字*/对两个数值型关键字的比括较约定为如下的宏定义#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))静态查找括的顺序存储结构typedefstruct{ ElemType*elem; intlength;}SSTable;有序表#defineN11/*数据元素个数*/typedefintKeyType;/*设关键字域为整型*/typedefstruct/*数据元素类型*/{ KeyTypekey;/*关键字域*/intothers;/*其它部分*/}ElemType;ElemTyper[N]={{5,1},{13,2},{19,3},{21,4},{37,5},{56,6},{64, 7},{75,8},{80,9},{88,10},{92,11}};/*数据元素 (以教科书219数据为例),全局变量*/对两个数值型关键字括较约定为如下的宏定义#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))静态查找表的顺序存储结构typedefstruct{ ElemType*elem; intlength;}SSTable;静态树表#defineN9/*数据元素个数*/typedefcharKeyType;/*设关键字域为字符型*/typedefstruct/*数据元素类型*/{ KeyTypekey; intweight;}ElemType;ElemTyper[N]={{'A',1},{'B',1},{'C',2},{'D',5},{'E',3}, {'F',4},{'G',4},{'H',3},{'I',5}};/*数据元素(以 教科书例9-1为例),全局变量*/intsw[N+1];/*累计权值，全局变量*/两个数值型关键字的括较约定为如下的宏定义#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))静态查表找的顺序存储结构typedefstruct{ ElemType*elem; Intlength;}SSTable;算法设计顺序表的查找StatusCreat_Seq(SSTable*ST,intn){//操作结果:构造一个含个n数据元素的静态顺查找表ST(数据来自全局数组) inti; (*ST).elem=(ElemType*)calloc(n+1,sizeof(ElemType)); if(!(*ST).elem) returnERROR; for(i=1;i<=n;i++) *((*ST).elem+i)=r[i-1];//把全局数组的值依次赋给ST (*ST).length=n; returnOK;}StatusDestroy(SSTable*ST){//初始条件:静态查找表存在//操作结果销毁表括ST free((*ST).elem); (*ST).elem=NULL; (*ST).length=0; returnOK;}intSearch_Seq(SSTableST,KeyTypekey){/*初始条件：静态查找表ST存在,key为和关键字类型相同的给定值。操作结果：若ST中存在关键字等于key的数据元素，则函数值为该元素在 表中的位置，否则为“空”。*/ inti; ST.elem[0].key=key;/*哨Θ?兵?*/ for(i=ST.length;!EQ(ST.elem[i].key,key);--i); returni;}StatusTraverse(SSTableST,void(*Visit)(ElemType)){/*初始条件：静态查找表ST存在，Visit()是对元素操作的应用函数。 操作结果：按顺序对ST的每个元素调用函数Visit()一次且仅一次，一旦 Visit()失败，则操作失败*/ ElemType*p; inti; p=++ST.elem;/*p指向第一个元素*/ for(i=1;i<=ST.length;i++) Visit(*p++); returnOK;}voidprint(ElemTypec)/*Traverse()调用的函数*/{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);}（2）有序表的查找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++) ifLT((*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){/*操作结果:构造一个含n个数据元素的静态按关键字非降序查找表ST*/ /*数据来自全局数组r*/ Statusf; f=Creat_Seq(ST,n); if(f) Ascend(ST); returnf;}StatusDestroy(SSTable*ST){/*初始条件:静态查找表ST存在。操作结果:销毁表ST*/ free((*ST).elem); (*ST).elem=NULL; (*ST).length=0; returnOK;}intSearch_Bin(SSTableST,KeyTypekey){/*在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为*/ /*该元素在表中的位置，否则为0。算法9.2*/ intlow,high,mid; low=1;/*置区间初值*/ high=ST.length; while(low<=high) { mid=(low+high)/2; ifEQ(key,ST.elem[mid].key)/*找到待查元素*/ returnmid; elseifLT(key,ST.elem[mid].key) high=mid-1;/*继续在前半区间进行查找*/ else low=mid+1;/*继续在后半区间进行查找*/ } return0;/*顺序表中不存在待查元素*/}静态树表的查找typedefElemTypeTElemType;typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild;/*左右孩子指针*/}BiTNode,*BiTree;StatusSecondOptimal(BiTree*T,ElemTypeR[],intsw[],intlow,int high){/*由有序表R[low..high]及其累计权值表sw(其中sw[0]==0)递归构造*/ /*次优查找树T。算法9.3*/ inti,j; doublemin,dw; i=low; min=(int)fabs(double(sw[high]-sw[low])); dw=sw[high]+sw[low-1]; for(j=low+1;j<=high;++j)/*选择最小的△Pi值*/ 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;/*左子树空*/ else SecondOptimal(&(*T)->lchild,R,sw,low,i-1); if(i==high) (*T)->rchild=NULL;/*右子树空*/ else SecondOptimal(&(*T)->rchild,R,sw,i+1,high); returnOK;}voidFindSW(intsw[],SSTableST){/*按照有序表ST中各数据元素的Weight域求累计权值表sw*/ 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){//由有序表ST构造一棵次优查找树T。ST的数据元素含有权域weight if(ST.length==0) *T=NULL; else { FindSW(sw,ST); SecondOptimal(T,ST.elem,sw,1,ST.length); } returnOK;}StatusSearch_SOSTree(SOSTree*T,KeyTypekey){/*在次优查找树T中查找关键字等于key的元素。找到则返回OK，否则返回FALSE */ while(*T)/*T非空*/ if((*T)->data.key==key) returnOK; elseif((*T)->data.key>key) *T=(*T)->lchild; else *T=(*T)->rchild; returnFALSE;/*顺序表中不存在待查元素*/}voidprint(ElemTypec)/*Traverse()调用的函数*/{ printf("(%c%d)",c.key,c.weight);}测试顺序查找表测试SSTablehead；voidmain(){charjude;SSTablest;inti,s;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,N);/*由全局数组产生静态查找表st*/printf("你想进行查找吗？请输入yorn\n");scanf("%c",&jude);while(jude=='y'){printf("准考证号姓名政治语文外语数学物理化学生物总分 \n");Traverse(st,print);/*按顺序输出静态查找表st*/printf("请输入待查找人的总分:");fflush(stdin);scanf("%d",&s);i=Search_Seq(st,s);/*顺序查找*/if(i)print(*(st.elem+i));Elseprintf("没找到\n");fflush(stdin);printf("你想进行查找吗？请输入yorn\n");scanf("%c",&jude);}Destroy(&st);}.有序表的查找STTablehead；voidmain(){ charjude; SSTablest; inti; KeyTypes; Creat_Ord(&st,N);/*由全局数组产生非降序静态查找表st*/ printf("你想进行查找吗？请输入yorn\n"); scanf("%c",&jude); while(jude=='y') { Traverse(st,print);/*顺序输出非降序静态查找表st*/ printf("\n"); printf("请输入待查找值的关键字:"); fflush(stdin); scanf("%d",&s); i=Search_Bin(st,s);/*折半查找有序表*/ if(i) printf("(%d%d)%d是第%d个记录的关键字 \n",st.elem[i].key,st.elem[i].others,s,i); else printf("没找到\n"); fflush(stdin); printf("你想进行查找吗？请输入yorn\n"); scanf("%c",&jude); } Destroy(&st);}.静态树表的查找STTablehead;voidmain(){ SSTablest; SOSTreet; Statusi; KeyTypes; charjude; Creat_Ord(&st,N);/*由全局数组产生非降序静态查找表st*/ printf("你想进行查找吗