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

数据结构(八)二叉树、哈希查找

文章目录

  • 一、树
    • (一)概念
      • 1. 前序遍历:根左右
      • 2. 中序遍历:左根右
      • 3. 后序遍历:左右根
      • 4. 层序遍历:需要借助队列实现
    • (二)代码实现:二叉树
      • 1. 结构体定义
      • 2. 创建二叉树
        • 1. 注意点
        • 2. 代码实现
      • 3. 遍历二叉树
        • 1. 注意点
        • 2. 代码实现
      • 4. 销毁树
        • 1. 注意点
        • 2. 代码实现
  • 二、哈希Hash
    • (一)构造函数:保留除数法(质数除余法)
    • (二)处理冲突的方法
      • 1. 开放地址法
      • 2. 链地址法
    • (三)使用实例
      • 1. 功能需求
      • 2. 需求分析
      • 3. 代码实现
        • (1)结构体定义
        • (2)

一、树

(一)概念

1. 前序遍历:根左右

先遍历根节点 然后遍历左子树 最后遍历右子树
一般用于创建一棵树时,因为得先有根节点,才能给根节点左右指针分配空间

2. 中序遍历:左根右

先遍历左子树 然后遍历根节点 最后遍历右子树
对于一颗有序的二叉树,使用中序遍历,可以得到一个有序的数列

3. 后序遍历:左右根

先遍历左子树 然后遍历右子树 最后遍历根节点
一般用于销毁一棵树时,因为需要先释放左右子树,才能释放根节点

4. 层序遍历:需要借助队列实现

根节点入队列,然后出队列前,先把要出的节点的左右子树

(二)代码实现:二叉树

1. 结构体定义

typedef struct _Node{char data; //数据域struct _Node *lchild; //左子树struct _Node *rchild; //右子树
}node_t;

2. 创建二叉树

1. 注意点
  1. 创建二叉树是按照前序的顺序来创建的
  2. 判断递归是否结束的语句,需要放在申请空间之前,否则如果申请空间后再执行递归结束,会造成内存泄漏
2. 代码实现
int create_tree(node_t **root){if(NULL==root) return -1;char data;printf("请输入节点数据:");scanf("%c",&data);getchar();//吃垃圾字符if('#'==data) return 0; //递归的出口*root=(node_t *)malloc(sizeof(node_t));if(NULL==*root) return -1;(*root)->lchild=NULL;(*root)->rchild=NULL;(*root)->data=data;//左子树create_tree(&((*root)->lchild));//右子树create_tree(&((*root)->rchild));return 0;
}

3. 遍历二叉树

1. 注意点
  1. 遍历二叉树,前序、中序、后序的区别仅在于调用函数的顺序,前序即先打印根节点,再打印左节点,最后打印右节点;中序则先打印左节点,再打印根节点,最后打印右节点;后序就是先打印左节点,再打印右节点,最后打印根节点
2. 代码实现
//前序遍历
int preorder(node_t *root){if(NULL == root) return -1;printf("%c ",root->data);preorder(root->lchild);preorder(root->rchild);return 0;
}//中序遍历
int inorder(node_t *root){if(NULL == root) return -1;inorder(root->lchild);printf("%c ",root->data);inorder(root->rchild);return 0;
}//后序遍历
int postorder(node_t *root){if(NULL == root) return -1;postorder(root->lchild);postorder(root->rchild);printf("%c ",root->data);return 0;
}

4. 销毁树

1. 注意点
  1. 销毁树要按照后续顺序销毁,即先销毁左右节点,最后再释放根节点
2. 代码实现
int destory_tree(node_t **root){if(NULL == root|| NULL==*root) return -1;//先销毁左右子树destory_tree(&((*root)->lchild));destory_tree(&((*root)->lchild));//销毁根节点free(*root);*root=NULL;return 0;
}

二、哈希Hash

理想的哈希查找方法:对于给定的key值不需任何比较就可以获取记录。
在建立记录表时,确定记录的key与其存储地址的关系,这个关系就是Hash函数,H(key)
下述仅介绍一种常用的方法

(一)构造函数:保留除数法(质数除余法)

基本思想:设一个Hash表空间长度为m,取一个不大于m的最大的质数p
公式表达:H(key)=key%p

(二)处理冲突的方法

冲突:表中某地址中已存放数据,但是另一个数据经过Hash函数后得到的地址与该地址相同
选取随机度好的Hash函数可以使冲突减少,但是很难完全避免

在处理冲突的过程中,可能发生一连串的冲突现象,即可能得到一个地址序列H1、H2……Hn,Hi∈[0,m-l]。
H1是冲突时选取的下一地址,而H1中可能己有记录,又设法得到下一地址H2……直到某个Hn不发生冲突为止。这种现象称为“聚积”,它严重影响了Hash表的查找效率

