2022年浙江自考數據結構復習筆記第四章

時間：2022-09-21 17:54:54 作者：儲老師

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

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

聲明：

（一）由于考試政策等各方面情況的不斷調整與變化，本網站所提供的考試信息僅供參考，請以權威部門公布的正式信息為準。

（二）本網站在文章內容來源出處標注為其他平臺的稿件均為轉載稿，免費轉載出于非商業性學習目的，版權歸原作者所有。如您對內容、版權等問題存在異議請與本站聯系，我們會及時進行處理解決。