Data Structures.docx
《Data Structures.docx》由会员分享,可在线阅读,更多相关《Data Structures.docx(14页珍藏版)》请在冰点文库上搜索。
![Data Structures.docx](https://file1.bingdoc.com/fileroot1/2023-4/30/233c56f1-2043-4c44-a482-c5e796f64fa3/233c56f1-2043-4c44-a482-c5e796f64fa31.gif)
DataStructures
DataStructures’PracticeReport
Lab2
Patternmatchingalgorithmofstring
----KMP
Candidate:
TingChen
StudentIDNo:
075081-12
Major:
CommunicationEngineering
Supervisor:
RangZhongWu
FacultyofElectronicInformation&Mechanics
ChinaUniversityofGeosciences(WuHan)
No.388LumoRoad,WuhanCity,HuBeiProvince,430074,P.R.China
March2011
§1Introduction
Patternmatchingalgorithmofstring-KMP,Lordstringandpatternstringconductpatternmatching.ThealgorithmisnotBacktracking,anditisbasedonnextfunctionvalue.Sowemustcomputethevalueofnextfunction.
§2RuntimeEnvironment
Hardwareplatform:
MicrosoftwindowsXP
Professional版本2002Servicepack3
CpuT44002.20GHz
SoftWareplatform:
MicrosoftVisualC++
§3ADT
#include
#include
#include/*malloc()等*/
#include/*INT_MAX等*/
#include/*EOF(=^Z或F6),NULL*/
#include/*atoi()*/
#include/*eof()*/
#include/*floor(),ceil(),abs()*/
#include/*exit()*/
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码,如OK等*/
typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/
#defineMAXSTRLEN40/*用户可在255以内定义最大串长(1个字节)*/
typedefcharSString[MAXSTRLEN+1];/*0号单元存放串的长度*/
StatusStrAssign(SStringT,char*chars);
StatusStrCopy(SStringT,SStringS);
StatusStrEmpty(SStringS);
intStrCompare(SStringS,SStringT);
intStrLength(SStringS);
StatusClearString(SStringS);
StatusConcat(SStringT,SStringS1,SStringS2);
StatusSubString(SStringSub,SStringS,intpos,intlen);
intIndex(SStringS,SStringT,intpos);
StatusStrInsert(SStringS,intpos,SStringT);
StatusStrDelete(SStringS,intpos,intlen);
StatusReplace(SStringS,SStringT,SStringV);
voidDestroyString();
voidStrPrint(SStringT);
voidget_next(SStringT,intnext[]);
intIndex_KMP(SStringS,SStringT,intpos,intnext[]);
§4DebugingandExperimentalResult
§5Summary
First,weknowthatKMPisaPatternmatchingalgorithmofstring,Lordstringandpatternstringconductpatternmatching.ThealgorithmisnotBacktracking,anditisbasedonnextfunctionvalue.Sowemustcomputethevalueofnextfunction.Whenwecomputethenextfunctionvalue,weshouldknowifPk=Pj?
Thenweknowifwecanusenext[j+1]=next[j]+1,thenweknowwhatcanwedonextstep.
§6ProgramList
InterfaceFile
#ifndefKMP_H
#defineKMP_H
#include
#include
#include/*malloc()等*/
#include/*INT_MAX等*/
#include/*EOF(=^Z或F6),NULL*/
#include/*atoi()*/
#include/*eof()*/
#include/*floor(),ceil(),abs()*/
#include/*exit()*/
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码,如OK等*/
typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/
#defineMAXSTRLEN40/*用户可在255以内定义最大串长(1个字节)*/
typedefcharSString[MAXSTRLEN+1];/*0号单元存放串的长度*/
StatusStrAssign(SStringT,char*chars);
StatusStrCopy(SStringT,SStringS);
StatusStrEmpty(SStringS);
intStrCompare(SStringS,SStringT);
intStrLength(SStringS);
StatusClearString(SStringS);
StatusConcat(SStringT,SStringS1,SStringS2);
StatusSubString(SStringSub,SStringS,intpos,intlen);
intIndex(SStringS,SStringT,intpos);
StatusStrInsert(SStringS,intpos,SStringT);
StatusStrDelete(SStringS,intpos,intlen);
StatusReplace(SStringS,SStringT,SStringV);
voidDestroyString();
voidStrPrint(SStringT);
voidget_next(SStringT,intnext[]);
intIndex_KMP(SStringS,SStringT,intpos,intnext[]);
#endif
implementationfile
#include"kmp.h"
StatusStrAssign(SStringT,char*chars)
{/*生成一个其值等于chars的串T*/
inti;
if(strlen(chars)>MAXSTRLEN)
returnERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
returnOK;
}
}
StatusStrCopy(SStringT,SStringS)
{/*由串S复制得串T*/
inti;
for(i=0;i<=S[0];i++)
T[i]=S[i];
returnOK;}
StatusStrEmpty(SStringS)
{/*若S为空串,则返回TRUE,否则返回FALSE*/
if(S[0]==0)
returnTRUE;
else
returnFALSE;
}
intStrCompare(SStringS,SStringT)
{/*初始条件:
串S和T存在*/
/*操作结果:
若S>T,则返回值>0;若S=T,则返回值=0;若Sinti;
for(i=1;i<=S[0]&&i<=T[0];++i)
if(S[i]!
=T[i])
returnS[i]-T[i];
returnS[0]-T[0];
}
intStrLength(SStringS)
{/*返回串的元素个数*/
returnS[0];
}
StatusClearString(SStringS)
{/*初始条件:
串S存在。
操作结果:
将S清为空串*/
S[0]=0;/*令串长为零*/
returnOK;
}
StatusConcat(SStringT,SStringS1,SStringS2)/**/
{/*用T返回S1和S2联接而成的新串。
若未截断,则返回TRUE,否则FALSE*/
inti;
if(S1[0]+S2[0]<=MAXSTRLEN)
{/*未截断*/
for(i=1;i<=S1[0];i++)
T[i]=S1[i];
for(i=1;i<=S2[0];i++)
T[S1[0]+i]=S2[i];
T[0]=S1[0]+S2[0];
returnTRUE;
}
else
{/*截断S2*/
for(i=1;i<=S1[0];i++)
T[i]=S1[i];
for(i=1;i<=MAXSTRLEN-S1[0];i++)
T[S1[0]+i]=S2[i];
T[0]=MAXSTRLEN;
returnFALSE;
}
}
StatusSubString(SStringSub,SStringS,intpos,intlen)
{/*用Sub返回串S的第pos个字符起长度为len的子串。
*/
inti;
if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)
returnERROR;
for(i=1;i<=len;i++)
Sub[i]=S[pos+i-1];
Sub[0]=len;
returnOK;
}
intIndex(SStringS,SStringT,intpos)
{/*返回子串T在主串S中第pos个字符之后的位置。
若不存在,则函数值为0。
*/
/*其中,T非空,1≤pos≤StrLength(S)。
*/
inti,j;
if(1<=pos&&pos<=S[0])
{
i=pos;
j=1;
while(i<=S[0]&&j<=T[0])
if(S[i]==T[j])/*继续比较后继字符*/
{
++i;
++j;
}
else/*指针后退重新开始匹配*/
{
i=i-j+2;
j=1;
}
if(j>T[0])
returni-T[0];
else
return0;
}
else
return0;}
StatusStrInsert(SStringS,intpos,SStringT)
{/*初始条件:
串S和T存在,1≤pos≤StrLength(S)+1*/
/*操作结果:
在串S的第pos个字符之前插入串T。
完全插入返回TRUE,部分插入返回FALSE*/
inti;
if(pos<1||pos>S[0]+1)
returnERROR;
if(S[0]+T[0]<=MAXSTRLEN)
{/*完全插入*/
for(i=S[0];i>=pos;i--)
S[i+T[0]]=S[i];
for(i=pos;iS[i]=T[i-pos+1];
S[0]=S[0]+T[0];
returnTRUE;
}
else
{/*部分插入*/
for(i=MAXSTRLEN;i<=pos;i--)
S[i]=S[i-T[0]];
for(i=pos;iS[i]=T[i-pos+1];
S[0]=MAXSTRLEN;
returnFALSE;
}
}
StatusStrDelete(SStringS,intpos,intlen)
{/*初始条件:
串S存在,1≤pos≤StrLength(S)-len+1*/
/*操作结果:
从串S中删除第pos个字符起长度为len的子串*/
inti;
if(pos<1||pos>S[0]-len+1||len<0)
returnERROR;
for(i=pos+len;i<=S[0];i++)
S[i-len]=S[i];
S[0]-=len;
returnOK;
}
StatusReplace(SStringS,SStringT,SStringV)
{/*初始条件:
串S,T和V存在,T是非空串(此函数与串的存储结构无关)*/
/*操作结果:
用V替换主串S中出现的所有与T相等的不重叠的子串*/
inti=1;/*从串S的第一个字符起查找串T*/
if(StrEmpty(T))/*T是空串*/
returnERROR;
do
{
i=Index(S,T,i);/*结果i为从上一个i之后找到的子串T的位置*/
if(i)/*串S中存在串T*/
{
StrDelete(S,i,StrLength(T));/*删除该串T*/
StrInsert(S,i,V);/*在原串T的位置插入串V*/
i+=StrLength(V);/*在插入的串V后面继续查找串T*/
}
}while(i);
returnOK;
}
voidDestroyString()
{/*由于SString是定长类型,无法销毁*/
}
voidStrPrint(SStringT)
{/*输出字符串T。
另加*/
inti;
for(i=1;i<=T[0];i++)
printf("%c",T[i]);
printf("\n");
}
voidget_next(SStringT,intnext[])
{/*求模式串T的next函数值并存入数组next*/
inti=1,j=0;
next[1]=0;
while(iif(j==0||T[i]==T[j])
{
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
intIndex_KMP(SStringS,SStringT,intpos,intnext[])
{/*利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。
*/
/*其中,T非空,1≤pos≤StrLength(S)。
*/
inti=pos,j=1;
while(i<=S[0]&&j<=T[0])
if(j==0||S[i]==T[j])/*继续比较后继字符*/
{
++i;
++j;
}
else/*模式串向右移动*/
j=next[j];
if(j>T[0])/*匹配成功*/
returni-T[0];
else
return0;
}
Drivefile
#include"kmp.h"
voidmain()
{
inti,j,*p;
SStrings1,s2;
StrAssign(s1,"ababababcabcbcc");
printf("masterstringis:
");
StrPrint(s1);
StrAssign(s2,"abcacba");
printf("substring:
");
StrPrint(s2);
i=StrLength(s2);
p=(int*)malloc((i+1)*sizeof(int));/*creatnextarrayofs2*/
get_next(s2,p);
printf("nextfunctionofsubstringis:
");
for(j=1;j<=i;j++)
printf("%d",*(p+j));
printf("\n");
i=Index_KMP(s1,s2,1,p);
if(i)
printf("masterstringandsubstringfirstmatchat%dcharacter\n",i);
else
printf("thematchingbetweenmasterstringandsubstringisfailed\n");
}