[C++] 线性表的三种查找方法：顺序查找、折半查找、分块查找（算法实现）

#include <iostream>
using namespace std;
#define MAX 20
typedef int KeyType;
typedef int MaxInt;
typedef struct {
KeyType key;//关键字域
}ElemType;
typedef struct {//顺序表结构类型定义
ElemType *R;//表基址
int length;//表长
}SSTable,*Sqlist;//Sequential Search Table
typedef struct {//定义块的结构
int key;//块中最大值
int start;//块起始地址
int end;//块结束地址
}Index_table;
Index_table index_table[4];
//SSTable ST;//定义顺序表ST
void InitList(Sqlist &ST)
{
ST = (SSTable*)malloc(sizeof(SSTable));//给顺序表分配空间
ST->R = (ElemType*)malloc(MAX*sizeof(ElemType));
ST->length = 0;
}
void CreateList(Sqlist &ST)
{
cout << "请输入线性表长度"<<endl;
cin >> ST->length;
cout << "请输入线性表中元素" << endl;
for (int i = 1; i <= ST->length; i++)
{
cin>>ST->R[i].key ;//赋值
}
}
void Block_Init(Sqlist &ST)
{
int i, j = 0;
for (i = 1; i <= 3; i++)
{
index_table[i].start = j + 1;//确定每个块的起始值
j = j + 1;
index_table[i].end = j + 4;//确定每个块的结束值
j = j + 4;
index_table[i].key = ST->R[j].key;//确定每个块范围中元素的最大值
}
}
int Search_block(Sqlist ST,KeyType key)
{////若成功返回其位置信息，否则返回0
int i, j;
i = 1;
while (i <= 3 && key > index_table[i].key)//确定在哪个块中
i++;
if (i > 3)//大于分块数
return 0;
j = index_table[i].start;//j=块范围的起始值
while (j <= index_table[i].end&&ST->R[j].key != key)//在确定块内进行查找
j++;
if (j > index_table[i].end)
j = 0;
return j;
}
int Search_Seq(Sqlist ST, KeyType key)
{//若成功返回其位置信息，否则返回0
ST->R[0].key = key;
int i;
for ( i = ST->length; ST->R[i].key != key; i--);//这个“；”很重要
return i;
}
int Search_Bin(Sqlist ST, KeyType key)
{
int low = 1,high=ST->length;//设置初始区间
while (low<=high)
{
int mid = (low + high) / 2;
if (ST->R[mid].key == key)return mid;//找到待查元素
else if (key < ST->R[mid].key)//缩小查找空间
high = mid - 1;//继续在前半区查找
else
low = mid + 1;//继续在后半区查找
}//while
return 0;//没找到
}//Search_Bin

int main()
{
//GraphAdjList *GL = (GraphAdjList*)malloc(sizeof(GraphAdjList));
//SSTable *ST1 = (SSTable*)malloc(sizeof(SSTable)); 
Sqlist ST1,ST2,ST3;
char ch1, ch2;
int m, n, k;
int key1, key2, key3;
char u;//起始点
ch1 = 'y';
while (ch1 == 'y')
{
cout << "----------线性表的查找----------" << endl;
cout << "------1.线性表的创建  ------" << endl;
cout << "------2.顺序查找  ------" << endl;
cout << "------3.折半查找  ------" << endl;
cout << "------4.分块查找  ------" << endl;
cout << "------0.退出      ------" << endl;
cout << "------请选择菜单号  ------" << endl;
cin >> ch2;
getchar();
cout << endl;
switch (ch2)
{
case'1':
//顺序表的构建
cout << "创建第一个无序线性表" <<endl;
InitList(ST1);
CreateList(ST1);
cout << "创建第二个有序线性表" << endl;
InitList(ST2);
CreateList(ST2);
cout << "创建第三个线性表(元素为15个)" << endl;
InitList(ST3);
CreateList(ST3);
Block_Init(ST3);
break;
case'2':
//顺序查找
cout << "请输入要查找的关键字key1:" << endl;
cin >> key1;
m = Search_Seq(ST1, key1);
if (m == 0) cout << "没找到" << endl;
else cout << key1 << "的位置为" << m << endl;
break;
case'3':
//折半查找
cout << "请输入要查找的关键字key2" << endl;
cin >> key2;
n = Search_Bin(ST2,key2);
if (n == 0)cout << "没找到" << endl;
else cout << key2 << "的位置为" << n << endl;
break;
case '4':
//分块查找
cout << "请输入要查找的关键字key2" << endl;
cin >> key3;
k = Search_block(ST3, key3);
if (n == 0)cout << "没找到" << endl;
else cout << key3 << "的位置为" << k << endl;
break;
case'0':
ch1 = 'n';
break;
default:
cout << "输入有误" << endl;
}//switch
}//while
return 0;
}