bf演算法c

『壹』 C語言：KMP演算法在什麼情況下，比較次數會比BF演算法多，難道無人能解嗎，有解的話求測試例子！求大神快來解

當模式串與首次匹配前文本串的所有後綴的公共前綴長度之和小於模式串與首次匹配前文本串的長度之和的時候

『貳』 c語言字元串操作演示程序設計求大神= =

（1）字元串初始化InitString。--------->InitString()
（2）字元串輸入InputString。--------->InputString()
（3）字元串輸出OutputString。--------->OutputString()
（4）給定字元串，求串長StringLen。--------->StringLen()
（5）給定位置，串插入InsertStringbyLocation。--------->InsertStringbyLocation()
（6）BF演算法查找字元串BFSear1ch。--------->BFSear1ch()
（7）KMP演算法查找字元串KMPSearch。--------->KMPSearch()
你的理解有問題，剩下的應該怎麼做不用我說了，上面的函數都是沒有返回值和參數的，這個要你自己定了

『叄』 BF演算法的C語言實現：

int Index(SString S,SString T,int pos)
{ /* 返回子串T在主串S中第pos個字元之後的位置。若不存在，則函數值為0。 */
/* 其中，T非空，1≤pos≤StrLength(S)。演算法4.5 */
int i,j;
if(1<=pos&&pos<=S[0])
{
i=pos;
j=1;
while(i<=S[0]&&j<=T[0])/*S[0],T[0]中存放的為串長*/
if(S[i]==T[j]) /* 繼續比較後繼字元 */
{
++i;
++j;
}
else /* 指針後退重新開始匹配 */
{
i=i-j+2;
j=1;
}
if(j>T[0])
return i-T[0];
else
return 0;
}
else
return 0;
}

『肆』 求以下題目答案

第1題 在數據結構中，從邏輯上可以把數據結構分成（A ）。
A、動態結構和靜態結構
B、緊湊結構和非緊湊結構
C、線性結構和非線性結構
D、內部結構和外部結構

第2題 關於鏈表的特點描述不正確的是（D ）。
A、存儲空間不一定連續；
B、元素之間的後繼關系是由指針來體現的；
C、邏輯上相鄰，物理上不一定相鄰；
D、隨機存取（順序存取），即訪問任何一個元素的時間相同。

第3題 用堆棧求算術表達式a+b*(c-d)-e/f的後綴表達式為（ D）。
A、abcd-*+ef/-
B、a+b*(c-d)-e/f
C、abcdef-*+/-
D、abc-d*ef/+-

第4題 採用BF演算法在主串a a b a a a c a a c b b b中查找子串a a a c a a c b的查找次數為（ B）。
A、13
B、14
C、15
D、16

第5題 假設主串的長度為m，模式串的長度為n，BF演算法在一般和最壞情況下的時間復雜性分別為 （ C），所以還是一個常用演算法。由於有回溯，所以主串輸入後必須保存。
A、n+m n*m
B、n m
C、n*m n+m
D、m n

第6題 一維數組和線性表的區別為 (A ) 。
A、前者長度固定,後者長度可變
B、兩者長度均固定
C、前者長度可變,後者長度固定
D、兩者長度均可變

第7題 對廣義表L=((a,b),c,d)進行操作tail(head(L))的結果是（A ）。
A、(c,d )
B、(d )
C、b
D、(b)

第8題 設A是一個m*n階矩陣，A按列序存儲在一組連續的存儲單元中，每個元素佔用w個存儲單元，若A[1,1]的存儲地址為base，則A[i,j]的存儲地址為（B ）。
A、base+[(i-1)*m+(j-1)]*w
B、base+[(j-1)*m+(i-1)]*w
C、base+（j*m+i）*w
D、base+（j*m+i）*w

第9題 樹最適合用來表示（ C）。
A、有序數據元素
B、無序數據元素
C、元素之間具有分支層次關系的數據
D、元素之間無聯系的數據