1. 开放地址法

在这里插入图片描述
如下图,46%13=7,07%13=7,但是地址8已有数据,使用线性探查法,将07存到了地址9
在这里插入图片描述
但是这种方法可能会因为处理冲突占用空间而导致冲突产生,例如,如果此时再存入数据09,09%13=9,09本应该存在地址9,但是为了解决46和07的冲突,占用了地址9的位置,而导致冲突产生。还有可能发生聚积。

此外,在遍历数据查找有无某元素时,无法确定需要遍历多少地址增量才能确定没有该元素.

2. 链地址法

发生冲突时,将各冲突记录链在一起
这种方法不会发生聚积现象,且容易判断某元素是否存在
在这里插入图片描述

(三)使用实例

1. 功能需求

运用哈希思想实现学生信息录入和查找
存储学生信息,以名字首字母为关键字设计哈希函数,用链地址法解决哈希冲突

2. 需求分析

  1. 需要定义一个学生节点的结构体

3. 代码实现

(1)结构体定义

(2)

相关文章:

数据结构(八)二叉树、哈希查找

文章目录 一、树(一)概念1. 前序遍历:根左右2. 中序遍历:左根右3. 后序遍历:左右根4. 层序遍历:需要借助队列实现 (二)代码实现:二叉树1. 结构体定义2. 创建二叉树1. 注意…...

uniApp 创建Android.keystore证书IOS的证书

Android 证书 1、安装JRE环境 可从Oracle官方下载jre安装包:https://www.oracle.com/technetwork/java/javase/downloads/index.html 打开命令行(cmd),输入以下命令: //切换工作目录到f:路径 D: //将jre命令添加到…...

怎么藏族翻译中文在线翻译?更好地了解藏族文化

怎么藏族翻译中文在线翻译?着全球化的发展,语言交流的重要性日益凸显。藏族,作为中国的一个古老而神秘的民族,其语言对于很多人来说充满了神秘感。然而,在今天的数字化时代,我们有了更多的工具来打破语言壁…...

模拟集成电路(5)----单级放大器(共栅级)

