摘要： 查数据无论是在生活中还是在计算机中都十分常见。常见的查找算法有顺序查找，二分查找和哈希查找。
顺序查找就是挨个挨个比对，其时间复杂度为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;
}
else if(paraList->elements[tempMiddle].key < paraKey)
{
tempLeft = tempMiddle + 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: %crn", binarySearch(tempListPtr, 10));
printf("Search result of 5 is: %crn", binarySearch(tempListPtr, 5));
printf("Search result of 4 is: %crn", binarySearch(tempListPtr, 4));
printf("Search result of 2 is: %crn", 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: %crn", hashSearch(tempPtr, 95));
printf("Search result of 38 is: %crn", hashSearch(tempPtr, 38));
printf("Search result of 57 is: %crn", hashSearch(tempPtr, 57));
printf("Search result of 4 is: %crn", 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-----------
