C/C++: 数据结构之索引查找(分块查找)
2023-12-14 22:50:26
?画图举例:
#include<bits/stdc++.h>
using namespace std;
/**
*
* Author:HackerHao
* Create:2023.12.14
*
*/
typedef struct
{
int Key;
int Link;
}indextype;
//分块查找
int IndexSequelSearch(indextype ls[], int s[], int m, int Key)
//关键字为Key, 索引表为ls[0]--ls[m-1], 顺序表为s, 块长为l,m为顺序表长度
{
int i = 0, j = 0;
//在索引表中顺序查找
while (i < m && Key > ls[i].Key)
i++;
if (i >= m)
return -1; //说明没找到,已经越界,返回-1
else
{
//在顺序表中顺序查找
j = ls[i].Link;
while (Key != s[j] && j - ls[i].Link < m + 1)
j++; //还没有找到
if (Key == s[j])
return j; //找到
else
return -1;
}
}
int main()
{
cout << "请输入索引表的块数" << endl;
int n;
cin >> n;
indextype ls[n];
cout << "请输入每一块中最大的元素和每块的分隔处元素下标: " << endl;
for (int i = 0; i < n; i++)
{
cin >> ls[i].Key >> ls[i].Link;
}
cout << "请输入顺序表的元素个数、各自的值:" << endl;
int cnt = 0;
cin >> cnt; //顺序表元素个数
int SqList[cnt];
for (int i = 0; i < cnt; i++)
cin >> SqList[i]; //各元素值
int key, m = n;
cout << "请输入想要查找到元素:" << endl;
cin >> key;
int u;
u = IndexSequelSearch(ls, SqList, m, key);
if (u != -1)
cout << "查找成功,为第" << u + 1 << "个记录" << endl;
else
cout << "查找失败,不存在!" << endl;
return 0;
}
/* 输入:
4
14 0
34 5
66 10
85 15
20
8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85
*/
文章来源:https://blog.csdn.net/Hacker_Hao/article/details/135004500
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!