教育培训机构有关的网站,澄迈住宅与建设局网站,青岛餐饮加盟网站建设,wordpress yarpp一、实验目的
1、掌握串的顺序存储结构 2、掌握顺序串的基本操作方法#xff08;插入、删除等#xff09;。 3、掌握串的链式存储结构。 4、掌握链式串的几种基本操作#xff08;插入、删除等#xff09;。 5、掌握Brute-Force算法
二、实验内容
1、编写函数BFIndex(Str…一、实验目的
1、掌握串的顺序存储结构 2、掌握顺序串的基本操作方法插入、删除等。 3、掌握串的链式存储结构。 4、掌握链式串的几种基本操作插入、删除等。 5、掌握Brute-Force算法
二、实验内容
1、编写函数BFIndex(String S, int start, String T)实现Brute-Force算法其中S为主串start为子串在主串中的查找位置T为子串。程序可参考书本例子。鼓励使用KMP算法。
2、设串采用静态数组存储结构编写函数实现串的替换Replace(S,start,T,V),即要求在主串S中从位置start开始查找是否存在子串T。若主串S中存在子串T则用子串V替换子串T且函数返回1若主串S中不存在子串T则函数返回0。并要求设计主函数进行测试。
三、参考代码 SString.h
#include stdio.h
#define MaxSize 100
typedef struct
{char str[MaxSize];int length;
} String;
int Insert(String *S, int pos, String T)
/*在串S的pos位置插入子串T*/
{int i;if(pos 0){printf(参数pos出错);return 0;}else if(S-length T.length MaxSize){printf(数组空间不足无法插入);return 0;}else{for(i S-length-1; i pos; i--)S-str[iT.length] S-str[i]; /*为插入做准备*/for(i 0; i T.length; i)S-str[posi] T.str[i]; /*插入*/S-length T.length; /*产生新的元素个数*/return 1;}
}int Delete(String *S, int pos, int len)
{int i;if(S-length 0){printf(数组中未存放字符无元素可删! \n);return 0;}else if(pos 0 || len 0 || poslen S-length){printf(参数pos和len出错);return 0;}else{for(i poslen; i S-length-1; i)S-str[i-len] S-str[i]; /*依次前移*/S-length - len; /*产生新的长度值*/return 1;}
}主程序
#include bits/stdc.h
#include SString.h
#define Maxlength 100using namespace std;// s 为主串start为开始的下标t为要查找的子串
// 成功匹配则返回第一个出现在主串的子串 的 首字符下标匹配失败返回 -1
int kmp(String s,int start,String t)
{
// TODO 自己完成int res -1;
// 预处理next数组int next[t.length];next[0] 0;for(int i 1,j 0; i t.length; i){while(j 0 t.str[i] ! t.str[j])//不匹配的情况往回跳j next[j-1];if(t.str[i] t.str[j])//匹配的情况jj;next[i] j;//打表}// kmp匹配过程for(int i 0, j 0; i s.length; i){while(j 0 s.str[i] ! t.str[j])j next[j-1];if(s.str[i] t.str[j] )j;if(j t.length)//匹配成功{res i - j 1;break;} }return res;
}// S 为主串start为开始的下标T为要查找的子串
// 成功匹配则返回第一个出现在主串的子串 的 首字符下标匹配失败返回 -1
int BFIndex(String S, int start, String T) {
// TODO 自己完成int res -1;//-1 表示没找到for(int i 0;i S.length; i){bool flag true;int k i;for(int j 0; j T.length; j){if(S.str[k] ! T.str[j]){flag false;break;}}if(flag){res i;break;}}return res;
}//原串s 开始下标start目标串t替换串v
int Replace(String *S, int start, String T, String V)
{
// TODO 自己完成int idx kmp(*S,0,T);if(idx -1)//没找到return 0;
// 找到了替换Delete(S,idx,T.length);Insert(S,idx,V);return 1;
}//原串s 开始下标start目标串t替换串v
int myReplace(String *s, int start, String t, String v)
{
// TODO 自己完成int idx kmp(*s,0,t);if(idx -1)//没找到return 0;
// 找到了替换int len s-length;int tlen t.length;//原本的长度 - 替换串的长度int d t.length-v.length;//d0 后面的串左移 d 位if(d 0)//后串左移for(int i idx tlen; i len; i)s-str[i-d] s-str[i];else if(d 0)//后串右移for(int i len-1; i len - idx tlen -1; i--)s-str[i-d] s-str[i];s-length - d;// 将替换串放入主串中for(int i idx, j 0; i idxv.length; i)s-str[i] v.str[j];return 1;
}int main(void) {String myString1, myString2, myString3;int i, start 0;printf(请输入主串myString1: );scanf(%s, myString1.str );printf(请输入子串myString2: );scanf(%s, myString2.str);printf(请输入子串myString3: );scanf(%s, myString3.str);myString1.length strlen(myString1.str);myString2.length strlen(myString2.str);myString3.length strlen(myString3.str);
// int res BFIndex(myString1,0,myString2);
// int res1 kmp(myString1,0,myString2);
// cout res res1;if (Replace(myString1, start, myString2, myString3) 0)printf(不成功 );elsefor (i 0; i myString1.length ; i)printf(%c, myString1.str[i]);
}
