《数据结构C语言版 索引表》由会员分享,可在线阅读,更多相关《数据结构C语言版 索引表(13页珍藏版)》请在金锄头文库上搜索。
1、/*数据结构 C语言版 索引表P86-P87 编译环境:Dev-C+ 4.9.9.2日期:2011 年 2月 8日说明一下,常用词表文件的数据,第一行是词表含有的常用词个数,然后每一行一个词,都是以回车符结束的。书目文件,每一行前面三个字符是书号,后面紧接着是书名,而没有空格,每一行一本书,以回车符结束。文件以一个空行结束。 注意是回车符结束,这个要用编辑器显示了回车符的才能够看到,我就是不小心删了,然后一直出错的。 */#include #include #include #include typedef int ElemType;/ 串的堆分配存储 typedef structchar *
2、ch; / 若是非空串,则按串长分配存储区,否则 ch为 NULL int length; / 串长度 HString;/ 带头结点的线性链表类型 typedef struct LNode / 结点类型 ElemType data;struct LNode *next;LNode,*Link,*Position;typedef struct LinkList / 链表类型 Link head,tail; / 分别指向线性链表中的头结点和最后一个结点 int len; / 指示线性链表中数据元素的个数 LinkList;/这里将有三个表,词表(一本书中的关键词) ,索引表,常用词表#define
3、 MaxKeyNum 25 / 索引表的最大容量(关键词的最大数) #define MaxLineLen 100 / 书目串(书名+书号)buf 的最大长度 #define MaxWordNum 10 / 词表(一本书的关键词)的最大容量 #define MaxNoIdx 10 / 常用词(仅指大写)的最大数 typedef struct _WordListTypechar *itemMaxWordNum; / 词表(字符串)指针数组 int last; / 词的数量 WordListType; / 词表类型(顺序表) typedef structHString key; / 关键词(堆分配类
4、型,HString.h) LinkList bnolist; / 存放书号索引的链表(LinkList.h) IdxTermType; / 索引项类型 typedef structIdxTermType itemMaxKeyNum+1;int last; / 关键词的个数 IdxListType; / 索引表类型(有序表) typedef structchar *itemMaxNoIdx; / 常用词表指针数组 int last; / 常用词的数量 NoIdxType; / 常用词表类型(有序表)/ 全局变量 char bufMaxLineLen+1 = 0; / 当前书目串(包括0) Wor
5、dListType wdlist; / 暂存一本书的词表 NoIdxType noidx; / 常用词表 #define MaxBookNum 10 / 假设只对 10本书建索引表 #define MaxKeyNum 25 / 索引表的最大容量(关键词的最大数) #define MaxLineLen 100 / 书目串(书名+书号)buf 的最大长度 typedef structchar booknameMaxLineLen; / 书目串 int bookno; / 书号 BookTermType; / 书目项类型 typedef struct BookListType / 书目表类型(有序表
6、) BookTermType itemMaxBookNum;int last; / 书目的数量 BookListType; / 书目表类型(有序表)/ 生成一个其值等于串常量 chars的串 T int StrAssign(HString *T, char *chars)int i,j;if(*T).ch)free(*T).ch); / 释放 T原有空间 i = strlen(chars); / 求 chars的长度 i if(!i) / chars的长度为 0 (*T).ch = NULL;(*T).length = 0;else/ chars的长度不为 0 (*T).ch = (char*
7、)malloc(i*sizeof(char); / 分配串空间 if(!(*T).ch) / 分配串空间失败 exit(0);for(j = 0; j T,则返回值0;若 S=T,则返回值=0;若 Snext=NULL;/将头尾结点都分配好,并将其下一结点置空(*L).head=(*L).tail=p;(*L).len=0; /初始为 0return 1;else / 分配失败返回return 0;/ 分配由 p指向的值为 e的结点,并返回 1;若分配失败。则返回 0int MakeNode(Link *p,ElemType e)*p = (Link)malloc(sizeof(LNode);
8、 /动态分配一个 Link空间if(!*p)return 0;(*p)-data = e; / 赋值return 1;/ 将指针 s(s-data为第一个数据元素)所指(彼此以指针相链,以 NULL结尾)的 / 一串结点链接在线性链表 L的最后一个结点之后,并改变链表 L的尾指针指向新 / 的尾结点 int Append(LinkList *L,Link s)int i=1; /记录 s为头的串结点个数(*L).tail-next=s; /尾结点指向 swhile(s-next)s=s-next;i+;(*L).tail=s;(*L).len+=i;return 1;/ 置索引表 idxlis
9、t为空表,且在 idxliat.item0设一空串 void InitIdxList(IdxListType *idxlist)(*idxlist).last=0; /将索引表的关键词个数置为 0/ 将索引表的关键词块存储初始化为 0InitString(&(*idxlist).item0.key);/ 将索引表的索引项的书号索引初始化为 0 InitList(&(*idxlist).item0.bnolist);/ 从 buf中提取书名关键词到词表 wdlist,书号存入 BookNo void ExtractKeyWord(int *BookNo)int i,l,f = 1; / f是字符
10、串结束标志 0: 结束 1: 未结束 char *s1,*s2;if(buf09) / buf的首字母不是数字 exit(0);/ 释放上一个书目在词表 wdlist的存储空间,相当于初始化词表 for(i = 1;i =A&s100;-i);if(m=0) / 找到 *b=1;return i;else*b=0;return i+1;/ 在索引表 idxlist的第 i项上插入新关键词 wd,并初始化书号索引的链表为空表 void InsertNewKey(IdxListType *idxlist,int i,HString wd)int j;InitList(&(*idxlist).ite
11、m(*idxlist).last+1.bnolist);for(j=(*idxlist).last;j=i;-j) / 后移索引项 (*idxlist).itemj+1=(*idxlist).itemj;InitString(&(*idxlist).itemi.key); StrCopy(&(*idxlist).itemi.key,wd); / 串拷贝插入新的索引项 InitList(&(*idxlist).itemi.bnolist); / 初始化书号索引表为空表(*idxlist).last+;/ 在索引表 idxlist的第 i项中插入书号为 bno的索引void InsertBook(
12、IdxListType *idxlist,int i,int bno) Link p;if(!MakeNode(&p,bno) / 分配失败 LinkList.c exit(0);p-next=NULL;Append(&(*idxlist).itemi.bnolist,p); / 插入新的书号索引/ 将书号为 bno的关键词插入索引表 void InsIdxList(IdxListType *idxlist,int bno)int i,j;int b;HString wd;InitString(&wd); / bo4-2.c for(i=0;inext;fprintf(f,%d ,p-data
13、);fprintf(f,n);int main()FILE *f; IdxListType idxlist; / 索引表 int BookNo; / 书号int i,k,l;BookListType booklist; / 书目表 HString ch; / 索引字符串 Link p;f = fopen(常用词表.txt,r); / 打开常用词文件 if(!f)exit(0);printf(常用词表中的内容:n);fscanf(f, %d, &noidx.last); / 常用词个数for(k = 0; k next=NULL;Append(&idxlist.itemk.bnolist,p);
14、 / 插入新的书号索引fclose(f);f=fopen(书目文件.txt,r); / 打开书目文件 if(!f)exit(0);i=0;while(!feof(f) / 把书目文件的内容拷到 booklist中 fgets(buf,MaxLineLen,f);/ 前三位为书号 booklist.itemi.bookno =(buf0-0)*100+(buf1-0)*10+(buf2-0);strcpy(booklist.itemi.bookname,buf);i+;booklist.last=i;printf(请输入书目的关键词(一个);scanf(%s,buf);i=0;while(buf
15、i)bufi+=tolower(bufi); / 字母转为小写 StrAssign(&ch,buf);i=0;dok=StrCompare(ch,idxlist.itemi.key); / HString.c i+;while(k&inext;while(p)l=0;while(ldata!=booklist.iteml.bookno)l+;if(lnext;elseprintf(没找到n);system(pause);return 0;/*常用词表.txt 的内容: 5AAnInOfThe书目文件.txt 的内容:005Computer Data Structures010Introduction to Data Structures023Fundamentals of Data Structures034The Design and Analysis of Computer Algorithms050Introduction to Numerical Analysis067Numerical Analysis输出效果:常用词表中的内容:AAnInOfThe