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