串查找和替换数据结构课程设计报告.doc

长沙理工大学数据结构课程设计报告 黄博 学 院 计算机与通信工程 专 业 计算机科学与技术 班 级 计算机0903班 学 号 200986250311 学生姓名 黄博 指导教师 陈倩诒 课程成绩 完成日期 2011年7月3日课程设计成绩评定学 院 城南学院 专 业 计算机科技与技术 班 级 计算机科学与技术 学 号 200986250311 学生姓名 黄 博 指导教师 陈倩诒 完成日期 2011年7月3日 指导教师对学生在课程设计中的评价评分项目优良中及格不及格课程设计中的创造性成果学生掌握课程内容的程度课程设计完成情况课程设计动手能力文字表达学习态度规范要求课程设计论文的质量指导教师对课程设计的评定意见综合成绩 指导教师签字 2011年7月10日课程设计任务书城南学院 计算机科学与技术专业 课程名称数据结构课程设计时间20102011学年第2学期1820周学生姓名黄博指导老师陈倩诒题 目串的查找和替换主要内容：问题描述：打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘要求：（1）通过实际项目的分析、设计、编码、测试等工作，掌握用C语言来开发和维护软件。（2）按要求编写课程设计报告书，能正确编写分析、设计、编码、测试等技术文档和用户使用手册。应当提交的文件：（1）课程设计学年论文。（2）课程设计附件（主要是源程序）。用C+语言解决串的查找和替换问题学生姓名：黄博 指导老师：陈倩诒摘 要 本课程设计主要解决的在一篇英语文章中，在文章中找出所指定的单词，然后对所指定的单词进行替换，替换为另一个单词，再存盘的课程设计。先建立一个文件，然后从文件中读取字符串保存到数组中。从键盘输入被替换的单词，然后删除这个单词。从键盘中输入替换的单词，把它插入到被删除的单词的位置。然后把该字符串再写入到文件中。程序通过调试运行，初步实现了设计目标。关键词 程序设计；C+；替换；字符串目 录1. 引言12. 课程设计目的和要求2 2.1 课程设计目的22.2 课程设计要求23. 课程设计分析33.1课程设计思路33.2课程设计要求函数分析33.3课程设计主要流程44. 课程设计调试65. 课程设计总结9 参考文献10附录11黄博 串的查找和替换 1 引 言 数据结构是一门理论性强，思维抽象，难度较大的一门课程。是基础课专业课之间的桥梁。该课程的先行课时计算机基础，程序设计语言、离散数学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。通过本门课程的学习，我们应该透彻的理解各种数据的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后学习和工作有着重要的影响。1 数据结构是计算机科学与技术的一门核心专业基础课程，在该专业课程中有着承上启下的作用，学习好数据结构对于提高理论认知水平和实践操作能力有重要的作用，学习数据结构的最终目的是为了获得解决求解问题的能力。对于现实世界的问题，应该从中抽象出一个适当的数学模型，该数学模型在计算机的用数构表示出来，然后在设计一个求数学模型的的算法，再进行编程调试，最后获得问题的解答。 数据课程设计着眼培养我们实践能力，加强编程能力的培养。 第1页2 课程设计目的和要求2.1 课程设计目的 通过课程设计的题目练习，强化对所学知识的掌握及对问题分析和任务定义的理解，对题目做了相应的逻辑分析和数据结构的选择通过对任务的分析，为操作对象定义相应的数据结构，一过程化程序设计的思想原则划分各个模块，定义数据的抽象数据类型。分模块对题目进行设计，强化对C+语言的掌握和对数据结构选择及掌握。通过程序的编译掌握对程序的调试及思想，并且学习一些编程的技巧。养成良好的编程习惯。2以及让学生对书本的上的知识进行实践。算法和数据结构是计算机科学与技术专业综合的专业基础课。它不仅是计算机学科的核心课程，而且成为其他理工专业的热门选修课。它又是操作系统、编译原理、数据库原理、算法分析、人工智能、图像处理等专业课程的前导课。具有承上启下的作用。数据结构的研究不仅设计到计算机硬件的研究方面，而且与计算机软件研究有着密切的关系。计算机科学各领域都要用到数据构，该课程的目的就是介绍一些常用的数据结构，阐明数据结构的内在逻辑关系，讨论它们计算机内的储存表示，并结合各种典型它们在进行各种运算时的动态性质和实际的执行算法。2.2 课程设计要求1.问题分析和任务的定义对问题的描述应避免具体的算法和涉及的数据结构，它是对要完成的任务明确的回答，强调是做什么，而不是怎么做。2.详细的设计及编码算法的描述与代码的编写。3.上机调试源程序的输入及代码的调试。 第2页3 课程设计分析3.1 课程设计思路先建立一个文件，然后从文件中读取字符串保存到数组中。从键盘输入被替换的单词，然后删除这个单词。从键盘中输入替换的单词，把它插入到被删除的单词的位置。然后把该字符串再写入到文件中。计算机上的非数值处理的对象基本上上字符串数据，字符串一般简称为串。串（string）是由零个或多个字符组成的有限序列，一般记为s=a1a2an(n大于零)。通常称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。当两个串的每个字符都相等时（串值相等），称这两个串是相等的。3在子串的查找定位过程中，分别利用计数指针j和k指示被替换串和替换串中当前正待比较的字符位置。所用算法的基本思想是：首先利用指针i来完成被替换串和替换串在文本中的遍历，从被替换串和替换串的第一个字符起进行比较，若相等则继续逐个比较后续字符；否则完成一次比较，指针i递增进行下一次的比较。以此类推，直至匹配成功4。3.2 课程设计主要函数分析本设计所采用的数据结构char String65535;/长度要大于输入文本文件的长度！char findString50;/输入的要查找的字符char replaceString50; /输入的替换后的string.程序中各部分功能函数：void InitStr()/*从文件初始化数组*/；void InputReplaceChar()/*输入要替换的字符串*/；int FindString()/*查找第一个出现要查找字符的下标*/；void FindStrings()/*查看文章中共有多少个要查找的字符*/；void Insert(char source,int index,char target)/*从指定的下标开始插入target数组第3页中的元素*/；void Replace()/*将String中要替换的内容替换掉*/；void Save()/*保存修改后的文章信息*/；void Menu()/*程序主菜单*/。3.3 课程设计主要流程首先利用标准库函数fopen()打开一个文件，然后从文件中读取字符串保存到数组中，完成文件的读入。其次，根据键盘输入的选择命令（数字14）程序调用不同功能模块来完成相应的操作。 5程序中用户选择命令（数字14）设置：“1”：文本文件显示；“2”：子串查找；“3”：子串替换；“4”：退出整个程序。程序设计流程图如图3.1所示： 图3.1 设计流程图第4页程序运行后显示主菜单，提示用户根据需要选择不同的命令操作。程序根据键盘输入的选择命令（数字14）调用不同功能模块来完成相应的操作。如果用户输入的命令是“1”，主函数调用InitStr()函数从文件进行初始化数组，利用标准输入函数将该数组输出到标准输出上；如果用户输入的命令是“2”，主函数调用FindStrings()函数查找匹配的字符串并连同匹配的字符串个数一并输出到标准输出上；如果用户输入的命令是“3”，主函数调用Replace()函数，将String中要替换的内容替换掉；如果用户输入的命令是“4”，程序自动退出。 第5页4课程设计调试程序的开发与调试均在Microsoft Visual C+环境下进行。首先程序运行后显示程序的主菜单，主菜单命令选择设置“1”：文本文件显示；“2”：子串查找；“3”：子串替换；“4”：退出整个程序。程序根据用户输入的命令（数字14）进行相应的操作 输入命令一后程序的运行结果：显示文本文件的内容。如图4.1 图4.1程序命令一的运行结果输入命令二后程序的运行结果：选择命令二，进行字符串的查找测试。从图4.3中可以看到查找后的结果。图中显示出查找到的字符串getchar的数量为3个，并显示查找成功等信息。如 图4.2 图4.3第6页 图4.2程序命令二 字符串查找 图4.3程序命令二 字符串查找再次输入命令三后程序的运行结果：选择命令三，进行字符串的替换测试。从图4.4中可以看到替换后的结果。图中显示出被替换的字符串getchar和替换后的字符串charget，并显示替换成功等信息 第7页 图4.4程序命令三 字符串替换 图4.5程序命令三 字符串替换再次输入命令一查看命令三是否真正替换成功：从图4.5中可以看到替换后的结果，鼠标箭头所指的方向看以看到原先文本文件（对比前面的程序测试图）中最后一行（当然，先前是查找到三个，这里只以最后一行容易观察到的来进行说明）的getchar()已经被替换成了charget()，说明程序替换成功，并将替换后的文本文件进行了保存。第8页5课程设计总结课程设计是培养学生综合运用所学知识 ,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节。数据结构是程序设计的基本算法，经过这次数据结构的课程设计对于实际应用数据结构有很大帮助，尤其是对于串的学习上。在数据结构课程的学习及其课程设计中要感谢陈老师的悉心教导，为我细心的指出错误。第9页参考文献1谭浩强.C+程序设计.北京：清华大学出版社.20042王晓东.计算机算法与分析.北京:电子工业出版社.20063徐孝凯. C+语言基础教程. 北京:清华大学出版社.200249.Esakov J, Weiss T. Data Structures:An Advanced Approach Using C.Prentice-Hall,Inc.,1989年5 晋良颍.数据结构.人民邮电出版社.2002第10页附录：源程序：#include#include#includeFILE* fp;char String65535;/长度要大于输入文本文件的长度！char findString50;/输入的要查找的字符char replaceString50; /输入的替换后的string void InitStr()/*从文件初始化数组*/int i=0;fp=fopen(test.txt,r);/打开文件，文件在当前目录下 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) /当前比较的两个字符相等，并且主/模式串都为结束，继续下一个的比较第11 页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-; 第12页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; 第13页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(-请选择：（1-4）-:);void main()/程序主函数部分，完成各功能函数的调用，程序的入口char menuNum;InitStr();while(1)Menu();scanf(%d,&menuNum);switch(menuNum)case 1: /1：文本文件显示； printf(%sn,String); getchar(); break;case 2:/ 2：子串查找 FindStrings(); break;case 3:/ 3：子串替换 Replace(); break;case 4:/ 4：退出整个程序 第14页Save(); exit(0);default: printf(n输入错误！n); printf(按任意键返回.n); getchar(); 第15页