查找操作   
 1．掌握各種查找的基本思想和方法； 
2．靈活使用高級程序設(shè)計語言實現(xiàn)查找算法。 
實驗內(nèi)容： 
1.設(shè)計一個程序設(shè)計折半查找。 
2.設(shè)計一個解決哈希查找中碰撞時的方法，并用程序?qū)崿F(xiàn)。  
 
 

/* 本程序提供了用順序表實現(xiàn)字典的情況下 
的二分法檢索算法*/ 

#include<stdio.h> 
#define TRUE 1 
#define FALSE 0 
#define MAXNUM 100 

typedef int KeyType ; 

typedef struct { 
 KeyType key; /* 字典元素的關(guān)鍵碼字段 */ 
 /*DataType value; /* 字典元素的屬性字段 */ 
} DicElement; /*元素字典*/ 

typedef struct { 
 int n; /* n<=MAXNUM，為字典中元素的個數(shù) */ 
 DicElement element[MAXNUM]; 
} SeqDictionary; 

/* 在字典中用二分法查找關(guān)鍵碼為key的元素 */ 
int binarySearch(SeqDictionary * pdic, KeyType key, int *position) { 
 int low = 0, high = pdic->n-1, mid; 

 while(low<=high) { 
 mid = (low+high)/2; /* 當前檢索的中間位置 */ 
 if(pdic->element[mid].key == key) { /* 檢索成功 */ 
 *position = mid; return TRUE; 
 } 
 else if (pdic->element[mid].key > key)  
 high = mid-1; /* 要檢索的元素在左半?yún)^(qū) */ 
 else low = mid+1; /* 要檢索的元素在右半?yún)^(qū) */ 
 } 
 *position=low; 
 return FALSE; /* 檢索失敗 */ 
} 

SeqDictionary dic={ 
 10, 1,3,5,7,9,11,13,19,21,30}; 

int main(){ 
 int i, position; 
 while(1){ 
 printf("Input the key you want to search: "); 
 scanf("%d",&i); 
 if(i==0)break; 
 if(binarySearch(&dic,i,&position)==TRUE) 
 printf("It is the %dth element!\n",position+1); 
 else printf("It is not in the dictionary!\n"); 
 } 
 return 0; 
} 


/* 本程序是用開地址法實現(xiàn)散列的檢索算法*/ 

#include<stdio.h> 

#define TRUE 1 
#define FALSE 0 

#define null -1 /* null為空結(jié)點標記 */ 
#define REGION_LEN 13 

typedef int KeyType; 

typedef struct { 
 KeyType key; /* 字典元素的關(guān)鍵碼字段 */ 
 /*DataType value; /* 字典元素的屬性字段 */ 
} DicElement; 

typedef struct { 
 int m; /* m=REGION_LEN，為基本區(qū)域長度 */ 
 DicElement element[REGION_LEN]; 
} HashDictionary; 

int h(KeyType key){ 
 return key % REGION_LEN; 
} 

int linearSearch(HashDictionary * phash, KeyType key, int *position) { 
 int d = h(key), inc; /* d為散列地址，散列函數(shù)為h(key) */ 

 for (inc = 0; inc < phash->m; inc++) { 
 if (phash->element[d].key == key) { 
 *position = d; /* 檢索成功 */ 
 return TRUE; 
 } 
 else if (phash->element[d].key == null) { 
 *position = d; /* 檢索失敗，也找到插入位置 */ 
 return FALSE; 
 } 
 d = (d+1) % phash->m; 
 } 

 *position = -1; /* 散列表溢出 */ 
 return FALSE; 
} 

int linearInsert(HashDictionary *phash, KeyType key) { 
 int position; 
 if(linearSearch(phash, key, &position) == TRUE )/* 已有關(guān)鍵碼為key的結(jié)點*/ 
 printf("Find\n"); 
 else if(position != -1) {  
 phash->element[position].key = key; /* 插入結(jié)點，還應(yīng)對value字段賦值 */ 
 } 
 else return FALSE; /* 散列表溢出 */ 

 return TRUE; 
} 

HashDictionary dic; 

int main(){ 
 int i, position, key; 
 dic.m = REGION_LEN; 
 for (i = 0; i < REGION_LEN; i++) 
 dic.element[i].key = null; 
 while (1) { 
 printf("Input 1 to insert element\n" 
 "2 to search element\n" 
 "else to exit\nWhat do you want to do?"); 
 scanf("%d",&i); 
 if (i == 1){ 
 printf("Input the key you want to insert:"); 
 scanf("%d", &key); 
 if (linearInsert(&dic, key) == FALSE) 
 printf("There is no space!\n"); 
 } 
 else if (i == 2){ 
 printf("Input the key you want to search:"); 
 scanf("%d", &key); 
 if(linearSearch(&dic, key, &position) == TRUE) 
 printf("It is the %dth element!\n", position+1); 
 else printf("It is not in the dictionary!\n"); 
 } 
 else break; 
 } 
 return 0; 
}