程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> c數據結構的字符串查找的Brute-Force算法

c數據結構的字符串查找的Brute-Force算法

編輯：關於C語言

c數據結構的字符串查找的Brute-Force算法

#include
#include
#include

//定義字符串的結構體
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;ilength;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
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
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
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 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 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 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 printf("%c",myString3.str[i]);
printf(" maxLength=%d",myString3.maxLength);
printf(" length=%d\n",myString3.length);

////////////////////////////
for(i=0;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算法的時間效率不高，主要原因是：在主串和子串已有相當多個字符比較相等的情況下，只要有一個字符不相等，便需要把主串的比較位置回退。