数据结构课程设计(共15页).doc

精选优质文档-倾情为你奉上 武汉理工大学 课程设计报告 计算机科学与技术学院课程名称 数据结构 设计题目 文学研究助手 班 级 计算机1101班 学 号 31 姓 名 王卫华 指导教师 杜海涛 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语言保留字集作为待统计的词汇集:if else for while return void int char typedef struct definesizeof delete include 三 概要设计 1、存储结构设计 #define SIZE 20 typedef FILE *PFILE; typedef char StringSIZE; typedef struct /单词类型 String data; /单词串 int len; /单词的长度 WordType; typedef struct WordNode / /单词结点类型 WordType data; WordNode *next; WordNode,*PWordNode; typedef struct RowLink /表示文本每一行的链表 WordNode *head,*tail; RowLink,*RLink; typedef struct RowNumNode /行号结点类型 int elem;/行号 RowNumNode *next; RowNumNode,*RowNumLink; typedef struct SearchWordNode /待搜索的单词结点类型 WordType data; /待搜索单词 int count; /待搜索单词出现的次数 RowNumLink RNhead,RNtail; /存放文本中出现待搜索单词行号的链表 SearchWordNode *next; SearchWordNode,*SWLink; struct SWLinkList /待搜索的单词集合的链表并用来存储统计结果 SWLink head,tail; ;2、 主要算法设计描述下列函数中较容易实现的未给出步骤(1) void CopyWord(WordType &w,String ch) 把字符串ch复制到单词元素w(2) int MatchWord(WordType w1,WordType w2) 单词的匹配,若相等则返回1,否则返回非0(3) void MakeWordNode(PWordNode &PN) 生成一个单词结点(4) void InsertAfter(RowLink &L,WordType w) 用后插法把单词结点w插入链表L MakeWordNode(L.tail->next); L.tail->next->data=w; L.tail=L.tail->next;(5) void DestroyWordLink(RowLink &L)销毁链表L(6) void CreateWordLink(RowLink &L,FILE *f)创建存放f指向文本每中一行单词的链表该函数的主要步骤： String ch; char c=getc(f); WordType w; char c=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(int i=0;c>='A'&&c<='Z'|c>='a'&&c<='z'i+)/取单词, chi=c; c=getc(f); chi='0' CopyWord(w,ch);/将获取的字符串复制到单词型的变量中 InsertAfter(L,w);/将获取的该单词插入到链表中 (7) void MakeRowNumNode(RowNumLink &p)生成一个行结点(8) void MakeSWNode(SWLink &p)生成一个待搜索的单词结点(9) void CreateSWLinkList(SWLinkList &S)建立一个待搜索的单词链表(10) void OutputSWLinkList(SWLinkList S)输出待搜索的单词链表的在文本中出现的次数和行号 (11)void OpenFile(PFILE &f,String ch)打开文件，ch表示文件的路径及名称 (12)中心函数描述 void MatchSWLinkList(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; /该指针指向文件该行的链表int label=1; /用于标志待搜索单词在本行中是否是第一次出 现，若是须创建一行结点，若不是，直接count+1 while(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模式匹配进行修改。此外还可以在行结点中增加一计数量来统计每一行中被检测单词出现的次数。六、 附源程序清单和运行结果。#include<iostream.h>#include<stdio.h>#include<stdlib.h>v#include<conio.h>#include<string.h>#define SIZE 20typedef FILE *PFILE;typedef char StringSIZE;typedef struct /单词类型 String data; /单词串 int len; /单词的长度 WordType;typedef struct WordNode /单词结点类型WordType data; WordNode *next;WordNode,*PWordNode;typedef struct RowLink /表示文本每一行的链表WordNode *head,*tail;RowLink,*RLink;typedef struct RowNumNode /行号结点类型int elem; /行号 RowNumNode *next;RowNumNode,*RowNumLink;typedef struct SearchWordNode /待搜索的单词结点类型WordType data; /待搜索单词 int count; /待搜索单词出现的次数 RowNumLink RNhead,RNtail; /存放文本中出现待搜索单词行号的链表 SearchWordNode *next;SearchWordNode,*SWLink;struct SWLinkList /待搜索的单词集合的链表SWLink head,tail;void CopyWord(WordType &w,String ch) /把字符串ch复制到单词元素w int j=strlen(ch); for(int i=0;i<=j;i+) w.datai=chi; w.len=j; int MatchWord(WordType w1,WordType w2)/单词的匹配,若相等则返回1,否则返回非0 if(w1.len!=w2.len)return 0;elsefor(int i=0;i<w1.len;i+)if(w1.datai!=w2.datai)break;if(i=w1.len)return 1;else return 0;void MakeWordNode(PWordNode &PN) /生成一个单词结点 if(!(PN=(PWordNode)malloc(sizeof(WordNode)cout<<"为新单词分配存储空间失败"<<endl; exit(0); PN->next=NULL;void InsertAfter(RowLink &L,WordType w) /用后插法把单词结点w插入链表L MakeWordNode(L.tail->next); L.tail->next->data=w; L.tail=L.tail->next;void DestroyWordLink(RowLink &L) /销毁链表Lwhile(L.head)L.tail=L.head->next; delete(L.head); L.head=L.tail;void CreateWordLink(RowLink &L,FILE *f)/创建存放f指向文本每中一行单词的链表 String ch; char c=getc(f); WordType w; MakeWordNode(L.head); L.tail=L.head; while(c!='n'&&!feof(f) while(!(c>='A'&&c<='Z'|c>='a'&&c<='z')&&c!='n'&&!feof(f)/滤去非法字符 c=getc(f); for(int i=0;c>='A'&&c<='Z'|c>='a'&&c<='z'i+)/取单词 chi=c; c=getc(f); chi='0' CopyWord(w,ch); InsertAfter(L,w); void MakeRowNumNode(RowNumLink &p)/生成一个行结点 if(!(p=(RowNumLink)malloc(sizeof(RowNumNode)cout<<"分配行号结点失败"<<endl; exit(0); p->next=NULL;void MakeSWNode(SWLink &p)/生成一个待搜索的单词结点 if(!(p=(SWLink)malloc(sizeof(SearchWordNode)cout<<"分配待搜索的单词结点失败"<<endl; exit(0); p->next=NULL;p->count=0; p->RNhead=NULL;p->RNtail=NULL;void CreateSWLinkList(SWLinkList &S)/建立一个待搜索的单词链表 MakeSWNode(S.head); S.tail=S.head;String st="#"WordType w,label;CopyWord(label,st); cout<<"请输入要搜索的英文单词,如果是'#'则表示输入结束"<<endl; cin>>st;CopyWord(w,st); while(!MatchWord(w,label) /w不是"#"MakeSWNode(S.tail->next); S.tail->next->data=w; S.tail=S.tail->next; cin>>st;CopyWord(w,st);void MatchSWLinkList(SWLinkList &S,FILE *f) /查找文本中出现待搜索的单词的次数和行号 RowLink RL; /用于保存文件中一行单词的链表PWordNode pr=NULL; /指向文件单次链表中的每一个单词SWLink ps=NULL; /指向被搜索的单词 int i=0; while(!(feof(f)/读取文本的每一行单词 i+; /行号 CreateWordLink(RL,f);/创建文本的一行单词链表 ps=S.head->next; while(ps)/遍历待搜索的单词链表的每个结点pr=RL.head->next;int label=1; /用于标志待搜索单词在本行中是否是第一次出现，若是须创建一行结点，若不是，直接count+1 while(pr) /本文中一行单词链表的每个结点依次与被搜索的单词比较if(MatchWord(pr->data,ps->data) ps->count+; if(label=1) if(ps->RNhead=NULL)/判断是否是第一个结点, MakeRowNumNode(ps->RNhead);/创建统计被搜索单词出现次数及行号的链表 ps->RNhead->elem=i; ps->RNtail=ps->RNhead; else MakeRowNumNode(ps->RNtail->next); ps->RNtail->next->elem=i; ps->RNtail=ps->RNtail->next; label=0; pr=pr->next; ps=ps->next; DestroyWordLink(RL);/销毁已被搜索过的文件中该行单词的链表void OutputSWLinkList(SWLinkList S)/输出待搜索的单词链表的在文本中出现的次数和行号 SWLink p;/指向待输出的单词RowNumLink pr;/指向待输出单词的某一行 cout<<"搜索结果:"<<endl; p=S.head->next; while(p)printf("%-8s:",p->data.data); cout<<"出现的次数"<<p->count<<" "<<"所在行为:" if(p->count) pr=p->RNhead; while(pr) cout<<pr->elem<<"," pr=pr->next; cout<<endl; p=p->next; void OpenFile(PFILE &f,String ch)/打开文件，ch表示文件的路径及名称 if(!(f=fopen(ch,"r")/以只读方式打开文件 cout<<"file not open"<<endl; cout<<"file open"<<endl;void main()PFILE f;String ch; SWLinkList S; cout<<"请输入要搜索的文本的路径及文件名:"<<endl;cin>>ch;OpenFile(f,ch); CreateSWLinkList(S);MatchSWLinkList(S,f);OutputSWLinkList(S);fclose(f); 本科生课程设计成绩评定表 班级：计算机1101班姓名：王卫华学号：31序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：201 年月日专心-专注-专业