靜態(tài)查找表adt

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

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

3、string.h"#include "malloc.h"#define ERROR 0;#define TRUE 1;#define OK 1;兩個存儲結構typedef struct KeyType key;ElemType;typedef struct /順序,有序存儲結構 ElemType elem100; int length;SSTable;SSTable ST;三、算法設計#include "string.h"#include "stdio.h"#include "string.h"#incl

4、ude "malloc.h"#define ERROR 0;#define TRUE 1;#define OK 1;typedef char KeyType;typedef struct KeyType key;ElemType;typedef struct /順序,有序存儲結構 ElemType elem100; int length;SSTable;SSTable ST;void main() /主函數(shù) int n; int flag; void menu1(); void menu2(); void goodbye(); void Creat_ST(); void D

5、estroy_ST(); void Search_ST(); void Sort_ST(); void Search_L(); void Travase(); void visit(); flag: system("cls"); printf("n"); printf("n"); printf(" 歡迎來到靜態(tài)查找表系統(tǒng)n"); printf(" *n"); printf(" * 1.順序查找 *n"); printf(" * 2.有序查找(折半查找) *n&quo

6、t;); 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() /順序查找表模塊 int a; int flag1; flag1: system("cls"); pr

7、intf("n"); printf("n"); printf(" 歡迎來到順序查找模塊n"); printf(" *n"); printf(" * 1.構建查找表 *n"); printf(" * 2.銷毀查找表 *n"); printf(" * 3.查找表中元素 *n"); printf(" * 4.遍歷表中元素 *n"); printf(" * 5.返回上一層目錄 *n"); printf(" * 6.

8、退出系統(tǒng) *n"); printf(" *n"); printf(" 請輸入您的選擇:"); scanf("%d",&a); switch(a) 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

9、4: Travase();system("PAUSE");menu1();break; case 5: main();break; case 6:goodbye();break; default : goto flag1; void menu2()/有序表查找模塊 int b; int flag2; flag2: system("cls"); printf("n");printf(" 11計科（7）班 梁永榮 3111005984 指導老師：曾孜n"); printf(" n");printf(

10、" 歡迎來到有序查找模塊n"); printf(" *n"); printf(" * 1.構建查找表 *n"); printf(" * 2.銷毀查找表 *n"); printf(" * 3.查找表中元素 *n"); printf(" * 4.遍歷表中元素 *n"); printf(" * 5.返回上一層目錄 *n"); printf(" * 6.退出系統(tǒng) *n"); printf(" *n"); printf(&qu

11、ot; 請輸入您的選擇:"); scanf("%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();sys

12、tem("PAUSE");menu2(); break; case 5: main();break; case 6: goodbye();break; default : goto flag2; void goodbye() /退出模塊 system("cls"); printf("n"); printf("n"); printf("n"); printf(" *n"); printf(" * 感謝使用靜態(tài)查找表系統(tǒng) *n"); printf( * *n&

13、quot;); printf(" * 再見! *n"); printf(" *n"); 創(chuàng)建查找表void Creat_ST() /構造一個含n個數(shù)據(jù)元素的表態(tài)查找表ST int n,i,j=0; char s100; system("cls"); printf("你需要構造多少個數(shù)據(jù)？請輸入："); scanf("%d",&n); printf("n"); while(n<0|n>100) printf("請輸入1-100范圍內(nèi)的數(shù)字：n&qu

14、ot;); getchar(); scanf("%d",&n); printf("請輸入%d個數(shù)據(jù)構造一個數(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;i<j;i+) printf("%cn",ST.elemi.key); printf("n");銷毀查找表：void Destroy_ST

15、() /銷毀查找表 int i; system("cls"); printf("n"); if(!ST.elem0.key) printf("錯誤！原表為空,銷毀失敗。n"); else for(i=ST.length-1;i<0;i-) free(ST.elemi.key); /從表尾開始銷毀 ST.length=0; printf("原表銷毀成功！按任意鍵返回上一層目錄。n"); 在查找表中查找元素:void Search_ST() /順序查找 KeyType ky; int i; system(&quo

16、t;cls"); if(ST.length=0) printf("查找表為空，請先建表！n"); return ERROR; printf("要查找的數(shù)據(jù):n"); getchar(); scanf("%c",&ky); ST.elemST.length+1.key=ky; /哨兵 for(i=0;ST.elemi.key!=ky;i+); /從前往后找 /i為要查找元素在表中位置，若失敗，為0 if(i<=ST.length)printf("恭喜，查找成功！該數(shù)據(jù)在表的第%d個位置上。n"

17、,i+1); else printf("查找失敗！n");有序查找的模塊，在創(chuàng)建靜態(tài)查找表之后排序，構成有序查找表：void Sort_ST() /將查找表的元素從小到大排序 int i,j; int c; for(j=0;j<ST.length-1;j+) for(i=0;i<ST.length-1-j;i+) if(ST.elemi.key>ST.elemi+1.key) c=ST.elemi.key; ST.elemi.key=ST.elemi+1.key; ST.elemi+1.key=c; printf("你輸入的數(shù)據(jù)有序排列后為:n&

18、quot;); for(i=0;i<ST.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"); get

19、char(); scanf("%c",&ky); while(low<=high) mid=(low+high)/2; if(ST.elemmid.key=ky) printf("恭喜，查找成功！該數(shù)據(jù)在表的第%d個位置上。n",mid+1); return; else if(ky<ST.elemmid.key) high=mid-1; else low=mid+1; printf("抱歉，查找失??！n");void Travase() /查找表的遍歷 int i; system("cls");

20、 printf("n"); if(ST.length=0) printf("查找表為空，不能進行遍歷n"); printf("現(xiàn)在將返回上層目錄"); else visit(); void visit() /visit函數(shù)，被Travese函數(shù)調用 int i; printf("查找表的元素如下：n"); for(i=0;i<ST.length;i+) printf("%cn",ST.elemi.key); 四、程序測試以及使用手冊：（1）主菜單界面（2）按“1”進入順序查找模塊 按“1”構建順序查找表（注意輸入以回車為結束標志）構建成功后按任意鍵返回上一層模塊構建失敗的出錯處理、按“2“進入銷毀查找表按“3“進入查找表中元素的操作查找成功的情況查找失敗的情況： 查找表為空，不能進行查找、按“4”進入查找表的遍歷操作 查找表為空，不能進行遍歷、按“5”返回上一層模塊、按“6”直接退出程序（3）按“2”進入到有序表的查找模塊、按“1”構建有序查找表（注意輸入以回車為結束標志）構建成功后按任意鍵返回上一層模塊，再按一下，所有元素有序排列、按“2”進行對有序查找表