摸一摸数据结构(查找 1.0)

本贴最后更新于 1171 天前,其中的信息可能已经天翻地覆

这一块猫猫在学生时代也只是知道一点简单的查找方式,更高级更难的猫猫也不懂,所以会以概念与查找的思想为主,不会再去测试与实现。

猫猫接受了折磨,还是先把树的坑磨平了再来……

查找的基本概念

查找:在数据集合中寻找满足某种条件的数据元素称为查找。

查找表:用于查找的数据集合称为查找表。对查找表的操作一遍有四种

  1. 查询元素是否在表中
  2. 检索满足某个特定的数据元素的各种属性
  3. 在查找表中插入一个数据元素
  4. 从查找表中删除某个数据元素

静态查找表:在查找表的操作只涉及到 1,2

关键字:数据元素中唯一标识该元素的某个数据项的值(有点像数据库的主键)

平均查找长度:在查找过程中,一次查找的长度是指需要比较的关键字次数。

查找算法分类

根据概念分有静态和动态查找,从其他方面,也有不同的归类方式

  1. 线性结构
    1. 顺序查找
    2. 折半查找
    3. 分块查找(索引顺序查找)
  2. 树形结构
    1. 二叉排序树
    2. 二叉平衡树
    3. B 树,B+ 树
  3. 散列结构:散列表
  4. 效率指标:查找成功或失败

查找算法实现

在此之前我们先声明表结构,有了表的结构才能在表上进行查找。

表结构
#include <stdio.h>
#include <stdlib.h>
#include "Status.h"		
#include "Scanf.c"			

/* 查找表类型定义 */
typedef int KeyType;			//关键字类型 
typedef struct
{
	int key;					//关键字域
	float weight;				//其他域(此处可设为权重) 
}ElemType_Search;				//有序表元素类型 

//0号单元弃用 
typedef struct
{
	ElemType_Search *elem;		//数据元素存储空间基址,0号单元为空
	int length;					//表长度 
}Table;			

表结构中有表长度和指针(指向表中的结点信息)信息,而表中的结点结构有关键字和权值信息。

所以我们可以通过 key 来查找表中的结点信息。

#include "Base.h" 		

Status Create(FILE *fp, Table *T, int n)
{
	int i;
	int a;
	float b;
	 
	T->elem = (ElemType_Search *)malloc((n+1)*sizeof(ElemType_Search));
	if(!(T->elem))
		exit(OVERFLOW);

	//此表0号单元是弃用的 
	for((*T).length=0,i=1; i<=n; i++)
	{
		if(Scanf(fp, "%d%f", &a, &b)==2)
		{
			(*T).elem[i].key = a;
			(*T).elem[i].weight = b;
			(*T).length++;
		}
	}

	return OK;
}

void Destory(Table *T)
{
	if(T->elem)
		free(T->elem);

	T->elem = NULL;
	T->length = 0;
}

void Traverse(Table T, void(Visit)(ElemType_Search))
{
	int i;

	for(i=0; i<T.length; i++)
	{
		if(i && !(i%10))
			printf("\n");

		Visit(T.elem[i+1]);
	}

	printf("\n");
}

/* 输出查找表中的关键字 */
void PrintKey(ElemType_Search e)
{
	printf("%3d ", e.key);
}
顺序查找(无序表)
int Search_Seq(Table T, KeyType key)
{
	int i;

	T.elem[0].key = key;

	for(i=T.length; !EQ(T.elem[i].key, key); --i)
		;

	return i;
}

传入表 T 和关键字 key,将传入的 key 值赋予表头元素的 key 值(注意创建表是 0 号位次的结点是没有信息的,而传入这个信息是为了在查找不到的时候最后输出 0 代表没有该关键字)。

折半查找
int zheban(Table T,KeyType key){
	int low,high,mid;
	low=1;
	high=T.len;
	while(low<=high){
		mid=(low+high)/2;
		if(EQ(key,T.elem[mid].key)) return mid;
		else if(LT(key,T.elem[mid].key)) high=mid-1;
		else low=mid+1;
	}
	return 0;

}

折半查找的思想很容易理解,以查找数组为例,我们定义 mid,low,high 来代表数组的上下限和中间位置的下标值。

从数组的中间开始查找(偶数也随便在中间的那两个随便选一个),最好的情况是等于(但一般不是);若大于中间数据,则我们更新中间值 mid 为(mid+high)/2,low 更新为 mid;若小于,则更新 mid 和 high。

如此循环,直至找到。若最后更新到 2 个相邻位次的值不等,则数组内没有该数据。

斐波那契查找

知道这两个的先知道斐波那契数列(1,1,2,3,5,8,13,21……),在这样的数列中,随着其递增,前后 2 个数的比值会越来越接近 0.618(黄金比例),利用这个特性,我们可以对折半进行提升。(通过运用这个比例来选择查找点进行查找,所以斐波那契查找也是一种有序查找算法)

