数据结构实习报告.pdf

《数据结构实习报告.pdf》由会员分享，可在线阅读，更多相关《数据结构实习报告.pdf（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数 据 结 构 实 习 报 告 题 目：文学研究助手 班 级：业计算 10 专本 姓 名：xxxxx 完成日期:2011-5-15 一、问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。二、需求分析：1、文本串非空且以文件形式存放，统计匹配的词集非空。文件名和词集均用户从键盘输入；2、“单词”定义：由字母构成的字符序列，中间不含空格字符且区分

2、大小写；3、待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置若干空格字符；4、在计算机终端输出的结果是：单词，出现的次数，出现的位置所在行的行号，同一行出现两次的只输出一个行号；5、测试数据：将实验的源程序作为测试文件,从中任意选取“单词”作为测试的词集。三、概要设计：采用截取字符串、比较字符串的模式来完成“单词匹配比较”，从而统计出其出现的位置和次数。1、数据结构定义：程序将涉及到如下两个线性表结构的数据类型，用类 C 语言描述如下：（1）定义从文本读取的“单词串”类型：ADT FileString 数据对象：D=Si|Si 标准 c+字符串集合,i=1,2,3,.,n,n

3、0；数据关系：R1=|Si-1,Si D,i=1,2,3,.,n 基本操作：createFileString(FSList&FSL);初始条件：已知一个空的“文本单词串表头”；操作结果：生成一个空的“文本单词串序列”；insertFileString(FSList&FSL,string str,int row);初始条件：FSL 为文本字符串序列的表头 str 为一个标准的 c+字符串，row 代表了字符串出现的行数；操作结果：将 str 插入到文本字符串序列中，不需要排序；若 FSL 为空表头，则创建一个字符串序列；否则插在字符串序列尾部；getFSLength(FSList FSL);初始

4、条件：FSL 为文本字符串序列的表头；操作结果：获取以 FSL 为表头的文本字符串的长度 printFileString(FSList FSL);初始条件：FSL 为文本字符串序列的表头;操作结果：打印以 FSL 为表头的文本字符串中的所有字符串；readFile(FSList&FSL);初始条件：FSL 为文本字符串序列的表头；操作结果：从文件中读取字符串序列，并将其保留在以 FSL 为表头的字符串序列中；clearFileString(FSList&FSL);初始条件：FSL 为文本字符串序列的表头；操作结果：以 FSL 为表头的文本字符串序列被清空；ADT FileString （2）定

5、义从键盘读取的“单词串”类型：ADT KeyString 数据对象：D=Si|Si 标准 c+字符串集合,i=1,2,3,.,n,n 0；数据关系：R1=|Si-1,Si D,i=1,2,3,.,n 基本操作：createKeyString(KSList&KSL);初始条件：已知一个空的“键盘单词串表头”；操作结果：生成一个空的“键盘单词串序列”；insertKeyString(KSList&KSL,string str,int row);初始条件：KSL 为键盘字符串序列的表头 str 为一个标准的 c+字符串，row 代表了字符串出现的行数；操作结果：将 str 插入到键盘字符串序列中，不

6、需要排序；若 KSL 为空表头，则创建一个字符串序列；否则插在字符串序列尾部；getKSLength(KSList KSL);初始条件：KSL 为键盘字符串序列的表头；操作结果：获取以 KSL 为表头的键盘字符串的长度 printKeyString(KSList KSL);初始条件：KSL 为键盘字符串序列的表头;操作结果：打印以 KSL 为表头的键盘字符串中的所有字符串；readKey(KSList&KSL);初始条件：KSL 为文本字符串序列的表头；操作结果：从键盘中读取字符串序列，并将其保留在以 KSL 为表头的字符串序列中；clearKeyString(KSList&KSL);初始条件

