search.c

计算机科班学生的数据结构课写的查找算法。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAXLEN 32      //关键词的最大长度
#define MAXNAME 32     //书名的最大长度
#define MAXNUM  2500   //关键词的最大数目
typedef struct BNList
{
	char BookName[MAXNAME];
	struct BNList *next;
}BNList; //定义书名
typedef struct
{
	char key[MAXLEN];
	BNList *bnolist;
}IdxElemType; //定义关键词
typedef struct WordList
{
	char key[MAXLEN];
	struct WordList *next;
}WordList;    //定义词表
typedef struct 
{
	IdxElemType *(item[MAXNUM]);
	int last;
}IdxListType; //关键词链表
WordList *list,*rear;
IdxListType *idxlist;
FILE *fp1;

int InBNList(int n,char *bno)  //检查一本书是否已经在书目链上
{
	BNList *p;
	if(!idxlist->item[n]->bnolist)  return 0;
	for(p=idxlist->item[n]->bnolist;p!=NULL;p=p->next)
		if(!strcmp(p->BookName,bno))  return 1;
    return 0;
}
int InsertBNList(int n,char *bono) // 将书名插入链中
{
	BNList *p;
	if(!InBNList(n,bono))
	{
		p=(BNList *)malloc(sizeof(BNList));
		if(!p)
		{
			printf("malloc failed\n");
			return 0;
		}

		printf("in int insertbooklist %s\n",bono);

		strcpy(p->BookName,bono);
		p->next=idxlist->item[n]->bnolist;
		idxlist->item[n]->bnolist=p;
		
		fwrite(idxlist->item[n]->key,(strlen(idxlist->item[n]->key))*sizeof(char),1,fp1);
		fwrite(bono,(strlen(bono)*sizeof(char)),1,fp1);	
	//	for(;p!=NULL;p=p->next)
		//	puts(p->BookName);
	}
	return 1;
}
int InsertIdxList(char *bona,char *key)  //插入索引表
{
	int i;
	IdxElemType *p;
	for(i=0;i<=idxlist->last;i++)
        if(!strcmp(idxlist->item[i]->key,key)) 
		{
			InsertBNList(i,bona);
			return 0;
		}
	idxlist->last++;
	p=(IdxElemType *)malloc(sizeof(IdxElemType));
	if(!p)
	{
		printf("malloc failed\n");
		return 0;
	}
	p->bnolist=(BNList *)malloc(sizeof(BNList));
	if(!p->bnolist) return 0;
	strcpy(p->key,key);
	strcpy(p->bnolist->BookName,bona);	
	fwrite(key,(strlen(key))*sizeof(char),1,fp1);
    fwrite(bona,(strlen(bona))*sizeof(char),1,fp1);	
	fwrite(p,sizeof(IdxElemType ),1,fp1);
	p->bnolist->next=NULL;
	idxlist->item[idxlist->last]=p;
	return 1;
}

int InsertList(char *str)    //插入词表
{
	WordList *p;
	p=(WordList *)malloc(sizeof(WordList));
	if(!p) return 0;
	strcpy(p->key,str);
	if(!list) 
	{
		list=p;
	    p->next=rear;
	    rear=p;
		return 1;
	}
	p->next=NULL;
	rear->next=p;
	rear=p;
	return 1;
}


int GeneWordList(void)   //产生词表
{
	char filename[MAXNAME],s[MAXLEN],format[10];
    FILE *fp;
	sprintf(format,"%%%ds",MAXLEN-1);
	printf("输入关键词表的路径和名字：\n");
	gets(filename);
	if(!(fp=fopen(filename,"r")))
	{
		printf("不能打开文件\n");
		return 0;
	}
	while(!feof(fp))
	{
		fscanf(fp,format,s);
	//	puts(s);
		if(!InsertList(s)) return 0;
	}
	if(!list) return 0 ;
	return 1;
}

int OpenTxt(char *filename)
{
	WordList *p;
	char fmt[10];
    unsigned int find,nword, n;
	int read;
	long int len;
	FILE *fp;
	char str[MAXLEN];

	fp=fopen(filename,"rb");
	if(!fp)
	{
		printf("can not open\n");
		return 0;
	}
	fseek(fp,0,2);
	len=ftell(fp);
	rewind(fp);
//	printf("the length:%ld **after rewind %ld**\n",len,ftell(fp));
//	printf("the length of the file is %ld**",len);
	while(!feof(fp)&&len>=ftell(fp))
//	for(i=0;i<3&&len!=ftell(fp);i++)
	{		// printf("here1");
		for(p=list,find=1;p!=NULL;p=p->next)
		{   
			
			if(!find)
		//	{
			//	printf("rewind\n");
			//	position=ftell(fp);
			//	printf("position:%d",position);
				fseek(fp,-nword,1);
			//	printf("after seek %d\n",ftell(fp));
	//		}
			if(len==ftell(fp)) 
			{
				printf("ok end file \n");
				return 1;
			}
			find=0;
		//	printf("here2\n");
			n=strlen(p->key);
		 //   printf("the key word is:\n");
		//	puts(p->key);
			sprintf(fmt,"%%%ds",n);
			
		//	printf("before read %d**\n",ftell(fp));
			if(len==ftell(fp)) 
		//	{printf("end**"); break;}
	        	break;
			read=fscanf(fp,fmt,str);
			nword=strlen(str) ; //printf("read:%d ",read);
		//	printf("len:%d  ",len);
		//	printf("after read %d**\n",ftell(fp));
			if(str[0]=='\n'||str[0]=='\0'||str[0]==' ') 
			{
				find=1;
				continue;
			}
			if(read==-1) return 1;
		//	 if(read<0&&feof(fp)) return 0;
			  
		//	while(read==-1)  return 1;{read=fscanf(fp,fmt,str);printf("look %d ",read);fseek(fp,0,2); }
		//	else 
		//		while((fscanf(fp,fmt,str))==0) ;
                  //  fscanf(fp,fmt,str);
		//	puts(str);
		
			if(!strcmp(p->key,str))
			{
				InsertIdxList(filename,str);
			//	printf("find**"); 
				find=1;
				break;
			}
		    
			
		}
	}
	fclose(fp);
	return 1;
}
 
void Idx(char *str)
{
	int i;
	char ch;
	BNList *p;
	FILE *fp;
	for(i=0;i<=idxlist->last;i++)
	{
		if(!strcmp(idxlist->item[i]->key,str))
		{
			for(p=idxlist->item[i]->bnolist;p!=NULL;)
			{	printf("搜索结果:\n");
				printf("***    %s   ***\n",p->BookName);
				//printf("是否想打开此文件，按0键表示不打开\n");
				//flag=0;
				//scanf("%d",&flag);
				//getchar();
				//if(flag)
				//{
					fp=fopen(p->BookName,"r");
					if(!fp)
					{
						printf("can not open!\n");
						return ;
					}
					while(!feof(fp))
					{
						ch=fgetc(fp);
					putchar(ch);
					}
				//}
				p=p->next;

			}
			return;
		}
	}
	printf("can not find\n");
	return ;
}
    
    



void main(void)
{
	char filename[32],key[32],file[32],flag='y';
 //   int n,n1;
//	int flag1;
//	FILE *fp;
//	BNList *p;
//	WordList *q;
	list=rear=NULL;
	idxlist=(IdxListType *)malloc(sizeof(IdxListType));
    printf("~*~*~*~*~*~*~*~*~*~*~搜 索 引 擎~*~*~*~*~*~*~*~*~*~*~\n");
	printf("新建一个文本文件以存放索引表，请为它取一个文件名：\n");
	scanf("%s",file);
	getchar();
	if(!(fp1=fopen(file,"wb"))) 
	{
		printf("can not open File \n");
		return;
	}
	if(!idxlist) 
	{
		printf("malloc failed\n");
		return;
	}
	idxlist->last=-1;
	if(!GeneWordList()) return ;
//	for(q=list;q!=NULL;q=q->next)
//		puts(q->key);
	while(flag=='y'||flag=='Y')
	{
		printf("输入一个文章路径和名字：\n");
		gets(filename);
	//	getchar();
	    if(!OpenTxt(filename)) return ;
		printf("是否继续导入文章，按y键表示是，n表示否。\n");
	//	getchar();
		flag=getchar();
		getchar();
	}
	fclose(fp1);flag='n';
	printf("是否要看生成的索引表，按y键表示是，n表示否。\n");
    flag=getchar();
	getchar();
	if(flag=='y'||flag=='Y')
	{
		if(!(fp1=fopen(file,"r")))
		{
			printf("对不起，不能打开存放索引表的文件\n");
			flag='N';
		}
		while(!feof(fp1))
		{
			flag=fgetc(fp1);
			putchar(flag);
		}
	}
	fclose(fp1);
	flag='y';
	while(flag=='y'||flag=='Y')
	{
	  printf("输入关键词：\n");
	  gets(key);
//	getchar();
      Idx(key);
	  printf("***   是否继续，按y键表示继续   ***\n");
	  flag=getchar();
	  getchar();
	}
	return;
}