靜態(tài)查找表實(shí)驗(yàn)報(bào)告

PAGE101.題目采用長(zhǎng)整型、整型、字符型為元素類(lèi)型和順序存儲(chǔ)為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型靜態(tài)查找表。軟件環(huán)境為VisualC++2010Express。抽象數(shù)據(jù)類(lèi)型定義以及各基本操作的簡(jiǎn)要描述ADTStaticSearchTable{數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素均含有類(lèi)型相同，可 唯一標(biāo)識(shí)數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬于一個(gè)集合。基本操作P：Create(&ST,n)操作結(jié)果:構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素的靜態(tài)順序查找表ST。Destroy(&ST)初始條件：靜態(tài)查找表ST存在操作結(jié)果：銷(xiāo)毀表ST。Search(St,key)初始條件：靜態(tài)查找表ST存在,key為和關(guān)鍵字類(lèi)型相同的給定值。操作結(jié)果：若ST中存在關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素在表 中的位置，否則為“空”。Traverse(ST,Visit())初始條件：靜態(tài)查找表ST存在，Visit()是對(duì)元素操作的應(yīng)用函數(shù)。操作結(jié)果：按順序?qū)T的每個(gè)元素調(diào)用函數(shù)Visit()一次且僅一次，一旦 Visit()失敗，則操作失敗。 }ADTStaticSearchTable3．存儲(chǔ)結(jié)構(gòu)定義公用頭文件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/*數(shù)據(jù)元素為5個(gè)*/typedefintKeyType;/*設(shè)關(guān)鍵字域?yàn)檎?/typedefstruct/*數(shù)據(jù)元素類(lèi)型（教科書(shū)9.1）*/{ longnumber;/*準(zhǔn)考證號(hào)*/ charname[9];/*姓名*/ intpolitics;/*政治*/ intChinese;/*語(yǔ)文*/ intEnglish;/*英語(yǔ)*/ intmath;/*數(shù)學(xué)*/ Intphysics;/*物理*/ intchemistry;/*化學(xué)*/ 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)為關(guān)鍵字*/對(duì)兩個(gè)數(shù)值型關(guān)鍵字的比括較約定為如下的宏定義#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))靜態(tài)查找括的順序存儲(chǔ)結(jié)構(gòu)typedefstruct{ ElemType*elem; intlength;}SSTable;有序表#defineN11/*數(shù)據(jù)元素個(gè)數(shù)*/typedefintKeyType;/*設(shè)關(guān)鍵字域?yàn)檎?/typedefstruct/*數(shù)據(jù)元素類(lèi)型*/{ KeyTypekey;/*關(guān)鍵字域*/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}};/*數(shù)據(jù)元素 (以教科書(shū)219數(shù)據(jù)為例),全局變量*/對(duì)兩個(gè)數(shù)值型關(guān)鍵字括較約定為如下的宏定義#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)typedefstruct{ ElemType*elem; intlength;}SSTable;靜態(tài)樹(shù)表#defineN9/*數(shù)據(jù)元素個(gè)數(shù)*/typedefcharKeyType;/*設(shè)關(guān)鍵字域?yàn)樽址?/typedefstruct/*數(shù)據(jù)元素類(lèi)型*/{ KeyTypekey; intweight;}ElemType;ElemTyper[N]={{'A',1},{'B',1},{'C',2},{'D',5},{'E',3}, {'F',4},{'G',4},{'H',3},{'I',5}};/*數(shù)據(jù)元素(以 教科書(shū)例9-1為例),全局變量*/intsw[N+1];/*累計(jì)權(quán)值，全局變量*/兩個(gè)數(shù)值型關(guān)鍵字的括較約定為如下的宏定義#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))靜態(tài)查表找的順序存儲(chǔ)結(jié)構(gòu)typedefstruct{ ElemType*elem; Intlength;}SSTable;算法設(shè)計(jì)順序表的查找StatusCreat_Seq(SSTable*ST,intn){//操作結(jié)果:構(gòu)造一個(gè)含個(gè)n數(shù)據(jù)元素的靜態(tài)順查找表ST(數(shù)據(jù)來(lái)自全局?jǐn)?shù)組) 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];//把全局?jǐn)?shù)組的值依次賦給ST (*ST).length=n; returnOK;}StatusDestroy(SSTable*ST){//初始條件:靜態(tài)查找表存在//操作結(jié)果銷(xiāo)毀表括ST free((*ST).elem); (*ST).elem=NULL; (*ST).length=0; returnOK;}intSearch_Seq(SSTableST,KeyTypekey){/*初始條件：靜態(tài)查找表ST存在,key為和關(guān)鍵字類(lèi)型相同的給定值。操作結(jié)果：若ST中存在關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素在 表中的位置，否則為“空”。*/ inti; ST.elem[0].key=key;/*哨Θ?兵?*/ for(i=ST.length;!EQ(ST.elem[i].key,key);--i); returni;}StatusTraverse(SSTableST,void(*Visit)(ElemType)){/*初始條件：靜態(tài)查找表ST存在，Visit()是對(duì)元素操作的應(yīng)用函數(shù)。 操作結(jié)果：按順序?qū)T的每個(gè)元素調(diào)用函數(shù)Visit()一次且僅一次，一旦 Visit()失敗，則操作失敗*/ ElemType*p; inti; p=++ST.elem;/*p指向第一個(gè)元素*/ for(i=1;i<=ST.length;i++) Visit(*p++); returnOK;}voidprint(ElemTypec)/*Traverse()調(diào)用的函數(shù)*/{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){/*重建靜態(tài)查找表為按關(guān)鍵字非降序排序*/ 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){/*操作結(jié)果:構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素的靜態(tài)按關(guān)鍵字非降序查找表ST*/ /*數(shù)據(jù)來(lái)自全局?jǐn)?shù)組r*/ Statusf; f=Creat_Seq(ST,n); if(f) Ascend(ST); returnf;}StatusDestroy(SSTable*ST){/*初始條件:靜態(tài)查找表ST存在。操作結(jié)果:銷(xiāo)毀表ST*/ free((*ST).elem); (*ST).elem=NULL; (*ST).length=0; returnOK;}intSearch_Bin(SSTableST,KeyTypekey){/*在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為*/ /*該元素在表中的位置，否則為0。算法9.2*/ intlow,high,mid; low=1;/*置區(qū)間初值*/ 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;/*繼續(xù)在前半?yún)^(qū)間進(jìn)行查找*/ else low=mid+1;/*繼續(xù)在后半?yún)^(qū)間進(jìn)行查找*/ } return0;/*順序表中不存在待查元素*/}靜態(tài)樹(shù)表的查找typedefElemTypeTElemType;typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild;/*左右孩子指針*/}BiTNode,*BiTree;StatusSecondOptimal(BiTree*T,ElemTypeR[],intsw[],intlow,int high){/*由有序表R[low..high]及其累計(jì)權(quán)值表sw(其中sw[0]==0)遞歸構(gòu)造*/ /*次優(yōu)查找樹(shù)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];/*生成結(jié)點(diǎn)*/ if(i==low) (*T)->lchild=NULL;/*左子樹(shù)空*/ else SecondOptimal(&(*T)->lchild,R,sw,low,i-1); if(i==high) (*T)->rchild=NULL;/*右子樹(shù)空*/ else SecondOptimal(&(*T)->rchild,R,sw,i+1,high); returnOK;}voidFindSW(intsw[],SSTableST){/*按照有序表ST中各數(shù)據(jù)元素的Weight域求累計(jì)權(quán)值表sw*/ inti; sw[0]=0; for(i=1;i<=ST.length;i++) sw[i]=sw[i-1]+ST.elem[i].weight;}typedefBiTreeSOSTree;/*次優(yōu)查找樹(shù)采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)*/StatusCreateSOSTree(SOSTree*T,SSTableST){//由有序表ST構(gòu)造一棵次優(yōu)查找樹(shù)T。ST的數(shù)據(jù)元素含有權(quán)域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){/*在次優(yōu)查找樹(shù)T中查找關(guān)鍵字等于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()調(diào)用的函數(shù)*/{ printf("(%c%d)",c.key,c.weight);}測(cè)試順序查找表測(cè)試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);/*由全局?jǐn)?shù)組產(chǎn)生靜態(tài)查找表st*/printf("你想進(jìn)行查找嗎？請(qǐng)輸入yorn\n");scanf("%c",&jude);while(jude=='y'){printf("準(zhǔn)考證號(hào)姓名政治語(yǔ)文外語(yǔ)數(shù)學(xué)物理化學(xué)生物總分 \n");Traverse(st,print);/*按順序輸出靜態(tài)查找表st*/printf("請(qǐng)輸入待查找人的總分:");fflush(stdin);scanf("%d",&s);i=Search_Seq(st,s);/*順序查找*/if(i)print(*(st.elem+i));Elseprintf("沒(méi)找到\n");fflush(stdin);printf("你想進(jìn)行查找嗎？請(qǐng)輸入yorn\n");scanf("%c",&jude);}Destroy(&st);}.有序表的查找STTablehead；voidmain(){ charjude; SSTablest; inti; KeyTypes; Creat_Ord(&st,N);/*由全局?jǐn)?shù)組產(chǎn)生非降序靜態(tài)查找表st*/ printf("你想進(jìn)行查找嗎？請(qǐng)輸入yorn\n"); scanf("%c",&jude); while(jude=='y') { Traverse(st,print);/*順序輸出非降序靜態(tài)查找表st*/ printf("\n"); printf("請(qǐng)輸入待查找值的關(guān)鍵字:"); fflush(stdin); scanf("%d",&s); i=Search_Bin(st,s);/*折半查找有序表*/ if(i) printf("(%d%d)%d是第%d個(gè)記錄的關(guān)鍵字 \n",st.elem[i].key,st.elem[i].others,s,i); else printf("沒(méi)找到\n"); fflush(stdin); printf("你想進(jìn)行查找嗎？請(qǐng)輸入yorn\n"); scanf("%c",&jude); } Destroy(&st);}.靜態(tài)樹(shù)表的查找STTablehead;voidmain(){ SSTablest; SOSTreet; Statusi; KeyTypes; charjude; Creat_Ord(&st,N);/*由全局?jǐn)?shù)組產(chǎn)生非降序靜態(tài)查找表st*/ printf("你想進(jìn)行查找嗎