串的查找和替换.docx

串的查找和替换.docx

《串的查找和替换.docx》由会员分享，可在线阅读，更多相关《串的查找和替换.docx（16页珍藏版）》请在冰点文库上搜索。

串的查找和替换

软件综合课程设计

串的查找和替换

神秘国度的爱情故事

二〇一四年六月

串的查找和替换

1．问题陈述

本课程设计主要解决的在一篇英语文章中，在文章中找出所指定的单词，然后对所指定的单词进行替换，替换为另一个单词，再存盘的课程设计。

先建立一个文件，然后从文件中读取字符串保存到数组中。

从键盘输入被替换的单词，然后删除这个单词。

从键盘中输入替换的单词，把它插入到被删除的单词的位置。

然后把该字符串再写入到文件中。

程序通过调试运行，初步实现了设计目标。

2．需求分析

1.问题分析和任务的定义

对问题的描述应避免具体的算法和涉及的数据结构，它是对要完成的任务明确的回答，强调是做什么，而不是怎么做。

2.详细的设计及编码

算法的描述与代码的编写。

3.上机调试

源程序的输入及代码的调试。

3．概要设计

先建立一个文件，然后从文件中读取字符串保存到数组中。

从键盘输入被替换的单词，然后删除这个单词。

从键盘中输入替换的单词，把它插入到被删除的单词的位置。

然后把该字符串再写入到文件中。

计算机上的非数值处理的对象基本上上字符串数据，字符串一般简称为串。

串（string）是由零个或多个字符组成的有限序列，一般记为s=`a1a2…an`（n大于零）。

通常称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

当两个串的每个字符都相等时（串值相等），称这两个串是相等的。

[3]

在子串的查找定位过程中，分别利用计数指针j和k指示被替换串和替换串中当前正待比较的字符位置。

所用算法的基本思想是：

首先利用指针i来完成被替换串和替换串在文本中的遍历，从被替换串和替换串的第一个字符起进行比较，若相等则继续逐个比较后续字符；否则完成一次比较，指针i递增进行下一次的比较。

以此类推，直至匹配成功[4]。

4．详细设计

本设计所采用的数据结构

charString[65535];//长度要大于输入文本文件的长度！

charfindString[50];//输入的要查找的字符

charreplaceString[50];//输入的替换后的string.

程序中各部分功能函数：

voidInitStr（）/*从文件初始化数组*/；

voidInputReplaceChar（）/*输入要替换的字符串*/；

intFindString（）/*查找第一个出现要查找字符的下标*/；

voidFindStrings（）/*查看文章中共有多少个要查找的字符*/；

voidInsert（charsource[],intindex,chartarget[]）/*从指定的下标开始插入target数组

中的元素*/；

voidReplace（）/*将String中要替换的内容替换掉*/；

voidSave（）/*保存修改后的文章信息*/；

voidMenu（）/*程序主菜单*/。

课程设计主要流程

首先利用标准库函数fopen（）打开一个文件，然后从文件中读取字符串保存到数组中，完成文件的读入。

其次，根据键盘输入的选择命令程序调用不同功能模块来完成相应的操作。

[5]

程序中用户选择命令设置：

“1”：

子串查找；

“2”：

子串替换；

“3”：

退出整个程序。

功能流程图：

5．程序代码

#include

#include

#defineSIZE20/*查找单词字符和输入替换单词少于20*/

#defineMAXLEN10000/*文章字符不大于10000*/

voidmain（void）

