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

数据结构 ——前缀树查词典的实现

news 来源：原创 2025/6/15 15:11:55

数据结构 ——前缀树查词典的实现

一、前缀树的概念

前缀树是一种多叉树结构，主要用于存储字符串。每个节点代表一个字符，路径从根节点到叶节点表示一个完整的字符串。前缀树的关键特征是共享前缀，也就是说，如果两个字符串有相同的前缀，它们会共享前缀部分的节点。
优点：由于共享前缀，前缀树能有效地节省空间，并且支持快速查找、插入、删除操作，尤其是在处理大量字符串时非常高效。
应用场景：主要用于实现高效的字符串查找、自动补全、词典查询等。

二、查词典的代码实现

在这里插入图片描述
插入key:ant过程，查找单词同插入差不多

在这里插入图片描述
插入key:donkey

下面是利用前缀树在一个给定的文件log.txt,来实现一个简单的查词典功能

//log,txt
ant:a samll insect that lives in group
butterfly:a flying insect with a long thin body
cobra:a highly dangerous snake
donkey: a animal with short legs and long ears

//利用前缀数，根据提供的文件实现一个简单的查词典功能
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define DESC_SIZE  256
#define KEY_SIZE   256
#define BUFSIZE    512
#define FNAME      "log.txt"
struct node_st
{struct node_st *ch[26];//存放26个字母char desc[DESC_SIZE];//单词的描述
};
//根据：拆分关键字和描述  donkey: a animal with short legs and long ears
int get_word(FILE *fp, char *key, char *desc)
{char buf[BUFSIZE];//用于存放读出来的一行的字符char *retp;int i,j;retp=fgets(buf,BUFSIZE,fp);//从fp文件，读取BUFSIZE个字符，存到buf中 //文件读取失败if (retp==NULL)return -1; //把关键字和描述分开  KEY_SIZE-1是预留一个尾0for(i=0;i<KEY_SIZE-1 && buf[i]!=':';i++) key[i]=buf[i];key[i]='\0';i++;for(j=0;j<DESC_SIZE-1 && buf[i]!='\0';j++,i++)desc[j]=buf[i];desc[j]='\0';return 0;  
}
struct node_st *newnode()
{struct node_st *node;int i;node=malloc(sizeof(*node));//申请的是 struct node_st的内存,指针内存是struct node_st *if(node==NULL)return NULL;//初始化一个指针数组ch和描述字符串descnode->desc[0]='\0';//字符串是以空字符结尾的字符数组,将第一个字符设置为 '\0' 实际创建了一个空字符串for(i=0;i<26;i++)node->ch[i]=NULL;return node;
}
int insert(struct node_st **root, char *key, char *desc)
{if(*root==NULL){*root=newnode();if(*root==NULL)return -1;}if(*key=='\0'){strcpy((*root)->desc,desc);return 0;}/*注意(*root)->ch+*key-'a'和root->ch[*key-'a']的区别struct node_st *ch[26]定义一个指针数组，ch指向的是一个结构体数组，数组的每一个元素存的是指针值 ch[1]=*(ch+1) 表示的是这个数组首地址偏移一个位置的解引用 *&，访问的是这个偏移一个位置后的数据，且该数据存的是一个指针，为一级指针ch+1 则是一个二级指针，表示指向的是这个指针数组首地址偏移一个位置后的地址*/return insert((*root)->ch+*key-'a',key+1,desc);//}
char *find(struct node_st *root, char *key)
{if(root==NULL)return NULL;if(*key=='\0')return root->desc;return find(root->ch[*key-'a'],key+1);}
int main() 
{FILE *fp;struct node_st *tree=NULL;char desc[DESC_SIZE]={'\0'}, key[KEY_SIZE]={'\0'};int ret;char *datap;fp=fopen(FNAME,"r");if(fp==NULL){fprintf(stderr,"fopen():error\n");return -1;}while (1){//拆单词ret=get_word(fp,key,desc);if(ret==-1)break;//测试key和desc是否分开// puts(key);// puts(desc);insert(&tree,key,desc);}// datap=find(tree,"donkey");datap=find(tree,"hello");if(datap==NULL)printf("Can not found!\n");elseputs(datap);fclose(fp);return 0;
}

关于指针数组的一点理解
在这里插入图片描述

数据结构 ——前缀树查词典的实现

数据结构 ——前缀树查词典的实现一、前缀树的概念前缀树是一种多叉树结构，主要用于存储字符串。每个节点代表一个字符，路径从根节点到叶节点表示一个完整的字符串。前缀树的关键特征是共享前缀，也就是说，如果两个字符串有相…...

编程日记 2025/6/4 15:12:51

边缘智能创新应用大赛获奖作品系列一：智能边缘计算✖软硬件一体化，开启全场景效能革命新征程

边缘智能技术快速迭代，并与行业深度融合。它正重塑产业格局，催生新产品、新体验，带动终端需求增长。为促进边缘智能技术的进步与发展，拓展开发者的思路与能力，挖掘边缘智能应用的创新与潜能，高通技术公司联…...

编程日记 2025/5/31 15:09:47

视频教程:修改ubuntu apt 源和apt 使用方法_哔哩哔哩_bilibili 1 修改apt源 1.1 获取阿里云ubuntu apt 源 https://developer.aliyun.com/mirror/ubuntu?spma2c6h.13651102.0.0.3e221b11mqqLBC 1.2 修改apt 源 vim /etc/apt/sources.list deb https://mirrors.aliyun.com/ub…...

编程日记 2025/6/3 16:48:04

Kafka 磁道寻址过程详解

前言 Apache Kafka 是一款高吞吐、分布式的消息流平台，广泛应用于实时数据处理和事件驱动系统。在 Kafka 中，消息是存储在磁盘上的，这种高效的数据读写性能得益于 Kafka 独特的磁盘存储架构和寻址机制。本文将从 Kafka 的存储结构、磁道寻址…...

编程日记 2025/6/1 22:07:59

GEE+本地XGboot分类

GEE本地XGboot分类我想做提取耕地提取，想到了一篇董金玮老师的一篇论文，这个论文是先提取的耕地，再做作物分类，耕地的提取代码是开源的。但这个代码直接在云端上进行分类，GEE会爆内存，因此我准备把数据下…...

编程日记 2025/6/4 15:59:26

安防监控Liveweb视频汇聚融合平台助力执法记录仪高效使用

Liveweb平台可接入的设备除了常见的智能分析网关与摄像头以外 ，还可通过GB28181协议接入执法记录仪，实现对执法过程的全程监控与录像，并对执法轨迹与路径进行调阅回看。那么，如何做到执法记录仪高效使用呢？ 由于执法记…...

编程日记 2025/6/1 17:11:14

酷盾安全：Edge SCDN边缘安全内容分发网络

在当今数字化迅猛发展的时代，互联网内容分发的高效与安全成为了企业不可忽视的重要课题。为了满足这一需求，酷盾安全推出了创新的Edge Secure Content Delivery Network（Edge Scdn）解决方案，它不仅融合了分布式DDoS防护…...

编程日记 2025/6/2 7:03:28

决策引擎技术

决策引擎（Decision Engine）是一种用于自动化决策过程的软件系统。它通常用于处理复杂的业务逻辑，根据输入的数据和预定义的规则或模型来做出决策。决策引擎在许多领域都有广泛的应用，如金融、保险、医疗、供应链管理等。在Java中…...

编程日记 2025/5/30 13:05:43

Servlet学习中遇到的一些问题及解决

错误：JavaWeb-错误：类xxx不是Servlet 解决：可能是Tomcat版本不匹配导致，更换Tomcat版本解决问题错误：在自定义的Servlet类中不能添加 WebServlet 注解解决：可能是WebServlet版本不匹配，更换…...

编程日记 2025/6/2 7:39:57

oracle开窗函数笔记、over()笔记

文章目录开窗函数、组函数、分析函数概念聚合函数和分析函数的区别partition by后面也可以跟多个字段开窗函数一定要加聚合函数、或分析函数吗，否则会报错lag()和lead()的用法lag和lead实战开窗函数可以和其他函数一起使用吗? TODO开窗函数中的count(1)是什么意…...

编程日记 2025/5/31 13:32:21

深度学习面试相关-2024.12.15记录

深度学习面试相关- 2024.12.15记录目录深度学习面试相关- 2024.12.15记录整体常问问题1数学基础1.1 概率统计1.2 线代 2机器学习算法2.1 深度学习算法2.2 机器学习算法整体常问问题 https://www.nowcoder.com/discuss/353154899112304640 1数学基础 1.1 概率统计 htt…...

编程日记 2025/6/2 1:38:48

CSS|07 标准文档流

标准文档流一、什么是标准文档流在制作的 HTML 网页和 PS 画图软件画图时有本质上面的区别: HTML 网页在制作的时候都得遵循一个“流的规则:从左至右、从上至下。使用 Ps 软件画图时可以在任意地方画图。 <!DOCTYPE html> <html lang"en"> <hea…...

编程日记 2025/6/1 19:47:44

1 JVM JDK JRE之间的区别以及使用字节码的好处

JDK jdk是编译java源文件成class文件的，我们使用javac命令把java源文件编译成class文件。我们在java安装的目录下找到bin文件夹，如下图所示: 遵循着编译原理，把java源文件编译成JVM可识别的机器码。其中还包括jar打包工具等。主要是针对…...

编程日记 2025/6/2 1:25:54

ubuntu安装8812au驱动却无法加载网卡的问题

驱动GIT地址 https://github.com/aircrack-ng/rtl8812au按照里面提示安装驱动输入 sudo dkms status查看驱动是否安装成功接入网卡，看看ifconfig能否输出网卡如果不行使用sudo dmesg -w插拔网卡看看输出如果输出为: load module with unavailable key is …...

编程日记 2025/5/31 2:07:44

Eureka学习笔记-服务端

Eureka学习笔记服务端模块设计 Resources ：这部分对外暴露了一系列的 Restful 接口。Eureka Client 的注册、心跳、获取服务列表等操作都需要调用这些接口。另外，其他的 Server 在同步 Registry 时也需要调用这些接口。Controller ：这里提…...

编程日记 2025/6/4 6:44:04

LangChain

文章目录一、LangChain 是什么？二、核心概念1. LLM Wrappers2. Prompt Templates3. Indexes4. Chains5. Agents 三、工作流程四、应用场景示例一：简单的语言模型调用示例二：使用Prompt Templates（提示模板）示例三&…...

编程日记 2025/6/1 5:12:00

搭建分布式Hive集群

title: 搭建分布式Hive集群 date: 2024-11-29 23:39:00 categories: - 服务器 tags: - Hive - 大数据搭建分布式Hive集群本次实验环境：Centos 7-2009、Hadoop-3.1.4、JDK 8、Zookeeper-3.6.3、Mysql-5.7.38、Hive-3.1.2 功能规划方案一（本地运行模…...

编程日记 2025/5/30 17:09:32

Scala的惰性求值：深入理解与实践

在编程中，我们经常需要处理那些计算成本高昂或者可能永远不会用到的值。在这种情况下，惰性求值（Lazy Evaluation）是一种非常有用的策略。它允许我们推迟计算，直到这些值真正需要被使用。Scala，作为一种多功…...

编程日记 2025/6/2 3:03:53

游戏引擎学习第54天

仓库: https://gitee.com/mrxiao_com/2d_game 回顾我们现在正专注于在游戏世界中放置小实体来代表所有的墙。这些实体围绕着世界的每个边缘。我们有活跃的实体，这些实体位于玩家的视野中，频繁更新，而那些离玩家较远的实体则以较低的频率运…...

编程日记 2025/5/29 11:40:34

QT绘制同心扇形

void ChartForm::paintEvent(QPaintEvent *) {QPainter painter(this);painter.setRenderHint(QPainter::Antialiasing);// 设置抗锯齿painter.save();// 设置无边框（不需要设置QPen，因为默认是不绘制边框的）QPen pen(Qt::NoPen);// QPen pen…...

编程日记 2025/6/1 21:24:17

梳理你的思路(从OOP到架构设计)_浅尝架构师的滋味02

目录 1、 App开发者的职责：买主提供需求知识，App开发者帮他写代码撰写的代码撰写代码，将装配(扩充)到 2、从生活中体会基於軟硬整合觀點“两种知识” 编辑 1、 App开发者的职责：买主提供需求知识，App开发者帮…...

编程日记 2025/6/1 21:12:32

使用VLC 搭建 RTSP 服务器

第一步：打开 VLC ，媒体--->流第二步：添加一个选择本地的文件，然后点击选择"串流" 第三步：确认你选择的文件，然后点击下一个第四步： 配置选择的视频文件使用哪种流输出&#xf…...

编程日记 2025/6/3 7:16:25

什么是大型语言模型

大型语言模型简介大型语言模型 (LLM) 是一种深度学习算法，可以使用非常大的数据集识别、总结、翻译、预测和生成内容。 NVIDIA 开发者计划想要了解有关 NIM 的更多信息？加入 NVIDIA 开发者计划，即可免费访问任何基础设施云、数据中心或个…...

编程日记 2025/6/2 3:32:31

游卡，科锐国际，蓝禾，汤臣倍健，顺丰，途游游戏25秋招内推

游卡，科锐国际，蓝禾，汤臣倍健，顺丰，途游游戏25秋招内推 ①科锐国际25届秋招补录人力资源类岗位，补录城市：上海，苏州，锦州；全日制公办本科及以上 25届应届毕业…...

编程日记 2025/6/1 20:20:18

Linux -- 线程控制相关的函数

目录 pthread_create -- 创建线程参数返回值代码 -- 不传 args： 编译时带 -lpthread 运行结果为什么输出混杂？ 如何证明两个线程属于同一个进程？ 如何证明是两个执行流？ 什么是LWP？ 代码 -- 传 args&a…...

编程日记 2025/6/2 5:33:25

【Linux】Linux内核启动流程分析

Linux 内核的启动流程要比 uboot 复杂的多，涉及到的内容也更多，因此我们大致的了解一下Linux 内核的启动流程即可。 Linux启动流程启动过程可以分为以下几个主要步骤： 1.引导加载程序（Bootloader）阶段 Linux 内核的…...

编程日记 2025/6/1 20:27:57

【uniapp蓝牙】基于native.js链接ble和非ble蓝牙

【uniapp蓝牙】基于native.js链接ble和非ble蓝牙 uniapp不是仅支持低功耗蓝牙（基础蓝牙通讯不支持），有些可能需要基础蓝牙。我现在同步我的手机蓝牙列表低功耗，基础蓝牙都支持 /*** author wzj* 通用蓝牙模块封装* 搜索 ble 和非…...

编程日记 2025/6/3 15:37:31

OpenGL ES 03 加载3张图片并做混合处理

OpenGL ES 02 加载3张图片并做混合处理什么是纹理单元纹理单元的作用使用纹理单元的步骤详细解释加载图片并绑定到到GPU纹理单元采样器的设置1.设置采样器变量的纹理单元编号，目的是为了告诉纹理采样器，从哪个纹理单元采集数据2.如果你没有显式地设置采…...

编程日记 2025/6/4 10:53:08

c++数据结构算法复习基础--13--基数算法

基数排序 - 桶排序时间复杂度 O(n*d) – d为数据的长度每次比较一位（个位、十位。。。），所以取值范围就为0-9。根据该特点，设计桶的概念 – 0号桶、1号桶… 1、思想 1）找出最长的数字，确定要处理的…...

编程日记 2025/6/2 17:17:29

基于YOLOv5的行人与帽子检测与识别说明文档

基于YOLOv5的行人与帽子检测与识别说明文档 1. 任务的内容和目标 1.1 任务目标在计算机视觉领域，头盔检测至关重要，主要用于判定图像或视频里的人是否佩戴头盔。于工业生产、建筑工地、交通出行（如摩托车与自行车骑行）等高危场…...

编程日记 2025/6/1 20:54:01

Mybatis——（2）

2.2 Mybatis 工具类（了解） 为了简化MyBatis的开发，可将MyBatis进一步封装。 import org.apache.ibatis.io.Resources; import org.apache.ibatis.session.SqlSession; import org.apache.ibatis.session.SqlSessionFactory; import org.apa…...

编程日记 2025/6/3 20:20:12

QT笔记- QSystemTrayIcon系统托盘功能完整示例

1. 创建托盘对象 // 创建托盘图标QSystemTrayIcon * trayIcon new QSystemTrayIcon(this);QIcon icon("://icon/test.png");trayIcon->setIcon(icon);trayIcon->show();trayIcon->connect(trayIcon, &QSystemTrayIcon::activated,this, &MainWindo…...

编程日记 2025/6/3 15:01:18

ElasticSearch08-分析器详解

零、文章目录 ElasticSearch08-分析器详解 1、分析器原理 Elasticsearch的分词器（Analyzer）是全文搜索的核心组件，它负责将文本转换为一系列单词（term/token）的过程，也叫分词。 （1&#xff…...

编程日记 2025/6/2 11:02:16

指针的深入讲解

本章重点： 字符指针数组指针指针数组数组传参和指针传参函数指针函数指针数组指向函数指针数组的指针回调函数我们在指针的初阶的时候主要讲了： 1.指针就是变量，用来存放地址，地址唯一标识一块内存空间 2.指针的大小是固定4个…...

编程日记 2025/6/1 22:40:43

王佩丰24节Excel学习笔记——第十二讲：match + index

【以 Excel2010 系列学习，用 Office LTSC 专业增强版 2021 实践】【本章小技巧】 vlookup与match，index 相结合使用match,index 结合，快速取得引用的值扩展功能，使用match/index函数，结合照相机工具获取照片一、回顾…...

编程日记 2025/6/3 5:38:50

概率论得学习和整理28：用EXCEL画折线图，X轴数据也被当成曲线的解决办法

目录 1 折线图和散点图，对数据的处理差别 1.1 EXCEL画图的一些默认设置 1.2 多于2列的数据，也是如此 2 如果我们非要以第1列数据为X轴，做一个折线图呢？也能 2.1 首先，把第1列，想当成X轴的数据&#xf…...

编程日记 2025/6/3 1:05:21

387. 字符串中的第一个唯一字符

1，题目给定一个字符串 s ，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1 。 2，代码 class Solution { public:int firstUniqChar(string s) {//记数排序int coutArr[26] {0};//统计字符出现…...

编程日记 2025/6/1 22:52:25

Oracle RAC最佳实践-优化私网连接

在 Oracle RAC 环境中，私网（Interconnect） 是节点之间通信和数据传输的关键部分。一直有个误解，认为私网（心跳网）只要能通随便什么交换机都可以,甚至有直连的，实际上私网的性能至关重要&#xf…...

编程日记 2025/6/4 7:37:31

[bug] StarRocks borker load意向之外的bug

意向之外，又清理之中背景： StarRocks各方面碾压相同类型的数据库，最近我们要从生成HIVE导历史数据（ORC格式）到StarRocks，前期小测一下，在测试是没问题，上生产先导2个月的数据&…...

编程日记 2025/6/1 23:12:25

游戏AI实现-寻路算法（Dijkstra）

戴克斯特拉算法（英语：Dijkstras algorithm），又称迪杰斯特拉算法、Dijkstra算法，是由荷兰计算机科学家艾兹赫尔戴克斯特拉在1956年发现的算法。算法过程： 1.首先设置开始节点的成本值为0，并将…...

编程日记 2025/6/1 18:23:54

9 OOM和JVM退出。OOM后JVM一定会退出吗？

首先我们把两个概念讲清楚 OOM是线程在申请堆内存，发现堆内存空间不足时候抛出的异常。 JVM退出的条件如下： java虚拟机在没有守护线程的时候会退出。守护线程是启动JVM的线程，服务于用户线程。我们简单说下守护线程的功能: 1.日志的记录…...

编程日记 2025/6/4 14:42:31

Linux 端口操作

安装netstat yum -y install net-tools 检测端口占用 netstat -npl | grep "端口" 安装lsof lsof yum -y install lsof 检测端口占用 lsof -i :端口号安装nc yum -y install nc 查看对方端口是否开放 nc -vz 对方ip 对方端口安装telnet telnet yum -y in…...

编程日记 2025/6/2 10:30:13

【USB-HID】“自动化键盘“ - 模拟键盘输入

目录【USB-HID】"自动化键盘" - 模拟键盘输入1. 前言2. 模拟键盘2.1 STM32CubeMX 配置2.2 修改代码配置2.3 发送按键信息 3. 接收主机Setup数据3.1 获取PC下发的数据 4. 总结【USB-HID】“自动化键盘” - 模拟键盘输入 1. 前言对于模拟键盘的实现，网…...

编程日记 2025/6/4 12:19:35

基于Spring Boot+Vue 的高校运动会管理系统

目录 1 绪论1.1研究背景1.2 研究意义1.3 相关开发技术简介1.3.1 Vue.js1.3.2 Spring Boot1.3.3 MySQL 2 系统分析2.1 需求分析2.1.1 功能需求2.1.2 非功能需求 2.2 系统可行性分析2.2.1 经济可行性2.2.2 技术可行性2.2.3 操作可行性 3 系统概要设计系统功能描述业务流程分析 4 …...

编程日记 2025/6/4 1:52:58

Linux应用程序中终止进程的几种方法

目录 1、正常退出进程的方法 1.1、exit(int status) 函数 1.2、_exit(int status) 函数 1.3、_Exit(int status) 函数 2、异常退出进程的方法 3、何时使用这些方法？ 在 Linux 应用程序中，终止进程的方式有多种，通常取决于进程是否需要进…...

编程日记 2025/6/1 10:33:14

电脑文档损坏：原因剖析和修复方法

在使用电脑的过程中，许多用户可能会遇到文档突然提示损坏、无法打开的情况。这种情况的发生往往让人感到困惑，特别是当并未进行任何明显错误操作时。以下是一些常见的原因以及应对方法。一、文档损坏的常见原因 1、非人为的异常操作： 在编…...

编程日记 2025/6/4 1:52:37

了解ARM的千兆以太网——RK3588

1. 简介本文并不重点讲解调试内容，重点了解以太网在ARM设计中的框架以及在设备树以及驱动的一个整体框架。了解作为一个驱动开发人员当拿到一款未开发过的ARM板卡应该怎么去把网卡配置使用起来。 2. 基础知识介绍在嵌入式ARM中实现以太网的解决方案通常有以下两种…...

编程日记 2025/6/3 17:03:31

【Nginx-4】Nginx负载均衡策略详解

在现代Web应用中，随着用户访问量的增加，单台服务器往往难以承受巨大的流量压力。为了解决这一问题，负载均衡技术应运而生。Nginx作为一款高性能的Web服务器和反向代理服务器，提供了多种负载均衡策略，能够有效地将请求分…...

编程日记 2025/6/2 11:01:53

低级计算机网络知识总结

1 应用层 1.1 HTTP(TCP) 浏览器访问WWW服务器过程：首先进行域名解析，然后通过TCP向服务器发送连接请求 HTTP本身是无连接，无状态的。无状态特性使服务器能够支持大量的并发HTTP请求。实际应用中，通常使用Cookie加数据库跟踪用户…...

编程日记 2025/6/2 11:01:49

linux sysrq的使用举例

在menuconfig中选择m和 *的区别： *: 模块驱动编译到内核中，启动时自动加载 M:标识作为内核模块编译空格:表示该功能不编译到内核中，即新的内核将不支持该功能。 m：模块会被编译，但是不会被编译到内核中，只…...

编程日记 2025/6/1 5:02:47

数据结构 ——前缀树查词典的实现

相关文章：