使用线性表+串的基本操作实现给定顺序的数号及数目,生成对应的索引表
参考《数据结构》严蔚敏老师及网上代码，使用code block调试；
易错点：
1，添加新关键词到索引表中,需先顺序移动插入点之后的关键字及书号链表，此时插入点的关键字串内存地址仍和其后的相同,
如果直接赋值新关键字到此地址,则会把其后的关键字也同时修改,所以需重新分配堆内存到带插入位置
2，插入一个新的额关键字后，需同时把此关键字位置对应的书号链表初始化并加入此关键字所在的书号
3，同一书目中连续出现多个相同的关键字时，只需要添加一个书号即可
上代码：调试中出现问题，请及时留言，谢谢
/**
*
* 建立图书馆书目索引表
*
* (从书目文件生成关键词索引表)
*
* 链表+串
*
* 1, 从书目文件中读入一个书目串
* 2, 从书目串中提取所有关键词插入词表
* 3, 对词表中每个关键词,在索引表中进行查找并作相应的插入操作
* 4, 循环上述步骤,直至书目文件读取完成
*
**/
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define OK 1
#define ERROR 0
#define MaxBookNum 100 // 最大对100本书建立索引表
#define MaxKeyNum 50 // 索引表的最大容量
#define MaxLineLen 100 // 书目串的最大长度
#define MaxWordNum 10 // 词表的最大容量
#define MaxWordLen 30 // 每个单词最大长度
typedef unsigned char uchar;
typedef int ElemType; // 书号索引
typedef int Status;
// 建立词表类型(顺序表)
typedef struct {
uchar item[MaxWordNum][MaxWordLen]; // 词表字符串数组
int last; // 词表的长度
}WordListType;
/* 线性表中节点类型定义 */
typedef struct Node {
ElemType bookno;
struct Node *next;
}*Link;
/* 线性表类型定义 */
typedef struct {
Link head; // 头指针:指向线性链表的头结点的指针
Link tail; // 尾指针:指向线性链表的最后一个节点指针
int len; // 标记线性链表的长度
} LinkList; // 存放书号索引的单链表
// 关键词串
typedef struct {
uchar *str;
int len;
}HeapString;
// 定义索引表项节点结构
typedef struct {
HeapString key;
LinkList bnolist;
}IdxItemType;
// 索引表结构(有序顺序表)
typedef struct {
IdxItemType idxitem[MaxKeyNum + 1];
int idxlast;
}IdxListType;
Status MakeNode(Link &p, const ElemType e)
{
p = new struct Node;
if (!p)
return ERROR;
p->bookno = e;
p->next = NULL;
return OK;
}
/* 针对线性表 */
/* 构建一个空的线性表 */
Status InitList(LinkList& L)
{
/* 生成头结点 */
Link head;
if (MakeNode(head,-1))
{
L.head = L.tail = head;/* 线性表为空的条件:头指针==尾指针都指向头结点 */
L.len = 0;
return OK;
} else
{
return ERROR;
}
}
// 串最小操作子集
Status StrAssign(HeapString & T, uchar *str)
{
if (T.str)
delete [] T.str; // 释放T原来的存储数据
int len = strlen((const char*)str);
uchar *newbase = new uchar[len];
if (!newbase)
return ERROR;
T.str = newbase;
memcpy(T.str, str, len);
T.len = len;
return OK;
}
// 串S复制到串T
Status StrCopy(HeapString&T, HeapString S)
{
if (T.str)
delete [] T.str;
T.str = new uchar[S.len];
if (!(T.str))
return ERROR;
memcpy(T.str, S.str, S.len);
T.len = S.len;
return OK;
}
int StrCompare(HeapString S, HeapString T)
{// S>T return 1
// S == T return 0
// S<T return -1
for (int idx = 0; (idx < S.len) && (idx < T.len); idx++)
{
if (S.str[idx] != T.str[idx]) {
return S.str[idx] – T.str[idx];
}
}
return S.len – T.len;
}
Status AppendList(LinkList &L, Link s)
{
int i = 1;
if (!s)
return ERROR;
if (L.tail->bookno == s->bookno) {
// 同一数目相同的关键字只添加一次书号
return OK;
}
L.tail->next = s; // s串添加到L的尾节点,
L.tail = s; // 更新L的尾节点
L.len += i; // 更新L的长度
return OK;
}
uchar buf[MaxLineLen]; // 书目串缓冲区
WordListType wdlist; // 词表
// 从词表中返回第i个关键词
void GetWord(int i, HeapString &wd)
{
uchar *p = wdlist.item[i];
StrAssign(wd, p);
}
// 在索引表中查找是否存在于wd相同的关键词,若存在,则返回其在索引表中位置,并置b为true
// 若不存在,返回将要插入此关键词的位置,并置b为false
int Locate(IdxListType idxlist, HeapString wd, bool &b)
{
int m;
int idx;
/* 查找待插入关键词是否已在索引表中 */
if (0 == idxlist.idxlast) {
b = false;
return 0;
}
for (idx = idxlist.idxlast – 1; idx >= 0; idx–) {
if ((m = StrCompare(idxlist.idxitem[idx].key, wd)) > 0) {
continue;
} else {
break;
}
}
if (0 == m) {
b = true;
return idx;
} else {
b = false;
return idx + 1;
}
}
// 在索引表第i项上插入新的关键词wd,并初始化书号索引的链表为空表
void InsertNewKey(IdxListType &idxlist, int i, HeapString wd)
{
for (int jdx = idxlist.idxlast – 1; jdx >= i; jdx–) { // 向后移动i之后的项
idxlist.idxitem[jdx + 1] = idxlist.idxitem[jdx]; // 拷贝过程中把关键字及书号链表全部拷贝走
}
idxlist.idxitem[i].key.str = NULL;
idxlist.idxitem[i].key.len = 0; // 需重新分配新关键字堆内存
StrCopy(idxlist.idxitem[i].key, wd);
InitList(idxlist.idxitem[i].bnolist); // 需清除拷贝过程中带来的书号链表
idxlist.idxlast++;
}
// 在索引表的第i项中插入书号为no的索引
Status InsertBookNo(IdxListType &idxlist, int i, ElemType no)
{
Link p;
if (!MakeNode(p,no))
return ERROR;
AppendList(idxlist.idxitem[i].bnolist, p);
return OK;
}
// 初始化索引表,置索引表为空表,且在idxitem[0]设置为空串
void InitIdxList(IdxListType &idxlist)
{
idxlist.idxlast = 0;
for (int idx = 0; idx < (MaxKeyNum + 1); idx++) {
InitList(idxlist.idxitem[idx].bnolist);
idxlist.idxitem[idx].key.str = NULL;
idxlist.idxitem[idx].key.len = 0;
}
}
// 从文件file中读取一个书目信息到书目串缓冲区buf
void GetLine(FILE *file)
{
fgets((char *)buf, MaxLineLen, file);
}
// 从书目串缓冲区提取关键词到词表wdlist,书号存入bno
void ExtractKeyWord(ElemType &bno)
{
uchar IgnoreChar[][10] = {“a”,”to”,”of”,”the”,”and”,”not”,”or”,”if” };
bool wordstartflag = false;
bool ignoreflag = false;
int idx = 0;
int wordcnt = 0;
wdlist.last = 0;
while (buf[idx] != ‘\n’ && buf[idx] != ‘\0’) { /* 提取书号字符 */
if (wordstartflag) { /* 开始接收有效字符 */
if (buf[idx] == ‘ ‘) { /* 开始下一个单词接收 */
wordstartflag = false;
wdlist.item[wdlist.last][wordcnt++] = 0; /* 每个单词添加结束符 */
for (int jdx = 0; jdx < (sizeof(IgnoreChar)/sizeof(IgnoreChar[0])); jdx++) {
if (0 == strcmp((const char*)(wdlist.item[wdlist.last]), (const char*)(IgnoreChar[jdx]))) { /* 忽略 */
ignoreflag = true;
break;
}
}
if (!ignoreflag) {
wdlist.last++;
}
ignoreflag = false;
wordcnt = 0;
} else { /* 非空格,添加到当前单词 */
if ((‘A’ <=buf[idx]) && (buf[idx] <= ‘Z’))
wdlist.item[wdlist.last][wordcnt] = buf[idx] + 32; /* 大写转小写 */
else
wdlist.item[wdlist.last][wordcnt] = buf[idx];
++wordcnt;
++idx;
}
} else {
/* 跳过各个单词之间的空格 */
if (buf[idx] != ‘ ‘) {
wordstartflag = true;
} else {
idx++;
}
}
}
wdlist.item[wdlist.last][wordcnt++] = 0;
wdlist.last++;
/* 提取书号 */
int bookno = -1;
if ((bookno = atoi((const char*)(wdlist.item[0]))) > 0) /* 将书号字符串转换为int型 */
bno = bookno;
}
// 将书号为bno的书名关键词按照字典顺序插入到索引表idxlist
Status InsIdxList(IdxListType &idxlist, ElemType bno)
{
HeapString wd;
bool b;
int jdx;
for (int idx = 1; idx < wdlist.last; idx++) {
wd.str = NULL;
GetWord(idx,wd);
jdx = Locate(idxlist,wd,b);
if (!b) {
InsertNewKey(idxlist,jdx,wd); // 插入新关键字
InsertBookNo(idxlist,jdx,bno); // 并把新关键字对应的书号保存到链表
} else {
if (!InsertBookNo(idxlist,jdx,bno))
return ERROR;
}
}
return OK;
}
// 将生成的索引表输出到文件g
void PutIdxList(FILE *file, IdxListType idxlist)
{
Link p;
for (int idx = 0; idx < idxlist.idxlast; idx++) {
for (int jdx = 0; jdx < idxlist.idxitem[idx].key.len; jdx++) {
putc(idxlist.idxitem[idx].key.str[jdx], file);
}
putc(‘\t’, file);
if (idxlist.idxitem[idx].key.len < 8)
putc(‘\t’, file);
p = idxlist.idxitem[idx].bnolist.head->next;
for (int k = 0; (p != NULL) && (k < idxlist.idxitem[idx].bnolist.len); k++) {
fprintf(file, “%03d”,p->bookno);
putc(‘ ‘, file);
p = p->next;
}
putc(‘\n’, file);
}
}
int main()
{
FILE *f, *g;
IdxListType idxlist;
ElemType bookno;
#if 0 // 测试当前工作目录
if ((f = fopen(“123.txt”, “w”)))
{
getch();
}
#endif
if ((f = fopen(“BookInfo.txt”, “r”))) {
if ((g = fopen(“BookIdx.txt”, “w”))) {
InitIdxList(idxlist);
while (!feof(f)) {
GetLine(f); // 读入一个书目信息到buf
ExtractKeyWord(bookno);
InsIdxList(idxlist, bookno);
}
PutIdxList(g, idxlist);
fclose(f);
fclose(g);
} else {
cout << “open BookIdx.txt failed!” << endl;
}
} else {
cout << “open BookInfo.txt failed!” << endl;
}
}