一、顺序串的基本操作：

假定下面所有的串均为顺序串，参数ch、ch1和ch2均是字符型，编写算法依次实现下列操作。

① 将串r中所有值为ch1的字符换成ch2的字符。

② 将串r中所有字符按照相反的次序仍存放在r中。

③ 从串r中删除其值等于ch的所有字符。

④ 从串r1中第index个字符起求出首次与串r2相同的子串的起始位置。
输入格式:

第一行：r

第二行：r1

第三行：r2

第四行：ch ch1 ch2

第五行：index

输出格式:

第一行：操作①结果

第二行：操作②结果

第三行：操作③结果

第四行：操作④结果(不存在输出-1)

1.操作1：替换字符

// 1. 字符替换：将S中所有ch1替换为ch2
void StrReplaceCh(SString *S, char ch1, char ch2) {
    for (int i = 0; i < S->len; i++) {
        if (S->ch[i] == ch1) {
            S->ch[i] = ch2;
        }
    }
}

2.操作2（双指针）：逆置字符串
 

// 2. 串逆置：将S中字符按相反次序存放
void StrRreverse(SString *S) {
    int left = 0;          // 左指针（起始位置）
    int right = S->len - 1;// 右指针（末尾位置）
    while (left < right) {
        // 交换左右指针指向的字符
        char temp = S->ch[left];
        S->ch[left] = S->ch[right];
        S->ch[right] = temp;
        // 指针移动
        left++;
        right--;
    }
}

3.操作3：删除字符
 

// 3. 字符删除：删除S中所有值为ch的字符
void StrDeleteCh(SString *S, char ch) {
    int k = 0;  // 记录有效字符的位置
    for (int i = 0; i < S->len; i++) {
        if (S->ch[i] != ch) {
            S->ch[k++] = S->ch[i];  // 有效字符存到k位置，k自增
        }
    }
    S->len = k;  // 更新串的长度为有效字符数
}

4.操作4：定位子串（查找主串中与子串进行匹配的起始位置）

// 4. 子串定位：从S的pos位置起，查找首次匹配T的起始位置（失败返回-1）
int StrIndex(SString *S, int pos, SString T) {
    // 边界检查：T为空、pos超出范围、S长度不足
    if (T.len == 0 || pos < 0 || pos >= S->len || S->len < T.len) {
        return -1;
    }
    // i：S中当前比较的位置，从pos开始；j：T中当前比较的位置
    int i = pos, j = 0;
    // 遍历S中可能的起始位置（最多到S->len - T->len）
    while (i <= S->len - T.len && j < T.len) {
        if (S->ch[i] == T.ch[j]) {
            // 字符匹配，继续比较下一个
            i++;
            j++;
        } else {
            // 字符不匹配，回溯：S回到上一轮起始位置+1，T回到0
            i = i - j + 1;
            j = 0;
        }
    }
    // 若j遍历完T，说明匹配成功，返回起始位置（i - T.len）
    return (j == T.len) ? (i - T.len) : -1;
}

5.代码汇总：

#include<stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXLEN 50   // 字符串的最大长度
typedef struct{
    char ch[MAXLEN];
    int  len;
}SString;

// 函数声明
void StrReplaceCh(SString *S, char ch1, char ch2);  /*字符替换函数*/
void StrRreverse(SString *S);   /*串逆置函数*/
void StrDeleteCh(SString *S, char ch);  /*在串S中删除值为ch的字符*/
int StrIndex(SString *S, int pos, SString T);  /*求串T在串S中的位置*/

// 串初始化（裁判代码已提供，此处仅作参考）
void StrInit(SString *s){
    s->len=0;
}

// 串赋值（裁判代码已提供，此处仅作参考）
void StrAssign(SString *s, char *r){    
    int i=0;
    while (r[i]!='\0'){
        s->ch[i]=r[i];
        i++;
    }
    s->len=i;
}

// 1. 字符替换：将S中所有ch1替换为ch2
void StrReplaceCh(SString *S, char ch1, char ch2) {
    for (int i = 0; i < S->len; i++) {
        if (S->ch[i] == ch1) {
            S->ch[i] = ch2;
        }
    }
}

