低频词过滤系统

1、 数据结构课程设计报告低频词过滤系统 采用线性表和二叉排序树模拟实现围棋操作采用方法：数组 班 级：_软件101班_ 姓 名： _ 学 号： 11 指导教师： 董跃华 成 绩：_ 信息工程学院 2012年6月20日 目录1、 低频词过滤系统1，需求分析.32，概要设计.33，详细设计.64，调试分析.105，测试结果.116，参考文献.12二、模拟实现围棋操作1，需求分析.132，概要设计.133，详细设计.144，调试分析.185，测试结果.186，参考文献.20低频词过滤系统一、需求分析 给定一篇的英文文章，我们要想了解文章的一些信息。主要有两种方法：1、阅读文章并了解文章大意；2、统计文

2、章中单词的一些状态，如：单词总数、每个单词出现的频率、出现频率高的单词的个数和频率。现在编写一个程序来统计英文文章中单词的这些状态，利用线性表和二叉排序树来实现单词频率的统计，实现低频词的过滤，并比较两种方法的效率。过滤系统要实现的内容： 1.读取英文文章文件（InFile.txt），识别其中的单词。2.分别利用线性表和二叉排序树构建单词的存储结构。当识别出一个单词后，若线性表或者二叉排序树中没有该单词，则在适当的位置上添加该单词；若该单词已经被识别，则增加其出现的频率。3.统计结束后，删除出现频率低于五次的单词，并显示该单词和其出现频率。4.其余单词及其出现频率按照从高到低的次序输出到文件中

3、（OutFile.txt），同时输出用两种方法完成该工作所用的时间。5.计算查找表的ASL值，分析比较两种方法的效率。程序的功能：系统运行后主菜单如下：当选择1后进入以下界面：其中选择2时显示利用线性表来实现所有功能所用的时间。 当在主菜单选择2二叉排序树后，进入的界面与上图一样。2、 概要设计 1、抽象数据类型的定义.设定线性表的抽象数据类型定义为:ADT List数据对象：D=ai|aiElemset,i=1,2,3,.,n,n0数据关系：R1=|ai-1,aiD,i=2,.,n基本操作：LLNode(&L)操作结果：构造一个空的线性表L，并把从文件InFile.txt中读取到的单词插入到

4、表L 中，若线性表中没有与读取到的单词相同的关键字则将此单词插入到表L中， 否则单词频数加1。wordscount(L)初始条件：L已经存在。操作结果：统计不同单词的个数。deletelow(L)初始条件：L已经存在。操作结果：删除低频单词tjsyword(L)初始条件：L已经存在。操作结果:统计删除了低频词后剩余的高频词ADT List.设定二叉排序树的抽象数据类型定义为:ADT SearchBST数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可 唯一标识数据元素的关键字。 数据对象R:数据元素同属一个集合。基本操作：int STBNode(&T)操作结果：构造一

