索引表的顺序查找

基本策略

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

索引表的建立

将线索表中数据按关键字分为若干块（块可按升序、降序排序）
对每块建立索引项，每一个索引项均包含：
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;	//6while (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;	//6while (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;
}