|
|
好同学们，大家好，今天呢，我们来为大家介绍一下数据结构当中查找这一部分的内容。那么本我们前面呢？给大家介绍了各种线性和非线性的数据结构，并讨论了这些数据结构的相应运算。那么，而在实际应用中呢？查找运算呢？是非常常见的。面对一些数据量很大的实时数据呢，比如说订票系统，互联网上的信息检索系统等，查找效率呢。
非常重要。那么接下来呢，我们将针对查找运算讨论应该采用何种数据结构，使用什么样的方法，并通过对它们的效率进行分析来比较各种查找算法呢？在不同情况下的优劣。首先我们来看一下，查找它分为了静态查找表和动态查找表。那么，如果在查找的同时对表做修改操作，比如说插入和删除。则称呢，相应的表为动态查找表，否则称之为静态查找表，也就是说动态查找表的表的本身结构呢。
是在查找过程当中生成的，在创建表时，对于点定值，若表中存在与关键字相等的记录。那么则返回查找成功，否则呢，插入与关键字相同的定值的这样一个记录。就是我们的动态查找表和静态查找表。我们的查找表是什么呢？查找表是一类。数据元素构成的集合，也就是说查找表是由同一类型数据元素或记录构成的集合。由于集合中的数据元素之间存在着这样一个完全松散的关系，因此查找表呢，是一种应用。
非常明辨的这样一个结构，可以利用其他的数据结构来实现，比如说我们要介绍的这样一个线性表述及散列表来进行实现。我们的关键字是什么呢？我们的关键字。关键字呢，是我们的数据。元素或记录中某个数据项的值可以用它来标识一个数据元素或记录，若这样的一个关键字呢，可以唯一的标识一个记录。则称此关键字呢为主关键字。否则呢，称用以识别若干记录的关键字为次。关键字当数据元素，只有一个数据项时。
其关键字呢，为该数据元素的值，那么我们对查找表经常进行操作呢，是查询某个特定的数据元素是否在查找表中？或者检索某个特定的数据元素的各种属性，又或者呢，在查找表中呢，插入一个数据元素。或者呢，在查找表中呢，删除某个数据元素。查找表，刚才我们讲过分，为了静态查找表和动态查找表，若在查找的同时对表了做修改插入，
比如说插入和删除这样的相应的表了。称为动态查找表，否则呢，称为静态查找表，比如说我们的静态查找表呢，只是仅做操作这样一个查询和检索的这样一个查找表。而动态调查查表呢，有时在查询中还需要将查询的结果在不在查找表中的数据元素了，插入到查找表中，否则呢。或者从其中呢，删除及查询结果为在查找表中的数据元素，就是我们动态查找表，也就是说动态查找表的表结构本身呢，是在查找过程中动态生成的。
记得创建表时，对于给定值若表中存在有关键字，给等于给定值的记录，则返回查找成功，否则呢，插入关键值等于这样一个定值的，这样一个记录。刚才我们讲过了，关键字是什么呢？关键字是数据元素或记录中某个数据项的值用，它可以标识一个数据元素或者说。标识一个记录。那么这样呢？如果这个关键字可以标识唯一的这样一个记录就称为主关键字，如果这个关键字呢？
能识别若干记录呢？就称为次关键字。所谓的查找是什么呢？查找是根据给定的某个值，在查找表中确定一个其关键字，等于给定值的数据元素或者记录。若在查找表中存在这样一个记录呢，则称查找成功，查找结果呢，是给出整个信息的记录，记录的信息或者只是该记录在查找表中的位置。否则称查找不成功，那么查找结果是给出空值或空记录，比如说查找呢，是根据给定的某个值，
在查找表中呢，确定一个关键字的值，给定其给定值的记录或者数据元素。若表中存在这样一个记录呢，只剩查找成功否？此时查找的结果呢，可以给出整个记录的信息，或者是该记录在查找表中的位置。若表中的不存在与关键字比例给定值相等的这样一个记录呢，则称查找不成功。此时的记结果呢，给出一个空或者说。通记录或者说止站，那么如何进行查找呢？查找的方法呢，
取决于查找表的结构。由于查找表中的数据元素之间呢，不存在明显的组织规律。因此呢，不便于查找。为了提高查找的效率，需要在查找表的数据元素之间人为的附加某种确定的关系。换句话说。用另外一种结构呢来表示，查找表首先我们来看一下静态查找表。我们假设静态查找表的顺序存储结构呢？是这样一个部分type define struct element type element inter。ss，我们首先呢，定义一个数据结构，
那么这样一个。结构体的数据类型定义它的这样一个名称ss stable。那么，定义这样一个数结构体的，这样一个名称，那么这是静态查找表的数据结构，元数据元素的定义类型呢？定义为type。kta bk关键字域以及了其他的域，那么element type定义这样一个结构体变量定义它的这样一个名称element type。还有呢element t element type。那么，对于两个关键字的比较的约定呢？井号。迪拜。
EQ AB.a呢等于b。井号defy l taba小于b。井号define lq aba小于等于b。那么，对字符型关键字的约定呢？井号define EQ。AB.strand可string compare。AB趋反def in型号definl tab string compare AB小于等于小于零。井号define lq AD。stress最compare AB小于等于零。我们的查找表呢，顺序查找表有序查找表，静态查找数表和顺序索引表。
首先我们来看一下顺序，查找表以顺序表和线性链表表示静态查找表。我们来看一下顺序表的查找过程，比如说。我们给定值一=66。给定值一=64，要求了stm的type I=1，那么那么要找这个I是多少？那么怎么样来来找这样一个部分啊？或者说给定值一=66。要求了s GM的I=e，那么要问这个I是多少？那么，我们可以来进行这样一个查询inter locations q list land type符号e。status compare信号compare。
element type,element type.I=1 p=l点element yi小于等于l点嫩时，并且呢，星号compare星pee e取反。I加加if I小于等于嫩s return，i else return in location，那么这里呢？首先呢？我们呢，定义一个I=1，然后呢p=l。element那么定义这样一个指针的，这样一个部分，while I小于等于呃当小于这个长度的时候呢，
并且呢，compare。星号compare。CP加加e。那么，这里啊，为零那么取反了为真？那么比就说我们的逻辑表达式呢，为真那么这个时候呢I加加if I小于等于length return I当最后的结果呢？比如说，当我们的llili小于等于嫩时，并且呢？我们的比较呢，它是为为零的，那么取反了为真，
那么这时候呢，我们进行这样一个I加加的这样一个操作。那么最后呢？如果I呢？它是小于等于lns的，那么说明呢？是这样一个。星t加加e，那么它是等于一的，这样一个部分。那么，它就retire I返回I的值在这一个位，在这个表中的位置，那么else的retire 0，否则呢，
返回一个零值，那么说明呢，就没有找到这个部分。那么，这是我们查找的。这样一个算法，那这是我们查找了这样一个运用的使用的算法，那么这里的y有I小于等于n次，它表示了我们的这I呢？小于我们的表长。那么，星号compare星p加加e，而是表示对这个。元素呢，进行比较，
那么它如果是为零的话呢，那么取反为真，那么为一的话呢，那么取反了，那么就为零。那么，这是我们比较比较的这样一个方式。那么，我们接下来看一下。比如说我们。要找64那么。就找到了它在这当中的这样一个位置，那么I了是这样一个位置的部分，那么我们要找60。那么就没有找到那么返回了I了，
等于零那么找64了返回的I了，等于七那么找60了返回的I了，等于零。接下来我们再看一下另外一个算法int search sts eqs stables TK type。k value在顺序表ST中顺序查找其关键字的等于k的数据元素，若找到了这函数值为。该元素在表中的位置，我作为0 ST element 0 k=k八六设置一个哨兵。for I=ST认识。那么从后了。往前找，那么它的这个。条件表达式呢？条件判断表达式呢？那么就是ST点element ik不等于ky 6，
那么当它不等于这个ky 6的时候呢？那么，继续了减减I从后了往前找，如果它等于这个k八六呢，就停止这样一个循环，最后呢return I返回I的值。那么，这如果找不到的时候呢？I就为零，这是我们在顺序表ST中顺序查找其关键词呢？等于k的数据元素，如果找到了，取函数值了再。该元素中，元素在表中的位置，
否则为零。接下来我们看一下。顺序查找的时间性能查找算法的平均查找长度呢？average research average search learns asl。未确定记录在查找表中的位置，需和给定值进行比较的关键字的个数的期望值asl呢等于I=sigma I=1到。I=1到n pic I，其中呢，n为表长，pi为常热表中di的记录的概率。写sigma I=1的npi=1。ci为查找该记录时和。乘到决定值比较过的关键词的个数，那么对于顺序表而言呢？ci等于n减I加一，
那么它的这样一个asl呢？在等概率查找下了pi等于n分之一。顺序表的查找的平均长度呢，是二分之n加一，这是顺序表查找的平均长度。接下来我们看一下有序表，有序表了上述查找顺序，查找的顺序查找算法比较简单，但平均查找长度较大，不适用于表长较大的查找表。若以有序表表示静态查找表，则查找过程呢，可以基于折半查找。啊，比如说k=64的查找过程，
我们提供进行折半查找no呢，我们设置一个no和hi和me的。no呢，只是查找区间的下界。no呢，只是查找区间的上界。me的等于no的加hi÷2向下区间。取取取这样一个小。它接近这样一个。整数部分的这样一个数的这样这样这样一个数的这样一个部分，比如说我们这里呢，露出一些指向下界。hi指向上界。那么MID呢？指向它们的中间。
然后接下来呢，进行比较。乐b的呢？幂的这样一个中间的这个数呢，比64小那么呢，漏了这个时候呢，变到了64。这个时候MID呢，变得MID。密的呢，变到80，接下来80呢，比64大，那么接下来害呢，变到75那么密的呢，
变到64，那么接下来再进行比较。逆的呢等于64，那么这个时候呢，我们就找到了64在的这样一个位置，也就是说我们的折半查找呢，也称为二分查找，它是一种效率较高的查找算法。那么但是呢，折半查找呢，必须要求线性表必须是顺序存储结构，而且表中关键元素呢，按关键字有序排列。那么，数据小额办查找的查找过程呢？
是从表的中间记录开始，如果给定值和中间记录的关键字相等。则查找成功，否则呢，如果给定值大于或小于中间的关键字记录，则在表中大于或小于中间记录的那一半中查找，如此呢，进行重复，这样一个部分。直到了查找成功或在某一步查找区间为空代表查找失败折半查找，每一次查找呢都会使。范围缩小一半与顺序查找相比呢，那么会提高我们的查找效率，我们为了记录。标记查找过程的每一次查找区间，
那么分别用no和hi来表示，当前查找区间的下界和上界密的表示，区间的中间位置。我们来看一下这个算法int search bins stables kk type k value no=1 high=ST length是初期间初值。while low=high，MID=low。加high÷2 if k，value=sk ST m的m idk return MID返回了代查元素。else if k value小于stm的幂的点k还等于幂的减一继续在，如果呢，我们的要查找的这样一个值呢？比我们这样一个中，比我们比比我们中间的这样一个值呢要小，那么我们继续呢，在前半区间进行查找，
那么把害了。设置为力的减一，否则呢，如果我们要查找的这个值呢，比中间的这个值大。那么，我们就在后半区间进行查找，把漏了设置为密的加一，最后呢？否则，如果没有找到呢，就返回零与二零表示顺序表中的不存在代查元素。我们来看一下这个算法，首先漏等于一，它也等于yes点nos就是表漏了，
指向我们开头的这样一个部分，它也呢，指向结尾的部分，那么这出现曲直。那么，漏小于等于害，当漏小于等于害的时候呢？力的等于。low+high÷2把low的放在low和high中间，if k value=stm的MID点k。如果我们的要查找的值呢，等于我们幂的这样一个值的值的值的时候，那么retire幂的就返回了这个幂的这样一个位置，找到代查元素。else if qr就小于s element element me的k，
那么如果呢？我们代查元素呢？要要查找的这个元素要查找这个数值呢？比我们的幂的这个数值要小的话。那么，我们继续在前半区间进行查找，把害的设为密的减一，否则呢，如果我们的这样一个要查找这样一个数据的值呢？比s比密的值大的话，那么我们在后半区间进行查找，把漏了设置为密的加一。那么，这是说我们查找的方式，那么最后呢？
如果没有找到的话呢？那么就于当我们的肉和害的不满足的时候呢？又小于等于还不满足的时候呢，那么没有找到的时候呢，那么就返回一个return 0表示的顺序表中呢，不存在代查元素，那么这就是我们。折半查找的这样一个方式好，我们接下来再看一下，分析一下折半查找的平均查找长度好吧，我们先看一下具体的情况，假设n=11。那么这个时候呢，我们的判定数呢是六九三一四七十二五八十一，那么一般情况下呢，
表长为n的角板插入了判定数的深度。和含有n个节点的完全二叉树的深度相同，假设n=2的h次方减一，并且查找概率相等，那么asl呢？那么，等于n分之n加一乘，以二n加一减一，当n大于五十的时候呢？可以得到近似结果。log2n+1-1就是它的这样一个。asu它的这样一个。平均查找长度。接下来我们再看一下索引顺序表，分块查找在建立顺序表的同时呢，
建立一个索引，比如说我们的顺序表。那么，这样一个查找，这样一个方式，那么我们的索引，那么我们的索引顺序表呢？那么，这样一个查找的方式，那么？又称为分块查找，这是一种性能介于顺序查找和折瓣查找。之间的一种查找方式，在这样一个查找法中，除了表本身之外，
还需建立一个索引表。那么，建立一个索引表呢？对吧？对于每个子表或者块呢？建立一个索引项，其中包括两项内容，关键字项。和指针项关键字项呢？为其值了，在该指表里的最大关键字。和指针项只是该词表的第一个记录，在表中的位置索引表按关键字有序按表则表了，或者有序了，或者分块有序。
所谓的分块语序呢，是第二个指标中所有记录的关键字，均大于第一个指标中的最大关键字。第三个指标中的所有关键字呢，均大于第二个指标中的最大关键字。那么，这样一个。顺序的这样一个部分，那么索引顺序表呢？就是我们的索引表加顺序表那么最大起始位置了，那么就是21，那么就这样一个最大的取21，这样一个起始的这样一个数值的这样一个部分。那么，这是它的这样一个地址和它的这样一个最大的这样一个关键字的，
这样一个部分，那么我们来看一下它的这样一个。数据结构的这样一个类型type defy struct key type max key int stand stad r。s dad dress.int index item.所以像这是定义一个结构体的这样一个名称hype rt fact ru CT index item。星号element inter STR。index table，这是定义一个数据，数据表那么定义一个这样一个。结构体的名称的部分。那么，索引表的顺序表的查找过程呢？是首先呢，由索引顺索引确定记录所在区间，
然后在顺序表的某个区间内进行查找。那么，索引顺序查找是一个缩小区间的查找过程，那么算我们来看一下它的这样一个算法分析。分块查找成功的asl呢，是asl index SQ asl index，加上asl sub list。那么，设把长度为n的表呢？分为均等的一个词表，每个词表呢？有s的对象，那么则b=n÷s。入射表中，每个对象的查找概率相等，
子表呢，为b分之一。表内子表内各对象呢，为s分之一，则顺序查找成功的a so呢。是asl index cq一二分之b加一，加上二分之s加一等于二分之b加s加一。折半查找快的成功sl呢是asl呢等于log二一加一减一加二分之s加一，那么等于log。二一加。s分之n加上二分之s，那么所以呢，索引查找的asl与表的长度n和子表的对象个数的s有关。那么，我们来对比一下顺序表和有序表的查找性能。
顺序表呢？它的。表的特点呢，是无序的，而有序表呢，它是有序它的表呢，当中呢，是按关键字有序的。那么，顺序表的存储结构呢？那么，是。顺序。顺序的这样一个结构有序表呢？它的存储结构呢？
那么是？顺序的。那么，插插入或者删除的操作呢？易于进行有序表了。需要移动元素顺序表的asl的值呢？比较大，那么有序表的as lsasl呢？它的值比较小。接下来我们看一下动态，查找数表，它的特点呢？是表结构。在查找过程中，动态生成它的要求呢，
是对于给定值k若表中存在其关键值等于k的记录。则查找返回成功，否则呢，插入。关键字等于k的记录。那么，我们之前前面介绍的三种方法呢？都是用线性表作为查找表的，这样一个组织形式，其中呢，折半查找效率较高。但由于折半查找要求，表中记录了按关键字有序排列且不能用链表做存储结构，因此呢，当表的插入或删除比较频繁的时候呢。
为了维护表的有序性，需要移动表格很多记录。这种由移动记录引起的额外时间开销，就会抵消折满查找的这样一个使用的这样一个。实现了这样一个运行，运行方式，运行效率，运行运行运行方面的这样一个。这个类型那么所以呢，线性表的查找呢，更适用于静态查找表。若要对动态查找表进行高效率的查找呢，可以采用特殊的二叉树作为查找表的形式。那么，我们将它们统称为数表，
那么首先呢，我们来看一下二叉排序数。二叉排序数呢，又称为二叉查找数，它是一种呢？对排序和查找都很有用的。这样一个特殊二叉树。那么，我们来看一下二叉排序数的定义。二叉排序数的定义呢？它要么呢，是一棵空树。要么呢？是具有那么这样一些特性的二叉树，比如说它的左指数不空则左指数上的所有结点的值呢，
均小于根结点的值。那么，若它的右指数不空，则右指数上所有结点的值呢？均大于根结点的值，并且呢，它的左右指数呢？分别也是二叉排序数，那么我们来看一下这样一个二叉排二，这样一个这样一个数。50。根节点是50，它的左子数上的值呢？都比50小，它的右子数上的值呢？
都比50大。好吧，我们看一下它左指数的根结点，三十三十的左指数上的值呢，都比它小右指数呢，就比它大那么同样的80呢，它的右指数上的值呢，都比它大。那么这样呢，我们可以看一下其他的这样一个实验的，这样一个应用部分实验应用部分，那么其他的也是脖子粗了，比它小柚子粗了比较大，那么这样呢，我们。
它的左指数不空，那么图纸上的节点的值呢？均小于它根节点的值，右指数不空，右指数上的节点的值呢？均大于它根节点的值，它的左右指数呢？也分别是二叉排序数，所以说这样的一个数呢？是二叉排序数。那么我们再看一下，如果我们加一个66上去加一个66，在这样一个地方，那么这样呢，它就不是二叉海系数。
那么通常呢，我们取二叉链表作为二叉排序数的存储结构，那就是type define struct bbt node。TM的type datas trust BT load信号l child信号rchildbtloadb信号b tree那么定义就这样一个结构体类型，那么它的名称呢？是我们的b。it load.还有我们的滴翠，那么一个结构体，实际上我们结构体变量的指针的这样一个名称，滴滴翠信号滴翠。那么，二叉排序数的查找算法，我们来看一下，若二叉排序数量为空，
则查找不成功，否则呢，若给定。值等于根据点的关键字则查找成功。若给定值小于根据点的关键字，则继续在左指数上进行查找。若给定值大于根据点的关键字，则继续在右指数上进行查找。比如说我们的二叉排序数，我们关键字呢？是50。35。40那么就查找35，90那么就在右子数上进行查找，那找了又是95了，
那么就没有这样一个记录，那么就没有就没有这样一个记录。那么这样呢？我们在查找过程当中呢，生成了一条查找路径，从根结点出发，沿着左分支或右分支呢逐层向下，直至关键字，直到给定值的节点。那么就是说，我们从根结点出发呢？沿着左分支或右分支逐渐向下，这是关键值。给给定值的节点，那么怎么样查找的呢？
比如说我们的二叉排序中的查找呢？呃二呃二叉排序出了为空，那么这个时候呢，调整失败，返回空指针，若二叉树非空，那么就将解径值与根节点的关键字进行比较。若给定值等于根据点的关键字，则查找成功返回根据点地址。若给定值小于根据点的关键字，那么就是递归查找果子数。那么，如果给定值的关键字大于。釉子树的根基点的关大于根基点的关键字则递归查找。柚子树那么所以说。
从根据点出发，沿着左分支或右分支逐层向下，直至指针指向公束位置，那么就是如果。如果呢？我们能。找到关关键字等于给定值的几点，那么查找成功，如果呢？我们指针呢？指向空数为止了，那么查找不成功。啊，比如说我们设关键字等于48，那么我们要查找这个48，
那么我们首先呢，与30进行比较30呢，比48小，那么这个时候我们要在它右子数进行查找。柚子树呢？进行查找之后呢？又比这个柚子树的根据点40大，那么这个时候又要在幼时一四十的柚子树上进行查找。但是呢，这个时候柚子数一四十的柚子数量为空，那么就查就没没有找到这样一个记录，那么就没有查找查查找失败，那没有查找成功。就没有找到这样一个记录，那么如果呢？
我们要查找22，那么怎么办呢？30首先比22大，那么我们要在30的左子数上进行查找。22呢，要比根据这个根据点呢，又比22小，那么又在它的右子上进行查找，25呢，又比它的这样一个根据，这样一个。铁定值的这样一个数值大，那么又要在它左子数上进行查找，那么又要在那么左子数的23又比这样一个22大，那么又要在它的左子数上进行查找。
但是呢，这个时候它的左指是为空，那么就没有查找这样一个记录，那么就查找失败。
|
|
|Archiver|手机版|小黑屋|5432考试网
( 蜀ICP备2022024372号|
川公网安备51152402000101号 )|网站地图
发表于 2024-4-15 09:19:50