建立词索引表.doc

005 Computer Data Structure010 Introduction to Data Structure023 Fundamental of Data Structure034 The Design and Analysis of Computer Algorithms050 Introduction to Numerical Analysis067 Numerical Analysisalgorithms 034,analysis 034,050,067,computer 005,034,data 005,010,023,design 034,fundamental 023,introduction 010,050,numerical 050,067,structure 005,010,023,#include#include #include#include/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int Boolean;#define MaxBookNum1000/ 假设只对 1000 本书建立词索引表#define MaxKeyNum2500/ 索引表的最大容量#define MaxLineLen500/ 书目串的最大长度#define MaxWordNum10/ 词表的最大容量#define MaxWordLen 100/ 关键词的最大长度typedef struct char* ch;/ 若是非空串, 则按串长分配存储区, 否则 ch 为 NULLint length;/ 串长度HString;typedef struct char* itemMaxWordNum;/ 字符串的数组int last;/ 词表的长度WordListType;/ 词表类型(顺序表)typedef int ElemType;/ 定义链表的数据元素类型为整型(书号类型)typedef struct LNode ElemType data3;/ 书号(三位数字)struct LNode *next;/ 指向下一个书号*Link,*LinkList;typedef struct HString key;/ 关键词LinkList bnolist;/ 存放书号索引的链表IdxTermType;/ 索引项类型typedef struct IdxTermType itemMaxKeyNum + 1;int last;IdxListType;/ 索引表类型(有序表)/主要变量char* buf;/ 书目串缓冲区char cMaxLineLen;int BookNo3;/ 书号char * No=and,of,if,the,to,many,more; / 常用词表WordListType wdlist;/ 词表IdxListType idxlist;/ 索引表/*/基本操作Status StrAssign(HString &T, char* chars);/ 生成一个其值等于串常量 chars 的串 Tint StrCompare(HString S, HString T);/ 若 ST , 则返回值 0 ; 若 S=T , 则返回值 =0 ; 若 ST , 则返回值 0 ; void StrCopy(HString &S, HString &T);/ 复制 T 到 S void InitIdxList(IdxListType &idxlist);/ 初始化操作, 置索引表 idxlist 为空表, 且在 idxlist.item0 设一空串Status GetLine(FILE* f);/ 从文件 f 读入一个书目信息到书目串缓冲区 bufvoid ExtractKeyWord(ElemType &bno);/ 从 buf 中提取书名关键字到词表 wdlist, 书号存入 bnoStatus InsIdxList(IdxListType &idxlist, ElemType bno);/ 将书号为 bno 的书名关键词按词典顺序插入索引表 idxlistvoid PutText(FILE g, IdxListType idxlist);/ 将生成的索引表 idxlist 输出到文件 gStatus InitList(LinkList &L);/ 初始化书号索引表为空表void InitWordList(WordListType &wdlist);/ 初始化词表Status IsKeyWord(char *wd);/ 判断是否为关键词Status MakeNode(Link &t,ElemType e);/ 初始化新的书号索引结点Status Appand(LinkList &L,Link s);/ 在关键词后插入新的书号结点void GetWord(int i, HString &wd);/ 用 wd 返回词表 wdlist 中第 i 个关键词int Locate(IdxListType idxlist, HString wd, Boolean &b);/ 在索引表 idxlist 中查询是否存在与 wd 相等的关键词。 若存在,则返回其在/ 索引表中的位置, 且 b 取值 TRUE; 否则返回插入位置, 且 b 取值 FALSEvoid InsertNewKey(IdxListType &idxlist, int i, HString wd);/ 在索引表 idxlist 的第 i 项上插入新关键词 wd, 并初始化书号索引的链表为空表Status InsertBook(IdxListType &idxlist, int i, int bno);/ 在索引表 idxlist 的第 i 项中插入书号为 bno 的索引*/Status StrAssign(HString &T, char* chars) int i;char *c;if(T.ch)free(T.ch);/ 释放 T 原有的空间for(i=0, c=chars; c!=/0; i+,c+)printf(%c, c);/ 求 chars 的长度 iif(!i)T.ch = NULL;T.length = 0;else if(!(T.ch = (char*)malloc(i*sizeof(char)return OVERFLOW;T.length = i;for(i=0; iT.length; i+)T.chi = charsi;T.chi=/0;return OK;/ StrAssignint StrCompare(HString S, HString T)int i;for(i=0; iS.length & iT.length; i+)if(S.chi != T.chi)return S.chi - T.chi;return S.length - T.length;/ StrComparevoid StrCopy(HString &S,HString &T)int i;if(T.ch=NULL)S.ch=NULL;S.length=0;elsefor(i=0;iT.length;i+)S.chi=T.chi;S.chi=/0;S.length=T.length;/ StrCopyvoid GetWord(int i, HString &wd)/char* p;/p = *(wdlist.item + i);/ 取词表中第 i 个字符串/StrAssign(wd, p);/ 生成关键字字符串char *t=&(*wdlist.itemi);int n;for(n=0;*t!=/0;n+)t+;wd.length=n;for(n=0;n0; i-);if(m = 0) / 找到b = TRUE;return i;else b = FALSE;return i+1;/ LocateStatus InitList(LinkList &L) int i;if(!(L=(Link)malloc(sizeof(LNode)return OVERFLOW;for(i=0; idatai = (int)malloc(sizeof(int) return OVERFLOW;L-next=NULL;return OK;/ InitListvoid InsertNewKey(IdxListType &idxlist,int i,HString &wd)int j;for(j = idxlist.last-1; j=i; j-) / 后移索引项StrCopy(idxlist.itemj+1.key,idxlist.itemj.key);idxlist.itemj+1.bnolist = idxlist.itemj.bnolist;/ 插入新的索引项StrCopy(idxlist.itemi.key, wd);/ 串赋值InitList(idxlist.itemi.bnolist);/ 初始化书号索引表为空表idxlist.last +;/ InsertNewKeyStatus MakeNode(Link &t,ElemType e)int i;if(!(t = (Link)malloc(sizeof(LNode)return OVERFLOW;else for(i=0;idatai=ei;t-next=NULL;return OK;/ MakeNodeStatus Appand(LinkList &L,Link s)Link q = L;if(!s)return ERROR;while(q-next)q=q-next;q-next=s;return OK;/ AppandStatus InsertBook(IdxListType &idxlist, int i, int bno) Link p;if(!MakeNode(p, bno)return ERROR;/ 分配失败Appand(idxlist.itemi.bnolist, p);/ 插入新的书号索引return OK;/ InsertBookvoid Init_HString(HString &wd)wd.ch=(char *)malloc(MaxWordLen*sizeof(char);for(int e=0; eMaxWordLen; e+)wd.che=/0;wd.length=0;Status InsIdxList(IdxListType &idxlist, int bno) int i, j, b;HString wd;Init_HString(wd);for(i=0; iwdlist.last; i+)GetWord(i, wd);j = Locate(idxlist, wd, b);if(!b)InsertNewKey(idxlist, j, wd);/ 插入新的索引项if(!InsertBook(idxlist, j, bno)/ 插入书号索引return OVERFLOW;return OK;/ InsertIdxListStatus GetLine(FILE* f)int i;buf = c;if(!feof(f)for(i=0; (ci=fgetc(f)!=EOF&ci!=/n&iMaxLineLen; i+);ci=/0;return OK;else return ERROR;void InitWordList(WordListType &wdlist)int i,j;for(i=0;iMaxWordNum;i+)wdlist.itemi = (char *)malloc(MaxWordLen*sizeof(char);for(j=0; jMaxWordLen; j+)wdlist.itemij=/0;wdlist.last=0;Status IsKeyWord(char *wd)int i;for(i=0; Noi!=NULL; i+)if(!strcmp(Noi,wd)return FALSE;return TRUE;void ExtractKeyWord(int BookNo3) int i = 0,j,k;char charsMaxWordLen;while(*buf!= )BookNoi = *buf - 0;buf+;i+;InitWordList(wdlist);int m=0;for(i=0; *buf!=/0&wdlist.lastMaxWordNum;i+)while(*buf= )buf+;for(j=0; *buf!= &*buf!=/0&*(&(*buf)!=/n; j+)/if(isSupper(*buf)charsj = tolower(*buf);/else/charsj = *buf;buf+;charsj=/0;if(IsKeyWord(chars)for(k=0;kj;k+)wdlist.itemmk = charsk;m+;wdlist.last+;void PutText(FILE* g,IdxListType idxlist)int i,j;for(i=0; inext;while(t)for(