為書庫創(chuàng)建查詢索引表

建立詞索引表基本步驟：

　　1、從書目文件中讀入一個(gè)書目單。

　　2、從書目單中提取所有關(guān)鍵字插入詞表。

　　3、對(duì)詞表中的每一個(gè)關(guān)鍵字在索引表中進(jìn)行查找并作相應(yīng)的插入操作。

詳細(xì)操作：

　　1、為識(shí)別從書名串中分離出來的單詞是否是關(guān)鍵字，需要一張常用詞表。順序掃描書目單，首先分離單詞，然后查找常用詞表，若不和表中任一詞相等，則為關(guān)鍵字，插入臨時(shí)存放關(guān)鍵字的詞表中。

　　2、在索引表中查詢關(guān)鍵字時(shí)可能出現(xiàn)兩種情況：其中一種是索引表上已經(jīng)有此關(guān)鍵詞的索引項(xiàng)，只要在該項(xiàng)中插入書號(hào)索引即可；其二是需要在索引表中插入此關(guān)鍵詞的索引項(xiàng)，插入應(yīng)按字典有序原則插入。

　　3、首先定義存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)：詞表為線性表，只存放一本書的書名中若干個(gè)關(guān)鍵字，其數(shù)量有限，采用順序存儲(chǔ)結(jié)構(gòu)即可，其中每個(gè)詞是一個(gè)字符串。索引表為有序表，雖是動(dòng)態(tài)生成，在生成過程中需頻繁進(jìn)行插入操作，但考慮索引表主要為查找用，為了提高查找效率，采用順序存儲(chǔ)結(jié)構(gòu)；表中每隔索引項(xiàng)包含兩個(gè)內(nèi)容：其一是關(guān)鍵詞，因索引表為常駐內(nèi)存，則考慮節(jié)省存儲(chǔ)，采用堆分配存儲(chǔ)表示的串類型；其二是書號(hào)索引，由于書號(hào)索引是在索引表生成過程中逐個(gè)插入，且不同關(guān)鍵詞的書號(hào)索引個(gè)數(shù)不等，甚至可能相差很多，則宜采用鏈表結(jié)構(gòu)的線性表。

代碼實(shí)現(xiàn)部分：

ConcordanceList.cpp

