数据结构(C语言版)-6.查找

news/2024/12/22 14:32:02/

1. 查找的基本概念

在这里插入图片描述

2. 静态查找

2.1 顺序查找

typedef int KeyType;
typedef int InfoType;
typedef struct
{KeyType key;InfoType otherdata;
}SeqList; // 顺序表类型
// 顺序查找
int SeqSearch(SeqList R[], int n, int k)
{int i = n;R[0].key = k;  // R[0].key为查找不成功的监视哨while (R[i].key != k)i--;return i; // 查找成功返回所找元素的索引,否则返回0;
}

2.2 有序表的查找

二分查找

int BinarySearch(SeqList R[], int n, int k)
{int left = 0, right = n - 1;int mid = 0;while (left <= right){mid = (left + right) / 2;if (R[mid].key > k)right = mid - 1;else if (R[mid].key < k)left = mid + 1;elsereturn mid;}return 0;// 没有找到
}

分块查找(索引顺序查找)

在这里插入图片描述

3. 树表形式的动态查找表

在这里插入图片描述

3.1 二叉排序树

在这里插入图片描述

二叉排序树的查找操作

// 二叉排序树的查找操作
BSTree* BSTSearch(BSTree* t, int k)
{while (t != NULL){if (t->key > k)t = t->lchild;else if (t->key < k)t = t->rchild;elsereturn t;}return NULL;
}

二叉排序树的插入操作和二叉树排序树的构造

  • 愚蠢的bug,直接拿着main函数传入的指针遍历二叉排序树,导致每次插入节点时都会丢失二叉排序树的根