// 2. 串逆置：将S中字符按相反次序存放
void StrRreverse(SString *S) {
    int left = 0;          // 左指针（起始位置）
    int right = S->len - 1;// 右指针（末尾位置）
    while (left < right) {
        // 交换左右指针指向的字符
        char temp = S->ch[left];
        S->ch[left] = S->ch[right];
        S->ch[right] = temp;
        // 指针移动
        left++;
        right--;
    }
}

// 3. 字符删除：删除S中所有值为ch的字符
void StrDeleteCh(SString *S, char ch) {
    int k = 0;  // 记录有效字符的位置
    for (int i = 0; i < S->len; i++) {
        if (S->ch[i] != ch) {
            S->ch[k++] = S->ch[i];  // 有效字符存到k位置，k自增
        }
    }
    S->len = k;  // 更新串的长度为有效字符数
}

// 4. 子串定位：从S的pos位置起，查找首次匹配T的起始位置（失败返回-1）
int StrIndex(SString *S, int pos, SString T) {
    // 边界检查：T为空、pos超出范围、S长度不足
    if (T.len == 0 || pos < 0 || pos >= S->len || S->len < T.len) {
        return -1;
    }
    // i：S中当前比较的位置，从pos开始；j：T中当前比较的位置
    int i = pos, j = 0;
    // 遍历S中可能的起始位置（最多到S->len - T->len）
    while (i <= S->len - T.len && j < T.len) {
        if (S->ch[i] == T.ch[j]) {
            // 字符匹配，继续比较下一个
            i++;
            j++;
        } else {
            // 字符不匹配，回溯：S回到上一轮起始位置+1，T回到0
            i = i - j + 1;
            j = 0;
        }
    }
    // 若j遍历完T，说明匹配成功，返回起始位置（i - T.len）
    return (j == T.len) ? (i - T.len) : -1;
}

// 裁判测试程序（已提供，此处仅作参考）
void main()
{
    SString s, s1, s2;
    char r[50], r1[50], r2[50];
    char ch, ch1, ch2;
    int i, loc, index;
    gets(r);  gets(r1);  gets(r2);
    scanf("%c %c %c", &ch, &ch1, &ch2); 
    StrAssign(&s, r);
    /*操作1：字符替换*/
    StrReplaceCh(&s, ch1, ch2);
    for(i=0;i<s.len;i++)
        printf("%c", s.ch[i]);
    printf("\n");
    /*操作2：串逆置*/
    StrRreverse(&s);
    for(i=0;i<s.len;i++)
        printf("%c", s.ch[i]);
    printf("\n");
    /*操作3：串删除*/
    StrDeleteCh(&s, ch);
    for(i=0;i<s.len;i++)
        printf("%c", s.ch[i]);
    printf("\n");
    /*操作4：串定位匹配*/
    StrAssign(&s1, r1); StrAssign(&s2, r2);
    scanf("%d", &index); 
    loc=StrIndex(&s1, index, s2);
    printf("%d\n",loc);
}

二、堆串的基本操作：

编写算法，实现堆串的基本操作StrReplace(S, T, V)。

初始条件: 串S, T和 V 均已存在,且 V 是非空串。

操作结果: 用V替换主串S中出现的所有与(模式串)T相等的不重叠的子串。

输入格式:

第一行：S

第二行：T

第三行：V

输出格式:

S = 被替换后的结果

1.替代操作：

// 核心：串替换函数
void StrReplace(HString *S, HString T, HString V) {
    // 边界条件：T为空或T长度大于S长度，无匹配可替换
    if (T.len == 0 || T.len > S->len) {
        return;
    }
    int pos = 0;  // 每次定位的起始位置
    int start;    // 匹配到的子串起始位置
    while (1) {
        // 从pos位置开始查找T的匹配
        start = StrIndex(S, pos, T);
        if (start == -1) {
            break;  // 无更多匹配，退出循环
        }
        // 1. 删除S中从start开始的T子串
        StrDelete(S, start, T.len);
        // 2. 在start位置插入V子串
        StrInsert(S, start, V);
        // 3. 更新下一轮定位起点（避免重叠，跳过已替换的V）
        pos = start + V.len;
        // 若起点超出S长度，退出循环
        if (pos >= S->len) {
            break;
        }
    }
}