第10題 樹根的層次為1，則有64個結點的完全二叉樹的深度為（A ）。
A、8
B、7
C、6
D、5

第11題 下列判斷正確的是（C ）。
A、二叉樹是樹的特例。
B、具有n個結點的完全二叉樹的深度為n/2。
C、Huffman樹是帶權路徑長度最小的二叉樹，樹中權值越大的葉子結點距離根結點越遠。
D、棧和隊列都是限制存取點的線性結構。

第12題 關於完全二叉樹，不正確的描述是（D ）。
A、每個結點必須首先有左兒子，然後才能有右兒子。
B、在具有相同結點的所有二叉樹中，它的高度最小。
C、每個結點的左右子樹的高度最多相差為1。
D、沒有度為1的結點。

第13題 某非空二叉樹的先序和後序序列正好相反，則二叉樹一定是（ A）的二叉樹。
A、空或只有一個結點
B、高度等於其結點數
C、任一結點無左孩子
D、任一結點無右孩子

第14題 在具有n個結點的二叉樹（二叉鏈表表示）中，值為空的鏈域數為( D)。
A、n-1
B、2n-1
C、n+1
D、2n+1

第15題 一棵具有 n個結點的完全二叉樹的樹高度（深度）是（ A）。
A、 logn +1
B、logn+1
C、 logn
D、logn-1

『伍』 關於BF演算法的C語言實現

我修改的程序都是把S[0] T[0]轉換為strlen(S) strlen(T)函數來實現的
為什麼不把strlen(S),strlen(T)分別賦予S[0],T[0],害怕覆蓋原來的數據嗎?沒有必要,他們原本就是來存儲這個數據的,君不見,它們都不參與匹配!他們的初始化應該在這個函數之外完成,在每次數組長度改變後,就及時設置,換句話說,在調用這個函數之前,應該保證他們已經設置正確,
在列印時,應該從第二個元素S[1]或T[1]開始,因為S[0],T[0]不再是數組的實際內容
不知道我有沒有表述清楚,
一般,數組的第一個元素存放實際的內容,而你這里並不是這樣,數組的第一個元素不再是數組的實際內容,而是數組長度
==================================================================
補充;
比較大小時S[0]的值不就變成了整形的ASCII碼值了么？
1.整數就是整數,沒有ASCII碼,ASCII碼是針對字元的
2.在C中,整數賦予字元變數是合法的
2.在C中,字元與整數的關系運算也是合法的,當你要把一個位元組的數解釋成字元的時候,它就是字元,可他存儲的還是數啊,就把它當整數用吧,畢竟我們沒有打算列印它,當然它能表示的整數太少了,所以數組長度受到限制
如果你要以字元顯示它,那它當然是那個整數所對應的字元,如果那是可列印字元的話

『陸』 一個簡單的小程序 C語言 BF演算法

引用沒問題，就是BF函數錯了。

#include<stdio.h>
#include<string.h>
#include<iostream>//.h去掉
usingnamespacestd;//命名空間

intBF(charS[],charT[])
{
inti,j,start;
i=0;
j=0;
start=0;
while(S[i]!=''&&T[j]!='')//T[i]改為T[j]
{
if(S[i]==T[j])
{
i++;j++;
}
else{
start++;
i=start;
j=0;
}
}
if(T[j]=='')
returnstart+1;//start+1，因為數組從0開始計數
else
return0;
}

