数据结构课程设计

武汉理工大学课程设计报告计算机科学与技术学院课程名称《数据结构》设计题目文学研究助手班级计算机1101班学号0121110340131姓名王卫华指导教师杜海涛2013年6月21日课程设计任务书学生姓名：王卫华专业班级：1101班指导教师：杜海涛工作单位：计算机科学系题目:文学研究助手初始条件：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。测试用例见题集p116。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1、问题描述简述题目要解决的问题是什么。2、设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、经验和体会（包括对算法改进的设想）5、附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第17周（6月17日至6月21日）完成。2、6月21日14：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名：年月日系主任（或责任教师）签名：年月日文学研究助手一、问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。二、需求分析：1、文本串非空且以文件形式存放，统计匹配的词集非空。文件名和词集均由用户从键盘输入；2、“单词”定义：由字母构成的字符序列，中间不含空格字符且区分大小写；3、待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置若干空格字符；4、在计算机终端输出的结果是：单词，出现的次数，出现的位置所在行的行号，同一行出现两次的只输出一个行号；5、测试数据以你的C源程序模拟英文小说，C语言保留字集作为待统计的词汇集:ifelseforwhilereturnvoidintchartypedefstructdefinesizeofdeleteinclude三．概要设计1、存储结构设计#defineSIZE20typedefFILE*PFILE;typedefcharString[SIZE];typedefstruct//单词类型{Stringdata;//单词串intlen;//单词的长度}WordType;typedefstructWordNode//单词结点类型{WordTypedata;WordNode*next;}WordNode,*PWordNode;typedefstructRowLink//表示文本每一行的链表{WordNode*head,*tail;}RowLink,*RLink;typedefstructRowNumNode//行号结点类型{intelem;//行号RowNumNode*next;}RowNumNode,*RowNumLink;typedefstructSearchWordNode//待搜索的单词结点类型{WordTypedata;//待搜索单词intcount;//待搜索单词出现的次数RowNumLinkRNhead,RNtail;//存放文本中出现待搜索单词行号的链表SearchWordNode*next;}SearchWordNode,*SWLink;structSWLinkList//待搜索的单词集合的链表并用来存储统计结果{SWLinkhead,tail;};2、主要算法设计描述下列函数中较容易实现的未给出步骤(1)voidCopyWord(WordType&w,Stringch)把字符串ch复制到单词元素w(2)intMatchWord(WordTypew1,WordTypew2)单词的匹配,若相等则返回1,否则返回非0(3)voidMakeWordNode(PWordNode&PN)生成一个单词结点(4)voidInsertAfter(RowLink&L,WordTypew)用后插法把单词结点w插入链表LMakeWordNode(L.tail-next);L.tail-next-data=w;L.tail=L.tail-next;(5)voidDestroyWordLink(RowLink&L)销毁链表L(6)voidCreateWordLink(RowLink&L,FILE*f)创建存放f指向文本每中一行单词的链表该函数的主要步骤：Stringch;charc=getc(f);WordTypew;charc=getc(f);//从文件中读取一个字符MakeWordNode(L.head);//调用该函数生成文件行单词链表的头结点L.tail=L.head;while(c!='\n'&&!feof(f))//c不是换行，文件也未结束{while(!(c='A'&&c='Z'||c='a'&&c='z')&&c!='\n'&&!feof(f))//滤去非法字符c=getc(f);for(inti=0;c='A'&&c='Z'||c='a'&&c='z';i++)//取单词,{ch[i]=c;c=getc(f);}ch[i]='\0';CopyWord(w,ch);//将获取的字符串复制到单词型的变量中InsertAfter(L,w);//将获取的该单词插入到链表中}(7)voidMakeRowNumNode(RowNumLink&p)生成一个行结点(8)voidMakeSWNode(SWLink&p)生成一个待搜索的单词结点(9)voidCreateSWLinkList(SWLinkList&S)建立一个待搜索的单词链表(10)voidOutputSWLinkList(SWLinkListS)输出待搜索的单词链表的在文本中出现的次数和行号(11)voidOpenFile(PFILE&f,Stringch)打开文件，ch表示文件的路径及名称(12)中心函数描述voidMatchSWLinkList(SWLinkList&S,FILE*f)查找文本中出现待搜索的单词的次数和行号）该函数是求解该问题的主演函数，其主要步骤为：i=0//记录行号while(!(feof(f)))//文件未结束{i++;CreateWordLink(RL,f);//创建文本的该行单词链表ps=S.head-next;//ps指向此时被搜索的单词while(ps)//当ps所指单词不为空，在本行中查找其出现的次数{pr=RL.head-next;//该指针指向文件该行的链表intlabel=1;//用于标志待搜索单词在本行中是否是第一次出现，若是须创建一行结点，若不是，直接count+1while(pr)//本文中一行单词链表的每个结点依次与被搜索的单词比较{if(MatchWord(pr-data,ps-data)){ps-count++;if(label==1)是该正在搜索指针所指的{创建统计被搜索单词行号的链表，记录此时的行号label=0;}}pr=pr-next;//指向本行中下一个单词并进行比较}ps=ps-next;//对待搜索的下一个单词进行统计}DestroyWordLink(RL);//销毁已被搜索过的文件中该行单词的链表}四、调试报告调试过程中遇到的问题及解决方案：(1)对单词类型WordType进行定义时，原本想采用字符数组对data进行定义，但是对字符数组的操作不如对字符串操作方便，故改用字符串。(2)在创建文件中每一行单词的链表以及待测试的单词的链表，及创建待测试的单词的链表时，原本按照生成头结点，然后再生成结点依次插入，但发现在其它函数中也用到生成结点，这导致程序冗杂，故把生成结点写成一个独立的函数，供其它函数调用。(3)在统计被测试单词在每一行中出现的次数时，若该单词在一行中出现了两次，统计时发生了错误。后经修改，设置了一个label标志，用于标志待搜所单词在本行中是否是第一次出现，若是，须创建一行结点，记录行号，若不是，直接count自增1，而无需再生成一个行结点。(4)在从文件中获取字符时，起初未考虑所获取的字符是否是英文字母，且未过滤非英文字母的字符。对设计和编码的分析：该设计的主要思想为：（1）存储结构思想如下：用结点为单词类型的链表存储文件中某一行的单词，用结点为待搜索单词类型（该节点中包括count用来记录文件中单词出现的总数，还带有指向行的指针等）的链表来表示待搜索的单词，并对结果进行统计。（2）在统计被测单词集在文件中出现的总次数及行号时，思想如下：首先，生成文件某一行的单词链表，取待搜索的第一个单词与本行每一个单词比较，若相等则count自增1，然后取待搜索的下一个单词，亦与本行的每一个单词比较，直至完成所有要搜索的单词。然后，生成下一行的单词链表，重复上一步骤，直至文件结束。五、经验和体会以及对算法改进的设想经验和体会：(1)理解分析问题的能力及解决问题的能力得到提高这次课程设计从解决问题的思想到实际编写代码及调试、分析代码的优劣，都需要自己再三斟酌，耐心的编写与解决编程中的问题，对于编程中一些不熟悉的用法还需要查找一些资料。经过此次课程设计，我认识到设计一个应用程序的关键是对要求做最准确的把握，也就是说弄清楚需求分析是很重要的。本程序要求我从文件中找到所要查找的单词出现的次数及位置，也就是在文件中检索字符串。这样想来，思路就清晰了。如何在文件中读取单词，读取后如何映射，映射的字符串有如何和带查找的单词关联、查找的结果如何存储，是解决该问题的几大关键模块。逐个解析，整个程序的框架就了然于胸了。且随着编程的进行，思路越来越清晰。（2）对程序设计语言的细微之处又有了更深刻的理解。由于字符串的操作是很原始的基于原子的操作，所以更能看清楚我们所用的字符串操作函数在底层的实现机制，尽管再次程序中实现时与标准字符串的实现原理和实施手段有所不同，但根本认识差的并不远。次算法存在的不足之处及对算法改进的设想：该思想的主要缺陷是在统计待搜索单词在每一行中出现的次数时，时间复杂度太高，每一个待搜索的单词都要与一行中的所有单词比较。若待搜索的单词有m个，文件中每行单词平均有n个，则统计一行中所有待搜索的单词出现的次数的时间复杂度就为O（m*n）。改进：可以通过KMP模式匹配进行修改。此外还可以在行结点中增加一计数量来统计每一行中被检测单词出现的次数。六、附源程序清单和运行结果。#includeiostream.h#includestdio.h#includestdlib.hv#includeconio.h#includestring.h#defineSIZE20typedefFILE*PFILE;typedefcharString[SIZE];typedefstruct//单词类型{Stringdata;//单词串intlen;//单词的长度}WordType;typedefstructWordNode//单词结点类型{WordTypedata;WordNode*next;}WordNode,*PWordNode;typedefstructRowLink//表示文本每一行的链表{WordNode*head,*tail;}RowLink,*RLink;typedefstructRowNumNode//行号结点类型{intelem;//行号RowNumNode*ne