《数据结构（C语言版）第二版》第七章-查找（7.3.2-7.4）

2024-09-01 09:20
文章标签 数据结构 查找 第二 语言版 第七章 7.4 7.3

本文主要是介绍《数据结构（C语言版）第二版》第七章-查找（7.3.2-7.4），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【B-树、B+树：适用于 文件很大且存放于计算机外存的查找】

7.3.3 B-树（属于动态查找树，适用于动态查找表）

▲课本算法实现/▲09 查找/08 B-Tree/B-Tree.c —— kangjianwei

【仅包括 查找、插入、分裂、创建、中序遍历打印，不包括删除】

#include <stdio.h>
#include <stdlib.h>
#include <math.h>#define m  3
#define TRUE 1
#define FALSE 0typedef int KeyType;
typedef char Record;  //假设位置存储类型是char型的typedef struct BTNode
{int keynum;struct BTNode* parent;KeyType key[m + 1];struct BTNode* ptr[m + 2];Record* recptr[m + 1];
}BTNode, * BTree;typedef struct
{BTNode* pt;int i;int tag;
}Result;void CreateBTree(BTree& T);
int InsertBTree(BTree& T, KeyType K, BTree q, int i);
void  split(BTree& q, int s, BTree& ap);
void NewRoot(BTree& T, int x, BTree& ap);
void Insert(BTree& q, int i, KeyType x, BTree ap);
Result SearchBTree(BTree T, KeyType key);
int Search(BTree T, KeyType key);
void PrintBTree(BTree T);int main()
{BTree T = NULL;CreateBTree(T);printf("\n该B-树的中序序列为：");PrintBTree(T);return 0;
}//B-树的创建（通过B-树的插入实现）
void CreateBTree(BTree& T)
{T = NULL;Result r = { NULL,0,0 };int j = 0;int N = 0;KeyType KEY = 0;printf("请输入关键字总个数：");scanf_s(" %d", &N);for (j = 1; j <= N; j++){printf("请输入第%d个关键字：", j);scanf_s(" %d", &KEY);r = SearchBTree(T, KEY); //在B-树整棵树上查找key是否存在if (r.tag == 0){InsertBTree(T, KEY, r.pt, r.i);}else{printf("该关键字已存在，无法插入，请重新输入。\n");j--;}}
}//算法7.9 B-树的插入【BTree q, int i 这两个参数来自于SearchBTree函数r.tag为0时的r.pt和r.i】
int InsertBTree(BTree& T, KeyType K, BTree q, int i)
{KeyType x = K;BTree ap = NULL;bool finished = FALSE;int s = 0;while (q && !finished){Insert(q, i, x, ap);if (q->keynum < m){finished = TRUE;}else  //if(q->keynum == m){s = (int)ceil((double)m / 2);//C 标准库 <math.h>函数 double ceil(double x) 返回大于或等于 x 的最小的整数值。//B树结点中关键字个数必须>=ceil(m/2)-1split(q, s, ap);x = q->key[s];q = q->parent;if (q){i = Search(q, x);}}}if (!finished)  //q的初始值为空，即整棵树T是空树{NewRoot(T,x,ap);  //书上是NewRoot(T,q,x,ap)，但q为NULL，在NewRoot函数中无用}return 1;
}void  split(BTree& q, int s, BTree& ap)
{int i = 0;ap = (BTree)malloc(sizeof(BTNode));//将q->key[s+1,..,m]保存到ap->key[1,..,m-s]中for (i = 1; i <= m-s; i++){ap->key[i] = q->key[s+i];q->key[s + i] = 0;}//将q->ptr[s,..,m]保存到ap->ptr[0,..,m-s]中for (i= 0; i <= m-s; i++){ap->ptr[i] = q->ptr[s+i];if (ap->ptr[i]){ap->ptr[i]->parent = ap;}q->ptr[s + i] = NULL;}ap->keynum = m - s;q->keynum = s-1;ap->parent = q->parent;
}//生成含信息（T, x, ap）的新的根结点*T，原T和ap为子树指针
void NewRoot(BTree& T, int x, BTree& ap)
{BTree newT = (BTree)malloc(sizeof(BTNode));newT->key[1] = x;newT->ptr[0] = T;  //必须等于T，而不能等于q，q指向NULLnewT->ptr[1] = ap;newT->keynum = 1;newT->parent = NULL;//第一次创建节点时，即树的根结点，该结点/树中只有一个关键字，且该关键字的左右子树都是空的，还无法指定其父节点为其本身。if (newT->ptr[0]){newT->ptr[0]->parent = newT;}if (newT->ptr[1]){newT->ptr[1]->parent = newT;}T = newT;
}//将x和ap分别插入到q->key[i + l]和q->ptr[i+1]
void Insert(BTree &q, int i, KeyType x, BTree ap)
{int a = 0;int b = 0;//将q->key中K(i+1)个到K(keynum)整体往后移动一个单位for (a = q->keynum + 1; a >= i + 2; a--){q->key[a] = q->key[a - 1];}//将q->ptr中的P(i+1)到第P(keynum)整体往后移动一个单位for (b = q->keynum + 1; b >= i + 2; b--){q->ptr[b] = q->ptr[b - 1];}q->key[i + 1] = x;q->ptr[i + 1] = ap;q->keynum++;
}//算法7.8 B-树的查找
//在磁盘上（外存）进行的：在B-树整棵树上查找结点
Result SearchBTree(BTree T, KeyType key)
{BTree p = T;BTree q = NULL;bool found = FALSE;int i = 0;Result r = { NULL,0,0 };while (p && !found){i = Search(p, key);/* 在内存中的Search函数中找到p中目标关键字的位置i之后，在外存磁盘上是不能将p->key[i]直接拿来使用的。在外存上，要先从Record指针类型的一维数组中，读取到该BTNode结点指针p中存储第i个关键字Ki的物理（实际）存放位置recptr[i]，也就是说是p->key[i]的索引项，才能在外存上使用关键字p->key[i]. 书上没有体现。 */if (i > 0 && p->key[i] == key){found = TRUE;}else             //if( p->key[i] != key ){q = p;p = p->ptr[i];}}//找到了或者p指向了叶子结点，跳出while循环if (found){r.pt = p;r.i = i;r.tag = 1;}else{r.pt = q;r.i = i;r.tag = 0;//可以在此处由q指向结点的第i个和第i+1个关键字之间，插入关键字key}return r;
}int Search(BTree p, KeyType K)
{int i = 0; int j = 1;for (i = 0, j = 1; j <= p->keynum; j++){if (p->key[j] <= K)i = j;elsebreak;}return i;
}/*
//在内存上进行的：在结点T中找关键字key
int Search(BTree T, KeyType key)
{BTree p = T;int i = 0;int endnum = 0;if (p)  //结点不为空时{endnum = p->keynum;  //获得节点包含的关键字个数}else{return 0;}if(key >= p->key[endnum])   //节点不为空，但当前值比最大的key还大,返回当前关键字的下标{i = endnum;return i; }else if (key <= p->key[1])  //节点不为空，但当前值比最小的key还小,返回当前关键字的下标{return i;  //i==0}else   //key < p->key[endnum] && key > p->key[1]{for (i = 1; i < endnum; i++)  {if (p->key[i] <= key && key < p->key[i + 1]){return i;}}}
}
*///中序遍历打印B-数
void PrintBTree(BTree T)
{int i = 0;if (T){for (i = 0; i <= T->keynum; i++){PrintBTree(T->ptr[i]);if (i < T->keynum)  /* 因为关键字的下标最大值为T->keynum，若打印关键字i最大只能取到T->keynum-1（打印时下标为i+1）若打印子树指针指向的树，那么i可取到T->keynum  */{printf("%d  ", T->key[i + 1]);}}}
}

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

7.3.4 B+ 树（属于动态查找树，适用于动态查找表）

▲课本算法实现/▲09 查找/09 B+Tree/B+Tree.c —— kangjianwei
【不包含删除代码】

B+ 树 ——OI Wiki

数据结构之B+树删除详解 —— 每天都要进步一点点

7.4 散列表的查找

7.4.4 散列表的创建与查找

#include  <stdio.h>
#include  <stdlib.h>
#include <math.h>#define m 16  //表长,能容纳的最多的元素个数
#define NULLKEY 0typedef int KeyType;
typedef char OtherInfo;typedef struct elem
{KeyType key;OtherInfo otherinfo;
}elem;/*  elem HashTable[m];HashTable是一个一维数组名称，里面包含m个元素，每个元素类型为一个结构体elem。HashTable 也是指向该数基地址/第一个元素地址的指针  */void CreateHash(elem HT[]);
void Insert(elem HT[], KeyType key);
int SearchHash(elem HT[], KeyType key);
int H(KeyType key);
int maxPrimeNumber(int n);
int checkPrimeNumber(int n);
void printHashTable(elem HT[]);int main()
{elem HT[m] = { 0 };CreateHash(HT);printHashTable(HT);return 0;
}//散列表的创建
void CreateHash(elem HT[])
{int i = 0;int j = 0;int KEY = 0;int flag = 0;/*HT = (elem*)malloc(sizeof(elem) * m); //HT已经被定义为一个具有固定大小的数组。  */for (i = 0; i < m; i++){HT[i].key = NULLKEY;   //将所有位置置为空}for (i = 1; i <= m; i++){printf("请输入第%d个关键字（结束时输入-1）：", i);scanf_s(" %d", &KEY);if (KEY != -1){flag = SearchHash(HT, KEY);if (flag == -1){Insert(HT, KEY);}else{printf("该元素已存在，无法插入，请重新输入。\n");i--;}}else{break;}}if (i > m){printf("散列表已满。");return;}
}//将查找不存在的元素，插入哈希表中
void Insert(elem HT[],KeyType key)
{int	H0 = 0;int Hi = 0;int i = 0;H0 = H(key);if (HT[H0].key == NULLKEY){HT[H0].key = key;}else{for (i = 1; i < m; i++){Hi = (H0 + i) % m;if (HT[Hi].key == NULLKEY){HT[Hi].key = key;break;}//如果HT[Hi].key是其它元素,那么继续计算下一个散列值}}
}//算法7.10 散列表的查找
int SearchHash(elem HT[], KeyType key)
{int i = 0;int	H0 = H(key);int Hi = 0;if (HT[H0].key == NULLKEY){return -1;}else if(HT[H0].key == key){return H0;}else   //HT[H0].key是其它元素{for (i = 1; i < m; i++){Hi = (H0 + i) % m;if (HT[Hi].key == NULLKEY){return -1;}else if (HT[Hi].key == key){return Hi;}else  {; //如果HT[Hi].key是其它元素,那么继续计算下一个散列值}}return -1;}
}//散列函数
/* 采用除留余数法构造散列函数，选择p为小于表长m的最大质数 */
int H(KeyType key)
{int p = maxPrimeNumber(m);return key % p;
}//确定[0,n]范围内的最大质数
int maxPrimeNumber(int n)
{int i = 0;int status = checkPrimeNumber(0);int max = 0;for (i = 0; i <= n; i++){status = checkPrimeNumber(i);if (status){max = i;}}return max;
}//判断一个数是否是素数（是的话返回1，不是返回0）
int checkPrimeNumber(int n)
{int i = 0;int sq = floor(sqrt(n)); //不大于√n的最大整数/*floor向下取整，ceil向上取整 */if (n <= 1) {return 0; //负数、0 和1 均不是素数}for (i = 2; i <= sq; i++){if (n % 2 == 0 || n % i == 0)  //n%2==0，说明n是偶数，而质数一定不是偶数{return 0;}}return 1;
}void printHashTable(elem HT[])
{int i = 0;printf("\n散列表中的元素为：");for (i = 0; i < m ; i++){if (HT[i].key != NULLKEY){printf("\n HT[%d].key = %d",i, HT[i].key);}//空槽不输出，但是其它的元素还是要输出}
}

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

这篇关于《数据结构（C语言版）第二版》第七章-查找（7.3.2-7.4）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1126541。

相关文章

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

对于大多数人而言，在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况，这使得“存储焦虑”不再是个别现象，而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得，我们似乎正处在互联网信息飞速增长的阶段，对于存储的需求也将会不断扩大。对于苹果用户而言，这一问题愈发严峻，毕竟512GB和1TB版本的iPhone可不是人人都消费得起的，因此成熟的外置存储方案开
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 （最大值之和）给定整数序列 a0,⋯,an−1，求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr（其中0≤l≤r<n0≤l≤r<n）表示，对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同，当且仅当下标不同。 例如，当原序列为 [1,2,1,2] 时，要计算子序列 [
阅读更多...
Verybot之OpenCV应用二：霍夫变换查找圆

Verybot之OpenCV应用二：霍夫变换查找圆

其实我是想通过这个程序来测试一下，OpenCV在Verybot上跑得怎么样，霍夫变换的原理就不多说了，下面是程序： #include "cv.h"#include "highgui.h"#include "stdio.h"int main(int argc, char** argv){cvNamedWindow("vedio",0);CvCapture* capture;i
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2