数据结构4.2_串操作应用举例

数据结构4.2_串操作应用举例_建立词索引表

信息检索是计算机应用的重要领域之一。

举个例子图书馆书名检索系统；

一般来讲通过书名关键词检索读者感兴趣的书是很重要的。

因为读者一般不知道自己感兴趣的书的全名，可能会凭印象提供一些关键词。

那么检索系统就要求能够根据读者提供的关键词，显示所有含有该关键词的书目；

1、从书名文件中读取一个书名串；

2、从书名串中提取所有关键词到词表中；

3、对词表中的每一个关键词，再关键词索引表中进行查找并作相应的插入操作；

4、还有一个判断是否为关键词的机制，创建一个常用词表（an、a、of、the），如果从书名提取出的词不与常用词表中任意词相等，即为关键词；

5、再索引表中查询关键词可能出现以下情况：

　　1）索引表中已有此关键词的索引项，只要在该项中插入书号索引即可；

　　2）需在索引表中插入词关键词的索引项，插入应按照词典有序原则进行；

首先设定数据结构：

词表是一个线性表，因为一本书名只有若干个关键词，其数量有限，则采用顺序存储结构即可。每个词都是一个字符串。

索引表是一个有序表，在生成过程中需要频繁进行插入操作；索引表也为了查找用，为了提高查找效率，应采用顺序存储结构；

索引表中每个索引项包含两个内容：其一是关键词；其二是书号索引；

　　关键词：索引表是常驻机构，采用堆分配存储表示的串类型；

　　书号索引：书号索引在索引表的生成过程中逐个插入，且不同关键词的书号索引个数不等，甚至可能相差很多，宜采用链表结构的线性表；

首先定义一下数据结构和基本操作：

 1 #define MaxBookNum  1000     //假设只对1000本书建立索引表
 2 #define MaxKeyNum    2500     //索引表的最大长度
 3 #define MaxLineLen     500      //书名串最大长度
 4 #define MaxWordNum  10        //词表最大容量
 5 
 6 typedef struct{
 7     char *item[];    //字符串的数组
 8     int last;            //词表长度
 9 }WordListType;   //词表类型
10 
11 
12 typedef struct{
13     HString  key;       //关键词
14     LinkList  bnolist;  //存放书号索引的链表
15 }IdxTermType；  //定义索引项
16 
17 typedef int ElemType；   //定义链表的数据元素类型为整型
18 
19 typedef struct{
20     IdxTermType  item[MaxKeyNum+1];
21     int    last;
22 }IdxListType    //索引表类型
23 
24 char * buf;  //书名串缓冲区
25 WordListType  wdlist;  //词表
26 
27 //初始化操作，置索引表为空表，且在idxlist.item[0]设一空串
28 void InitIdxList(IdxListType &idxlist);
29 
30 //从文件f读入一个书目到书目串缓冲区buf
31 void GetLine(FILE f)
32 
33 //从buf中提取书名关键词到词表wdlist,书号存入bno
34 void ExtractKeyWord(ElemType &bno)
35 
36 
37 //将书号为bno的书名关键词按词典顺序插入索引表idxlist
38 Status InsIdxList(IdxListType &idxlist,  ElemType bno)
39 
40 //将生成的索引表idxlist输出到文件g中
41 void PutText(FILE g, IdxListType idxlist)

这个词表用来把书目（书名）串，拆解成一个个词，存放到词表中。这里是将其作为一个缓冲区存在；

插入书号索引表的函数中首先要检索词表中的词是否为关键词，是关键词的话再插入；

这里先建立一个主函数：

 1 void main() {
 2     if(f=openf("BookInfo.txt","r")) 
 3         if(g=openf("BookIdx.txt","w")){
 4             InitIdxList(idxlist); //初始化索引表idxlist为空表
 5             while(!feof(f)){
 6                 GetLine(f); //从文件f中读入一个书目信息到buf
 7                 ExtractKeyWord(BookNo); //从buf提取关键词到词表，书号存入BookNo中
 8                 InsIdxList(idxlist, BookNo); //将书号为BookNo的关键词插入索引表
 9             }
10             PutText(g, idxlist); //将生成的索引表idxlist输出到文件g 
11         }
12 }

为实现上述操作，要先把InsIdxList实现：

 1 //用wd返回wdlist词表中的第i个关键词
 2 void GetWord(int i, HString &wd)
 3 
 4 //在索引表idxlist中查询是否存在与wd相等的关键词。
 5 //若存在，则返回其在索引表中的位置，且b取值TRUE；否则返回插入位置，且b取值FALSE；
 6 int Locate(IdxListType idxlist, HString wd, Boolean b)
 7 
 8 
 9 //在索引表idxlist的第i项插入新关键词wd，并初始化书号索引的链表为空 
10 void InserNewKey();
11 
12 //在索引表idxlist的第i项插入书号为bno索引
13 Status InsertBook();
14 
15 
16 Status InsIdxList(IdxListType &idxlist, int bno){
17     for(i=0; i<wdlist.list; ++i){
18         GetWord(i,wd);
19         j=Locate(idxlist,wd,b);
20         if(!b) InserNewKey(idxlist, j, wd)；   //插入新的索引项
21         if(!InsertBook(idxlist,j,bno)) return OVERFLOW;   //插入书号索引
22     }
23     return OK;
24 }

 1 void GetWord(int i, HString &wd){
 2     p=*(wdlist.item+i);  //取词表中第i个字符串
 3     StrAssign(wd,p);     //生成关键词字符串
 4 }
 5 
 6 
 7 
 8 int Locate(IdxListType &idxlist, HString wd, Boolean &b){
 9     for(i=idxlist.last-1; m=StrCompare(idxlist.item[i].key,wd)>0; --i);
10     if(m==0) {b=TRUE; return i;}   //找到
11     else{b=FALSE; return i+1;}
12 }
13 
14 
15 
16 void InserNewKey(int i, StrType wd){
17     for(j=idxlist.last-1;j>=i;--j)   //后移索引项
18         idxlist.item[j+1]=idxlist.item[j];
19     StrCopy(idxlist.item[i],wd);           //串赋值
20     InitIdxList(idxlist.item[i].bnolist);  //初始化书号索引表为空表
21     ++idxlist.last;
22 }
23 
24 
25 
26 Status InsertBook(IdxListType &idxlist, int i, int bno){
27     if(!MakeNode(p,bno)) return ERROR;   //分配失败
28     Appand(idxlist.item[i].bnolist, p);    //插入新的书号索引
29     return OK;
30 }