《數(shù)據(jù)結(jié)構(gòu)-串》課件

《數(shù)據(jù)結(jié)構(gòu)-串》ppt課件串的基本概念串的順序存儲(chǔ)結(jié)構(gòu)串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)串的常用操作串的模式匹配算法目錄CONTENT串的基本概念01詳細(xì)描述詳細(xì)描述在數(shù)據(jù)結(jié)構(gòu)中，串是一種特殊的線性表，由零個(gè)或多個(gè)字符組成的有序字符序列。詳細(xì)描述串的長度定義為串中字符的個(gè)數(shù)，通常用大寫的L表示?？偨Y(jié)詞定義了串的字符集定義了串的基本概念總結(jié)詞總結(jié)詞定義了串的長度串的字符集是串中可能出現(xiàn)的字符的集合，通常用小寫的Σ表示。串的定義第二季度第一季度第四季度第三季度總結(jié)詞詳細(xì)描述總結(jié)詞詳細(xì)描述串的表示介紹了字符串的存儲(chǔ)表示字符串通常有兩種存儲(chǔ)表示方式，順序存儲(chǔ)和鏈接存儲(chǔ)。順序存儲(chǔ)方式使用一維數(shù)組來存儲(chǔ)字符串中的字符，而鏈接存儲(chǔ)方式使用結(jié)點(diǎn)來存儲(chǔ)字符串中的字符。介紹了字符串的抽象表示字符串的抽象表示方式是指僅考慮字符串的基本操作，而不考慮其具體的實(shí)現(xiàn)方式。在抽象表示中，我們只關(guān)心字符串的長度、連接、插入、刪除等基本操作。介紹了字符串的連接操作總結(jié)詞字符串的連接操作是將兩個(gè)字符串合并成一個(gè)新的字符串。在具體實(shí)現(xiàn)中，可以采用順序存儲(chǔ)和鏈接存儲(chǔ)兩種方式，但無論采用哪種方式，都需要考慮如何處理字符串中的結(jié)束符'0'。詳細(xì)描述串的基本操作總結(jié)詞介紹了字符串的比較操作詳細(xì)描述字符串的比較操作是比較兩個(gè)字符串的大小。比較時(shí)，從兩個(gè)字符串的第一個(gè)字符開始逐個(gè)比較，直到出現(xiàn)不同的字符或遇到結(jié)束符'0'為止。如果兩個(gè)字符串相等，則它們的長度一定相等；反之，如果兩個(gè)字符串的長度相等，則它們的值不一定相等。串的基本操作串的順序存儲(chǔ)結(jié)構(gòu)0203地址每個(gè)字符在存儲(chǔ)單元中的位置標(biāo)識(shí)。01順序存儲(chǔ)結(jié)構(gòu)將串的字符序列按照一定的順序存儲(chǔ)在一片連續(xù)的存儲(chǔ)單元中，每個(gè)字符占用一個(gè)固定長度的存儲(chǔ)單元。02存儲(chǔ)單元用于存儲(chǔ)字符的物理空間，可以是字節(jié)、字或其他數(shù)據(jù)單位。順序存儲(chǔ)結(jié)構(gòu)的定義為串分配一片連續(xù)的存儲(chǔ)空間，并設(shè)置相應(yīng)的指針指向串的首字符。初始化在串的末尾插入新字符時(shí)，需要移動(dòng)已有的字符，為新字符騰出空間。插入字符刪除串中的某個(gè)字符時(shí)，需要將該位置后的字符向前移動(dòng)一位，覆蓋被刪除字符的位置。刪除字符通過指針遍歷存儲(chǔ)單元，逐個(gè)比較每個(gè)字符，直到找到目標(biāo)字符或遍歷完整個(gè)串。查找字符順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)空間利用率高連續(xù)的存儲(chǔ)空間便于管理，可以充分利用存儲(chǔ)空間。存取速度快由于字符在內(nèi)存中是連續(xù)存儲(chǔ)的，因此訪問某個(gè)字符的速度較快。順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)易于實(shí)現(xiàn)字符串的基本操作：如插入、刪除、查找等操作。VS順序存儲(chǔ)結(jié)構(gòu)的空間是預(yù)先分配的，如果實(shí)際使用的空間遠(yuǎn)小于預(yù)分配的空間，會(huì)造成浪費(fèi)；反之，如果實(shí)際使用的空間超出預(yù)分配的空間，則無法再添加新的字符。插入和刪除操作效率低在順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除操作需要移動(dòng)已有的字符，時(shí)間復(fù)雜度較高。動(dòng)態(tài)調(diào)整困難順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)03鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義使用一組地址任意的存儲(chǔ)單元來依次存放字符串中的字符。這組地址任意的存儲(chǔ)單元稱為鏈表。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)域和指針域。數(shù)據(jù)域用于存放字符數(shù)據(jù)，指針域用于指向下一個(gè)節(jié)點(diǎn)。鏈表中的每個(gè)元素稱為節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含兩部分定義一個(gè)結(jié)構(gòu)體，包含數(shù)據(jù)域和指針域兩個(gè)成員變量。數(shù)據(jù)域用于存放字符數(shù)據(jù)，指針域用于指向下一個(gè)節(jié)點(diǎn)。創(chuàng)建節(jié)點(diǎn)在鏈表中插入一個(gè)新的節(jié)點(diǎn)，需要找到插入位置的前一個(gè)節(jié)點(diǎn)，修改其指針域，使其指向新節(jié)點(diǎn)，然后將新節(jié)點(diǎn)的指針域指向原插入位置的節(jié)點(diǎn)。插入節(jié)點(diǎn)找到需要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，修改其指針域，使其指向需要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，然后釋放需要?jiǎng)h除節(jié)點(diǎn)的內(nèi)存空間。刪除節(jié)點(diǎn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)現(xiàn)可以動(dòng)態(tài)地分配和回收內(nèi)存空間，空間利用率較高；可以方便地插入和刪除節(jié)點(diǎn)，便于修改字符串。訪問某個(gè)字符時(shí)需要從頭節(jié)點(diǎn)開始遍歷鏈表，時(shí)間復(fù)雜度為O(n)，訪問效率較低；需要維護(hù)指針域，增加了編程的復(fù)雜性。優(yōu)點(diǎn)缺點(diǎn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)串的常用操作04插入操作插入操作是指將一個(gè)或多個(gè)字符插入到串的指定位置。如果在串的末尾插入字符，時(shí)間復(fù)雜度為O(1)。插入操作的時(shí)間復(fù)雜度取決于插入的位置和插入的字符數(shù)量。如果在串的開頭插入字符，時(shí)間復(fù)雜度為O(n)，其中n為串的長度。01刪除操作是指從串中刪除一個(gè)或多個(gè)字符。02刪除操作的時(shí)間復(fù)雜度取決于刪除的字符數(shù)量和刪除的位置。03如果刪除一個(gè)字符，時(shí)間復(fù)雜度為O(1)。04如果刪除多個(gè)字符或刪除位置不在末尾，時(shí)間復(fù)雜度為O(n)，其中n為串的長度。刪除操作201401030204替換操作替換操作是指將串中的某個(gè)字符或子串替換為另一個(gè)字符或子串。如果替換一個(gè)字符，時(shí)間復(fù)雜度為O(1)。替換操作的時(shí)間復(fù)雜度取決于替換的字符數(shù)量和替換的位置。如果替換多個(gè)字符或替換位置不在末尾，時(shí)間復(fù)雜度為O(n)，其中n為串的長度。ABCD比較操作比較操作的時(shí)間復(fù)雜度取決于串的長度。比較操作是指比較兩個(gè)串是否相等。對(duì)于不等長的兩個(gè)串，比較操作的時(shí)間復(fù)雜度也為O(n)，其中n為較長的串的長度。對(duì)于等長的兩個(gè)串，比較操作的時(shí)間復(fù)雜度為O(n)，其中n為串的長度。串的模式匹配算法05時(shí)間復(fù)雜度O(n*m)，其中n為主串長度，m為模式串長度。適用場(chǎng)景適用于模式串較短且主串長度較小的情況。樸素模式匹配算法時(shí)間復(fù)雜度O(n+m)，其中n為主串長度，m為模式串長度。要點(diǎn)一要點(diǎn)二適用場(chǎng)景適用于模式串較長且主串長度較大的情況。KMP算法O(n/m)，其中n為主串長度，m為模式串長度。適用于模式串較長且主串長度較大的情