实验总结报告串和数组.docx
《实验总结报告串和数组.docx》由会员分享，可在线阅读，更多相关《实验总结报告串和数组.docx（20页珍藏版）》请在冰点文库上搜索。
实验总结报告串和数组
实验总结报告—栈和队列
学号：
姓名：
时间：
一、目的
1.做实验的目的
2.2.撰写实验报告的目的
二、内容
1.说明实验次数及实验内容
本次实验用一个实验课时完成。
实验内容：
1.编写函数StrAssign（）,StrCopy（）,StrLenth（）,StrCompare（）,StrConcat（）,
Substring（）,Replace（）,完成串赋值,串复制,求串长度,串比较,串连接,求字
串,子串替代等相应功能。
注:
Replace（）依赖Find_KMP（）
2.使用KMP算法,编写函数Find_KMP（char*S,char*P,intstart）实现字符串匹配。
测试数据:
2.1
charS[]=“abcabcabcd”;
charP[]=“abcabcd”;
2.2charS[]=“abcdababcabcdabcabcabcd”;
charP[]=“abcabcd”;
2.3
charS[]=“cocaocoaoc”;
charP[]=“coaoc”;
要求:
1.打印出模式串P的next[]模式数组;
2.完成Find_KMP（）后在Repalce（）中调用,将P替换成“AAA”。
注意2.2有2个地方要替换。
3.创建三元组实现以下稀疏矩阵的存储,并利用三元组实现稀疏矩阵的转置,比
较“按需查找”方法与“按位就座”方法的区别。
01290000
0000000
30000140
00240000
01800000
15007000
建议实现流程为1.矩阵2.三元组3.转置的三元组4.转置的矩阵,将3或4
打印出来。
2.做实验完成情况
实验内容在实验课时时间内完成（提前编写了大概1/2部分的代码），选做内容也完成。
本次实验内容较多，为使代码看着简洁有条理，采用了建工程的方式。
串部分：
自定义了头文件String.h:
/*自定义头文件*/
#include
#defineMAX_LEN255
typedefunsignedcharSString[MAX_LEN+1];
/*自定义函数*/
voidStrAssign（SString&T,chars[]）;//将字符串常量s赋给T
voidStrPrint（SStringT）;//打印串
voidStrCopy（SString&T,SStringS）;//串复制
voidtest（）;//检验串操作
intStrLength（SStringT）;//求串长
intStrCompare（SStringT,SStringS）;//比较串，T>S返回正值，TvoidStrConcat（SString&T,SStringS1,SStringS2）;//用T返回SString类型串S1、S2连接成的新串
voidSubString（SString&S,SStringT,intpos,intlen）;//用S返回串T中起始位置为pos，长度为len的字串
voidIndex（SStringS,SStringT,intpos[]）;//若S串中存在不重叠的子串T，则用pos[]返回所有T串的起始位置
voidStrReplace（SString&S,SStringT,SStringV）;//若串S中存在字串T，则用V替代所有不重叠的T
voidStrInsert（SString&S,intpos,SStringT）;//在串S中pos位置插入子串T
voidStrDelete（SString&S,intpos,intlen）;//在串S中pos位置删除长度为len的子串
voidGetNext（SStringS,intnext[]）;//求模式串中的next函数修正值并写入数组next[]
intFindKMP（SStringS,SStringT,intstart）;//在串S中从start位置开始，查找第一次出现模式T的位置返回，没找到返回-1
voidStrReplace2（SString&S,SStringT,SStringV）;//若串S中存在字串T，则用V替代所有不重叠的T
voidKMP（）;//KMP算法及其应用
在头文件中对所有要用到的自定义函数进行了声明，各函数的功能可见代码注释部分。
串赋值：
#include"String.h"
voidStrAssign（SString&T,chars[]）{
if（!
s）{
printf（"Error\n"）;
return;
}
inti=0;
while（s[i]!
='\0'）{
T[i]=s[i];
i++;
}
T[i]='\0';
}
该操作将字符串常量s中的元素赋值给SString类型T；
串复制：
#include"String.h"
voidStrCopy（SString&T,SStringS）{
if（!
S）{
printf（"原串为空串\n"）;
return;
}
inti=0;
while（S[i]!
='\0'）{
T[i]=S[i];
i++;
}
T[i]='\0';
}
该操作完成将SString类型T赋给SString类型S；
求串长度：
#include"String.h"
intStrLength（SStringT）{
inti=0;
while（T[i]!
='\0'）
i++;
returni;
}
该操作返回SString类型中元素的个数即串的长度；
串比较：
#include"String.h"
intStrCompare（SStringT,SStringS）{
inti;
for（i=0;T[i]!
='\0'&&S[i]!
='\0';i++）
if（S[i]!
=T[i]）
returnT[i]-S[i];
returnT[i]-S[i];
}
串连接：
#include"String.h"
voidStrConcat（SString&T,SStringS1,SStringS2）{
inti;
if（!
S1&&!
S2）{
printf（"Error\n"）;
return;
}//S1、S2均为空
if（!
S1&&S2）{
for（i=0;S2[i]!
='\0';i++）
T[i]=S2[i];
T[i]='\0';
return;
}//S1为空
if（!
S2&&S1）{
for（i=0;S1[i]!
='\0';i++）
T[i]=S1[i];
T[i]='\0';
return;
}//S2为空
for（i=0;i<=StrLength（S1）;i++）
T[i]=S1[i];
for（i=0;i<=StrLength（S2）;i++）
T[i+StrLength（S1）]=S2[i];
T[StrLength（S1）+StrLength（S2）+1]='\0';
}
此操作完成将串S1和S2连接之后赋给T；
求子串：
#include"String.h"
voidSubString（SString&S,SStringT,intpos,intlen）{
intTlen,i;
Tlen=StrLength（T）;
if（pos+len>Tlen||pos<0||pos>Tlen-1||len<0）{
printf（"Error"）;
return;
}
for（i=0;iS[i]=T[i+pos];
S[i]='\0';
}
该操作求出T串的一个子串S；
子串代替：
参考BF算法：
#include"String.h"
voidStrReplace（SString&S,SStringT,SStringV）{
intpos[20],i,Tlen;
Tlen=StrLength（T）;
for（i=0;i<20;i++）
pos[i]=1000;
Index（S,T,pos）;
for（i=0;pos[i]!
=1000;i++）{
StrDelete（S,pos[i],Tlen）;
StrInsert（S,pos[i],V）;
}
}
此方法要用到Index（）函数，此函数参考BF算法完成：
#include"String.h"
voidIndex（SStringS,SStringT,intpos[]）{
inti,j=0,Slen,Tlen,flag=0,count=0;
Slen=StrLength（S）;
Tlen=StrLength（T）;
for（i=0;i<=Slen;）{
if（S[i]==T[j]）{
flag++;
if（flag==Tlen）{
pos[count]=i-Tlen+1;
count++;
flag=0;
j=0;
i++;
}
else{
i++;
j++;
}
}
else{
flag=0;
i++;
j=0;
}
}
if（count==0）
printf（"S中没有T串\n"）;
}
参考KMP算法：
#include"String.h"
voidStrReplace2（SString&S,SStringT,SStringV）{
intstart,Tlen;
Tlen=StrLength（T）;
while（FindKMP（S,T,0）!
=-1）{
start=FindKMP（S,T,0）;
StrDelete（S,start,Tlen）;
StrInsert（S,start,V）;
}
}
此方法利用了KMP算法，需要求next[]数组；
KMP算法：
#include"String.h"
intFindKMP（SStringS,SStringT,intstart）{
inti,j=0,next[20];
GetNext（T,next）;
if（start<0||start>StrLength（S）-StrLength（T））{
return-1;
}
i=start;
while（iif（j==-1||S[i]==T[j]）{
i++;
j++;
}
else
j=next[j];
}
if（j==StrLength（T））
returni-j;
return-1;
}
KMP算法需要求next[]数组进行辅助；
Next：
#include"String.h"
voidGetNext（SStringS,intnext[]）{
intj=0,k=-1;
next[0]=-1;
while（jif（k==-1||S[j]==S[k]）{
j++;
k++;
if（S[j]!
=S[k]）
next[j]=k;
else
next[j]=next[k];
}
else
k=next[k];
}
}
此操作获得模式串改进后的next[]数组；
除此之外，我还用到了子串删除和子串插入的操作：
#include"String.h"
voidStrDelete（SString&S,intpos,intlen）{
inti;
if（pos>StrLength（S）-1||pos+len>StrLength（S）||len<0||pos<0）{
printf（"Error"）;
return;
}
for（i=pos;i<=StrLength（S）-len;i++）
S[i]=S[i+len];
}
#include"String.h"
voidStrInsert（SString&S,intpos,SStringT）{
inti,Slen,Tlen;
Slen=StrLength（S）;
Tlen=StrLength（T）;
for（i=Slen;i>=pos;i--）
S[i+Tlen]=S[i];
for（i=0;iS[pos+i]=T[i];
S[Slen+Tlen+1]='\0';
}
主函数中分别调用test（）和KMP（）用来实现对串操作的检验和对KMP算法的检验
主函数：
/*主函数*/
#include"String.h"
#include
intmain（）{
/*检验串操作的正确性*/
test（）;
/*KMP算法及其应用*/
KMP（）;
system（"pause"）;
return0;
}
Test（）：
#include"String.h"
voidtest（）{
printf（"=========================================\n"）;
printf（"TestBegain:
\n"）;
printf（"\n"）;
chars[]="abcdefgh";
intlen,r,pos[20],i;
SStringT,S,Q,P;
SStringR="abcdkhaksabcdlkjflabcd";
SStringR2="abc";
SStringR3="xyz";
StrAssign（T,s）;
StrPrint（T）;
StrCopy（S,T）;
StrPrint（S）;
len=StrLength（S）;
printf（"len=%d\n",len）;
r=StrCompare（R,T）;
printf（"r=%d\n",r）;
StrConcat（Q,T,R）;
StrPrint（Q）;
SubString（P,Q,5,10）;
StrPrint（P）;
for（i=0;i<20;i++）
pos[i]=1000;
Index（R,R2,pos）;
for（i=0;pos[i]!
=1000;i++）
printf（"pos[%d]=%d",i,pos[i]）;
printf（"\n"）;
StrDelete（R,5,6）;
StrInsert（R,4,R2）;
StrReplace（R,R2,R3）;
StrPrint（R）;
printf（"\n"）;
printf（"TestEnd!
\n"）;
printf（"=========================================\n"）;
}
KMP（）：
#include"String.h"
voidKMP（）{
printf（"KMPBegain:
\n"）;
printf（"\n"）;
SStringS1="abcabcabcd",S2="abcdababcabcdabcabcabcd",S3="cocaocoaoc";
SStringP1="abcabcd",P2="abcabcd",P3="coaoc";
SStringP="AAA";
intnext1[20],next2[20],next3[20],i,r1,r2,r3;
GetNext（P1,next1）;
for（i=0;iprintf（"next1[%d]=%d\n",i,next1[i]）;
r1=FindKMP（S1,P1,0）;
printf（"r1=%d\n",r1）;
StrReplace2（S1,P1,P）;
StrPrint（S1）;
printf（"\n"）;
GetNext（P2,next2）;
for（i=0;iprintf（"next2[%d]=%d\n",i,next2[i]）;
r1=FindKMP（S2,P2,0）;
printf（"r2=%d\n",r1）;
StrReplace2（S2,P2,P）;
StrPrint（S2）;
printf（"\n"）;
GetNext（P3,next3）;
for（i=0;iprintf（"next3[%d]=%d\n",i,next3[i]）;
r1=FindKMP（S3,P3,0）;
printf（"r3=%d\n",r1）;
StrReplace2（S3,P2,P）;
StrPrint（S3）;
printf（"\n"）;
printf（"KMPEnd!
\n"）;
printf（"=========================================\n"）;
}
实验结果：
从实验结果来看，串的各个操作成功实现。
数组部分：
自定义了头文件Array.h：
/*自定义头文件（数组）*/
#include
#defineMAX_SIZE1000
/*结构体*/
typedefintElemType;
typedefstruct{
inti,j;
ElemTypee;
}Triple;
typedefstruct{
Tripledata[MAX_SIZE];
intmu,nu,tu;
}TSMatrix;
/*自定义函数*/
voidCreateTSMatrix（TSMatrix&M,ElemTypem[][7],intr,intc）;//创建三元组
voidPrintTSMatrix（TSMatrixM）;//打印三元组
voidCreateRpos（TSMatrixM,intrpos[],intnum[]）;//求矩阵的rops数组
voidTRansposeTS（TSMatrixM,TSMatrix&T）;//将三元组顺序表压缩存储的矩阵M转置为矩阵T
在头文件中对所有要用到的自定义函数进行了声明，各函数的功能可见代码注释部分。
创建三元组：
#include"Array.h"
voidCreateTSMatrix（TSMatrix&M,ElemTypem[][7],intr,intc）{
M.mu=r;
M.nu=c;
M.tu=0;
intk,l;
for（k=0;kfor（l=0;lif（m[k][l]!
=0）{
M.data[M.tu].e=m[k][l];
M.data[M.tu].i=k;
M.data[M.tu].j=l;
M.tu++;
}
}
}
}
此操作将r*c的矩阵创建成三元组表示的矩阵TSMatrixM；
转置三元组矩阵：
#include"Array.h"
#defineMAXM100
voidTRansposeTS（TSMatrixM,TSMatrix&T）{
intp,q,col;
intnum[MAXM],rpos[MAXM];
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if（!
M.tu）
return;
CreateRpos（M,rpos,num）;
for（p=0;pcol=M.data[p].j;
q=rpos[col];
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++rpos[col];
}
}
该操作将原三元组矩阵进行转置得到新的三元组矩阵，此过程需要用到一个辅助函数以获得rpos[]数组：
#include"Array.h"
voidCreateRpos（TSMatrixM,intrpos[],intnum[]）{
intcol,t;
for（col=0;colnum[col]=0;
for（t=0;t++num[M.data[t].j];
rpos[0]=0;
for（col=1;colrpos[col]=rpos[col-1]+num[col-1];
}
为检验是否正确建立三元组矩阵以及是否成功进行了转置，需要将三元组进行打印：
#include"Array.h"
voidPrintTSMatrix（TSMatrixM）{
printf（"ije\n"）;
intk;
for（k=0;kprintf（"%d%d%d\n",M.data[k].i,M.data[k].j,M.data[k].e）;
print
升级会员 