数据结构课程设计报告文本编辑和串查找统计

《数据结构课程设计报告文本编辑和串查找统计》由会员分享，可在线阅读，更多相关《数据结构课程设计报告文本编辑和串查找统计（9页珍藏版）》请在金锄头文库上搜索。

1、0数据结构与算法设计数据结构与算法设计 课程设计报告课程设计报告题目：文本编辑和串查找统计题目：文本编辑和串查找统计学生姓名：学生姓名： 学学 号：号： 班班 级：级： 指导教师：指导教师： 2011 年年 12 月月 29 日日1目录目录1.需求分析说明需求分析说明.22. 总体设计总体设计 33.详细设计详细设计 44.实现部分实现部分 5-75.总结总结 81.需求分析说明需求分析说明21.1题目与要求题目与要求文本编辑和串查找统计文本编辑和串查找统计任务：输入一页文字，程序可以统计出文字、数字、空格和其它标点符号的个数。静态存储一页文章，每行最多不超过 80 个字符，共 N 行；功能要

2、求：1） 、分别统计出其中英文字母数、空格数、标点符号及整篇文章总字数；2） 、统计某一字符串在文章中出现的次数，并输出该次数；3） 、删除某一子串，并将后面的字符前移。要求用菜单选择操作，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分 5 行输出“全部字母数“、“数字个数“、“空格个数“、 “标点符号个数”“文章总字数“（3）输出删除某一字符串后的文章；1.2 本程序涉及的知识点本程序涉及的知识点链串的插入，删除，查找，模式匹配（knp 算法）及文件的写入与写出，用 switch,c

3、ase 语句进行菜单的选择，用 while 语句进行循环，用 if 语句进行条件的判断等等。 2 总体设计总体设计32.1 基本思路基本思路本文采用链式存储字符串，链串的插入采用后插法，以*为字符串结束的标志。在插入字符串的同时用文件存储字符串。删除算法的基本思路：输入要删除的字符串，同样以#结束，然后在文中查找该字符串，若找到了则把它删除，同时长度要减少；否则，没找到不能删除。查找算法与删除算法类似；但也有不同之处，不同在于：这里是要查找某字符串在文中出现的次数，因此，当找到该字符串后还要继续往后查找，并将次数加 1；直到文章的末尾才结束查找。用菜单做选择，用 switch，case 语句进

4、行选择判断，并用类的对象调用类的成员函数以实现特定的功能。2.2 功能设计功能设计根据提示选择相应功能y n选择操作退出调用相应函数是否继续？3.详细设计详细设计ca 类中有 data 和 next 分别表示输入的数据和指向下一个地址；另外还包含 5 个子函数，分别是 1，void shuru()函数，用尾插法建立链串，并将字符串存入文件，遇到*时结束；2，void chazhao()函数，4用于查找某个字符，当遇到的字符大于等于 48 并且小于等于 57 时，数字个数加 1，当遇到的字符为标点符号时，相应的标点符号数加1，并输出；判断完后指针后移。3，void shanchu()为删除字符串

5、的函数，输入一个字符，若在文中找到了一个字符与要删除的第一个字符相同，则指针分别往后移，若文中的下一个字符与第二个字符不相同，则继续找文中的下一个字符与要删除的字符从第一个字符开始从新匹配，直到要删除的字符都匹配完；找到了要删除的字符串在文中的位置后，将文中与这串字符匹配的第一个字符开始到最后一个匹配的这段字符删除；若没有找到该字符串则不能删除。4，void print1(link )函数，输出要删除的字符串。 5，void print2()函数用于查找字符串在文中出现的次数；设置一个整型变量 num，用于统计出现次数，其初始值为 0。同样采用模式匹配的算法，但不同的是，找到第一次在文中出现的

6、位置后 num+1，并且还要继续找文中的下一个，找到了又要 num+1，直到文章的末尾，然后输出num 值。 部分函数模块流程图：void Chazhao(ca *L)ca *H = L;char s80, *q;ca *p;couts;While (P!=NULL)ca *next; ;void Shuru(ca *L) coutdata = getchar() != *) L-next = new ca;L = L-next;L-next = NULL; void Chazhao(ca *L) if (*q = 0) n+;L = L-next;Else6int n = 0;char s8

7、0, *q;ca *p;couts;while(L-next) for (p = L, q = s; *q != 0 p = p-next, q+)if (p-data != *q) break;if (*q = 0) n+;L = L-next;couts;if (H-data = *s) for (p = H-next, q = s+1; *q != 0 p = p-next, q+)if (p-data != *q) break;if (*q = 0) H = p;while(L-next) for (p = L-next, q = s; *q != 0 p = p-next, q+)i

8、f (p-data != *q) break;if (*q = 0) L-next = p;else L = L-next;return H; void print1(ca *L) while(L-next) coutdata;7L = L-next;coutnext; L = L-next, n+)if(isalpha(L-data) p1+;else if(isdigit(L-data) p2+;else if(L-data = ) p3+;else if(L-data = n) n-;coutdata;switch(data) case 1:print2(L, p1, p2, p3, n

9、);break;case 2:Chazhao(L);break;case 3:Shanchu(L);case 4:print1(L);while(data); 85.总结总结在做课程设计之前，我对文件操作这个知识点一直不是很理解，每当遇到要存储数据之类的问题时就不知所措。于是仔细看书，网上找资料理解了文件操作的基本操作。但在我完成文件操作后，另一个问题又出现了空格与换行符的存储问题。因为我用的是字符的链式存储，每当我输入空格和换行符时，在输出结果中却没有显示空格和换行符，最后在通过网上找资料解决。解决成了输入与输出问题后，还有一个查找问题。课本上介绍了一个模式匹配的knp 算法，我在统计某一字符串在文中出现的次数及删除某一字符串时用到了这一算法，对于这一算法，我没有完全照搬，在统计字符串出现的次数时，我增加了一个 num 作为统计数，并在找到这一字符串后继续往后找，而不是停止，时间复杂度为 O(1)。另外，在删除字符串时，我在字符串相匹配的前一个字符和最后一个字符分别设定了一个指针，删除的时候直接把前一个指针的 next 指向最后一个指针的 next，时间复杂度为 O(1)。做完这个课程设计后，我对文件操作，字符串的存储及链表有了进一步的理解，只要自己愿意动手去做，或多或少都会有一点收获的。