数据结构试题库集及答案

导读:voidHString_Concat(HStrings1,HStrings2,H,intHString_Replace(HString&S,HString,严蔚敏《数据结构习题集》解答,StatusHString_Insert(HString&S,intpo,}第37页共124页if(++i==CHUNKSIZE)//转到下一个元素,当为块中最后一个元素时,转到下一块{p=p-

数据结构试题库集及答案

}

第 37 页 共 124 页

if(++i==CHUNKSIZE) //转到下一个元素,当为块中最后一个元素时,转到下一块

{

p=p->next;

i=0;

}

}//for

return 1; //成功匹配

}//LString_Palindrome

4.24

void HString_Concat(HString s1,HString s2,HString &t)//将堆结构表示的串s1 和s2 连接为新串 t

{

if(t.ch) free(t.ch);

t.ch=malloc((s1.length+s2.length)*sizeof(char));

for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1];

for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1];

t.length=s1.length+s2.length;

}//HString_Concat

4.25

int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数 {

for(n=0,i=0;i<=S.length-T.length;i++)

{

for(j=i,k=0;k<T.length&&S.ch[j]==T.ch[k];j++,k++);

if(k==T.length) //找到了与T 匹配的子串:分三种情况处理

{

if(T.length==V.length)

for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换

S.ch[i+l-1]=V.ch[l-1];

else if(T.length<V.length) //新子串长度大于原子串时:先将后部右移

{

for(l=S.length-1;l>=i+T.length;l--)

S.ch[l+V.length-T.length]=S.ch[l];

for(l=0;l<V.length;l++)

S[i+l]=V[l];

}

else //新子串长度小于原子串时:先将后部左移

{

for(l=i+V.length;l<S.length+V.length-T.length;l++)

S.ch[l]=S.ch[l-V.length+T.length];

for(l=0;l<V.length;l++)

S[i+l]=V[l];

严蔚敏《数据结构习题集》解答

}

S.length+=V.length-T.length;

i+=V.length;n++;

}//if

}//for

return n;

}//HString_Replace

4.26

第 38 页 共 124 页

Status HString_Insert(HString &S,int pos,HString T)//把T 插入堆结构表示的串S 的第pos 个字 符之前

{

if(pos<1) return ERROR;

if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾

S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char));

for(i=S.length-1;i>=pos-1;i--)

S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置

for(i=0;i<T.length;i++)

S.ch[pos+i-1]=T.ch[pos]; //插入串T

S.length+=T.length;

return OK;

}//HString_Insert

4.27

int Index_New(Stringtype s,Stringtype t)//改进的定位算法

{

i=1;j=1;

while(i<=s[0]&&j<=t[0])

{

if((j!=1&&s[i]==t[j])||(j==1&&s[i]==t[j]&&s[i+t[0]-1]==t[t[0]]))

{ //当j==1 即匹配模式串的第一个字符时,需同时匹配其最后一个

i=i+j-2;

j=1;

}

else

{

i++;j++;

}

}//while

if(j>t[0]) return i-t[0];

}//Index_New

4.28

void LGet_next(LString &T)//链串上的get_next 算法

{

p=T->succ;p->next=T;q=T;

while(p->succ)

严蔚敏《数据结构习题集》解答

{

if(q==T||p->data==q->data)

{

p=p->succ;q=q->succ;

p->next=q;

}

else q=q->next;

}//while

}//LGet_next

4.29

第 39 页 共 124 页

LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)//链串上的KMP 匹配算法,返回 值为匹配的子串首指针

{

p=pos;q=T->succ;

while(p&&q)

{

if(q==T||p->chdata==q->chdata)

{

p=p->succ;

q=q->succ;

}

else q=q->next;

}//while

if(!q)

{

for(i=1;i<=Strlen(T);i++)

p=p->next;

return p;

} //发现匹配后,要往回找子串的头

return NULL;

}//LIndex_KMP

4.30

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

{

for(maxlen=0,i=1;i<S[0];i++)//串S2 向右移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("Longest Repeating Substring length:%d\n",maxlen);

printf("Position1:%d Position 2:%d\n",lrs1,lrs2);

}

else printf("No Repeating Substring found!\n");

}//Get_LRepSub

第 40 页 共 124 页

分析: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<A[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;

五星文库wxphp.com包含总结汇报、办公文档、IT计算机、考试资料、文档下载、党团工作、资格考试、教程攻略、计划方案、教学研究以及数据结构试题库集及答案等内容。

本文共54页1<<31323334353637>>54