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

数据结构课程
设计汇报

题  目： 文章中单词查找

专 业： 软件工程

起止时间： .07.06－.07.10

集美大学计算机工程学院软件工程教研室制
年 7 月 09日 

目 录

一 引言 1
二系统功效和原始数据 1
三 程序总体设计 1
四 功效模块函数设计和调试 5
五 程序清单 9
六 课程设计总结 19
七 参考资料 19

一、引言
本课程实习是在理论学习和基础试验基础上，学习开发规模较大程序，利用已掌握应用数据结构来处理实际问题基础方法。经过对程序结构分析，设计和开发过程，提升综合应用数据结构能力，为学习软件专业课程创建较扎实理论基础和实践基础。此次任务是设计一个能够实现从存放多篇英文文章文件目录中读取文件，并统计各篇文章单词个数，或查找指定单词在各篇文章中出现位置程序，并激励开发者经过多个渠道提升程序运行效率。经过此次课程设计不仅能够加深对所学知识了解也提升了把知识应用到实践中能力。
二、系统功效和原始数据
(1)系统功效
有多篇英文文章存放于文件中，每行约等于80个字符，每页约等于40行。分别放于多个文件中，并实现以下功效：
（1）统计文件个数，统计每篇文章单词个数，统计文章中不反复单词个数
（2）查找一个单词所在文章，页号，行号，测试三种情况可能时间，该单词仅出现一次，出现数次，不出现。
(2)原始数据
存放于文件中多篇英文文章
三、程序总体设计
（1）数据结构
主程序下定义数据结构：
typedef struct{
char data[MaxLength]; //串数据域
int length;//串长度
}SqString;//串类型
typedef struct{
unsigned int count; //已查找到个数
int localPage[100]; //存放页码
int localRow[100]; // 存放行数
}SearchOut; //暂存单词100个查找结果

WordCount类下定义数据结构：
typedef struct node{
char data; //节点数据
unsigned int count //出现次数
struct node *next; //next指向下一个字母节点
struct node *sibling; // sibling指向相邻节点
}Word;//统计下节点类型
typedef struct{
int top;//栈顶
Word* data[MaxLength]; //栈数据域
}Stack; //输出统计结果字母栈类型

（2）模块划分和层次结构
划分和层次结构

（3）函数原型清单
主程序下函数清单
函数原型：void countAllPaper()
函数功效：统计全部文件中单词

函数原型：void Search()
函数功效：查找函数

函数原型：void getFiles(unsigned int &files_num,char filename[MaxFiles][20])
函数功效：获取文件夹下全部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）查找单词模块
查找单词时，实现过程以下：
每次从文件中读取字符以填满数组temp[80]，再将数组头指针（first）置为0，使数组尾指针（rear）指向最终一个非字母字符并将其置为’\n’（以下图1）。将目标单词（SqString t）和数组比较，若匹配长度为t.length，比较第t.length是否为字母，若并不为字母则统计单词位置，不然不统计。数组头指针指向下一个非字母字符，若该字符为‘\n’，行加1。读取下一个字符，反复匹配过程直到first〉=rear或temp[first]==EOF则退出本循环。将temp数组中rear后字符复制到temp前面单元，反复上诉过程，直到文章结束。

图1查找单词模块步骤图

（二）程序调试
（1）统计单词

（2）查找单词

五、程序清单
主程序：
stdafx.h
#pragma once

#include "targetver.h"
#include <process.h>
#include <Windows.h>
#include<conio.h>
#include<io.h>
#include <time.h>
#include <string.h>
#include <stdio.h>
#include <tchar.h>
#include <iostream>
#define MaxFiles 30//文件夹下最多文件数
#define FileNameLength 20//文件名最大长度
#define PageSize 40//单页最大行数
#define MaxLength 30//单词最大长度
#define RowSize 80//单行最大长度
#define pathIn "F:\\Test\\paper\\"
#define pathOut "F:\\Test\\count\\"

