📄 xtjd4.htm
字号:
r=(LStrNode*)malloc(sizeof(LStrNode));<br>
r->ch=p->ch;<br>
q->next=r;q=r;<br>
}<br>
q->next=NULL;<br>
}//StringAssign
<p>void StringCopy(LString &s,LString t)//把串t复制为串s.与前一个程序的区别在于,串s业已存在.<br>
{<br>
for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next)<br>
{<br>
p->ch=q->ch;pre=p;<br>
}<br>
while(q)<br>
{<br>
p=(LStrNode*)malloc(sizeof(LStrNode));<br>
p->ch=q->ch;<br>
pre->next=p;pre=p;<br>
}<br>
p->next=NULL;<br>
}//StringCopy
<p>char StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数<br>
{<br>
for(p=s->next,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next);<br>
if(!p&&!q) return 0;<br>
else if(!p) return -(q->ch);<br>
else if(!q) return p->ch;<br>
else return p->ch-q->ch;<br>
}//StringCompare
<p>int StringLen(LString s)//求串s的长度(元素个数)<br>
{<br>
for(i=0,p=s->next;p;p=p->next,i++);<br>
return i;<br>
}//StringLen
<p>LString * Concat(LString s,LString t)//连接串s和串t形成新串,并返回指针<br>
{<br>
p=malloc(sizeof(LStrNode));<br>
for(q=p,r=s->next;r;r=r->next)<br>
{<br>
q->next=(LStrNode*)malloc(sizeof(LStrNode));<br>
q=q->next;<br>
q->ch=r->ch;<br>
}//for //复制串s<br>
for(r=t->next;r;r=r->next)<br>
{<br>
q->next=(LStrNode*)malloc(sizeof(LStrNode));<br>
q=q->next;<br>
q->ch=r->ch;<br>
}//for //复制串t<br>
q->next=NULL;<br>
return p;<br>
}//Concat
<p>LString * Sub_String(LString s,int start,int len)//返回一个串,其值等于串s从start位置起长为len的子串<br>
{<br>
p=malloc(sizeof(LStrNode));q=p;<br>
for(r=s;start;start--,r=r->next); //找到start所对应的结点指针r<br>
for(i=1;i<=len;i++,r=r->next)<br>
{<br>
q->next=(LStrNode*)malloc(sizeof(LStrNode));<br>
q=q->next;<br>
q->ch=r->ch;<br>
} //复制串t<br>
q->next=NULL;<br>
return p;<br>
}//Sub_String
<p>4.22
<p>4.23
<p>书后对这两题给出了一些提示.由于作者对这些提示的可行性感到困惑,或者尚没有完全理解其意图,致使无法给出参考算法.请读者认真思考后自行写出,欢迎发表你的解答.
<p>4.24
<p>void HString_Concat(HString s1,HString s2,HString &t)//将堆结构表示的串s1和s2连接为新串t<br>
{<br>
if(t.ch) free(t.ch);<br>
t.ch=malloc((s1.length+s2.length)*sizeof(char));<br>
for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1];<br>
for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1];<br>
t.length=s1.length+s2.length;<br>
}//HString_Concat
<p>4.25
<p>int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数<br>
{<br>
for(n=0,i=0;i<=S.length-T.length;i++)<br>
{<br>
for(j=i,k=0;k<T.length&&S.ch[j]==T.ch[k];j++,k++);<br>
if(k==T.length) //找到了与T匹配的子串:分三种情况处理<br>
{<br>
if(T.length==V.length)<br>
for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换<br>
S.ch[i+l-1]=V.ch[l-1];<br>
else if(T.length<V.length) //新子串长度大于原子串时:先将后部右移<br>
{<br>
for(l=S.length-1;l>=i+T.length;l--)<br>
S.ch[l+V.length-T.length]=S.ch[l];<br>
for(l=0;l<V.length;l++)<br>
S[i+l]=V[l];<br>
}<br>
else //新子串长度小于原子串时:先将后部左移<br>
{<br>
for(l=i+V.length;l<S.length+V.length-T.length;l++)<br>
S.ch[l]=S.ch[l-V.length+T.length];<br>
for(l=0;l<V.length;l++)<br>
S[i+l]=V[l];<br>
}<br>
S.length+=V.length-T.length;<br>
i+=V.length;n++;<br>
}//if<br>
}//for<br>
return n;<br>
}//HString_Replace
<p>4.26
<p>Status HString_Insert(HString &S,int pos,HString T)//把T插入堆结构表示的串S的第pos个字符之前<br>
{<br>
if(pos<1) return ERROR;<br>
if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾<br>
S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char));<br>
for(i=S.length-1;i>=pos-1;i--)<br>
S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置<br>
for(i=0;i<T.length;i++)<br>
S.ch[pos+i-1]=T.ch[pos]; //插入串T<br>
S.length+=T.length;<br>
return OK;<br>
}//HString_Insert
<p>4.27
<p>int Index_New(Stringtype s,Stringtype t)//改进的定位算法<br>
{<br>
i=1;j=1;<br>
while(i<=s[ 0 ]&&j<=t[ 0 ])<br>
{<br>
if((j!=1&&s[i]==t[j])||(j==1&&s[i]==t[j]&&s[i+t[
0 ]-1]==t[t[ 0 ]]))<br>
{ //当j==1即匹配模式串的第一个字符时,需同时匹配其最后一个<br>
i=i+j-2;<br>
j=1;<br>
}<br>
else<br>
{<br>
i++;j++;<br>
}<br>
}//while<br>
if(j>t[ 0 ]) return i-t[ 0 ];<br>
}//Index_New
<p>4.28
<p>void Lget_next(LString &T)//链串上的get_next算法<br>
{<br>
p=T->succ;p->next=T;q=T;<br>
while(p->succ)<br>
{<br>
if(q==T||p->data==q->data)<br>
{<br>
p=p->succ;q=q->succ;<br>
p->next=q;<br>
}<br>
else q=q->next;<br>
}//while<br>
}//Lget_next
<p>4.29
<p>LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)//链串上的KMP匹配算法,返回值为指针<br>
{<br>
p=pos;q=T->succ;<br>
while(p&&q)<br>
{<br>
if(q==T||p->chdata==q->chdata)<br>
{<br>
p=p->succ;<br>
q=q->succ;<br>
}<br>
else q=q->next;<br>
}//while<br>
if(!q)<br>
{<br>
for(i=1;i<=Strlen(T);i++)<br>
p=p->next;<br>
return p;<br>
} //发现匹配后,要往回找子串的头<br>
return NULL;<br>
}//LIndex_KMP
<p>4.30
<p>void Get_LRepSub(Stringtype S)//求S的最长重复子串的位置和长度<br>
{<br>
for(maxlen=0,i=1;i<S[ 0 ];i++)//串S2向右移i格<br>
{<br>
for(k=0,j=1;j<=S[ 0 ]-i;j++)//j为串S2的当前指针,此时串S1的当前指针为i+j,两指针同步移动<br>
{<br>
if(S[j]==S[j+i]) k++; //用k记录连续相同的字符数<br>
else k=0; //失配时k归零<br>
if(k>maxlen) //发现了比以前发现的更长的重复子串<br>
{<br>
lrs1=j-k+1;lrs2=mrs1+i;maxlen=k;
//作记录<br>
}<br>
}//for<br>
}//for<br>
if(maxlen)<br>
{<br>
printf("Longest Repeating Substring length:%d\n",maxlen);<br>
printf("Position1:%d Position
2:%d\n",lrs1,lrs2);<br>
}<br>
else printf("No Repeating Substring found!\n");<br>
}//Get_LRepSub<br>
分析:i代表"错位值".本算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).
<p>4.31
<p>void Get_LPubSub(Stringtype S,Stringtype T)//求串S和串T的最长公共子串位置和长度<br>
{<br>
if(S[ 0 ]>=T[ 0 ])<br>
{<br>
StrAssign(A,S);StrAssign(B,T);<br>
}<br>
else<br>
{<br>
StrAssign(A,T);StrAssign(B,S);<br>
} //为简化设计,令S和T中较长的那个为A,较短的那个为B<br>
for(maxlen=0,i=1-B[ 0 ];i<A[ 0 ];i++)<br>
{<br>
if(i<0) //i为B相对于A的错位值,向左为负,左端对齐为0,向右为正<br>
{<br>
jmin=1;jmax=i+B[ 0 ];<br>
}//B有一部分在A左端的左边<br>
else if(i>A[ 0 ]-B[ 0 ])<br>
{<br>
jmin=i;jmax=A[ 0 ];<br>
}//B有一部分在A右端的右边<br>
else<br>
{<br>
jmin=i;jmax=i+B[ 0 ];<br>
}//B在A左右两端之间.<br>
//以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax.<br>
for(k=0,j=jmin;j<=jmax;j++)<br>
{<br>
if(A[j]==B[j-i]) k++;<br>
else k=0;<br>
if(k>maxlen)<br>
{<br>
lps1=j-k+1;lps2=j-i-k+1;maxlen=k;<br>
}<br>
}//for<br>
}//for<br>
if(maxlen)<br>
{<br>
if(S[ 0 ]>=T[ 0 ])<br>
{<br>
lpsS=lps1;lpsT=lps2;<br>
}<br>
else<br>
{<br>
lpsS=lps2;lpsT=lps1;<br>
} //将A,B上的位置映射回S,T上的位置<br>
printf("Longest Public Substring length:%d\n",maxlen);<br>
printf("Position in S:%d Position in
T:%d\n",lpsS,lpsT);<br>
}//if<br>
else printf("No Repeating Substring found!\n");<br>
}//Get_LPubSub<br>
分析:本题基本思路与上题同.唯一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。</p>
<p align="left" style="line-height: 100%; margin-top: 0; margin-bottom: 0"> </p>
<HR>
<P align=left><B><SPAN
style="COLOR: blue; FONT-FAMILY: 宋体; FONT-SIZE: 24pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">数据结构辅导站</SPAN><SPAN
lang=EN-US
style="COLOR: blue; FONT-FAMILY: Times New Roman; FONT-SIZE: 24pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-spacerun: yes; mso-fareast-font-family: 宋体">
</SPAN></B><span lang="EN-US" style="font-size:10.5pt;mso-bidi-font-size:12.0pt;font-family:宋体;
mso-bidi-font-family:"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:
EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"><a href="index.htm">返回主页</a></span></P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -