苗火 Nicholas

[Data structures]Create index lists (An example of string)

2019-8-30 萧 写技术

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

#define MAX_KEY_NUM 255
#define MAX 255
typedef unsigned char SString[MAX+1];

typedef struct _WordList{
	char *item[MAX_KEY_NUM];
	int last;
}WordList;

typedef struct _LinkList{
	int book_number;
	struct _LinkList *next;
}LinkList;

typedef struct _IdxItem{
	SString key;
	LinkList *bnolist;
}IdxItem;

typedef struct _IdxList{
	IdxItem item[MAX_KEY_NUM + 1];
	int last;
}IdxList;

char buf[MAX];
WordList wdList;

void InitIdxList(IdxList *idxList)
{
	IdxItem item;
	item.key[0] = 0;
	item.key[1] = 0;
	item.bnolist = NULL;

	idxList->last = 0;
	idxList->item[0] = item;
}

int SStrcmp(SString A, SString B)
{
	if(A[0] == 0){
		A[1] = 0;;
	}
	if(B[0] == 0){
		B[1] = 0;
	}
	return strcmp(A+1,B+1);
}

int GetLine(FILE *fp)
{
	char c;
	int i=0;
	//fscanf(fp, "%[^\n]", buf);
	while(!feof(fp) && (c = fgetc(fp)) != '\n'){
		buf[i++] = c;
	}
	if(c != '\n'){
		return 0;
	}else{
		return 1;
	}
}

void ExtractKeyWord(int *bno)
{
	int i;
	char *p = buf;
	int n;
	n = strlen(buf);
	i=0;
	wdList.last = 0;

	while(buf[i] == ' '){
		i++;
	}
	p = buf+i;

	while(buf[i] != ' '){
		i++;	
	}
	buf[i++] = 0;
	sscanf(p, " %d", bno);

	while(i<n){
		while(i<n && buf[i] == ' '){
			i++;
		}
		p = buf + i;
	
		while(i<n && buf[i] != ' '){
			i++;
		}
		buf[i++] = 0;

		wdList.item[wdList.last++] = p;
	}
}


void GetWord(int i, SString wd)
{
	strcpy(wd+1, wdList.item[i]);
	wd[0] = strlen(wdList.item[i]);
}

int Locate(IdxList *iList, SString wd, int *b)
{
	int i;
	int m=-1;
	/* In order */
	for(i=iList->last - 1; 
			i>=0 && ( (m = strcmp(iList->item[i].key+1, wd+1) ) > 0); 
			i--);

	if(m==0){
		*b = 1;
		return i;
	}else{
		*b = 0;
		return i+1;
	}
}

void InsertNewKey(IdxList *iList, int i, SString wd)
{
	int j;
	for(j=iList->last-1; j>=i; j--){
		iList->item[j+1] = iList->item[j];
	}
	strcpy(iList->item[i].key+1, wd+1);
	iList->item[i].key[0] = wd[0];
	iList->item[i].bnolist = NULL;
	iList->last++;
}

int InsertBook(IdxList *iList, int i, int bno)
{
	LinkList *p = (LinkList *)malloc(sizeof(LinkList));
	p->book_number = bno;
	p->next = iList->item[i].bnolist;
	iList->item[i].bnolist = p;	
	return 1;
}

int InsIdxList(IdxList *iList, int bno)
{
	int i,j,b;
	SString wd;
	wd[0] = 0;
	wd[1] = 0;
	for(i=0; i<wdList.last; i++){
		GetWord(i, wd);
		j = Locate(iList, wd, &b);
		if(!b){
			InsertNewKey(iList, j, wd);
		}
		InsertBook(iList, j, bno);
	}	
}

void main()
{
	int bno;
	IdxList iList;

	int i;
	LinkList *p;

	printf("log.anycle.com\n\n");
	FILE *fp;

	printf("Original data:\n");
	fp = fopen("./bookList.txt", "r");
	while(!feof(fp)){
		putchar(fgetc(fp));
	}
	fclose(fp);
	printf("\n");

	printf("Create index of books:\n");
	fp = fopen("./bookList.txt", "r");
	InitIdxList(&iList);
	while(GetLine(fp)){
		ExtractKeyWord(&bno);
		InsIdxList(&iList, bno);
	}
	fclose(fp);

	for(i=0; i<iList.last; i++){
		printf("%s\r\t\t\t:", iList.item[i].key+1);
		for(p=iList.item[i].bnolist; p; p=p->next){
			printf(" %02d", p->book_number);
		}
		printf("\n");
	}

}

标签: Data Structures data_structures