首页 > 其他分享 >【数据结构】查找

【数据结构】查找

时间：2023-06-11 18:03:11浏览次数：40  
标签：结点 二叉 ST 关键字 查找 key 数据结构

基本概念

查找表  由同一类型的数据元素（记录）构成的集合。所谓集合指记录间不存在前驱后继关系，因此查找表是一种应用灵便的结构。

静态查找表  只对查找表做查找操作，即只查询某个记录是否在表中，或只检索某个记录的各种属性。或者说：查找表加上不会使该表的内容发生变化的查找操作，称作静态查找表。

动态查找表  查找过程中插入表中原来不存在的记录或者删除已经存在的记录，称作动态查找表。

关键字  数据元素中某个数据项的值，用它可以标识一个数据元素。关键字有主关键字和次关键字之分 主关键字可以唯一的标识一个记录，次关键字能标识若干记录 。

查找  根据给定的值，在查找表中确定一个其关键字等于给定值的记录。记录存在，称查找成功，此时查找的结果为整个记录的信息或该记录在表中的位置。反之，称查找不成功，此时查找结果可以为空记录或空指针。

比较时约定的宏

#define  EQ(a,b)   ((a)==(b))

#define  LT(a,b)    ((a) < (b))

#define  LQ(a,b)   ((a)<=(b)) 

带参数的宏，宏体代换宏名，实参代替形参，代换时不能人为用（）

#define  EQ(a,b)   (strcmp((a),(b))==0)

#define  LT(a,b)    (strcmp((a),(b)) < 0)

#define  LQ(a,b)   (strcmp((a),(b))<=0) 

 线性表的查找

顺序查找（线性查找）

应用范围：顺序表或线性链表表示的静态查找表

表内元素之间无序

顺序表的表示

数据元素类型定义

typedef struct
{
	KeyType key;
}ElemType;
typedef struct
{
	ElemType *elem;
	int length;
}SSTable;
SSTable ST;

在顺序表ST中查找值为key的数据元素

从最后一个元素开始比较

改进：把待查关键字key存入表头（哨兵）从后往前比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。

int Search_Seq(SSTable ST,KeyType key)
{
  ST.elem[0].key=key;
  for(i=ST.length;!EQ(ST.elem[i].key,key;i--);
  return i;
}

顺序查找时间性能分析

平均查找长度（Average Search Length)  为确定记录在查找表中的位置，需要和给定值比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度ASL 。

ASL=∑PiCi        (i=1,2,……n) 

Pi为查找第i个记录的概率

Ci为查找到与给定值相等的第i个记录的关键字时已进行过的比较次数 。

比较次数与key位置有关：

查找第i个元素，需要比较n-i+1次。

查找失败，需要比较n+1次。

【数据结构】查找_子树

【数据结构】查找_二叉排序树_02

【数据结构】查找_子树_03

【数据结构】查找_结点_04

【数据结构】查找_子树_05


【数据结构】查找_子树_06

顺序查找的特点

优点：算法简单，逻辑次序无要求，且不同存储结构均适用。

缺点：ASL太长，时间效率太低。

折半查找

每次将待查记录所在区间缩小一半。

int Search_Bin ( SSTable ST, KeyType key ){
    low = 1;  high = ST.length;  
    while (low <= high) {
        mid = (low + high) / 2;
        if (EQ (key , ST.elem[mid].key) )//
            return  mid;    
        else  if ( LT (key , ST.elem[mid].key) )
            high = mid - 1; 
        else  low = mid + 1; 
    }
    return 0;  
}
//递归算法
int search_bin(SSTable ST,keyType key,int low,int high)
{
  if(low>high)
    return 0;
  mid=(low+high)/2;
  if(key==ST.elem[mid].key)
    return mid;
  else if(key<ST.elem[mid].key)
    
}

【数据结构】查找_子树_07

重要结论：

如果查找成功，那么比较次数就等于路径上的结点数，也就是结点的层数。

比较次数小于等于树的深度。

查找不成功：比较次数=路径上的内部结点数 比较次数小于等于树的深度。

折半查找优点：效率比顺序查找高。

缺点：只适用于有序表，且限于顺序存储结构。

索引顺序表的查找

条件：1、将表分成几块，且表或者有序，或者分块有序；若i<j，则第j块中所有记录的关键字均大于第i块中的最大关键字。

2、建立索引表（每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序）。

查找过程：先确定待查记录所在块（顺序或折半查找），再在块内查找（顺序查找）。

【数据结构】查找_子树_08

优点：插入和删除比较容易，无需进行大量移动。

缺点：要增加一个索引表的存储空间。

