Question

下面是BM算法的C语言源码，小弟看的不是太懂，求高手在重点位置加点标注既对每行代码解释一下，谢谢。。。

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

/*生成skip数组，即delta1数组*/
int *make_skip(char *ptrn, int plen)
{
int *skip = (int *)malloc(256 * sizeof(int));
int *sptr = skip + 256;

if (skip == NULL)
fprintf(stderr, "malloc failed!");

while (sptr-- != skip)
*sptr = plen + 1;

while (plen != 0)
skip[(unsigned char)*ptrn++] = plen--;

return skip;
}

/*生成shift数组，即delta2数组*/
int *make_shift(char *ptrn, int plen)
{
int *shift = (int *)malloc(plen * sizeof(int));
int *sptr = shift + plen - 1;
char *pptr = ptrn + plen - 1;
char c;

if (shift == NULL)
fprintf(stderr, "malloc failed!");

c = ptrn[plen - 1];
*sptr = 1;

while (sptr -- != shift)
{
char *p1 = ptrn + plen - 2, *p2, *p3;

do
{
while (p1 >= ptrn && *p1-- != c);

p2 = ptrn + plen - 2;
p3 = p1;

while (p3 >= ptrn && *p3-- == *p2-- && p2 >=pptr);
}while (p3 >= ptrn && p2 >= pptr);

*sptr = shift + plen - sptr + p2 - p3;

pptr--;
}
return shift;
}

/*搜索函数*/
int mSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)
{
int b_idx = plen;

if (plen == 0)
return 1;

while (b_idx <= blen)
{
int p_idx = plen, skip_stride, shift_stride;

while (buf[--b_idx] == ptrn[--p_idx])
{
if (b_idx < 0)
return 0;

if (p_idx == 0)
{
return 1;
}
}

skip_stride = skip[(unsigned char)buf[b_idx]];
shift_stride = shift[p_idx];

b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;
}

return 0;
}

int main()
{
char str[100] = "faecabcxxdefeabcxxxabcdwaw";
char pattern[10] = "abcxxxabc";
int *skip, *shift, i;

skip = make_skip(pattern, strlen(pattern));
shift = make_shift(pattern, strlen(pattern));

if (!mSearch(str, strlen(str), pattern, strlen(pattern), skip, shift))
printf("The string \"%s\" doesn't contain string \"%s\"\n", str, pattern);
else
printf("The string \"%s\" does contain string \"%s\"\n", str, pattern);

return 0;
}

Answer 1

Dijkstra算法--c++源代码--by 伟伟猪 [转贴 2005-12-15 20:21:00 ] 发表者: 伟伟猪

/***********************************************
设G=(V,E)是一个每条边都有非负长度的有向图，有一个特异的顶点s称为缘。
单源最短路径问题，或者称为最短路径问题，是要确定从s到V中没一个其他
顶点的距离，这里从顶点s到x的距离定义为从s到x的最短路径问题。这个问题
可以用Dijkstra算法解决。下面我给我了c++下的源代码！ --by 伟伟猪
************************************************/
#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;

d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];

for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}

for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t))
s[k]=1;//point k join the S
for (j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))

}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";

}
/*********
顶点个数用n表示，这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具体例子见 电子工业出版社 《算法设计技巧与分析》148页
************/