低频词过滤系统

1数据结构课程设计报告低频词过滤系统——采用线性表和二叉排序树模拟实现围棋操作——采用方法：数组班级：_____软件101班_____姓名：_学号：11指导教师：董跃华成绩：________________信息工程学院2012年6月20日2目录一、低频词过滤系统1，需求分析................................................................................................32，概要设计................................................................................................33，详细设计................................................................................................64，调试分析................................................................................................105，测试结果................................................................................................116，参考文献................................................................................................12二、模拟实现围棋操作1，需求分析................................................................................................132，概要设计................................................................................................133，详细设计................................................................................................144，调试分析................................................................................................185，测试结果................................................................................................186，参考文献................................................................................................203低频词过滤系统一、需求分析给定一篇的英文文章，我们要想了解文章的一些信息。主要有两种方法：1、阅读文章并了解文章大意；2、统计文章中单词的一些状态，如：单词总数、每个单词出现的频率、出现频率高的单词的个数和频率。现在编写一个程序来统计英文文章中单词的这些状态，利用线性表和二叉排序树来实现单词频率的统计，实现低频词的过滤，并比较两种方法的效率。过滤系统要实现的内容：1.读取英文文章文件（InFile.txt），识别其中的单词。2.分别利用线性表和二叉排序树构建单词的存储结构。当识别出一个单词后，若线性表或者二叉排序树中没有该单词，则在适当的位置上添加该单词；若该单词已经被识别，则增加其出现的频率。3.统计结束后，删除出现频率低于五次的单词，并显示该单词和其出现频率。4.其余单词及其出现频率按照从高到低的次序输出到文件中（OutFile.txt），同时输出用两种方法完成该工作所用的时间。5.计算查找表的ASL值，分析比较两种方法的效率。程序的功能：系统运行后主菜单如下：当选择1后进入以下界面：其中选择2时显示利用线性表来实现所有功能所用的时间。当在主菜单选择2二叉排序树后，进入的界面与上图一样。二、概要设计1、抽象数据类型的定义.设定线性表的抽象数据类型定义为:ADTList{数据对象：D={ai|aiElemset,i=1,2,3,...,n,n0}数据关系：R1={ai-1,ai|ai-1,aiD,i=2,...,n}基本操作：4LLNode(&L)操作结果：构造一个空的线性表L，并把从文件InFile.txt中读取到的单词插入到表L中，若线性表中没有与读取到的单词相同的关键字则将此单词插入到表L中，否则单词频数加1。wordscount(L)初始条件：L已经存在。操作结果：统计不同单词的个数。deletelow(L)初始条件：L已经存在。操作结果：删除低频单词tjsyword(L)初始条件：L已经存在。操作结果:统计删除了低频词后剩余的高频词}ADTList.设定二叉排序树的抽象数据类型定义为:ADTSearchBST{数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据对象R:数据元素同属一个集合。基本操作：intSTBNode(&T)操作结果：构造一个空的二叉排序树T，并把从文件InFile.txt中读取到的单词插入到树T中。seachbstree(&T)初始条件:二叉排序树T已存在。操作结果：若二叉排序树中没有与读取到的单词相同的关键字则将此单词插入到树T中，否则单词频数加1。intdeleteLOW(T，Visit1())初始条件:二叉排序树T已存在,Visit1是对结点操作的函数。操作结果：通过函数Visit1()删除低频单词。seachbstree1(&T)初始条件:二叉排序树T已存在。操作结果：将删除完低频词后的高频词插入到树T中。InOrderTraverse(&T)初始条件:二叉排序树T已存在。操作结果：中序遍历二叉排序树。LevelOrderTraverse(&T)初始条件:二叉排序树T已存在。操作结果：层次遍历二叉排序树。}ADTSearchBST2、主程序的流程main（）{提示操作方法5调用线性表和二叉排序树的函数}3、程序的模块结构体模块--------------用于变量和对象的管理线性表模块--------------实现线性表的抽象数据类型二叉排序树模块-------------实现二叉排序树的抽象数据类型各模块之间的调用关系如下：主程序模块↓结构体模块↓线性表模块↓二叉排序树模块三、详细设计1、实现数据类型线性表实现伪代码doubleLLNode(intM){//统计文章InFile.txt中的单词printf(**************************************\n);FILE*fp;charch,array[1000][20];inti=0,j=0,k=0,jj;fp=fopen(InFile.txt,r);//打开文件if(fp==NULL){printf(cannotopenfile\n);exit(0);}LNode*L,*P,*Q;//定义结构指针L=Q=(LNode*)malloc(sizeof(LNode));L-next=NULL;while((ch=fgetc(fp))!=EOF){if(ch=='-'||ch=='\'')continue;//elseif(ch65||(ch90&&ch97)||ch122)//单词{if(j==0)continue;//输入的是空格或数字或符号if(L-next){//第二个以后的单词进入单链表P=(LNode*)malloc(sizeof(LNode));array[i][j]=0;for(jj=0;array[i][jj]!='\0';jj++)P-Wordname[jj]=array[i][jj];P-Wordname[jj]='\0';P-count=1;P-next=NULL;while(1){if(strcmp(Q-next-Wordname,P-Wordname)!=0)Q=Q-next;else{Q-next-count++;break;}//有相同的单词6if(!Q-next){Q-next=P;break;}//没有相同的单词}if(M==1)printf(%s,array[i]);}else{//第一个单词，头结点无数据P=(LNode*)malloc(sizeof(LNode));array[i][j]=0;for(jj=0;array[i][jj]!='\0';jj++)P-Wordname[jj]=array[i][jj];P-Wordname[jj]='\0';P-count=1;P-next=NULL;L-next=P;if(M==1)printf(%s,array[i]);}i++;j=0;Q=L;//Q指向头结点}elseif(ch64&&ch91)array[i][j++]=ch+32;//大写字母elsearray[i][j++]=ch;}if(M==1)printf(\n单词数：%d\n,i);if(M==1||M==2||M==3)k=wordscount(Q,M);if(M==1||M==2||M==4||M==5)L=deletelow(L,M);if(M==1||M==2||M==5)k=tjsyword(L,M);return(k+1)/2.0;}doublehh=0;二叉排序树实现伪代码intSTBNode(intm){printf(**************************************\n);FILE*fp;charch[40],cc[20];inti=0,j=0,l=1;doublekk=1;BSTree*B,*SS,*T,*N,*M;T=B=(BSTree*)malloc(sizeof(BSTree));fp=fopen(InFile.txt,r);//打开文件if(fp==NULL){printf(cannotopenfile\n);exit(0);}fscanf(fp,%s,cc);//取出根节点for(i=0;cc[i]!='\0';i++)if(cc[i]64&&cc[i]91)cc[i]=cc[i]+32;strcpy(B-wordname,cc);B-count=1;B-lchild=B-rchild=NULL;if(m==1)printf(%s,B-wordname);while(fscanf(fp,%s,ch)!=EOF){j=0;for(i=0;ch[i]!='\0';i++){//单词处理if(ch[i]=='-'||ch[i]=='\'')continue;7if(ch[i]64&&ch[i]91)cc[j++]=ch[i]+32;elseif(ch[i]96&&ch[i]123)cc[j++]=ch[i];else{//连续多个单词在一起时cc[j]='\0';j=0;if(cc[0]!='\0'){SS=(BSTree*)malloc(sizeof(BSTree));SS-lchild=SS-rchild=NULL;SS-count=1;strcpy(SS-wordname,cc);if(m==1)printf(%s,cc);l++;N=seachbstree(B,cc);//到树中比较，返回访问树的最后一个节