中國科大數(shù)據(jù)結(jié)構(gòu)-中科大繼續(xù)教育學(xué)院(編輯修改稿)
2025-03-17 14:41 本頁面
【文章內(nèi)容簡介】 存儲(chǔ) 順序串上的插入和刪除操作極不方便，需要移動(dòng)大量的字符。因此，我們可用單鏈表方式來存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈串，如下圖所示。 a b c ds e f結(jié)點(diǎn)大小為 1的鏈串 s 413 中國科大《數(shù)據(jù)結(jié)構(gòu)》 串的存儲(chǔ)結(jié)構(gòu) ? 鏈串的類型描述 ： typedef struct node { char ch。 struct node *next。 //next為指向結(jié)點(diǎn)的指針 } LString。 LString s。 //定義一個(gè)串變量 s 一個(gè)鏈串由頭指針惟一確定。 這種結(jié)構(gòu)便于進(jìn)行插入和刪除運(yùn)算，但存儲(chǔ)空間利用率太低。 414 中國科大《數(shù)據(jù)結(jié)構(gòu)》 串的存儲(chǔ)結(jié)構(gòu) 為了提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。如圖所示，通常將結(jié)點(diǎn)數(shù)據(jù)域存放的字符個(gè)數(shù)定義為結(jié)點(diǎn)的大小，顯然，當(dāng)結(jié)點(diǎn)大小大于 1時(shí)，串的長度不一定正好是結(jié)點(diǎn)的整數(shù)倍，因此要用特殊字符來填充最后一個(gè)結(jié)點(diǎn)，以表示串的終結(jié)。 a b c d e f g 結(jié)點(diǎn)大小為 4的鏈串 415 中國科大《數(shù)據(jù)結(jié)構(gòu)》 串的存儲(chǔ)結(jié)構(gòu) 對(duì)于結(jié)點(diǎn)大小不為 1的鏈串，其類型定義只需對(duì)上述的結(jié)點(diǎn)類型做簡單的修改即可。 define nodesize 80 typedef struct node { char data[nodesize]。 struct node *next。 } LString。 雖然增大結(jié)點(diǎn)的數(shù)據(jù)域使得存儲(chǔ)密度增大，但是做插入、刪除運(yùn)算時(shí)，需要考慮結(jié)點(diǎn)的分拆與合并，可能會(huì)引起大量字符的移動(dòng)，給運(yùn)算帶來不便。 416 中國科大《數(shù)據(jù)結(jié)構(gòu)》 串的存儲(chǔ)結(jié)構(gòu) 鏈串的插入 a b c x f g y z d e417 中國科大《數(shù)據(jù)結(jié)構(gòu)》 串的基本運(yùn)算的實(shí)現(xiàn) 1. 求子串運(yùn)算 (采用靜態(tài)存儲(chǔ)順序串 ) int StrSub(SString *sub, SString s, int pos, int len) //用 sub返回串 s中序號(hào) pos開始的長度為 len 的子串 { int i。 if (pos0 || pos || len1 || len) { sublen=0。 return(0)。 } //子串起始位置及長度是否合適 else { for(i=0。ilen。i++) subch[i]=[i+pos]。 sub[len]= 39。\039。 //子串結(jié)束 sublen=len。 return(1)。 } } 418 中國科大《數(shù)據(jù)結(jié)構(gòu)》 串的基本運(yùn)算的實(shí)現(xiàn) 2. 定位運(yùn)算 (采用靜態(tài)存儲(chǔ)順序串 ) 串的定位運(yùn)算也稱為串的模式匹配，是一種重要的串運(yùn)算。 設(shè) s和 t是給定的兩個(gè)串，在主串 s中找到等于子串 t的過程稱為模式匹配，如果在 s中找到等于 t的子串，則稱匹配成功，函數(shù)返回 t在 s中的首次出現(xiàn)的存儲(chǔ)位置 (或序號(hào) )，否則匹配失敗，返回－ 1。 t也稱為模式。 ? 【算法思想】 首先將 s0與 t0進(jìn)行比較，若不同，就將 s1與 t0進(jìn)行比較 …… ，直到 s的某一個(gè)字符 si和 t0相同，再將它們之后的字符進(jìn)行比較，若也相同，則如此繼續(xù)往下比較，當(dāng) s的某一個(gè)字符 si與 t的字符 tj不同時(shí)，則 s返回到本趟開始字符的下一個(gè)字符，即 si－ j+1， t返回到 t0，繼續(xù)開始下一趟的比較，重復(fù)上述過程。若 t中的字符全部比較完，則說明本趟匹配成功，本趟的起始位置是 i－ j，否則，匹配失敗
外語相關(guān)推薦
鄂ICP備17016276號(hào)-1