C语言数据结构-algo4-4.c

blake

1. /* algo4-4.c 生成书名关键词索引文件bookidx.txt，算法4.9～4.14 */
   
2. /* 为运行algo4-5.c做准备 */
   
3. #include "c1.h"
   
4. typedef int ElemType;
   
5. #include"c2-5.h"
   
6. #include"bo2-6.c"
   
7. #include"c4-2.h"
   
8. #include"bo4-2.c"
   
9. 
   
10. #define MaxKeyNum 25 /* 索引表的最大容量(关键词的最大数) */
    
11. #define MaxLineLen 51 /* 书目串(书名+书号)buf的最大长度 */
    
12. #define MaxWordNum 10 /* 词表(一本书的关键词)的最大容量 */
    
13. #define MaxNoIdx 10 /* 常用词(仅指大写)的最大数 */
    
14. typedef struct
    
15. {
    
16.    char *item[MaxWordNum]; /* 词表(字符串)指针数组 */
    
17.    int last; /* 词的数量 */
    
18. }WordListType; /* 词表类型(顺序表) */
    
19. 
    
20. typedef struct
    
21. {
    
22.    HString key; /* 关键词(堆分配类型,c4-2.h) */
    
23.    LinkList bnolist; /* 存放书号索引的链表(c2-5.h) */
    
24. }IdxTermType; /* 索引项类型 */
    
25. 
    
26. typedef struct
    
27. {
    
28.    IdxTermType item[MaxKeyNum+1];
    
29.    int last; /* 关键词的个数 */
    
30. }IdxListType; /* 索引表类型(有序表) */
    
31. 
    
32. typedef struct
    
33. {
    
34.    char *item[MaxNoIdx]; /* 常用词表指针数组 */
    
35.    int last; /* 常用词的数量 */
    
36. }NoIdxType; /* 常用词表类型(有序表) */
    
37. 
    
38. /* 全局变量 */
    
39. char buf[MaxLineLen+1]; /* 当前书目串(包括'\0') */
    
40. WordListType wdlist; /* 暂存一本书的词表 */
    
41. NoIdxType noidx; /* 常用词表 */
    
42. 
    
43. void InitIdxList(IdxListType *idxlist)
    
44. { /* 初始化操作，置索引表idxlist为空表，且在idxliat.item[0]设一空串 */
    
45.    (*idxlist).last=0;
    
46.    InitString(&(*idxlist).item[0].key); /* bo4-2.c */
    
47.    InitList(&(*idxlist).item[0].bnolist); /* bo2-6.c */
    
48. }
    
49. 
    
50. void ExtractKeyWord(int *BookNo)
    
51. { /* 从buf中提取书名关键词到词表wdlist，书号存入BookNo */
    
52.    int i,l,f=1; /* f是字符串结束标志 0: 结束 1: 未结束 */
    
53.    char *s1,*s2;
    
54.    if(buf[0]<'0'||buf[0]>'9') /* buf的首字母不是数字 */
    
55.      exit(OVERFLOW);
    
56.    for(i=1;i<=wdlist.last;i++) /* 释放上一个书目在词表wdlist的存储空间 */
    
57.    {
    
58.      free(wdlist.item[i]);
    
59.      wdlist.item[i]=NULL;
    
60.    }
    
61.    wdlist.last=0;
    
62.    *BookNo=(buf[0]-'0')*100+(buf[1]-'0')*10+(buf[2]-'0'); /* 前三位为书号 */
    
63.    s2=&buf[2]; /* s1指向书号的尾字符 */
    
64.    do
    
65.    { /* 提取书名关键词到词表wdlist */
    
66.      s1=s2+1; /* s1向后移动一个单词 */
    
67.      s2=strchr(s1,' '); /* s2指向s1的第一个空格,如没有,返回NULL */
    
68.      if(!s2) /* 到串尾 */
    
69.      {
    
70.        s2=strchr(s1,'\12'); /* s2指向buf的最后一个字符(回车符) */
    
71.        f=0;
    
72.      }
    
73.      l=s2-s1; /* 单词长度 */
    
74.      if(s1[0]>='A'&&s1[0]<='Z') /* 单词首字母为大写 */
    
75.      { /* 写入词表 */
    
76.        wdlist.item[wdlist.last]=(char *)malloc((l+1)*sizeof(char));
    
77.        /* 生成串空间(包括'\0') */
    
78.        for(i=0;i<l;i++)
    
79.          wdlist.item[wdlist.last][i]=s1[i]; /* 写入词表 */
    
80.        wdlist.item[wdlist.last][l]=0;
    
81.        for(i=0;i<noidx.last;i++) /* 查找是否为常用词 */
    
82.          if(!strcmp(wdlist.item[wdlist.last],noidx.item[i]))
    
83.            break;
    
84.        if(i!=noidx.last) /* 是常用词 */
    
85.        {
    
86.          free(wdlist.item[wdlist.last]); /* 从词表中删除该词 */
    
87.          wdlist.item[wdlist.last]=NULL;
    
88.        }
    
89.        else
    
90.          wdlist.last++; /* 词表长度+1 */
    
91.      }
    
92.    }while(f);
    
93. }
    
94. 
    
95. void GetWord(int i,HString *wd)
    
96. { /* 用wd返回词表wdlist中第i个关键词 */
    
97.    StrAssign(wd,wdlist.item[i]); /* 生成关键字字符串 bo4-2.c */
    
98. }
    
99. 
    
100. int Locate(IdxListType *idxlist,HString wd,Status *b)
     