intmain()
{
charS[1000],T[1000];
intstart;
printf("輸入主串：
");
scanf("%s",S);
printf("%s
",S);
printf("輸入子串:
");
scanf("%s",T);
printf("%s
",T);
start=BF(S,T);
cout<<"主串與子串在主串的第"<<start<<"個字元匹配"<<endl;

}

『柒』 數據結構 BF演算法

建議動手畫一畫會比較直觀
i,j是這里作位置指針 i指向SString S中的一個位置 j指向SString T的一個位置
while後的括弧中是循環繼續的條件
很多地方字元串本身可以理解成一個字元構成的數組
S[0]這里指0號位置的內容 這里用既然用i,j和這個0#內容比較來確定何時結束循環
即可以把0號位置的內容理解為i最終的移動位置 j同理
這里++i和i++皆可 先加後加不影響 因為本句里已經沒有再用到i的值了
最後一句 如果j>T[0]導致循環結束，此時返回i，這里i是一個在S中移動最終位置
與T[0]的差 相當於兩個最終位置間的距離
另外 一般用return 0 表示正常返回

強烈建議動手畫 文字表述不能很直觀

『捌』 使用BF演算法在主串S中查找子串T第一次出現的位置。函數int search_BF(char*s,c

#include<stdio.h>#include<string.h>void main(){ int count_substr(char *str,char *sub_str); char string[100]; char sub_str[100]; printf("input a string:\n"); scanf("%s",string); printf("input the substring:\n"); scanf("%s",sub_str); char *str1,*str2; str1 = string; str2 = sub_str; printf("count = %d",count_substr(str1,str2));}int count_substr(char *str,char *sub_str){ int count = 0; int i,j; for(i=0;i<strlen(str);i++) { for(j=0;j<strlen(sub_str);j++) { if(*(sub_str+j)!=*(str+i+j)) break; } if(j==strlen(sub_str))count++; } return count;}

『玖』 解析一哈c語言中的kmp演算法，bf演算法,kr演算法之間的聯系與區別，盡量淺顯易懂，謝謝！

三種演算法聯系：都是字元串匹配演算法。
區別：
「KMP演算法」：在匹配過程稱，若發生不匹配的情況，如果next[j]>=0，則目標串的指針i不變，將模式串的指針j移動到next[j]的位置繼續進行匹配；若next[j]=-1，則將i右移1位，並將j置0，繼續進行比較。
「BF演算法」是普通的模式匹配演算法，BF演算法的思想就是將目標串S的第一個字元與模式串P的第一個字元進行匹配，若相等，則繼續比較S的第二個字元和P的第二個字元；若不相等，則比較S的第二個字元和P的第一個字元，依次比較下去，直到得出最後的匹配結果。
「KR演算法」在每次比較時，用HASH演算法計算文本串和模式串的HASH映射，通過比較映射值的大小來比較字元串是否匹配。但是考慮到HASH沖突，所以在映射值相同的時候，還需要近一步比較字元串是否相同。但是在每次比較時，需要計算HASH值，所以選擇合適的HASH演算法很重要。
略知一二！

『拾』 C語言程序設計：單詞符號統計

導入文件可以直接調用庫函數fopen("filename","r");
要統計所有標識符及關鍵字需要用BF演算法實現比較容易，
函數體為：
int index(char str1[],char str2[])
{ int i=0,j=0,lenth1,lenth2;
lenth1=strlen(str1);
lenth2=strlen(str2);
while(i<lenth1&&j<lenth2){
if(str1[i]==str2[j]){ i++;j++;}
else{ i=i-j+1;j=0;}
}
return (j>=lenth2)?0:-1;
}
你再根據實際情況修改一下。
至於統計標點符號的個數很簡單，我寫過一個類似的程序，你稍作修改一下就行。
#include<stdio.h>
#include<stdlib.h>
void main()
{
int character=0,line=0,sentence=0,define=0;
char ch;
FILE *fout;
if((fout=fopen("filename","r"))==NULL){
printf("Cannot open the file!\n");
exit(0);
}
while(!feof(fout)){
ch=fgetc(fout);
character++;
putchar(ch);
switch(ch){
case'\n':line++;break;//遇到'\n'表示一行
case';':sentence++;break; //遇到';'表示一條語句
case'#':define++;break; //遇到'#'表示一個預處理
}
}
printf("\n\n字元：%d個\n",character);
printf("行數：%d行\n",line+1);//讀到文件尾時會結束，沒有回車符，所以要加1
printf("語句：%d句\n",sentence);
printf("預處理：%d個\n",define);
fclose(fout);
}