还剩8页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第四章串
4.10voidString_ReverseStringtypesStringtyper//求s的逆串r{ StrAssignr;//初始化r为空串 fori=Strlens;i;i-- { StrAssigncSubStringsi1; StrAssignrConcatrc;//把s的字符从后往前添加到r中 }}//String_Reverse
4.11voidString_SubtractStringtypesStringtypetStringtyper//求所有包含在串s中而t中没有的字符构成的新串r{ StrAssignr; fori=1;i=Strlens;i++ { StrAssigncSubStringsi1; forj=1;jiStrComparecSubStringsj1;j++;//判断s的当前字符c是否第一次出现 ifi==j { fork=1;k=StrlentStrComparecSubStringtk1;k++;//判断当前字符是否包含在t中 ifkStrlentStrAssignrConcatrc; } }//for}//String_Subtract
4.12intReplaceStringtypeSStringtypeTStringtypeV;//将串S中所有子串T替换为V并返回置换次数{ forn=0i=1;i=StrlenS-StrlenT+1;i++//注意i的取值范围 if!StrCompareSubStringSiStrlenTT//找到了与T匹配的子串 {//分别把T的前面和后面部分保存为head和tail StrAssignheadSubStringS1i-1; StrAssigntailSubStringSi+StrlenTStrlenS-i-StrlenT+1; StrAssignSConcatheadV; StrAssignSConcatStail;//把headVtail连接为新串 i+=StrlenV;//当前指针跳到插入串以后 n++; }//if returnn;}//Replace分析:i+=StrlenV;这一句是必需的也是容易忽略的.如省掉这一句则在某些情况下会引起不希望的后果虽然在大多数情况下没有影响.请思考:设S=placeT=aceV=face则省掉i+=StrlenV;运行时会出现什么结果
4.13intDelete_SubStringStringtypesStringtypet//从串s中删除所有与t相同的子串并返回删除次数{ forn=0i=1;i=Strlens-Strlent+1;i++ if!StrCompareSubStringsiStrlentt { StrAssignheadSubStringS1i-1; StrAssigntailSubStringSi+StrlentStrlens-i-Strlent+1; StrAssignSConcatheadtail;//把headtail连接为新串 n++; }//if returnn}//Delete_SubString
4.14StatusNiBoLan_to_BoLanStringtypestrStringtypenew//把前缀表达式str转换为后缀式new{ Initstacks;//s的元素为Stringtype类型 fori=1;i=Strlenstr;i++ { r=SubStringstri1; ifr为字母pushsr; else { ifStackEmptysreturnERROR; popsa; ifStackEmptysreturnERROR; popsb; StrAssigntConcatrb; StrAssigncConcatta;//把算符r子前缀表达式ab连接为新子前缀表达式c pushsc; } }//for popsnew; if!StackEmptysreturnERROR; returnOK;}//NiBoLan_to_BoLan分析:基本思想见书后注释
3.
23.请读者用此程序取代作者早些时候对
3.23题给出的程序.
4.15voidStrAssignStringtypeTcharchars#;//用字符数组chars给串T赋值Stringtype的定义见课本{ fori=0T
[0]=0;chars[i];T
[0]++i++T[i+1]=chars[i];}//StrAssign
4.16charStrCompareStringtypesStringtypet//串的比较st时返回正数s=t时返回0st时返回负数{ fori=1;i=s
[0]i=t
[0]s[i]==t[i];i++; ifis
[0]it
[0]return0; elseifis
[0]return-t[i]; elseifit
[0]returns[i]; elsereturns[i]-t[i];}//StrCompare
4.17intString_ReplaceStringtypeSStringtypeTStringtypeV;//将串S中所有子串T替换为V并返回置换次数{ forn=0i=1;i=S
[0]-T
[0]+1;i++ { forj=ik=1;T[k]S[j]==T[k];j++k++; ifkT
[0]//找到了与T匹配的子串:分三种情况处理 { ifT
[0]==V
[0] forl=1;l=T
[0];l++//新子串长度与原子串相同时:直接替换 S[i+l-1]=V[l]; elseifT
[0]V
[0]//新子串长度大于原子串时:先将后部右移 { forl=S
[0];l=i+T
[0];l-- S[l+V
[0]-T
[0]]=S[l]; forl=1;l=V
[0];l++ S[i+l-1]=V[l]; } else//新子串长度小于原子串时:先将后部左移 { forl=i+V
[0];l=S
[0]+V
[0]-T
[0];l++ S[l]=S[l-V
[0]+T
[0]]; forl=1;l=V
[0];l++ S[i+l-1]=V[l]; } S
[0]=S
[0]-T
[0]+V
[0]; i+=V
[0];n++; }//if }//for returnn;}//String_Replace
4.18typedefstruct{ charch; intnum; }mytype;voidStrAnalyzeStringtypeS//统计串S中字符的种类和个数{ mytypeT[MAXSIZE];//用结构数组T存储统计结果 fori=1;i=S
[0];i++ { c=S[i];j=0; whileT[j].chT[j].ch!=cj++;//查找当前字符c是否已记录过 ifT[j].chT[j].num++; elseT[j]={c1}; }//for forj=0;T[j].ch;j++ printf%c: %d\nT[j].chT[j].num;}//StrAnalyze
4.19voidSubtract_StringStringtypesStringtypetStringtyper//求所有包含在串s中而t中没有的字符构成的新串r{ r
[0]=0; fori=1;i=s
[0];i++ { c=s[i]; forj=1;jis[j]!=c;j++;//判断s的当前字符c是否第一次出现 ifi==j { fork=1;k=t
[0]t[k]!=c;k++;//判断当前字符是否包含在t中 ifkt
[0]r[++r
[0]]=c; } }//for}//Subtract_String
4.20intSubString_DeleteStringtypesStringtypet//从串s中删除所有与t相同的子串并返回删除次数{ forn=0i=1;i=s
[0]-t
[0]+1;i++ { forj=1;j=t
[0]s[i+j-1]==t[i];j++; ifjm//找到了与t匹配的子串 { fork=i;k=s
[0]-t
[0];k++s[k]=s[k+t
[0]];//左移删除 s
[0]-=t
[0];n++; } }//for returnn;}//Delete_SubString
4.21typedefstruct{ charch; LStrNode*next; }LStrNode*LString;//链串结构voidStringAssignLStringsLStringt//把串t赋值给串s{ s=mallocsizeofLStrNode; forq=sp=t-next;p;p=p-next { r=LStrNode*mallocsizeofLStrNode; r-ch=p-ch; q-next=r;q=r; } q-next=NULL;}//StringAssignvoidStringCopyLStringsLStringt//把串t复制为串s.与前一个程序的区别在于串s业已存在.{ forp=s-nextq=t-next;pq;p=p-nextq=q-next { p-ch=q-ch;pre=p; } whileq { p=LStrNode*mallocsizeofLStrNode; p-ch=q-ch; pre-next=p;pre=p; } p-next=NULL;}//StringCopycharStringCompareLStringsLStringt//串的比较st时返回正数s=t时返回0st时返回负数{ forp=s-nextq=t-next;pqp-ch==q-ch;p=p-nextq=q-next; if!p!qreturn0; elseif!preturn-q-ch; elseif!qreturnp-ch; elsereturnp-ch-q-ch;}//StringCompareintStringLenLStrings//求串s的长度元素个数{ fori=0p=s-next;p;p=p-nexti++; returni;}//StringLenLString*ConcatLStringsLStringt//连接串s和串t形成新串并返回指针{ p=mallocsizeofLStrNode; forq=pr=s-next;r;r=r-next { q-next=LStrNode*mallocsizeofLStrNode; q=q-next; q-ch=r-ch; }//for//复制串s forr=t-next;r;r=r-next { q-next=LStrNode*mallocsizeofLStrNode; q=q-next; q-ch=r-ch; }//for//复制串t q-next=NULL; returnp;}//ConcatLString*Sub_StringLStringsintstartintlen//返回一个串其值等于串s从start位置起长为len的子串{ p=mallocsizeofLStrNode;q=p; forr=s;start;start--r=r-next;//找到start所对应的结点指针r fori=1;i=len;i++r=r-next { q-next=LStrNode*mallocsizeofLStrNode; q=q-next; q-ch=r-ch; }//复制串t q-next=NULL; returnp;}//Sub_String
4.22voidLString_ConcatLStringtLStringscharc//用块链存储结构把串s插入到串t的字符c之后{ p=t.head; whilep!i=Find_Charpcp=p-next;//查找字符c if!p//没找到 { t.tail-next=s.head; t.tail=s.tail;//把s连接在t的后面 } else { q=p-next; r=Chunk*mallocsizeofChunk;//将包含字符c的节点p分裂为两个 forj=0;ji;j++r-ch[j]=#;//原结点p包含c及其以前的部分 forj=i;jCHUNKSIZE;j++//新结点r包含c以后的部分 { r-ch[j]=p-ch[j]; p-ch[j]=#;//p的后半部分和r的前半部分的字符改为无效字符# } p-next=s.head; s.tail-next=r; r-next=q;//把串s插入到结点p和r之间 }//else t.curlen+=s.curlen;//修改串长 s.curlen=0;}//LString_ConcatintFind_CharChunk*pcharc//在某个块中查找字符c如找到则返回位置是第几个字符如没找到则返回0{ fori=0;iCHUNKSIZEp-ch[i]!=c;i++; ifi==CHUNKSIZEreturn0; elsereturni+1;}//Find_Char
4.23intLString_PalindromeLStringL//判断以块链结构存储的串L是否为回文序列是则返回1否则返回0{ InitStackS; p=S.head;i=0;k=1;//i指示元素在块中的下标k指示元素在整个序列中的序号从1开始 fork=1;k=S.curlen;k++ { ifk=S.curlen/2PushSp-ch[i];//将前半段的字符入串 elseifkS.curlen+1/2 { PopSc;//将后半段的字符与栈中的元素相匹配 ifp-ch[i]!=creturn0;//失配 } if++i==CHUNKSIZE//转到下一个元素当为块中最后一个元素时转到下一块 { p=p-next; i=0; } }//for return1;//成功匹配}//LString_Palindrome
4.24voidHString_ConcatHStrings1HStrings2HStringt//将堆结构表示的串s1和s2连接为新串t{ ift.chfreet.ch; t.ch=mallocs
1.length+s
2.length*sizeofchar; fori=1;i=s
1.length;i++t.ch[i-1]=s
1.ch[i-1]; forj=1;j=s
2.length;j++i++t.ch[i-1]=s
2.ch[j-1]; t.length=s
1.length+s
2.length;}//HString_Concat
4.25intHString_ReplaceHStringSHStringTHStringV//堆结构串上的置换操作返回置换次数{ forn=0i=0;i=S.length-T.length;i++ { forj=ik=0;kT.lengthS.ch[j]==T.ch[k];j++k++; ifk==T.length//找到了与T匹配的子串:分三种情况处理 { ifT.length==V.length forl=1;l=T.length;l++//新子串长度与原子串相同时:直接替换 S.ch[i+l-1]=V.ch[l-1]; elseifT.lengthV.length//新子串长度大于原子串时:先将后部右移 { forl=S.length-1;l=i+T.length;l-- S.ch[l+V.length-T.length]=S.ch[l]; forl=0;lV.length;l++ S[i+l]=V[l]; } else//新子串长度小于原子串时:先将后部左移 { forl=i+V.length;lS.length+V.length-T.length;l++ S.ch[l]=S.ch[l-V.length+T.length]; forl=0;lV.length;l++ S[i+l]=V[l]; } S.length+=V.length-T.length; i+=V.length;n++; }//if }//for returnn;}//HString_Replace
4.26StatusHString_InsertHStringSintposHStringT//把T插入堆结构表示的串S的第pos个字符之前{ ifpos1returnERROR; ifposS.lengthpos=S.length+1;//当插入位置大于串长时看作添加在串尾 S.ch=reallocS.chS.length+T.length*sizeofchar; fori=S.length-1;i=pos-1;i-- S.ch[i+T.length]=S.ch[i];//后移为插入字符串让出位置 fori=0;iT.length;i++ S.ch[pos+i-1]=T.ch[pos];//插入串T S.length+=T.length; returnOK;}//HString_Insert
4.27intIndex_NewStringtypesStringtypet//改进的定位算法{ i=1;j=1; whilei=s
[0]j=t
[0] { ifj!=1s[i]==t[j]||j==1s[i]==t[j]s[i+t
[0]-1]==t[t
[0]] {//当j==1即匹配模式串的第一个字符时需同时匹配其最后一个 i=i+j-2; j=1; } else { i++;j++; } }//while ifjt
[0]returni-t
[0];}//Index_New
4.28voidLGet_nextLStringT//链串上的get_next算法{ p=T-succ;p-next=T;q=T; whilep-succ { ifq==T||p-data==q-data { p=p-succ;q=q-succ; p-next=q; } elseq=q-next; }//while}//LGet_next
4.29LStrNode*LIndex_KMPLStringSLStringTLStrNode*pos//链串上的KMP匹配算法返回值为匹配的子串首指针{ p=pos;q=T-succ; whilepq { ifq==T||p-chdata==q-chdata { p=p-succ; q=q-succ; } elseq=q-next; }//while if!q { fori=1;i=StrlenT;i++ p=p-next; returnp; }//发现匹配后要往回找子串的头 returnNULL;}//LIndex_KMP
4.30voidGet_LRepSubStringtypeS//求S的最长重复子串的位置和长度{ formaxlen=0i=1;iS
[0];i++//串S2向右移i格 { fork=0j=1;j=S
[0]-i;j++//j为串S2的当前指针此时串S1的当前指针为i+j两指针同步移动 { ifS[j]==S[j+i]k++;//用k记录连续相同的字符数 elsek=0;//失配时k归零 ifkmaxlen//发现了比以前发现的更长的重复子串 { lrs1=j-k+1;lrs2=mrs1+i;maxlen=k;//作记录 } }//for }//for ifmaxlen { printfLongestRepeatingSubstringlength:%d\nmaxlen; printfPosition1:%d Position2:%d\nlrs1lrs2; } elseprintfNoRepeatingSubstringfound!\n;}//Get_LRepSub分析:i代表错位值.本算法的思想是依次把串S的一个副本S2向右错位平移1格2格3格...与自身S1相匹配如果存在最长重复子串则必然能在此过程中被发现.用变量lrs1lrs2maxlen来记录已发现的最长重复子串第一次出现位置第二次出现位置和长度.题目中未说明重复子串是否允许有重叠部分本算法假定允许.如不允许只需在第二个for语句的循环条件中加上k=i即可.本算法时间复杂度为OStrlenS^
2.
4.31voidGet_LPubSubStringtypeSStringtypeT//求串S和串T的最长公共子串位置和长度{ ifS
[0]=T
[0] { StrAssignAS;StrAssignBT; } else { StrAssignAT;StrAssignBS; }//为简化设计令S和T中较长的那个为A较短的那个为B formaxlen=0i=1-B
[0];iA
[0];i++ { ifi0//i为B相对于A的错位值向左为负左端对齐为0向右为正 { jmin=1;jmax=i+B
[0]; }//B有一部分在A左端的左边 elseifiA
[0]-B
[0] { jmin=i;jmax=A
[0]; }//B有一部分在A右端的右边 else { jmin=i;jmax=i+B
[0]; }//B在A左右两端之间. //以上是根据A和B不同的相对位置确定A上需要匹配的区间与B重合的区间的端点:jminjmax. fork=0j=jmin;j=jmax;j++ { ifA[j]==B[j-i]k++; elsek=0; ifkmaxlen { lps1=j-k+1;lps2=j-i-k+1;maxlen=k; } }//for }//for ifmaxlen { ifS
[0]=T
[0] { lpsS=lps1;lpsT=lps2; } else { lpsS=lps2;lpsT=lps1; }//将AB上的位置映射回ST上的位置 printfLongestPublicSubstringlength:%d\nmaxlen; printfPositioninS:%d PositioninT:%d\nlpsSlpsT; }//if elseprintfNoRepeatingSubstringfound!\n;}//Get_LPubSub分析:本题基本思路与上题同.唯一的区别是由于AB互不相同因此B不仅要向右错位而且还要向左错位以保证不漏掉一些情况.当B相对于A的位置不同时需要匹配的区间的计算公式也各不相同请读者自己画图以帮助理解.本算法的时间复杂度是o(strlrn(s)*strlen(t))。