当前位置：首页 > news >正文

哈希表及算法

news 2025/6/18 12:37:38

哈希表

在记录的存储位置和它的关键字之间建立一种去特定的对应关系，使得每个关键字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 27typedef 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);}
}

查看全文

http://www.mrgr.cn/news/23043.html