严蔚敏版数据结构C语言版参考答案第五章(4)

void Get_LRepSub(Stringtype S)//求S的最长重复子串的位置和长度 {

for(maxlen=0,i=1;i

for(k=0,j=1;j<=S[0]-i;j++)//j为串S2的当前指针,此时串S1的当前指针为i+j,两指针同步移动 {

if(S[j]==S[j+i]) k++; //用k记录连续相同的字符数 else k=0; //失配时k归零

if(k>maxlen) //发现了比以前发现的更长的重复子串 {

lrs1=j-k+1;lrs2=mrs1+i;maxlen=k; //作记录 } }//for }//for

if(maxlen) {

printf(\ printf(\ }

else printf(\}//Get_LRepSub

分析:i代表\错位值\本算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明\重复子串\是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2). 4.31

void Get_LPubSub(Stringtype S,Stringtype T)//求串S和串T的最长公共子串位置和长度 {

if(S[0]>=T[0]) {

StrAssign(A,S);StrAssign(B,T); } else {

StrAssign(A,T);StrAssign(B,S);

} //为简化设计,令S和T中较长的那个为A,较短的那个为B for(maxlen=0,i=1-B[0];i

if(i<0) //i为B相对于A的错位值,向左为负,左端对齐为0,向右为正 {

jmin=1;jmax=i+B[0];

}//B有一部分在A左端的左边

else if(i>A[0]-B[0]) {

jmin=i;jmax=A[0];

}//B有一部分在A右端的右边 else {

jmin=i;jmax=i+B[0]; }//B在A左右两端之间.

//以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax.

for(k=0,j=jmin;j<=jmax;j++) {

if(A[j]==B[j-i]) k++; else k=0; if(k>maxlen) {

lps1=j-k+1;lps2=j-i-k+1;maxlen=k; } }//for }//for

if(maxlen) {

if(S[0]>=T[0]) {

lpsS=lps1;lpsT=lps2; } else {

lpsS=lps2;lpsT=lps1;

} //将A,B上的位置映射回S,T上的位置

printf(\ printf(\ }//if

else printf(\}//Get_LPubSub

分析:本题基本思路与上题同.唯一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。

第五章 数组和广义表

5.18

void RSh(int A[n],int k)//把数组A的元素循环右移k位,只用一个辅助存储空间 {

for(i=1;i<=k;i++)

if(n%i==0&&k%i==0) p=i;//求n和k的最大公约数p for(i=0;i

j=i;l=(i+k)%n;temp=A[i]; while(l!=i) {

A[j]=temp; temp=A[l]; A[l]=A[j]; j=l;l=(j+k)%n; }// 循环右移一步 A[i]=temp; }//for }//RSh

分析:要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个\循环链\上面.举例如下:

n=15,k=6,则p=3.

第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]. 第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1]. 第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2]. 恰好使所有元素都右移一次.

虽然未经数学证明,但作者相信上述规律应该是正确的. 5.19

void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点 {

for(i=0;i

for(min=A[i][0],j=0;j

if(A[i][j]

for(j=0;j

if(A[i][j]==min) //判断这个(些)最小值是否鞍点 {

for(flag=1,k=0;k printf(\ } }//for

}//Get_Saddle

5.20

本题难度极大,故仅探讨一下思路.这一题的难点在于,在多项式的元数m未知的情况下,如何按照降幂次序输出各项.可以考虑采取类似于层序遍历的思想,从最高次的项开始,依次对其每一元的次数减一,入一个队列.附设访问标志visited以避免重复. 5.21

void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法 {

C.mu=A.mu;C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1;

for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 {

while(A.data[pa].i

while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 {

if(A.data[pa].j==B.data[pb].j) {

ce=A.data[pa].e+B.data[pb].e; if(ce) //和不为0 {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=ce; pa++;pb++;pc++; } }//if

else if(A.data[pa].j>B.data[pb].j) {

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } else

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; }

}//while

while(A.data[pa]==x) //插入A中剩余的元素(第x行) {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; }

while(B.data[pb]==x) //插入B中剩余的元素(第x行) {

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } }//for C.tu=pc;

}//TSMatrix_Add 5.22

void TSMatrix_Addto(TSMatrix &A,TSMatrix B)//将三元组矩阵B加到A上 {

for(i=1;i<=A.tu;i++)

A.data[MAXSIZE-A.tu+i]=A.data[i];/把A的所有元素都移到尾部以腾出位置 pa=MAXSIZE-A.tu+1;pb=1;pc=1;

for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 {

while(A.data[pa].i

while(A.data[pa].i==x&&B …… 此处隐藏：1762字，全部文档内容请下载后查看。喜欢就下载吧 ……