散列法解决1000个整数的搜索

爱被打了一巴掌 2022-04-21 14:50 44阅读 0赞

/\*  
\*散列法解决1000个整数的搜索问题（为了方便显示结果，程序中将1000改为了100）  
\*/

\#include<stdio.h>  
\#include<stdlib.h>  
\#include<windows.h>  
\#include<time.h>  
\#define LEN 100  
typedef int dataType;

typedef struct HNode  
\{  
dataType key; //关键字  
int flag; //判断是否被赋值  
\}HNode;

//初始化数据  
void initData(dataType data\[\],int len);  
//打印数据  
void printData(dataType data\[\],int len);  
//在原数组中查找元素下标，找不到则返回-1  
int searchInData(dataType data\[\],int d);  
//初始化哈希表  
void initHash(HNode arr\[\],dataType data\[\],int len);  
//打印哈希表  
void printHash(HNode arr\[\],int len);

//如果冲突，采用开放地址法的线性探测在散列  
int getIndex(HNode arr\[\],int d);

//查找元素，查找成功返回1，否则返回0  
int search(HNode arr\[\],int d);

int main()  
\{  
int keyword;  
int tempIndex;  
dataType data\[LEN\];  
HNode arr\[LEN\];  
initData(data,LEN);  
printData(data,LEN);  
initHash(arr,data,LEN);  
printHash(arr,LEN);

printf("\\n输入要查找的整数(输入q结束):");  
while(scanf("%d",&keyword))  
\{  
tempIndex = searchInData(data,keyword);  
if(tempIndex != -1)  
\{  
printf("%d在元素数组中的下标是%d\\n",keyword,tempIndex);  
\}  
if(search(arr,keyword))  
\{  
printf("查找成功!\\n");  
\}  
else  
\{  
printf("查找失败!\\n");  
\}  
printf("\\n输入要查找的整数(输入q结束):");  
\}  
  
return 0;  
\}

//初始化数据  
void initData(dataType data\[\],int len)  
\{  
int i;  
srand((unsigned)time(NULL));  
for(i = 0; i < len; i++)  
\{  
data\[i\] = rand();  
\}  
\}

//打印数据  
void printData(dataType data\[\],int len)  
\{  
int i;

printf("原始数据:");  
for(i = 0; i < len; i++)  
\{  
if(i % 10 == 0)  
\{  
printf("\\n");  
\}  
printf("%d\\t",data\[i\]);  
\}  
printf("\\n");  
\}

//在原数组中查找元素下标，找不到则返回-1  
int searchInData(dataType data\[\],int d)  
\{  
int i;

for(i = 0; i < LEN; i++)  
\{  
if(data\[i\] == d)  
\{  
return i;  
\}  
\}  
return -1;  
\}

//初始化哈希表  
void initHash(HNode arr\[\],dataType data\[\],int len)  
\{  
int i;  
int index;  
for(i = 0; i < len; i++)  
\{  
index = getIndex(arr,data\[i\]);  
arr\[index\].key = data\[i\];  
arr\[index\].flag = 1;  
\}  
\}

//打印哈希表  
void printHash(HNode arr\[\],int len)  
\{  
int i;

printf("Hash表中的数据:");  
for(i = 0; i < len; i++)  
\{  
if(i % 10 == 0)  
\{  
printf("\\n");  
\}  
printf("%d\\t",arr\[i\].key);  
\}  
printf("\\n");  
\}

int getIndex(HNode arr\[\],int d)  
\{  
int result = 0;  
result = d % LEN;  
//如果冲突了  
while(arr\[result\].flag == 1)  
\{  
result = (result + 1) % LEN;  
\}  
return result;  
\}  
//查找元素，查找成功返回1，否则返回0  
int search(HNode arr\[\],int d)  
\{  
int circle = 0;  
int index = 0;  
index = d % LEN;  
while(arr\[index\].key != d)  
\{  
if((circle == 1) && (index == d % LEN))  
break;  
index = (index + 1) % LEN;  
if(index >= LEN -1)  
\{//已经扫描到尾了  
circle++;  
\}  
\}  
if(arr\[index\].key == d)  
\{  
return 1;  
\}  
return 0;  
\}

运行结果：

![1356839723_6927.jpg][]

/\*博主寄语：如若发现错误，望指出，谢谢\*/

[1356839723_6927.jpg]: https://img-my.csdn.net/uploads/201212/30/1356839723_6927.jpg