©2020-2024 ioDraw All rights reserved
【问题描述】编写一个程序，当在一个字符串中出现子串时就删除它（字符串的字符个数不超过1000）。
【输入形式】第一行输入一个字符串，第二行输入一个子串。
【输出形式】程序在下一行输出删除其中所有子串后的字符串。如果字符串不包含子串则输出原字符串本身。
【样例输入1】
I am a boy!
a
【样例输出1】
I m boy!
【样例输入2】
Ah Love!could you and I with Fate conspire
ould
【样例输出2】
Ah Love!c you and I with Fate conspire
初始化一个顺序串
初始化一个顺序串，方法基本和初始化一个顺序表相同
#include<stdio.h> #include<malloc.h> #include<string.h> #define SIZE 10
#define INCREAM 10 typedef struct String{ char *data; //因为是个串，所以应该是字符型 int len;
int size; }String,*PString; //其他都和顺序表一样 int Init_String(PString S){
S->data=(char *)malloc(sizeof(char)*SIZE); S->len=0; S->size=SIZE; return 1; }
将字符串赋值给串
在将字符串赋值给串的时候要小心，先判断串的最大容量是否够容下字符串，不够的话要重新开辟空间
int Creat_String(PString S,char *s){ if(strlen(s)>S->size){ //先判断串的大小是否足够
S->data=(char *)realloc(S->data,(S->size+INCREAM)*sizeof(char));
S->size+=INCREAM; } int i=0; while(*s){ //将字符串的值依次赋值给串 S->data[i++]=*s++;
S->len++; } return 1; }
查找子串并输出子串在主串中的位置
查找子串时运用了BF算法
int Index_String(PString S,PString T,int start){ int i=start-1; int j=0;
while(i<S->len&&j<T->len){ if(S->data[i]==T->data[j]){ //BF算法 i++; j++; }else{
i=i-j+1; j=0; } } if(j>=T->len){ return i-T->len+1; }else{ return 0; } }
删除子串（方法一）
int Delete_1_Sub(PString S,PString T){ int pos=1,t; int i,j,k;
for(i=0;i<S->len;i++){ if(Index_String(S,T,pos)) //判断是否查找成功 {
t=Index_String(S,T,pos); //t是子串在主串中的位置 for(j=0;j<T->len;j++){
//一种方法是运用双重循环，实现删除操作 for(k=t-1;k<S->len-1;k++){ S->data[k]=S->data[k+1]; }
S->len--; //每删除一个顺序串长度减少1 } } pos++; } }
删除子串（方法二）
int Delete_2_Sub(PString S,PString T){ int pos=1,k; int i;
for(i=0;i<S->len;i++){ if(Index_String(S,T,pos)) { int j;
k=Index_String(S,T,pos); for(j=k-1;j<S->len-T->len;j++) //这种方法不容易想到 {
S->data[j]=S->data[j+T->len]; //时间复杂度相对较小 } S->len=S->len-T->len; } pos++; } }
打印串
int Print_String(PString S){ int i; for(i=0;i<S->len;i++){
printf("%c",S->data[i]); } printf("\n"); return 1; }
完整代码
#include<stdio.h> #include<malloc.h> #include<string.h> #define SIZE 10
#define INCREAM 10 typedef struct String{ char *data; int len; int size;
}String,*PString; int Init_String(PString S){ S->data=(char
*)malloc(sizeof(char)*SIZE); S->len=0; S->size=SIZE; return 1; } int
Creat_String(PString S,char *s){ if(strlen(s)>S->size){ S->data=(char
*)realloc(S->data,(S->size+INCREAM)*sizeof(char)); S->size+=INCREAM; } int i=0;
while(*s){ S->data[i++]=*s++; S->len++; } return 1; } int Copy_String(PString
S,PString T){ int i; S->len=T->len; for(i=0;i<T->len;i++){
S->data[i]=T->data[i]; } return 1; } int Index_String(PString S,PString T,int
start){ int i=start-1; int j=0; while(i<S->len&&j<T->len){
if(S->data[i]==T->data[j]){ i++; j++; }else{ i=i-j+1; j=0; } } if(j>=T->len){
return i-T->len+1; }else{ return 0; } } int Delete_1_Sub(PString S,PString T){
int pos=1,t; int i,j,k; for(i=0;i<S->len;i++){ if(Index_String(S,T,pos)) {
t=Index_String(S,T,pos); for(j=0;j<T->len;j++){ for(k=t-1;k<S->len-1;k++){
S->data[k]=S->data[k+1]; } S->len--; } } pos++; } } int Delete_2_Sub(PString
S,PString T){ int pos=1,k; int i; for(i=0;i<S->len;i++){
if(Index_String(S,T,pos)) { int j; k=Index_String(S,T,pos);
for(j=k-1;j<S->len-T->len;j++) { S->data[j]=S->data[j+T->len]; }
S->len=S->len-T->len; } pos++; } } int Print_String(PString S){ int i;
for(i=0;i<S->len;i++){ printf("%c",S->data[i]); } printf("\n"); return 1; } int
main(){ char s[100],t[100]; String S,T; gets(s); gets(t); Init_String(&S);
Init_String(&T); Creat_String(&S,s); Creat_String(&T,t); //Creat_2_Sub(&S,&T);
Delete_1_Sub(&S,&T); Print_String(&S); return 0; }
运行结果