typedef struct{
char data[MaxLength];
int length;
}SqString;//串
typedef struct{
unsigned int count;
int localPage[100],localRow[100];//存放页码，行数
}SearchOut;//暂存单词查找结果
typedef struct{
char files[MaxFiles/2][FileNameLength];//
unsigned int files_num;//文件数
}Param;//用于多线程传参数

Article.cpp
#include "stdafx.h"
#include "WordCount.h"

void getFiles(unsigned int &files_num,char filename[MaxFiles][20]){//获取"F:\Test\paper"文件夹下全部txt文件 files_num文件数 filename[]文件名数组
long Handle;
files_num=0;
struct _finddata_t FileInfo;
char path[50]=pathIn;
strcat(path,"*.txt");
if((Handle=_findfirst(path,&FileInfo))==-1L)
printf("没有找到匹配项目\n");
else
{
int i=0;
for(;FileInfo.name[i]!='\0';i++)//将FileInfo.name[i]复制到filename数组
filename[files_num][i]=FileInfo.name[i];
filename[files_num][i]='\0';//添加‘\0’
files_num++;

while( _findnext(Handle,&FileInfo)==0&&files_num<MaxFiles){
for(i=0;FileInfo.name[i]!='\0';i++)//将FileInfo.name[i]复制到filename数组
filename[files_num][i]=FileInfo.name[i];
filename[files_num][i]='\0';//添加‘\0’
files_num++;
}
_findclose(Handle);
}
}
//线程函数
unsigned int WINAPI count(PVOID param){
WordCount((char*)param);
printf("\2\2\2");
return NULL;
}
void countAllPaper(){//统计全部文件
char files[MaxFiles][20];//存放文件列表数组MaxFiles为可读最大文件数，20为文件名长度
unsigned int files_num=0;
getFiles(files_num,files);
HANDLE hThread[MaxFiles];
unsigned int threadID;
//设置参数
clock_t t1=clock();
//创建线程
printf("—————");
for(int i=0;i<files_num;i++){
hThread[i]=(HANDLE)_beginthreadex(NULL,0,count,files[i],0,&threadID);}
//等候线程结束
for(int i=0;i<files_num;i++){
WaitForSingleObject(hThread[i], -1);
CloseHandle(hThread[i]);
}
printf("—————\n已统计该文件夹下%d个txt文件单词个数,\n此次统计耗时:%dms\n",files_num,clock()-t1);
printf("注：统计结果存放于%s目录下\n",pathOut);
}
void InitSqString(SqString &s,char str[]){
int i;
for(i=0;str[i]!='\0';i++){
s.data[i]=str[i];
}
s.data[i]='\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;i<s.count%100;i++)
fprintf(fout,"%d\t%d\n",s.localPage[i],s.localRow[i]);
}
//查找单词
int Mate(SqString t){
clock_t t1;
int j=0,page,row,k,rear; //k为数组头指针，first为尾指针

bool flag;
char ch,files[MaxFiles][20],inFile[50],outFile[50]=pathOut;
char temp[81];
//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("Can't creat a new txt:%s\n",outFile);
return -1;
}
fprintf(fout,"Word \"%s\" in every article location(page\trow):\n",t.data);
for(unsigned int i=0;i<files_num;i++){
//打开文件
strcpy(inFile,"F:\\Test\\paper\\");
strcat(inFile,files[i]);
if((fin=fopen(inFile,"r"))==NULL){
printf("can't open %s\n",inFile);
return -1;
}
//初始化
s.count=0;
page=row=1;
rear=79;
flag=false;//文件末尾标志
fprintf(fout,"\n\nWord in %s location:\n",files[i]);
t1=clock();
while(!flag){
rear++;
for(k=0;rear<80;k++,rear++)
temp[k]=temp[rear];
for(;k<80;k++)//读满temp
temp[k]=fgetc(fin);
k--;//k指向最终一个字符

for(;k>=0;k--){//k指向最终一个非字母
if(temp[k]<'A'||temp[k]>'z'||(temp[k]>'Z'&&temp[k]<'a'))
break;
}
rear=k;//rear指向最终一个非字母
if(k>=0)
temp[k]='\n';//换为‘换行符’
k=0;//k指向temp头
ch=temp[k];
//开始匹配，直到文章结束为止
while(k<(rear)&&ch!=EOF) {//rear为temp可读长度
j=0;
while(ch==t.data[j]&&j<t.length){
ch=temp[++k];//指向下一个字符
j++;
}

if(j==t.length){ //匹配
if(ch<'A'||ch>'z'||(ch>'Z'&&ch<'a')){
s.localPage[s.count%100]=page;
s.localRow[s.count%100]=row;
s.count++;//s已满，输出并初始化
if(s.count%100==99){
OutFile(s,fout);
}
}
}
while((ch>='a'&&ch<='z')||(ch<='Z'&&ch>='A')&&k<rear)//单词间以非字母隔开
ch=temp[++k]; //若为换行符，则行数加1
if ( ch=='\n') {
row++;
if(row>PageSize){//PageSize为最大行数
row=1;
page++;
}
}
ch=temp[++k];
}
if(ch==EOF)
flag=true;
}
usedtime=clock()-t1;
OutFile(s,fout);//读完一篇输出s
fprintf(fout,"the numbre of words:%d",s.count);
fprintf(fout,"\nused time:%d",usedtime);
fclose(fin);
totaltime+=usedtime;
}
fprintf(fout,"\n\nUsed totaltime:%d",totaltime);
fclose(fout);
return totaltime;
}
void Search(){
char search[MaxLength];
SqString t;
int time;

printf("请输入要查找单词：");
fflush(stdin);//清空输入缓冲区
scanf("%s",search);
InitSqString(t,search);
time=Mate(t);
if(time!=-1){
printf("已统计可匹配单词：%s\n",search);
printf("此次统计耗时:%d ms\n",time);
}
else
printf("统计失败，请检验后再试！\n");
}
int _tmain(int argc, _TCHAR* argv[])
{
char ifContinue;
int choose;
do{
printf("——————————————————Welcome——————————————————\n");
printf("*请将需要统计英文文章存放于%s目录下\n",pathIn);
printf("\n\t\t\t\t1、统计单词\n\n\t\t\t\t2、查找单词\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);
}
else
printf("输入不正确！\n");

fflush(stdin);
printf("\n是否继续？(Y/y)：");
scanf("%c",&ifContinue);
std::system("CLS");
}while(ifContinue=='Y'||ifContinue=='y');
printf("\n\n\t\t程序已退出........\n\n\n");
printf("————————————————————————————————————————\n");
system("pause");
return 0;
}
WordCount类：
WordCount.h
#pragma once
typedef struct node{
char data;
unsigned int count;
struct node *next,*sibling;
}Word;
typedef struct{
int top;
Word* data[MaxLength];
}Stack;

