哈希表 and 算法

哈希表：

哈希表（Hash table），也被称为散列表，是一种根据关键码值（Key value）而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数被称为散列函数或哈希函数，而存放记录的数组则被称为散列表或哈希表。

哈希表的优点

1. 查找速度快：哈希表通过哈希函数直接定位到数组中的位置，因此查找速度非常快，时间复杂度接近O(1)。
2. 插入和删除操作方便：由于哈希表是基于数组实现的，因此插入和删除操作也相对简单。
3. 空间利用率高：哈希表通过哈希函数将关键码值映射到有限的数组空间中，可以高效地利用存储空间。

哈希表的缺点

1. 冲突问题：不同的关键码值可能通过哈希函数得到相同的哈希值，即产生冲突。解决冲突的方法有多种，如开放寻址法、链地址法等。
2. 哈希函数的选择：哈希函数的选择对哈希表的性能有很大影响。一个好的哈希函数应该能够均匀地分布哈希值，减少冲突的发生。
3. 动态扩容问题：当哈希表中的元素数量增加到一定程度时，可能需要进行动态扩容以维持性能。扩容操作会涉及到数据的重新哈希和存储，可能会带来一定的性能开销。

#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;
}