查找之静态查找表

数据结构中查找分为如下部分：

静态查找表动态查找表哈希表及其查找以下分别对数据结构中的查找算法进行描述
一、静态查找表1.顺序表查找
顺序查找(Sequential Search)又称为线性查找，是一种最简单的查找方法。
查找过程如下：从线性表的一端开始顺序扫描线性表，依次将扫描到的结点关键字和给定值进行比较。若当前扫描到的结点关键字与给定值相等，则查找成功；若扫描结束后，仍未能找到关键字等于给定值的结点，则查找失败。
代码实现如下：

#include <stdio.h>#include <stdlib.h>#define MAX 16typedef int key_type;typedef struct element{key_type key;//关键字}ele;typedef struct _index{key_type key;int low, high;}index;int index_search(ele* e, key_type key, int count, index *idx, int idx_length){int i;int low = 0;int high = idx_length - 1;int mid;//从块的索引表中查找关键字所在的块(使用折半查找法)while(low <= high){mid = (low + high) / 2;if(key < idx[mid].key)high = mid - 1;else if(key > idx[mid].key)low = mid + 1;else{break;}}//从块中查找关键值（使用顺序查找）i = idx[mid].low;while(i < idx[mid].high && e[i].key != key)i++;if(i > idx[mid].high)return -1;elsereturn i + 1;}int main(int argc, char** argv){ele linelist[MAX] = {8, 20, 13, 17, 40, 42, 45, 32,49, 58, 50, 52,67, 79, 78, 80};int count = sizeof(linelist)/sizeof(ele);int i = 0;key_type key = 50;//建立索引表index index_table[4] ={{20,0,3}, {45,4,7}, {58,8,11}, {80,12,15}};int idx_length = sizeof(index_table)/sizeof(index);printf("线性表中的元素为：\n");while(i < count){printf("%d\n", linelist[i].key);i++;}printf("\n关键字[%d]在线性表中的位置为[%d]\n", key, index_search(linelist, key, count, index_table, idx_length));system("pause");return 0;}

存在一问题：如何对给定的数据序列进行分块，本例中是手动进行的分块
索引表查找算法：实际上进行了两次查找（折半查找+顺序查找）。因此整个算法的平均查找长度是两次查找的平均查找长度之和。