数据结构实习报告Word格式.docx
《数据结构实习报告Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构实习报告Word格式.docx（17页珍藏版）》请在冰点文库上搜索。
初始条件：
已知一个空的“文本单词串表头”；
操作结果：
生成一个空的“文本单词串序列”；
insertFileString（FSList&
FSL,stringstr,introw）;
FSL为文本字符串序列的表头str为一个标准的c++字符串，row代表了字符串出现的行数；
将str插入到文本字符串序列中，不需要排序；
若FSL为空表头，则创建一个字符串序列；
否则插在字符串序列尾部；
getFSLength（FSListFSL）;
FSL为文本字符串序列的表头；
获取以FSL为表头的文本字符串的长度
printFileString（FSListFSL）;
FSL为文本字符串序列的表头;
打印以FSL为表头的文本字符串中的所有字符串；
readFile（FSList&
从文件中读取字符串序列，并将其保留在以FSL为表头的字符串序列中；
clearFileString（FSList&
以FSL为表头的文本字符串序列被清空；
}ADTFileString
（2）定义从键盘读取的“单词串”类型：
ADTKeyString{
createKeyString（KSList&
KSL）;
已知一个空的“键盘单词串表头”；
生成一个空的“键盘单词串序列”；
insertKeyString（KSList&
KSL,stringstr,introw）;
KSL为键盘字符串序列的表头str为一个标准的c++字符串，row代表了字符串出现的行数；
将str插入到键盘字符串序列中，不需要排序；
若KSL为空表头，则创建一个字符串序列；
getKSLength（KSListKSL）;
KSL为键盘字符串序列的表头；
获取以KSL为表头的键盘字符串的长度
printKeyString（KSListKSL）;
KSL为键盘字符串序列的表头;
打印以KSL为表头的键盘字符串中的所有字符串；
readKey（KSList&
KSL为文本字符串序列的表头；
从键盘中读取字符串序列，并将其保留在以KSL为表头的字符串序列中；
clearKeyString（KSList&
以KSL为表头的文本字符串序列被清空；
}ADTKeyString
2、模块设计：
1）主程序模块：
主函数设计如下
intmain（）{
登陆界面和使用提示；
构建文本字符串序列；
构建键盘字符串序列；
构建模式匹配排除符集合；
字符串模式匹配，统计单词；
结束一轮工作，提示是否继续操作；
2）文本字符串模块-------构建文本字符串序列；
3）键盘字符串模块--------实现键盘字符串数据类型；
4）模式匹配模块------实现文本字符串和键盘字符串的匹配统计；
5）登陆界面模块--------提示用户程序使用方法
3、各模块间的调用关系：
四、详细设计
1、主程序用到的宏定义：
#defineMAX_WORD_LENGTH1000//最大字符串长度
#defineMAX_MODELEXCEPTION_LENGTH50
#defineFILE_NAME_LENGTH100//文件名长度
2、存储结构设
/**
*从文件读取的字符串集合
*/
typedefstructFileString{
stringname;
//字符串名称
introw;
//字符串所在的行
FileString*next;
//邻接字符串
}FileString,*FSList;
*从键盘读取的字符串集合
typedefstructKeyString{
int*rows;
//字符串所在行向量
intcount;
//字符串出现的次数
KeyString*next;
}KeyString,*KSList;
*匹配文本字符串和键盘字符串的模式匹配排除符集合
typedefchar*Model;
3、主要算法设计：
*在文件字符串集合中插入新的字符串
intinsertFileString（FSList&
FSL,stringstr,introw）{
if（!
FSL）//如果是空表，则创建集合
createFileString（FSL）;
FSListsp,tp;
sp=tp=FSL;
while（sp=sp->
next）
tp=sp;
FSLists=newFileString;
//插在既有的集合中
s）{
cout<
<
"
overflow!
\n"
;
}
s->
name=str;
row=row;
next=NULL;
tp->
next=s;
//顺序插入
return1;
}
*从文件中读取串
intreadFile（FSList&
FSL）{
charurl[FILE_NAME_LENGTH];
//指向文件路径的const指针
cout<
Enterthefiletoread:
gets（url）;
while（url[0]=='
\0'
）{//保证文件名不为空
Thefile'
snamecannotbenull!
endl;
gets（url）;
ifstreamfs=ifstream（url）;
//打开文件读取字符串
fs）{
Filereadswrong!
return0;
introwLine=1;
strings;
while（fs.peek（）!
=EOF）{//遇到文件尾符，结束读取
getline（fs,s,'
\n'
）;
//依行读取s
insertFileString（FSL,s,rowLine++）;
//将获取的字符串插入文件字符串集合}
*统计模式匹配排除字符
intgetModelException（Model&
model）{
model=newchar[MAX_MODELEXCEPTION_LENGTH];
//集合model能统计除了默认匹配字符外的所有客户指定的排除字符
charmatch;
Press'
y'
toaddtheModel-Exception-Character-Set\n"
cin>
>
match;
cin.ignore（）;
//避免其他方法的流操作带来负面影响
inti=0;
while（match=='
）{
if（!
i）{
cout<
Begintoreceive:
}
if（cin.peek（）=='
if（!
cout<
Nocharacterreceived"
}
Endreceiving"
break;
cin.get（model[i++]）;
//默认的模式匹配排除符
model[i]='
'
model[i+1]='
'
model[i+2]='
.'
model[i+3]='
\'
'
model[i+4]='
\"
model[i+5]='
model[i+6]='
*'
model[i+7]='
#'
model[i+8]='
!
model[i+9]='
$'
model[i+10]='
%'
model[i+11]='
^'
model[i+12]='
&
model[i+13]='
（'
model[i+14]='
）'
model[i+15]='
-'
model[i+16]='
+'
model[i+17]='
_'
model[i+18]='
|'
model[i+19]='
\\'
model[i+20]='
{'
model[i+21]='
}'
model[i+22]='
['
model[i+23]='
]'
model[i+24]='
:
model[i+25]='
model[i+26]='
model[i+27]='
model[i+28]='
?
model[i+29]='
/'
model[i+30]='
~'
model[i+31]='
\t'
model[i+32]='
//串尾标志
*模式匹配方法
boolmodelMatch（strings,Modelmodel,intpos）{
for（inti=strlen（model）-1;
i>
=0;
i--）{
if（s[pos]==model[i]）
returntrue;
returnfalse;
*查找模式串T在主串S中出现的次数
intcount（stringS,conststringT,Modelmodel）{
intcount=0;
constchar*tc=T.c_str（）;
while（i<
S.length（））{
//定义模式匹配规则----扫描排除字符
if（modelMatch（S,model,i））{//遇到模式匹配规则所定义的字符，则忽略读取
i++;
continue;
}else{//至此，S[i]肯定不是模式匹配的排除字符
char*sc=newchar[MAX_WORD_LENGTH];
char*sp=sc;
//此处的while循环保证了在读取过程中始终保证不遇到模式匹配的排除字符
while（S[i]!
='
modelMatch（S,model,i））{//未至行尾并且没有遇到
//模式匹配规则所定义
//的排除字符，则读取
*sp=S[i];
//读取子串
sp++,i++;
*sp='
//结束子串读取
strcmp（sc,tc））{//比较模式串和子串
count++;
//相等则增加计数
deletesc;
returncount;
*定位KSL中字符串在FSL中的位置
voidlocate（FSList&
FSL,KSList&
KSL,Modelmodel）{
FSL&
KSL）{
空字符串集合\n"
//exit（-1）;
return;
KSListkp=KSL;
/inti=1;
while（kp=kp->
next）{
FSListfp=FSL;
//sp是SL的副本操作
int*row=newint[getFSLength（FSL）+1];
//对于键盘字符串集合中的每个字符串，
//row都会重新申请空间
int*r=row;
kp->
rows=row;
while（fp=fp->
intc=count（fp->
name,kp->
name,model）;
if（c）{//kp->
name在fp->
name出现了，则统计其位置
kp->
count+=c;
*r=fp->
row;
r++;
*r=0;
//堆栈指针指向空间最后单元的下个单元赋NULL值
五、调试报告：
1、程序在设计过程中主要遇到了如下几个主要的问题：
1）从文本中读取文件时的错误。
最典型的错误就是当键入的文件名为空时，程序会抛掷异常，且给出严重的警告。
该问题的发现，是在我对主程序模块作了添加一个do{}while（）循环后发现的。
经过调试分析，我发现问题在于readFile（FSList&
FSL）
模块中的语句：
gets（url）；
当第一轮循环结束后，欲再继续二轮循环时，会执行指令：
cin>
on；
该语句只接受了on的赋值，却将enter键传给了下一轮的gets（url）；
从而导致错误。
我初步的修改是取一个折中的方法，在readFile（FSList&
FSL）模块中添加语句：
cin.ignore（）；
这样自然会忽略enter键的键入，但使得初次循环在输入文件名时，要先回车，后输入文件回车。
给用户很不好理解的困惑。
于是，我又再次修改：
将cin.ignotrz（）添加到主程序模块中cin>
语句之后；
这样就可以忽略enter，同时又保证程序模块可以复用，不会产生读取错误，如当前版本所示。
2）在统计单词匹配时发生的错误。
这里的主要问题是关于模式匹配排除符的把握问题
，具体体现在算法count（stringS,conststringT,Modelmodel）中。
模式匹配排除是我自己在设计程序的过程中提出的一个术语。
我起初并没有想过提出这么一个概念，而是想以一个condition的bool变量来表示。
后来，我看到若手工指定排除符，则condition的内容就是变化的，而且随着定义的排除符的数目的不同，每次对condition的修改都会引起程序大规模的改动。
特别是在我想到将condition区分为用户特别指定和程序初始化时的默认分配情况时，这种由condition控制的表示就越来越有问题，这迫使我想到用一种数据结构来封装和模式匹配的相关操作。
于是，我提出了模式匹配排除符的概念，并且对其作了相应的处理。
其中，仿照windows程序的消息机制，我也对排除符做了相应的规划，区分为特别的排除符和默认的排除符，具体的实现机制在getModelException（Model&
model）算法中。
3）程序设计中对动态内存分配的妥善处理。
由于文本字符串序列和键盘字符串序列长度的不确定性，而且又用到了链式存储结构，故对内存分配的处理是很关键的。
本程序中new操作多达7次（在不考虑是否处于循环体中的情况下）。
其中算法
locate（FSList&
KSL,Modelmodel）在动态分配了内存给rows变量后，并没有回收内存，这就考虑到跨模块去回收内存的问题。
我定义了一个clear***（）函数，用来清理由FSList和KSList所申请到的内存。
clear***（）要求对字符串序列的统计操作后，立即调用它来释放内存，保证不会产生内存泄露。
2、程序的时空复杂度分析：
设从文本中依行读取的字符串平均长度为L，其行数为m，待统计单词平均长度为S，其个数为n，则程序的时间消耗主要用于统计定位操作上。
对于modelMatch（）算法，其时间复杂度为：
O（L）;
对于count（）算法，其时间复杂度为：
O（L*L）,这是因为count（）中调用了modelMatch（）；
对于locate（）算法，其时间复杂度为：
O（L*L*n*m）；
这是因为调用了count（）。
从空间角度来看，辅存空间依然消耗在统计和定位上，还包括在构建单词穿序列上。
对于count（）算法，其空间复杂度为O（L）;
对于locate（）算法，其空间复杂度为O（m*n）；
这是因为要为KSL的rows动态分配内存；
构建单词串的时间复杂度为O（m+n）；
从时空复杂度来看，这个程序实际上效率其实并不是很高。
我统计过，当统计单词数在5个以上时，就会有延时倾向；
当统计的单词数控制在12个以上时，查找延时相当明显，约有0.5秒的间隔出现。
当统计单词数为15个时，有1秒延迟，当统计超过17个单词时
有1.5-2秒的延迟。
此外，输入的单词的特征也对统计延时有影响，当待统计的单词与文本串中读取的单词长度相当时，统计延时最大；
而待统计单词过长或过短，都不会有太大的影响。
由此可见，单词长度对统计的影响，无论时时间复杂度还是空间复杂度，都是很突出的。
3、程序的扩展方向：
程序还不能完全处理汉字串的情况，可以向着类似offic和一般的文本编辑工具所提供的全字匹配查找与一般查找方向拓展，真正做到“一查即得，一查即准”。
同时，针对统计延时，可以在参考KMP算法的同时，加以优化改良。
六、经验体会：
1）理解分析问题的能力得到提高。
设计一个应用程序关键是对要求做最准确的把握，也就是说弄清楚需求分析是很重要的。
本程序要求我从文件中读取单词的位置，就是在文件中检索字符串，这样一抽象，问题的脉络就清晰了。
接下来，如何读取，读取后如何映射，映射的字符串又怎么和待查字符串关联，这就构成了解决问题的几大关键模块。
逐个解析，整个程序的框架就了然于胸了。
特别要指出的是，对整个程序的把握，随着编程工作的深入，是越来越深刻，而且新的思路也是层出不穷。
2）创新意识和创新能力的提高。
本程序的设计，我最开始的想法是按照习题集上所指导的参考KMP算法，后来，我放弃了KMP算法，原因有两个，其一是KMP算法的缺陷，就我的了解来看，getlength中含有一部分是length，若用KMP算法来检索length，肯定会认为getlength也算作length的出处。
这显然不合单词的定义要求。
其二是我想自己设计一种新的算法来挑战自己，挑战自己的数据结构与算法设计能力。
这也是最重要的原因。
于是，在这种动力的催动下，我设计出了新的算法，如源程序中的locate（）和count（）所示的定位和统计方法。
撇开算法的性能来看，本人的创新能力是值得肯定的。
而分析到算法的执行性能，本人认为也是可以得到肯定的。
通过这个项目的课程设计，我真正提高了创新意识和创新能力。
3）对程序设计语言的细微之处又了更深刻的理解。
由于字符串的操作是很原始的几于原子的操作，所以更能看清楚平时我们所用的字符串操作函数在底层的实现机制，尽管我的实现和标准字符串的实现原理和实施手段会又不同，但是根本认识也差的不远。
同时，对指针也有了新的认识，譬如程序中有一处检验指针操作是否到了结束处，我惯用的就是
while（p）,j结果陷入了死循环，非得用while（*p）来检测，这就让我对new和指针的本质有了更深刻的认识。
再就是有时候p==NULL和!
p其实不是一回事。
这些平时不在意的问题，这次统统暴露了。
七、测试结果：
1）测试用例设计：
以本程序的源程序assistant.cpp模拟英文小说，以其中的某些关键字和常量模拟待查找形容词，如ifelsewhilenewfordeleteincludecout等
2）测试结果如下：
图1屏幕提示信息
图2输入文件和待统计的单词
（使用默认模式匹配排除符，不打印文件）
图3打印单词统计结果
图4结束测试
升级会员 