search.txt

查找算法,在VC中实现的查找算法,希望对爱好编程的朋友有所帮助!

查找操作   
 1．掌握各种查找的基本思想和方法； 
2．灵活使用高级程序设计语言实现查找算法。 
实验内容： 
1.设计一个程序设计折半查找。 
2.设计一个解决哈希查找中碰撞时的方法，并用程序实现。  
 
 

/* 本程序提供了用顺序表实现字典的情况下 
的二分法检索算法*/ 

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

typedef int KeyType ; 

typedef struct { 
 KeyType key; /* 字典元素的关键码字段 */ 
 /*DataType value; /* 字典元素的属性字段 */ 
} DicElement; /*元素字典*/ 

typedef struct { 
 int n; /* n<=MAXNUM，为字典中元素的个数 */ 
 DicElement element[MAXNUM]; 
} SeqDictionary; 

/* 在字典中用二分法查找关键码为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; /* 要检索的元素在左半区 */ 
 else low = mid+1; /* 要检索的元素在右半区 */ 
 } 
 *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; 
} 


/* 本程序是用开地址法实现散列的检索算法*/ 

#include<stdio.h> 

#define TRUE 1 
#define FALSE 0 

#define null -1 /* null为空结点标记 */ 
#define REGION_LEN 13 

typedef int KeyType; 

typedef struct { 
 KeyType key; /* 字典元素的关键码字段 */ 
 /*DataType value; /* 字典元素的属性字段 */ 
} DicElement; 

typedef struct { 
 int m; /* m=REGION_LEN，为基本区域长度 */ 
 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为散列地址，散列函数为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 )/* 已有关键码为key的结点*/ 
 printf("Find\n"); 
 else if(position != -1) {  
 phash->element[position].key = key; /* 插入结点，还应对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; 
}