1 #include "ChainedList.h" 2 #include "HeapString.h" 3 4 #include <conio.h> 5 6 #define MaxBookNum 1000 // 假設(shè)只對(duì)1000本書建索引表 7 #define MaxKeyNum 2500 // 索引表的最大容量 8 #define MaxLineLen 500 // 書目串的最大長度 9 #define MaxWordNum 10 // 詞表的最大容量 10 #define MaxWordLength 30 // 單詞的最大長度 11 12 typedef int Boolean; 13 typedef int Status; 14 15 typedef struct { 16 char item[MaxWordNum][MaxWordLength]; // 字符串的數(shù)組 17 int last; // 詞表的長度 18 } WordListType; // 詞表類型（順序表） 19 20 typedef struct { 21 HString key; // 關(guān)鍵詞 22 LinkList bnolist; // 存放書號(hào)索引的鏈表 23 } IdxTermType; // 索引項(xiàng)類型 24 25 typedef struct { 26 IdxTermType item[MaxKeyNum+1]; 27 int last; 28 } IdxListType; // 索引表類型（有序表） 29 30 //------ 基本操作 ------ 31 void InitIdxList(IdxListType &idxlist); 32 // 初始化操作，置索引表idxlist為空表，即idxlist.last=0, 33 // 且在idxlist.item[0]設(shè)一空串 34 void GetLine(FILE *f); 35 // 從文件f讀入一個(gè)書目信息到書目串緩沖區(qū)buf 36 Status ExtractKeyWord(char *Buffer, WordListType &w, int &bno); 37 // 從buf中提取書名關(guān)鍵詞到詞表wdlist，書號(hào)存入bno 38 Status InsertIdxList(IdxListType &idxlist, ElemType bno); 39 // 將書號(hào)為bno的書名關(guān)鍵詞按詞典順序插入索引表idxlist 40 Status PutText(FILE *g, IdxListType idxlist); 41 // 將生成的索引表idxlist輸出到文件g 42 void PrintFile(FILE *FileName); 43 44 Status InsertIdxList(IdxListType &idxlist, int bno); 45 // 索引表插入算法 46 void GetWord(int i, HString &wd); 47 // 用wd返回詞表wdlist中第i個(gè)關(guān)鍵詞。 48 int Locate(IdxListType &idxlist, HString wd, Boolean &b); 49 // 在索引表idxlist中查詢是否存在與wd相等的關(guān)鍵詞。 50 // 若存在，則返回其在索引表中的位置， 51 // 且b取值TRUE；否則返回插入位置，且b取值FALSE 52 void InsertNewKey(IdxListType &idxlist, int i, HString wd); 53 // 在索引表idxlist的第i項(xiàng)上插入新關(guān)鍵詞wd， 54 // 并初始化書號(hào)索引的鏈表為空表 55 Status InsertBook(IdxListType &idxlist, int i, int bno); 56 // 在索引表idxlist的第i項(xiàng)中插入書號(hào)為bno的索引 57 58 //------ 主要變量 ------ 59 char buf[MaxLineLen]; // 書目串緩沖區(qū) 60 WordListType wdlist; // 詞表 61 IdxListType idxlist; // 索引表 62 63 //------ 主函數(shù) ------ 64 int main(int argc, char* argv[]) { 65 FILE *f,*g; 66 int BookNo; 67 if ((f = fopen("BookInfo.txt", "r"))==NULL) { 68 printf("ERROR in open BookInfo.txt!\n"); 69 exit(1); 70 } 71 if ((g = fopen ("BookIdx.txt", "w"))==NULL) { 72 printf("ERROR in open BookIdx.txt!\n"); 73 exit(1); 74 } 75 printf("書目文件：\n"); 76 PrintFile(f); 77 InitIdxList(idxlist); // 初始化索引表idxlist為空表 78 while (!feof (f)) { 79 GetLine (f); // 從文件f讀入一個(gè)書目信息到buf 80 ExtractKeyWord(buf,wdlist,BookNo); 81 // 從buf提取關(guān)鍵詞到詞表，書號(hào)存入BookNo 82 InsertIdxList(idxlist, BookNo); // 書號(hào)為BookNo的關(guān)鍵詞插入索引表 83 } 84 PutText(g, idxlist); // 將生成的索引表idxlist輸出到文件g 85 fclose(f); 86 fclose(g); 87 printf("對(duì)書目文件進(jìn)行處理后的索引文件：\n"); 88 if ((g = fopen ("Algo0409BookIdx.txt", "r"))==NULL) { 89 printf("ERROR in open BookIdx.txt!\n"); 90 exit(1); 91 } 92 PrintFile(g); 93 fclose(g); 94 printf("按任意鍵，結(jié)束 ......\n"); 95 getch(); 96 return 0; 97 } // main 98 99 Status InsertIdxList(IdxListType &idxlist, int bno) { 100 int i,j; 101 HString wd; 102 Boolean b; 103 for (i=0; i<wdlist.last; i++) { 104 GetWord(i, wd); 105 j = Locate(idxlist, wd, b); 106 if (!b) 107 InsertNewKey(idxlist, j, wd); // 插入新的索引項(xiàng) 108 InsertBook(idxlist, j, bno); // 插入書號(hào)索引 109 } 110 return OK; 111 } // InsertIdxList 112 113 void GetWord(int i, HString &wd) { 114 char *p; 115 p = *(wdlist.item +i); // 取詞表中第i個(gè)字符串 116 StrAssign(wd, p); // 生成關(guān)鍵字字符串 117 } // GetWord 118 119 int Locate(IdxListType &idxlist, HString wd, Boolean &b) { 120 int i,m; 121 for (i = idxlist.last-1; 122 ((m = StrCompare(idxlist.item[i].key, wd)) > 0); --i); 123 if (m==0) { // 找到 124 b = TRUE; 125 return i; 126 } else { // 沒找到 127 b = FALSE; 128 return i+1; 129 } 130 } // Locate 131 132 void InsertNewKey(IdxListType &idxlist, int i, HString wd) { 133 int j; 134 for (j=idxlist.last-1; j>=i; --j) // 后移索引項(xiàng) 135 idxlist.item[j+1] = idxlist.item[j]; 136 // 插入新的索引項(xiàng) 137 StrCopy(idxlist.item[i].key, wd); // 串賦值 138 InitList(idxlist.item[i].bnolist); // 初始化書號(hào)索引表為空表 139 ++idxlist.last; 140 } // InsertNewKey 141 142 Status InsertBook(IdxListType &idxlist, int i, int bno) { 143 Link p; 144 if (!MakeNode (p, bno)) 145 return OVERFLOW; // 分配失敗 146 Append(idxlist.item[i].bnolist, p); // 插入新的書號(hào)索引 147 return OK; 148 } // InsertBook 149 150 //------ 基本操作 ------- 151 void InitIdxList(IdxListType &idxlist) { 152 int i; 153 idxlist.last= 0; 154 for(i=0; i<MaxKeyNum+1; i++) 155 InitList(idxlist.item[i].bnolist); 156 } 157 158 Status ExtractKeyWord(char* Buffer,WordListType &w,int &Num) { 159 int i=0, j=0, k=0; 160 bool Ignore; 161 char TempChar[30]; 162 char IgnoreChar[7][10] = { "to","of","the","and","not","or","if" }; 163 w.last=0; 164 while(*(Buffer+i)!= ' ') { TempChar[i]=*(Buffer+i); i++; } 165 i++; 166 TempChar[i]= '\0'; 167 Num=atoi(TempChar); 168 while(*(Buffer+i)!='\n' && *(Buffer+i)!='\0') { 169 // 每個(gè)字符串末尾都有作為結(jié)束符'\n' 170 if(*(Buffer+i)!=' ') { // 若非空字符，則把當(dāng)前字符加入新的字符串中 171 if(*(Buffer+i)>='A' && *(Buffer+i)<='Z') // 大寫字母轉(zhuǎn)換為小寫 172 *(Buffer+i)-='A'-'a'; 173 w.item[j][k]=*(Buffer+i); 174 k++; i++; 175 } else { // 如果是空字符，這是則開始另一個(gè)字符串 176 Ignore=false; 177 w.item[j][k++]='\0'; 178 for (int m=0; m<7; m++) 179 if(strcmp(w.item[j],IgnoreChar[m])==0) 180 { Ignore=true; break; } 181 if (!Ignore) { j++; k=0; i++; w.last++; } 182 else { k=0; i++; } 183 } 184 } 185 w.item[j][k++]='\0'; // 把最后一個(gè)字符串收尾 186 Ignore=false; 187 for (int m=0; m<7; m++) 188 if (strcmp(w.item[j],IgnoreChar[m])==0) 189 { Ignore=true; break; } 190 if (!Ignore) w.last++; // 并把最大數(shù)加1 191 return OK; 192 } 193 194 void GetLine(FILE *f) { 195 fgets(buf, MaxLineLen, f); // buf是全局?jǐn)?shù)組變量 196 } 197 198 Status PutText(FILE *IdxFile, IdxListType MyIdx) { 199 int i,j,k; 200 Link p; 201 for(i=0; i<MyIdx.last; i++) { 202 for(j=0; j<MyIdx.item[i].key.length; j++) 203 putc(*(MyIdx.item[i].key.ch+j ),IdxFile); 204 putc('\t',IdxFile); 205 if (MyIdx.item[i].key.length < 8) putc('\t',IdxFile); 206 p = MyIdx.item[i].bnolist.head; 207 for (k=0; k<MyIdx.item[i].bnolist.len; k++) { 208 p = p->next; 209 fprintf(IdxFile,"%03d",p->data); 210 putc(' ', IdxFile); 211 } 212 putc('\n',IdxFile); 213 } 214 return OK; 215 } 216 217 void PrintFile(FILE *FileName) { // 輔助函數(shù) 218 char ch; 219 rewind(FileName); 220 ch=getc(FileName); 221 while (ch!=EOF) { 222 putchar(ch); 223 ch=getc(FileName); 224 } 225 printf("\n"); 226 rewind(FileName); 227 }

