#define  MaxBookNum      1000    // 假設(shè)只對(duì)1000本書(shū)建索引表
#define  MaxKeyNum       2500    // 索引表的最大容量
#define  MaxLineLen       500    // 書(shū)目串的最大長(zhǎng)度
#define  MaxWordNum        10    // 詞表的最大容量
#define  MaxWordLength     30    // 單詞的最大長(zhǎng)度

typedef int Boolean;

typedef struct {
    char    item[MaxWordNum][MaxWordLength];  // 字符串的數(shù)組
    int     last;        // 詞表的長(zhǎng)度
} WordListType;          // 詞表類(lèi)型（順序表）

typedef struct {
    HString   key;       // 關(guān)鍵詞
    NLinkList bnolist;   // 存放書(shū)號(hào)索引的鏈表
} IdxTermType;           // 索引項(xiàng)類(lèi)型

typedef struct {
    IdxTermType  item[MaxKeyNum+1];
    int          last;
} IdxListType;           // 索引表類(lèi)型（有序表）

//------ 基本操作 ------
void InitIdxList(IdxListType &idxlist);
   // 初始化操作，置索引表idxlist為空表，即idxlist.last=0,
   // 且在idxlist.item[0]設(shè)一空串
void GetLine(FILE *f);
   // 從文件f讀入一個(gè)書(shū)目信息到書(shū)目串緩沖區(qū)buf
Status ExtractKeyWord(char *Buffer, WordListType &w, int &bno);
   // 從buf中提取書(shū)名關(guān)鍵詞到詞表wdlist，書(shū)號(hào)存入bno
Status InsertIdxList(IdxListType &idxlist, ElemType bno);  
   // 將書(shū)號(hào)為bno的書(shū)名關(guān)鍵詞按詞典順序插入索引表idxlist
Status PutText(FILE *g, IdxListType idxlist);           
   // 將生成的索引表idxlist輸出到文件g
void PrintFile(FILE *FileName);

Status InsertIdxList(IdxListType &idxlist, int bno);   // 算法4.10
   // 索引表插入算法
void GetWord(int i, HString &wd);                      // 算法4.11
   // 用wd返回詞表wdlist中第i個(gè)關(guān)鍵詞。
int Locate(IdxListType &idxlist, HString wd, Boolean &b); // 算法4.12
   // 在索引表idxlist中查詢(xún)是否存在與wd相等的關(guān)鍵詞。
   // 若存在，則返回其在索引表中的位置，
   // 且b取值TRUE；否則返回插入位置，且b取值FALSE
void InsertNewKey(IdxListType &idxlist, int i, HString wd);//算法4.13
   // 在索引表idxlist的第i項(xiàng)上插入新關(guān)鍵詞wd，
   // 并初始化書(shū)號(hào)索引的鏈表為空表
Status InsertBook(IdxListType &idxlist, int i, int bno); // 算法4.14
   // 在索引表idxlist的第i項(xiàng)中插入書(shū)號(hào)為bno的索引

//------ 主要變量 ------
char          buf[MaxLineLen];   // 書(shū)目串緩沖區(qū)
WordListType  wdlist;    // 詞表
IdxListType   idxlist;   // 索引表

//------ 主函數(shù) ------
int main(int argc, char* argv[]) {  // 算法4.9
  FILE *f,*g;
  int BookNo;
  printf("**************************************************\n");
  printf("       《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版) 嚴(yán)蔚敏 吳偉民 編著     \n");
  printf("                算法4.9-4.14（參見(jiàn)圖4.9）          \n");
  printf("**************************************************\n\n");
  if ((f = fopen ("Algo0409BookInfo.txt", "r"))==NULL) {
    printf("ERROR in open BookInfo.txt!\n");
    exit(1);
  }
  if ((g = fopen ("Algo0409BookIdx.txt", "w"))==NULL) {
    printf("ERROR in open BookIdx.txt!\n");
    exit(1);
  }
  printf("書(shū)目文件：\n");
  PrintFile(f);
  InitIdxList(idxlist);         // 初始化索引表idxlist為空表
  while (!feof (f)) {
    GetLine (f);                // 從文件f讀入一個(gè)書(shū)目信息到buf
    ExtractKeyWord(buf,wdlist,BookNo);  
        // 從buf提取關(guān)鍵詞到詞表，書(shū)號(hào)存入BookNo
    InsertIdxList(idxlist, BookNo);  // 書(shū)號(hào)為BookNo的關(guān)鍵詞插入索引表
  }
  PutText(g, idxlist);          // 將生成的索引表idxlist輸出到文件g
  fclose(f);
  fclose(g);
  printf("對(duì)書(shū)目文件進(jìn)行處理后的索引文件：\n");
  if ((g = fopen ("Algo0409BookIdx.txt", "r"))==NULL) {
    printf("ERROR in open BookIdx.txt!\n");
    exit(1);
  }
  PrintFile(g);
  fclose(g);
  printf("按任意鍵，結(jié)束 ......\n");
  getch();
  return 0;
} // main