void BSTCreate(BSTree** t, int k)
{BSTree* pre = NULL;while ((*t) != NULL){if ((*t)->key > k) {pre = *t;*t = (*t)->lchild;}else if ((*t)->key < k) {printf("______________,右子树\n");pre = *t;*t = (*t)->rchild;}else  // 所查节点已经存在break;} //当所查节点不存在时if (*t == NULL){BSTree* tmp = (BSTree*)malloc(sizeof(BSTree));tmp->lchild = NULL;tmp->rchild = NULL;tmp->key = k;if (pre != NULL) {if (pre->key > k) {  // 应该插入pre的左孩子pre->lchild = tmp;}else { // 应该插入pre的右孩子printf("应该插入pre的右孩子\n");pre->rchild = tmp;}}else { // 二叉排序树还未建立printf("建立二叉排序树\n");*t = tmp;}}}
  • 正确的方式
void BSTCreate(BSTree** t, int k)
{BSTree* pre = NULL,*current = *t;while (current != NULL){if (current->key > k) {pre = current;current = current->lchild;}else if (current->key < k) {/*	printf("______________,右子树\n");*/pre = current;current = current->rchild;}else  // 所查节点已经存在return;} BSTree* tmp = (BSTree*)malloc(sizeof(BSTree));tmp->lchild = NULL;tmp->rchild = NULL;tmp->key = k;if (pre != NULL) {if (pre->key > k) {  // 应该插入pre的左孩子pre->lchild = tmp;}else { // 应该插入pre的右孩子//printf("应该插入pre的右孩子\n");pre->rchild = tmp;}}// 二叉排序树还未建立else { printf("建立二叉排序树\n");*t = tmp;}}

在这里插入图片描述
在这里插入图片描述

删除二叉排序树中的节点

在这里插入图片描述
在这里插入图片描述

void BSTDeleteLeafChild(BSTree* pre, BSTree* current)
{if (pre->lchild == current) // 待删除节点为pre的左孩子{pre->lchild = NULL;}else if (pre->rchild == current) {pre->rchild = NULL;}free(current);current = NULL;
}
void BSTDeleteRightChild(BSTree* pre, BSTree* current)
{// 待删除节点current只有右孩子,直接将该有孩子替换到待删除节点位置即可if (pre->lchild == current) // 待删除节点为pre的左孩子{pre->lchild = current->rchild;free(current);current = NULL;}else if (pre->rchild == current) {pre->rchild = current->rchild;free(current);current = NULL;}else {printf("BSTDeleteRightChild:pre和current没有父子关系!!!\n");}}
void BSTDeleteLeftChild(BSTree* pre, BSTree* current)
{// 待删除节点current只有左孩子,直接将该左孩子替换到待删除节点位置即可if (pre->lchild == current) // 待删除节点为pre的左孩子{pre->lchild = current->lchild;free(current);current = NULL;}else if (pre->rchild == current) {pre->rchild = current->lchild;free(current);current = NULL;}else {printf("BSTDeleteRightChild:pre和current没有父子关系!!!\n");}
}
// 在二叉排序树种删除某个节点
void BSTDelete(BSTree** t, int k)
{/*会出现四种情况1. 待删除的节点为叶子2. 待删除的节点只有左孩子3. 待删除节点只有右孩子4. 待删除节点左右孩子都有*/BSTree* pre = NULL, * current = *t;while (current != NULL){if (current->key > k) {pre = current;current = current->lchild;}else if (current->key < k) {pre = current;current = current->rchild;}else  // 节点找到break;}if (current == NULL){printf("该节点没有找到\n");return;}//1. 待删除的节点为叶子if (current->lchild == NULL && current->rchild == NULL){BSTDeleteLeafChild(pre, current);}//2. 待删除的节点只有左孩子else if (current->lchild != NULL && current->rchild == NULL){BSTDeleteLeftChild(pre, current);}//3. 待删除节点只有右孩子else if (current->lchild == NULL && current->rchild != NULL){BSTDeleteRightChild(pre,current);}//4. 待删除节点左右孩子都有else  {// 1. 首先找到以待删除节点为根的最左节点BSTree* t1 = current,*t2 = current;while (t2->lchild != NULL){t1 = t2;t2 = t2->lchild;}current->key = t2->key; 2. 删除最左节点if(t2->rchild!=NULL)BSTDeleteRightChild(t1, t2);else {t1->lchild = NULL;free(t2);t2 = NULL;}}
}

3.2 平衡二叉树(AVL)

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

红黑树

红黑树

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3.3 B树和B+树

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

B树

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

B树的插入

在这里插入图片描述
在这里插入图片描述

  • 例子
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

在这里插入图片描述

  • 例子
    在这里插入图片描述
  • 插入15
    在这里插入图片描述
  • 插入35
    在这里插入图片描述
  • 插入95
    在这里插入图片描述
B树的删除

在这里插入图片描述

在这里插入图片描述在这里插入图片描述

  • 例子
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

  • 删除92
    在这里插入图片描述
    在这里插入图片描述

  • 删除80

在这里插入图片描述

在这里插入图片描述

    • 删除70
      在这里插入图片描述在这里插入图片描述

在这里插入图片描述

B+树

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

两者的区别

区别

4. 哈希

4.1 哈希表与哈希方法

在这里插入图片描述

4.2 哈希函数

直接定址法

在这里插入图片描述

除留余数法

在这里插入图片描述

数字分析法

在这里插入图片描述

平方取中法

在这里插入图片描述

折叠法

在这里插入图片描述

4.3 处理冲突的方法

在这里插入图片描述

在这里插入图片描述

闭散列表

开放地址法

在这里插入图片描述

再散列法

在这里插入图片描述

开散列表

在这里插入图片描述

4.4 哈希表的查找

练习题


http://www.ppmy.cn/news/1557209.html

相关文章

【Java并发】创建和使用线程常用方法总结

目录 什么是线程 线程和进程、协程&#xff08;虚拟线程&#xff09;的区别 线程和进程的区别 线程和协程的区别 线程的六种状态 1.NEW 2.RUNNABLE 3.BLOCKED 4.WAITING 5.TIME_WAITING 6.TERMINATED 创建线程 方法一&#xff1a;通过继承Thread类 方法二&#xf…

sql server msdb数据库备份恢复

备份 BACKUP DATABASE [msdb] TO DISK ND:\liyuanshuai\test\sqlserver_bakfile\msdb20241219.bak WITH NOFORMAT, NOINIT, NAME Nlys-完整 数据库 备份, SKIP, NOREWIND, NOUNLOAD, COMPRESSION, STATS 10 GO然后删除2个测试的job&#xff0c;停止 SQL Server 代理…

第19天:信息收集-Web应用源码获取闭源备份开发泄漏WebPack打包资源搜索ICO定位

#知识点 1、信息收集-Web应用-源码获取-已知指纹&未知指纹 2、信息收集-Web应用-源码获取-泄漏问题&发现指纹 一、参考文章&#xff1a; https://www.secpulse.com/archives/124398.html https://mp.weixin.qq.com/s/QgLDdaefXlZtvlSiFQShZw 二、源码泄漏原因&#xff…

第十四届蓝桥杯Scratch国赛真题—转动的车轮

转动的车轮 编程实现&#xff1a; 转动的车轮&#xff08;车轮使用画笔绘制&#xff0c;画面中不能出现其他角色&#xff0c;否则0分&#xff09;。 注&#xff1a;角色、背景非源素材。 具体要求&#xff1a; 1). 点击绿旗&#xff0c;背景如图所示&#xff1b; 2). 等待1…

练习题 最小栈

最小栈 最小栈 class MinStack {private Stack<Integer> stack;private Stack<Integer> minstack;public MinStack() {stacknew Stack<>();minstacknew Stack<>();}public void push(int val) {stack.push(val);if(minstack.empty()){minstack.push(…

【C++11】可变模板参数

目录 可变模板的定义方式 参数包的展开方式 递归的方式展开参数包 STL中的emplace相关接口函数 STL容器中emplace相关插入接口函数 ​编辑 模拟实现&#xff1a;emplace接口 C11的新特性可变参数模板能够让您创建可以接受可变参数的函数模板和类模板&#xff0c;相比 C9…

Odoo:免费开源ERP的AI技术赋能出海企业电子商务应用介绍

概述 伴随电子商务的持续演进&#xff0c;客户对于便利性、速度以及个性化服务的期许急剧攀升。企业务必要探寻创新之途径&#xff0c;以强化自身运营&#xff0c;并优化购物体验。达成此目标的最为行之有效的方式之一&#xff0c;便是将 AI 呼叫助手融入您的电子商务平台。我们…

Debian环境安装Docker Engine

Debian环境安装Docker Engine 卸载旧版本使用APT工具安装Docker设置存储库安装Docker设置权限 docker compose命令卸载Docker 卸载旧版本 要卸载的非官方软件包是&#xff1a; docker.iodocker-composedocker-docpodman-docker 此外&#xff0c;Docker Engine 依赖 containe…