23、数据结构/查找相关练习20240205

一、请编程实现哈希表的创建存储数组{12,24,234,234,23,234,23},输入key查找的值，实现查找功能。

代码：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<math.h>
typedef struct Node
{int data;struct node *next;
}*list;
int max_prime(int m)
{int i=m;for(i;i>1;i--){int flag=0;for(int j=2;j<=sqrt(i);j++){if(i%j==0){flag=-1;break;}}if(flag==0)return i;}
}
list create_node()
{list s=(list)malloc(sizeof(struct Node));if(NULL==s)return NULL;s->data=0;s->next=NULL;return s;
}
void insert_hash(int arr,int p,list hash[])
{int value=arr%p;list s=create_node();s->data=arr;if(NULL==hash[value]){hash[value]=s;}else{s->next=hash[value];hash[value]=s;}
}
void output_hash(list hash[],int m)
{for(int i=0;i<m;i++){list p=hash[i];printf("%d: ",i);while(p){printf("%d ",p->data);p=p->next;}puts("end");}
}
int search_hash(list hash[],int p,int key)
{int value=key%p;list head=hash[value];while(head){if(head->data==key)return 0;head=head->next;}return -1;
}
int main(int argc, const char *argv[])
{int arr[]={12,24,234,234,23,234,23};int len=sizeof(arr)/sizeof(arr[0]);int m=len*4/3;//哈希表长list hash[m];for(int i=0;i<m;i++){hash[i]=NULL;}int p=max_prime(m);//计算不大于m的最大质数for(int i=0;i<len;i++){insert_hash(arr[i],p,hash);//循环输入数组元素存入哈希表；}output_hash(hash,m);//输出哈希表；int key;printf("please enter search key:");scanf("%d",&key);int flag=search_hash(hash,p,key);//根据输入的值查找if(flag==0)puts("exists");elseputs("unexists");return 0;
}

运行：

二、现有数组{12,23,45,56,445,5676,6888},请输入key实现二分查找。

代码：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
enum BISE
{SUCCESS,FAILURE
};
int binary_search(int *p,int len,int key)
{int low=0,high=len-1;while(low<=high){int mid=(low+high)/2;if(*(p+mid)<key){low=mid+1;}else if(*(p+mid)==key){return SUCCESS;}else if(*(p+mid)>key){high=mid-1;}}return FAILURE;
}
int main(int argc, const char *argv[])
{int arr[]={12,23,45,56,445,5676,6888};int len=sizeof(arr)/sizeof(arr[0]);int key;printf("please enter search key:");scanf("%d",&key);int flag=binary_search(arr,len,key);if(flag==SUCCESS)puts("exists");elseputs("unexists");return 0;
}

代码运行：