有序顺序表的查找——斐波那契查找

Fibonacci数列：1   1   2   3   5   8   13   21   34   55…… 

假设表长比某个斐波那契数小1，n=Fu -1

例如：表长为20，20=F8-1，即u=8 

首先将key与ST.elem[Fu-1].key比较。若相等，找到 

若key< ST.elem[Fu-1].key，则在1….12间查找，注意此时表长为Fu-1-1 

若key>ST.elem[Fu-1].key,   则在14…20间查找，此时表长为Fu-2-1 

【数据结构】查找_二叉排序树_09

【数据结构】查找_二叉排序树_10

【数据结构】查找_结点_11

//静态查找表的建立及斐波那契查找
#include "my.h"
#include <stdio.h>
#include <stdlib.h>

#define  EQ(a,b)   ((a)==(b))
#define  LT(a,b)   ((a)< (b))
#define  LQ(a,b)   ((a)<=(b))

typedef int KeyType;

typedef struct{
     KeyType    key;

}ElemType;

typedef struct{
    ElemType *elem;
    int length;
}SSTable;

Status Create(SSTable *ST,int n)
{
  int i;

  ST->elem=(ElemType*)malloc((n+1)*sizeof(ElemType));
  if(!ST->elem) exit(OVERFLOW);
  for(i=1;i<=n;i++)
     scanf("%d",&ST->elem[i].key);
  ST->length=n;
  return OK;
}

Status Create2(SSTable *ST,int n,int a[])
{
  int i;

  ST->elem=(ElemType*)malloc((n+1)*sizeof(ElemType));
  if(!ST->elem) exit(OVERFLOW);
  for(i=1;i<=n;i++)
     ST->elem[i].key=a[i];
  ST->length=n;
  return OK;
}


int Search(SSTable ST,KeyType key){
   int i;

   ST.elem[0].key=key;
   for(i=ST.length;!EQ(ST.elem[i].key,key);--i);
   return i;
}

int Search_Fibo(SSTable ST,KeyType key){
   int i,u,low,high,mid,flag=0;
   int fibo[]={0,1,1,2,3,5,8,13,21,34,55};
   
   for(i=1;i<=10;i++){
   	if(fibo[i]-1==ST.length)
   	  u=i;
   	if(i>10) return -1;
   }   
   low=1,high=ST.length;  
    
   while(low<=high){
   	printf("u=%d,Fibo[u]=%d,",u,fibo[u]);
   	if(flag==0)
	   	mid=fibo[u-1];
	else
	    mid=low+fibo[u-1]-1;
	printf("low=%d,mid=%d,high=%d\n",low,mid,high);
	
   	if(EQ(key,ST.elem[mid].key)) return mid;
   	else if(LQ(key,ST.elem[mid].key)){
   		flag=0;
   		high=mid-1;
   		u=u-1;   		
	}
	else{
		flag=1;
		low=mid+1;
		u=u-2;
	}
   } 
   
   printf("u=%d,Fibo[u]=%d,",u,fibo[u]);
   printf("low=%d,mid=%d,high=%d\n",low,mid,high);
   
   return -1;
}

Status Traverse(SSTable ST, void (*visit)(KeyType)){
   int i;
   for(i=1;i<=ST.length;i++)
     (*visit)(ST.elem[i].key);
}

void fun(KeyType key){
   printf("%d ",key);
}

int main()
{
   SSTable ST;
   int a[]={0,11,22,33,44,55,66,77,88,99,100,
            110,120,130,140,150,160,170,180,190,200};

//   Create(&ST,10);
//   Traverse(ST,fun);
//   printf("\n");
//   printf("%d\n",Search(ST,5));
//   printf("%d\n",Search(ST,20));
   
   Create2(&ST,20,a);
   Traverse(ST,fun);  
   printf("\n");     
   printf("position:%d\n",Search_Fibo(ST,-1));
   printf("position:%d\n",Search_Fibo(ST,300));
   printf("position:%d\n",Search_Fibo(ST,44));
     
   return 0;
}

树表的查找

当表插入、删除操作频繁时，为维护表的有序性，需要移动表中很多记录。

改用动态查找表——几种特殊的树

表结构在查找过程中动态生成

对于给定值key

若表中存在，则成功返回；

否则，插入关键字等于key的记录。

动态查找表主要有二叉树结构和树结构两

种类型。二叉树结构有二叉排序树、平衡 二叉树等。树结构有B-树、B+树等。 

二叉排序树

二叉排序树或者为空，或者是满足下列性质的二叉树：

若其左子树不空，则左子树上所有结点的值均小于其根结点的值