模拟集成电路(5)----单级放大器(共栅级) 有一些场合需要一些小的输入电阻(电流放大器) 大信号分析 − W h e n V i n ≥ V B − V T H ∙ M 1 i s o f f , V o u t V D D − F o r L o w e r V i n I d 1 2 μ n C o x W L ( V…...

学习笔记——数据通信基础——数据通信网络(网络工程师)

网络工程师 网络工程,就是围绕着网络进行的一系列的活动,包括∶网络规划、设计、实施、调试、排错等。网络工程设计的知识领域很宽广,其中路由和交换是计算机网络的基本。 网络工程师∶是在网络工程领域,掌握专业的网络技术&…...

将本地项目上传到 gitee 仓库

1、创建 gitee 仓库 到 gitee 官网,新建仓库 配置新建仓库 完成仓库的创建 项目上传到仓库 上传项目需要安装git git官方下载地址:git下载地址 安装完成,前往本地项目所在文件夹,右击选择 Git Bash Here 刚下载完成需要配置G…...

Django学习

1.pycharm社区版创建django PyCharm社区版如何创建Django项目并运行_pycharm社区版打开django-CSDN博客 2.Django TemplateDoesNotExist: rest_framework 当我们使用djangorestframework框架时,首先下载pip install djangorestframework 参考博文Django Templat…...

说唱程序员

Yo yo yo,这里是代码的战场,程序员的秀场, 键盘敲击声,是我们的节奏响亮。 夜深人静时,我们与Bug正面刚, 调试、优化,每一行代码都得刚强。 我们不懂数理化,只是喜欢瞎搞哈&#xf…...

058.最后一个单词的长度

题意 给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。 难度 简单 示例 1: 输入:s "Hello World" 输…...

决策树模型-预测用户是否购买某母婴产品

1,场景描述 假设我们是京东的数据分析师,负责分析母婴产品的购买行为。我们想预测用户是否会购买一款新上线的母婴产品。为了进行预测,我们将利用用户的历史购买数据、浏览行为和其他特征,通过决策树模型进行分析,并提…...

工具使用-网络性能测试工具(iperf)-TCP 和 UDP 的吞吐量-包转发率参数的理解

时间戳:2024年5月26日15:18:39 iperf 和 netperf 都是最常用的网络性能测试工具,测试 TCP 和 UDP 的吞吐量。它们都以客户端和服务器通信的方式,测试一段时间内的平均吞吐量。 接下来,我们就以 iperf 为例,看一下 TC…...

什么是JS引擎

JS引擎(JavaScript引擎)是负责在浏览器或Node.js等环境中解析和执行JavaScript代码的软件组件。它是JavaScript运行时的核心,将JavaScript代码转换为机器语言,使其能够在计算机上执行。 不同的浏览器和运行环境使用不同的JS引擎。…...

前端手写文件上传;使用input实现文件拖动上传

使用input实现文件拖动上传 vue2代码&#xff1a; <template><div><div class"drop-area" dragenter"highlight" dragover"highlight" dragleave"unhighlight" drop"handleDrop"click"handleClick&quo…...

Flutter 中的 PhysicalModel 小部件:全面指南

Flutter 中的 PhysicalModel 小部件&#xff1a;全面指南 Flutter 的 PhysicalModel 小部件提供了一种简单而高效的方式来给应用添加物理效果&#xff0c;如阴影和层次感。它本质上是一个矩形的 Container&#xff0c;带有圆角边框和可选的阴影&#xff0c;能够模仿真实世界中…...

Flutter 中的 Center 小部件:全面指南

Flutter 中的 Center 小部件&#xff1a;全面指南 在Flutter的世界里&#xff0c;Center是一个简单而强大的布局小部件&#xff0c;它能够将子组件放置在父组件的中心位置。无论是水平中心、垂直中心&#xff0c;还是两者都居中&#xff0c;Center都能轻松实现。本文将详细介绍…...

windows 执行node报错 800A1391

在项目下执行node -v的时候&#xff0c;抛了这个错误&#xff0c;一开始没发现有啥问题 现在一看&#xff0c;这个报错里的node怎么是个文件... 出现这个问题&#xff0c;是因为项目下&#xff0c;有个同名的文件叫node.js&#xff0c;搞得windows一时不知道是想打开node.js文…...

无人机操作界面来了,起点就很高呀。

无人机操作界面设计需要考虑以下几个方面&#xff1a; 易用性&#xff1a;无人机操作界面应该简单直观&#xff0c;易于操作和理解。操作按钮和控键应该布局合理&#xff0c;易于触摸或点击。重要的操作功能应该易于找到和使用&#xff0c;避免用户迷失或困惑。实时反馈&#…...

Android 11 AudioPolicyService 启动流程

AudioPolicyService在init进程中启动&#xff0c;源码路径&#xff1a;frameworks/av/media/audioserver/audioserver.rc service audioserver /system/bin/audioserverclass coreuser audioserver# media gid needed for /dev/fm (radio) and for /data/misc/media (tee)grou…...

java中static关键字面试五连问

抽象&#xff08;abstract&#xff09;方法是否可同时是静态的&#xff08;static&#xff09;? 抽象方法本来将来就是要被重写的&#xff0c;而静态方法不能被重写&#xff0c;所以是错误的 是否可以从一个静态&#xff08;static&#xff09;方法内部发出对非静态方法的调…...

基于文本来推荐相似酒店

基于文本来推荐相似酒店 查看数据集基本信息 import pandas as pd import numpy as np from nltk.corpus import stopwords from sklearn.metrics.pairwise import linear_kernel from sklearn.feature_extraction.text import CountVectorizer from sklearn.feature_extrac…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

Vue3 PC端 UI组件库我更推荐Naive UI

一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用&#xff0c;前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率&#xff0c;还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库&#xff08;Naive UI、Element …...

Mac flutter环境搭建

一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...

Windows 下端口占用排查与释放全攻略

Windows 下端口占用排查与释放全攻略​ 在开发和运维过程中&#xff0c;经常会遇到端口被占用的问题&#xff08;如 8080、3306 等常用端口&#xff09;。本文将详细介绍如何通过命令行和图形化界面快速定位并释放被占用的端口&#xff0c;帮助你高效解决此类问题。​ 一、准…...

基于stm32F10x 系列微控制器的智能电子琴(附完整项目源码、详细接线及讲解视频)

注&#xff1a;文章末尾网盘链接中自取成品使用演示视频、项目源码、项目文档 所用硬件&#xff1a;STM32F103C8T6、无源蜂鸣器、44矩阵键盘、flash存储模块、OLED显示屏、RGB三色灯、面包板、杜邦线、usb转ttl串口 stm32f103c8t6 面包板 …...

大数据驱动企业决策智能化的路径与实践

&#x1f4dd;个人主页&#x1f339;&#xff1a;慌ZHANG-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、引言&#xff1a;数据驱动的企业竞争力重构 在这个瞬息万变的商业时代&#xff0c;“快者胜”的竞争逻辑愈发明显。企业如何在复杂环…...

算法刷题-回溯

今天给大家分享的还是一道关于dfs回溯的问题&#xff0c;对于这类问题大家还是要多刷和总结&#xff0c;总体难度还是偏大。 对于回溯问题有几个关键点&#xff1a; 1.首先对于这类回溯可以节点可以随机选择的问题&#xff0c;要做mian函数中循环调用dfs&#xff08;i&#x…...