哈希表及算法
哈希表
在记录的存储位置和它的关键字之间建立一种去特定的对应关系，使得每个关键字key对应一个存储位置；查找时，根据确定的对应关系，找到给定的key的映射。
address = f(key);
我们把这种关系f称为哈希函数（散列函数）；采用这种散列技术将记录存储在一块连续的存储空间，这块连续存储开空间称为哈希表或散列表。
存储时，通过散列函数计算出记录的散列地址；
查找时，根据同样的散列函数计算记录的散列地址，并按此散列地址访问记录。
哈希冲突/哈希矛盾：关键字key不同，经过哈希函数后映射的位置相同，可以用链地址法解决哈希矛盾
链地址法（指针数组）：哈希表中存储链表首地址
将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在哈希表中只存储所有同义词子表的头指针。 此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。
对于关键字集合{12,67,56,16,25,37,22,29,15,47,48,34}，用12为除数，进行除留余数法，可得到如图结构。
哈希表相关操作
1. 创建哈希表
2. 设计哈希函数
3. 插入数据
4. 查找
5. 销毁
6. 遍历
HSNode_t *hashtable[HASH_SIZE] = {NULL};
int hash_function(char key) //哈希函数
{
if(key >= 'a' && key <= 'z')
{
return key - 'a';
}
if(key >= 'A' && key <= 'Z')
{
return key - 'A';
}
else
{
return HASH_SIZE - 1;
}
}
int insert_hashtable(HSDataType data) //插入
{
int addr = hash_function(data.name[0]);
HSNode_t *pnode = malloc(sizeof(HSNode_t));
if(pnode == NULL)
{
perror("malloc fail");
return -1;
}
pnode->data = data;
pnode->pnext = NULL;
if(hashtable[addr] == NULL)
{
hashtable[addr] = pnode;
}
else
{
pnode->pnext = hashtable[addr];
hashtable[addr] = pnode;
}
return 0;
}
void print_hashtable() //遍历
{
for(int i = 0;i < HASH_SIZE - 1;++i)
{
HSNode_t *p = hashtable[i];
while(p != NULL)
{
printf("%s\n",p->data.name);
p = p->pnext;
}
}
}
HSNode_t *find_hashtable(char *name) //查找
{
int addr = hash_function(name[0]);
HSNode_t *p = hashtable[addr];
while(p != NULL)
{
if(strcmp(p->data.name,name) == 0)
{
return p;
}
p = p->pnext;
}
}
void destroy_hashtable() //销毁
{
for(int i = 0;i < HASH_SIZE;++i)
{
while(hashtable[i] != NULL)
{
HSNode_t *p = hashtable[i];
hashtable[i] = p->pnext;
free(p);
}
}
}#define HASH_SIZE 27
typedef struct per
{
char name[64];
char tel[64];
}HSDataType;
typedef struct hsnode
{
HSDataType data;
struct hsnode *pnext;
}HSNode_t;int main(void)
{
HSDataType pers[] = {{"zhangsan","110"},{"lisi","120"},{"wangwu","119"},{"maliu","10086"},{"zhaoqi","12306"}};
insert_hashtable(pers[0]);
insert_hashtable(pers[1]);
insert_hashtable(pers[2]);
insert_hashtable(pers[3]);
insert_hashtable(pers[4]);
print_hashtable();
char name[] = "wangwu";
HSNode_t*p = find_hashtable(name);
printf("%s tel = %s\n",name,p->data.tel);
destroy_hashtable();
return 0;
}算法：
解决特定问题求解步骤
算法的设计，
1.正确性，
语法正确
合法的输入能得到合理的结果。
对非法的输入，给出满足要求的规格说明
对精心选择，甚至刁难的测试都能正常运行，结果正确
2. 可读性，便于交流，阅读，理解 高内聚 低耦合
3. 健壮性，输入非法数据，能进行相应的处理，而不是产生异常
4. 高效率(时间复杂度)
5. 低存储（空间复杂度）
算法时间复杂度
执行这个算法所花时间的度量
将数据量增长和时间增长用函数表示出来，这个函数就叫做时间复杂度。
一般用大O表示法：O（n）-----时间复杂度是关于数据n的一个函数
随着n的增加，时间复杂度增长较慢的算法时间复杂度低
时间复杂度的计算规则：
1，用常数1 取代运行时间中的所有加法常数
2，在修改后的运行函数中，只保留最高阶项。
3，如果最高阶存在且系数不是1，则去除这个项相乘的常数。
算法复杂度 O（1）
算法复杂度O（n）
冒泡排序
思想：相邻两元素两两比较，小的放前，大的放后
时间复杂度：O(n^2)
排序算法的稳定性：稳定
选择排序
思想：数组合适的位置放合适的数
时间复杂度：O（n^2）
稳定性：不稳定
插入排序
思想：将无序的数组中的数插入有序的数组
时间复杂度：O（n^2）
稳定性：稳定
快速排序：
思想：选择一基准值key,比key大的放后面，比key小的放前面
时间复杂度：O(nlogn)
稳定性：不稳定
void quick_sort(int *a, int begin, int end)
{
if (begin >= end)
{
return ;
}
int i = begin;
int j = end;
int key = a[i];
while (i < j)
{
while (i < j && a[j] >= key)
{
j--;
}
a[i] = a[j];
while (i < j && a[i] <= key)
{
i++;
}
a[j] = a[i];
}
a[i] = key;
quick_sort(a, begin, i-1);
quick_sort(a, i+1, end);
}二分查找（折半查找）： 序列必须有序
算法复杂度： O(logn)
int binarysearch(int *a,int len,int n)
{
int begin = 0,mid = 0;
int end = len - 1;
while(begin <= end)
{
mid = (begin + end) / 2;
if(a[mid] > n)
{
end = mid - 1;
}
else if(a[mid] < n)
{
begin = mid + 1;
}
else
{
break;
}
}
if(begin <= end)
{
printf("find %d\n",a[mid]);
printf("mid %d\n",mid);
}
}