步骤:

  • 构建斐波那契数列;
  • 计算数组长度对应的斐波那契数列元素个数;
  • 对数组进行填充;
  • 循环进行区间分割,查找中间值;
  • 判断中间值和目标值的关系,确定更新策略;
#include "FibonacciSearch.h" 			//**▲09 查找**//

int Search_Fib(Table T, KeyType key)
{
	int low, high, mid;
	int Fib[MaxSize+1];
	int i, k;
	int *table;

	Fib[1] = Fib[2] = 1;
	for(i=3; i<=MaxSize; i++)
		Fib[i] = Fib[i-1] + Fib[i-2];

	table = (int *)malloc((Fib[MaxSize])*sizeof(int));

	for(i=1; i<=T.length; i++)
		table[i] = T.elem[i].key;

	for(i=T.length+1; i<=Fib[MaxSize]-1; i++)
		table[i] = T.elem[T.length].key;

	k = MaxSize;
	low = 1;
	high = Fib[k];

	while(low<=high)
	{
		mid = low + Fib[k-1] - 1;	//中点的确定 

		if(key<table[mid])
		{
			high = mid - 1;
			k = k - 1;
		}
		else if(key>table[mid])
		{
			if(mid<T.length)
			{
				low = mid + 1;
				k = k - 2;
			}
			else
				return 0;			//未找到 
		}
		else
		{
			if(mid<T.length)
				return mid;
			else
				return T.length;	//在最后一个位置 
		}
	}

	return 0; 
}

#endif

首先创建斐波那契数列,在根据表的长度将斐波那契数列的值替换为表中的关键字(注意这里是将斐波那契的值添加入表值,没加一次表长度加一)。

之后我们就可以确定表中的最值和中点值。这里中点值的算法不是像折半一样用最值和除以二,而是用低于高值之间的关系来确定。

因为斐波那契数列 f[k]=f[k-1]+f[k-2];所以数列可以分为 2 段,(后补)

插值查找
#include "InterpolationSearch.h" 			
int Search_Int(Table T, KeyType key)
{
	int low, high, m;
	float j;

	low = 1;
	high = T.length;

	while(low<=high)
	{
		m = (1.0*(key-T.elem[low].key)/(T.elem[high].key-T.elem[low].key))*(high-low) + low;	//注意浮点数转整型

		if(key<T.elem[m].key)
			high = m - 1;
		else if(key>T.elem[m].key)
			low = m + 1;
		else
			return m;
	}

}

#endif

差值查找是一种有序表的操查找方式,根据关键字与查找表中最大最小记录关键字比较后的查找方法。同时也是基于二分查找,将查找点的选择改为自适应选择来提高效率。

什么是差值查找

次优查找树
二叉排序树
平衡二叉树
B 树查找与相关操作

什么是 B 树

我们可以先知道它是怎么实现了,再去思考他的思想。

B 树,又叫多路平衡二叉树,B 树中所有结点的孩子个数的最大值是 B 树的阶,通常用 m 表示。一棵 m 阶 b 树或为空树,或为满足以下特性的 m 叉树

  1. 树中每个结点最多有 m 棵子树,至多含有 m-1 个关键字。

  2. 若根结点不是终端节点(不是叶子结点),则至少有 2 课子树。

  3. 除根结点外的所有非叶子结点至少有 m/2 棵子树。

  4. 所有非叶子结点的结构:

    n p_0
    k_1
    p_1 k_2
    p_2 …… k_n
    p_n

    其中 k_i 是关键字,满足从小到大的顺序,P_i 是指向子树根结点的指针,且指针

  5. 所有叶子结点都出现在同一层次上,并且不带信息,实际上这些结点不存在(指向这些结点的指针为空)

#include <stdlib.h>
#include <math.h>							//提供ceil原型 
#include "../00 Base/Base.c" 				//**▲09 查找**//

/* 宏定义 */
#define M 3									//B树的阶,暂设为3 
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a) < (b))

/* 类型定义 */ 
typedef ElemType_Search BTElemType;			//B树元素类型 
typedef struct BTNode						//B树存储表示
{
	int keynum;								//结点中关键字个数 
	struct BTNode* parent;					//指向双亲结点 

	KeyType key[M+1];						//关键字向量,0号单元未用 
	struct BTNode* ptr[M+1];				//子树指针向量 
}BTNode;									//B树结点 
typedef BTNode* BTree;						//指向B树结点的指针

/* B树查找结果类型 */ 
typedef struct
{
	BTree pt;								//指向找到的结点 
	int i;									//1...n,关键字在结点中的序号(插入位置) 
	int tag;								//1:查找成功,0:查找失败 
}Result; 
B+ 树
双链树
trie 树
哈希表

ps: 摸一摸数据结构(目录)

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...