课程设计串的查找与替换.doc

学号2014-2015学年 第一学期数据结构课程设计报告题目：串的查找与替换专业：计算机科学与技术（对口）班级：姓名：指导教师：成绩：目录1设计目的及要求11.1问题描述11.2内容要求12设计内容12.1现根据问题描述作如下分析22.1.1本设计所采用的数据结构22.1.2程序中各部分功能函数22.1.3程序设计流程图33设计调试44设计总结95参考文献106源程序11数据结构课程设计报告1设计目的及要求数据结构课程设计的目的是：通过设计掌握数据结构课程中学到的基本理论和算法并综合运用于解决实际问题中，它是理论与实践相结合的重要过程。设计要求会如何对实际问题定义相关数据结构，并采用恰当的设计方法和算法解决问题，同时训练学生进行复杂程序设计的技能和培养良好的程序设计习惯。1.1问题描述打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。1.2内容要求（1）根据题目要求进行需求分析，分析出该项任务的主要功能和设计重点。（2）根据需求分析的内容划分模块（3）进行程序设计2设计内容计算机上的非数值处理的对象基本上上字符串数据，字符串一般简称为串。串（string）是由零个或多个字符组成的有限序列，一般记为s=a1a2an(n大于零)。通常称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。当两个串的每个字符都相等时（串值相等），称这两个串是相等的。在子串的查找定位过程中，分别利用计数指针j和k指示被替换串和替换串中当前正待比较的字符位置。所用算法的基本思想是：首先利用指针i来完成被替换串和替换串在文本中的遍历，从被替换串和替换串的第一个字符起进行比较，若相等则继续逐个比较后续字符；否则完成一次比较，指针i递增进行下一次的比较。以此类推，直至匹配成功。2.1现根据问题描述作如下分析首先利用标准库函数fopen()打开一个文件，然后从文件中读取字符串保存到数组中，完成文件的读入。其次，根据键盘输入的选择命令（数字14）程序调用不同功能模块来完成相应的操作。2.1.1本设计所采用的数据结构char String65535;/长度要大于输入文本文件的长度！char findstring50;/输入的要查找的字符char replaceString 50; /输入的替换后的string2.1.2程序中各部分功能函数void InitStr()/*从文件初始化数组*/；void InputReplaceChar ()/*输入要替换的字符串*/；int FindString ()/*查找第一个出现要查找字符的下标*/；void FindStrings ()/*查看文章中共有多少个要查找的字符*/；void Insert (char source,int index,char dest)/*从指定的下标开始插入dest数组中的元素*/；void Replace ()/*将Str中要替换的内容替换掉*/；void Save()/*保存修改后的文章信息*/；void Menu ()/*程序主菜单*/。程序中用户选择命令（数字14）设置：“1”：文本文件显示；“2”：子串查找；“3”：子串替换；“4”：退出整个程序。2.1.3程序设计流程图如图（一）所示图1程序流程图程序运行后显示主菜单，提示用户根据需要选择不同的命令操作。程序根据键盘输入的选择命令（数字14）调用不同功能模块来完成相应的操作。如果用户输入的命令是“1”，主函数调用InitStr()函数从文件进行初始化数组，利用标准输入函数将该数组输出到标准输出上；如果用户输入的命令是“2”，主函数调用FindStrings()函数查找匹配的字符串并连同匹配的字符串个数一并输出到标准输出上；如果用户输入的命令是“3”，主函数调用Replace()函数，将String中要替换的内容替换掉；如果用户输入的命令是“4”，程序自动退出。3设计调试程序的开发与调试均在Microsoft Visual C+环境下进行。首先程序运行后显示程序的主菜单，主菜单命令选择设置“1”：文本文件显示；“2”：子串查找；“3”：子串替换；“4”：退出整个程序。程序根据用户输入的命令（数字14）进行相应的操作。主菜单显示如图（二）：图2程序主菜单在程序主菜单中任意输入命令进行测试。输入命令一，如图（三）：图3程序主菜单 命令输入一输入命令一后程序的运行结果：显示文本文件的内容。如图（四）：图4程序命令一的运行结果输入命令二后程序的运行结果：选择命令二，进行字符串的查找测试。从图（六）中可以看到查找后的结果。图中显示出查找到的字符串getchar的数量为3个，并显示查找成功等信息。如图（五）、（六）：图5程序命令二 字符串查找图6程序命令二 字符串查找输入命令三后程序的运行结果：选择命令三，进行字符串的替换测试。从图（八）中可以看到替换后的结果。图中显示出被替换的字符串getchar和替换后的字符串charget，并显示替换成功等信息。如图（七）、（八）：图7程序命令三 字符串替换图8程序命令三 字符串替换再次输入命令一查看命令三是否真正替换成功：从图（九）中可以看到替换后的结果，在图中鼠标箭头所指的方向看以看到原先文本文件（对比前面的程序测试图）中最后一行（当然，先前是查找到三个，这里只以最后一行容易观察到的来进行说明）的getchar()已经被替换成了charget()，说明程序替换成功，并将替换后的文本文件进行了保存。如图（九）：图9程序命令三 字符串替换的验证再次输入命令二进行字符串的查找测试，输入的字符串仍为先前查找过的getchar字符串，从图（十）中可以看到程序的运行结果（图中鼠标箭头所指的位置），共查找到0个getchar。这是因为在上一步的字符串替换测试中已经将字符串getchar替换成了charget并保存了原始文本文件，所以在此处显示共查找到0个getchar。图10程序命令二 字符串查找的验证最后输入命令四，测试程序是否能正常退出。从图（十一）最后一行可以看到程序已经退出，DOS命令窗口正显示“Press any key to continue”来提示用户如何退出DOS命令窗口。如图（十一）：图11程序命令四 程序退出命令验证4设计总结课程设计是培养学生综合运用所学知识 ,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节。数据结构是程序设计的基本算法，经过这次数据结构的课程设计对于实际应用数据结构有很大帮助，尤其是对于串的学习上。在数据结构课程的学习及其课程设计中要感谢杨老师的悉心教导以及研究生师姐在实验课上的指导。5参考文献1王昆仑,李红等编著. 数据结构与算法. 北京:中国铁道出版社,2007.2苏仕华等编著. 数据结构课程设计. 北京：机械工业出版社 ,2005.3苏仕华编著. 数据结构与算法解析. 合肥:中国科学技术大学出版社,2004.4郭嵩山等著. 国际大学生程序设计竞赛例题解. 北京:电子工业出版社,2008.5刘大有,唐海鹰等编著. 数据结构. 北京:高等教育出版社,2001.6徐孝凯编著.数据结构实用教程. 北京: 清华大学出版社,1999.7严蔚敏,陈文博编著. 数据结构及算法教程. 北京: 清华大学出版社,2001.8刘振安,刘燕君等编著. C 程序设计课程设计. 北京: 机械出版社,2004.9胡学钢. 数据结构与算法设计指导. 北京: 清华大学出版社, 1999186源程序程序中所用数据结构定义：#include#include#includechar String65535;char findString50;char replaceString 15;void InitStr()/*从文件初始化数组*/int i=0;fp=fopen(c:text.txt,rt+);/打开文件，文件在当前目录下 r-read onlywhile(!feof(fp)Stringi=fgetc(fp);/int fgetc( FILE *stream );i+;/Read a character from a stream.String-i=0;/添加结束标志 fclose(fp);void InputReplaceChar() /*输入要替换的字符串*/printf(输入被替换的字符串：);scanf(%s,findString);printf(输入要替换的字符串：);scanf(%s,replaceString);int FindString()/*查找第一个出现要查找字符的下标*/int i,j,k;for(i=0;istrlen(String);i+) j=i;k=0;while(Stringj=findStringk) & (findStringk!=0) & (Stringj!=0) /当前比较的两个字符相等，并且主/模式串都为结束，继续下一个的比较j+;k+;if(findStringk=0) return i;/返回的是最后的匹配位置return -1;void FindStrings()/*查看文章中共有多少个要查找的字符*/int i,j,k,all=0;printf(输入要查找的字符串：);scanf(%s,findString);for(i=0; i = index)/index 为 pos，pos是找到的位置sourcei=sourcem;i-;m-;i=index; /index 为 pos，pos是找到的位置m=0;while(mj)sourcei=targetm;i+;m+;void Replace()/*将String中要替换的内容替换掉*/int pos,b=0;InputReplaceChar();dopos=FindString();/FindString()-return i;返回的是最后的匹配位置b=pos;/FindString()未找到时返回的是-1，故判断b=-1if(b=-1) printf(查找内容不存在！n);return;else while(Stringb+strlen(findString)!=0)Stringb=Stringb+strlen(findString); b+;Stringb=0;/字符串添加结束符Insert(String,pos,replaceString);pos=FindString();while(pos!=-1); printf(替换成功！n); printf(n按任意键返回.n); getchar();void Save() /*保存修改后的文章信息*/int i=0;FILE *fp;fp=fopen(test.txt,w);while(i strlen(String)fputc(Stringi,fp);/int fputc( int c, FILE *stream );i+;/Writes a character to a stream .void Menu()/程序主菜单实现printf(n);printf(程序主菜单n);printf(n);printf(1 文本文件显示n);printf(2 子串查找n);printf(3 子串替换n);printf(4 退出整个程序n);printf(回车键返回菜单n);printf(n);printf(请选择：（14）:);void main()/程序主函数部分，完成各功能函数的调用，程序的入口char menuNum;InitStr();while(1)Menu();scanf(%d,&menuNum);switch(m