查找算法的实现

#include #include #include #include #define MAXL 100 #define MAXI 10

//查找表中最多记录个数 //索引表的最大长度

typedef int KeyType;

typedef char InfoType[10]; typedef struct {

KeyType key; //KeyType为关键字的数据类型

InfoType data; //其他数据 }NodeType;

typedef struct {

KeyType key; int link;

//key为分块的最大值 //指向分块的起始下标

}IdxType;

typedef NodeType SeqList[MAXL]; typedef IdxType IDX[MAXI];

//顺序表类型 //索引表类型

int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k) //二分查找算法 {

int low=0,high=m-1,mid,i; int b=n/m; //b为每块的记录个数

while (low<=high) //在索引表中进行二分查找,找到的位置存放在low中 {

mid=(low+high)/2; if (I[mid].key>=k)

high=mid-1; else }

low=mid+1;

i=I[high+1].link;

while (i<=I[high+1].link+b-1 && R[i].key!=k) i++; //i为k在查找表中的位置下标

if (i<=I[high+1].link+b-1) return i;

else

return -1;

}

void main() { SeqList R;//定义顺序表 KeyType k;//查找关键字

IDX I;//定义索引表 int a=0,i,j=0,n,b,s,o=0;

float m;

printf(\"请确定你的查找表的大小(小于等于100的平方数):\"); scanf(\"%f\

while(!((int)m==m && (m>=1 && m<=100) && (int)sqrt(m)==sqrt(m))) { printf(\"输入的大小有误,请重新输入:\");

scanf(\"%f\

//查找表中元素个数 //索引表大小，即查找表的均分的块数 //每一块的大小

}

n=(int)m; b=(int)sqrt(m); s=(int)sqrt(m);

do

{ printf(\"初始化查找表（块间有序），请输入%d个数据：\\n\

//继续录入代码，完成查找表数据的录入并建立索引表，最后实现数据的查找 for(i=0;i{ scanf(\"%d\ }

while(j{ int max=R[s*j].key; for(i=s*j;iif(R[i].key>max) { }

}

max=R[i].key;

I[j].key=max; I[j].link=s*j;

j++;

//s=2*s;问题：这样写的话则s的值在不断的被改写

}

for(j=0;j{ a++;

}

if(a} else { }

o=0;

printf(\"查找表不符合要求（块间无序），请重新输入：\\n\"); o=1; break;

}while(o==1); while(1)

{

printf(\"请输入您要查找的数据(输入负数结束程序)：\\n\");

scanf(\"%d\ if(k>I[s-1].key)//判断其输入的关键值k是否超出索引表中最大值的界限，若 { printf(\"元素%d不在查找表中！\\n\ continue;//本次循环到此结束，从起始位置printf(\"请输入您要查找的数据(输入负数结束程序)：\\n\");开始重新执行

j=IdxSearch( I, b, R, n, k); if(j<0)

{

printf(\"元素%d不在查找表中！\\n\} else { }

if(k<0)

{

printf(\"您的使用到此结束，谢谢您的使用！\\n\"); exit(0); }

}

}

printf(\"元素%d在查找表中位置为：%d\\n\}