公司网站怎么做分录,网站运营推广方案设计,使用织梦系统建设网站教程,制作电子印章#x1f31e; “清醒 自律 知进退#xff01;” 查找 #x1f388;1.查找的相关概念#x1f388;2.静态查找表#x1f52d;2.1静态查找表的类定义#x1f52d;2.2顺序查找#x1f52d;2.3二分查找#x1f50e;二分查找例题 #x1f52d;2.4分块查找#x1f52d;2.5三… “清醒 自律 知进退” 查找 1.查找的相关概念2.静态查找表2.1静态查找表的类定义2.2顺序查找2.3二分查找二分查找例题 2.4分块查找2.5三种算法的比较分析 查找是在一些有序的或无序的数据元素中通过一定的方法找出与给定关键字相同的数据元素的过程即根据给定的某个值在查找表中确定一个关键字等于给定的记录或数据元素。查找是信息处理科学中十分重要的操作。 1.查找的相关概念
查找表是同一类型数据元素或记录构成的集合与4种数据关系中的集合结构对应。由于集合中数据元素之间存在着完全松散的关系。因此查找表往往要借助其他数据结构来实现相关算法。关键字是可以标识一个数据元素或记录的数据项关键字的值被称之为键值。若关键字可以唯一地标识一条记录则称此关键字为主关键字。查找是根据给定的某个值在查找表中确定一个关键字等于给定值的记录或数据元素的过程。若在查找表中存在与给定值匹配的记录则查找成功此时查找的结果可以是整个记录的信息或查找成功标记等。若在查找表中不存在与给定值匹配的记录则查找不成功此时查找结果可以是不成功标记或将被查找记录插入查找表。静态查找表是仅对表进行查找操作而不进行插入和删除操作的查找表。静态查找在查找不成功时只返回一个不成功标志不改变查找表因此表中数据元素的数量不会发生变化。动态查找表是在查找的同时对表进行插入和删除操作的表。动态查找在查找不成功时需要将被查找的记录插入查找表因此表中数据元素的数量可能会发生变化。
2.静态查找表
2.1静态查找表的类定义
#define _CRT_SECURE_NO_WARNINGS 1
#define Max 100
#include iostream
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef int IndexType;
typedef struct
{KeyType key;//KeyType为关键字数据类型InfoType otherinfo;//其他域
}SElemType;
class StaticSearchtable
{
private:SElemType* elem;int length;
public:StaticSearchtable()//构造函数0位留空{elem new SElemType[Max 1];length 0;}~StaticSearchtable()//析构函数释放存储空间{delete[]elem;length 0;}void Create(int n)//创建n个元素的顺序表{for (int i 0; i n; i){cin elem[i].key elem[i].otherinfo;}length n;}int SqSearch(KeyType key);//顺表表查找值等于key的关键字int BinSearch(KeyType key);//二分查找值等于key的关键字int IndexSearch(IndexType index[Max], KeyType key, int b);//分块查找值等于key的关键字b为块数
};2.2顺序查找
顺序查找的主要思想
设立哨兵位elem[0].keykey,其作用是防止扫描溢出。从表的末端开始向左扫描线性表依次将扫描到的关键字值和给定值key进行比较若找到关键字则查找成功返回该关键字在顺序表中的下标否则查找失败返回0.
int StaticSearchtable::SqSearch(KeyType key)
{elem[0].key key;//哨兵位int i 0;for (i length; elem[i].key ! key; i--)//从末端开始向左扫描{;//空语句}return i;
}顺序查找分析
2.3二分查找 二分查找又称折半查找它是一种效率较高的查找方法。二分查找要求线性表采用顺序存储结构且元素有序。类似于顺序查找方法在存储元素时数组元素第0位留空。 二分查找的主要思想是每次将待查找记录所在的区间缩小一 半。具体步骤如下设elem[low..high]是当前的查找区间首先确定中间点位置mid [(lowhigh)/2],然后将待查元素的关键字key值与elem[mid].key比较初始时令low1,highlength
mid [(lowhigh)/2]若keyelem[mid].key,则查找成功返回mid,即该元素在顺序表中的下标。若keyelem[mid].key,则high mid-1若keyelem[mid].key,则low mid1重复上述操作直至lowhigh时查找失败此时返回0
int StaticSearchtable::BinSearch(KeyType key)
{int low 1,high length;int mid;while (low high){mid (low high) / 2;if (key elem[mid].key)return mid;else if (key elem[mid].key)high mid - 1;elselow mid 1;}return 0;
}✅二分查找过程可用二叉树来描述在构造二叉树的过程中把当前查找区间的中点位置上的元素作为树根左子表和右子表的元素分别作为根的左子树和右子树。由此递归得到二叉树通常称描述查找的过程的二叉树为判定树。判定树的形态与表中个数n相关与输入示例中的key值无关。 例如要找到15个数据元素的有序表中的第8个元素仅需比较1次找到第4和第12个元素需要比较2次找到第2,610和14个元素需要比较3次找到第1,35,79,11,13和15个元素需要比较4次。其查找过程如图所示树中的每个圆圈结点表示表中一个元素结点中的值表示该元素在表中的位置圆圈结点表示查找成功方框结点表示查找失败。若查找失败则比较过程是一条从判定树的根到某结点的路径所需关键字比较次数是该路径上圆圈结点的个数。 二分查找分析 判定树为满二叉树有序表元素个数为:n2h-1 1.查找成功时平均查找长度 2.查找不成功时平均查找长度h 判定树为非满二叉树
1.查找成功时平均查找长度 2.查找不成功时平均查找长度
二分查找例题 例给定18个元素的有序表 {2,58,10,15,40,42,55,66,70,72,75,80,88,90,100,108,200}采用二分查找试问 1.查找长度为4和5的元素个数分别有多少个 2.若要查找值为15的数据元素要经过多少次比较依次与哪些元素进行比较 3.在查找概率相等的情况下计算查找成功和查找不成功的平均查找长度。 解第一问可以直接数第四行和第五行元素的个数分别是8和3. 第二问数这条路径圆圈结点的个数为比较次数圆圈内的值为比较的数 因此我们需要进行4次比较依次与表中的元素66,10,40,15比较。 第三问在查找概率相等的情况下查找成功的平均查找长度为 1122438435/1832/9。 查找不成功的平均查找长度为4135*6/1982/19 2.4分块查找 分块查找又称索引顺序查找它是顺序表查找的一种改进方法其性能介于顺序查找和二分查找之间。在索引查找方法中除存储表本身以外还需存储一个索引表。存储方法如下
将线性表elem[1..n]均分为b块前b-1块中元素个数为s[n/b]最后一块即b块的元素个数小于等于s.每一块中的关键字不一定有序但前一块中的最大关键字小于后一块中的最小关键字即块内无序块间有序。抽取各块的最大关键字及起始位置构成一个索引表index[0..b-1],即index[i]0ib-1中存放第i块的最大关键字和该块在表中的初始位置。
索引表的数据类型定义
typedef struct
{KeyType key;int link;
}IndexType;分块查找的算法
int StaticSearchtable::IndexSearch(IndexType index[Max], KeyType key, int b)
{//b为块数int low 0, high b - 1, mid, i, s;if (length % b 0)s length / b;elses length / b 1;while (low high){mid (low high) / 2;if (index[mid].key key)high mid - 1;elselow mid 1;}//在索引表high1快对应的线性表中顺序查找keyi index[high 1].link;while (i index[high 1].link s - 1 elem[i].key ! key){i;}if (i index[high 1].link s - 1)return i;//查找成功返回该元素的下标elsereturn 0;//查找失败返回0
}2.5三种算法的比较分析
顺序查找的时间复杂度最差二分查找的时间复杂度最好分块查找的时间复杂度介于两种之间。分块查找需要增加索引数据的空间空间复杂度最大。顺序查找对表没有特殊要求。分块查找的数据块之间在物理上可以不连续插入、删除数据只涉及对应的块但增加了索引的维护。二分查找要求表有序若表的元素插入与删除很频繁则维持有序的工作量极大。在表不大的时候一般使用顺序查找。
运行示例
#define _CRT_SECURE_NO_WARNINGS 1
#define Max 100
#include iostream
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef struct
{KeyType key;//KeyType为关键字数据类型InfoType otherinfo;//其他域
}SElemType;
typedef struct
{KeyType key;int link;
}IndexType;
class StaticSearchtable
{
private:SElemType* elem;int length;
public:StaticSearchtable()//构造函数0位留空{elem new SElemType[Max 1];length 0;}~StaticSearchtable()//析构函数释放存储空间{delete[]elem;length 0;}void Create(int n)//创建n个元素的顺序表{for (int i 0; i n; i){cout 输入第 i1 个元素的值和下标;cin elem[i].key elem[i].otherinfo;}length n;}int SqSearch(KeyType key);//顺表表查找值等于key的关键字int BinSearch(KeyType key);//二分查找值等于key的关键字int IndexSearch(IndexType index[Max], KeyType key, int b);//分块查找值等于key的关键字b为块数
};
int StaticSearchtable::SqSearch(KeyType key)
{elem[0].key key;//哨兵位int i 0;for (i length; elem[i].key ! key; i--)//从末端开始向左扫描{;//空语句}if (i 0)cout 该数所在顺序表中的下标为: i endl;elsecout 未找到 endl;return 0;
}
int StaticSearchtable::BinSearch(KeyType key)
{int low 1, high length;int mid;while (low high){mid (low high) / 2;if (key elem[mid].key){cout 该数经二分查找下标为 mid endl;break;}else if (key elem[mid].key)high mid - 1;elselow mid 1;}if(lowhigh)cout 未找到 endl;return 0;
}
int StaticSearchtable::IndexSearch(IndexType index[Max], KeyType key, int b)
{//b为块数int low 0, high b - 1, mid, i, s;if (length % b 0)s length / b;elses length / b 1;while (low high){mid (low high) / 2;if (index[mid].key key)high mid - 1;elselow mid 1;}//在索引表high1快对应的线性表中顺序查找keyi index[high 1].link;while (i index[high 1].link s - 1 elem[i].key ! key){i;}if (i index[high 1].link s - 1)return i;//查找成功返回该元素的下标elsereturn 0;//查找失败返回0
}
int main()
{StaticSearchtable a;a.Create(8);a.SqSearch(6);a.BinSearch(7);return 0;
}好啦关于静态查找表的知识到这里就先结束啦后期会继续更新学习数据结构与算法的相关知识欢迎大家持续关注、点赞和评论❤️❤️❤️
