精华内容
下载资源
问答
  • 1.查找表可分为两类: (1)静态查找表:仅做查询和检索操作的查找表。 (2)动态查找表:在查询之后,还需要将查询结果为不在查找表中的数据元素插入到查找表中;或者,从查找表中删除其查询结果为在查找表中的...

    1.查找表可分为两类:

    (1)静态查找表:仅做查询和检索操作的查找表。

    (2)动态查找表:在查询之后,还需要将查询结果为不在查找表中的数据元素插入到查找表中;或者,从查找表中删除其查询结果为在查找表中的数据元素。

    2.查找的方法取决于查找表的结构:由于查找表中的数据元素之间不存在明显的组织规律,因此不便于查找。为了提高查找效率,需要在查找表中的元素之间人为地附加某种确定的关系,用另外一种结构来表示查找表。

    3.顺序查找表:以顺序表或线性链表表示静态查找表,假设数组0号单元留空。算法如下:

    int location(SqList L, ElemType &elem)

    {

      i = 1;

      p = L.elem;

      while (i <= L.length && *(p++)!= e)

      {

        i++;

      }

      if (i <= L.length)

      {

        return i;

      } else

      {

        return 0;

      }

    }

    此算法每次循环都要判断数组下标是否越界,改进方法:加入哨兵,将目标值赋给数组下标为0的元素,并从后向前查找。改进后算法如下:

    int Search_Seq(SSTable ST, KeyType kval) //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到,则函数值为该元素在表中的位置,否则为0。

    {

      ST.elem[0].key = kval; //设置哨兵

      for (i = ST.length; ST.elem[i].key != kval; i--) //从后往前找,找不到则返回0

      {

      }

      return 0;

    }

    4.顺序表查找的平均查找长度为:(n+1)/2。

    5.上述顺序查找表的查找算法简单,但平均查找长度较大,不适用于表长较大的查找表。若以有序表表示静态查找表,则查找过程可以基于折半进行。算法如下:

    int Search_Bin(SSTable ST, KeyType kval)

    {

      low = 1; 

      high = ST.length; //置区间初值

      while (low <= high)

      {

        mid = (low + high) / 2;

        if (kval == ST.elem[mid].key)

        {

          return mid; //找到待查元素

        } else if (kval < ST.elem[mid].key)

        {

          high = mid - 1; //继续在前半区间查找

        } else

        {

          low = mid + 1; //继续在后半区间查找

        }

      }

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

    } //表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同

    6.几种查找表的时间复杂度:

    (1)从查找性能看,最好情况能达到O(logn),此时要求表有序;

    (2)从插入和删除性能看,最好情况能达到O(1),此时要求存储结构是链表。

    7.二叉排序树(二叉查找树):

    (1)定义:二叉排序树或者是一棵空树;或者是具有如下特性的二叉树:

    ①若它的左子树不空,则左子树上所有结点的值均小于根结点的值;

    ②若它的右子树不空,则右子树上所有的结点值均大于根结点的值;

    ③它的左、右子树也都分别是二叉排序树(对二叉排序顺进行中序遍历得到的是一个有序序列)。

    (2)通常取二叉链表作为二叉排序树的存储结构。

    typedef struct BiTNode //结点结构

    {

      TElemType data;

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

    } BiTNode, *BiTree;

    (3)二叉排序树的查找算法:若二叉排序树为空,则查找不成功;否则:

    ①若给定值等于根结点的关键字,则查找成功;

    ②若给定值小于根结点的关键字,则继续在左子树上进行查找;

    ③若给定值大于根结点的关键字,则继续在右子树上进行查找。

    (4)从上述查找过程可见,在查找过程中,生成了一条查找路径:

    ①查找成功:从根结点出发,沿着左分支或右分支逐层向下直至关键字等于给定值的结点;

    ②查找不成功:从根结点出发,沿着左分支或右分支逐层向下直至指针指向空树为止。

    (5)二叉排序树中递归地查找关键字算法:

    Status SearchBST(BiTree T, KeyType kval, BiTree f, BiTree &p) //在根指针T所指二叉排序树中递归地查找其关键字等于kval的数据元素,若查找成功,则返回指针p指向该数据元素的结点,并返回函数值为TRUE;否则表明查找不成功,返回FALSE,指针f指向当前访问结点的双亲,其初始调用值为NULL(f用于二叉排序树的插入操作)

    {

      if (!T)

      {

        p = f;

        return FALSE; //查找不成功

      } else if (kval == T->data.key)

      {

        p = T;

        return TRUE;

      } else if (kval < T->data.key)

      {

        return SearchBST(T->lchild, kval, T, p); //在左子树中继续查找

      } else

      {

        return SearchBST(T->rchild, kval, T, p); //在右子树中继续查找

      }

    }

    (6)二叉排序树的插入算法:根据动态查找表的定义,插入操作在查找不成功时才进行;若二叉排序树为空树,则新插入的结点为新的根结点;否则,新插入的结点必为一个新的叶子结点,其插入位置由查找过程得到。算法如下:

    Status Insert BST(BiTree &T, ElemType e) //当二叉排序树中不存在关键字等于e.key的数据元素时,插入元素值为e的结点,并返回TRUE;否则,不进行插入并返回FALSE

    {

      if (!SearchBST(T, e.key, NULL, p))

      {

        s = new BiTNode; //为新结点分配空间

        s->data = e;

        s->lchild = s->rchild = NULL;

        if (!p)

        {

          T = s; //插入s为新的根结点

        } else if (e.key < p->data.key)

        {

          p->lchild = s; //插入*s为*p的左孩子

        } else

        {

          p->rchild = s; //插入*s为*p的右孩子

        }

        return TRUE; //插入成功

      } else

      {

        return FALSE;

      }

    (7)二叉排序树的删除算法:和插入相反,删除在查找成功之后进行,并且要求在删除二叉排序树上某个结点之后,仍然保持二叉排序树的特性。可分三种情况讨论:

    ①被删除的结点是叶子:其双亲结点中相应指针域的值改为空;

    ②被删除的结点只有左子树或者只有右子树:其双亲结点的相应指针域的值改为指向被删除结点的左子树或右子树;

    ③被删除的结点既有左子树,也有右子树:以其前驱结点替换该结点,再删除该前驱结点;或者以其后继节点替换该结点,再删除该后继结点。

    算法描述如下:

    Status DeleteBST(BiTree &T, KeyType kval) //若二叉排序树T中存在其关键字等于kval的数据元素,则删除该数据元素结点,并返回函数值TRUE,否则返回函数值FALSE

    {

      if (!T)

      {

        return FALSE; //不存在关键字等于kval的数据元素

      } else

      {

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

        {

          Delete(T);

          return TRUE; //找到关键字等于key的数据元素

        } else if (kval < T->data.key)

        {

          return DeleteBST(T->lchild, kval); //继续在左子树中进行查找

        } else

        {

          return DeleteBST(T->rchild, kval); //继续在右子树中进行查找

        }

      }

    }

    void Delete(BiTree &p) //从二叉排序树中删除结点p,并重接它的左子树或右子树

    {

      if (!p->rchild)

      {

        p = p->lchild;

      } else if (!p->lchild)

      {

        p = p->rchild;

      } else

      {

        tmp = p->left;

        while (tmp->right)

        {

          tmp = tmp->right;

        }

        p->data = tmp->data;

        Delete(tmp);

      }

    }

    (8)查找性能分析:对于每一棵特定的二叉排序树,均可按照平均查找长度的定义来求它ASL,由值相同的n个关键字构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同,甚至可能差别很大。

    8.平衡二叉树:平衡二叉树是二叉查找树的另一种形式,特点为树中每个结点的左、右子树深度之差的绝对值不大于1。

    (1)构造平衡二叉(查找)树的方法是:在插入过程中,采用平衡旋转技术(LL、RR、LR、RL)。

    (2)当发生不平衡的情况,找到最小不平衡子树进行调整:

    ①LL型:整体向右旋转一次;

    ②RR型:整体向左旋转一次;

    ③LR型:底部向左旋转一次,变成LL型,再整体向右旋转一次;

    ④RL型:底部向右旋转一次,变成RR型,再整体向左旋转一次。

    例如:依次插入的关键字为5, 4, 2, 8, 6, 9

     

    (3)平衡二叉树的查找性能分析:在平衡树上进行查找的过程和二叉排序树相同,因此查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。因此,在平衡二叉树上进行查找时,查找过程中和给定值进行比较的关键字的个数和log(n)相当(最坏情况等效于顺序表查找性能和n相当)。

    9.B树:

    (1)定义:B树是一种平衡的多路查找树。在m阶的B树上,每个非终端结点可能含有:

    ①n个关键字Ki(1 ≤ i ≤ n,n < m);

    ②n个指向记录的指针Di(1 ≤ i ≤ n);

    ③n+1个指向子树的指针Ai(0 ≤ i ≤ n);

    例如,下图为一棵B树:

    (2)查找过程:

    (3)插入操作:

    (4)删除操作:

    (5)查找性能分析:

    10.B+树:

    转载于:https://www.cnblogs.com/hou36/p/9922841.html

    展开全文
  • 静态表查找

    2017-03-03 10:19:03
    静态查找表是指表结构不是在查询过程中动态生成的,它可分为 顺序查找(无序)、二分查找(有序)、分块查找(索引顺序查找)。 1.顺序查找 时间复杂度(O(n)) public static int seqSearch(int[] array, int key){...

    静态查找表是指表结构不是在查询过程中动态生成的,它可分为 顺序查找(无序)、二分查找(有序)、分块查找(索引顺序查找)。

    1.顺序查找

    时间复杂度(O(n))
    public static int seqSearch(int[] array, int key){
    	for(int i = 0; i < array.length; i++){
    		if(array[i] == key)
    			return i;		
    	}
    	return -1;
    }

    2.二分查找

    时间复杂度(O(log2n))
    //非递归实现
    public static int binSearch(int[] array, int key){
    	int low = 0;
    	int high = array.length - 1;
    	int mid = 0;
    	while(low <= high){
    		mid = (low + high)/2;
    		if(key == array[mid])
    			return mid;
    		else if(key > array[mid])
    			low = mid + 1;
    		else
    			high = mid - 1;	
    	}
    	return -1;
    }
    //递归实现
    public static int binarySearch(int key, int[] array, int low, int high){
    	if(low > high)
    		return -1;
    	if(low <= high){
    		int mid = (low >>> 1) + (high >>> 1);
    		if(key == array[mid])
    			return mid;
    		else if(key > array[mid])
    			low = mid + 1;
    		else
    			high = mid - 1;
    	}
    	return binarySearch(key, array, low, high);
    }

    3.分块查找

    时间复杂度介于顺序查找和二分查找之间

    分块查找又称索引顺序查找,它是顺序查找的一种改进方法,性能优于顺序查找。

    方法描述:

    将n个数据元素“按块有序”划分为m块(一般块的长度均匀,最后一块可以不满)(m<=n),每一块中的节点不必有序,但块与块之间必须“按块有序”;即第一块中的关键字必须小于(或者大于)第二块中的关键字,第二块中的关键字必须小于(或者大于)第三块中的关键字,构造索引表,索引表按关键字有序排列。

    如下图所示:


    图示为一个索引顺序表,其中包括三个块,第一个块的其实地址为0,快内最大关键字为25;第二个块的其实地址为5,块内最大关键字为58;第三个块的起始地址为10,块内最大关键字为88。

    分块查找基本步骤:

    Step1、先选取各块中最大关键字构成一个索引表;

    Step2、查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。




    展开全文
  • 查找表可分为两类 ;在各种系统软件或应用软件中查;次关键字Secondary ;此表为一个查找表表中每一行为;如何进行查找 ;总之 查;内查找和外查找 若整个查找;对一个含n个数据元素的表查找;9.1 静态查找表9.2 动;9.1 静态...
  • 1查询某个特定的数据元素是否在查找表中2检索某个特定的数据元素的各种属性3在查找表中插入一个数据元素4从查找表中删去某个数据元素查找表可分为两类:静态查找表仅作查询和检索操作的查找表动态查找表有时在查询...
  • 数据结构之查找运算

    2019-12-18 20:09:24
    查找表可分为两类 静态查找表 仅作查询和检索操作的查找表。 动态查找表 有时在查询之后,还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中;或者,从查找表中删除其“查询”结果为“在查找表中”...

    查找

    • 查找表可分为两类
    1. 静态查找表
      仅作查询和检索操作的查找表。
    2. 动态查找表
      有时在查询之后,还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中;或者,从查找表中删除其“查询”结果为“在查找表中”的数据元素。
    • 关键字
      是数据元素(或记录)中某个数据项的值,用以标识(识别)一个数据元素(或记录)。
      若此关键字可以识别唯一的一个记录,则称之谓“主关键字”。
      若此关键字能识别若干记录,则称
      之谓“次关键字”。

    线性表的查找

    顺序查找(都是从后往前找)

    顺序查找方法既适用于线性表的顺序存储结构,又适用于线性表的链式存储结构。(无序
    时间复杂度为O(n)。
    在不等概率查找的情况下,ASLss 在
    Pn≥Pn-1≥···≥P2≥P1时取极小值
    若查找概率无法事先测定,则查找过程采取的改进办法是,在每次查找之后,将刚刚查找到的记录直接移至表尾的位置上。

    折半查找(二分查找)

    折半查找要求线性表必须才用顺序存储结构,而且表中元素按关键字有序排列。
    时间复杂度为O(log2 n)。
    算法步骤:

    1. 置查找区间初值,low为1,high为表长。
    2. 当low小于等于high时,循环执行以下操作:
    • mid取值为low和high的中间值;
    • 将给定值key和中间位置记录的关键字进行比较,若相等则查找成功,返回中间位置mid;
    • 若不相等则利用中间位置记录将表分为前后两个字表。如果key比中间位置记录的关键字小,则high取mid-1,否则low取为mid+1。
    1. 循环结束,说明查找区间为空,则查找失败,返回0。

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

    索引顺序表=索引+顺序表,一般情况下,索引是一个有序表
    分块有序,即分成若干子表,要求每个子表中的数值都比后一块中数值小(但子表内部未必有序)。
    然后将各子表中的最大关键字构成一个索引表,表中还要包含每个子表的起始地址(即头指针)
    分块查找过程:

    1. 对索引表使用折半查找法(因为索引表是有序表);
    2. 确定了待查关键字所在的子表后,在子表内采用顺序查找法(因为各子表内部是无序表);

    线性表查找的比较

    顺序查找 折半查找 分块查找
    查找时间复杂度 O(n) O(log2n) 与确定所在块的查找方法有关
    特点 算法简单,对表结构无任何要求,但查找效率较低 对表结构要求较高,查找效率较高 对表结构有一定的要求,查找效率介于折半查找和顺序查找之间
    适用情况 任何结构的线性表,不经常做插入和删除 有序的顺序表,不经常做插入和删除 块间有序、块内无序的顺序表,经常做插入和删除

    数表的查找

    • 这里暂时不做过多解释… …

    哈希表(散列表的查找)

    • 对于动态查找而言,(1)表长不确定;(2)在设计查找表时,只知道关键字所属范围,而不知道确切的关键字。
    • 因此在一般情况下,需要关键字于记录在表中的存储位置之间建立一个函数关系,以 f(key) 作为关键字为 key 的记录在表中的位置,通常称这个函数 f(key) 为哈希函数(散列函数)。
    • 简单地说,哈希表(散列表)是基于哈希函数(散列函数)建立的一种查找表。
    1. 哈希表的定义:
      根据设定的哈希函数 H(key) 和所选中的处理冲突的方法,将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上,并以关键字在地址集中的“象”作为相应记录在表中的存储位置,如此构造所得的查找表称之为“哈希表

    2. 散列函数的构造方法

    • a. 直接定址法
      哈希函数为关键字的线性函数
      H(key) = key 或者
      H(key) = a * key + b
    • b. 数字分析法
      假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us),分析关键字集中的全体, 并从中提取分布均匀的若干位或它们的组合作为地址。
      此方法仅适合于:能预先估计出全体关键字的每一位上各种数字出现的频度。
    • c.平方取中法
      以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ,同时平方值的中间各位又能受到整个关键字中各位的影响。
      此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。
    • d. 折叠法
      将关键字分割成若干部分,然后取它们的叠加和为哈希地址。有两种叠加处理的方法:移位叠加间界叠加
      此方法适合于: 适合于散列地址的位数较少,而关键字的位数较多,且难于直接从关键字中找到取值较为分散的几位。
    • e.除留余数法(最常用)
      设定哈希函数为:
      H(key) = key MOD p
      其中, p≤m (表长) 并且p且为质数
    • f.随机数法
      设定哈希函数为:
      H(key) = Random(key)
      其中,Random 为伪随机函数
      通常,此方法用于对长度不等的关键字构造哈希函数。
    1. 处理冲突的方法
    • a.开放地址法
      a. 线性探测再散列 di = 1,2,3,…,m-1 且di=i
      b.平方探测再散列 di = 12, -12, 22, -22, …,+k2, -k2(K<=m/2)
      c.随机探测再散列 di 是一组伪随机数列 或者
      di=i×H2(key) (又称双散列函数探测)
      线性探测法的特点
      优点:只要哈希表未被填满,保证能找到一个空地址单元存放有冲突的元素。
      缺点:会产生“二次聚集”现象,降低查找效率.
      二次探测法和伪随机探测法的的特点
      优点: 可以避免“二次聚集”现象
      缺点:不能保证一定找到不发生冲突的地址。
      开放地址法建立哈希表的步骤
      step1 取数据元素的关键字key,计算其哈希函数值(地址)。若该地址对应的存储 空间还没有被占用,则将该元素存入;否则执行step2解决冲突。
      step2 根据选择的冲突处理方法,计算关键字key的下一个存储地址。若下一个存储地址仍被占用,则继续执行step2,直到找 到能用的存储地址为止。

    • b.链地址法
      相同哈希地址的记录链成一单链表,m个哈希地址就设m个单链表,然后用用一个数组将m个单链表的表头指针存储起来,形成一个动态的结构
      链地址法建立哈希表的步骤:
      step1 取数据元素的关键字key,计算其哈希函数值(地址)。若该地址对应的链表为空,则将该元素插入此链表;否则执行step2解决冲突。
      step2 根据选择的冲突处理方法,若该地址对应的链表为不为空,则利用链表的前插法或后插法将该元素插入此链表。

    • c.两种处理冲突方法的比较

    开放地址法 链地址法
    空间 无指针域,存储效率较高 附加指针域,存储效率较低
    时间 查找方面:有二次聚集现象,查找效率较低;插入和删除方面:不易实现 查找方面:无二次聚集现象,查找效率较高
    适用情况 表的大小固定,适于表长无变化的情况 结点动态生成,适于表长经常变化得情况
    1. 哈希表的查找
      查找过程和造表过程一致。假设采用开放定址处理冲突,则查找过程为:
      a.对于给定值 K, 计算哈希地址 i = H(K)
      b.若 r[i] = NULL 则查找不成功
      c.若 r[i].key = K 则查找成功
      d.否则 “求下一地址 Hi” ,直至 r[Hi] = NULL (查找不成功)或 r[Hi].key = K (查找成功) 为止。
    • 一般情况下,可以认为选用的哈希函数是“均匀”的,则在讨论ASL时,可以不考虑它的因素。因此,哈希表的ASL是处理冲突方法和装载因子的函数。
    展开全文
  • 索引的顺序查找

    2021-04-25 12:57:34
    将线索中数据按关键字分为若干块(块按升序、降序排序) 对每块建立索引项,每一个索引项均包含: 关键字项(该块的最大、最小关键字) 指针项(记录该块第一个数据在线索中的位置) 将所有索引项组成索引...

    索引表的顺序查找

    基本策略

    • 采用建立“目录”的形式,先查找目录,然后根据目录将需要的数据块读入内存,从而实现只需先对小部分数据进行查询,提高查找效率的效果

    索引表的建立

    1. 将线索表中数据按关键字分为若干块(块可按升序、降序排序)
    2. 对每块建立索引项,每一个索引项均包含:
      1. 关键字项(该块的最大、最小关键字)
      2. 指针项(记录该块第一个数据在线索表中的位置)
    3. 将所有索引项组成索引表

    索引表的查找

    1. 查找目录 (根据索引表的关键字项查找记录所在块;根据指针项确定所在块的第一个记录的物理地址)
    2. 查找数据(在块内部根据关键字查找记录的详细信息)

    实例分析

    在这里插入图片描述

    算法分析

    以查找关键字为 38的数据为例:

    • 在索引表中查询,定位关键字为38的数据元素在索引表的第二块中
    • 从线索表的第七个数据开始遍历,直到索引表第二块遍历结束(>12)
    • 如果没有找到,则查找失败,否则,查找成功

    算法实现(c语言)

    • 定义索引项、索引表

      #define BLOCK_NUMBER 3
      
      /*
      * Struct: IndexNode
      * Description: 索引表的索引项
      * Member: 
      *			data: 该块中最大关键字
      *			link: 该块第一个记录在表中的位置
      */
      typedef struct IndexNode
      {
      	int data;	//数据
      	int link;	//指针
      }IndexNode;
      
      //索引表
      IndexNode indextable[BLOCK_NUMBER];
      
    • 建立索引表

      #define BLOCK_NUMBER 3
      #define BLOCK_LENGTH 6
      
      /*
      * Function: IndexTable
      * Description: 建立索引表
      * Parameter: 
      			int s[]: 线索表
      			int l: 线索表长度
      			IndexNode indextable[]: 索引表数组
      * Return: void
      */
      void IndexTable(int s[], int l, IndexNode indextable[])
      {
      	int j = 0;
      	for (int i = 0; i < BLOCK_NUMBER; i++)
      	{
      		indextable[i].data = s[j];
      		indextable[i].link = j;
      		for (j; j < indextable[i].link + BLOCK_LENGTH && j < l; j++)
      		{
      			if (s[j] > indextable[i].data)
      			{
      				indextable[i].data = s[j];
      			}
      		}
      	}
      	for (int i = 0; i < BLOCK_NUMBER; i++)
      	{
      		indextable[i].link++;	
      	}
      }
      
    • 线索表的顺序查找

      #define BLOCK_NUMBER 3
      
      /*
      * Function: IndexSequelSearch
      * Description: 顺序表线索查找
      * Parameter: 
      *			int s[]: 线索表
      *			int l: 线索表长度
      *			IndexNode it[]: 索引表
      *			int key: 待查找关键字
      * Return: int
      *			-1: 查找失败
      *			>= 1: 关键字在线索表中的位置
      */
      int IndexSequlSearch(int s[], int l, IndexNode it[], int key)
      {
      	//块间查找
      	int i = 0;
      	while (key > it[i].data && i < BLOCK_NUMBER)
      	{
      		i++;
      		
      	}
      	if (i > BLOCK_NUMBER)
      	{
      		return -1;
      	}
      	else
      	{
      		//在块间顺序查找
      		int j = it[i].link - 1;	//6
      		while (key != s[j] && j < l) 
      		{
      			j++;
      		}
      		if (key == s[j])
      		{
      			return j + 1;
      		}
      		else
      		{
      			return -1;
      		}
      	}
      }
      

    性能分析

    在这里插入图片描述

    算法测试(c语言)

    #include <stdio.h>
    
    #define BLOCK_NUMBER 3
    #define BLOCK_LENGTH 6
    
    /*
    * Struct: IndexNode
    * Description: 索引表的索引项
    * Member: 
    *			data: 该块中最大关键字
    *			link: 该块第一个记录在表中的位置
    */
    typedef struct IndexNode
    {
    	int data;	//数据
    	int link;	//指针
    }IndexNode;
    
    //索引表
    IndexNode indextable[BLOCK_NUMBER];
    
    /*
    * Function: IndexSequelSearch
    * Description: 顺序表线索查找
    * Parameter: 
    *			int s[]: 线索表
    *			int l: 线索表长度
    *			IndexNode it[]: 索引表
    *			int key: 待查找关键字
    * Return: int
    *			-1: 查找失败
    *			>= 1: 关键字在线索表中的位置
    */
    int IndexSequlSearch(int s[], int l, IndexNode it[], int key)
    {
    	//块间查找
    	int i = 0;
    	while (key > it[i].data && i < BLOCK_NUMBER)
    	{
    		i++;
    		
    	}
    	if (i > BLOCK_NUMBER)
    	{
    		return -1;
    	}
    	else
    	{
    		//在块间顺序查找
    		int j = it[i].link - 1;	//6
    		while (key != s[j] && j < l) 
    		{
    			j++;
    		}
    		if (key == s[j])
    		{
    			return j + 1;
    		}
    		else
    		{
    			return -1;
    		}
    	}
    }
    
    /*
    * Function: IndexTable
    * Description: 建立索引表
    * Parameter: 
    			int s[]: 线索表
    			int l: 线索表长度
    			IndexNode indextable[]: 索引表数组
    * Return: void
    */
    void IndexTable(int s[], int l, IndexNode indextable[])
    {
    	int j = 0;
    	for (int i = 0; i < BLOCK_NUMBER; i++)
    	{
    		indextable[i].data = s[j];
    		indextable[i].link = j;
    		for (j; j < indextable[i].link + BLOCK_LENGTH && j < l; j++)
    		{
    			if (s[j] > indextable[i].data)
    			{
    				indextable[i].data = s[j];
    			}
    		}
    	}
    	for (int i = 0; i < BLOCK_NUMBER; i++)
    	{
    		indextable[i].link++;
    	}
    }
    
    /*
    * Function: print
    * Description: 打印查找的数据元素以及其在线索表中的位置
    * Parameter: 
    			int searchNumber 查找的数据元素
    			int index		 IndexSequelSearch函数的返回值
    * Return: void
    */
    void print(int searchNumber, int index)
    {
    	if (index == -1)
    	{
    		printf("查找元素:%d\n", searchNumber);
    		printf("查找失败!\n");
    		printf("------------------------------\n");
    		return;
    	}
    	else
    	{
    		printf("查找元素:%d\n", searchNumber);
    		printf("元素位置:%d\n", index);
    		printf("------------------------------\n");
    		return;
    	}
    }
    
    int main()
    {
    	int s[18] = {22, 12, 13, 8,   9, 20,
    				 33, 42, 44, 38, 24, 48,
    				 60, 58, 74, 49, 86, 53};
    
    	IndexTable(s, 18, indextable);
    
    	printf("线索表:");
    	for (int i = 0; i < 18; i++)
    	{
    		printf("%d ",s[i]);
    	}
    	printf("\n");
    	printf("------------------------------\n");
    
    	int indexNumber1 = 38;
    	int index1 = IndexSequlSearch(s, 18, indextable, indexNumber1);
    	print(indexNumber1, index1);
    
    	int indexNumber2 = 28;
    	int index2 = IndexSequlSearch(s, 18, indextable, indexNumber2);
    	print(indexNumber2, index2);
    
    	return 0;
    }
    

    输出如下
    在这里插入图片描述

    参考资料

    1. 《数据结构与算法》北京大学出版社 2018年版 林劼 刘震 陈端兵 戴波 著
    展开全文
  • 第七章小结--查找

    2019-06-01 22:47:00
    查找表可分为静态查找表和动态查找表,若在查找的同时对表做修改操作则为动态查找表;查找可分为成功和不成功 (2)关键字是数据元素(或记录)中的某个数据项的值,可以用于标识一个数据元素(或记录)。 ...
  • 博客作业05-查找

    2018-05-26 22:30:00
    1.查找表可分为两类: 静态查找: 仅作查询和检索操作的查找表。 动态查找: 有时在查询之后,还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中;(如手机通讯录) 或者,从查找表中删除其“查询”...
  • 通常分为:1—无序线性表的一般查找; 2—对关键字有序的顺序表查找; 优缺点分析: 缺点:当线性表的长过于长时,平均查找长度较大,效率低。 优点:对顺序中数据元素的存储没有要求,顺序存储链式存储均。 ...
  • 数据结构-----查找

    2016-10-15 22:09:46
    第九章 查找 何谓查找表 ?  查找表是由同一类型的数据元素(或记录)构成的集合。  由于“集合”中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的结构。 ...对查找表经常进行的...查找表可分为两类:
  • 查找

    2020-12-28 21:39:53
    查找 一、查找概论 查找表:由同一类型的数据元素(或记录)构成...查找表按照操作方式可分为:静态查找表与动态查找表 静态查找表:只作查找操作的查找表 动态查找表:在查找过程中同时插入查找表中不存在的数据元素
  • 根据对查找表所进行查找操作的不同查找表可分为两类 ? 静态查找表若对查找表只做查找操作则此类查找表是静态查找表 ? 动态查找表若在查找过程中进行插入或删除操作则此类查找表是动态查找表 ;9.1 静态查找表 ...
  • 查询某个特定的数据元素是否在查找表中检索某个特定的数据元素的各种属性在查找表中插入一个数据元素从查找表中删去某个数据元素查找表可分为两类:静态查找表仅作 前两种即查询和检索操作的查找表即检索的前后不会...
  • 索引顺序查找又叫分块查找,它是介于顺序查找和折半查找之间的一种查找方法。折半查找虽然具有很好的性能,但其前提条件是...将查找表分为若干个子表,为每一个子表建立一个索引项存储在索引表中,索引项包括两项内容
  • 分块查找

    2014-03-26 20:49:41
    分块查找(又名索引顺序表查找)  分块查找本质上就是二分...例如:原查找表为:1 4 3 5 7 6 10 9 8,此时将查 找表分为3块,第一个子表为:1 4 3,第二个子表为:5 7 6,第三个子表为:10 9 8,虽然每个子表无序
  • 查找的几个基本概念

    2020-02-26 09:56:59
    1、查找有两种基本形式:静态...根据存储结构的不同,查找方法可分为三大类: ① 顺序表和链表的查找:将给定的K值与查找表中记录的关键字逐个进行比较, 找到要查找的记录; ② 散列表的查找:根据给定的K值直接...
  • 顺序查找

    千次阅读 2018-10-13 23:48:24
    顺序查找通常分为对一般无序线性表的查找和对按关键字有序的顺序查找。 顺序查找的缺点是当n很大时,平均查找长度较大,效率低;优点是对数据元素的存储没有要求,顺序存储和链式存储皆。 一般线性表的顺序...
  • 查找算法 -- 简介 查找(Searching)就是根据给定的某个...查找表按照操作方式可分为: 1.静态查找表(Static Search Table):只做查找操作的查找表。他的主要操作是: 查询某个“特定的”数据元素是否在表中...
  • Python常见查找算法

    2018-09-02 18:50:28
    1.关键字定义 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素。 查找表(Search Table):由同一类型的数据元素构成...2.查找表按照操作方式可分为: ①静态查找表 ...
  • 查找、排序算法整理

    2020-07-09 08:37:06
    静态查找:仅对查找表做查询和检索操作。 动态查找:在查找时包含插入、删除或修改。 还可分为无序查找和有序查找: 无序查找:被查找数列有序无序均可。 有序查找:被查找数列必须为有序数列。典型的有二分查找、...
  • 数据结构--查找

    2021-03-03 21:32:39
    查找表分为:静态查找表、动态查找表。 平均查找长度(ASL):关键字的平均比较次数。 二、线性表的查找 1.顺序查找 静态查找表,表内的元素是无序的 改进: 将key作为监视哨放在头部,当数组较长的时候,能够使...
  • 算法学习笔记18-查找

    2017-08-27 12:05:25
    这里主要讲用于查找的数据结构——查找表(Search Table),可分为两类: 动态查找表 静态查找表 静态查找表对于顺序表或线性链表(有序表),可以用折半查找(二分查找),它的时间复杂度是O(log n),此外还有...
  • 顺序查找

    2017-07-08 17:34:01
    按数据大小来分,查找分为内部查找和外部查找,如果从另一角度分,又可分为静态查找和动态查找。  内部查找:数据量较小的文件,可以一次性全部加载到内存中进行查找。  外部查找:数据量大的文件,无法一次加载...
  • 查找算法 数据结构

    2015-08-03 15:31:12
    查找算法总体分为静态查找,和动态查找,其中静态查找法,不改变查找表结构,动态查找表,可以进行插入和删除操作。 一、查找的基本概念 查找,也称检索,是在大量的数据元素中找到某个特定的数据元素而进行...
  • 查找表按照操作方式可分为: 静态查找表(Static Search Table):只做查找操作的查找表。它的主要操作是: 查询某个“特定的”数据元素是否在表中 检索某个“特定的”数据元素和各种属性 动态查找表(Dynamic ...
  • 数据结构的查找问题

    2018-09-17 19:40:47
    一、 1、查找表,是由同一类型的数据元素(或记录)构成的集合;关键字,key是数据元素中某个...2、查找表按照操作方式可分为静态查找表和动态查找 静态查找表,只作查找操作的查找表,主要操作有(1):查询...
  • 七大查找算法Python

    2019-10-17 18:27:14
    参考链接一、参考链接二 查找算法简介 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素。 查找表(Search Table):由同一类型的数据...查找表按照操作方式可分为: ...
  • 根据操作可分为 静态查找表:只做查找操作的查找表 动态查找表:查找时插入或删除数据的查找表 常见查找方式: 顺序表查找 **方法:**线性表+顺序遍历+等值比较 有序表查找 方法: 线性表+排序+折半查找/插值查找/...
  • DS博客作业07--查找

    2019-06-16 17:26:00
    1.查找,可以分为线性表的查找、树表的查找和哈希表的查找,而线性表则是最简单的查找表,又可分为顺序查找、折半查找和索引存储和分块查找,折半查找在上学期就已经学过了,而且书上的代码看起来没有那么晦涩难懂,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 675
精华内容 270
关键字:

查找表可分为