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

 #define MaxKeyNum 25 // 索引表的最大容量(關鍵詞的最大數目)
 #define MaxLineLen 52 // 書目串(書目文件的1行)buf的最大長度
 #define MaxNoIdx 10 // 非索引詞(也是一個書目中關鍵詞)的最大數目

 struct WordListType // 一個書目的詞表(順序表)和非索引詞表(有序表)共用類型
 {
   char *item[MaxNoIdx]; // 詞表(字符串)指針數組
   int last; // 詞的數量
 };

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

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

 // 全局變量
 char buf[MaxLineLen+1]; // 當前書目串(包括'\0')
 WordListType wdlist,noidx; // 暫存一種書的詞表，非索引詞表

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

 void ExtractKeyWord(int &BookNo)
 { // 從buf中提取書名關鍵詞到詞表wdlist，書號存入BookNo
   int i,l,f=1; // f是字符串buf結束標志 0：結束 1：未結束
   char *s1,*s2;
   for(i=1;i<=wdlist.last;i++)
   { // 釋放上一個書目在詞表wdlist的存儲空間
     free(wdlist.item[i]);
     wdlist.item[i]=NULL;
   }
   wdlist.last=0; // 初始化詞表wdlist的詞數量
   BookNo=atoi(buf); // 將前幾位數字轉化為整數，賦給書號BookNo
   s1=&buf[4]; // s1指向書名的首字符
   while(f)
   { // 提取書名關鍵詞到詞表wdlist
     s2=strchr(s1,' '); // s2指向s1后的第一個空格，如沒有，返回NULL
     if(!s2) // 到串尾(沒空格)
     {
       s2=strchr(s1,'\12'); // s2指向buf的最后一個字符(回車符10)
       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&&(l=strcmp(wdlist.item[wdlist.last],noidx.item[i]))>0;i++);
       // 查找是否為非索引詞
       if(!l) // 是非索引詞
       {
         free(wdlist.item[wdlist.last]); // 從詞表中刪除該詞
         wdlist.item[wdlist.last]=NULL;
       }
       else
	 wdlist.last++; // 詞表長度+1
     }
     s1=s2+1; // s1移動到下一個單詞的首字符處
   };
 }

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

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

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

 void InsertBook(IdxListType &idxlist,int i,int bno)
 { // 在索引表idxlist的第i項中插入書號為bno的索引，算法4.14
   Link p;
   MakeNode(p,bno); // 分配結點 bo2-6.cpp
   p->next=NULL;
   Append(idxlist.item[i].bnolist,p); // 插入新的書號索引 bo2-6.cpp
 }

 void InsIdxList(IdxListType &idxlist,int bno)
 { // 將書號為bno的關鍵詞插入索引表，算法4.10
   int i,j;
   Status b;
   HString wd;
   InitString(wd); // bo4-2.cpp
   for(i=0;i<wdlist.last;i++)
   {
     GetWord(i,wd);
     j=Locate(idxlist,wd,b); // 關鍵詞的位置或待插入的位置(當索引表中不存在該詞)
     if(!b) // 索引表中不存在關鍵詞wd
       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]); // HString類型串尾沒有\0，只能逐個字符輸出
     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()
 { // 算法4.9
   FILE *f; // 任何時間最多打開一個文件
   IdxListType idxlist; // 索引表
   int BookNo; // 書號變量
   int k;
   if(!(f=fopen("NoIdx.txt","r"))) // 打開非索引詞文件
     exit(OVERFLOW);
   fscanf(f,"%d",&noidx.last); // 讀取非索引詞個數
   for(k=0;k<noidx.last;k++) // 把非索引詞文件的內容依次拷到noidx中
   {
     fscanf(f,"%s",buf);
     noidx.item[k]=(char*)malloc((strlen(buf)+1)*sizeof(char));
     strcpy(noidx.item[k],buf);
   }
   fclose(f); // 關閉非索引詞文件
   if(!(f=fopen("BookInfo.txt","r"))) // 打開書目文件
     exit(FALSE);
   InitIdxList(idxlist); // 設索引表idxlist為空，并初始化[0]單元
   while(fgets(buf,MaxLineLen,f)) // 由書目文件讀取1行信息到buf成功
   {
     ExtractKeyWord(BookNo);//將buf中的書號存入BookNo,關鍵詞提取到詞表(當前書目的關鍵詞表)中
     InsIdxList(idxlist,BookNo); // 將書號為BookNo的關鍵詞及書號插入索引表idxlist中
   }
   fclose(f); // 關閉書目文件
   if(!(f=fopen("BookIdx.txt","w"))) // 打開書名關鍵詞索引文件
     exit(INFEASIBLE);
   PutText(f,idxlist); // 將生成的索引表idxlist輸出到書名關鍵詞索引文件
   fclose(f); // 關閉書名關鍵詞索引文件
 }