当前位置: 首页 > 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;
}

相关文章:

哈希表 and 算法

哈希表&#xff1a; 哈希表&#xff08;Hash table&#xff09;&#xff0c;也被称为散列表&#xff0c;是一种根据关键码值&#xff08;Key value&#xff09;而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录&#xff0c;以加快查找的速度。这个映射…...

Comsol 共用声固耦合边界与热粘性声学边界的亥姆霍兹腔体超材料板精准隔声设计

声子晶体可分为局域共振型声子晶体和布拉格散射型声子晶体, 由于布拉格声子晶体需要的结构尺寸往往很大, 不便于实际应用; 而基于局域共振型机理的声子晶体能够实现“小体积控制大波长”, 因而有更加广泛的应用, 其中利用Helmholtz共鸣腔是局域共振型机理的典型应用, 近年来, H…...

Linux系统本地化部署Dify并安装Ollama运行llava大语言模型详细教程

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

极光出席深圳国际人工智能展并荣获“最具投资价值人工智能奖”

9月8-10日&#xff0c;由深圳市工业和信息化局、深圳市发展和改革委员会、深圳市科技创新局、深圳市政务服务和数据管理局、深圳市中小企业服务局共同指导&#xff0c;深圳市人工智能行业协会主办的第五届深圳国际人工智能展正式开幕。作为中国领先的客户互动和营销科技服务商&…...

人工智能领域的性能指的是什么

目录 1. 准确性&#xff08;Accuracy&#xff09; 2. 精确率与召回率&#xff08;Precision & Recall&#xff09; 3. F1分数 4. 运行时间与延迟&#xff08;Latency&#xff09; 5. 吞吐量&#xff08;Throughput&#xff09; 6. 可扩展性&#xff08;Scalability&a…...

SQL进阶技巧:如何利用SQL解决趣味赛马问题?| 非等值关联匹配问题