若其右子树不空，则右子树上所有结点的值均大于等于其根节点的值

它的左右子树也分别是二叉排序树。 

二叉排序树的中序序列是递增的 。

二叉排序树的性质：

中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排序的递增有序序列。

二叉排序树的操作——查找

BST的查找过程：  首先将给定值与根节点的关键字进行比较，若相等则查找成功，否则按给定值与根节点的关键字之间的大小关系，分别在左子树和右子树上进行查找。 

BiTree SearchBST(BiTree T, KeyType key){
    if( (!T)|| EQ(key, T->data.key) )
        return  T;
    else  if  LT(key, T->data.key) 
        return (SearchBST (T->lchild, key));
    else
        return (SearchBST (T->rchild, key));
}

二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。

【数据结构】查找_结点_12

二叉排序树的操作——插入

从空树开始，经过一系列的查找和插入操作(未找到时则插入)，可将一组关键字生成为一棵二叉排序树。 

若二叉排序树为空，则插入结点作为根结点插入到空树中；

否则，继续在其左、右子树上查找；

树中已有，不再插入；

树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子节点的左孩子或右孩子。

插入的元素一定在叶结点上。

Status InsertBST(BiTree  &T,  ElemType  e ){
     if (!SearchBST ( T, e.key , NULL , p )){
           s = (BiTree) malloc (sizeof (BiTNode));
    s->data = e;
    s->lchild = s->rchild = NULL; 
    if ( !p )  T = s;   // 根结点
    else if LT(e.key, p->data.key) 
        p->lchild = s;
    else p->rchild = s; 
    return TRUE;  

     }
     else return FALSE;
}

二叉排序树的操作——删除

【数据结构】查找_子树_13

【数据结构】查找_结点_14

【数据结构】查找_子树_15

以其中序前驱值替换之，然后删除该前驱结点。前驱是左子树中最大的结点。

也可以用其后继替换之，然后再删除该后继结点。后继是右子树中最小的结点。

Status DeleteBST (BiTree &T, KeyType key ) {
    if (!T)  return FALSE;
    else {   
        if ( EQ (key, T->data.key) )  { return Delete (T); }
        else if ( LT (key, T->data.key) )
            return DeleteBST (T->lchild, key );
        else
            return DeleteBST ( T->rchild, key );              
    }
}
Status Delete ( BiTree &p ){
    if (!p->rchild) {
        q = p;  p = p->lchild;  free(q); 
    }
    else if (!p->lchild) {
        q = p;  p = p->rchild;  free(q);
    }
    else 
    {q = p;  s = p->lchild;
while (s->rchild) { q = s;  s = s->rchild; }
p->data = s->data; 
if (q != p )  q->rchild=s->lchild;
//q==p表明c没有右子树
else q->lchild = s->lchild;
free(s);
 }  //左右子树均不空
    return TRUE；
}

显然，当二叉排序树为单支树时，查找性能最差，查找长度为(n+1)/2，与顺序查找相同。而最好情况是二叉排序树与折半查找的判定树形态相同，与log2n成正比。

因此为提高二叉排序树的查找性能，应尽量使该树平衡。 

平衡二叉树

又称AVL树。

一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：

①左子树与右子树的高度之差的绝对值小于等于1；

②左子树和右子树也是平衡二叉排序树。

为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子（BF）。

平衡因子=结点左子树的高度-结点右子树的高度

根据平衡二叉树的定义，平衡二叉树上所有的结点的平衡因子只能是-1、0、1。

【数据结构】查找_二叉排序树_16

失衡二叉排序树的分析与调整

当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现平衡因子绝对值大于1的结点。

【数据结构】查找_二叉排序树_17

如果在一棵AVL树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡。

【数据结构】查找_子树_18

【数据结构】查找_二叉排序树_19

（1）LL型调整

【数据结构】查找_二叉排序树_20

【数据结构】查找_结点_21

【数据结构】查找_结点_22

【数据结构】查找_结点_23


（2）RR型调整

【数据结构】查找_子树_24


【数据结构】查找_结点_25


【数据结构】查找_二叉排序树_26

【数据结构】查找_子树_27

（3）LR型调整

在当前失衡结点的左子树的右子树插入了一个结点导致的失衡

【数据结构】查找_结点_28

【数据结构】查找_结点_29

【数据结构】查找_结点_30

（4）RL型调整

在当前失衡结点的右子树的左子树插入了一个结点导致的失衡

【数据结构】查找_结点_31

【数据结构】查找_子树_32

例题

输入关键字序列（16，3，7，11，9，26，18，14，15），给出构造一棵AVL树的步骤。

