Question

索引顺序查找算法

要实现的功能
（1） 要求能自动建立索引表；
（2） 对任意待查找的关键字，若查找成功，给出其关键字比较次数。
先给100分 完成的再给100分
楼下那个是没什么用的 我早看过了 会写的来吧
那些百度一下能出来的东西就别发出来 我不是傻子
还有 我要的是算法 不懂的别乱写 OK？

Answer 1

参考代码，不一定正确。
#include <malloc.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <memory.h>

struct element
{
long key;
long data;
};

struct index
{
long address;
long maxkey;
};

struct index *creatidxtable(struct element *elems, long elen, long *tlen, long *plen)
{
struct index *itable;
long i, step, len;
len = (long)sqrt(elen);
*plen = len;
step = len;
len = (len * len == elen ? len : len + 1);
*tlen = len;
itable = (struct index *)malloc(sizeof(struct index) * len);

for (i = 0; i < len; ++i)
{
itable[i].address = i;

if (i < len - 1)
itable[i].maxkey = elems[ i * step + *plen - 1].key;
else
itable[i].maxkey = elems[elen - 1].key;
}

return itable;
}

long searchposition(struct index *itable, long length, long *times, long key)
{
long i;

++(*times);

if (key <= itable[0].maxkey)
return itable[0].address;

++(*times);

if (key >= itable[length - 1].maxkey)
return itable[length - 1].address;

for (i = 0; i < length - 1; ++i)
{
(*times) += 2;

if (key > itable[i].maxkey && key <= itable[i + 1].maxkey)
return itable[i + 1].address;
}

return -1;
}

long seqencesearch(struct element *elems, long start, long length, long *times, long key)
{
long i;

for (i = start; i < start + length; ++i)
{
++(*times);
if (elems[i].key == key)
return i;
}

return -1;
}

void selectionsort(struct element *elems, long length)
{
long i, j, k, s = sizeof(struct element);
struct element t;

for (i = 0; i < length - 1; ++i)
{
k = i;

for (j = i + 1; j < length; ++j)
{
if (elems[k].key > elems[j].key)
{
k = j;
}
}

if (k != i)
{
memcpy(&t, elems + i, s);
memcpy(elems + i, elems + k, s);
memcpy(elems + k, &t, s);
}
}
}

void initdata(struct element *elems, int length)
{
long i;

srand(time(NULL));
for (i = 0; i < length; ++i)
{
elems[i].data = elems[i].key = rand();
}
}

void output(struct element *elems, int length)
{
long i;

for (i = 0; i < length; ++i)
{
printf("%-10d ", elems[i].key);

if ((i + 1) % 5 == 0)
printf("\n");
}
}

void main()
{
struct element * elems;
struct index *itable;
long num, tlen, plen, times, key, start, pos;

while (1)
{
printf("请输入想要测试的数据量：");
scanf("%ld", &num);

if (num <= 0)
break;

elems = (struct element *)malloc(sizeof(struct element) * num);
initdata(elems, num);
selectionsort(elems, num);
output(elems, num);
itable = creatidxtable(elems, num, &tlen, &plen);
times = 0;
printf("\n");
printf("请输入一个查找关键字：");
scanf("%ld", &key);

if ((start = searchposition(itable, tlen, ×, key)) == -1)
{
printf("查找失败1！\n");
}
else
{
pos = seqencesearch(elems, start * plen,
(start == tlen - 1 ? num - (tlen - 1) * plen : plen), ×, key);
if (pos != -1)
{
printf("查找成功！\n");
printf("关键字对应的值：%ld\n", elems[pos].data);
printf("关键字比较次数：%ld\n", times);
}
else printf("查找失败！\n");
}

free(elems);
free(itable);
}
system("PAUSE");
}

Answer 2

索引查找是在索引表和主表(即线性表的索引存储结构)上进行的查找。索引查找的过程是：首先根据给定的索引值K1，在索引表上查找出索引值等于KI的索引项，以确定对应予表在主表中的开始位置和长度，然后再根据给定的关键字K2，茬对应的子表中查找出关键字等于K2的元素(结点)。对索引表或子表进行查找时，若表是顺序存储的有序表，则既可进行顺序查找，也可进行二分查找，否则只能进行顺序查找。
设数组A是具有mainlist类型的一个主表，数组B是具有inde)dist类型的在主表A 上建立的一个索引表，m为索引表B的实际长度，即所含的索引项的个数，KI和K2分别为给定待查找的索引值和关键字(当然它们的类型应分别为索引表中索引值域的类型和主表中关键字域在索引存储中，不仅便于查找单个元素，而且更便于查找一个子表中的全部元素。当需要对一个子袁中的全部元素依次处理时，只要从索引表中查找出该子表的开始位置即可。由此开始位置可以依次取出该子表中的每一个元素，所以整个查找过程的时间复杂度为，若不是采用索引存储，而是采用顺序存储，即使把它组织成有序表而进行二分查找时，索引查找一个子表中的所有元素与二分查找一个子表中的所有元素相比。
若在主表中的每个子表后都预留有空闲位置，则索引存储也便于进行插入和删除运算，因为其运算过程只涉及到索引表和相应的子表，只需要对相应子表中的元素进行比较和移动，与其它任何子表无关，不像顺序表那样需涉及到整个表中的所有元素，即牵一发而动全身。
在线性表的索引存储结构上进行插入和删除运算的算法，也同查找算法类似，其过程为：首先根据待插入或删除元素的某个域(假定子表就是按照此域的值划分的)的值查找索引表，确定出对应的子表，然后再根据待插入或删除元素的关键字，在该子表中做插入或删除元素的操作。因为每个子表不是顺序存储，就是链接存储，所以对它们做插入或删除操作都是很简单的。

不知道答案与兄台的问题是否一致，也是网上找的，不对请见谅哈~~

Answer 3

http://www.pudn.com/downloads111/sourcecode/windows/other/detail462506.html
LZ干脆去注册一下,直接下载算了.