目录 0 问题描述 1 数据准备 2 问题分析 方法一:先分后合思想 方法2:非等值关联匹配 3 小结 0 问题描述 有一张赛马记录表,如下所示: create table RacingResults ( trace_id char(3) not null,race_date date not null, race_nbr int not null,win_name char(30) n…...

Vue Echarts报错Initialize failed: invalid dom解决方法

此问题是图表初始化时 找不到dom&#xff0c;以下是解决方法 1、不要用created&#xff08;用mounted&#xff09;&#xff0c;created这时候还只是创建了实例&#xff0c;但模板还没挂载完成&#xff1b; created&#xff1a; 在模板渲染成 html 前调用&#xff0c;通常初始…...

MySQL—死锁

什么是死锁&#xff1f; 好比是两个事务都在等待对方释放锁&#xff0c;之后进行下一步操作&#xff0c;但是最后双方都没有释放资源&#xff0c;所以导致一直处于等待的状态。 但是服务器不会让死锁的状态一直持续&#xff0c;会关闭其中一个影响较小的事务&#xff08;右边的…...

CS5363|CS5263升级方案|DP转HDMI 4K60HZ芯片方案

CS5363是一种高度集成的单芯片&#xff0c;适用于多个细分市场和显示应用&#xff0c;如Typec扩展、手机/电脑投屏、扩展底座、投影仪等。 CS5363管脚分布情况如下&#xff1a; CS5363是一款高度集成的单芯片&#xff0c;适用于多个mGeneral 支持最高分辨率/定时4k60Hz 支持…...

Git Lab 项目迁移到gitee 并且包含提交记录

步骤 1: 准备工作 1.安装Git&#xff1a;确保你在本地计算机上安装了Git。如果尚未安装&#xff0c;可以从Git官网下载并安装。 2.创建Gitee账号&#xff1a;如果你还没有Gitee账号&#xff0c;请先注册一个&#xff0c;访问Gitee官网进行注册。 3.创建新的Gitee仓库&#xff1…...

如何用用智能码二维码zhinengma.cn做空调机房巡检

用智能码二维码做空调机房巡检 引言 空调机房是保障建筑物内环境舒适度的关键设施&#xff0c;其巡检工作对于确保空调系统的稳定运行至关重要。通过引入智能码二维码技术&#xff0c;可以大大提高空调机房巡检的效率和准确性。 一、二维码在空调机房巡检中的应用 1.1 巡检…...

如何与客户保持高度粘性?这个系统给您答案

客户粘性是企业成功的关键因素之一&#xff0c;企客宝企微版在打通获客、转化、运营全链路方面发挥着重要作用&#xff0c;实现客户粘性的提升。 前言 客户粘性是企业成功的关键因素之一。企业需要不断通过各种手段提升客户粘性&#xff0c;保持客户忠诚度和长期合作关系。企客…...

算法知识点————两个栈实现一个队列

思路&#xff1a;当队列入队的时候&#xff0c;将元素入栈&#xff08;instack&#xff09;&#xff0c;当队列出栈的时候&#xff0c;先判断栈&#xff08;outstack&#xff09;是否为空&#xff0c;如果为空&#xff0c;则将栈&#xff08;instack&#xff09;的元素全部放入…...

并行程序设计基础——并行I/O(1)

目录 一、概述 1、按照读写定位分类 2、按照同步机制分类 3、按照参加读写操作的进程的限制分类 二、并行文件管理的基本操作 1、MPI_FILE_OPNE 2、MPI_FILE_CLOSE 3、MPI_FILE_DELETE 4、MPI_FILE_SET_SIZE 5、MPI_FILE_PREALLOCATE 6、MPI_FILE_GET_SIZE 7、MPI_…...

在JS中的设计模式的单例模式、策略模式、代理模式、原型模式浅讲

1. 单例模式&#xff08;Singleton Pattern&#xff09; 确保一个类只有一个实例&#xff0c;并提供一个全局访问点。 示例代码&#xff1a; class Singleton {constructor() {if (Singleton.instance) {return Singleton.instance;}Singleton.instance this;this.data []…...

JVM系列(十) -垃圾收集器介绍

一、摘要 在之前的几篇文章中,我们介绍了 JVM 内部布局、对象的创建过程、运行期的相关优化手段以及垃圾对象的回收算法等相关知识。 今天通过这篇文章,结合之前的知识,我们一起来了解一下 JVM 中的垃圾收集器。 二、垃圾收集器 如果说收集算法是内存回收的方法论,那么…...

项目实战 ---- 商用落地视频搜索系统(9)---UI与上层service的交互优化

目录 背景 第一次优化(UI优化) 优化前UI 优化方向与问题 代码 修改效果 第二次优化(整合优化) 优化方向与问题 代码 优化效果 第三次优化(js层优化) 优化方向与问题 代码 优化效果 第四次优化(UI逻辑再优化) 优化方向与问题 代码 优化效果 第五次优化(纯U…...

媒体服务器软件BUG说明及改进方案

媒体服务器软件BUG说明及改进方案 一、BUG描述二、问题分析三、改进方案四、实施计划五、预期效果六、总结一、BUG描述 在当前版本的媒体服务器中,存在一个关于静音媒体流处理的问题。具体表现为:当主叫连续发送静音帧到媒体服务器时,媒体服务器并未将这些静音帧转发给被叫…...

Gitlab修改已push的历史commit信息

文章目录 一、需求 二、思路 三、修改过程 四、注意 五、参考链接 一、需求 项目组结合使用JIRA和Gitlab进行项目开发。其中&#xff0c;JIRA用于管理开发任务(每个任务都存在一个JIRA_ID)&#xff0c;Gitlab用于进行代码版本管理。每次代码提交时&#xff0c;commit mes…...

[Linux入门]---进程替换

文章目录 1.进程替换原理2.进程替换函数2.1execl函数2.2execlp函数2.3execv函数2.4execvp函数2.5execle函数2.6execve函数2.7跨语言调用程序 3.总结 1.进程替换原理 一个程序替换的函数&#xff1a; #include <unistd.h> int execl(const char *path, const char *arg,…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...

从零手写Java版本的LSM Tree (一):LSM Tree 概述

&#x1f525; 推荐一个高质量的Java LSM Tree开源项目&#xff01; https://github.com/brianxiadong/java-lsm-tree java-lsm-tree 是一个从零实现的Log-Structured Merge Tree&#xff0c;专为高并发写入场景设计。 核心亮点&#xff1a; ⚡ 极致性能&#xff1a;写入速度超…...

Redis上篇--知识点总结

Redis上篇–解析 本文大部分知识整理自网上&#xff0c;在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库&#xff0c;Redis 的键值对中的 key 就是字符串对象&#xff0c;而 val…...