7、：KSL 为文本字符串序列的表头；操作结果：以 KSL 为表头的文本字符串序列被清空；ADT KeyString 2、模块设计：1）主程序模块：主函数设计如下 int main()登陆界面和使用提示；构建文本字符串序列；构建键盘字符串序列；构建模式匹配排除符集合；字符串模式匹配，统计单词；结束一轮工作，提示是否继续操作；2）文本字符串模块-构建文本字符串序列；3）键盘字符串模块-实现键盘字符串数据类型；4）模式匹配模块-实现文本字符串和键盘字符串的匹配统计；5）登陆界面模块-提示用户程序使用方法 3、各模块间的调用关系：四、详细设计 1、主程序用到的宏定义：#define MAX_WORD_L

8、ENGTH 1000 /最大字符串长度#define MAX_MODELEXCEPTION_LENGTH 50#define FILE_NAME_LENGTH 100 /文件名长度 2、存储结构设/*从文件读取的字符串集合*/typedef struct FileString string name;/字符串名称 int row;/字符串所在的行 FileString*next;/邻接字符串 FileString,*FSList;/*从键盘读取的字符串集合*/typedef struct KeyString string name;/字符串名称 int*rows;/字符串所在行向量 int c

9、ount;/字符串出现的次数 KeyString*next;/邻接字符串 KeyString,*KSList;/*匹配文本字符串和键盘字符串的模式匹配排除符集合*/typedef char*Model;3、主要算法设计：/*在文件字符串集合中插入新的字符串*/int insertFileString(FSList&FSL,string str,int row)if(!FSL)/如果是空表，则创建集合 createFileString(FSL);FSList sp,tp;sp=tp=FSL;while(sp=sp-next)tp=sp;FSList s=new FileString;/插在既有的

10、集合中 if(!s)coutname=str;s-row=row;s-next=NULL;tp-next=s;/顺序插入 return 1;/*从文件中读取串*/int readFile(FSList&FSL)char urlFILE_NAME_LENGTH;/指向文件路径的 const 指针 coutEnter the file to read:;gets(url);while(url0=0)/保证文件名不为空 coutThe files name can not be null!endl;gets(url);ifstream fs=ifstream(url);/打开文件读取字符串 if(!

11、fs)coutFile reads wrong!n;return 0;int rowLine=1;string s;while(fs.peek()!=EOF)/遇到文件尾符，结束读取 getline(fs,s,n);/依行读取 s insertFileString(FSL,s,rowLine+);/将获取的字符串插入文件字符串集合 return 1;/*统计模式匹配排除字符*/int getModelException(Model&model)model=new charMAX_MODELEXCEPTION_LENGTH;/集合 model 能统计除了默认匹配字符外的所有客户指定的排除字符 c

12、har match;coutmatch;cin.ignore();/避免其他方法的流操作带来负面影响 int i=0;while(match=y)if(!i)coutBegin to receive:;if(cin.peek()=n)if(!i)coutNo character receivedendl;coutEnd receivingendl;break;cin.get(modeli+);/默认的模式匹配排除符 modeli=;modeli+1=,;modeli+2=.;modeli+3=;modeli+4=;modeli+5=;modeli+6=*;modeli+7=#;modeli+8

13、=!;modeli+9=$;modeli+10=%;modeli+11=;modeli+12=&;modeli+13=(;modeli+14=);modeli+15=-;modeli+16=+;modeli+17=_;modeli+18=|;modeli+19=;modeli+20=;modeli+21=;modeli+22=;modeli+23=;modeli+24=:;modeli+25=;modeli+26=;modeli+28=?;modeli+29=/;modeli+30=;modeli+31=t;modeli+32=0;/串尾标志 return 1;/*模式匹配方法*/bool m