101. { /* 在索引表idxlist中查询是否存在与wd相等的关键词。若存在,则返回其 */
     
102.    /* 在索引表中的位置,且b取值TRUE;否则返回插入位置,且b取值FALSE */
     
103.    int i,m;
     
104.    for(i=(*idxlist).last;(m=StrCompare((*idxlist).item[i].key,wd))>0;--i); /* bo4-2.c */
     
105.    if(m==0) /* 找到 */
     
106.    {
     
107.      *b=TRUE;
     
108.      return i;
     
109.    }
     
110.    else
     
111.    {
     
112.      *b=FALSE;
     
113.      return i+1;
     
114.    }
     
115. }
     
116. 
     
117. void InsertNewKey(IdxListType *idxlist,int i,HString wd)
     
118. { /* 在索引表idxlist的第i项上插入新关键词wd,并初始化书号索引的链表为空表 */
     
119.    int j;
     
120.    InitList(&(*idxlist).item[(*idxlist).last+1].bnolist); /* bo2-6.c */
     
121.    for(j=(*idxlist).last;j>=i;--j) /* 后移索引项 */
     
122.      (*idxlist).item[j+1]=(*idxlist).item[j];
     
123.    InitString(&(*idxlist).item[i].key); /* bo4-2.c */
     
124.    StrCopy(&(*idxlist).item[i].key,wd); /* 串拷贝插入新的索引项 bo4-2.c */
     
125.    InitList(&(*idxlist).item[i].bnolist); /* 初始化书号索引表为空表 bo2-6.c */
     
126.    (*idxlist).last++;
     
127. }
     
128. 
     
129. void InsertBook(IdxListType *idxlist,int i,int bno)
     
130. { /* 在索引表idxlist的第i项中插入书号为bno的索引 */
     
131.    Link p;
     
132.    if(!MakeNode(&p,bno)) /* 分配失败 bo2-6.c */
     
133.      exit(OVERFLOW);
     
134.    p->next=NULL;
     
135.    Append(&(*idxlist).item[i].bnolist,p); /* 插入新的书号索引 bo2-6.c */
     
136. }
     
137. 
     
138. void InsIdxList(IdxListType *idxlist,int bno)
     
139. { /* 将书号为bno的关键词插入索引表 */
     
140.    int i,j;
     
141.    Status b;
     
142.    HString wd;
     
143.    InitString(&wd); /* bo4-2.c */
     
144.    for(i=0;i<wdlist.last;i++)
     
145.    {
     
146.      GetWord(i,&wd);
     
147.      j=Locate(idxlist,wd,&b);
     
148.      if(!b)
     
149.        InsertNewKey(idxlist,j,wd); /* 插入新的索引项 */
     
150.      InsertBook(idxlist,j,bno); /* 插入书号索引 */
     
151.    }
     
152. }
     
153. 
     
154. void PutText(FILE *f,IdxListType idxlist)
     
155. { /* 将生成的索引表idxlist输出到文件f */
     
156.    int i,j;
     
157.    Link p;
     
158.    fprintf(f,"%d\n",idxlist.last);
     
159.    for(i=1;i<=idxlist.last;i++)
     
160.    {
     
161.      for(j=0;j<idxlist.item[i].key.length;j++)
     
162.        fprintf(f,"%c",idxlist.item[i].key.ch[j]);
     
163.      fprintf(f,"\n%d\n",idxlist.item[i].bnolist.len);
     
164.      p=idxlist.item[i].bnolist.head;
     
165.      for(j=1;j<=idxlist.item[i].bnolist.len;j++)
     
166.      {
     
167.        p=p->next;
     
168.        fprintf(f,"%d ",p->data);
     
169.      }
     
170.      fprintf(f,"\n");
     
171.    }
     
172. }
     
173. 
     
174. void main()
     
175. {
     
176.    FILE *f; /* 任何时间最多打开一个文件 */
     
177.    IdxListType idxlist; /* 索引表 */
     
178.    int BookNo; /* 书号变量 */
     
179.    int k,l;
     
180.    f=fopen("NoIdx.txt","r"); /* 打开常用词文件 */
     
181.    if(!f)
     
182.      exit(OVERFLOW);
     
183.    fscanf(f,"%d",&noidx.last); /* 常用词个数 */
     
184.    for(k=0;k<noidx.last;k++) /* 把常用词文件的内容拷到noidx中 */
     
185.    {
     
186.      fscanf(f,"%s",buf);
     
187.      l=strlen(buf);
     
188.      noidx.item[k]=(char*)malloc(l*sizeof(char));
     
189.      strcpy(noidx.item[k],buf);
     
190.    }
     
191.    fclose(f);
     
192.    f=fopen("BookInfo.txt","r"); /* 打开书目文件 */
     
193.    if(!f)
     
194.      exit(FALSE);
     
195.    InitIdxList(&idxlist); /* 初始化索引表idxlist为空 */
     
196.    wdlist.last=0; /* 词表长度初值为0 */
     
197.    while(!feof(f))
     
198.    {
     
199.      fgets(buf,MaxLineLen,f);
     
200.      l=strlen(buf);
     
201.      if(l<=1)
     
202.        break;
     
203.      ExtractKeyWord(&BookNo); /* 从buf中提取关键词到词表，书号存入BookNo */
     
204.      InsIdxList(&idxlist,BookNo);
     
205.    }
     
206.    fclose(f);
     
207.    f=fopen("BookIdx.txt","w");
     
208.    if(!f)
     
209.      exit(INFEASIBLE);
     
210.    PutText(f,idxlist); /* 将生成的索引表idxlist输出到文件f */
     
211.    fclose(f);
     
212. }

复制代码