数据结构课程设计报告-2

PAGE山东理工大学计算机学院课程设计（数据结构）班级计升1002姓名王蕊学号1022051061指导教师肖爱梅二○一一年一月二十日课程设计任务书及成绩评定课题名称建立词索引表Ⅰ、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。2、设计题目要求：信息检索是计算机应用的重要领域之一，为提高查询效率，建立好的索引系统是必要的，如在图书馆书目检索系统中可以按书名、作者名和分类号检索，但在实际系统中，最好的检索方法是按书名关键词检索。基本要求：依据书目基本信息文件建立关键词索引表Ⅱ、设计进度及完成情况日期内容1.10-1.11选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.12~1.14创建相关数据结构,录入源程序。1.17~1.19调试程序并记录调试中的问题，初步完成课程设计报告。1.20~1.21上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。Ⅲ、主要参考文献及资料[1]严蔚敏数据结构（C语言版）清华大学出版社1999[2]严蔚敏数据结构题集（C语言版）清华大学出版社1999[3]谭浩强C语言程序设计清华大学出版社[4]与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一一年一月二十一日

目录第一章概述……………1第二章系统分析………2第三章概要设计………第四章详细设计………第五章运行与测试……………………第六章总结与心得……………………参考文献………………PAGE17第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是建立词索引表。信息检索是计算机应用的重要领域之一，为提高查询效率，建立好的索引系统是必要的，但在实际系统中最好的检索方法是按书名关键词检索。读者可以很容易从关键词索引表中查询到他所感兴趣的书目。第二章系统分析