14、odelMatch(string s,Model model,int pos)for(int i=strlen(model)-1;i=0;i-)if(spos=modeli)return true;return false;/*查找模式串 T 在主串 S 中出现的次数*/int count(string S,const string T,Model model)int count=0;const char*tc=T.c_str();int i=0;while(i S.length()/定义模式匹配规则-扫描排除字符 if(modelMatch(S,model,i)/遇到模式匹配规则所定义的字符

15、，则忽略读取 i+;continue;else /至此，Si肯定不是模式匹配的排除字符 char*sc=new charMAX_WORD_LENGTH;char*sp=sc;/此处的 while 循环保证了在读取过程中始终保证不遇到模式匹配的排除字符 while(Si!=0&!modelMatch(S,model,i)/未至行尾并且没有遇到/模式匹配规则所定义/的排除字符，则读取 *sp=Si;/读取子串 sp+,i+;*sp=0;/结束子串读取 if(!strcmp(sc,tc)/比较模式串和子串 count+;/相等则增加计数 delete sc;return count;/*定位 KSL

16、 中字符串在 FSL 中的位置*/void locate(FSList&FSL,KSList&KSL,Model model)if(!FSL&!KSL)coutnext)FSList fp=FSL;/sp 是 SL 的副本操作 int*row=new intgetFSLength(FSL)+1;/对于键盘字符串集合中的每个字符串，/row 都会重新申请空间 int*r=row;kp-rows=row;while(fp=fp-next)int c=count(fp-name,kp-name,model);if(c)/kp-name 在 fp-name 出现了，则统计其位置 kp-count+=c

17、;*r=fp-row;r+;*r=0;/堆栈指针指向空间最后单元的下个单元赋 NULL 值 五、调试报告：1、程序在设计过程中主要遇到了如下几个主要的问题：1）从文本中读取文件时的错误。最典型的错误就是当键入的文件名为空时，程序会抛掷异常，且给出严重的警告。该问题的发现，是在我对主程序模块作了添加一个 dowhile（）循环后发现的。经过调试分析，我发现问题在于 readFile(FSList&FSL)模块中的语句：gets（url）；当第一轮循环结束后，欲再继续二轮循环时，会执行指令：cinon；该语句只接受了 on 的赋值，却将 enter 键传给了下一轮的 gets（url）；从而导致错

18、误。我初步的修改是取一个折中的方法，在 readFile（FSList&FSL）模块中添加语句：cin.ignore（）；这样自然会忽略 enter 键的键入，但使得初次循环在输入文件名时，要先回车，后输入文件回车。给用户很不好理解的困惑。于是，我又再次修改：将 cin.ignotrz（）添加到主程序模块中 cinon；语句之后；这样就可以忽略 enter，同时又保证程序模块可以复用，不会产生读取错误，如当前版本所示。2）在统计单词匹配时发生的错误。这里的主要问题是关于模式匹配排除符的把握问题，具体体现在算法 count（string S,const string T,Model model）

19、中。模式匹配排除是我自己在设计程序的过程中提出的一个术语。我起初并没有想过提出这么一个概念，而是想以一个condition 的 bool 变量来表示。后来，我看到若手工指定排除符，则 condition 的内容就是变化的，而且随着定义的排除符的数目的不同，每次对 condition 的修改都会引起程序大规模的改动。特别是在我想到将 condition 区分为用户特别指定和程序初始化时的默认分配情况时，这种由 condition 控制的表示就越来越有问题，这迫使我想到用一种数据结构来封装和模式匹配的相关操作。于是，我提出了模式匹配排除符的概念，并且对其作了相应的处理。其中，仿照 windows

20、程序的消息机制，我也对排除符做了相应的规划，区分为特别的排除符和默认的排除符，具体的实现机制在 getModelException(Model&model)算法中。3)程序设计中对动态内存分配的妥善处理。由于文本字符串序列和键盘字符串序列长度的不确定性，而且又用到了链式存储结构，故对内存分配的处理是很关键的。本程序中 new 操作多达 7 次（在不考虑是否处于循环体中的情况下）。其中算法 locate(FSList&FSL,KSList&KSL,Model model)在动态分配了内存给 rows 变量后，并没有回收内存，这就考虑到跨模块去回收内存的问题。我定义了一个 clear*()函数，用

21、来清理由 FSList 和 KSList 所申请到的内存。clear*（）要求对字符串序列的统计操作后，立即调用它来释放内存，保证不会产生内存泄露。2、程序的时空复杂度分析：设从文本中依行读取的字符串平均长度为 L，其行数为 m，待统计单词平均长度为 S，其个数为 n，则程序的时间消耗主要用于统计定位操作上。对于 modelMatch（）算法，其时间复杂度为：O（L）;对于 count（）算法，其时间复杂度为：O（L*L）,这是因为 count（）中调用了 modelMatch（）；对于 locate（）算法，其时间复杂度为：O（L*L*n*m）；这是因为调用了 count（）。从空间角度来看

22、，辅存空间依然消耗在统计和定位上，还包括在构建单词穿序列上。对于 count（）算法，其空间复杂度为 O（L）;对于 locate（）算法，其空间复杂度为 O（m*n）；这是因为要为 KSL 的 rows 动态分配内存；构建单词串的时间复杂度为 O（m+n）；从时空复杂度来看，这个程序实际上效率其实并不是很高。我统计过，当统计单词数在5 个以上时，就会有延时倾向；当统计的单词数控制在 12 个以上时，查找延时相当明显，约有 0.5 秒的间隔出现。当统计单词数为 15 个时，有 1 秒延迟，当统计超过 17 个单词时 有 1.5-2 秒的延迟。此外，输入的单词的特征也对统计延时有影响，当待统计的

23、单词与文本串中读取的单词长度相当时，统计延时最大；而待统计单词过长或过短，都不会有太大的影响。由此可见，单词长度对统计的影响，无论时时间复杂度还是空间复杂度，都是很突出的。3、程序的扩展方向：程序还不能完全处理汉字串的情况，可以向着类似 offic 和一般的文本编辑工具所提供的全字匹配查找与一般查找方向拓展，真正做到“一查即得，一查即准”。同时，针对统计延时，可以在参考 KMP 算法的同时，加以优化改良。六、经验体会：1)理解分析问题的能力得到提高。设计一个应用程序关键是对要求做最准确的把握，也就是说弄清楚需求分析是很重要的。本程序要求我从文件中读取单词的位置，就是在文件中检索字符串，这样一抽

24、象，问题的脉络就清晰了。接下来，如何读取，读取后如何映射，映射的字符串又怎么和待查字符串关联，这就构成了解决问题的几大关键模块。逐个解析，整个程序的框架就了然于胸了。特别要指出的是，对整个程序的把握，随着编程工作的深入，是越来越深刻，而且新的思路也是层出不穷。2）创新意识和创新能力的提高。本程序的设计，我最开始的想法是按照习题集上所指导的参考 KMP 算法，后来，我放弃了 KMP 算法，原因有两个，其一是 KMP 算法的缺陷，就我的了解来看，getlength 中含有一部分是 length，若用 KMP 算法来检索 length，肯定会认为 getlength 也算作 length 的出处。这

25、显然不合单词的定义要求。其二是我想自己设计一种新的算法来挑战自己，挑战自己的数据结构与算法设计能力。这也是最重要的原因。于是，在这种动力的催动下，我设计出了新的算法，如源程序中的 locate（）和 count（）所示的定位和统计方法。撇开算法的性能来看，本人的创新能力是值得肯定的。而分析到算法的执行性能，本人认为也是可以得到肯定的。通过这个项目的课程设计，我真正提高了创新意识和创新能力。3）对程序设计语言的细微之处又了更深刻的理解。由于字符串的操作是很原始的几于原子的操作，所以更能看清楚平时我们所用的字符串操作函数在底层的实现机制，尽管我的实现和标准字符串的实现原理和实施手段会又不同，但是根

26、本认识也差的不远。同时，对指针也有了新的认识，譬如程序中有一处检验指针操作是否到了结束处，我惯用的就是 while（p）,j 结果陷入了死循环，非得用 while（*p）来检测，这就让我对 new 和指针的本质有了更深刻的认识。再就是有时候 p=NULL 和!p 其实不是一回事。这些平时不在意的问题，这次统统暴露了。七、测试结果：1）测试用例设计：以本程序的源程序 assistant.cpp 模拟英文小说，以其中的某些关键字和常量模拟待查找形容词，如 if else while new for delete include cout 等 2）测试结果如下：图 1 屏幕提示信息 图 2 输入文件和待统计的单词(使用默认模式匹配排除符，不打印文件)图 3 打印单词统计结果 图 4 结束测试