5、个空的二叉排序树T，并把从文件InFile.txt中读取到的单词插入 到树T中。seachbstree(&T)初始条件:二叉排序树T已存在。操作结果：若二叉排序树中没有与读取到的单词相同的关键字则将此单词插入到树T 中，否则单词频数加1。int deleteLOW(T，Visit1()初始条件:二叉排序树T已存在,Visit1是对结点操作的函数。操作结果：通过函数Visit1()删除低频单词。seachbstree1(&T)初始条件:二叉排序树T已存在。操作结果：将删除完低频词后的高频词插入到树T中。InOrderTraverse(&T)初始条件:二叉排序树T已存在。操作结果：中序遍历二叉排序

6、树。LevelOrderTraverse(&T)初始条件:二叉排序树T已存在。操作结果：层次遍历二叉排序树。ADT SearchBST2、主程序的流程 main（） 提示操作方法 调用线性表和二叉排序树的函数 3、 程序的模块 结构体模块-用于变量和对象的管理 线性表模块-实现线性表的抽象数据类型 二叉排序树模块- 实现二叉排序树的抽象数据类型 各模块之间的调用关系如下： 主程序模块 结构体模块 线性表模块 二叉排序树模块3、 详细设计 1、实现数据类型 线性表实现伪代码double LLNode(int M)/统计文章InFile.txt中的单词printf(*n);FILE *fp; ch

7、ar ch,array100020;int i=0,j=0,k=0,jj; fp=fopen(InFile.txt,r);/打开文件 if (fp=NULL) printf(cannot open filen);exit(0); LNode *L,*P,*Q;/定义结构指针 L=Q=(LNode *)malloc(sizeof(LNode);L-next=NULL; while(ch=fgetc(fp)!=EOF) if(ch=-|ch=)continue;/ else if(ch90&ch122)/单词 if(j=0)continue;/输入的是空格或数字或符号 if(L-next)/第二个

8、以后的单词进入单链表 P=(LNode *)malloc(sizeof(LNode);arrayij=0; for(jj=0;arrayijj!=0;jj+) P-Wordnamejj=arrayijj; P-Wordnamejj=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;/有相同的单词 if(!Q-next)Q-next=P;break;/没有相同的单词 if(M=1)printf( %s,arrayi); els

9、e /第一个单词 ，头结点无数据 P=(LNode *)malloc(sizeof(LNode);arrayij=0; for(jj=0;arrayijj!=0;jj+) P-Wordnamejj=arrayijj; P-Wordnamejj=0;P-count=1;P-next=NULL;L-next=P; if(M=1)printf(%s,arrayi); i+;j=0;Q=L;/Q指向头结点 else if(ch64&ch64&cciwordname,cc);B-count=1;B-lchild=B-rchild=NULL;if(m=1)printf(%s ,B-wordname); w

10、hile(fscanf(fp,%s,ch)!=EOF) j=0; for(i=0;chi!=0;i+) /单词处理 if(chi=-|chi=)continue;if(chi64&chi96&chilchild=SS-rchild=NULL;SS-count=1;strcpy(SS-wordname,cc);if(m=1)printf(%s ,cc);l+; N=seachbstree(B,cc);/到树中比较，返回访问树的最后一个节点；if(N=NULL)continue; if(!N-lchild|!N-rchild)/插入到树中 if(strcmp(N-wordname,SS-wordn

11、ame)0)N-lchild=SS;kk+; else if(strcmp(N-wordname,SS-wordname)rchild=SS;kk+; B=T; ccj=0;if(cc0!=0)/读入的是单个单词时 SS=(BSTree* )malloc(sizeof(BSTree); SS-lchild=SS-rchild=NULL;SS-count=1; N=seachbstree(B,cc); if(m=1)printf(%s ,cc);l+; if(N=NULL)continue; strcpy(SS-wordname,cc); if(!N-lchild|!N-rchild)/插入到树

12、中 if(strcmp(N-wordname,SS-wordname)0)N-lchild=SS;kk+; else if(strcmp(N-wordname,SS-wordname)rchild=SS;kk+; B=T; if(m=1)printf(n单词数：%d,l); M=(BSTree* )malloc(sizeof(BSTree);if(m=3)asl=LevelOrderTraverse(T)/kk;printf(单词种数：%dn,(int)kk); if(m=4|m=5|m=2) deleteLOW(M,T,m); if(m=5|m=2) FILE *fp=fopen(OutFi

13、le1.txt,w); clock_t start=clock(); InOrderTraverse(L,m,fp); clock_t end=clock(); if(m=5)printf(高频词个数：%dn,(int)gp); asl=LevelOrderTraverse(L)/gp;gp=0; printf(ntime:%.3fsn,double(end-start)/CLOCKS_PER_SEC); fprintf(fp,ntime:%.3fsn,double(end-start)/CLOCKS_PER_SEC); fclose(fp); int ecoperation(int m)/二

14、叉排序树的主操作 clock_t start=clock();STBNode(m);clock_t end=clock();if(m!=1&m!=2&m!=5)printf(*n);if(m=6)printf(nASL:%.3fn*n,asl);if(m=1|m=2)printf(n*ntime:%.3fsn,double(end-start)/CLOCKS_PER_SEC);2、函数与函数调用的关系图主程序的流程图线性表流程图 二叉排序树流程图4、 调试分析 1、遇到的问题和解决方法在此次设计中，我遇到了很多问题。其中有文件的读取和输出到文件的问题、计算执行时间的方法问题、在线性表的操作中高

15、频词的排序问题、在二叉排序树中如何计算ASL等等。通过查找资料我了解到可以利用fget()和fscanf()来读取文件单词，这两种方法不同的是：fget()是以字符为单位读取；而fscanf()可以以字符串为单位读取，也可以以字符为单位读取；输出的方式也有两种fput()和fprintf()，用法与fget()和fscanf()相对应。计算执行时间的方法我也是通过查找资料了解的，方法是：定义两个clock_t类型的时间变量，分别获取执行开始和结束的时间，而程序的执行时间就是结束的时间减去开始的时间再除以一秒的时钟计时单元CLOCKS_PER_SEC，至于为什么要除以CLOCKS_PER_SEC

16、，这是因为获取的开始和结束时间都是以毫秒为单位，要正确输出时间差需要把它换成秒，就需要除以CLOCKS_PER_SEC。对于线性表操作中的高频词排序的问题，我想了很久，想得头都晕了，还是没有想明白如何查找和插入结点，最终是通过与同学讨论和反复思考才想明白。建立一个新的单链表，在循环的作用下，通过结点指针的移动找到要插入的位置，在通过前驱和后继的变化插入到新的链表中。计算二叉排序树的ASL是用每一层结点的个数与所在层数的乘积的和再除以所有结点的总个数，其中难以操作的是每一层结点的个数的统计，我的程序中是用层次遍历要计算ASL的那一棵二叉排序树，在每一层的执行中统计下一层结点的个数并记录下来，每一

17、层执行完之后就完成这一层结点的个数与所在层数的乘积，直到这棵树的完全遍历，这是我通过反复的推敲和与同学的探讨得出的方法。我遇到的这几个问题中，前面两个是比较简单的，只要通过查找一些资料就能够解决；而后面两个是要通过分析和讨论才得到解决的，是比较复杂的，有时一个问题要花费一个上午的时间才能够解决。整个程序设计中偶尔还会有一些语法的错误，经过仔细检查及程序系统的提示下，问题得以解决。2、 算法的时空分析和改进设想有上面的伪代码可以看出线性表实现的时间复杂度是O(n+m)，n表示文章中字符个数，m表示文章中的单词个数；空间复杂度是O(n),n表示文章中的单词个数。二叉排序树实现的时间复杂度是O(n)

18、,n表示文章中单词的个数；空间复杂度是O(n),n表示文章中的单词个数。对于这个程序，应该可以通过一些操作实现当输出到OutFile.txt文件时，这个文件能够自动打开，更方便和DOC下的操作进行对比，有一些单词的统计方法不好，例如dont这个字符串是do not的缩写，我的程序中是把这个字符串看成dont来记录的，应该可以通过一些改进，用更好的方法来统计这类单词3、经验和体会通过这次课程设计，除了平时老师给予我们线性表和树的教导外，还让我对单链表和二叉排序树有了更深一层次的了解，对单链表和二叉排序树的结构和一些基本操作有了进一步的掌握。线性表中的单链表是由结点构成的。结点分为数据域和指针域，

19、数据域用于存储数据元素的信息，指针域存储直接后继存储位置。单链表结点的插入和删除都有其固定的模式，单链表的排序也是建立在插入和删除的基础上利用指针将无序的链表化为有序。二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。它至多每个结点有两个孩子。还有左右之分， 不能调换。正因为排序树的这种性质使它在搜索、插入、删除中很强的逻辑性。这次课程设计让我学到了很多，也使我更深刻地意识到，其实每个人都是很坚强的，每个人在

20、平时学习和生活中都有潜在的能力未曾发挥出来，只要有信心、有勇气去面对，就没有解决不了的难题。通过这段时间的磨合不断加深了我和同学之间的友谊，我们也懂得了合作的巨大力量，我们在设计的过程中寻找快乐！5、 测试结果1、低频词过滤系统的主菜单和操作方法2、线性表的第5步操作：输出高频词和频率，按频率高到低排序3、 线性表的第6步操作：计算比输出ASL4、 二叉排序树的第5步操作：输出高频词和频率，按频率高到低排序5、 二叉排序树的第6步操作：计算比输出ASL6、 参考文献 1、严蔚敏，吴伟民. 数据结构（C语言版），清华大学出版社。2、谭浩强，c语言程序设计，清华大学出版社。3、黄同成，黄俊民，董建

21、寅数据结构中国电力出版社模拟实现围棋操作1、 需求分析围棋是一种智力游戏，起源于中国。传说在黄帝时开始流传，到汉朝时规则大体定型。中国、日本和韩国是现今围棋的三大支柱，但近年来日本围棋逐步衰弱，形成了中韩争霸的局面。 在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下子后，有可能提取对方（白方的一串子）。以W1919表示一个棋盘，若Wij=0表示在位置(i,j)上没有子，Wij=1表示该位置上的是黑子，Wij=-1表示该位置上是白子。模拟实现围棋过程。程序的功能：当一方的棋子将另一方的棋子围住时，能够实现提取对方的棋子的功能，当某方下子后，该子立即呈无气状态，同时又不能提取对方的棋

22、子即在“禁着点”的位置时，禁止该方下到此处，并重新下子。当出现“打劫”时，能够正确的处理。 2、 概要设计 1、抽象数据类型的定义设定数组的抽象数据类型ADT Array 数据对象：ji=0,.,bi-1,i=1,2,.,n,D=aj1j2.jn|n(0)称为数组的维数， bi是数组第i维的长度，ji是数组元素的第i 为下标， aj1j2.jnElemSet 数据关系：R=R1,R2,.,Rn Ri=|0jkbk-1,1kn且k i,0jibi-2,aj1.ji.jn,aj1.ji+1.jnD,i=2,.n 基本操作： qipan() 操作结果：画出棋盘和棋盘上的棋子 EATing(count

23、) 操作结果：在输入第count步棋子所在的位置后，判定棋盘上的棋子分布的变 化和对第count步棋的判定。ADT Array2、主程序的流程 main（） 提示操作方法显示棋盘 调用棋子操作的函数 对函数返回值操作 3、 程序的其他模块 棋子操作模块-用于变量和对象的管理 各模块之间的调用关系如下： 主程序模块 棋子操作模块3、 详细设计1、实现数据类型实现下子后棋盘变化的伪算法int EATing(int count)int temp1919,i,j,t,eat361,breath361;/temp标记已被访问的点，eat用来 标记棋盘上已访问的点的位置，breath表示每个棋子的气。 f

24、or(i=0;i361;i+)breathi=0;for(t=0;t=count;t+)int c=0;for(i=0;i19;i+) for(j=0;j=0)cc=0;ii=eatkk/19;jj=eatkk%19;for(int k=0;k18)continue;if(Wiijj=+)cc=1;break; if(Wiijj=Weatkk/19eatkk%19&tempiijj=0)/颜色相同且未遍历过 tempiijj=1;eat+tt=ii*19+jj;else if(k=1)ii=eatkk/19-1;if(ii18)continue;if(Weatkk/19jj=+)cc=1;br

25、eak;if(Weatkk/19jj=Weatkk/19eatkk%19 &tempeatkk/19jj=0)tempeatkk/19jj=1;eat+tt=eatkk/19*19+jj;else jj=eatkk%19-1;if(jj0)continue;if(Weatkk/19jj=+)cc=1;break;if(Weatkk/19jj=Weatkk/19eatkk%19 &tempeatkk/19jj=0)tempeatkk/19jj=1;eat+tt=eatkk/19*19+jj;if(cc=1)break;/有气 kk+;if(cc=0)breathi*19+j=1;/无气 if(b

26、reathCOUNTcount=1)/当最后下的棋子没有气时 if(breathCOUNTcount-1=1) breathCOUNTcount=2;return 2;/打劫时不能连续吃子for(t=0;t=count)breathCOUNTcount=2;return 2;/不能自杀。else if(tcount&breathCOUNTcount!=2)/打劫 for(i=0;icount;i+) if(breathCOUNTi=1&WCOUNTi/19COUNTi%19= WCOUNTcount/19COUNTcount%19)breathCOUNTi=0; /与最后一个棋子颜色相同的无棋

27、子变为有气。for(i=0;icount;i+)if(breathCOUNTi=1)WCOUNTi/19COUNTi%19=+; /吃掉已经没有气的子。elsefor(t=0;tcount;t+)if(breathCOUNTt=1)WCOUNTt/19COUNTt%19=+; /吃掉已经没有气的子。return 1; 2、函数与函数调用的关系图主程序的流程图棋盘操作的流程图下子后棋盘局势变化的流程图 四、调试分析1、 遇到的问题和解决方法在此次设计中，我遇到了很多问题。其中有如何判断下一步棋后棋盘中是否会出现无气的棋子、如何用代码来区别“打劫”和“禁着点”等等。通过查找资料和与同学的讨论，我明白了可以利用一维数组来标记当某一个棋子四周都没有空位且有本方棋子时本方棋子已被访问和记录位置，再通过循环来判断这一棋子是否有气，若无气，则标记该棋子气为1，当这一棋子四周有空格时，就说明这一棋子有气，是活棋，则标记该棋子气为0，这样的标记是为了方便下面的操作。判断下了一个棋子后是否会出现“打劫”和“禁着点”，主要是判定已经没有气的位置是否能的下子，当当前下子方无法提取对方的棋子时，此位置就是“禁着