整合營銷服務(wù)商
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
一、與串相關(guān)的概念
1、串（或字符串）是由零個或多個字符組成的有限序列。一般記作：s=〃c0c1c2…cn-1〃(n≥0)。零個字符的串稱為空串，通常以兩個相鄰的雙引號來表示空串，僅由空格組成的的串稱為空格串，如：s=〃〃；
2、串與線性表的異同。字符串一般簡稱為串，可以將它看作是一種特殊的線性表，這種線性表的數(shù)據(jù)元素的類型總是字符型的，字符串的數(shù)據(jù)對象約束為字符集。在線性表的基本操作中，大多以“單個元素”作為操作對象，而在串中，則是以“串的整體”或一部分作為操作對象。因此，線性表和串的操作有很大的不同。
3、當(dāng)兩個串的長度相等且各對應(yīng)位置上的字符都相同時，這兩個串是相等的。串中任意個連續(xù)字符組成的序列稱為該串的子串。包含子串的串被稱為主串。
4、模式匹配：子串定位運(yùn)算稱為模式匹配()或串匹配()。模式匹配成功是指在目標(biāo)串s中找到一個模式串t；模式匹配不成功則指目標(biāo)串s中不存在模式串t。在串匹配中，一般將主串稱為目標(biāo)串，子串稱之為模式串。
二、串的幾種表示方法
1、順序存儲結(jié)構(gòu)（靜態(tài)）
分配一組地址連續(xù)的存儲單元存放串值的字符序列。
#
String[+1];
2、串的塊鏈存儲表示
塊，一組連續(xù)的字符。塊鏈存儲表示，把串分成指定等長的塊，每一塊用一個結(jié)點表示，把各塊鏈成一個鏈表。當(dāng)一個結(jié)點不滿時，用特殊字符（如‘#’）填充。若塊的長度為1，就是以單字符為結(jié)點的鏈表結(jié)構(gòu)。
#;//定義結(jié)點的大小
{//結(jié)點結(jié)構(gòu)
charstr[];
*next;
}Lstring;
塊的大小與存儲密度有關(guān)：
3、堆分配存儲表示（常用）
堆存儲結(jié)構(gòu)的特點是，仍以一組空間足夠大的、地址連續(xù)的存儲單元存放串值字符序列，但它們的存儲空間是在程序執(zhí)行過程中動態(tài)分配的。所以也稱為動態(tài)存儲分配的順序表。每當(dāng)產(chǎn)生一個新串時，系統(tǒng)就從剩余空間的起始處為串值分配一個長度和串值長度相等的存儲空間。
在C語言中，存在一個稱為“堆”的自由空間，由動態(tài)分配函數(shù)malloc()分配一塊實際串長所需的存儲空間，如果分配成功，則返回這段空間的起始地址，作為串的基址。由free()釋放串不再需要的空間。
C語言對堆分配存儲結(jié)構(gòu)的定義如下：
{
char*str;
;
}Hstring;
三、Brute-Force算法的思想
Brute-Force算法的基本思想是：從目標(biāo)串s的第一個字符起和模式串t的第一個字符進(jìn)行比較，若相等，則繼續(xù)逐個比較后續(xù)字符，否則從串s的第二個字符起再重新和串t進(jìn)行比較。依此類推，直至串t中的每個字符依次和串s的一個連續(xù)的字符序列相等，則稱模式匹配成功，此時串t的第一個字符在串s中的位置就是t在s中的位置，否則模式匹配不成功。
四、Brute-Force算法的C語言描述
五、Brute-Force算法的C語言實現(xiàn)
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"ctype.h"
#
#
;//Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等
;//Boolean是布爾類型,其值是TRUE或false
#//數(shù)據(jù)元素個數(shù)
#//關(guān)鍵字的最大長度
#E10//存儲空間初始分配量
#2//存儲空間分配增量
char*ch;
;
}HString;
(HString&T)
{//初始化(產(chǎn)生空串)字符串T
T.length=0;
T.ch=NULL;
}//
(HString&T,char*chars)
{//生成一個其值等于串常量chars的串T
inti,j;
if(T.ch)
free(T.ch);//釋放T原有空間
i=strlen(chars);//求chars的長度i
if(!i)
{//chars的長度為0
T.ch=NULL;
T.length=0;
}//if
else
T.ch=(char*)malloc(i*sizeof(char));//分配串空間
if(!T.ch)exit(-1);//失敗
for(j=0;j
T.ch[j]=chars[j];
T.length=i;
}//else
;
}//
(HString&T)
inti;
for(i=0;i
printf("%c",T.ch[i]);
printf("\n");
}//
(,,intpos)
inti,j;
i=pos;//指向串s的第1個字符
j=0;//指向串t的第1個字符
while((i
if(s.ch[i]==t.ch[j])//比較兩個子串是否相等
{++i;//繼續(xù)比較后繼字符
++j;
}//if
else
i=i-j+1;//串s指針回溯重新開始尋找串t，注意，在算法中我們的存儲結(jié)構(gòu)是數(shù)組，我//們在此實現(xiàn)中，采用的是堆，導(dǎo)致語句有點小不一樣。
j=0;
}//else
if(j>=t.length)return(i-t.length+1);//匹配成功，返回模式串t在串s中的起始位置
;//匹配失敗返回0
(HString&t)
printf("串t為:");
(t);
}//
(HString&s)
charch[80];
printf(":\n");
scanf("%s",ch);
(s,ch);
}//InputS
intmain()
inti,pos=1;
,s;
(s);//由于HSring定義了指針，所以必須初始化
(t);
InputS(s);
InputS(t);
(s);
(t);
i=Index(s,t,pos);
printf(":%d\n",i);
return1;
六、Brute-Force算法的復(fù)雜度分析
最好的情況：算法時間復(fù)雜度為：O（Strlen(T)）;
最壞的情況：算法時間復(fù)雜度為：O（Strlen(S)×Strlen(T)）。
*請認(rèn)真填寫需求信息，我們會在24小時內(nèi)與您取得聯(lián)系。