HeapString.h

1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 5 typedef int Status; 6 #define OK 1 7 #define ERROR 0 8 #define OVERFLOW -2 9 10 typedef struct{ 11 char *ch; //若是非空串，則按串長度分配存儲(chǔ)區(qū)域，否則ch為NULL 12 int length; //串的長度 13 }HString; 14 15 /*生成一個(gè)其值等于等于串常量chars的串T*/ 16 Status StrAssign(HString &T, char *chars){ 17 if(T.ch) 18 free(T.ch); //若串存儲(chǔ)空間不為NULl 釋放原有空間 19 int i = strlen(chars); //獲取chars長度 20 if(!i){ 21 T.ch = NULL; //串常量chars長度為0時(shí)串為空串長度0存儲(chǔ)區(qū)間指向NULL 22 T.length = 0; 23 } 24 else{ 25 T.ch = (char *)malloc(i * sizeof(char)); //申請(qǐng)空間 26 if(!T.ch) 27 exit(OVERFLOW); 28 for(int j = 0; j < i; j++) 29 T.ch[j] = chars[j]; //寫入chars串 30 T.length = i; 31 } 32 return OK; 33 } 34 35 /*由串S復(fù)制得到T*/ 36 Status StrCopy(HString &T, HString S){ 37 if(T.ch) 38 free(T.ch); 39 T.ch = (char*)malloc(S.length * sizeof(char)); 40 if(!T.ch) 41 exit(OVERFLOW); 42 for(int j = 0; j < S.length; j++) 43 T.ch[j] = S.ch[j]; 44 T.length = S.length; 45 return OK; 46 } 47 /*若S>T，則返回值>0；若S=T,則返回值=0；若S<T，則返回值<0*/ 48 int StrCompare(HString T, HString S){ 49 for(int i = 0; i < S.length && i < T.length; i++) 50 if(S.ch[i] != T.ch[i]) 51 return S.ch[i] - T.ch[i]; 52 return S.length - T.length; 53 }

