版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領
文檔簡介
1、第四章 串 4.10 void String_Reverse(Stringtype s,Stringtype &r)/求s的逆串r StrAssign(r,''); /初始化r為空串 for(i=Strlen(s);i;i-) StrAssign(c,SubString(s,i,1); StrAssign(r,Concat(r,c); /把s的字符從后往前添加到r中 /String_Reve
2、rse 4.11 void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)/求所有包含在串s中而t中沒有的字符構(gòu)成的新串r StrAssign(r,''); for(i=1;i<=Strlen(s);i+) StrAssign(c,SubString(s,i,1); for(j=1;j<i&&StrCompare(c,S
3、ubString(s,j,1);j+); /判斷s的當前字符c是否第一次出現(xiàn) if(i=j) for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1);k+); /判斷當前字符是否包含在t中 if(k>Strlen(t) StrAssign(r,Concat(r,c);
4、; /for/String_Subtract 4.12 int Replace(Stringtype &S,Stringtype T,Stringtype V);/將串S中所有子串T替換為V,并返回置換次數(shù) for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i+) /注意i的取值范圍 if(!StrCompare(SubString(S,i,Strlen(T),T) /找到了與T匹配的子串 /分別
5、把T的前面和后面部分保存為head和tail StrAssign(head,SubString(S,1,i-1); StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1); StrAssign(S,Concat(head,V); StrAssign
6、(S,Concat(S,tail); /把head,V,tail連接為新串 i+=Strlen(V); /當前指針跳到插入串以后 n+; /if return n;/Replace分析:i+=Strlen(V);這一句是必需的,也是容易忽略的.如省掉這一句,則在某些情況下,會引起不希望的后果,雖然在大多數(shù)情況下沒有影響.請思考:設S='place', T='ace&
7、#39;, V='face',則省掉i+=Strlen(V);運行時會出現(xiàn)什么結(jié)果? 4.13 int Delete_SubString(Stringtype &s,Stringtype t)/從串s中刪除所有與t相同的子串,并返回刪除次數(shù) for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i+) if(!StrCompare(SubString(s,i,Strlen(t),t)
8、 StrAssign(head,SubString(S,1,i-1); StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1); StrAssign(S,Concat(head,tail); /把head,tail連接為新串 n+; /if
9、; return n,/Delete_SubString 4.14 Status NiBoLan_to_BoLan(Stringtype str,Stringtype &new)/把前綴表達式str轉(zhuǎn)換為后綴式new Initstack(s); /s的元素為Stringtype類型 for(i=1;i<=Strlen(str);i+) r=SubString(str,i,1); if(r為字母) push(s,r
10、); else if(StackEmpty(s) return ERROR; pop(s,a); if(StackEmpty(s) return ERROR; pop(s,b);
11、 StrAssign(t,Concat(r,b); StrAssign(c,Concat(t,a); /把算符r,子前綴表達式a,b連接為新子前綴表達式c push(s,c); /for pop(s,new); if(!StackEmpty(s) return ERROR; 4.15 void Str
12、Assign(Stringtype &T,char chars&#;)/用字符數(shù)組chars給串T賦值,Stringtype的定義見課本 for(i=0,T0=0;charsi;T0+,i+) Ti+1=charsi;/StrAssign 4.16 char StrCompare(Stringtype s,Stringtype t)/串的比較,s>t時返回正數(shù),s=t時返回0,s<t時返回負數(shù) for(i=1;i<=s0&&i<=t0&&si=ti;i+);
13、;if(i>s0&&i>t0) return 0; else if(i>s0) return -ti; else if(i>t0) return si; else return si-ti;/StrCompare 4.17 int String_Replace(Stringtype &S,Stringtype T,Stringtype V);/將串S中所有子串T替換為V,并返回置換次數(shù) for(n=0,i=1;i<=S0-T0+1;i+)
14、160; for(j=i,k=1;Tk&&Sj=Tk;j+,k+); if(k>T0) /找到了與T匹配的子串:分三種情況處理 if(T0=V0) for(l=1;l<=T0;l+) /新子串長度與原子串相同時:直接替換
15、 Si+l-1=Vl; else if(T0<V0) /新子串長度大于原子串時:先將后部右移 for(l=S0;l>=i+T0;l-) Sl+V0-T0=Sl;
16、160; for(l=1;l<=V0;l+) Si+l-1=Vl; else /新子串長度小于原子串時:先將后部左移
17、160; for(l=i+V0;l<=S0+V0-T0;l+) Sl=Sl-V0+T0; for(l=1;l<=V0;l+) Si+l-1=Vl;
18、60; S0=S0-T0+V0; i+=V0;n+; /if /for return n;/String_Replace 4.18 typedef struct char ch;
19、; int num; mytype;void StrAnalyze(Stringtype S)/統(tǒng)計串S中字符的種類和個數(shù) mytype TMAXSIZE; /用結(jié)構(gòu)數(shù)組T存儲統(tǒng)計結(jié)果 for(i=1;i<=S0;
20、i+) c=Si;j=0; while(Tj.ch&&Tj.ch!=c) j+; /查找當前字符c是否已記錄過 if(Tj.ch) Tj.num+; else Tj=c,1; /for for(j=0;Tj.ch;j+) printf("%c: %dn&
21、quot;,Tj.ch,Tj.num);/StrAnalyze 4.19 void Subtract_String(Stringtype s,Stringtype t,Stringtype &r)/求所有包含在串s中而t中沒有的字符構(gòu)成的新串r r0=0; for(i=1;i<=s0;i+) c=si; for(j=1;j<i&&sj!=c;j+); /判斷s的當前字符c是否第一次出現(xiàn)
22、160; if(i=j) for(k=1;k<=t0&&tk!=c;k+); /判斷當前字符是否包含在t中 if(k>t0) r+r0=c; /for/Subtract_String 4.20int SubString_Delete(Stringtype &s,Stringtype
23、t)/從串s中刪除所有與t相同的子串,并返回刪除次數(shù) for(n=0,i=1;i<=s0-t0+1;i+) for(j=1;j<=t0&&si+j-1=ti;j+); if(j>m) /找到了與t匹配的子串 for(k=i;k<=s0-t0;k+) sk=sk+t0; /左移刪除
24、 s0-=t0;n+; /for return n;/Delete_SubString 4.21 typedef struct char ch;
25、0; LStrNode *next; LStrNode,*LString; /鏈串結(jié)構(gòu) void StringAssign(LString &s,LString t)/把串t賦值給串s s=malloc(sizeof(LStrNode); for(q=s,p=t->next;p;p=p->next)
26、; r=(LStrNode*)malloc(sizeof(LStrNode); r->ch=p->ch; q->next=r;q=r; q->next=NULL;/StringAssign void StringCopy(LString &s,LString t)/把串t復制為串s.與前一個程序的區(qū)別在于,串s業(yè)已存在. for(p=s->n
27、ext,q=t->next;p&&q;p=p->next,q=q->next) p->ch=q->ch;pre=p; while(q) p=(LStrNode*)malloc(sizeof(LStrNode); p->ch=q->ch; pre->next=
28、p;pre=p; p->next=NULL;/StringCopy char StringCompare(LString s,LString t)/串的比較,s>t時返回正數(shù),s=t時返回0,s<t時返回負數(shù) for(p=s->next,q=t->next;p&&q&&p->ch=q->ch;p=p->next,q=q->next); if(!p&&!q) return 0; els
29、e if(!p) return -(q->ch); else if(!q) return p->ch; else return p->ch-q->ch;/StringCompare int StringLen(LString s)/求串s的長度(元素個數(shù)) for(i=0,p=s->next;p;p=p->next,i+); return i;/StringLen LString * Concat(LString s,LString t)/連接串s和串t形成新串,并返回指
30、針 p=malloc(sizeof(LStrNode); for(q=p,r=s->next;r;r=r->next) q->next=(LStrNode*)malloc(sizeof(LStrNode); q=q->next; q->ch=r->ch; /for /復制串s for(r=t->next;r
31、;r=r->next) q->next=(LStrNode*)malloc(sizeof(LStrNode); q=q->next; q->ch=r->ch; /for /復制串t q->next=NULL; return p;/Concat LString * Sub_String(LString s,int start,int l
32、en)/返回一個串,其值等于串s從start位置起長為len的子串 p=malloc(sizeof(LStrNode);q=p; for(r=s;start;start-,r=r->next); /找到start所對應的結(jié)點指針r for(i=1;i<=len;i+,r=r->next) q->next=(LStrNode*)malloc(sizeof(LStrNode); q=q->
33、next; q->ch=r->ch; /復制串t q->next=NULL; return p;/Sub_String 4.22 void LString_Concat(LString &t,LString &s,char c)/用塊鏈存儲結(jié)構(gòu),把串s插入到串t的字符c之后 p=t.head; while(p&&!(i=Find_Char(p,c) p=p->next; /查找字符c
34、 if(!p) /沒找到 t.tail->next=s.head; t.tail=s.tail; /把s連接在t的后面 else q=p->next; r=(Chunk*)malloc(sizeof(Chunk); /將包含字符c的節(jié)點p分裂為兩個
35、160;for(j=0;j<i;j+) r->chj='#' /原結(jié)點p包含c及其以前的部分 for(j=i;j<CHUNKSIZE;j+) /新結(jié)點r包含c以后的部分 r->chj=p->chj; p->chj='#' /p的后半部分和r的前半部分的字符改為無效字符'#'
36、0; p->next=s.head; s.tail->next=r; r->next=q; /把串s插入到結(jié)點p和r之間 /else t.curlen+=s.curlen; /修改串長 s.curlen=0;/LString_Concat int Find_Char(Chunk *p,char c)/在某個塊中查找字符c,如找到則返回位置是
37、第幾個字符,如沒找到則返回0 for(i=0;i<CHUNKSIZE&&p->chi!=c;i+); if(i=CHUNKSIZE) return 0; else return i+1;/Find_Char4.23 int LString_Palindrome(LString L)/判斷以塊鏈結(jié)構(gòu)存儲的串L是否為回文序列,是則返回1,否則返回0 InitStack(S); p=S.head;i=0;k=1; /i指示元素在塊中的下標,k指示元素在整個序列中的
38、序號(從1開始) for(k=1;k<=S.curlen;k+) if(k<=S.curlen/2) Push(S,p->chi); /將前半段的字符入串 else if(k>(S.curlen+1)/2) Pop(S,c); /將后半段的字符與棧中的元素相匹配
39、; if(p->chi!=c) return 0; /失配 if(+i=CHUNKSIZE) /轉(zhuǎn)到下一個元素,當為塊中最后一個元素時,轉(zhuǎn)到下一塊 p=p->next; i=0; /for return
40、1; /成功匹配/LString_Palindrome4.24 void HString_Concat(HString s1,HString s2,HString &t)/將堆結(jié)構(gòu)表示的串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.chi-1=s1.chi-1; for(j=1;j<=s2.length;j+,i+) t
41、.chi-1=s2.chj-1; t.length=s1.length+s2.length;/HString_Concat 4.25 int HString_Replace(HString &S,HString T,HString V)/堆結(jié)構(gòu)串上的置換操作,返回置換次數(shù) for(n=0,i=0;i<=S.length-T.length;i+) for(j=i,k=0;k<T.length&&S.chj=T.chk;j+,k+);
42、160; if(k=T.length) /找到了與T匹配的子串:分三種情況處理 if(T.length=V.length) for(l=1;l<=T.length;l+) /新子串長度與原子串相同時:直接替換 S.chi+l-1=V.chl-
43、1; else if(T.length<V.length) /新子串長度大于原子串時:先將后部右移 for(l=S.length-1;l>=i+T.length;l-) S.chl+V.length-T.length=S.chl;
44、160; for(l=0;l<V.length;l+) Si+l=Vl; else /新子串長度小于原子串時:先將后部左移
45、; for(l=i+V.length;l<S.length+V.length-T.length;l+) S.chl=S.chl-V.length+T.length; for(l=0;l<V.length;l+) Si+l=V
46、l; S.length+=V.length-T.length; i+=V.length;n+; /if /for return n;/HString_Replace 4.26 Status HString_Insert(HString &S,int pos,HString T)/把T插入堆
47、結(jié)構(gòu)表示的串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.chi+T.length=S.chi; /后移為插入字符串讓出位置 f
48、or(i=0;i<T.length;i+) S.chpos+i-1=T.chpos; /插入串T S.length+=T.length; return OK;/HString_Insert 4.27 int Index_New(Stringtype s,Stringtype t)/改進的定位算法 i=1;j=1; while(i<=s0&&j<=t0) if(
49、j!=1&&si=tj)|(j=1&&si=tj&&si+t0-1=tt0) /當j=1即匹配模式串的第一個字符時,需同時匹配其最后一個 i=i+j-2; j=1; else
50、 i+;j+; /while if(j>t0) return i-t0;/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) &
51、#160; p=p->succ;q=q->succ; p->next=q; else q=q->next; /while/LGet_next 4.29 LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)/鏈串上的KMP匹配算法,返回值
52、為匹配的子串首指針 p=pos;q=T->succ; while(p&&q) if(q=T|p->chdata=q->chdata) p=p->succ; q=q->succ;
53、160; else q=q->next; /while if(!q) for(i=1;i<=Strlen(T);i+) p=p->next; return p; /發(fā)現(xiàn)匹配后,要往回找子串的頭 return NULL;/LIndex_KMP 4.30 void Get_LRepSub(Strin
54、gtype S)/求S的最長重復子串的位置和長度 for(maxlen=0,i=1;i<S0;i+)/串S2向右移i格 for(k=0,j=1;j<=S0-i;j+)/j為串S2的當前指針,此時串S1的當前指針為i+j,兩指針同步移動 if(Sj=Sj+i) k+; /用k記錄連續(xù)相同的字符數(shù) else k
55、=0; /失配時k歸零 if(k>maxlen) /發(fā)現(xiàn)了比以前發(fā)現(xiàn)的更長的重復子串 lrs1=j-k+1;lrs2=mrs1+i;maxlen=k; /作記錄 /for /for if(maxl
56、en) printf("Longest Repeating Substring length:%dn",maxlen); printf("Position1:%d Position 2:%dn",lrs1,lrs2); else printf("No Repeating Substring found!n");/Get_LRepSub分析:i代表&quo
57、t;錯位值".本算法的思想是,依次把串S的一個副本S2向右錯位平移1格,2格,3格,.與自身S1相匹配,如果存在最長重復子串,則必然能在此過程中被發(fā)現(xiàn).用變量lrs1,lrs2,maxlen來記錄已發(fā)現(xiàn)的最長重復子串第一次出現(xiàn)位置,第二次出現(xiàn)位置和長度.題目中未說明"重復子串"是否允許有重疊部分,本算法假定允許.如不允許,只需在第二個for語句的循環(huán)條件中加上k<=i即可.本算法時間復雜度為O(Strlen(S)2). 4.31 void Get_LPubSub(Stringtype S,Stringtype T)/求串S和串T的最長公共子串位置和長度 if(S0>=T0) StrAssign(A,S);StrAssign(B
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 山東省濟寧市2023-2024學年六年級下學期期末考試英語試卷
- 第一中學學校安全管理制度
- 24.1.2 垂直于弦的直徑 人教版數(shù)學九年級上冊堂堂練(含答案)
- 貴州省2023-2024學年高三下學期高考模擬預測信息卷語文一(解析版)
- 關(guān)于民族特色酒館的問卷調(diào)查
- 電商行業(yè)的消費者滿意度影響因素實踐研究
- 股權(quán)結(jié)構(gòu)對公司財務透明度的提升作用研究分析
- 江蘇省南京市鼓樓實驗中學2024屆中考數(shù)學考試模擬沖刺卷含解析
- 綠色建筑科技行業(yè)經(jīng)營模式分析
- 廢舊橡膠回收利用行業(yè)的消費市場分析
- 名著導讀鋼鐵是怎樣煉成的教學設計 人教版
- 2024年內(nèi)蒙古呼和浩特市中考英語試卷真題(含答案解析)
- 小學體育跨學科主題學習教學設計:小小志愿軍
- 2024年時事政治試題(有答案)
- 人教版八年級歷史上冊 第一、二單元 單元測試卷( 2024年秋)
- DZ/T 0462.5-2023 礦產(chǎn)資源“三率”指標要求 第5部分:金、銀、鈮、鉭、鋰、鋯、鍶、稀土、鍺(正式版)
- 獸醫(yī)檢驗題庫與答案
- 【海天味業(yè)公司人才激勵機制現(xiàn)狀、問題及優(yōu)化建議(含問卷)15000字(論文)】
- 2022年度食品安全負責人考試題庫(含答案)
- GB/T 30987-2020植物中游離氨基酸的測定
- FMEA第五版實例
評論
0/150
提交評論