靜態(tài)查找表adt

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題 目 靜態(tài)查找表 學(xué) 院 計算機學(xué)院 專 業(yè) 計算機科學(xué)與技術(shù) 年級班別 11計科七班 學(xué) 號 3111005984 學(xué)生姓名 梁永榮 指導(dǎo)教師 曾孜 2013 年 6月 25日一、題目：靜態(tài)查找表的基本操作實現(xiàn)。ADT StataiSerachTable數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素集合，各個數(shù)據(jù)元素均含有類型相同，可惟一標(biāo)識數(shù)據(jù)元素的關(guān)鍵的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合?；静僮鱌:Create(&ST,n);操作結(jié)果：構(gòu)造一個含n個數(shù)據(jù)元素的靜態(tài)查找表ST。Destory(&ST)；初始條件:靜態(tài)查找表ST存在。操作結(jié)果：銷毀表ST；Search(ST

2、,key);初始條件:靜態(tài)查找表ST存在，key為和關(guān)鍵字類型相同的給定值。操作結(jié)果：若ST中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。Traverse();初始條件；靜態(tài)查找表ST存在，Visit是對元素操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)T的每個元素調(diào)用函數(shù)visit（）一次且一次。一旦visit()失敗，則操作失敗。ADT StataiSerachTable二、存儲結(jié)構(gòu)的定義公用頭文件#include string.h#include stdio.h#include string.h#include malloc.h#define ERROR

3、 0;#define TRUE 1;#define OK 1;兩個存儲結(jié)構(gòu)typedef struct KeyType key;ElemType;typedef struct /順序,有序存儲結(jié)構(gòu) ElemType elem100; int length;SSTable;SSTable ST;三、算法設(shè)計#include string.h#include stdio.h#include string.h#include malloc.h#define ERROR 0;#define TRUE 1;#define OK 1;typedef char KeyType;typedef struct

4、KeyType key;ElemType;typedef struct /順序,有序存儲結(jié)構(gòu) ElemType elem100; int length;SSTable;SSTable ST;void main() /主函數(shù) int n; int flag; void menu1(); void menu2(); void goodbye(); void Creat_ST(); void Destroy_ST(); void Search_ST(); void Sort_ST(); void Search_L(); void Travase(); void visit(); flag: syst

5、em(cls); printf(n); printf(n); printf( 歡迎來到靜態(tài)查找表系統(tǒng)n); printf( *n); printf( * 1.順序查找 *n); printf( * 2.有序查找(折半查找) *n); printf( * 3.離開系統(tǒng) *n); printf( *n); printf( 請輸入您的選擇:); scanf(%d,&n); switch(n) case 1: menu1();break; case 2: menu2();break; case 3: goodbye();break; default :goto flag; void menu1() /

6、順序查找表模塊 int a; int flag1; flag1: system(cls); printf(n); printf(n); printf( 歡迎來到順序查找模塊n); printf( *n); printf( * 1.構(gòu)建查找表 *n); printf( * 2.銷毀查找表 *n); printf( * 3.查找表中元素 *n); printf( * 4.遍歷表中元素 *n); printf( * 5.返回上一層目錄 *n); printf( * 6.退出系統(tǒng) *n); printf( *n); printf( 請輸入您的選擇:); scanf(%d,&a); switch(a)

7、case 1: Creat_ST();system(PAUSE);menu1();break; case 2: Destroy_ST();system(PAUSE);menu1();break; case 3: Search_ST();system(PAUSE);menu1();break; case 4: Travase();system(PAUSE);menu1();break; case 5: main();break; case 6:goodbye();break; default : goto flag1; void menu2()/有序表查找模塊 int b; int flag2;

8、 flag2: system(cls); printf(n);printf( 11計科（7）班 梁永榮 3111005984 指導(dǎo)老師：曾孜n); printf( n);printf( 歡迎來到有序查找模塊n); printf( *n); printf( * 1.構(gòu)建查找表 *n); printf( * 2.銷毀查找表 *n); printf( * 3.查找表中元素 *n); printf( * 4.遍歷表中元素 *n); printf( * 5.返回上一層目錄 *n); printf( * 6.退出系統(tǒng) *n); printf( *n); printf( 請輸入您的選擇:); scanf(%

9、d,&b); switch(b) case 1: Creat_ST();system(PAUSE);Sort_ST();system(PAUSE);menu2();break; case 2: Destroy_ST();system(PAUSE);menu2();break; case 3: Search_L();system(PAUSE);menu2();break; case 4: Travase();system(PAUSE);menu2(); break; case 5: main();break; case 6: goodbye();break; default : goto fla

10、g2; void goodbye() /退出模塊 system(cls); printf(n); printf(n); printf(n); printf( *n); printf( * 感謝使用靜態(tài)查找表系統(tǒng) *n); printf( * *n); printf( * 再見! *n); printf( *n); 創(chuàng)建查找表void Creat_ST() /構(gòu)造一個含n個數(shù)據(jù)元素的表態(tài)查找表ST int n,i,j=0; char s100; system(cls); printf(你需要構(gòu)造多少個數(shù)據(jù)？請輸入：); scanf(%d,&n); printf(n); while(n100) p

