數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告之靜態(tài)查找表

..數(shù)據(jù)構(gòu)造實(shí)驗(yàn)報(bào)告題目：靜態(tài)查找表的實(shí)現(xiàn)成績(jī)____________________2014年6月10號(hào)靜態(tài)查找表抽象數(shù)據(jù)類型的實(shí)現(xiàn)一、設(shè)計(jì)任務(wù)、要求及所用的軟件環(huán)境或工具：1.設(shè)計(jì)任務(wù)及要求：用C語言實(shí)現(xiàn)靜態(tài)查找表的抽象數(shù)據(jù)類型2.軟件環(huán)境：win73.開發(fā)工具：C-Free二、抽象數(shù)據(jù)類型的實(shí)現(xiàn)1.題目采用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)為存儲(chǔ)構(gòu)造，實(shí)現(xiàn)抽象數(shù)據(jù)類型StaticSearchTable。ADTStaticSearchTable{數(shù)據(jù)對(duì)象D：D是具有一樣特性的數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素含有類型一樣的關(guān)鍵字，可唯一標(biāo)識(shí)元素的關(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é)果：銷毀表ST。Search(ST,key);初始條件：靜態(tài)查找表ST存在，key為和關(guān)鍵字類型一樣的給定值。操作結(jié)果：假設(shè)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()失敗，那么操作失敗。}ADTStaticSearchTable2．存儲(chǔ)構(gòu)造定義*公用頭文件DS0.h:#include<stdio.h>#include<malloc.h>#include<math.h>*預(yù)定義常量和類型//函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;typedefintKeyType;typedeffloatKeyType;typedefcharKeyType;typedefintElemType;typedefElemTypeTElemType;1)順序存儲(chǔ)構(gòu)造typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲(chǔ)空間基址，0號(hào)單元留空intlength;//表長(zhǎng)}SSTable;2)二叉鏈表存儲(chǔ)構(gòu)造typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;3.算法設(shè)計(jì)1)順序表的查找voidCreat_Seq(SSTable*ST,ElemTyper[],intn){inti;(*ST).elem=(ElemType*)calloc(n+1,sizeof(ElemType));//動(dòng)態(tài)生成n+1個(gè)數(shù)據(jù)元素空間(0號(hào)單元不用)if(!(*ST).elem)exit(0);for(i=1;i<=n;i++)(*ST).elem[i]=r[i-1];//將數(shù)組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;//找不到時(shí)，i為0}voidTraverse(SSTableST,void(*Visit)(ElemType)){ElemType*p;inti;p=++ST.elem;//p指向第一個(gè)元素for(i=1;i<=ST.length;i++)Visit(*p++);}2)有序表的查找intSearch_Bin(SSTableST,KeyTypekey){intlow,high,mid;low=1;high=ST.length;//置區(qū)間初值while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid])returnmid;//找到待查元素elseif(key<ST.elem[mid])high=mid-1;/*繼續(xù)在前半?yún)^(qū)間查找*/elselow=mid+1;//繼續(xù)在后半?yún)^(qū)間查找}return0;//查找失敗}3)靜態(tài)樹表的查找StatusCreat_Seq(SSTable*ST,intn){inti;(*ST).elem=(ElemType*)calloc(n+1,sizeof(ElemType));//動(dòng)態(tài)生成n+1個(gè)數(shù)據(jù)元素空間(0號(hào)單元不用)if(!(*ST).elem)exit(0);for(i=1;i<=n;i++)(*ST).elem[i]=r[i-1];//將數(shù)組r的值依次賦給ST(*ST).length=n;returnOK;}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++)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];//生成結(jié)點(diǎn)if(i==low)(*T)->lchild=NULL;//左子樹空elseSecondOptimal(&(*T)->lchild,R,sw,low,i-1);//構(gòu)造左子樹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指向第一個(gè)元素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;}測(cè)試：1〕順序表的查找typedefstruct{//數(shù)據(jù)元素longnumber;//號(hào)charname[9];intpolitics;intChinese;intEnglish;intmath;intphysics;intchemistry;intbiology;inttotal;//總分}ElemType;//以教科書圖9.1高考成績(jī)?yōu)槔齰oidprint(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++)//計(jì)算總分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("號(hào)政治語文外語數(shù)學(xué)物理化學(xué)生物總分\n");Traverse(st,print);printf("請(qǐng)輸入待查找人的考號(hào):");scanf("%ld",&s);i=Search_Seq(st,s);if(i)print(st.elem[i]);elseprintf("查找失敗\n");}結(jié)果截圖如下：<1>查找成功：<2>查找失?。?〕有序表的查找SSTbalehead;intmain(){ intj,k,t,w; SSTableST; inti;ST.length=LENGTH;printf("請(qǐng)按大小順序輸入一個(gè)順序表共%d個(gè)元素!\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("請(qǐng)輸入要查找的元素："); scanf("%d",&k); w=Search_Bin(ST,k); if(w)printf("您要查找的%d是第%d個(gè)元素\n",k,w); elseprintf("查找失敗\n");}結(jié)果截圖如下：<1>查找成功：<2>查找失敗：3〕靜態(tài)樹鏈表的查找typedefstruct{//數(shù)據(jù)元素類型 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()調(diào)用的函數(shù)*/{printf("(%c%d)",c.key,c.wei