/* algo4-4.c 生成書名關鍵詞索引文件bookidx.txt，算法4.9～4.14 */
 /* 為運行algo4-5.c做準備 */
 #include"c1.h"
 typedef int ElemType;
 #include"c2-5.h"
 #include"bo2-6.c"
 #include"c4-2.h"
 #include"bo4-2.c"

 #define MaxKeyNum 25 /* 索引表的最大容量(關鍵詞的最大數) */
 #define MaxLineLen 51 /* 書目串(書名+書號)buf的最大長度 */
 #define MaxWordNum 10 /* 詞表(一本書的關鍵詞)的最大容量 */
 #define MaxNoIdx 10 /* 常用詞(僅指大寫)的最大數 */
 typedef struct
 {
   char *item[MaxWordNum]; /* 詞表(字符串)指針數組 */
   int last; /* 詞的數量 */
 }WordListType; /* 詞表類型(順序表) */

 typedef struct
 {
   HString key; /* 關鍵詞(堆分配類型,c4-2.h) */
   LinkList bnolist; /* 存放書號索引的鏈表(c2-5.h) */
 }IdxTermType; /* 索引項類型 */

 typedef struct
 {
   IdxTermType item[MaxKeyNum+1];
   int last; /* 關鍵詞的個數 */
 }IdxListType; /* 索引表類型(有序表) */

 typedef struct
 {
   char *item[MaxNoIdx]; /* 常用詞表指針數組 */
   int last; /* 常用詞的數量 */
 }NoIdxType; /* 常用詞表類型(有序表) */

 /* 全局變量 */
 char buf[MaxLineLen+1]; /* 當前書目串(包括'\0') */
 WordListType wdlist; /* 暫存一本書的詞表 */
 NoIdxType noidx; /* 常用詞表 */

 void InitIdxList(IdxListType *idxlist)
 { /* 初始化操作，置索引表idxlist為空表，且在idxliat.item[0]設一空串 */
   (*idxlist).last=0;
   InitString(&(*idxlist).item[0].key); /* bo4-2.c */
   InitList(&(*idxlist).item[0].bnolist); /* bo2-6.c */
 }

 void ExtractKeyWord(int *BookNo)
 { /* 從buf中提取書名關鍵詞到詞表wdlist，書號存入BookNo */
   int i,l,f=1; /* f是字符串結束標志 0: 結束 1: 未結束 */
   char *s1,*s2;
   if(buf[0]<'0'||buf[0]>'9') /* buf的首字母不是數字 */
     exit(OVERFLOW);
   for(i=1;i<=wdlist.last;i++) /* 釋放上一個書目在詞表wdlist的存儲空間 */
   {
     free(wdlist.item[i]);
     wdlist.item[i]=NULL;
   }
   wdlist.last=0;
   *BookNo=(buf[0]-'0')*100+(buf[1]-'0')*10+(buf[2]-'0'); /* 前三位為書號 */
   s2=&buf[2]; /* s1指向書號的尾字符 */
   do
   { /* 提取書名關鍵詞到詞表wdlist */
     s1=s2+1; /* s1向后移動一個單詞 */
     s2=strchr(s1,' '); /* s2指向s1的第一個空格,如沒有,返回NULL */
     if(!s2) /* 到串尾 */
     {
       s2=strchr(s1,'\12'); /* s2指向buf的最后一個字符(回車符) */
       f=0;
     }
     l=s2-s1; /* 單詞長度 */
     if(s1[0]>='A'&&s1[0]<='Z') /* 單詞首字母為大寫 */
     { /* 寫入詞表 */
       wdlist.item[wdlist.last]=(char *)malloc((l+1)*sizeof(char));
       /* 生成串空間(包括'\0') */
       for(i=0;i<l;i++)
         wdlist.item[wdlist.last][i]=s1[i]; /* 寫入詞表 */
       wdlist.item[wdlist.last][l]=0;
       for(i=0;i<noidx.last;i++) /* 查找是否為常用詞 */
         if(!strcmp(wdlist.item[wdlist.last],noidx.item[i]))
           break;
       if(i!=noidx.last) /* 是常用詞 */
       {
         free(wdlist.item[wdlist.last]); /* 從詞表中刪除該詞 */
         wdlist.item[wdlist.last]=NULL;
       }
       else
         wdlist.last++; /* 詞表長度+1 */
     }
   }while(f);
 }

 void GetWord(int i,HString *wd)
 { /* 用wd返回詞表wdlist中第i個關鍵詞 */
   StrAssign(wd,wdlist.item[i]); /* 生成關鍵字字符串 bo4-2.c */
 }

 int Locate(IdxListType *idxlist,HString wd,Status *b)
 { /* 在索引表idxlist中查詢是否存在與wd相等的關鍵詞。若存在,則返回其 */
   /* 在索引表中的位置,且b取值TRUE;否則返回插入位置,且b取值FALSE */
   int i,m;
   for(i=(*idxlist).last;(m=StrCompare((*idxlist).item[i].key,wd))>0;--i); /* bo4-2.c */
   if(m==0) /* 找到 */
   {
     *b=TRUE;
     return i;
   }
   else
   {
     *b=FALSE;
     return i+1;
   }
 }

 void InsertNewKey(IdxListType *idxlist,int i,HString wd)
 { /* 在索引表idxlist的第i項上插入新關鍵詞wd,并初始化書號索引的鏈表為空表 */
   int j;
   InitList(&(*idxlist).item[(*idxlist).last+1].bnolist); /* bo2-6.c */
   for(j=(*idxlist).last;j>=i;--j) /* 后移索引項 */
     (*idxlist).item[j+1]=(*idxlist).item[j];
   InitString(&(*idxlist).item[i].key); /* bo4-2.c */
   StrCopy(&(*idxlist).item[i].key,wd); /* 串拷貝插入新的索引項 bo4-2.c */
   InitList(&(*idxlist).item[i].bnolist); /* 初始化書號索引表為空表 bo2-6.c */
   (*idxlist).last++;
 }

 void InsertBook(IdxListType *idxlist,int i,int bno)
 { /* 在索引表idxlist的第i項中插入書號為bno的索引 */
   Link p;
   if(!MakeNode(&p,bno)) /* 分配失敗 bo2-6.c */
     exit(OVERFLOW);
   p->next=NULL;
   Append(&(*idxlist).item[i].bnolist,p); /* 插入新的書號索引 bo2-6.c */
 }

 void InsIdxList(IdxListType *idxlist,int bno)
 { /* 將書號為bno的關鍵詞插入索引表 */
   int i,j;
   Status b;
   HString wd;
   InitString(&wd); /* bo4-2.c */
   for(i=0;i<wdlist.last;i++)
   {
     GetWord(i,&wd);
     j=Locate(idxlist,wd,&b);
     if(!b)
       InsertNewKey(idxlist,j,wd); /* 插入新的索引項 */
     InsertBook(idxlist,j,bno); /* 插入書號索引 */
   }
 }

 void PutText(FILE *f,IdxListType idxlist)
 { /* 將生成的索引表idxlist輸出到文件f */
   int i,j;
   Link p;
   fprintf(f,"%d\n",idxlist.last);
   for(i=1;i<=idxlist.last;i++)
   {
     for(j=0;j<idxlist.item[i].key.length;j++)
       fprintf(f,"%c",idxlist.item[i].key.ch[j]);
     fprintf(f,"\n%d\n",idxlist.item[i].bnolist.len);
     p=idxlist.item[i].bnolist.head;
     for(j=1;j<=idxlist.item[i].bnolist.len;j++)
     {
       p=p->next;
       fprintf(f,"%d ",p->data);
     }
     fprintf(f,"\n");
   }
 }

 void main()
 {
   FILE *f; /* 任何時間最多打開一個文件 */
   IdxListType idxlist; /* 索引表 */
   int BookNo; /* 書號變量 */
   int k,l;
   f=fopen("NoIdx.txt","r"); /* 打開常用詞文件 */
   if(!f)
     exit(OVERFLOW);
   fscanf(f,"%d",&noidx.last); /* 常用詞個數 */
   for(k=0;k<noidx.last;k++) /* 把常用詞文件的內容拷到noidx中 */
   {
     fscanf(f,"%s",buf);
     l=strlen(buf);
     noidx.item[k]=(char*)malloc(l*sizeof(char));
     strcpy(noidx.item[k],buf);
   }
   fclose(f);
   f=fopen("BookInfo.txt","r"); /* 打開書目文件 */
   if(!f)
     exit(FALSE);
   InitIdxList(&idxlist); /* 初始化索引表idxlist為空 */
   wdlist.last=0; /* 詞表長度初值為0 */
   while(!feof(f))
   {
     fgets(buf,MaxLineLen,f);
     l=strlen(buf);
     if(l<=1)
       break;
     ExtractKeyWord(&BookNo); /* 從buf中提取關鍵詞到詞表，書號存入BookNo */
     InsIdxList(&idxlist,BookNo);
   }
   fclose(f);
   f=fopen("BookIdx.txt","w");
   if(!f)
     exit(INFEASIBLE);
   PutText(f,idxlist); /* 將生成的索引表idxlist輸出到文件f */
   fclose(f);
 }