2022年浙江自考數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記第四章

時(shí)間：2022-09-21 17:54:54 作者：儲(chǔ)老師

　　以下自考復(fù)習(xí)資料均由浙江自考網(wǎng)整理并發(fā)布，考生想要了解更多關(guān)于浙江自考報(bào)名、考試、成績查詢、畢業(yè)、歷年真題、常見問答等相關(guān)信息請(qǐng)關(guān)注浙江自考網(wǎng)，獲取浙江自考更多信息。
串是零個(gè)或多個(gè)字符組成的有限序列。 ·空串：是指長度為零的串，也就是串中不包含任何字符(結(jié)點(diǎn))。
·空白串：指串中包含一個(gè)或多個(gè)空格字符的串。
·在一個(gè)串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。
·子串在主串中的序號(hào)就是指子串在主串中首次出現(xiàn)的位置。
·空串是任意串的子串，任意串是自身的子串。
串分為兩種： ·串常量在程序中只能引用不能改變；
·串變量的值可以改變。
串的基本運(yùn)算有： ·求串長strlen(char*s)
·串復(fù)制strcpy(char*to,char*from)
·串聯(lián)接strcat(char*to,char*from)
·串比較charcmp(char*s1,char*s2)
·字符定位strchr(char*s,charc)
.串是特殊的線性表(結(jié)點(diǎn)是字符)，所以串的存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類似。串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序串。順序串又可按存儲(chǔ)分配的不同分為： ·靜態(tài)存儲(chǔ)分配：直接用定長的字符數(shù)組來定義。優(yōu)點(diǎn)是涉及串長的操作速度快，但不適合插入、鏈接操作。
·動(dòng)態(tài)存儲(chǔ)分配：是在定義串時(shí)不分配存儲(chǔ)空間，需要使用時(shí)按所需串的長度分配存儲(chǔ)單元。

串的鏈?zhǔn)酱鎯?chǔ)就是用單鏈表的方式存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。為了解決"存儲(chǔ)密度"低的狀況，可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符，即結(jié)點(diǎn)的大小。順序串上子串定位的運(yùn)算：又稱串的"模式匹配"或"串匹配"，是在主串中查找出子串出現(xiàn)的位置。在串匹配中，將主串稱為目標(biāo)(串)，子串稱為模式(串)。這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標(biāo)串T中首次出現(xiàn)的有效位移或者是全部有效位移。最壞的情況下時(shí)間復(fù)雜度是O((n-m+1)m),假如m與n同階的話則它是O(n^2)。鏈串上的子串定位運(yùn)算位移是結(jié)點(diǎn)地址而不是整數(shù)

聲明：

（一）由于考試政策等各方面情況的不斷調(diào)整與變化，本網(wǎng)站所提供的考試信息僅供參考，請(qǐng)以權(quán)威部門公布的正式信息為準(zhǔn)。

（二）本網(wǎng)站在文章內(nèi)容來源出處標(biāo)注為其他平臺(tái)的稿件均為轉(zhuǎn)載稿，免費(fèi)轉(zhuǎn)載出于非商業(yè)性學(xué)習(xí)目的，版權(quán)歸原作者所有。如您對(duì)內(nèi)容、版權(quán)等問題存在異議請(qǐng)與本站聯(lián)系，我們會(huì)及時(shí)進(jìn)行處理解決。