数据结构实战

    返回首页    发表留言
本文作者:李德强
          第二节 索引查找
 
 

        索引表查找顾名思义,就是为现有的查找表建立一张索引表,这张索引表中存放了查找表中的索引内容。通过对索引表中的数据进行查找,快速的确认待查找元素所在的区域,再在这个区域内顺序查找到其所在的位置。当然,建立索引表也是有前提的,首先要为查找表分块,也就是区域,每一个区域中的key值范围不能重复。例如:1~28、29~56、57~88等等。其次,为每个块建立一个索引,记录这个块的最大值和起始位置,并将这些索引按升序排列,组成一个索引表。

#include <stdio.h>

//数组大小
#define A_SIZE (12)
//索引表大小
#define I_SIZE (3)
//索引块大小
#define I_SUB_SIZE (4)

//索引表
typedef struct
{
	//索引快中最大值
	int val;
	//在有序表中的索引
	int ind;
} s_index;

//返回在有序索引表中key值所在的索引,如没找到结果返回-1
int search(int *array, s_index *index, int i_size, int key)
{
	//索引表的索引
	int i_ind = -1;
	//首先在索引表中查找
	for (int i = 0; i < i_size; ++i)
	{
		//找到索引块
		if (key <= index[i].val)
		{
			//记录索引表的索引
			i_ind = i;
			break;
		}
	}

	//如果在索引表中没找到
	if (i_ind == -1)
	{
		//返回-1
		return -1;
	}

	//在索引块中顺序查找
	for (int i = 0; i < I_SUB_SIZE; ++i)
	{
		//如果找到key值相等
		if (key == array[index[i_ind].ind + i])
		{
			//返回所在索引
			return index[i_ind].ind + i;
		}
	}

	//如果没找到则返回-1
	return -1;
}

int main(int argc, char **args)
{
	int array[A_SIZE] =
	{ 12, 17, 19, 8, 34, 39, 57, 48, 59, 81, 67, 99 };

	s_index index[3] =
	{
	{ 19, 0 },
	{ 57, 4 },
	{ 99, 8 } };

	printf("%d %d %d\n", search(array, index, I_SIZE, 5), search(array, index, I_SIZE, 48), search(array, index, I_SIZE, 67));

	return 0;
}

        运行结果:

-1 7 10

        本例代码:

code path   chapter.07/e.g.7.2/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure

    返回首页    返回顶部
  看不清?点击刷新

 

  Copyright © 2015-2018 问渠网 辽ICP备15013245号