blocksearch.cpp

数据结构c++-书的一些源代码

typedef int keytype;

typedef struct
{
   keytype Key;
} elemtype;

typedef struct
{
   keytype Key;
   int Link;
} indextype;

int IndexSequelSearch(indextype ls[],elemtype s[],int m,int l,keytype Key)
/*分块查找关键字为Key的记录。索引表为ls[0]--ls[m-1], 顺序表为s, 块长为l*/
{
   int i,j;
   
   /*在索引表中顺序查找*/
   i=0;
   while(i < m && Key > ls[i].Key) i++;

   if(i >= m) return -1;
   else
   {
      /*在顺序表中顺序查找*/
      j = ls[i].Link;
      while(Key != s[j].Key && j - ls[i].Link < l)  j++;

      if(Key == s[j].Key) return j;
      else return -1;
   }
}

main()
{
   indextype ls[5]={{14,0},{34,5},{66,10},{85,15},{100,20}};
   elemtype Test[25]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,
		    46,71,78,68,80,85,100,94,88,96,87};
   int m = 5,l = 6, Key = 87, i;

   i = IndexSequelSearch(ls,Test,m,l,Key);

   if(i != -1) printf("\n查找成功！该数据元素为第 %d 个记录", i);
   else  printf("\n查找失败！该数据元素在记录集合中不存在");
}