数据结构优秀课程设计.docx

数据结构课程设计汇报题 目： 文章中单词查找 专 业： 软件工程 起止时间： .07.06.07.10 集美大学计算机工程学院软件工程教研室制 年 7 月 09日目 录一 引言1二系统功效和原始数据1三 程序总体设计1四 功效模块函数设计和调试5五 程序清单9六 课程设计总结19七 参考资料19一、引言本课程实习是在理论学习和基础试验基础上，学习开发规模较大程序，利用已掌握应用数据结构来处理实际问题基础方法。经过对程序结构分析，设计和开发过程，提升综合应用数据结构能力，为学习软件专业课程创建较扎实理论基础和实践基础。此次任务是设计一个能够实现从存放多篇英文文章文件目录中读取文件，并统计各篇文章单词个数，或查找指定单词在各篇文章中出现位置程序，并激励开发者经过多个渠道提升程序运行效率。经过此次课程设计不仅能够加深对所学知识了解也提升了把知识应用到实践中能力。二、系统功效和原始数据(1)系统功效有多篇英文文章存放于文件中，每行约等于80个字符，每页约等于40行。分别放于多个文件中，并实现以下功效：（1）统计文件个数，统计每篇文章单词个数，统计文章中不反复单词个数（2）查找一个单词所在文章，页号，行号，测试三种情况可能时间，该单词仅出现一次，出现数次，不出现。(2)原始数据存放于文件中多篇英文文章三、程序总体设计（1）数据结构主程序下定义数据结构：typedef structchar dataMaxLength; /串数据域int length;/串长度SqString;/串类型typedef structunsigned int count; /已查找到个数int localPage100; /存放页码int localRow100; / 存放行数SearchOut; /暂存单词100个查找结果WordCount类下定义数据结构：typedef struct nodechar data; /节点数据unsigned int count /出现次数struct node *next; /next指向下一个字母节点struct node *sibling; / sibling指向相邻节点Word;/统计下节点类型typedef structint top;/栈顶Word* dataMaxLength; /栈数据域Stack; /输出统计结果字母栈类型（2）模块划分和层次结构划分和层次结构（3）函数原型清单主程序下函数清单函数原型：void countAllPaper() 函数功效：统计全部文件中单词函数原型：void Search()函数功效：查找函数函数原型：void 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类下函数清单Public：结构函数：WordCount(char* filesname)函数功效：统计filesname文件全部单词函数原型：unsigned int getUsedTime(void)函数功效：获取WordCount对象usedTime值Private：函数原型：void Init(Word *&node,int ch)函数功效：使用ch字符初始化节点函数原型：void Insert(Word *&p,char ch)函数功效：在p节点前插入值域为ch节点函数原型：void JoinTree(Word *&p,char ch)函数功效：将字母字符ch插入p节点next域函数原型：void Fout(Word *r,int &d,FILE* fout)函数功效：将树r保留经过fout输出（4）程序总体框架（5）程序组织stdafx.h（主程序头文件）：定义程序需要使用到常量、结构体，引用程序所需要文件。Article.cpp（主程序源文件）：关键包含主程序函数具体实现方法。WordCount.h（类头文件）：关键包含类组员、方法申明，定义结构体和常数等 。WordCount.cpp（类源文件）：关键包含函数具体实现方法。四、功效模块函数设计和调试（一）算法描述：（1）统计单词模块统计单词模块使用树形存放结构（以下图）和类设计实现，实现过程以下：类（WordCount）在结构时（使用WordCount（char *）结构函数），每次从文件中读取一个字符时，并判定是否为字母字符。若为字母字符，则将在目前节点（假设为q）next域（下一层）节点中查找到一个字母适宜位置（使每一层有序），若该层没有该字母节点则新建节点。反复读取字符，直到读取一个非字母字符，则将q-count加1，q=root（root为根）。反复上述过程直到文件读完整篇文章。最终，将树遍历并输到文件树形存放结构统计单词模块步骤图（2）查找单词模块查找单词时，实现过程以下：每次从文件中读取字符以填满数组temp80，再将数组头指针（first）置为0，使数组尾指针（rear）指向最终一个非字母字符并将其置为n（以下图1）。将目标单词（SqString t）和数组比较，若匹配长度为t.length，比较第t.length是否为字母，若并不为字母则统计单词位置，不然不统计。数组头指针指向下一个非字母字符，若该字符为n，行加1。读取下一个字符，反复匹配过程直到first=rear或tempfirst=EOF则退出本循环。将temp数组中rear后字符复制到temp前面单元，反复上诉过程，直到文章结束。图1查找单词模块步骤图（二）程序调试（1）统计单词（2）查找单词五、程序清单主程序：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:Testpaper#define pathOut F:Testcounttypedef 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#include WordCount.hvoid getFiles(unsigned int &files_num,char filenameMaxFiles20)/获取F:Testpaper文件夹下全部txt文件 files_num文件数 filename文件名数组long Handle;files_num=0;struct _finddata_t FileInfo;char path50=pathIn;strcat(path,*.txt);if(Handle=_findfirst(path,&FileInfo)=-1L)printf(没有找到匹配项目n);elseint i=0;for(;FileInfo.namei!=0;i+)/将FileInfo.namei复制到filename数组filenamefiles_numi=FileInfo.namei;filenamefiles_numi=0;/添加0files_num+;while( _findnext(Handle,&FileInfo)=0&files_numMaxFiles)for(i=0;FileInfo.namei!=0;i+)/将FileInfo.namei复制到filename数组filenamefiles_numi=FileInfo.namei;filenamefiles_numi=0;/添加0files_num+;_findclose(Handle);/线程函数unsigned int WINAPI count(PVOID param)WordCount(char*)param);printf(222);return NULL;void countAllPaper()/统计全部文件char filesMaxFiles20;/存放文件列表数组MaxFiles为可读最大文件数，20为文件名长度unsigned int files_num=0;getFiles(files_num,files);HANDLE hThreadMaxFiles;unsigned int threadID;/设置参数clock_t t1=clock();/创建线程printf();for(int i=0;ifiles_num;i+)hThreadi=(HANDLE)_beginthreadex(NULL,0,count,filesi,0,&threadID);/等候线程结束for(int i=0;ifiles_num;i+)WaitForSingleObject(hThreadi, -1);CloseHandle(hThreadi);printf(n已统计该文件夹下%d个txt文件单词个数,n此次统计耗时:%dmsn,files_num,clock()-t1);printf(注：统计结果存放于%s目录下n,pathOut);void InitSqString(SqString &s,char str)int i;for(i=0;stri!=0;i+)s.datai=stri;s.datai=0;s.length=i;/输出查找结果到文件void OutFile(SearchOut &s,FILE *fout)/if(s.count=0)fputs(There is no word which you want in this article.n,fout);return;for(int i=0;is.count%100;i+)fprintf(fout,%dt%dn,s.localPagei,s.localRowi);/查找单词int Mate(SqString t)clock_t t1;int j=0,page,row,k,rear; /k为数组头指针，first为尾指针bool flag;char ch,filesMaxFiles20,inFile50,outFile50=pathOut;char temp81;/files存放文件列表数组MaxFiles为可读最大文件数，20为文件名长度strcat(outFile,SearchResult.txt);unsigned int files_num=0,totaltime=0,usedtime;/文件个数getFiles(files_num,files);SearchOut s;FILE *fin,*fout;if(fout=fopen(outFile,w)=NULL)printf(Cant creat a new txt:%sn,outFile);return -1;fprintf(fout,Word %s in every article location(pagetrow):n,t.data);for(unsigned int i=0;ifiles_num;i+)/打开文件strcpy(inFile,F:Testpaper);strcat(inFile,filesi);if(fin=fopen(inFile,r)=NULL)printf(cant open %sn,inFile);return -1;/初始化s.count=0;page=row=1;rear=79;flag=false;/文件末尾标志fprintf(fout,nnWord in %s location:n,filesi);t1=clock();while(!flag)rear+;for(k=0;rear80;k+,rear+)tempk=temprear;for(;k=0;k-)/k指向最终一个非字母if(tempkz|(tempkZ&tempk=0)tempk=n;/换为换行符k=0;/k指向temp头ch=tempk;/开始匹配，直到文章结束为止while(k(rear)&ch!=EOF) /rear为temp可读长度j=0;while(ch=t.dataj&jt.length)ch=temp+k;/指向下一个字符j+;if(j=t.length) /匹配if(chz|(chZ&ch=a&ch=z)|(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 Search()char searchMaxLength;SqString t;int time;printf(请输入要查找单词：);fflush(stdin);/清空输入缓冲区scanf(%s,search);InitSqString(t,search);time=Mate(t);if(time!=-1)printf(已统计可匹配单词：%sn,search);printf(此次统计耗时:%d msn,time);elseprintf(统计失败，请检验后再试！n);int _tmain(int argc, _TCHAR* argv)char ifContinue;int choose;doprintf(Welcomen);printf(*请将需要统计英文文章存放于%s目录下n,pathIn);printf(ntttt1、统计单词nntttt2、查找单词n);printf(n);printf(请输入功效号(1/2)：);fflush(stdin);/清空输入缓冲区scanf(%d,&choose);if(choose=1)countAllPaper();else if(choose=2)Search();printf(统计结果已存放于%sSearchResult.txt目录下文档.n,pathOut);elseprintf(输入不正确！n);fflush(stdin);printf(n是否继续？(Y/y)：);scanf(%c,&ifContinue);std:system(CLS);while(ifContinue=Y|ifContinue=y);printf(nntt程序已退出.nnn);printf(n);system(pause);return 0;WordCount类：WordCount.h#pragma oncetypedef struct nodechar data;unsigned int count;struct node *next,*sibling;Word;typedef structint top;Word* dataMaxLength;Stack;class WordCountprivate:Stack St;Word *root;unsigned int usedTime;void InitStack(Stack &s);void Init(Word *&node,int ch);void Insert(Word *&p,char ch);void JoinTree(Word *&p,char ch);void Fout(Word *r,int &d,FILE* fout,unsigned int &sum);public:WordCount();WordCount(char* filesname);unsigned int getUsedTime(void);WordCount(void);WordCount.cpp#include StdAfx.h#include WordCount.hWordCount:WordCount()WordCount:WordCount(char* filename)char outFile50=pathOut,inFile50=pathIn;/文件名char s120;char ch;/文件读入字符,outTxt_Name文件名int i=0,d=0;/d为不一样单词数,j为目前行截止下标unsigned int sum=0;root=new Word();Word* p=root;InitStack(St);clock_t t1;/生成文件目录和文件名for(i=0;filenamei!=.;i+)s1i=filenamei;s1i=0;strcat(outFile,s1);strcat(outFile,Count.txt0);strcat(inFile,filename);FILE *fin,*fout;if(fin=fopen(inFile,r)=NULL)printf(cant open %sn,inFile);elseif(fout=fopen(outFile,w)=NULL)printf(cant creat a new txt: %sn,outFile);t1=clock();/开始计时while(ch=fgetc(fin)!=EOF)/开始统计个数JoinTree(p,ch);usedTime=clock()-t1;fclose(fin);Fout(root-next,d,fout,sum);fprintf(fout,%s%d,the number of all words:,sum);fprintf(fout,%s%d,nthe number of different words:,d);fprintf(fout,%s%d,nused time:,usedTime);/将计时差存入txtfclose(fout);WordCount:WordCount(void)void WordCount:InitStack(Stack &s)s.top=-1;void WordCount:Init(Word *&node,int ch)node=new Word();node-data=ch;node-count=0;node-sibling=node-next=NULL;void WordCount:Insert(Word *&p,char ch)/p节点前插入新节点Word *newnode;/p节点后插入新节点newnodeInit(newnode,p-data);newnode-sibling=p-sibling;p-sibling=newnode;newnode-count=p-count;/将p值给予newnodenewnode-next=p-next;p-next=NULL;/p节点赋新值p-data=ch;p-count=0;void WordCount:JoinTree(Word *&p,char ch)/将读入字母字符加入树if(ch=a&ch=z)|(ch=A)/是否为字母if(p-next=NULL)Word *newnode;/创建并初始化节点Init(newnode,ch);p-next=newnode;p=p-next;return;p=p-next;while(p-sibling!=NULL&p-datasibling;if(p-data=ch)return;else if(p-datach)Insert(p,ch);/在p前面插入新节点return;else if(p-sibling=NULL)Word *newnode;/创建并初始化节点Init(newnode,ch);p-sibling=newnode;p=newnode;elsep-count+;p=root;void WordCount:Fout(Word *r,int &d,FILE* fout,unsigned int &sum)/将单词个数输出，root为树根if(r=NULL)return;St.data+St.top=r;if(r-count!=0)d+;int i=0;char inStMaxLength;for(;idata;inSti+=t;inSti=0;fprintf(fout,%s%dn,inSt,r-count);sum+=r-count;Fout(r-next,d,fout,sum);St.top-;Fout(r-sibling,d,fout,sum);unsigned int WordCount:getUsedTime()return usedTime;六、总结经过此次课程设计我中我付出了部分，也收获了部分。在实现多线程编程时，因为我们是在C/C+环境在设计程序，所以选择使用_beginhreadex()方法创建一个安全性更高线程。但_beginhreadex()方法和CreateTread（）方法参数不一样且网上相关_beginhreadex()示例也少部分，所以费了些时间了解_beginhreadex()方法使用。再有，在传参数时，因为之前对char，char*，string区分不是很清楚也花了部分时间。在完成匹配模块功效时，我最先想到使用KMP算法，而且也确实做到匹配。不过，结果和预期并不一致，我这才恍然大悟KMP算法匹配子串，但并不能确保匹配字串是一个单词（如：假设目标单词为with，KMP算法认为without中with也是符合要求，但实际上without中with并不是我们要）。然而，觉察到错误以后，我只是在原先KMP算法上修修补补，造成我对预想匹配算法逐步模糊，所以即使花费很多时间也没能完成匹配功效，最终我删掉全部代码并根据预想思绪重新编写很快就实现算法功效。总而言之，经过此次试验我看到了本身很多需要提升地方，当然也在其它方面提升了很多。经过此次课程设计我也了解到了在一个程序设计开发过程中，一个优异数据结构对程序实现也是至关关键。即使此次课程设计规模不大，但还是为我以后编程学习打下了基础。在编程过程中，我也体会到了学习编程辛劳。参考资料： 1 Jeffrey Richter.Windows关键设计(第五版).北京：清华大学出版社，