GDPU 数据结构 天码行空6
一、实验目的
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[i+T.length] = S->str[i]; /*为插入做准备*/for(i = 0; i < T.length; i++)S->str[pos+i] = 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 || pos+len > S->length){printf("参数pos和len出错");return 0;}else{for(i = pos+len; 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])//匹配的情况，j++j++;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;//d>0 后面的串左移 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 < idx+v.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]);
}