11、rintf(請輸入1-100范圍內(nèi)的數(shù)字：n); getchar(); scanf(%d,&n); printf(請輸入%d個數(shù)據(jù)構(gòu)造一個數(shù)據(jù)表n,n); getchar(); gets(s); for(;sj!=0;j+) ST.elemj.key=sj; ST.length=j; printf(你輸入了%d個數(shù)據(jù)!它們是：n,j); for(i=0;ij;i+) printf(%cn,ST.elemi.key); printf(n);銷毀查找表：void Destroy_ST() /銷毀查找表 int i; system(cls); printf(n); if(!ST.elem0.key)

12、 printf(錯誤！原表為空,銷毀失敗。n); else for(i=ST.length-1;i0;i-) free(ST.elemi.key); /從表尾開始銷毀 ST.length=0; printf(原表銷毀成功！按任意鍵返回上一層目錄。n); 在查找表中查找元素:void Search_ST() /順序查找 KeyType ky; int i; system(cls); if(ST.length=0) printf(查找表為空，請先建表！n); return ERROR; printf(要查找的數(shù)據(jù):n); getchar(); scanf(%c,&ky); ST.elemST.le

13、ngth+1.key=ky; /哨兵 for(i=0;ST.elemi.key!=ky;i+); /從前往后找 /i為要查找元素在表中位置，若失敗，為0 if(i=ST.length)printf(恭喜，查找成功！該數(shù)據(jù)在表的第%d個位置上。n,i+1); else printf(查找失?。);有序查找的模塊，在創(chuàng)建靜態(tài)查找表之后排序，構(gòu)成有序查找表：void Sort_ST() /將查找表的元素從小到大排序 int i,j; int c; for(j=0;jST.length-1;j+) for(i=0;iST.elemi+1.key) c=ST.elemi.key; ST.elemi.k

14、ey=ST.elemi+1.key; ST.elemi+1.key=c; printf(你輸入的數(shù)據(jù)有序排列后為:n); for(i=0;iST.length;i+) printf(%cn,ST.elemi.key); printf(n); void Search_L() /有序查找 KeyType ky; int i; int high,mid; int low=0; system(cls); if(ST.length=0) printf(查找表為空，請先建表！n); return ERROR; high=ST.length; printf(要查找的數(shù)據(jù):n); getchar(); sca

15、nf(%c,&ky); while(low=high) mid=(low+high)/2; if(ST.elemmid.key=ky) printf(恭喜，查找成功！該數(shù)據(jù)在表的第%d個位置上。n,mid+1); return; else if(kyST.elemmid.key) high=mid-1; else low=mid+1; printf(抱歉，查找失??！n);void Travase() /查找表的遍歷 int i; system(cls); printf(n); if(ST.length=0) printf(查找表為空，不能進(jìn)行遍歷n); printf(現(xiàn)在將返回上層目錄); e

16、lse visit(); void visit() /visit函數(shù)，被Travese函數(shù)調(diào)用 int i; printf(查找表的元素如下：n); for(i=0;iST.length;i+) printf(%cn,ST.elemi.key); 四、程序測試以及使用手冊：（1）主菜單界面（2）按“1”進(jìn)入順序查找模塊 按“1”構(gòu)建順序查找表（注意輸入以回車為結(jié)束標(biāo)志）構(gòu)建成功后按任意鍵返回上一層模塊構(gòu)建失敗的出錯處理、按“2“進(jìn)入銷毀查找表按“3“進(jìn)入查找表中元素的操作查找成功的情況查找失敗的情況： 查找表為空，不能進(jìn)行查找、按“4”進(jìn)入查找表的遍歷操作 查找表為空，不能進(jìn)行遍歷、按“5”返

17、回上一層模塊、按“6”直接退出程序（3）按“2”進(jìn)入到有序表的查找模塊、按“1”構(gòu)建有序查找表（注意輸入以回車為結(jié)束標(biāo)志）構(gòu)建成功后按任意鍵返回上一層模塊，再按一下，所有元素有序排列、按“2”進(jìn)行對有序查找表的銷毀、按“3”查找表中元素，查找成功的情況： 查找失敗的情況：查找表為空的情況：、按“4”進(jìn)行遍歷有序查找表的操作查找表為空的情況：、按“5”返回上層目錄、按“6”直接退出系統(tǒng) （3）按“3”退出系統(tǒng)五，2種查找表的比較與分析存儲結(jié)構(gòu) 順序查找表有序查找表(折半查找)基本操作時間復(fù)雜度創(chuàng)建查找表creat_ST()O(n)O(n2)銷毀查找表destory_ST（）O(n)O(n)查找表中元素search_ST()和search_L()O(n)O(log(2n)遍歷表中元素Travese()O(n)O(n)優(yōu)缺點分析優(yōu)點算法簡單，且對表的結(jié)構(gòu)無任何要求，無論是用向量還是用鏈表來存放結(jié)點，也無論結(jié)點之間是否按關(guān)鍵字有序，它都同樣適用。查找效率低，因此，當(dāng)n較大時不宜采用順序查找。缺點要求表中的記錄是有序的，且只能用于順序存儲結(jié)構(gòu)。若表中的記錄經(jīng)常變化，為保持表的有序性，需要不斷進(jìn)行調(diào)整，這在一定程度上要降低查找效率。