数据结构19:二分查找与哈希查找

  • Post author:
  • Post category:其他



摘要:

查数据无论是在生活中还是在计算机中都十分常见。常见的查找算法有顺序查找,二分查找和哈希查找。

顺序查找就是挨个挨个比对,其时间复杂度为O(n),由于比较简单,所有没有写。

二分查找针对的是有序的数据,其时间复杂度为O(log n)每一次取中点值与要查找的数据进行对比,直到找到为止。

哈希查找,

核心思想是用空间换时间

,在数据无重复的情况下,其时间复杂度为O(1),如果有数据重复,其查找次数取决于重复的个数以及重复数据存储方法。重点是在初始化的时候,我们要通过数据知道他的存储位置,从而实现无重复时一次找到,下面的代码使用较简单的除数取余法获得数据存放地址 (下标),并且通过线性探测再散列(顺移)的方法解决冲突。

其重点是在初始化的时候处理数据存放的位置



一.折半查找


1)创建

typedef struct node
{
	int key;
	char data;
}*nodePtr;

typedef struct list
{
	int length;
	nodePtr elements; 
}*listPtr;


2)初始化

listPtr binarySearchInit(int paraLength,int* paraKeyArray,char* paraDataArray)
{
	int i; 
	listPtr resultList = (listPtr)malloc(sizeof(struct list));
	
	resultList->length = paraLength;
	//我们第零个位置不用,数组大小申请n+1个; 
	resultList->elements = (nodePtr)malloc(sizeof(struct node)* (paraLength + 1));
	
	for(i = 0;i < paraLength;i ++)
	{
		resultList->elements[i + 1].key  = paraKeyArray[i];
		resultList->elements[i + 1].data  = paraDataArray[i];
	}
	
	return resultList;
}


3)查找函数

char binarySearch(listPtr paraList,int paraKey)
{
	int tempLeft = 1;
	int tempRight = paraList->length;
	int tempMiddle = (tempLeft + tempRight)/2;
	
	while(tempLeft <= tempRight)
	{
		//如果找到了就直接返回对应data 
		if(paraList->elements[tempMiddle].key == paraKey)
		{
			return paraList->elements[tempMiddle].data;
		}
		/*如果中间值比parakey要小,说明在右边,就把左移到中间+1的位置
		因为中间的值已经比对过了,不需要了*/ 
		else if(paraList->elements[tempMiddle].key < paraKey)
		{
			tempLeft = tempMiddle + 1;
		}
		/*同理,如果中间值比parakey要大,说明在左边,就把右移到中间-1
		的位置*/
		else
		{
			tempRight = tempMiddle - 1;
		}
		
		tempMiddle = (tempLeft + tempRight)/2;
	}
	
	return 'x';
}


4)测试函数

void binarySearchTest() 
{
	int tempUnsortedKeys[] = { 1, 3, 4, 5, 6, 7, 9, 10 };
	char tempContents[] = { 'h', 'e', 'l', 'o', 'w', 'r', 'd', '!' };
	listPtr tempListPtr = binarySearchInit(8,tempUnsortedKeys, tempContents);

	printf("Search result of 10 is: %c\r\n", binarySearch(tempListPtr, 10));
	printf("Search result of 5 is: %c\r\n", binarySearch(tempListPtr, 5));
	printf("Search result of 4 is: %c\r\n", binarySearch(tempListPtr, 4));
	printf("Search result of 2 is: %c\r\n", binarySearch(tempListPtr, 2));
}


5)运行结果

Binary search begins-------
Search result of 10 is: !
Search result of 5 is: o
Search result of 4 is: l
Search result of 2 is: x
Binary search ends---------



二.哈希查找


1)创建

//表的总大小,我们要用空间换时间,尽量大一点 
#define TABLE_SIZE 500
//这个是代表要取余的数 
#define MODKEY 19 

typedef struct node
{
	int key;
	char data;
}*nodePtr;

typedef struct list
{
	int length;
	nodePtr elements; 
}*listPtr;


2)初始化

listPtr hashSearchInit(int paraLength,int* paraKeyArray,char* paraDataArray)
{
	int i,tempPosition;
	listPtr resultList = (listPtr)malloc(sizeof(struct list));
	resultList->length = paraLength;
	
	resultList->elements = (nodePtr)malloc(sizeof(struct node) * TABLE_SIZE);
	
	//先初始化把所有的key设置为-1代表没有数据 
	for(i = 0;i < TABLE_SIZE;i ++)
	{
		resultList->elements[i].key = -1;
		resultList->elements[i].data = 'x';
	}
	
	for(i = 0;i < paraLength;i ++)
	{
		tempPosition = paraKeyArray[i] % MODKEY;
		
		//找位置放置,如果位置被占了,就顺移到下一个没人占的空位置 
		while(resultList->elements[tempPosition].key != -1)
		{
			tempPosition = (tempPosition + 1) % MODKEY;
		}
		
		resultList->elements[tempPosition].key = paraKeyArray[i];
		resultList->elements[tempPosition].data = paraDataArray[i];
	}
	
	return resultList;
}


3)查找函数

char hashSearch(listPtr paraList,int paraKey)
{
	int tempPosition = paraKey % MODKEY;
	
	//如果都到了没人占的位置,说明表中没有这个数据 
	while(paraList->elements[tempPosition].key != -1)
	{
		if(paraList->elements[tempPosition].key == paraKey)
		{
			return paraList->elements[tempPosition].data;
		}	
		tempPosition = (tempPosition + 1) % MODKEY;
	}
	
	return 'x'; 
}


4)测试函数

void hashSearchTest() 
{
	int tempUnsortedKeys[] = { 16, 33, 38, 69, 57, 95, 86 };
	char tempContents[] = { 'h', 'e', 'l', 'o', 'w', 'r', 'd' };
	listPtr tempPtr = hashSearchInit(7,tempUnsortedKeys, tempContents);

	printf("Search result of 95 is: %c\r\n", hashSearch(tempPtr, 95));
	printf("Search result of 38 is: %c\r\n", hashSearch(tempPtr, 38));
	printf("Search result of 57 is: %c\r\n", hashSearch(tempPtr, 57));
	printf("Search result of 4 is: %c\r\n", hashSearch(tempPtr, 4));
}


5)运行结果

Hash search begins---------
Search result of 95 is: r
Search result of 38 is: l
Search result of 57 is: w
Search result of 4 is: x
Hash search ends-----------



版权声明:本文为qq_70132617原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。