Status InsertIdxList(IdxListType &idxlist,  int bno) {  // 算法4.10
  int i,j;
  HString wd;
  Boolean b;
  for (i=0;  i<wdlist.last;  i++) {
    GetWord(i, wd);   
    j = Locate(idxlist, wd, b);
    if (!b)
      InsertNewKey(idxlist, j, wd);  //  插入新的索引項(xiàng)
    InsertBook(idxlist, j, bno);     //  插入書(shū)號(hào)索引
  }
  return OK;
} // InsertIdxList

void GetWord(int i,  HString &wd) {  // 算法4.11
  char *p;
  p = *(wdlist.item +i);  // 取詞表中第i個(gè)字符串
  StrAssign(wd, p);       // 生成關(guān)鍵字字符串
} // GetWord

int Locate(IdxListType &idxlist, HString wd, Boolean &b) { // 算法4.12
  int i,m;
  for (i = idxlist.last-1; 
       ((m = StrCompare(idxlist.item[i].key, wd)) > 0);  --i);
  if (m==0) { // 找到
    b = TRUE;
    return i;  
  } else {  // 沒(méi)找到
    b = FALSE;
    return i+1;
  }         
} // Locate

void InsertNewKey(IdxListType &idxlist, int i, HString wd) {//算法4.13
  int j;
  for (j=idxlist.last-1;  j>=i;  --j)  // 后移索引項(xiàng)
    idxlist.item[j+1] = idxlist.item[j];
  // 插入新的索引項(xiàng)
  StrCopy(idxlist.item[i].key, wd);    // 串賦值
  InitList(idxlist.item[i].bnolist);   // 初始化書(shū)號(hào)索引表為空表
  ++idxlist.last;
} // InsertNewKey

Status InsertBook(IdxListType &idxlist, int i, int bno) {  //算法4.14
  NLink p;
  if (!MakeNode (p, bno)) 
    return OVERFLOW;                   // 分配失敗
  Append(idxlist.item[i].bnolist, p);  // 插入新的書(shū)號(hào)索引
  return OK;
} // InsertBook

//------ 基本操作 -------
void InitIdxList(IdxListType &idxlist) {
  int i;
  idxlist.last= 0;
  for(i=0; i<MaxKeyNum+1; i++)
    InitList(idxlist.item[i].bnolist);
}

Status ExtractKeyWord(char* Buffer,WordListType &w,int &Num) {
  int i=0, j=0, k=0;
  bool Ignore;
  char TempChar[30];
  char IgnoreChar[7][10] = { "to","of","the","and","not","or","if" };
  w.last=0;
  while(*(Buffer+i)!= ' ') { TempChar[i]=*(Buffer+i);  i++; }
  i++;
  TempChar[i]= '\0';
  Num=atoi(TempChar);
  while(*(Buffer+i)!='\n' && *(Buffer+i)!='\0') { 
    // 每個(gè)字符串末尾都有作為結(jié)束符'\n'
    if(*(Buffer+i)!=' ') { // 若非空字符，則把當(dāng)前字符加入新的字符串中
      if(*(Buffer+i)>='A' && *(Buffer+i)<='Z')  // 大寫(xiě)字母轉(zhuǎn)換為小寫(xiě)
        *(Buffer+i)-='A'-'a';
      w.item[j][k]=*(Buffer+i);
      k++;  i++;
    } else {               // 如果是空字符，這是則開(kāi)始另一個(gè)字符串
      Ignore=false;
      w.item[j][k++]='\0';
      for (int m=0; m<7; m++)
        if(strcmp(w.item[j],IgnoreChar[m])==0) 
          { Ignore=true;  break; }
      if (!Ignore) { j++;  k=0;  i++;  w.last++; }
      else { k=0;  i++; }
    }
  }
  w.item[j][k++]='\0';     // 把最后一個(gè)字符串收尾
  Ignore=false;
  for (int m=0; m<7; m++)
    if (strcmp(w.item[j],IgnoreChar[m])==0) 
      { Ignore=true;  break; }
  if (!Ignore) w.last++;   // 并把最大數(shù)加1
  return OK;
}

void GetLine(FILE *f) {
  fgets(buf, MaxLineLen, f);  // buf是全局?jǐn)?shù)組變量
}

Status PutText(FILE *IdxFile, IdxListType MyIdx) { 
  int i,j,k;
  NLink p;
  for(i=0; i<MyIdx.last; i++) {
    for(j=0; j<MyIdx.item[i].key.length; j++)
      putc(*(MyIdx.item[i].key.ch+j ),IdxFile);
    putc('\t',IdxFile);
    if (MyIdx.item[i].key.length < 8) putc('\t',IdxFile);
    p = MyIdx.item[i].bnolist.head;
    for (k=0; k<MyIdx.item[i].bnolist.len; k++) {
      p = p->next;
      fprintf(IdxFile,"%03d",p->data);
      putc(' ', IdxFile);
    }
    putc('\n',IdxFile);
  }
  return OK;
}
	
void PrintFile(FILE *FileName) {  // 輔助函數(shù)
  char ch;
  rewind(FileName);
  ch=getc(FileName);
  while (ch!=EOF) {
    putchar(ch);
    ch=getc(FileName);
  }
  printf("\n");
  rewind(FileName);
}