模式匹配.txt

用C语言编写的一个简单的数据结构算法.可实现括号的模式匹配.

/* 模式匹配问题的无回溯算法*/

#include<stdio.h>

#define  MAXNUM    	100	/* 串允许的最大字符个数 */
struct SeqString 				/* 顺序串的类型 */
{ 
	char  c[MAXNUM];
    int   n;					/* 串的长度，n<MAXNUM */
};
 
typedef  struct SeqString  *PSeqString;

struct SeqString t={
	'a','a','b','c','b','a','b','c','a','a','b','c','a','a','b','a','b','c'},
p={'a','b','c','a','a','b','a','b','c'};



void makeNext(PSeqString p, int *next)

/* 变量next是数组next的第一个元素next[0]的地址 */

{    int i=0,k=-1;   /* 初始化 */

next[0]=-1;          

while (i<p->n-1)            /* 计算next[i+1] */

{    while (k>=0 && p->c[i]!=p->c[k])/* 找出p0…pi中最大的相同的前后缀长度k */

k=next[k];

i++; k++;

if (p->c[i]==p->c[k])           /* 填写next[i]，同时考虑改善 */

next[i]=next[k];

else next[i]=k;

}

}


int index(PSeqString t,PSeqString p, int *next)

/* 求p所指的串在t所指的串中第一次出现时，*/

/* p所指串的第一个元素在t所指的串中的序号 */

/* 变量next是数组next的第一个元素next[0]的地址 */

{    int i=0,j=0;                           /* 初始化 */

while (i<p->n && j<t->n)         /*反复比较*/

if (i==-1||p->c[i]==t->c[j]){ i++; j++; }    /* 继续匹配下一字符 */

else i=next[i];                       /* j不变，i后退 */

if (i>=p->n)

return( j - p->n + 1); /* 匹配成功，返回p中第一个字符在t中的序号 */

else return 0;                   /* 匹配失败 */

}




int main( ){
PSeqString pt=&t,pp=&p;
int next[MAXNUM];
pt->n=18;
pp->n=9;
makeNext(pp,next);
printf("%d\n",index(pt,pp,next));
return 0;
}




==================================================
/* 模式匹配问题的朴素算法(有回溯算法)*/

#include<stdio.h>

#define  MAXNUM    	100	/* 串允许的最大字符个数 */
struct SeqString 				/* 顺序串的类型 */
{ 
	char  c[MAXNUM];
      int   n;					/* 串的长度，n<MAXNUM */
};
 
typedef  struct SeqString  *PSeqString;


struct SeqString t={
	'a','a','b','c','b','a','b','c','a','a','b','c','a','a','b','a','b','c'},
p={'a','b','c','a','a','b','a','b','c'};


int index(PSeqString t,PSeqString p)

/* 求p所指的串在t所指的串中第一次出现时,*/

/*p所指串的第一个元素在t所指的串中的序号(即：下标+1) */

{    int i=0,j=0;/*初始化*/

while (i<p->n && j<t->n)   /*反复比较*/

if (p->c[i]==t->c[j]){ i++; j++; }         /* 继续匹配下一个字符 */

/* 主串、子串的i、j值回溯，重新开始下一次匹配 */

else{ j = j - i + 1;i = 0;}

if (i>=p->n)

return( j - p->n + 1);/* 匹配成功，返回p中第一个字符在t中的序号 */

else return 0;             /* 匹配失败 */

}



int main( ){
PSeqString pt=&t,pp=&p;
pt->n=18;
pp->n=9;
printf("%d\n",index(pt,pp));
return 0;
}