【C语言】【数据结构】查找（顺序查找、折半查找、哈希查找）

1、顺序查找

顺序查找：从最后一个开始逐个比较

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1

typedef int Status;

typedef int ElemType;
typedef struct SSTable{
	ElemType *elem;
	int length;
}SSTable;

//顺序查找 
Status Create_Seq(SSTable & , int );	//建表（从1开始）
int Search_Seq(SSTable , ElemType );	//顺序查找

int main()
{
	SSTable ST;		
	int n;
	ElemType key;
	int loc;
	
	printf("请输入元素个数：\n");
	scanf("%d", &n);
	if(!Create_Seq(ST, n)) printf("Create Error!\n");
	printf("请输入要查找关键字的值：\n");
	scanf("%d", &key);
	loc = Search_Seq(ST,key);
	if(loc == 0) printf("This element is not exist.\n");
	else printf("The element position is %d.\n", loc);
}

//建表
Status Create_Seq(SSTable &ST, int n)
{
	int i;
	
	ST.elem = (ElemType *) malloc ((n+1) * sizeof(ElemType));
	if(!ST.elem) return ERROR;
	ST.length = n;
	printf("请依次输入%d个关键字的值（用空格隔开）：\n", n); 
	for(i=1; i<=n; i++)				//把数组的第一个位置0空出来作为监视哨
		scanf("%d", &ST.elem[i]);
	return OK;
}

int Search_Seq(SSTable ST, ElemType key)
{
	int i;
	
	ST.elem[0] = key;
	for(i=ST.length; i>=0; i--)
		if(ST.elem[i] == key) return i;		//监视哨的目的，免去检测是否查找完毕
}

2、二分查找（折半查找）

二分查找：三个指针low、high、mid，与mid位置关键字比较

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1

typedef int Status;

typedef int ElemType;
typedef struct SSTable{
	ElemType *elem;
	int length;
}BSTable;

//二分查找 
Status CreateTable(BSTable & , int );	//建表（从0开始）
int BinarySearch(BSTable , ElemType );	//二分查找

int main()
{
	//二分查找 		
	BSTable ST;
	int n;
	ElemType key;
	int loc;
	
	printf("请输入元素个数：\n");
	scanf("%d", &n);
	if(!CreateTable(ST, n)) printf("Create Error!\n");
	printf("请输入要查找关键字的值：\n");
	scanf("%d", &key);
	loc =  BinarySearch(ST, key);
	if(loc == -1) printf("This element is not exist.\n");
	else printf("The element position is %d.\n", loc);
}

Status CreateTable(BSTable &ST, int n)
{
	int i;
	
	ST.elem = (ElemType *) malloc (n * sizeof(ElemType));
	if(!ST.elem) return ERROR;
	ST.length = n;
	printf("请依次输入%d个关键字的值（用空格隔开）：\n", n); 
	for(i=0; i<n; i++)
		scanf("%d", &ST.elem[i]);
	return OK;
}

int BinarySearch(BSTable ST, ElemType key)
{
	int low, high, mid;
	
	low = 0;
	high = ST.length-1;
	while(high>=low)
	{
		mid = (high + low) / 2;
		if(key == ST.elem[mid]) return mid;
		else if(key < ST.elem[mid]) high = mid-1;
		else low = mid+1;
	}
	return -1;
}

3、哈希查找

使用哈希函数：H(k)=3*k MOD length，并采用开放定址法处理冲突。试对输入的关键字序列构造哈希表，哈希表长度为length，求等概率情况下查找成功的平均查找长度，并设计构造哈希表的完整的算法。

#include"malloc.h" /* malloc()等 */
#include"stdlib.h" /* exit() */
#include"stdio.h"
#define EQ(a,b) ((a)==(b))
#define SUCCESS 1
#define UNSUCCESS 0
#define NULLKEY -1 /*哈希表无元素时值为-1*/

typedef int ElemType;
int length;
typedef struct
{
   ElemType *elem; /* 数据元素存储基址，动态分配数组 */
   int count; /* 当前数据元素个数 */
}HashTable;

void InitHashTable(HashTable * );	//构建 
unsigned Hash(ElemType );	//哈希函数（用在查找中） 
void collision(int * );		//解决冲突（用在查找中） 
int SearchHash(HashTable ,ElemType ,int * ,int *);	//查找插入位置（用在插入中） 
int InsertHash(HashTable * ,ElemType );		//插入
void TraverseHash(HashTable );	//遍历

main()
{
	float i=0,j=0;
	ElemType e;
	HashTable H;
         //printf("Input Table length:");
	scanf("%d",&length);
	InitHashTable(&H);
	//printf("Input key words sequence, -1 conclusion input：");
	scanf("%d",&e);
	while(e!=-1)
	{
		j ++;  /*j记录输入元素个数*/
		i = i + InsertHash(&H,e);  /*i记录查找长度的和*/ 
		scanf("%d",&e);		                       
	}
	TraverseHash(H);	
	printf("Average search length=%f\n",i/j);
}


void InitHashTable(HashTable *H)
{ /* 操作结果: 构造一个长度为length的哈希表,length为全局变量 */
	int i;
	(*H).count=0; /* 当前元素个数为0 */
	(*H).elem=(ElemType*)malloc(length*sizeof(ElemType));
	if(!(*H).elem)
		exit(0); /* 存储分配失败 */
	for(i=0;i<length;i++)
		(*H).elem[i]=NULLKEY; /* 未填记录的标志 */
}

unsigned Hash(ElemType K)	/* 一个简单的哈希函数*/
{ 
	return 3*K % length;
}

void collision(int *p) /*线性探测再散列 */
{ /* 开放定址法处理冲突 */
	*p = (*p+1) % length;
}

int SearchHash(HashTable H,ElemType K,int *p,int *c)
{  /* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 */
   /* 元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS */
   /* c用以计冲突次数，其初值置零，供建表插入时参考。算法9.17 */
	*p=Hash(K); /* 求得哈希地址 */
	while(H.elem[*p]!=NULLKEY&&!EQ(K,H.elem[*p]))
	{ /* 该位置中填有记录,并且关键字不相等 */
		(*c)++;
		if(*c<length)
			collision(p); /* 求得下一探查地址p */
		else
			break;
	}
	if EQ(K,H.elem[*p])
		return SUCCESS; /* 查找成功，p返回待查数据元素位置 */
	else
		return UNSUCCESS; /* 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置 */
}

int InsertHash(HashTable *H,ElemType e)
{ /* 查找不成功时插入数据元素e到开放定址哈希表H中，并返回查找长度 */
	int c,p;
	c=0;
	if(SearchHash(*H,e,&p,&c))   /* 表中已有与e有相同关键字的元素 */
		printf("哈希表中已有元素%d。\n",e);
	else{ /* 插入e */  
		(*H).elem[p]=e; 
		++(*H).count;
	}
	return c+1; /*查找长度为冲突次数加1*/
}

void TraverseHash(HashTable H)
{ /* 按哈希地址的顺序打印哈希表，无元素位置用X表示 */
	int i;
	printf("HashTable Address:0～%d\n",length-1);
	for(i=0;i<length;i++)
		if(H.elem[i]==NULLKEY) /* 有数据 */
			printf("X ");
	else
		printf("%d ",H.elem[i]); 
		printf("\n");
}