精华内容
下载资源
问答
  • 大话数据结构 第八章 查找顺序表查找、有序表查找、线性索引查找查找定义顺序表查找有序表查找折半查找插值查找斐波那契查找线性索引查找稠密索引分块索引倒排索引 查找 定义 查找表:由同一类型的数据元素...

    大话数据结构 第八章 查找(一) 顺序表查找、有序表查找、线性索引查找

    查找

    定义

    • 查找表:由同一类型的数据元素(或记录)构成的集合
    • 关键字:数据元素中某个数据项的值。若此关键字可以唯一地标识一个记录,则称其为主关键字
    • 查找表分为静态查找表和动态查找表
    • 静态查找表:只作查找操作的查找表
    • 动态查找表:在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已经存在的某个数据元素

    顺序表查找

    • 顺序查找又叫线性查找,是最基本的查找技术,它的查找过程是:从表中第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值比较,若==某个记录的关键字和给定值相等,则查找成功,找到所查的记录;==如果知道最后一个(或第一个)记录,其关键字和给定值比较都不等时,则表中没有所查的记录,查找不成功。
    • 在查找过程中可以设置“哨兵”,免去在查找过程中每一次比较后都要判断查找位置是否过界。
    • 算法的时间复杂的为O(n)

    有序表查找

    • 前提:线性表中记录有一定顺序

    折半查找

    • 又称为“二分查找”
    • 其基本思想是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止。
    • 时间复杂度O(log n)

    插值查找

    • 使用插值计算公式
    • 时间复杂度O(log n)
    • 适用于表长较大,关键字分布比较均匀的查找表。不适于极端数据

    斐波那契查找

    • 使用斐波那契数组辅助进行分隔
    • 时间复杂度O(log n)
    • 平均性能要优于折半查找

    线性索引查找

    • 索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程
    • 索引按照结构可分为:线性索引、树形索引和多级索引。其中线性索引主要有稠密索引、分块索引和倒排索引

    稠密索引

    • 稠密索引是指在线性索引中,将数据集中的每个记录对应一个索引项,索引项一定是按照关键码有序的排列
    • 可以使用折半、插值、斐波那契等有序查找方法

    分块索引

    • 为了减少索引项的个数,可以对数据集进行分块,使其分块有序,然后再对每一块建立一个索引项
    • 要求块内无序,块间有序
    • 索引项结构:最大关键码,块长,块首指针
    • 查找步骤:
    • 【1】在分块索引表中查找要查关键字所在的块
    • 【2】根据块首指针找到相应的块,并在块中顺序查找关键码
    • 分块索引在兼顾了对细分块不需要有序的情况下,大大增加了整体查找的速度,所以普遍被用于数据库表查找等技术的应用中

    倒排索引

    • 索引项通用结构:次关键码,记录号表
    • 其中记录号表存储具有相同次关键字的所有记录的记录号(或者指向记录的指针),这样的方法就是倒排索引
    • 倒排索引的优点是查找记录非常快,但是缺点是记录号不定长
    展开全文
  • 对于分块有序查找首先,我们需要先建立一个索引表索引表中为每一块都设置–索引项,每一个索引项都包含两个内容: 该块的起始地址 该块最大(或最小)的元素显然,索引表是按关键字递增或递减次序排列的。如...

    算法背景

    有时候,可能会遇到这样的表:整个表中的元素未必有序,但若划分为若干块后,每一块中的所有元素均小于(或大于)其后面块中的所有元素。我们称这种为分块有序

    对于分块有序表的查找

    首先,我们需要先建立一个索引表,索引表中为每一块都设置–索引项,每一个索引项都包含两个内容:

    • 该块的起始地址
    • 该块中最大(或最小)的元素

      显然,索引表是按关键字递增或递减次序排列的。如下图所示:
      这里写图片描述

    查找过程

    在前面建立的索引表的基础上,我们查找一个关键字需要两个步骤:

    1. 在索引表中查找,目的是找出关键所属的块的位置。这里如果索引表较大的话,可以采用折半查找。
    2. 进入该块中,使用简单顺序表查找算法进行关键字查找。

    算法分析

    这种带索引表的分块有序表查找的时间性能取决于两步查找时间之和:如前面所述,第一步可以采用简单顺序查找和折半查找之一进行。第二步只能采用简单顺序查找,但由于子表的长度较原表的长度小。因此,其时间性能介于顺序查找和折半查找之间。

    展开全文
  • 动态查找表:不仅进行查找操作,而且在查找过程中还伴随着插入(查找的数据元素在表中时)、删除某个数据元素的操作。 3、关键字(key):是数据元素(或记录)的某个数据项的值,用它可标识(识别)一个数据元素...

    一、基本概念

    1、查找表:同一类型的数据元素(记录)构成的集合。

    2、静态查找表:对查找表只进行查找操作。动态查找表:不仅进行查找操作,而且在查找过程中还伴随着插入(查找的数据元素不在表中时)、删除某个数据元素的操作。

    3、关键字(key):是数据元素(或记录)的某个数据项的值,用它可标识(识别)一个数据元素(或记录)。

    4、平均查找长度(ASL):需和给定值进行比较的关键字个数的期望。

    二、常见的算法及其思想

    我们的存储结构为:

    typedef struct

          {  ElemType  *elem;

             int length;

          }SSTable;

    1、简单顺序查找 

    从表的一端开始,逐个把每条记录的关键字值与给定值k进行比较。若某个记录关键字值与给定值k相等,则查找成功,返回找到的记录位置。反之,若已查找到表的另一端,仍未找到关键字值与给定值相等的记录,则查找不成功,返回-1。我们用第一个存储单元来存储要查找的数值,来免去查找过程中每一步都要检测整个表是否查找完毕。这个单元起了监视哨的作用。

    2、折半查找

    首先确定待查记录所在的范围(区域)。假设用变量low和high分别表示当前查找区域的首尾下标。将待查关键字k和该区域的中间元素,其下标为mid=(low+high)/2的关键字进行比较。若相等,则查找成功,返回此位置值;否则若所找记录关键字大,则取后半部记录,否则取其前半部记录。

    3、分块查找(也叫索引顺序表)

    首先把表长为n的线性表分成b块,前b-1块记录个数为s=n/b,第b块的记录个数小于等于s。在每一块中,结点的存放不一定有序,但块与块之间必须是分块有序的(假定按结点的关键字值递增有序)。即指后一个块中所有记录的关键字值都应比前一个块中所有记录的关键字值大。为实现分块检索,还需建立一个索引表。索引表的每个元素对应一个块,其中包括该块内最大关键字值和块中第一个记录位置的地址指针。显然这个索引顺序表是一个递增有序表。

    基本思想:先建立索引(最大(最小)关键字表)。要查找关键字为key的元素,先按折半查找获得key对应记录所在的块,再按线性(顺序)查找在块中找到key对应的记录。

    4、静态树表的查找

    我们前面的几种方法都是假定查找是等概率然情况下进行的。实际中,如果概率是不等的,情况又如何呢?即使按折半查找中判断树进行,也不一定最优。使查找性能最佳的判定树是其带权内路径长充之和PH值

     

    三、算法的C语言描述

    1、简单顺序查找


     

    2、折半查找

    3、分块查找(也叫索引顺序表)

    #define MaxIndex <索引表的最大长度>

      typedef struct{

        KeyType key;

        int link;

       }IdxType;

    int IdxSerch(SSTable ST,IdxType index[],int b,KeyType key)

    { //分块查找关键字为k的记录,索引表为index[0..b-1] 

      int low=0,high=b-1,mid,i;

      int s=ST.length/b;           //每块记录个数

    while(low<=high) 

    {   //在索引表中进行折半查找,找到的位置放在low中

        mid=(low+high)/2;

        if(index[mid].key<key) low=mid+1;

        else high=mid-1;

    }//while

    if(low==b) low--;

    if(low<=b) //在顺序表中顺序查找

        {

                  for(i=index[low].link;(i<=index[low].link+s-1)&&(i<=ST.length);i++)

           {

                  //printf(" %d %d",ST.elem[i].key,key);   

                  if(ST.elem[i].key==key) return i;

              }//for

        return -1;

        }//if

    else return -1;

    }//IdsSerch

    4、静态树表的查找

    构造次优查找树的递归算法如下:

    按有序表构造次优二叉树的算法如:

    四、算法的C语言实现

    #include "stdio.h"

    #include "stdlib.h"

    #include "string.h"

    #include "math.h"

    #define OK 1

    typedef int KeyType;

    //静态查找表的顺序存储结构

    typedef struct

    {

    KeyType key;

    int item;

    }ElemType;

    typedef struct

    {

    ElemType *elem;//数据元素存储空间基址,建表时按实际升序分配,0号单元

                   //留空。

    int length;    //表长度

    }SSTable;

     

    typedef struct

    {

        KeyType key;

        int link;

    }IdxType;

    int MaxIndex;

    typedef struct BiTNode

     {

       ElemType data;

       BiTNode *lchild,*rchild; // 左右孩子指针

     }BiTNode,*BiTree;

     typedef BiTree SOSTree; // 次优查找树采用二叉链表的存储结构

    //输入

    int InputS(SSTable &ST)

     {

     int N;

     printf("Please input the number of data:\n");

     scanf("%d",&N);

     printf("Please input the %d's data:\n",N);

     ST.elem=(ElemType*)calloc(N+1,sizeof(ElemType));//动态生成N个数据单元空间,

     //0号单元不用

     if(!ST.elem) printf("error");

     for(int i=1;i<=N;i++)

           {

           printf("Please input the %d's data:\n",i);     

           scanf("%d",&ST.elem[i].key);

           printf("Please input the %d's item:\n",i);

        scanf("%d",&ST.elem[i].item);

        }//for

     ST.length=N;

     return OK;

     }//InputS

    //排序

    void Ascend(SSTable &ST)

    {

    //重建静态查找表为按关键字非降序排序

           int i,j,k;

           for(i=1;i<ST.length;i++)

           {

           k=i;

           ST.elem[0]=ST.elem[i];

           for(j=i+1;j<=ST.length;j++)

                  if(ST.elem[j].key<ST.elem[0].key)

                  {

                  k=j;

                  ST.elem[0]=ST.elem[j];

                  }//if

                  if(k!=i)

                  {

                  ST.elem[k]=ST.elem[i];

                  ST.elem[i]=ST.elem[0];

                  }//if

           }//for

    }//Ascend

    int Creat_Ord(SSTable &ST)

     { // 操作结果: 构造一个含n个数据元素的静态按关键字非降序查找表ST

       // 数据来自全局数组r

       int f;

       f=InputS(ST);

       if(f)

           Ascend(ST);

       return f;

     }

    //顺序查找

     int Search_Seq(SSTable ST,KeyType key)

     {

     int i;

     ST.elem[0].key=key;

     for(i=ST.length;ST.elem[i].key!=key;--i) ;

           return i;

     }//Search_Seq

     //折半查找

     int Search_Bin(SSTable ST,KeyType key)

     {

     int low,high,mid;

     low=1;

     high=ST.length;

     while(low<=high)

       {

        mid=(low+high)/2;

           if(ST.elem[mid].key==key) return mid;

           else if(key<ST.elem[mid].key) high=mid-1;

           else low=mid+1;

       }//while

     return 0;

     }//Search_Bin

     //分块查找

     

    int IdxSerch(SSTable ST,IdxType index[],int b,KeyType key)

    { //分块查找关键字为k的记录,索引表为index[0..b-1] 

      int low=0,high=b-1,mid,i;

      int s=ST.length/b;           //每块记录个数

    while(low<=high) 

    {   //在索引表中进行折半查找,找到的位置放在low中

        mid=(low+high)/2;

        if(index[mid].key<key) low=mid+1;

        else high=mid-1;

    }//while

    if(low==b) low--;

    if(low<=b) //在顺序表中顺序查找

        {

                  for(i=index[low].link;(i<=index[low].link+s-1)&&(i<=ST.length);i++)

           {

                  //printf(" %d %d",ST.elem[i].key,key);   

                  if(ST.elem[i].key==key) return i;

              }//for

        return -1;

        }//if

    else return -1;

    }//IdsSerch

     

    //释放

     int Destroy(SSTable &ST)

     { 

           // 初始条件: 静态查找表ST存在。操作结果: 销毁表ST

       free(ST.elem);

       ST.elem=NULL;

       ST.length=0;

       return OK;

     }

     

     int IdxSerchIt(SSTable &ST,KeyType s)

     {

     int i;

     printf("input the MaxIndex of index table:\n");

     scanf("%d",&MaxIndex); //注意对,MAxIndex的选取有讲究,不然会出

        //现结果不对的情况。

     IdxType index[MaxIndex];

     int ince=1;   

     for(int j=0;j<MaxIndex;j++)

           {     

           index[j].key=ST.elem[ince].key;

           index[j].link=ince;

        if(ince<ST.length) ince+=ST.length/MaxIndex;

        }//for

     i=IdxSerch(ST,index,MaxIndex,s);

     return i;

     }//IdxSerchIt

     

    int SecondOptimal(BiTree &T, ElemType R[],int sw[],int low,int high)

     { //构造次优查找树 

       int i,j;

       double min,dw;

       i=low;

       min=fabs(sw[high]-sw[low]);

       dw=sw[high]+sw[low-1];

       for(j=low+1;j<=high;++j) 

         if(fabs(dw-sw[j]-sw[j-1])<min)

         {

           i=j;

           min=fabs(dw-sw[j]-sw[j-1]);

         }

       if(!(T=(BiTree)malloc(sizeof(BiTNode))))

         return 0;

       T->data=R[i]; 

       if(i==low)

         T->lchild=NULL; 

       else

         SecondOptimal(T->lchild,R,sw,low,i-1); 

       if(i==high)

         T->rchild=NULL;

       else

         SecondOptimal(T->rchild,R,sw,i+1,high); 

       return OK;

     }

     

    void FindSW(int sw[],SSTable ST)

     { // 按照有序表ST中各数据元素的Weight域求累计权值表sw

       int i;

       sw[0]=0;

       for(i=1;i<=ST.length;i++)

           sw[i]=sw[i-1]+ST.elem[i].item;

     }

    int CreateSOSTree(SOSTree &T,SSTable ST)

     { // 由有序表ST构造一棵次优查找树T

       //ST的数据元素含有权域weight

       int sw[ST.length+1]; // 累计权值表sw

       if(ST.length==0)

         T=NULL;

       else

       {

         FindSW(sw,ST); // 按照有序表ST中各数据元素的Weight域求累计权值表sw

         SecondOptimal(T,ST.elem,sw,1,ST.length);

       }

       return OK;

     }

     

    int Search_SOSTree(SOSTree &T,KeyType key)

     { // 在次优查找树T中查找关键字等于key的元素。找到则返回OK,否则返回FALSE

       while(T) // T非空

         if(T->data.key==key)

           return OK;

         else if(T->data.key>key)

           T=T->lchild;

         else

           T=T->rchild;

       return 0; // 顺序表中不存在待查元素

     }

     void SearchIt(SSTable &ST)

     {

      int s,i;

      SOSTree T;

      printf("请输入要查找的数据:\n ");

      scanf("%d",&s);

       i=Search_Seq(ST,s); // 顺序查找

       //i=Search_Bin(ST,s);//折半查找

       //i=IdxSerchIt(ST,s);//分块查找

       //CreateSOSTree(T,ST);//创建静态查找树

       //Search_SOSTree(T,s);//静态查找树查找

       if(i)

         printf("%d: %d",i,ST.elem[i].key);

       else

         printf("没找到\n");

     }

    int main()

     {

           SSTable ST;

        Creat_Ord(ST);

           SearchIt(ST);

           return OK;

     }

    五、算法的复杂度分析

    1、简单顺序查找 

    从顺序查找过程可见(不考虑越界比较),顺序查找不论给定值k为何,若第1个记录符合给定值,只要比较1次。若第n个记录符合给定值,要比较n次,即ci=i。若每个记录的查找概率相等,且每次查找都是成功的。则在等概率的情况下,顺序查找的平均查找长度为:

    2、折半查找

    折半查找算法的计算复杂性可以用二叉树来进行分析。我们把当前查找区间的中间位置上的记录作为根。左子表和右子表中的记录分别作为根的左子树和右子树。由此得到的二叉树,称为描述二分查找的判定树或比较树。

    树中每个结点表示一个记录,结点的编号为该记录在表中的位置。找到一个记录的过程就是走了一条从根结点到与该记录结点的路径。和给定值进行比较的次数正好是该结点所在的层次数。折半查找在查找成功时和给定值进行比较的关键字的个数至多为floor(log2n)+1。同理,查找不成功的过程也是走了一条从根结点到某一个终端结点的路径,其所用的比较次数等于树的深度。 

    折半查找只适用有序顺序存储结构,不适于线性链表结构。为保持表的有序性,在顺序结构里插入和删除都必须移动大量的记录。折半查找特别适用于那种一经建立就很少改动,而又经常需要查找的线性表。

    3、分块查找(也叫索引顺序表)

    由于分块查找实际上是两次查找过程,所以分块查找的平均查找长度是:查找索引表确定给定值所在块内的平均查找长度ASLb与在块的查找关键值的平均查找长度ASLk之和。即ASL=ASLb+ASLk。

     

    4、静态树表的查找

    其查找过程类似折半查找。其平均查找长度和Logn成正比。当在记录中查找概率不等时,可用次优查找树。

    五、涉及函数

    1、void *calloc(unsigned num, unsigned size),分配一块内存,num和size分配内存的数量参数,实际字节等于num*size。头文件为alloc.h。

     

    展开全文
  • 为了提高查找效率,对65025个元素的有序顺序表建立索引顺序结构,最好情况下查找表中已有元素,平均需要执行(B)次关键字比较。 A. 10 B. 14 C. 20 D. 21 分析:明确一个概念:索引顺序结构就是分块...

    有序表的索引顺序结构查找次数分析

    @(算法学习)

    为了提高查找效率,对65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,平均需要执行(B)次关键字比较。
    A. 10
    B. 14
    C. 20
    D. 21

    分析:明确一个概念:索引顺序结构就是分块结构。综合了顺序查找和折半查找的优点

    分析一下这种存储结构下查找的策略。分块查找的思路是:将查找表分为若干子块,块内元素可以无序,但是块之间有序,将每个块中的最值抽出来建立一个索引表。索引表存储的是每个块的最值和地址,关键字有序。因此可以对其进行折半查找加快速度。

    再思考一般情况下折半查找平均查找长度。

    折半查找树是一棵平衡树。
    设为满的平衡树。高度为h,根结点高度是1.则每层最多结点是2h−12^{h-1}2h1.

    ASL=1n(1×1+2×2+...+h×2h−1)=1n((h−1)2h+1) ASL = \frac{1}{n}(1\times1+2\times2+...+h\times2^{h-1}) \\ = \frac{1}{n}\big((h-1)2^h+1\big) ASL=n1(1×1+2×2+...+h×2h1)=n1((h1)2h+1)

    树高h=⌈log2(n+1)⌉h =\lceil log_2 (n+1)\rceilh=log2(n+1)

    所以:

    ASL≈log2(n+1)−1 ASL \approx log_2(n+1)-1 ASLlog2(n+1)1

    由这个公式可以推导上面的问题了。

    将65025个关键字分组:65025=255\sqrt{ 65025 } = 25565025=255

    即分为255块,每块255个元素时,将会有最小的平均查找次数。

    总查找次数为:

    ASL=log2(255+1)−1+log2(255+1)−1=14. ASL = log_2(255+1) - 1 + log_2(255+1) - 1 = 14. ASL=log2(255+1)1+log2(255+1)1=14.

    2019.10 Update:

    第一届PAT算法直播课培训班招募帖,欢迎点击查看详情、

    END.

    展开全文
  • 查找表(search table)是由同一类型的...(3)在查找表中插入一个数据元素。 (4)从查找表中删除某个数据元素。 只做查询的操作的查找表称为静态查找表(Static Search Table)。 若在查找过程中同时插入查找...
  • 索引顺序查找又叫分块查找,它是介于顺序查找和折半查找之间的一种查找方法。折半查找虽然具有很好的性能,但其前提条件是...将查找表分为若干个子表,为每一个子表建立一个索引项存储在索引表中,索引项包括两项内容
  • 在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素 顺序查找: 从开头一个个比较,直到查找到关键字或者到达末尾 平均查找长度(ASL)=(n+1)/2 int search(int a[] ...
  • 根据给定的某个值,在查找表中确定一个其关键字(唯一的标识一个记录)等于给定值的数据元素或数据记录。静态查找:只查找,不修改元素[线性表、顺序查找、二分查找] 动态查找查找时,插入或者删除元素[二叉排序...
  • 数据结构第二天,完成啦!QAQ,开心! 1、顺序表 内存是以一个字节为索引单位的,一个字节是八位的,一个...列表进行查找的话,锁定第一个元素的初试位置,偏移量处直接找到访问的元素 (2)元素外置的顺序
  • 线性表的查找算法ASLASLASL的定义顺序查找基本思想及查找算法查找性能索引查找索引表的构建索引表顺序查找算法查找性能 查找算法涉及两主要问题:是数据如何组织——查找表;而是在查找表上如何查找——查找...
  • #笔记整理 ...给定一个值 key,含有 n 个记录的表中找出关键字等于 key 的记录。若找到,则查找成功,返回该记录的信息或该记录在表中的位置;否则查找失败,返回相关的指示信息。 静态查找表(Static S...
  • 条件: 将表分为几块,且表或者有序,或者分块有序(块间有序,块内无序); 分块有序含义: 若i<j,则第j块中所有记录的关键字均大于第i块中的最大关键字。...例子: 上述表中查找值为38的元素。 方法:首先...
  • 3.查找想要查询元素num在索引表的位置 4.在块内顺序查询关键字。 #include<stdio.h> typedef struct node { int start; //定义每数据块的头,尾及最大 int key; int tail; }Key; BlockSearch(int a
  • 该方法,this指针所代表的定长顺序表对象中,查找是否存在一个有序子表X,该子表中的元素全部依次对应other表中的所有元素. 若存在,返回OK,同时output参数中包含:X中每个元素在this表中索引
  • 此方法本身外,还需创建一个索引表。 按照索引表将待查表分为若干个块。索引表的一组数据代表待查表的一个块。即查找的思想为先找到需要查找元素的所在块,然后遍历这个块。得到需要查找元素在待查表的...
  • 根据给定的某个值,在查找表中确定一个其关键字(唯一的标识一个记录)等于给定值的数据元素或数据记录。 静态查找:只查找,不修改元素[线性表、顺序查找、二分查找] 动态查找查找时,插入或者删除元素[二叉排序...
  • 查找索引查找

    2017-12-03 16:24:18
    /* 名称:索引查找(分块查找) 说明:本程序写的有...它要求有两个表一个索引表,每个索引表中的索引对应一个元素表(此处的索引即为对应元素表中元素的最大值)。还要求表间有序,表内无序。这样首先在索引表中
  • 索引查找又称为分块查找,是种介于顺序查找和二分查找之间的查找方法,分块查找的基本思想是:首先查找索引表,可用二分查找顺序查找,然后确定的块进行顺序查找。 分块查找的时间复杂度为O(√n)。 ...
  • 索引查找又称为分块查找,是种介于顺序查找和二分查找之间的查找方法,索引查找的基本思想是:首先查找索引表,可用二分查找顺序查找,然后确定的块进行顺序查找实现索引查找算法前需要弄清楚以下...
  • 顺序查找

    2013-08-20 08:04:37
    是从表的一段开始逐个比较元素,若找到则返回元素在表中对应位置;否则,则返回一个无意义的位置标 识。 值得一提的是设置监视哨这一思想,将a[0]设置成监视哨则可以避免每次比较元素后都需要判断
  • 概念:给定一个值K,含有n个记录的文件进行搜索,寻找一个关键字值等于k的记录,如找到则输出该记录,否则输出查找不成功的信息。 查找算法的优劣 用比较次数的平均值来评估算法的优劣,称为平均查找长度ASL ...
  • 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素 静态查找查找时不做插入或删除操作。适用于用线性表存储,可以采用顺序查找或折半查找 动态查找查找时会有插入或删除操作,...
  • 查找时,首先在索引表中进行查找,确定要找到数据元素所在的块。然后,在相应的块中采用顺序查找,即可找到对应的数据元素。在这种分块查找中,查找效率低,空间浪费过大(因为块与块之间必须留有一定的空间进行插入...
  • 查找技术相关总结: 1.顺序查找:(1)如果线性表为无序表(即表中元素的...3.分块查找(又称索引顺序查找):分块有序表结构分为两部分(1)线性表本身采用顺序存储结构(2)在建立一个索引表,在索引表中,对线性
  • 一顺序查找 Linear search又称线性查找 顺序查找 查找过程从表的一端开始逐个进行记录的关键字和给 定值的比较 算法描述 算法的实现 讨论 查不到怎么办 折半查找举例 讨论 若关键字不在表中怎样得知和停止 三分块...
  • 查找算法:分块查找

    2020-10-13 19:59:29
    分块查找就是将顺序表(主表)分成若干个子表,然后为每个子表建立一个索引表,利用索引在其中一个表中查找。 两部分: 索引表:存储顺序表的每个子表的开始索引和最大值。 顺序表:主表所有数据存放的位置。 ...
  • 查找

    2016-03-23 12:48:34
    一、查找的基本概念  1、查找就是查找某个特定的元素是否在查找表中,或者查那个元素的属性,或者忘查找表中进行插入...就是增加一个索引表,里面的每个元素代表查找表中一个范围。每个元素包含两个域,一个说明那
  • 查找之分块查找

    2018-04-26 22:26:24
    再建一个索引表,索引表中的元素含有各块的最大关键字和各块中第一个元素的地址,索引表按关键字有序排列。 示意图 查找分2步 a. 首先在索引表中进行折半查找,确定元素在那个块间(折半查找可以查看前面所写),...

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 289
精华内容 115
关键字:

在索引顺序表中查找一个元素