首页 > 代码库 > c数据结构的字符串查找的Brute-Force算法

c数据结构的字符串查找的Brute-Force算法

2024-07-12 10:08:49   215人阅读

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


//定义字符串的结构体
typedef struct {


char *str;//字符串
int maxLength;//最大可以存放字符的长度
int length;//目前的字符长度
}DString;




//1.初始化操作
//初始化操作用来建立和存储串的动态数组空间以及给相关的数据域赋值
void Initiate(DString *s,int max,char *string){


int i;
s->str=(char *)malloc(sizeof(char)*max);//申请动态存储空间
s->maxLength=max;//动态数组元素的最大的个数
s->length=strlen(string);//置串的当前长度
for(i=0;i<s->length;i++){//进行for循环赋值

s->str[i]=string[i];//赋值
}
}




//2.插入子串操作
int Insert(DString *s,int pos,DString t){
//在主串s的pos位置插入子串t，插入成功返回1，失败返回0
int i;
if(pos<0){

printf("参数pos的位置出错，pos<0\n");
return 0;
}else{
//如果空间不够，则进行从新分配空间
if(s->length+t.length>s->maxLength){

//重新申请s->str所指的数组空间，原数组元素存放在新数组的前面
realloc(s->str,(s->length+t.length)*sizeof(char));
s->maxLength=s->length+t.length;//最大的长度变了
}


for(i=s->length-1;i>=pos;i--){
//依次往后移动t.length个位置
s->str[i+t.length]=s->str[i];
}


//在pos位置进行插入操作
for(i=0;i<t.length;i++){

s->str[pos+i]=t.str[i];//插入


}


s->length=s->length+t.length;//置新的数据元素的位置
return 1;
}
}






//3.删除子串操作
int Delete(DString *s,int pos,int len){
//删除主串s从pos位置开始的长度为len的子串，删除成功则返回1，失败则返回0
int i;
if(s->length<=0){
printf("数组中未存放字符无元素可删!\n");
return 0;
}else if(pos<0||len<0||pos+len>s->length){

printf("参数pos和len不合法!\n");
return 0;
}else{

for(i=pos+len;i<=s->length-1;i++){

s->str[i-len]=s->str[i];//依次前移len歌位置
}


s->length=s->length-len;//置新的元素的个数
return 1;
}




}






//4.取子串操作
int SubString(DString *s,int pos,int len,DString *t){
//取主串从pos位置开始的长度为len的子串，取成功则返回1，失败则返回0
int i;
if(pos<0||len<0||pos+len>s->length){

printf("参数pos和len的位置出错!!!\n");
return 0;
}
//当t的空间不够的时候，在进行从新分配空间
if(len>t->maxLength){

t->str=(char *)realloc(t->str,len*sizeof(char));//重新申请数组空间
t->maxLength=len;
}


for(i=0;i<len;i++){

t->str[i]=s->str[pos+i];//取子串
}


t->length=len;
return 1;


}






//5.撤销操作
void Destroy(DString *s){


//撤销串s占用的内存空间
free(s->str);
s->maxLength=0;
s->length=0;
}








//Brute-Force算法函数的设计
//i变量指示主串s当前比较字符的下标
//用j变量表示子串t当前比较字符的下标
int BFIndex(DString s,int start,DString t){


int i=start,j=0,v;
while(i<s.length&&j<t.length){

if(s.str[i]==t.str[j]){

i++;
j++;
}else{

i=i-j+1;
j=0;
}


}


if(j==t.length){

v=i-t.length;


}else{

v=-1;
}


return v;


}






int main(){
/*
DString myString1,myString2,myString3;
int i,max1=5,max2=9,max3=0;
//测试初始化函数
Initiate(&myString1,max1,"Data");
Initiate(&myString2,max2," Structure");
Initiate(&myString3,max3,"");


printf("初始化myString2串:        ");
for(i=0;i<myString2.length;i++)
printf("%c",myString2.str[i]);
printf("    maxLength=%d",myString2.maxLength);
    printf("    length=%d\n",myString2.length);


//测试插入函数
Insert(&myString2,0,myString1);
printf("插入子串后myString2串:  ");
for(i=0;i<myString2.length;i++)
printf("%c",myString2.str[i]);
printf("    maxLength=%d",myString2.maxLength);
    printf("    length=%d\n",myString2.length);


//测试删除函数
Delete(&myString2,0,5);
    printf("删除子串后myString2串:  ");
for(i=0;i<myString2.length;i++)
printf("%c",myString2.str[i]);
printf("    maxLength=%d",myString2.maxLength);
    printf("    length=%d\n",myString2.length);




//测试取子串函数
SubString(&myString2,0,5,&myString3);
printf("取子串后myString3串:  ");
for(i=0;i<myString3.length;i++)
printf("%c",myString3.str[i]);
printf("    maxLength=%d",myString3.maxLength);
    printf("    length=%d\n",myString3.length);






////////////////////////////
    for(i=0;i<myString2.length;i++)
printf("%c",myString2.str[i]);
printf("    maxLength=%d",myString2.maxLength);
    printf("    length=%d\n",myString2.length);




//测试撤销函数
//Destroy(&myString1);
    //Destroy(&myString2);
//Destroy(&myString3);
*/






DString myString1,myString2;
int max1=29,max2=9;
int pos=0;
Initiate(&myString1,max1,"Data Structure Data Structure");
    Initiate(&myString2,max2,"Structure");
//第一次查找
pos=BFIndex(myString1,pos,myString2);
printf("第一次查找时 pos=%d\n",pos);


//第二次查找
pos=BFIndex(myString1,pos+1,myString2);
printf("第二次查找时 pos=%d\n",pos);
return 0;

}


brute-force算法简单易于理解，在大部分的情况下，该算法的效率较好，但是在有些情况下，brute-force算法的时间效率不高，主要原因是：在主串和子串已有相当多个字符比较相等的情况下，只要有一个字符不相等，便需要把主串的比较位置回退。


联系
我们