[串](1.1)建立词索引表
信息检索是计算机应用的重要领域之一由于信息检索的主要操作是在大量的存放在磁盘上的信息中查询一个特定的信息，为了提高查询效率，一个重要的问题是建立一个好的索引系统。
例如图书馆书目检索系统中有三张索引表，分别可按书名、作者名和分类号编排，在实际系统中，按书名检索并不方便，因为很多内容相似的书籍其书名不一定相同，因此较好的办法是建立“书名关键词索引”
例如下图（A）中书目相应的关键词索引如图（B）所示，读者很容易从关键词索引表中查询到他所感兴趣的书目，为了便于查询，可设定此索引表按词典有序的线性表，算法主要实现为如何从书目文件生成这个有序词表
重复下列操作直至文件结束：
- 从书目文件中读入一个书目串
- 从书目串中提取所有关键词插入词表
- 对词表中的每一个关键词，在索引表中进行查找并作相应的插入操作
为识别从书名串中分离出来的单词是否是关键词，需要一张常用词表(如“an”、“a”、“of”、“the”等词)顺序扫描书名串，首先分离单词，然后查找常用词表，若不和表中任一词相等，则为关键词，插入临时存放关键词的词表中
在索引表中查询关键词时可能出现两种情况：
- 一是索引表上以有此关键词的索引项，只要在该项中插入书号索引即可
- 二是需在索引表中插入此关键词的索引项，插入应按字典有序原则进行
首先设定数据结构：
词表为线性表，只存放一本书的书名中的若干关键词，其数量有限，则采用是顺序存储结构即可，其中每个词是一个字符串
索引表为有序表，虽是动态生成，在生成过程中需频繁进行插入操作，但考虑索引表主要为查找用，为了提高查找效率，宜采用顺序存储结构，表中每个索引项包含两个内容：
- 一是关键词，因为索引表为常驻结构，则应考虑节省存储，采用堆分配存储表示的串类型
- 其二是书号索引，由于书号索引是在索引表的生成过程中逐个插入，且不同关键词的书号索引个数不等，甚至可能相差很多，则采用链表结构的线性表
逻辑图像表明如下：
从图中我们可以看到，索引表为一结构数组，数组元素包括了存放书本关键词的字符串和存储包含此关键词的链表。
我们需要完成的操作为：单链的插入和查找是否有重复，索引表的排序功能，字符串的查找是否有重复，索引表按词典顺序排列的插入功能。
这种结构嵌套难处理的就是逻辑，逻辑结构弄清楚后，就好处理了，链表的类型和字符串的类型相同，索引表又采用的静态数组结构。按照书本上的思路如下代码：
#define _CRT_SECURE_NO_WARNINGS
#define MaxBookNum 1000//假设只对1000本书建立索引表
#define MaxKeyNum 2500 //索引表的最大容量
#define MaxLineLen 500 //书目串的最大长度
#define MaxWordNum 10//词表的最大容量
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
char* ch;//堆分配字符串
int length;
}HString;
typedef struct node
{
char* number;//书号链表
struct node* next;
}Node,*LinkList;
typedef struct
{
char* item[MaxWordNum];//字符串数组
int last;//词表的长度
}WordListType;
typedef struct
{
HString key;
LinkList bonlist;
}IdxTermType;
typedef struct
{
IdxTermType item[MaxKeyNum + 1];
int last;
}IdxListType;
char* buf;
WordListType wdlist;
LinkList node;
void InitIdxList(IdxListType* idxlist);//初始化索引表
void GetLine(FILE* f);//从文件中读取一字符串
int VisitList(LinkList* L, char* bon);//观察书号表中是否有重复的书号
int Used(char* temp);//判断是否为常用表中的字符
void ExtractKeyWord(char* bon);//分割字符串，将关键词读入wdlist词表中
void InitList(LinkList* L);//初始化书号链表，带头结点
void InsertList(LinkList* L, char* bon);//插入新的书号
int Locate(IdxListType idxlist, char* e);//判断索引表中是否已存在此关键词，如存在，返回该关键词位置，否则返回-1
void InsertNewkey(IdxTermType* temp, char* e);//插入新的关键词
int FondInsert(IdxListType* idxlist, char e);//找到插入位置，按字典原则有序进行
void MoveArr(IdxListType* idxlist, int i);//移动索引表数组元素
void InsIdxList(IdxListType* idxlist, char* bon);//将书号为bon的关键词按词典顺序插入索引表idxlist
void PutText(FILE* g, IdxListType* idxlist);//将文件导出到新的文本中
FILE* fp;
FILE* fg;
int main()
{
IdxListType idxlist;
buf = (char*)malloc(sizeof(char) * MaxLineLen);
char BookNo[20];
if (fp = fopen("BookInfo.txt", "r"))
{
if (fg = fopen("BookIdx.txt", "w"))
{
InitIdxList(&idxlist);
idxlist.last = 0;
while (!feof(fp))
{
GetLine(fp);
ExtractKeyWord(BookNo);
InsIdxList(&idxlist, BookNo);
}
}
PutText(fg, &idxlist);
}
fclose(fp);
system("pause");
return 0;
}
void InitIdxList(IdxListType* idxlist)
{
idxlist = (IdxListType*)malloc(sizeof(IdxListType));
idxlist->last = 0;
}
void GetLine(FILE* f)
{
fgets(buf, 1000, f);
printf("%s", buf);//观察文件字符串
int k = strlen(buf);
for (int i = 0; i < k; i++)//方便操作清除尾部换行符
{
if (buf[i] == '\n')
{
buf[i] = '\0';
break;
}
}
}
int VisitList(LinkList* L, char* bon)
{
LinkList p = (*L)->next;
while (p != NULL)
{
if (!strcmp(p->number, bon))
{
return 0;
}
p = p->next;
}
return 1;
}
int Used(char* temp)
{
int k;
k = strcmp("an", temp);
if (k == 0)
{
return 0;
}
k = strcmp("a", temp);
if (k == 0)
{
return 0;
}
k = strcmp("of", temp);
if (k == 0)
{
return 0;
}
k = strcmp("the", temp);
if (k == 0)
{
return 0;
}
k = strcmp("and", temp);
if (k == 0)
{
return 0;
}
k = strcmp("The", temp);
if (k == 0)
{
return 0;
}
k = strcmp("to", temp);
if (k == 0)
{
return 0;
}
return 1;
}
void ExtractKeyWord(char* bon)
{
char temp[100];
int i = 0, j;
while (buf[i] != '\0')
{
j = 0;
while (buf[i] != ' ' && buf[i] != '\0')
{
temp[j] = buf[i];
i++;
j++;
}
temp[j] = '\0';
if (temp[0] >= '0' && temp[0] <= '9')
{
strcpy(bon, temp);
i++;
continue;
}
if (Used(temp))
{
wdlist.item[wdlist.last] = (char*)malloc(sizeof(char) * (strlen(temp) + 1));
strcpy(wdlist.item[wdlist.last], temp);
wdlist.last++;
i++;
}
else
{
i++;
}
memset(temp, 0, sizeof(temp));
}
memset(buf, 0, sizeof(buf));
/*
for (int i = 0; i <= wdlist.last; i++)
{
printf("%s\n", wdlist.item[i]);
}
system("pause");
*/
}
/*链表处理*/
void InitList(LinkList* L)
{
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
}
void InsertList(LinkList* L, char* bon)
{
node = (LinkList)malloc(sizeof(Node));
node->next = NULL;
node->number = (char*)malloc(sizeof(char) * MaxBookNum);
strcpy(node->number, bon);
LinkList p;
p = (*L);
while (p->next != NULL)
{
p = p->next;
}
p->next = node;
}
int Locate(IdxListType idxlist, char* e)
{
for (int i = 0; i < idxlist.last; i++)
{
if (!strcmp(idxlist.item[i].key.ch, e))
{
return i;
}
}
return -1;
}
void InsertNewkey(IdxTermType* temp, char* e)
{
temp->key.length = strlen(e);
temp->key.ch = (char*)malloc(sizeof(char) * strlen(e));
strcpy(temp->key.ch, e);
}
int FondInsert(IdxListType* idxlist, char e)//找到插入位置
{
int i = 0;
if (idxlist->last == 0)
{
return 0;
}
for (i = 0; i < idxlist->last; i++)
{
if (idxlist->item[i].key.ch[0] > e)
{
return i;
break;
}
}
return i;
}
void MoveArr(IdxListType* idxlist, int i)//移动索引表数组元素
{
for (int k = idxlist->last - 1; k >= i; k--)
{
idxlist->item[k + 1] = idxlist->item[k];
}
}
void InsIdxList(IdxListType* idxlist, char* bon)
{
char p;
int k;
for (int i = 0; i < wdlist.last; i++)
{
p = wdlist.item[i][0];
if (Locate(*idxlist, wdlist.item[i]) != -1)
{
k = Locate(*idxlist, wdlist.item[i]);
if (VisitList(&idxlist->item[k].bonlist, bon))
{
InsertList(&idxlist->item[k].bonlist, bon);
}
}
else
{
k = FondInsert(idxlist, p);
MoveArr(idxlist, k);
InitList(&idxlist->item[k].bonlist);
InsertNewkey(&idxlist->item[k], wdlist.item[i]);
if (VisitList(&idxlist->item[k].bonlist, bon))
{
InsertList(&idxlist->item[k].bonlist, bon);
}
idxlist->last++;
}
}
memset(wdlist.item, 0, sizeof(wdlist.item));
wdlist.last = 0;
}
void PutText(FILE* g, IdxListType* idxlist)
{
for (int i = 0; i < idxlist->last; i++)
{
fprintf(g, "%s ", idxlist->item[i].key.ch);
LinkList p = idxlist->item[i].bonlist->next;
while (p != NULL)
{
fprintf(g, "%s ", p->number);
p = p->next;
}
fprintf(g, "\n");
}
}需要注意的点就在
这段代码中，由于每本书的关键词都是先分割完关键词存入临时词表wdlist中，再载入idlist索引表中，所以在结束函数的时候需要将wdlist.item数组清0
首先先判断索引表中是否已存在wdlist中的关键词，若存在，则只需要添加书号即可
若不存在，则用wdlist词表中关键词的首字母去遍历，找到合适的插入位置，再移动数组元素，进行插入进去。
以上调用了string操作：strlen，strcmp，strcpy函数等为了方便我直接调用了库函数，自定义函数如下所示
int StrLength(char* a)
{
int i = 0;
while (a[i] != '\0')
{
i++;
}
return i;
}
int StrComper(char* a, char* b)
{
int i = 0;
while (a[i] && b[i])
{
if (a[i] > b[i])
{
return 1;
}
if (a[i] < b[i])
{
return -1;
}
i++;
}
if (a[i])
{
return 1;
}
if (b[i])
{
return -1;
}
return 0;
}
void StrCopy(char* a, char* b)
{
int i;
for (i = 0; i < StrLength(b); i++)
{
a[i] = b[i];
}
a[i] = '\0';
}