1．依据书目信息建立关键词索引，应具有三大结构：一个书目文件，一个词表，一个关键词索引表。功能：首先从书目文件中读入一个书目串，然后从书目串中提取所有关键词插入词表，对词表中的每一个关键词，在索引表中进行查找并做相应的插入操作。2．建立一个以.txt为扩展名的文件作为书目文件。3．设定词表，词表中存放一本书的书名中若干关键词。其中每个词是一个字符串。4．动态生成索引表。索引表的功能:查找。索引表中每个索引项包含两部分：关键词和书号索引。5．要实现关键词索引程序中涉及的函数及函数实现的功能如下：IdxListType*InitIdxList(IdxListType*idxlist)初始化操作，置索引表idxlist为空表，且在idxlist.item[0]设一空串。voidGetLine(FILE*f)从文件f读入一个书目信息到书目缓冲区bufintExtractKeyWord(intbno[])从buf中提取书目关键词到词表wdlist，书号存入bnointInsIdxList(IdxListType*idxlist,intbno[])将书号bno的书名关键词按词典顺序插入索引表idxlistvoidPutText(FILE*g,IdxListType*idxlist)将生成的索引表idxlist输入到输出文件gvoidIdxlist_free(IdxListType*idxlist)释放空间第三章概要设计本章主要介绍1、数据结构的设计在这次课程设计中，词表中只存放一本书的书名中若干关键词，其数量有限，则采用顺序存储结构的线性表，索引表为有序表，索引表中每个索引项包含两部分。一、关键词，因索引表为常驻结构，考虑到节省存储空间，采用堆分配存储表示的串类型。二、书号索引，由于书号索引是在索引表的生成过程中逐个插入，且不同关键词的书号索引个数不等，甚至会相差很多，所以这里采用链表结构的线性表。2、算法的设计本设计从总体上划分为三个模块。模块一、完成从书目文件中读取书目串并从书目串中提取所有关键词插入词表。功能函数：GetLine(FILE*f)，ExtractKeyWord(intbno[])算法：voidGetLine(FILE*f){intj=0;staticchara[100][100];charc;c=fgetc(f);while(((a[v][j++]=tolower(c))!='\n')&&(c!=EOF))c=fgetc(f);a[v][j-1]='\0';buf=a[v++];printf("%s",buf);}intExtractKeyWord(intbno[]){intk,s,t=0,j=0;externintb=i;char*p=buf,*q,*c[10];while(!isalnum(*p))p++;while(isdigit(*p)||!isalpha(*p)){bno[j]=*p-'0';p++;j++;}j--;while(!isalpha(*p))p++;q=p;while(*q){while((*q!='')&&*q&&(*q!=EOF))q++;q++;*(q-1)='\0';c[t++]=p;p=q;}for(k=0;k<t;++k){for(s=0;s<8;++s){if(strcmp(c[k],com[s])==0)break;}if(s==8)wdlist.item[i++]=c[k];}wdlist.last=i;printf("词表的长度%d",wdlist.last);printf("书号：");for(k=0;k<j;++k)printf("%d",bno[k]);printf("\n");for(k=b;k<i;++k)printf("关键字%s\n",wdlist.item[k]);return0;}模块二、完成索引表的建立。功能函数：InitIdxList(IdxListType*idxlist)算法：IdxListType*InitIdxList(IdxListType*idxlist){idxlist=(IdxListType*)malloc(sizeof(IdxListType));if(idxlist==NULL){printf("ERROR——1!");exit(-1);}idxlist->item[0].key=(HString*)malloc(sizeof(HString));idxlist->item[0].bnolist=(LinkList)malloc(sizeof(LNode));idxlist->item[0].key->ch=NULL;idxlist->item[0].key->length=0;idxlist->item[0].bnolist->next=NULL;idxlist->last=0;returnidxlist;}模块三完成对词表中的每一个关键词，在索引表中进行查找并做相应的插入操作。功能函数：InsIdxList(IdxListType*idxlist,intbno[])算法：intInsIdxList(IdxListType*idxlist,intbno[]){intk,t,s,j=0,c=b,d;LinkListp,q;if(i>=MaxKeyNum+1){printf("超过索引表最大存储，请调整！\n");exit(-1);}for(t=idxlist->last;j<i-b;j++,c++){if(t==0)//第一个关键字插入{idxlist->item[0].key->ch=wdlist.item[c];for(d=0;d<3;++d)idxlist->item[0].bnolist->data[d]=bno[d];//书号存储idxlist->item[0].bnolist->next=NULL;//链表尾部指向空idxlist->last++;t++;}else{for(k=0;k<t;k++){if((s=strcmp(wdlist.item[c],idxlist->item[k].key->ch))==0){Length(idxlist->item[k].bnolist)+1,bno);p=(LinkList)malloc(sizeof(LNode));printf("\n插入的书号：");for(d=0;d<3;++d){p->data[d]=bno[d];printf("%d",p->data[d]);}q=idxlist->item[k].bnolist;for(d=0;d<3;++d)printf("%d",q->data[d]);while(q->next!=NULL)q=q->next;q->next=p;p->next=NULL;printf("\n关键字%-20s\t\n",idxlist->item[k].key->ch);q=idxlist->item[k].bnolist;while(q){for(d=0;d<3;++d)printf("%d",q->data[d]);if(q->next!=NULL)printf(",");q=q->next;}printf("\n");break;}elseif(s>0){if(k==t-1)//插入的关键字大于最后一个已存在的关键字，则插在最后{idxlist->item[t].key=(HString*)malloc(sizeof(HString));idxlist->item[t].bnolist=(LinkList)malloc(sizeof(LNode));idxlist->item[t].key->ch=wdlist.item[c];for(d=0;d<3;++d)idxlist->item[t].bnolist->data[d]=bno[d];idxlist->item[t].bnolist->next=NULL;idxlist->last++;t++;break;}}else{idxlist->item[t].key=(HString*)malloc(sizeof(HString));idxlist->item[t].bnolist=(LinkList)malloc(sizeof(LNode));for(s=t-1;s>=k;--s){//插入的关键字小于当前已有的关键字，则把当前的到最后的关键字向后移idxlist->item[s+1].key->ch=idxlist->item[s].key->ch;idxlist->item[s+1].bnolist->next=idxlist->item[s].bnolist->next;for(d=0;d<3;d++)idxlist->item[s+1].bnolist->data[d]=idxlist->item[s].bnolist->data[d];}idxlist->item[k].key->ch=wdlist.item[c];//在当前关键字上插入新关键字for(d=0;d<3;++d)idxlist->item[k].bnolist->data[d]=bno[d];idxlist->item[k].bnolist->next=NULL;idxlist->last++;t++;break;}}}}return0;}第四章详细设计1、成员函数voidGetLine(FILE*f){intj=0;staticchara[100][100];charc;c=fgetc(f);while(((a[v][j++]=tolower(c))!='\n')&&(c!=EOF))c=fgetc(f);a[v][j-1]='\0';buf=a[v++];printf("%s",buf);}intExtractKeyWord(intbno[]){intk,s,t=0,j=0;externintb=i;char*p=buf,*q,*c[10];while(!isalnum(*p))p++;while(isdigit(*p)||!isalpha(*p)){bno[j]=*p-'0';p++;j++;}j--;while(!isalpha(*p))p++;q=p;while(*q){while((*q!='’)&&*q&&(*q!=EOF))q++;q++;*(q-1)='\0';c[t++]=p;p=q;}for(k=0;k<t;++k){for(s=0;s<8;++s){if(strcmp(c[k],com[s])==0)break;}if(s==8)wdlist.item[i++]=c[k];}wdlist.last=i;printf("词表的长度%d",wdlist.last);printf("书号：");for(k=0;k<j;++k)printf("%d",bno[k]);printf("\n");for(k=b;k<i;++k)printf("关键字%s\n",wdlist.item[k]);return0;}IdxListType*InitIdxList(IdxListType*idxlist){idxlist=(IdxListType*)malloc(sizeof(IdxListType));if(idxlist==NULL){printf("ERROR——1!");exit(-1);}idxlist->item[0].key=(HString*)malloc(sizeof(HString));idxlist->item[0].bnolist=(LinkList)malloc(sizeof(LNode));idxlist->item[0].key->ch=NULL;idxlist->item[0].key->length=0;idxlist->item[0].bnolist->next=NULL;idxlist->last=0;returnidxlist;}intInsIdxList(IdxListType*idxlist,intbno[]){intk,t,s,j=0,c=b,d;LinkListp,q;if(i>=MaxKeyNum+1){printf("超过索引表最大存储，请调整！\n");exit(-1);}for(t=idxlist->last;j<i-b;j++,c++){if(t==0)//第一个关键字插入{idxlist->item[0].key->ch=wdlist.item[c];for(d=0;d<3;++d)idxlist->item[0].bnolist->data[d]=bno[d];//书号存储idxlist->item[0].bnolist->next=NULL;//链表尾部指向空idxlist->last++;t++;}else{for(k=0;k<t;k++){if((s=strcmp(wdlist.item[c],idxlist->item[k].key->ch))==0){Length(idxlist->item[k].bnolist)+1,bno);p=(LinkList)malloc(sizeof(LNode));printf("\n插入的书号：");for(d=0;d<3;++d){p->data[d]=bno[d];printf("%d",p->data[d]);}q=idxlist->item[k].bnolist;for(d=0;d<3;++d)printf("%d",q->data[d]);while(q->next!=NULL)q=q->next;q->next=p;p->next=NULL;printf("\n关键字%-20s\t\n",idxlist->item[k].key->ch);q=idxlist->item[k].bnolist;while(q){for(d=0;d<3;++d)printf("%d",q->data[d]);if(q->next!=NULL)printf(",");q=q->next;}printf("\n");break;}elseif(s>0){if(k==t-1)//插入的关键字大于最后一个已存在的关键字，则插在最后{idxlist->item[t].key=(HString*)malloc(sizeof(HString));idxlist->item[t].bnolist=(LinkList)malloc(sizeof(LNode));idxlist->item[t].key->ch=wdlist.item[c];for(d=0;d<3;++d)idxlist->item[t].bnolist->data[d]=bno[d];idxlist->item[t].bnolist->next=NULL;idxlist->last++;t++;break;}}else{idxlist->item[t].key=(HString*)malloc(sizeof(HString));idxlist->item[t].bnolist=(LinkList)malloc(sizeof(LNode));for(s=t-1;s>=k;--s){//插入的关键字小于当前已有的关键字，则把当前的到最后的关键字向后移idxlist->item[s+1].key->ch=idxlist->item[s].key->ch;idxlist->item[s+1].bnolist->next=idxlist->item[s].bnolist->next;for(d=0;d<3;d++)idxlist->item[s+1].bnolist->data[d]=idxlist->item[s].bnolist->data[d];}idxlist->item[k].key->ch=wdlist.item[c];//在当前关键字上插入新关键字for(d=0;d<3;++d)idxlist->item[k].bnolist->data[d]=bno[d];idxlist->item[k].bnolist->next=NULL;idxlist->last++;t++;break;}}}}return0;}voidPutText(FILE*g,IdxListType*idxlist){intk,t;if((g=fopen("BookIdx.txt","w"))==NULL){printf("\n\n不能建立索引表");return;}fprintf(g,"%-20s%-60s\n","关键字","书号");printf("%-20s%-60s\n","关键字","书号");for(k=0;k<idxlist->last;k++){fprintf(g,"%-20s\t",idxlist->item[k].key->ch);printf("%-20s\t",idxlist->item[k].key->ch);while(idxlist->item[k].bnolist){for(t=0;t<3;++t){fprintf(g,"%d",idxlist->item[k].bnolist->data[t]);printf("%d",idxlist->item[k].bnolist->data[t]);}if(idxlist->item[k].bnolist->next!=NULL){printf(",");fprintf(g,",");}idxlist->item[k].bnolist=idxlist->item[k].bnolist->next;}fprintf(g,"\n");printf("\n");}fclose(g);}2、main()函数：intmain(){IdxListType*idxlist=NULL;FILE*f,*g;intBookNo[5];if((f=fopen("BookInfo.txt","r"))==NULL){