class WordCount
{
private:
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.h"
WordCount::WordCount(){}
WordCount::WordCount(char* filename)
{
char outFile[50]=pathOut,inFile[50]=pathIn;//文件名
char s1[20];
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;filename[i]!='.';i++)
s1[i]=filename[i];
s1[i]='\0';
strcat(outFile,s1);
strcat(outFile,"Count.txt\0");
strcat(inFile,filename);

FILE *fin,*fout;
if((fin=fopen(inFile,"r"))==NULL){
printf("can't open %s\n",inFile);
}
else{
if((fout=fopen(outFile,"w"))==NULL){
printf("can't creat a new txt: %s\n",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);//将计时差存入txt
fclose(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节点后插入新节点newnode
Init(newnode,p->data);
newnode->sibling=p->sibling;
p->sibling=newnode;

newnode->count=p->count;//将p值给予newnode
newnode->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<='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->data<ch)
p=p->sibling;
if(p->data==ch)
return;
else if(p->data>ch){
Insert(p,ch);//在p前面插入新节点
return;
}
else if(p->sibling==NULL){
Word *newnode;//创建并初始化节点
Init(newnode,ch);
p->sibling=newnode;
p=newnode;
}
}
else{
p->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 inSt[MaxLength];
for(;i<=St.top;i++)
inSt[i]=St.data[i]->data;
inSt[i++]='\t';
inSt[i]='\0';
fprintf(fout,"%s%d\n",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关键设计(第五版).北京：清华大学出版社，