【数据结构】查找_二叉排序树_33

重要结论：高度为h的AVL树的最少结点个数：n(h)=F(h+2)-1 (n>0)

其中F(i)为Fibonacci数列中的第i项的值。

此定理还可以表述为n(h)=n(h-1)+n(h-2)+1

n(1)=1  n(2)=2  n(3)=4 n(4)=7               n(5)=12             n(6)=20 

则具有n个结点的平衡二叉树的最大深度：

h(n)= logϕ(sqrt(5) (n+1)) - 2 

B-树

一棵m阶的B-树，或为空树，或为满足下列特性的m叉树： 

1.树中每个结点至多有m棵子树

2.若根结点不是叶子，则至少有两棵子树

3.除根之外的所有非终端结点至少有  m/2 (向上取整)棵子树 

4.所有非终端结点包含下列信息数据     (n，A0，K1，A1，K2，A2，…，An-1，Kn，An) 

其中：

Ki为关键字，且Ki<Ki+1 

Ai为指向子树根结点的指针

Ai-1所指子树中所有结点的关键字均小于Ki Ai   所指子树中所有结点的关键字均大于Ki 

n为关键字的个数，m/2  -1≤n≤m-1，n+1为子树个数 

5.所有叶子结点都在同一层次，并且不带信息 

B-树的插入实现

对于B-树来说，与二叉排序树相同，插入操作一定是发生在叶子结点上。可与二叉排序树不同的是，B-树插入一个元素的过程有可能会对该树的结构产生连锁反应。

【数据结构】查找_结点_34

【数据结构】查找_子树_35

【数据结构】查找_二叉排序树_36

【数据结构】查找_子树_37

【数据结构】查找_结点_38

【数据结构】查找_结点_38


【数据结构】查找_子树_40

【数据结构】查找_结点_41

【数据结构】查找_结点_42

B-树的插入：结点分裂法

若p结点已有m-1个关键字，或者说p已满，此时若插入新的关键字，则从中间，即m/2向上取整或者说从(m+1)/2向下取整的位置，将结点分解为p和p’。 

此时*p中包含[m/2]-1个关键字，*p结点的内容为：

([m/2]-1,A0,K1,A1,K2……K[m/2]-1,A[m/2]-1) 

而*p’中包含m-[m/2]个关键字，*p’结点的内容为：

(m-[m/2],A[m/2],K[m/2]+1, A[m/2]+1, ……,Km,Am) 

最后将K[m/2]和p’插入到*p的父结点中 

B-树的删除

首先找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于

⎡m/2⎤-1，否则，要从其左(或右)兄弟结 点“借调”关键字，若其左和右兄弟结点 均无关键字可借(结点中只有最少量的 关键字)，则必须进行结点的“合并” 

【数据结构】查找_二叉排序树_43

【数据结构】查找_二叉排序树_44

【数据结构】查找_结点_45

【数据结构】查找_二叉排序树_46

【数据结构】查找_结点_47

【数据结构】查找_子树_48

【数据结构】查找_二叉排序树_49

为什么二叉排序树长高时，新结点总是一个叶子，而B-树长高时，新结点总是根？哪一种长高能保证树平衡？ 

由二叉排序树的性质可知，插入位置必为查找过程中最后一个结点的左孩子或者右孩子，即新插入的是叶子。 

而在深度为h+1的m阶B-树上插入关键字要分两步进行：首先在第h层找到该关键字应插入的结点x，然后判断其中是否有空位置，若其关键字的个数小于m-1，直接插入即可；若其中关键字个数等于m-1，则需要分裂该结点。分裂方法为：将该结点以中间关键字为界一分为二，并将中间关键字向上插入到父结点。若父结点已满，则用相同的方法继续分裂，在最坏情况下，可能一直向上分裂到根结点，此时树的高度才会增加1。因此B-树长高时新结点一定是根。也正因为如此，B-树长高时将保证树的平衡。 

散列表的查找

散列表的基本概念

基本思想：记录的存储位置与关键字之间存在对应关系。

对应关系——hash函数

【数据结构】查找_结点_50

散列表的若干术语

散列方法（杂凑法）

选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定定值k计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功。

散列函数（杂凑函数）：散列方法中使用的转换函数。

散列表（杂凑表）：按上述思想构造的表。

冲突：不同的关键码映射到同一个散列地址

key1≠key2，但是H(key1)=H(key2)

【数据结构】查找_结点_51

同义词：具有相同函数值的多个关键字。

在散列查找方法中，冲突不可避免，只能减少。

散列函数的构造方法

直接定址法

