哈希表 and 算法
哈希表：
哈希表（Hash table），也被称为散列表，是一种根据关键码值（Key value）而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数被称为散列函数或哈希函数，而存放记录的数组则被称为散列表或哈希表。
哈希表的优点
- 查找速度快：哈希表通过哈希函数直接定位到数组中的位置，因此查找速度非常快，时间复杂度接近O(1)。
- 插入和删除操作方便：由于哈希表是基于数组实现的，因此插入和删除操作也相对简单。
- 空间利用率高：哈希表通过哈希函数将关键码值映射到有限的数组空间中，可以高效地利用存储空间。
哈希表的缺点
- 冲突问题：不同的关键码值可能通过哈希函数得到相同的哈希值，即产生冲突。解决冲突的方法有多种，如开放寻址法、链地址法等。
- 哈希函数的选择：哈希函数的选择对哈希表的性能有很大影响。一个好的哈希函数应该能够均匀地分布哈希值，减少冲突的发生。
- 动态扩容问题：当哈希表中的元素数量增加到一定程度时，可能需要进行动态扩容以维持性能。扩容操作会涉及到数据的重新哈希和存储，可能会带来一定的性能开销。
#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
HSNode_t *hashtable[HASH_SIZE] = {NULL};
int hash_function(char key) //哈希表函数
{
if (key >='a'&&key<='z')
{
return key - 'a';
}
else if(key >= 'A'&&key <= 'Z')
{
return key - 'A';
}
else
{
return HASH_SIZE-1;
}
}
int intsert_hashtable(HSDataType data)//向哈希表添加元素
{
int addr = hash_function(data.name[0]);
HSNode_t *pnode =(HSNode_t*)malloc(sizeof(HSNode_t));
if(pnode == NULL)
{
perror("malloc fail");
return 0;
}
pnode->data = data;
pnode -> pnext = NULL;
if(hashtable[addr] == NULL)
{
hashtable[addr] = pnode;
return 0;
}
pnode ->pnext = hashtable[addr]->pnext;
hashtable[addr]->pnext = pnode;
return 0;
}
HSNode_t *find_hashtable(char *name)//查找
{
int addr = hash_function(name[0]);
HSNode_t *p = hashtable[addr];
while(p != NULL)
{
if(!strncmp(p->data.name,name,strlen(name)))
{
break;
}
p = p->pnext;
}
return p;
}
void print_hashtable()//打印哈希表
{
int i = 0;
for( i = 0 ; i<HASH_SIZE;++i)
{
HSNode_t *p = hashtable[i];
while( p!= NULL)
{
printf("%s,%s\n",p->data.name,p->data.tel);
p = p->pnext;
}
}
return ;
}
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);
}
}
}
算法：
排序：
选择排序法：
基本思想：
第1次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后 再从剩余的元素中选择最小（或最大）的元素，然后放到已排序的序列的末尾。以此类推， 直到全部待排序的数据元素排完。
时间复杂度：O(n^2)
稳定性：不稳定
代码：
int main(void)
{
int a[] = {1,2,4,3,6,7,8,5,9,0};
int len = sizeof(a) / sizeof(a[0]);
int i,j;
for(i = 0;i < len -1;++i)
{
for(j = i + 1;j < len;++j)
{
if(a[i] > a[j])
{
int t;
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
}
插入排序法：
基本思想：
是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。在 整个排序过程中，我们反复地将一个记录插入到前面已排好序的序列中，直到全部记录插入 完成，排序也就结束了。
时间复杂度：O(n^2)
稳定性：不稳定
代码：
int main(void)
{
int a[] = {1,4,5,6,2,8,3,7,9,0};
int len = sizeof(a) / sizeof(a[0]);
int i;
for(i = 1; i< len;++i)
{
int j;
int t = a[i];
j = i;
while(j >0 && a[j - 1]>t)
{
a[j] = a[j - 1];
--j;
}
a[j] = t;
}
return 0;
}
冒泡排序法：
基本思想：
通过重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过 来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
时间复杂度：O(n^2)
稳定性：稳定
代码
int main(void)
{
int a[] = {1,4,5,6,2,8,3,7,9,0};
int len = sizeof(a) / sizeof(a[0]);
int i,j;
for(j = len - 1;j > 0;--j)
{
for(i = 0;i < j;++i)
{
if(a[i] > a[i + 1])
{
int t;
t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
return 0;
}
快速排序法：
基本思想：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分 的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以 递归进行，以此达到整个数据变成有序序列。
时间复杂度：O(n log n)
稳定性：不稳定
代码：
#include <stdio.h>
void print_array(int *a,int len)
{
for(int i = 0;i < len ;++i)
{
printf("%d,",a[i]);
}
printf("\n");
}
void quick_sort(int *a,int begin ,int end)
{
int i = begin;
int j = end;
int key = a[i];
if(i > j)
{
return ;
}
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);
}
int main(int argc, char *argv[])
{
int a[] = {1,-1,3,2,4,-5,6,-7,8,9};
int len = sizeof(a)/sizeof(a[0]);
quick_sort(a,0,len-1);
print_array(a,len);
return 0;
}