数据结构课程设计
———串的查找与替换、
目录
（一）设计思路 (1)
（二）问题描述 (1)
（三）内容要求 (1)
（四）设计目的 (1)
（五）设计实现 (5)
（六）设计调试 (10)
（七）设计总结 (15)
（八）参考文献 (15)
(一)设计目的
数据结构课程设计的目的是：通过设计掌握数据结构课程中学到的基本理论和算法并综合运用于解决实际问题中，它是理论与实践相结合的重要过程。
设计要求会如何对实际问题定义相关数据结构，并采用恰当的设计方法和算法解决问题，同时训练学生进行复杂程序设计的技能和培养良好的程序设计习惯。
(二)问题描述：
打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。
(三)内容要求：
1.根据题目要求进行需求分析，分析出该项任务的主要功能和设计重点。
2.根据需求分析的内容划分模块
3.进行程序设计
(四)设计思路
计算机上的非数值处理的对象基本上上字符串数据，字符串一般简称为串。
串（string）是由零个或多个字符组成的有限序列，一般记为s=`a1a2…an`(n 大于零)。
通常称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
当两个串的每个字符都相等时（串值相等），称这两个串是相等的。
在子串的查找定位过程中，分别利用计数指针j和k指示被替换串和替换串中当前正待比较的字符位置。
所用算法的基本思想是：首先利用指针i来完成被替换串和替换串在文本中的遍历，从被替换串和替换串的第一个字符起进行比较，若相等则继续逐个比较后续字符；否则完成一次比较，指针i递增进行下一次的比较。
以此类推，直至匹配成功。
现根据问题描述作如下分析：
首先利用标准库函数fopen()打开一个文件，然后从文件中读取字符串保
存到数组中，完成文件的读入。
其次，根据键盘输入的选择命令（数字1~4）程序调用不同功能模块来完成相应的操作。
本设计所采用的数据结构
char String[65535]; //长度要大于输入文本文件的长度！
char findString[50]; //输入的要查找的字符
char replaceString[50]; //输入的替换后的string
程序中各部分功能函数：
void InitStr()/*从文件初始化数组*/；
void InputReplaceChar()/*输入要替换的字符串*/；
int FindString()/*查找第一个出现要查找字符的下标*/；
void FindStrings()/*查看文章中共有多少个要查找的字符*/；
void Insert(char source[],int index,char target[])/*从指定的下标开始插入target数组中的元素*/；
void Replace()/*将String中要替换的内容替换掉*/；
void Save()/*保存修改后的文章信息*/；
void Menu()/*程序主菜单*/。
程序中用户选择命令（数字1~4）设置：
“1”：文本文件显示；
“2”：子串查找；
“3”：子串替换；
“4”：退出整个程序。
程序设计流程图如图（一）所示：
否
图（一）程序流程图
程序运行后显示主菜单，提示用户根据需要选择不同的命令操作。
程序根据键盘输入的选择命令（数字1~4）调用不同功能模块来完成相应的操作。
如果用户输入的命令是“1”，主函数调用InitStr()函数从文件进行初始化数组，利用标准输入函数将该数组输出到标准输出上；如果用户输入的命令是“2”，主函数调用FindStrings()函数查找匹配的字符串并连同匹配的字符串个数一并输出到标准输出上；如果用户输入的命令是“3”，主函数调用Replace()函数，将String中要替换的内容替换掉；如果用户输入的命令是“4”，程序自动退出。
(五)设计实现
程序中所用数据结构定义：
char String[65535]; //长度要大于输入文本文件的长度！
char findString[50]; //输入的要查找的字符
char replaceString[50]; //输入的替换后的string
Replace();
break;
case 4:// “4”：退出整个程序
Save();
exit(0);
default:
printf("\n输入错误！\n");
printf("按任意键返回.....\n");
getchar();
} } }
(六)设计调试
程序的开发与调试均在Microsoft Visual C++环境下进行。
首先程序运行后显示程序的主菜单，主菜单命令选择设置“1”：文本文件显示；“2”：子串查找；“3”：子串替换；“4”：退出整个程序。
程序根据用户输入的命令（数字1~4）进行相应的操作。
主菜单显示如图（二）：
图（二）程序主菜单
在程序主菜单中任意输入命令进行测试。
输入命令一，如图（三）：
图（三）程序主菜单命令输入一
输入命令一后程序的运行结果：显示文本文件的内容。
如图（四）：
图（四）程序命令一的运行结果
输入命令二后程序的运行结果：选择命令二，进行字符串的查找测试。
从图（六）中可以看到查找后的结果。
图中显示出查找到的字符串getchar的数量为3个，并显示查找成功等信息。
如图（五）、（六）：
图（五）程序命令二字符串查找
图（六）程序命令二字符串查找
输入命令三后程序的运行结果：选择命令三，进行字符串的替换测试。
从图（八）中可以看到替换后的结果。
图中显示出被替换的字符串getchar和替换后的字符串charget，并显示替换成功等信息。
如图（七）、（八）：
图（七）程序命令三字符串替换
图（八）程序命令三字符串替换
再次输入命令一查看命令三是否真正替换成功：从图（九）中可以看到替换后的结果，在图中鼠标箭头所指的方向看以看到原先文本文件（对比前面的程序测试图）中最后一行（当然，先前是查找到三个，这里只以最后一行容易观察到的来进行说明）的getchar()已经被替换成了charget()，说明程序替换成
功，并将替换后的文本文件进行了保存。
如图（九）：
图（九）程序命令三字符串替换的验证
再次输入命令二进行字符串的查找测试，输入的字符串仍为先前查找过的getchar字符串，从图（十）中可以看到程序的运行结果（图中鼠标箭头所指的位置），共查找到0个getchar。
这是因为在上一步的字符串替换测试中已经将字符串getchar替换成了charget并保存了原始文本文件，所以在此处显示共查找到0个getchar。
图（十）程序命令二字符串查找的验证
最后输入命令四，测试程序是否能正常退出。
从图（十一）最后一行可以看到程序已经退出，DOS命令窗口正显示“Press any key to continue”来提示用户如何退出DOS命令窗口。
如图（十一）：
图（十一）程序命令四程序退出命令验证
(七)设计总结
课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节。
数据结构是程序设计的基本算法，经过这次数据结构的课程设计对于实际应用数据结构有很大帮助，尤其是对于串的学习上。
在数据结构课程的学习及其课程设计中要感谢杨老师的悉心教导以及研究生师姐在实验课上的指导。
(八)参考文献：
《数据结构（C语言版）》严蔚敏吴伟民清华大学出版社
《数据结构实践指导教程》阮宏一华中科技大学出版社。