Data StructuresWord文件下载.docx
- 文档编号:4009749
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:14
- 大小:49.29KB
Data StructuresWord文件下载.docx
《Data StructuresWord文件下载.docx》由会员分享,可在线阅读,更多相关《Data StructuresWord文件下载.docx(14页珍藏版)》请在冰点文库上搜索。
#include<
string.h>
ctype.h>
malloc.h>
/*malloc()等*/
limits.h>
/*INT_MAX等*/
stdio.h>
/*EOF(=^Z或F6),NULL*/
stdlib.h>
/*atoi()*/
io.h>
/*eof()*/
math.h>
/*floor(),ceil(),abs()*/
process.h>
/*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
#defineMAXSTRLEN40/*用户可在255以内定义最大串长(1个字节)*/
#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*/
for(i=0;
=S[0];
T[i]=S[i];
returnOK;
StatusStrEmpty(SStringS)
{/*若S为空串,则返回TRUE,否则返回FALSE*/
if(S[0]==0)
returnTRUE;
returnFALSE;
intStrCompare(SStringS,SStringT)
{/*初始条件:
串S和T存在*/
/*操作结果:
若S>
T,则返回值>
0;
若S=T,则返回值=0;
若S<
T,则返回值<
0*/
for(i=1;
=S[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;
/*令串长为零*/
StatusConcat(SStringT,SStringS1,SStringS2)/**/
{/*用T返回S1和S2联接而成的新串。
若未截断,则返回TRUE,否则FALSE*/
if(S1[0]+S2[0]<
=MAXSTRLEN)
{/*未截断*/
=S1[0];
T[i]=S1[i];
=S2[0];
T[S1[0]+i]=S2[i];
T[0]=S1[0]+S2[0];
{/*截断S2*/
=MAXSTRLEN-S1[0];
T[0]=MAXSTRLEN;
StatusSubString(SStringSub,SStringS,intpos,intlen)
{/*用Sub返回串S的第pos个字符起长度为len的子串。
*/
if(pos<
1||pos>
S[0]||len<
0||len>
S[0]-pos+1)
=len;
Sub[i]=S[pos+i-1];
Sub[0]=len;
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<
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;
return0;
StatusStrInsert(SStringS,intpos,SStringT)
串S和T存在,1≤pos≤StrLength(S)+1*/
在串S的第pos个字符之前插入串T。
完全插入返回TRUE,部分插入返回FALSE*/
S[0]+1)
if(S[0]+T[0]<
{/*完全插入*/
for(i=S[0];
i>
=pos;
i--)
S[i+T[0]]=S[i];
for(i=pos;
pos+T[0];
S[i]=T[i-pos+1];
S[0]=S[0]+T[0];
{/*部分插入*/
for(i=MAXSTRLEN;
S[i]=S[i-T[0]];
S[0]=MAXSTRLEN;
StatusStrDelete(SStringS,intpos,intlen)
串S存在,1≤pos≤StrLength(S)-len+1*/
从串S中删除第pos个字符起长度为len的子串*/
S[0]-len+1||len<
0)
for(i=pos+len;
S[i-len]=S[i];
S[0]-=len;
StatusReplace(SStringS,SStringT,SStringV)
串S,T和V存在,T是非空串(此函数与串的存储结构无关)*/
用V替换主串S中出现的所有与T相等的不重叠的子串*/
inti=1;
/*从串S的第一个字符起查找串T*/
if(StrEmpty(T))/*T是空串*/
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);
voidDestroyString()
{/*由于SString是定长类型,无法销毁*/
voidStrPrint(SStringT)
{/*输出字符串T。
另加*/
printf("
%c"
T[i]);
printf("
\n"
);
voidget_next(SStringT,intnext[])
{/*求模式串T的next函数值并存入数组next*/
inti=1,j=0;
next[1]=0;
while(i<
if(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算法。
inti=pos,j=1;
if(j==0||S[i]==T[j])/*继续比较后继字符*/
else/*模式串向右移动*/
if(j>
T[0])/*匹配成功*/
returni-T[0];
return0;
Drivefile
voidmain()
{
inti,j,*p;
SStrings1,s2;
StrAssign(s1,"
ababababcabcbcc"
masterstringis:
"
StrPrint(s1);
StrAssign(s2,"
abcacba"
substring:
StrPrint(s2);
i=StrLength(s2);
p=(int*)malloc((i+1)*sizeof(int));
/*creatnextarrayofs2*/
get_next(s2,p);
nextfunctionofsubstringis:
for(j=1;
=i;
j++)
%d"
*(p+j));
i=Index_KMP(s1,s2,1,p);
if(i)
masterstringandsubstringfirstmatchat%dcharacter\n"
i);
thematchingbetweenmasterstringandsubstringisfailed\n"
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Data Structures