当前位置: 首页 > news >正文

字符串中删除子串

【问题描述】编写一个程序,当在一个字符串中出现子串时就删除它(字符串的字符个数不超过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; 
}

运行结果

相关文章:

  • 【vue】vuex
  • [C#小技巧]如何捕捉上升沿和下降沿
  • tf.ConfigProto类
  • 基于STM32单片机和Android的便携式数字示波器设计
  • 【刷题日记】笔试经典编程题目(八)
  • HBase基础入门|原理
  • 移动安全事件总结情况说明
  • Thread 类
  • u盘文件删除怎么恢复?解决方法很简单
  • LeetCode·392.判断子序列·动态规划
  • java基本微信小程序的校园通知小程序系统 uniapp 小程序
  • goahead(嵌入式) webservice (3.3.0)运行goforms
  • 解构赋值+$set()+axios
  • [网络管理 1] 环境配置与VLAN配置
  • java 基本微信小程序的讲座预约系统 uniapp 小程序
  • 520表白网页代码html 爱心网页制作
  • Linux内核之seqlock机制
  • 30+行业头部企业相聚杭城,创邻科技“Graph+X”生态合作伙伴大会成功举办
  • 【极力推荐】SpringBoot+SpringCloud全彩指南(终极版)
  • es6 用法总结
  • 2022全国车辆工程专业大学排名一览表
  • 2022周口职业技术学院单招学费多少钱一年-各专业收费标准
  • 2022年中原工学院艺术类招生简章
  • 2022浙江经贸职业技术学院学费多少钱一年-各专业收费标准
  • 2022年湖南大学强基计划报名条件-报名时间-报名入口
  • 2020河北工程大学运动训练专业招生简章
  • 2022湖州有哪些民办大学?湖州所有民办大学名单一览表(1所)
  • 2022天津城市建设管理职业技术学院学费多少钱一年-各专业收费标准
  • 2022滁州学院艺术类学费多少钱一年-各专业收费标准
  • 2022云南警官学院学费多少钱一年-各专业收费标准