【数据结构】查找_结点_52


除留余数法

【数据结构】查找_二叉排序树_53

解决冲突的方法

开放地址法

【数据结构】查找_子树_54

【数据结构】查找_子树_55


链地址法

基本思想：相同散列地址的记录链成一单链表。

【数据结构】查找_子树_56

建立散列表步骤

①取数据元素的关键字key，计算其散列函数值（地址）。若该地址对应的链表为空，则将该元素插入此链表；否则执行第②步解决冲突。

②根据选择的冲突处理方法，计算关键字key的下一个存储地址。若该地址对应的链表为不为空，则利用链表的前插法或后插法将该元素插入此链表。

优点：

非同义词不会冲突，无聚集现象。

散列表的查找

【数据结构】查找_结点_57


【数据结构】查找_结点_58

【数据结构】查找_结点_59

设哈希表长m=14，哈希函数H(key)=key mod 11。表中已有4个结点H(15)=4，H(38)=5，H(61)=6，H(84)=7，其余地址为空，如用平方探测法处理冲突，则关键字49的地址为 9.

H(49)=49mod11=5 冲突 H(49)=(5+11)mod11=6  冲突 H(49)=(5+22)mod11=9

假设有k个关键字互为同义词，若用线性探测法将其存入哈希表中，至少需要((1+2+...+k)=k(k+1)/2 )次探查。 

标签：结点,二叉,ST,关键字,查找,key,数据结构
From： https://blog.51cto.com/heliotopekxy/6458421

相关文章

  • NOI / 1.9编程基础之顺序查找
    06:笨小猴描述笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-mi......
  • 推荐两个查找rpm包的网站
    http://rpmfind.net/http://rpm.pbone.net/addbyjoeyon1985......
  • Redis学习笔记4-脚本、持久化和集群 Redis学习笔记1-基础命令及数据结构： http://blog.
        Redis学习笔记4-脚本、持久化和集群Redis学习笔记1-基础命令及数据结构：http://blog.guoyb.com/2016/07/21/learn-redis-basic-commands/Redis学习笔记2-事务与过期时间：http://blog.guoyb.com/2016/08/23/learn-redis-adv/Redis学习笔记3-排序与消息通知：http://blog......
  • LeetCode----二分查找
    1算法原理适用条件：有序数组2算法模板classSolution:defsearch(self,nums:List[int],target:int)->int:left=0right=len(nums)-1#规则[left,right]whileleft<=right:#根据规则，举例[1,1]添加=是否合法即可......
  • 【数据结构】顺序表
    前言<fontcolor=bluesize=4>顺序表作为数据结构中的小小弟，还是很好应付的</font><fontsize=4>。说到数据结构，顺序表是我们的向导，它让你明白数据结构到底是干啥的，为啥数据结构这么的重要。</font></font><fontsize=4>实际上，通讯录的底层就是一个顺序表，里面的增添联系人，删......
  • Redis数据结构：高频面试题及解析
    概述Redis是速度非常快的非关系型（NoSQL）内存键值数据库，可以存储键和五种不同类型的值之间的映射。键的类型只能为字符串，值支持五种数据类型：字符串、列表、集合、散列表、有序集合。Redis支持很多特性，例如将内存中的数据持久化到硬盘中，使用复制来扩展读性能，使用分片来扩展写性能......
  • 《数据结构与算法》之队列与链表复习
    导言：我们在上一次学习了堆栈的数据结构以后，可以了解到它是受限制的操作，比如我们操作只能在栈顶，现在我们要学习的东西叫做队列，它也是受限制的一种数据结构，它的特点是队头只出数据，而队尾只入数据，它的结构就和它的名字，像我们平时排队一样先来的人肯定要先服务啊，所以它的英文叫做Fri......
  • Redis数据结构--SDS动态字符串
    Redis中保存的key是字符串，value往往是字符串或者字符串的集合，但是redis并没有直接使用c语言中的字符串原因在于：1.获取字符串长度需要通过运算2.非二进制安全3.不可修改SDSstructsdshdr{//记录buf数组中使用字节的数量//等于SDS所保存字符串的长度......
  • 和与积 题解 简单二分查找
    题目大意：给定两个整数\(a(2\lea\le2\times10^9)\)和\(b(1\leb\le10^{18})\)。判断是否存在两个正整数\(x\)和\(y\)，同时满足如下两个条件：\(x+y=a\)\(x\timesy=b\)解题思路：用\(a-x\)表示\(y\)，可以得到面积的表达式为\(x\times(a-x)\)，然后......
  • 大二上 | 数据结构小测试卷
    一共有三张图片：......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99