寒假作业-day4

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

代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef int datatype;
typedef struct Node{
	datatype data;
	struct Node *next;
}*node;

int maxprime(int m);
node create();
void insert_hash(int key,int p,node hash[]);
void output(node hash[],int m);
void search_hash(datatype key,int p,node hash[]);

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;
	int p=maxprime(m);
	node hash[m];
	for(int i=0;i<m;i++)
		hash[i]=NULL;
	for(int i=0;i<len;i++){
		insert_hash(arr[i],p,hash);
		output(hash,m);
	}
//	search_hash(23,p,hash);
	return 0;
}

int maxprime(int m){
	for(int i=m;i>=2;i--){
		int flag=0;
		for(int j=2;j<sqrt(i);j++){
			if(i%j==0)
			flag=1;
			break;
		}
		if(flag==0)
			return i;
	}
}
node create(){
	node p=(node)malloc(sizeof(struct Node));
	if(!p)
		return NULL;
	p->data=0;
	p->next=NULL;
	return p;
}
void insert_hash(int key,int p,node hash[]){
	int index=key%p;
	node q=create();
	q->data=key;
	if(!hash[index]){
		hash[index]=q;
	}
	else{
		q->next=hash[index];
		hash[index]=q;
	}
}

void output(node hash[],int m){
	for(int i=0;i<m;i++){
		node p=hash[i];
		printf("hash[%d]:",i);
		while(p){
			printf("%d\t",p->data);
			p=p->next;
		}
		puts("");
		}
	puts("------------------------------");
}
void search_hash(datatype key,int p,node hash[]){
	int index=key%p;
	node q=hash[index];
	int flag=0;
	while(q){
		if(q->data==key){
			printf("can find %d\n",key);
			flag=1;
			break;		
		}
		q=q->next;
	}
	if(flag==0)
		printf("No\n");
}

结果：

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

代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int search(int arr[],int key,int low,int high){
	while(low<=high){
		int mid=(low+high)/2;
		if(arr[mid]==key)
			return mid;
		if(arr[mid]>key)
			return search(arr,key,low,mid-1);
		if(arr[mid]<key)
			return search(arr,key,mid+1,high);
	}
	return -1000000;
}
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("请输入关键字：");
	scanf("%d",&key);
	printf("%d\n",search(arr,key,0,len-1));
	return 0;
}

结果：