{

inti,j;

intflag;/*用于标记匹配单词*/

intcountFlag;/*用于检查匹配计数*/

intcountOne=0;/*记录未改文章字符个数*/

intcountTwo=0;/*记录改后文章字符个数*/

charkeyWords[SIZE];/*查找单词*/

charcopyWords[SIZE];/*替换单词*/

charstrOne[MAXLEN];/*将未改文章的所有字符储存在里面*/

charstrTwo[MAXLEN];/*将改后文章的所有字符储存在里面*/

FILE*fp;

printf（"请输入要查找的单词:

"）;

gets（keyWords）;

printf（"请输入要替换的单词:

"）;

gets（copyWords）;

if（NULL==（fp=fopen（"123.txt","r"）））/*读文件*/

{

printf（"文件打开失败!

\n"）;

exit

（1）;

}

while（!

feof（fp））/*读文件*/

{

strOne[countOne++]=fgetc（fp）;

}

countOne--;/*减去最后一个文件结束字符*/

for（i=0;i

{

if（keyWords[0]==strOne[i]）/*判断查找单词第一个字符是否匹配*/

{

if（（''==strOne[i-1]）||（'\n'==strOne[i-1]）||（0==i））/*1.检查单词前的一个字符*/

{

flag=1;

countFlag=i+1;

for（j=1;keyWords[j]!

='\0';j++）

{

if（keyWords[j]!

=strOne[countFlag++]）/*是否匹配*/

{

flag=0;

break;

}

}

if（（''==strOne[countFlag]）||

（'\n'==strOne[countFlag]）||

（EOF==strOne[countFlag]））/*2.检查单词后的一个字符*/

{

if（1==flag）/*若匹配,则进行拷贝*/

{

i=countFlag-1;

for（j=0;copyWords[j]!

='\0';j++）

{

strTwo[countTwo++]=copyWords[j];

}

}

}

else/*另外*/

{

strTwo[countTwo++]=strOne[i];

}

}

else/*另外*/

{

strTwo[countTwo++]=strOne[i];

}

}

else/*另外*/

{

strTwo[countTwo++]=strOne[i];

}

}

fclose（fp）;

if（NULL==（fp=fopen（"123.txt","w"）））/*写入文件*/

{

printf（"文件打开失败!

\n"）;

exit

（1）;

}

for（i=0;i

{

fputc（strTwo[i],fp）;

}

fclose（fp）;

}

6．运行结果与测试

运行测试进入界面：

显示查找内容界面

显示替换内容界面：

退出界面

按任意键即可退出

7．设计体会与总结

两周的课程设计结束了，在这次的课程设计中不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情。

在课程设计过程中，我一开始对自己如何完成一个独立的数据结构茫然不知所措，通过向老师和同学们请教，我逐步的了解了如何完成这次课程设计，并且提高了我对串的操作的熟练程度。

课程设计是我们专业课程知识综合应用的实践训练，是我们迈向社会，从事职业工作前一个必不少的过程．”千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义．我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础．

在这次数据结构课程设计过程中，体现出自己单独完成问题的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。

在此我十分感谢我的老师，在他们的指导下，我克服了在课程设计过程中许多的难题与不足，使我能够熟练的掌握了关于串的有关操作。

由于我的设计能力有限，在设计过程中难免出现错误，恳请老师们多多指教,我十分乐意接受老师的批评与指正，我将万分感谢。

神秘国度的爱情故事

1．问题陈述

输入要求：

输入由若干组测试数据组成。

每组数据的第1行包含一正整数N（1≤N≤50000），代表神秘国度中小村的个数，每个小村即从0到N-1编号。

接下来有N-1行输入，每行包含一条双向道路的两端小村的编号，中间用空格分开。

之后一行包含一正整数M（1≤M≤500000），代表着该组测试问题的个数。

接下来M行，每行给出A,B,C三个小村的编号，中间用空格分开。

当N为0时，表示全部测试结束，不要对该数据做任何处理。

输出要求：

对每一组测试给定的A,B,C，在一行里输出答案，即：

如果C在A和B之间的路径上，输出Yes,否则输出No。

2．程序代码

//神秘国度的爱情故事代码

#include

usingnamespacestd;

#defineMAXNODE100//图中顶点的最大个数

typedefcharElemType;//顶点的数据类型

structNode//定义边的表结点

{intadjvex;//邻接点在顶点向量中的下标

structNode*next;//指向下一邻接点的指针

};

typedefstruct//定义顶点结点

{ElemTypevertex;//顶点信息

Node*firstarc;//指向第一邻接点的指针

}VerNode;

