建立词索引表

/*!
 * 数据结构（C语言版）
 * 第四章P86-89 建立词索引表
 *  
 */


#include
#include
#include  


#define MaxBookNum 1000
#define MaxKeyNum 2500
#define MaxLineLen 500
#define MaxWordNum 10
#define MaxKeyWordLen 20


#define OK 1
#define FALSE 0


typedef int Status;
typedef int ElemType;


typedef struct{
char item[MaxWordNum][MaxKeyWordLen];
int  lenth;
}WordListType;


typedef struct LinkList{
ElemType BookNo;
struct LinkList *next;
}LinkList;


typedef struct{
char key[20];
LinkList bnolist;
}IdxTermType;


typedef struct{
IdxTermType item[MaxKeyNum];
int len;
}IdxListType;


const char NotKeyWord[5][4] = {"An", "A", "Of", "The", "To"};


char  buf[MaxLineLen];
WordListType wdlist;


void InitIdxList(IdxListType *ptr)
{
int i;
ptr->len = 0;

for(i = 0; i < MaxKeyNum; i++)
{
(ptr->item[i]).key[0] = '\0';
(ptr->item[i]).bnolist.BookNo = -1;
(ptr->item[i]).bnolist.next = NULL;
}
}


int ExtractKeyWord(void)
{
int Book_No, i, j;
char key_word[MaxKeyWordLen];


Book_No = atoi(buf);
wdlist.lenth = 0;
i = 0;
while(buf[i] != ' ')//跳过每行开头的书号索引（数字） 
{
i = i+1;
}
while((buf[i]!= '\0') && (buf[i] != '\n'))
{
j = 0;
while(buf[i] == ' ')
{
i = i+1;
}
while((buf[i] != ' ') && (buf[i] != '\n') && (buf[i]))
{
key_word[j] = buf[i];
i++;
j++;
}
key_word[j] = '\0';

if((key_word[0] >= 'a') && (key_word[0] <= 'z'))//将关键字第一个字符转换为大写 
key_word[0] = key_word[0] - 32;

for(j = 0; j < 5; j++)
{
if(strcmp(key_word, NotKeyWord[j]) == 0)
break;
}
if(j >= 5)
{
memcpy(wdlist.item[wdlist.lenth], key_word, strlen(key_word) + 1);
wdlist.lenth++;
}
}

return Book_No;
}


void InsertNewKey(IdxListType *list, int pos, char *str, int _bno)
{
int i;
for(i = list->len; i > pos; i--)
list->item[i] = list->item[i-1];

strcpy(list->item[i].key, str);
(list->item[i]).bnolist.BookNo = _bno;
(list->item[i]).bnolist.next = NULL;
}


void InsertBook(IdxListType *plist, int pos, int bookno)
{
LinkList *p;
LinkList *q;
LinkList *tmp;
int num;

if((plist->item[pos]).bnolist.BookNo < 0)
{//如果第一个结点为空，则填充第一个结点 
(plist->item[pos]).bnolist.BookNo = bookno;
(plist->item[pos]).bnolist.next = NULL;

return;
}

p = (LinkList *)malloc(sizeof(LinkList));
if(p == NULL)
{
printf("\r\nmemory malloc failed, exit\r\n");
exit(1);
}
// p->BookNo = bookno;
q = &((plist->item[pos]).bnolist);
tmp = q;

//按书号索引大小插入 
while(1)
{
if((q->BookNo) < bookno)
{
if((q->next) == NULL)
break;
else
q = q->next;
}
else
{
num = q->BookNo;
q->BookNo = bookno;
break;
}
}
 
  if(q->next == NULL)
{
p->BookNo = bookno;
q->next = p;
p->next = NULL;
q = tmp;

return;
}
while(q->next)
{
p->BookNo = q->next->BookNo;
q->next->BookNo = num;
num = p->BookNo;
q = q->next;
}
q->next = p;
p->next = NULL;

return;
}


int Locate(IdxListType *p_idxlist, char *p_keyword, Status *val)
{
int i, m;

m = -1;

for(i = 0; i < p_idxlist->len; i++)
{
m = strcmp((p_idxlist->item[i]).key, p_keyword);
if(m >= 0)//书名关键字是按字典顺序排列 
break;
}

if(m == 0)
{
*val = OK;
}
else
{
*val = FALSE;
}

return i;
}


Status InsIdxList(IdxListType *p_idx, int bno)
{
int i, j;
Status b;

for(i = 0; i < wdlist.lenth; i++)
{
j = Locate(p_idx, wdlist.item[i], &b);
if(b == OK)
{
InsertBook(p_idx, j, bno);
}
else
{
InsertNewKey(p_idx, j, wdlist.item[i], bno);
p_idx->len++;
}
}

return OK;
}


void PutText(FILE *fw, IdxListType *b_list)
{
int i;
LinkList *p, *tmp;

for(i = 0; i < b_list->len; i++)
{

fprintf(fw, "%s", b_list->item[i].key);
p = &(b_list->item[i].bnolist);
tmp = p;
while(p)
{
fprintf(fw, " %d", p->BookNo);
p = p->next;
}
fprintf(fw, "\r\n");
p = tmp;
}
return;
}


int main(void)
{
FILE *fin;
FILE *fout;

IdxListType idxlist;
int BookNo;

fin = fopen("BookInfo.txt", "r");
if(fin == NULL)
{
printf("\r\nopen BookInfo.txt failed, exit\r\n");
exit(0);
}
fout = fopen("BookIdx.txt", "w");
if(fout == NULL)
{
fclose(fin);
printf("\r\nopen BookIdx.txt failed, exit\r\n");
exit(0);
}

InitIdxList(&idxlist);
while(!feof(fin))
{
memset(buf, 0, sizeof(buf));

fgets(buf, MaxLineLen, fin);

BookNo = ExtractKeyWord();

InsIdxList(&idxlist, BookNo);
}

PutText(fout, &idxlist);

fclose(fin);
fclose(fout);
return 0;
}