数据结构 day7 树+二叉树+哈希表

?哈希表功能实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
typedef struct Node
{
	//数据元素
	int data;
	//指针域：下一个节点的地址
	struct Node *next;
}*node;
/*
 * function:    计算小于等于m的最大质数
 * @param [ in] 
 * @param [out] 
 * @return      返回最大质素
 */
int Prime(int m)
{
	for(int i=m;i>=2;i--)
	{
		//判断i是否是素数
		//12: 2 3  4 6
		int flag=1;
		for(int j=2;j<=sqrt(i);j++)
		{
			if(i%j==0)
			{
				flag=0;
				break;
			}
		}
		if(flag==1)
			return i;
	}
}
/*
 * function:    创建节点
 * @param [ in] 
 * @param [out] 
 * @return      
 */
node create_node()
{
	node s=(node)malloc(sizeof(struct Node));
	if(NULL==s)
		return NULL;
	s->data=0;
	s->next=NULL;
	return s;
}
/*
 * function:    插入哈希表
 * @param [ in] 
 * @param [out] 
 * @return      无
 */
void insert_hash(node hash[],int key,int p)
{
	int index=key%p;
	//插入到hash[index]为头指针的单链表中
	
	//创建新节点
	node s=create_node();
	if(NULL==s)
		return;
	s->data=key;
	if(hash[index]==NULL)
		hash[index]=s;
	else
	{
		s->next=hash[index];
		hash[index]=s;
	}
}
/*
 * function:    循环输出哈希表
 * @param [ in] 
 * @param [out] 
 * @return      无
 */
void output(node hash[],int m)
{
	for(int i=0;i<m;i++)
	{
		//hash[i]类似单链表的head
		printf("%d:",i);
		node q=hash[i];
		while(q!=NULL)
		{
			printf("%-4d",q->data);
			q=q->next;
		}
		puts("NULL");
	}
}
/*
 * function:    哈希查找
 * @param [ in] 
 * @param [out] 
 * @return      成功返回0 失败返回-1
 */
int search_hash(node hash[],int key,int p)
{
	int index=key%p;
	//查找hash[index]该链表中是否存在查找元素key
	node q=hash[index];
	if(q==NULL)
		return -1;
	while(q!=NULL)
	{
		if(q->data==key)
			return 0;
		q=q->next;
	}
	return -1;
}
int main(int argc, const char *argv[])
{
	//数组
	int arr[]={41,54,67,25,51,8,22,26,11,16};
	
	//把数组元素通过哈希函数存到哈希表
	//哈希表
	//数组长度
	int len=sizeof(arr)/sizeof(arr[0]);
	//哈希表长度
	int m=len*4/3;
	int p=Prime(m);
	node hash[m];
	//防止野指针
	for(int i=0;i<m;i++)
	{
		hash[i]=NULL;
	}
	
	//把数组存储到哈希表
	for(int i=0;i<len;i++)
	{
		insert_hash(hash,arr[i],p);
	}

	//遍历哈希表
	output(hash,m);

	//查找
	int key;
	printf("plase enter key:");
	scanf("%d",&key);
	int flag=search_hash(hash,key,p);
	if(flag==-1)
		puts("unexists");
	else
		puts("exists");
	return 0;
}