typedefstruct

{VerNodevertices[MAXNODE];//定义邻接表

intvexnum,arcnum;//顶点和边的数目

}AlGraph;

AlGraphcreatgraph（AlGraphG）{//建立图函数

inti,j,k;//i，j，k用于边和顶点的建立

Node*p;//用于新生成顶点的指针

cout<<"输入小村的个数：

"<

cin>>G.vexnum;

G.arcnum=G.vexnum-1;

for（i=0;i

{

G.vertices[i].firstarc=NULL;

}

cout<<"输入道路两端小村的编号（"<

"<

for（k=0;k

{

cin>>i>>j;

p=（Node*）malloc（sizeof（Node））;

p->adjvex=j;

p->next=G.vertices[i].firstarc;

G.vertices[i].firstarc=p;//用头插法

p=（Node*）malloc（sizeof（Node））;

p->adjvex=i;

p->next=G.vertices[j].firstarc;

G.vertices[j].firstarc=p;

}

returnG;

}

intvisited[MAXNODE];//用于深度遍历记住遍历过的顶点

AlGraphG;//全局图

intw;//记住C【j】点

intcount=0;//计数器，深度优先后，保存是否在AB间

intcount1=0;//辅助计数器，判断ABC是否重复

voidDFS（AlGraphG,intA,intB,intC）{//G为邻接表存储的图，从第v个顶点出发递归的深度优先遍历函数

if（A==C||B==C）count1++;//如果遍历到A或B点辅助计数器加一

visited[C]=1;Node*p;

p=（Node*）malloc（sizeof（Node））;//为p申请空间

p=G.vertices[C].firstarc;//指向c的第1邻接点的指针

while（p!

=NULL）

{

if（!

visited[p->adjvex]）

{DFS（G,A,B,p->adjvex）;}//访问p的顶点向量中的下标

if（p->adjvex==w&&count1==1）

count=1;//如果辅助计数器为一且遍历返回到C时计数器为一

if（count==1）break;

p=p->next;//遍历到已被遍历的顶点从此顶点的下一邻接点

}

}

voidIf（AlGraphG）{//判断C是否在A和B之间，原理是判断是否在一次探测，还是产生回溯

intd;//d为判断的次数

cout<<"输入测试的次数：

"<

cin>>d;

intA[10],B[10],C[10];//记住每次用于测试A、B、C的值

cout<<"输入A,B,C三个小村的编号（"<

"<

for（inti=0;i

{cin>>A[i]>>B[i]>>C[i];}

cout<<"显示测试结果：

"<

for（intj=0;j

{

w=C[j];

DFS（G,A[j],B[j],C[j]）;

if（count==1）

cout<<"YES恭喜你将找到命中的恋人"<

if（count==0）cout<<"NO你将与她错过"<

for（intk=0;k<=G.vexnum;k++）

visited[k]=0;

count=0;

count1=0;//计数器清0

}

}

voidmain（）{

cout<<"《故事背景介绍》\n"<

cout<<"/*欢迎来到神秘国度，在神秘国度里你将找到命中的恋人*/\n"<

cout<<"。

。

。

请按照提示信息寻找爱情。

。

。

\n"<

G=creatgraph（G）;//调用图建立函数

If（G）;//调用判断函数

}

3．运行结果

4．设计体会与总结

通过这次课程设计，我认识到了我在程序设计方面的严重不足，以及基础知识掌握的不牢固。

这样一种更贴切实际的课程设计，大大的提高了我的学习效率，让我对学过的知识有了更进一步的了解，一些理解的不够深刻的问题，也得到了更深的理解。

在编写一个程序之前，自己能够综合考虑各种因素，选取我们需要的数据结构，而不是盲目的下手，在编写每一个函数之前，仔细斟酌比对，挑选出最适合当前状况的算法。

这样，即使在完整的程序还没有写出来之前，我们心中已经有了明确的原图了，这样在无形中就提高了我们编写的程序的质量。

另外，还体会到深刻理解数据结构的重要性。

只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。