i_search.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/****************************************************/
/*                分块查找算法                      */
/*  文件名：i_search.c    函数名：indexseqsearch()  */
/****************************************************/
#include "seqlist.h"

typedef struct    /*索引表结点类型*/
     { datatype key;
       int address;
     } indexnode;

/*--------分块查找--------*/
int indexseqsearch(seqlist l,indexnode index[],int m,datatype key)
{   /*分块查找关键字为Key的记录，索引表为index[0..m-1]*/
    int i=0,j,last;
    while (i<m && key>index[i].key) i++;
    if (i>=m)  return -1;
     else
     { /*在顺序表中顺序检索*/
       if (i==m-1) j=l.len-1;
             else j=index[i+1].address-1;  /*j初始时指向本块的最后一个结点*/
       while (j>=index[i].address && key!=l.data[j] )
             j--;    /*从后向前逐个查找*/
       if (j<index[i].address) return -1; 
          else return j; 
     }
}
    
main()
{ int i,k,m;
  datatype key;
  seqlist l;
  indexnode index[10];
  FILE *rf ;
  rf = fopen("G9_2.txt", "r") ;   /*G9_2.txt中存放了图9.2中所有的输入数据*/
  fscanf(rf,"%d",&l.len); /*输入线性表的长度*/
  for (i=0;i<l.len;i++)   /*输入线性表的结点内容*/
     fscanf(rf,"%d", &l.data[i]);
  fscanf(rf,"%d",&m);     /*输入索引表的长度*/
  for (i=0;i<m;i++)       /*输入索引表的内容*/
    fscanf(rf,"%d%d",&index[i].address,&index[i].key);
  printf("Please input a Key:");
  scanf("%d",&key);
  k=indexseqsearch(l,index,m,key);
  printf("\nk=%d",k);
  fclose(rf);
}