ChainedList.h

1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define OK 1 5 #define ERROR 0 6 #define OVERFLOW -2 7 #define TRUE 1 8 #define FALSE 0 9 10 typedef int Status; 11 typedef int ElemType; 12 13 typedef struct LNode{ 14 ElemType data; 15 struct LNode *next; 16 }*Link, *Position; 17 typedef struct{ 18 Link head, tail; 19 int len; 20 }LinkList; 21 22 Status InitList(LinkList &L){ 23 L.head = (Link)malloc(sizeof(LNode)); 24 if(!L.head) 25 exit(OVERFLOW); 26 L.tail = L.head; 27 L.len = 0; 28 L.head->next = NULL; 29 return 0; 30 } 31 32 Status MakeNode(Link &p,ElemType e){ 33 p = (Link)malloc(sizeof(LNode)); 34 if(!p) 35 exit(OVERFLOW); 36 p->data = e; 37 p->next = NULL; 38 return OK; 39 } 40 41 Status Append(LinkList &L, Link S){ 42 Link p; 43 L.tail->next = S; 44 p = S; 45 ++L.len; 46 while(p->next){ 47 p = p->next; 48 ++L.len; 49 } 50 L.tail = p; 51 return OK; 52 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ABook/p/5697014.html

總結(jié)

以上是生活随笔為你收集整理的数据结构-串操作应用之词索引表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。