《数据结构课程设计》由会员分享，可在线阅读，更多相关《数据结构课程设计（31页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告题 目： 文章中单词查找 专 业： 软件工程 学校 专业 姓名 学号 性别集美大学 软件工程 殷梓健 201521122028 帅哥起止时间： 2016.07.062016.07.10 集美大学计算机工程学院软件工程教研室制2016 年 7 月 09 日 目 录一 引言 .1二系统功能和原始数据 .1三 程序总体设计 .1四 功能模块函数设计和调试 .5五 程序清单 .9六 课程设计总结 .19七 参考资料 .191一、引言本课程实习是在理论学习和基础实验的基础上，学习开发规模较大的程序，运用已掌握应用数据结构来解决实际问题的基本方法。通过对程序结构的分析，设计和开发的过程
2、，提高综合应用数据结构的能力，为学习软件专业课程创建较扎实的理论基础和实践基础。本次任务是设计一个能够实现从存放多篇英文文章的文件目录中读取文件，并统计各篇文章单词个数，或查找指定单词在各篇文章中出现的位置的程序，并鼓励开发者通过多种渠道提高程序运行效率。通过本次课程设计不仅可以加深对所学知识的理解也提高了把知识应用到实践中能力。二、系统功能和原始数据(1)系统功能有多篇英文文章存放于文件中，每行约等于 80 个字符，每页约等于 40 行。分别放于多个文件中，并实现如下功能：（1）统计文件的个数，统计每篇文章的单词个数，统计文章中不重复单词个数（2）查找一个单词所在的文章，页号，行号，测试三种
3、情况可能的时间，该单词仅出现一次，出现多次，不出现。(2)原始数据存放于文件中的多篇英文文章三、程序总体设计（1）数据结构主程序下定义数据结构：typedef structchar dataMaxLength; /串数据域int length;/串长度2SqString;/串类型typedef structunsigned int count; /已查找到的个数int localPage100; /存放页码int localRow100; / 存放行数SearchOut; /暂存单词 100 个查找结果WordCount 类下定义数据结构：typedef struct nodechar dat
4、a; /节点数据unsigned int count /出现次数struct node *next; /next 指向下一个字母节点struct node *sibling; / sibling 指向相邻节点Word;/统计下节点类型typedef structint top;/栈顶Word* dataMaxLength; /栈数据域Stack; /输出统计结果字母栈类型（2）模块划分和层次结构划分和层次结构3（3）函数原型清单主程序下函数清单函数原型：void countAllPaper() 函数功能：统计所有文件中单词函数原型：void Search()4函数功能：查找函数函数原型：voi
5、d getFiles(unsigned int &files_num,char filenameMaxFiles20)函数功能：获取文件夹下所有 txt 文件：files_num 为文件数，filename为文件名数组函数原型：unsigned int WINAPI count(PVOID param)函数功能：线程函数用于统计单词函数原型：void OutFile(SearchOut &s,FILE *fout)函数功能：将暂存于 SearchOut 的查找结果输入文件函数原型：int Mate(SqString t)函数功能：查找单词 SqString t 返回查找时间WordCount
6、类下函数清单Public：构造函数：WordCount(char* filesname)函数功能：统计 filesname 文件的所有单词函数原型：unsigned int getUsedTime(void)函数功能：获取 WordCount 对象的 usedTime 值Private：5函数原型：void Init(Word *&node,int ch)函数功能：使用 ch 字符初始化节点函数原型：void Insert(Word *&p,char ch)函数功能：在 p 节点前插入值域为 ch 的节点函数原型：void JoinTree(Word *&p,char ch)函数功能：将字母字
7、符 ch 插入 p 节点的 next 域函数原型：void Fout(Word *r,int &d,FILE* fout)函数功能：将树 r 保存通过 fout 输出6（4）程序总体框架（5）程序组织stdafx.h（主程序头文件）：定义程序需要使用到的常量、结构体，引用程序所需要的文件。Article.cpp（主程序源文件）：主要包含主程序的函数具体实现方法。WordCount.h（类头文件）：主要包含类成员、方法声明，定义结构体和常数等 。WordCount.cpp（类源文件）：主要包含函数具体实现方法。7四、功能模块函数设计和调试（一）算法描述：（1）统计单词模块统计单词模块使用树形存储
8、结构（如下图）和类设计实现，实现过程如下：类（WordCount）在构造时（使用WordCount（char *）构造函数） ，每次从文件中读取一个字符时，并判断是否为字母字符。若为字母字符，则将在当前节点（假设为 q）的 next 域（下一层）的节点中查找到一个字母的合适位置（使每一层有序） ，若该层没有该字母的节点则新建节点。反复读取字符，直到读取一个非字母字符，则将 q-count 加 1，q=root（root 为根） 。反复上述过程直到文件读完整篇文章。最后，将树遍历并输到文件8树形存储结构统计单词模块流程图9（2）查找单词模块查找单词时，实现过程如下：每次从文件中读取字符以填满数组
9、 temp80，再将数组头指针（first）置为 0，使数组尾指针（rear）指向最后一个非字母字符并将其置为n （如下图 1） 。将目标单词（SqString t）与数组比较，若匹配长度为 t.length，比较第 t.length 是否为字母，若并不为字母则记录单词位置，否则不记录。数组头指针指向下一个非字母字符，若该字符为n ，行加 1。读取下一个字符，重复匹配过程直到 first=rear 或 tempfirst=EOF 则退出本循环。将 temp 数组中 rear 后的字符复制到 temp 前面单元，重复上诉过程，直到文章结束。图 110查找单词模块流程图11（二）程序调试（1）统计
10、单词（2）查找单词12五、程序清单主程序：stdafx.h#pragma once#include targetver.h#include #include #include#include#include #include #include #include #include #define MaxFiles 30/文件夹下最多文件数#define FileNameLength 20/文件名最大长度#define PageSize 40/单页最大行数#define MaxLength 30/单词最大长度#define RowSize 80/单行最大长度#define pathIn F:Tes
11、tpaper#define pathOut F:Testcount13typedef structchar dataMaxLength;int length;SqString;/串typedef structunsigned int count;int localPage100,localRow100;/存放页码，行数SearchOut;/暂存单词查找结果typedef structchar filesMaxFiles/2FileNameLength;/unsigned int files_num;/文件数Param;/用于多线程传参数Article.cpp#include stdafx.h#
12、include WordCount.hvoid getFiles(unsigned int &files_num,char filenameMaxFiles20)/获取F:Testpaper文件夹下所有txt文件 files_num文件数 filename文件名数组long Handle;files_num=0;14struct _finddata_t FileInfo;char path50=pathIn;strcat(path,*.txt);if(Handle=_findfirst(path,&FileInfo)=-1L)printf(没有找到匹配的项目n);elseint i=0;for
13、(;FileInfo.namei!=0;i+)/将FileInfo.namei复制到filename数组filenamefiles_numi=FileInfo.namei;filenamefiles_numi=0;/添加0files_num+;while( _findnext(Handle,&FileInfo)=0&files_num=0;k-)/k指向最后一个非字母if(tempkz|(tempkZ&tempk=0)tempk=n;/换为换行符19k=0;/k指向temp头ch=tempk;/开始匹配，直到文章结束为止while(kz|(chZ&ch=a&ch=A)&kPageSize)/PageSize为最大行数row=1;page+;ch=temp+k;if(ch=EOF)flag=true;usedtime=clock()-t1;OutFile(s,fout);/读完一篇输出sfprintf(fout,the numbre of words:%d,s.count);fprintf(fout,nused time:%d,usedtime);fclose(fin);totaltime+=usedtime;fprintf(fout,nnUsed totaltime:%d,totaltime);fclose(fout);return totaltime;void Se