2.代码汇总：

#include<stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct{
    char *ch;
    int  len;
}HString;

// 函数声明（裁判已提供部分，此处补充）
void StrReplace(HString *S, HString T, HString V);
void StrInit(HString *s);
int StrAssign(HString *s, char *tval);
int StrInsert(HString *s, int pos, HString t);
int StrDelete(HString *s, int pos, int len);
int StrIndex(HString *s, int pos, HString t);

//初始化
void StrInit(HString *s) {
    s->ch=NULL;
    s->len=0;
}
//赋值字符串
int StrAssign(HString *s, char *tval) {    
    int len,i=0;
    if (s->ch!=NULL) free(s->ch);
    while (tval[i]!='\0')  i++;
    len=i;
    if (len){
        s->ch=(char *)malloc(len);
        if (s->ch==NULL)  return(0); 
        for (i=0;i<len;i++)
            s->ch[i]=tval[i];
    }
    else  s->ch=NULL;
    s->len=len;
    return(1);
}
//插入串
int StrInsert(HString *s, int pos, HString t){
    int i;  
    char *temp;
    if (pos<0 || pos>s->len)
        return(0);
    temp=(char *)malloc(s->len + t.len);
    if (temp==NULL)  return(0);
    for (i=0;i<pos;i++)
        temp[i]=s->ch[i];
    for (i=0;i<t.len;i++)
        temp[i+pos]=t.ch[i];
    for (i=pos;i<s->len;i++)
        temp[i + t.len]=s->ch[i];
    s->len+=t.len;
    free(s->ch);
    s->ch=temp;
    return(1);
} 
//删除串
int StrDelete(HString *s, int pos, int len) {
    int i; 
    char *temp;
    if (pos<0 || pos>(s->len - len))
        return(0);
    temp=(char *)malloc(s->len - len);
    if (temp==NULL)  return(0);
    for (i=0;i<pos;i++)
        temp[i]=s->ch[i];
    for (i=pos;i<s->len - len;i++)
        temp[i]=s->ch[i+len];
    s->len=s->len-len;
    free(s->ch);
    s->ch=temp;
    return(1);
}
//求索引
int StrIndex(HString *s, int pos, HString t){
    int i,j,start;
    if (t.len==0 || pos < 0 || pos >= s->len)  return(-1);
    start=pos; i=start; j=0;
    while (i<s->len && j<t.len){
        if (s->ch[i]==t.ch[j])  {i++;j++;}
        else  {start++; i=start; j=0;}
    }
    if (j>=t.len) return(start);
    else return(-1);
} 

// 核心：串替换函数
void StrReplace(HString *S, HString T, HString V) {
    // 边界条件：T为空或T长度大于S长度，无匹配可替换
    if (T.len == 0 || T.len > S->len) {
        return;
    }
    int pos = 0;  // 每次定位的起始位置
    int start;    // 匹配到的子串起始位置
    while (1) {
        // 从pos位置开始查找T的匹配
        start = StrIndex(S, pos, T);
        if (start == -1) {
            break;  // 无更多匹配，退出循环
        }
        // 1. 删除S中从start开始的T子串
        StrDelete(S, start, T.len);
        // 2. 在start位置插入V子串
        StrInsert(S, start, V);
        // 3. 更新下一轮定位起点（避免重叠，跳过已替换的V）
        pos = start + V.len;
        // 若起点超出S长度，退出循环
        if (pos >= S->len) {
            break;
        }
    }
}

// 裁判测试程序
void main()
{
    HString s, t, v;
    char str1[100],str2[100],str3[100];
    int i;
    gets(str1);  StrInit(&s);  StrAssign(&s, str1);
    gets(str2);  StrInit(&t);  StrAssign(&t, str2);
    gets(str3);  StrInit(&v);  StrAssign(&v, str3);

    StrReplace(&s, t, v);
    printf("S = '");
    for(i=0;i<s.len;i++)
        printf("%c", s.ch[i]);
    printf("'\n");
}