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);
}