2.cpp

字符串匹配的BM算法,完全自己做出来的, 大家可以拿去参考,一切分享

 #include<malloc.h>    
 #include<stdio.h>     
 #include<math.h>      
 #include<process.h>                  
 #define OK 1        // 函数结果状态代码
 #define ERROR 0
 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK,ERROR
//==========================================================================
 typedef struct LNode {    
   char data;
   int  Xdata;
   struct LNode *next;
 }LNode;
 typedef struct LNode *LinkList;
//========================================================================
void InitList(LinkList *L){ 
   *L=(LinkList)malloc(sizeof(struct LNode));  /* 产生头结点，并使L指向此头结点 */
   if(!*L)   
     exit(OVERFLOW);  //存储分配失败 
   (*L)->next=NULL;   //指针域为空 
 }
//==========================================================================
Status ListInsert(LinkList L,int i,char name,int X,int jj){              
    int j=0;
    LinkList p=L,s;
   while(p&&j<i-1){   /* 寻找第i-1个结点 */
     p=p->next;
     if(p->data==name)
		 return ERROR;
     j++;   
   }
   if(!p||j>i-1)     /* i小于1或者大于表长 */
     return ERROR;
   s=(LinkList)malloc(sizeof(struct LNode));   /* 生成新的插入结点S */
   s->data=name;   
   if(X==jj+1)
     s->Xdata=X;
   else s->Xdata=X-jj-1;
   s->next=p->next;  
   p->next=s;
   return OK;
 }
//======================================================================
Status ListLength(LinkList L){ 
   int i=0;
   LinkList p=L->next;     /* p指向第一个结点 */
   while(p)       /* 直找到表尾 ，用i记录循环次数*/
	  { i++; 
        p=p->next; } 
   return i;      
}
//====================================================================
Status GetPlace(LinkList L, char e, int *X){   //已知e，用X，Y返回其所在结点的Xdata,Ydata值
   LinkList p=L->next;   
   while(p){
      if(p->data==e){    /* 找到这样的数据元素p->data,并返回所在结点的其它数据*/
	       *X=p->Xdata;
	        return OK; }
        else p=p->next;	   
      }
   return ERROR;
 }
//=======================================================================
Status GetLNode(LinkList L,int i,char *name,int *X) {  
   int j=0;             /* j为计数器 */
   LinkList p=L->next;  /* p指向第一个结点 */
   while(p&&j<i-1){     /* 顺指针向后查找，直到p指向第i个元素或p为空 */
      p=p->next; 
      j++; }
   if(!p||j>i-1)   
	   return ERROR;   /* 第i个元素不存在 */
   *name=p->data;   
   *X=p->Xdata;   /* 取第i个元素的数据 */
   return OK;
 }
//==========================================================================
void DestroyList(LinkList *L) { // 初始条件：线性表L已存在。操作结果：销毁线性表L 
   LinkList q;
   while(*L)
      { q=(*L)->next;
        free(*L);
        *L=q; }
 }
//============================================================================== 
void BM(LinkList L,char *t,char *p,int m){	 
	int n=0,r=0,g=0,i,j,k,X;
	while(t[n]!='\0') 	 n++;	
	m=m-1; 
	n=n-1;
	i=m;
    while(i<=n){   
    j=m;
	k=i;
	while(j>=0&&(p[j]==t[k])){
		j=j-1;
	    k=k-1;
	  }
	if(j+1==0){ 
	   printf("匹配位置为:%d\n",i-m+1);
	   g=g+1;
	   i=i+1;
	 }
	else 
		if(!GetPlace(L,t[k],&X))
		     i=k+m+1;
	    else i=k+X;
    }
  if(g==0)
	  printf("在正文中没有找到匹配的子串!\n\n");
}
//====================================================================================
void main(){ 
  LinkList L;
  int      i=0,j,jj,X,m=0;   
  char     t[255],p[255],name,PP,b;
  char a;      
  while(a!='n')
{
  InitList(&L);
  printf("输入正文:");  scanf("%s",t);
  printf("输入模式:");  scanf("%s",p); 
  while(p[m]!='\0')     m++;  
  for(j=0;j<m;j++){
	i=ListLength(L)+1;
	ListInsert(L,i,p[j],m,j); 
  }	   
  printf("字母到正整数的映射表：\n");                            
  for(j=1;j<=i;j++){ 
	GetLNode(L,j,&name,&X);            
	printf("dist(%c)=%d\n",name,X);
  }  
  BM(L,t,p,m);
  DestroyList(&L);   
  printf("\n映射表dist被销毁。按'n'键结束本次匹配演算,按其它键继续.");
  getchar(); 
  scanf("%c",&a);	  
 }
}