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

哈希表 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;
}

http://www.lryc.cn/news/433726.html

相关文章:

  • Comsol 共用声固耦合边界与热粘性声学边界的亥姆霍兹腔体超材料板精准隔声设计
  • Linux系统本地化部署Dify并安装Ollama运行llava大语言模型详细教程
  • 极光出席深圳国际人工智能展并荣获“最具投资价值人工智能奖”
  • 人工智能领域的性能指的是什么
  • SQL进阶技巧:如何利用SQL解决趣味赛马问题?| 非等值关联匹配问题
  • Vue Echarts报错Initialize failed: invalid dom解决方法
  • MySQL—死锁
  • CS5363|CS5263升级方案|DP转HDMI 4K60HZ芯片方案
  • Git Lab 项目迁移到gitee 并且包含提交记录
  • 如何用用智能码二维码zhinengma.cn做空调机房巡检
  • 如何与客户保持高度粘性?这个系统给您答案
  • 算法知识点————两个栈实现一个队列
  • 并行程序设计基础——并行I/O(1)
  • 在JS中的设计模式的单例模式、策略模式、代理模式、原型模式浅讲
  • JVM系列(十) -垃圾收集器介绍
  • 项目实战 ---- 商用落地视频搜索系统(9)---UI与上层service的交互优化
  • 媒体服务器软件BUG说明及改进方案
  • Gitlab修改已push的历史commit信息
  • [Linux入门]---进程替换
  • Java语言程序设计基础篇_编程练习题*18.9 (以逆序输出一个字符串中的字符)
  • IT英语每日积累
  • QML学习二:Qt启用qml文件实时预览编辑,以及打印日志到控制台
  • JVM面试真题总结(四)
  • P1352 没有上司的舞会
  • JAVA智听未来一站式有声阅读平台听书系统小程序源码
  • 2024 第七届“巅峰极客”网络安全技能挑战赛初赛 Web方向 题解WirteUp
  • 论文阅读笔记《面向集群协同的两点相对定位技术》
  • RK3566/RK3568 Android 11 无操作自动隐藏导航栏、底部上拉显示导航栏
  • 四、Django模型
  • Telephony SS