index.c

推荐刚刚开始学C语言的同志们看下

#define KEYLEN 10 /*索引关键字长度*/
#define ITEMLEN (KEYLEN+4) /*索引项长度*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int binsearch1(char *key,char *base,int nelem);
int binsearch2(char *key,char *base,int nelem);
int index(char *key);
char headblock,*keyword = "工程师";/*keyword是所要查找的关键字*/
FILE *fp;
void main(void)
{
	unsigned long recno;
	if((fp = fopen("example.idx","rb")) == NULL)
	{
		printf("Open file example,idx fail!\n");
		exit(0);
	}
	fseek(fp,1L,SEEK_SET);
    fscanf(fp,"%c",&headblock);
	recno = index(keyword);
	if(recno > 0)  printf("The record number being found is:%u\n",recno);
	else printf("Can not find the record containing key %s\n",keyword);
}

int binsearch1(char *key,char *base,int nelem)
/*在当前块中二分查找key，返回下层结点块号，nelem为块中索引项数*/
{
	int bnelem,unfound,before,after;
	unfound = 1;
	if(strcmp(key,base) <= 0) return(*(base+KEYLEN+2));
	else if(strcmp(key,base+(nelem-1)*ITEMLEN)>0) return(0);
	else{
		while(unfound)
		{
			bnelem = nelem/2;
			before = strcmp(key,base+(bnelem-1)*ITEMLEN);
			after = strcmp(key,base+bnelem*ITEMLEN);
			if(before <= 0) nelem = bnelem;
			else if((before > 0)&&(after <= 0))
			{
				unfound = 0;
				base += bnelem*ITEMLEN+KEYLEN+2;
				return(*base+(*(base+1))*0x100);
			}
			else if(after >0)
			{
				base = base+bnelem*ITEMLEN;
				nelem -= bnelem;
			}
		}

	}
	return(0);

}

int binsearch2(char *key,char *base,int nelem)
/*在当前块中二分查找key，返回记录号，nelem为块中索引项数*/
{
	int bnelem,unfound,comp;
	unfound = 1;
	while((nelem>0)&&unfound)
	{
		bnelem = (nelem+1)/2;
        comp = strcmp(key,base+(bnelem-1)*ITEMLEN);
		if(comp > 0)
		{
			base += bnelem*ITEMLEN;
			nelem /= 2;
		}
		if(comp < 0) nelem = bnelem-1;
		if(!comp)
		{
			unfound = 0;
			base += (bnelem - 1)*ITEMLEN+KEYLEN;
			return((*base * 0x1000000)+(*(base+1)*0x10000)+(*(base+2)*0x100)+(*(base+3)));

		}
	}
	return(0);
}


int index(char *key)
{
	char buffer[512];
	long fileoffset;
	int i;
	fileoffset = headblock *0x100;
	fseek(fp,fileoffset,SEEK_SET);
	fread(buffer,512,1,fp);
	while((buffer[0] != 0x2) && (buffer[0] != 0x3))
	{
		fileoffset = binsearch1(key,&buffer[12],buffer[2])*0x100;
		fseek(fp,fileoffset,SEEK_SET);
		fscanf(fp,"%512c",buffer);
	}
	return(binsearch2(key,&buffer[12],buffer[2]));

}