串

定義

也叫字符串

案例引用

串的類型定義以及存儲結(jié)構(gòu)

抽象類型定義

存儲結(jié)構(gòu)(順序表較為常用)

順序存儲結(jié)構(gòu)

為了方便一些操作，通常串的數(shù)組的第一個(gè)位置不放元素，而是從ch【1】開始存放元素

鏈?zhǔn)酱鎯Y(jié)構(gòu)

如果一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域只放一個(gè)字符，那么會導(dǎo)致存儲密度異常的底，解決這個(gè)問題：在數(shù)據(jù)域放更多的字符數(shù)據(jù)

上面的結(jié)構(gòu)體定義結(jié)點(diǎn)結(jié)構(gòu)，下面定義鏈表頭指針

可以得知，對于好多功能的鏈?zhǔn)奖硎径际嵌x兩個(gè)結(jié)構(gòu)：一個(gè)是結(jié)點(diǎn)、一個(gè)是指向第一個(gè)結(jié)構(gòu)體的指針?biāo)M成的結(jié)構(gòu)體
定義鏈表時(shí)：先定義第二個(gè)結(jié)構(gòu)體的對象，創(chuàng)建出鏈表頭指針，如果要?jiǎng)?chuàng)建新的結(jié)點(diǎn)，那么要用到第一個(gè)結(jié)構(gòu)體，進(jìn)行插入即可

實(shí)際上 第二個(gè)結(jié)構(gòu)體定義只是對第一個(gè)結(jié)構(gòu)體里面的第二個(gè)重命名（也就是*Queueptr）做一個(gè)拓展 本質(zhì)上還是第一個(gè)結(jié)構(gòu)體即可 第二個(gè)結(jié)構(gòu)體均屬于指向第一個(gè)結(jié)構(gòu)體的指針類型 沒有第二個(gè)結(jié)構(gòu)體的話 在程序里仍然可以定義指向第一個(gè)結(jié)構(gòu)體的指針

串的模式匹配算法（查找主串中是否有某個(gè)字串）

BF算法

如果匹配失敗，那么需要對兩個(gè)串的下標(biāo)進(jìn)行回溯，從而重新比較下一組

對于主串，先回溯到原始位置：i=i-(j-1)
因?yàn)閷τ诖牡谝粋€(gè)下標(biāo)都是1，所以，j移動(dòng)的格數(shù)是j-1，而i與j同步移動(dòng)，所以，回溯到原始位置是i-(j-1)
之后，因?yàn)橐M(jìn)行下一組比較，所以，i回到原始位置之后，還需要后移一位，所以i=i-(j-1)+1

對于字串，直接回到第一個(gè)位置即可：j=1

由于第一個(gè)位置下標(biāo)為1，方便了這里字串位置的計(jì)算，直接i-T.length即可

while循換條件：當(dāng)主串的下標(biāo)或者字串的下標(biāo)有一個(gè)出界，那就代表匹配結(jié)束，最后要么匹配成功（j>=T.length）要么匹配失敗，循環(huán)繼續(xù)的條件是二者都沒有出界，一旦有一個(gè)出界，那么結(jié)果為假，那么整體為假，&&一假則假

最好情況是o（1）
最壞情況是o（n*m）

綜合平均：o（n*m）

KMP算法

設(shè)計(jì)思想

對字串的回溯進(jìn)行了優(yōu)化

對于第一個(gè)max 其中的條件是 模式串中 j前面的字符串 該字符串的前綴==后綴 那么就可以得到k

當(dāng)字串第j個(gè)元素失配，需要回溯到的下標(biāo)位置，放入數(shù)組next【j】中

第一個(gè)元素失配，那么需要回溯到0，但是由于沒有0位置，所以實(shí)際上的操作是i++，j仍然是1
之后的元素 想看是否滿足其前面的首位子集是否相等，例如j=5時(shí)，前四個(gè)元素，先看1、4，二者相等，所以k-1=1，那么k=2，之后再看12、34，再看123、234，如果有更大的k，那么就取最大的k為最終值，注意不能全部包含 例如1234，這樣是不可以的

如果這種情況也不滿足，就是其他情況，next【j】=1

代碼

kmp算法：

next【j】的算法：

對next【j】進(jìn)行優(yōu)化

按照上述標(biāo)黃的語句，進(jìn)行分析即可，開頭兩位一般是01 或者00
之后 如果回溯位置的元素與自身相同，那么val值與回溯位置的next值一樣，如果不同 ，那么仍然是自己的next值
最后要注意標(biāo)黃的第四種情況，也就是如果相同，每次要判斷到第一位為止

總結(jié)來說 不同為自身，相同做替換，不同則停止，相同則到底

改進(jìn)后的next【j】：

數(shù)組

類型

一維數(shù)組

二維數(shù)組

二維數(shù)組可以是非線性結(jié)構(gòu)，也可以是特殊的線性結(jié)構(gòu)

特殊的線性結(jié)構(gòu)：將一行看成一個(gè)線性結(jié)構(gòu)，該行的每個(gè)元素是一個(gè)列向量

分開定義，實(shí)際上就是對特殊的線性結(jié)構(gòu)的代碼解釋

數(shù)組一旦定義，那么長度固定，所以一般只是做取元素和修改元素操作

抽象類型定義

順序存儲結(jié)構(gòu)

因?yàn)閮?nèi)存單元只能是線性的，但是數(shù)組有多維，所以要想辦法將多維關(guān)系映射到一維關(guān)系，接下來通過找指定元素的地址來反映這個(gè)關(guān)系，接下來就是解決這個(gè)問題

已知首元地址，求某個(gè)元素的地址（該元素第一個(gè)字節(jié)的地址）

一維數(shù)組

二維數(shù)組

也就是（第一維下標(biāo)*列數(shù)+第二維下標(biāo)）*一個(gè)元素所占字節(jié)數(shù)+首元地址=目標(biāo)元素的地址
（本質(zhì)上，是要求該元素的前面有幾個(gè)元素，但是因?yàn)橄聵?biāo)都是從0開始，所以根據(jù)數(shù)學(xué)關(guān)系，下標(biāo)的數(shù)就是該元素之前有幾個(gè)元素的多少）

三維數(shù)組

n維

案例

注意這里假設(shè)元素占用一個(gè)空間，先利用第一個(gè)條件求出列數(shù)，之后利用公式，求出答案

特殊矩陣的壓縮存儲

對稱矩陣

只存上三角或者下三角，元素位置：i*（i-1）/2+j 這就是目標(biāo)元素前面的元素個(gè)數(shù)

三角矩陣

帶狀矩陣

稀疏矩陣

順序結(jié)構(gòu)

鏈?zhǔn)浇Y(jié)構(gòu)

每行每列都有許多頭指針，負(fù)責(zé)該行或者該列

每個(gè)非零元素都有一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)包括行數(shù)、列數(shù)、值、指向下方的結(jié)點(diǎn)、指向右方的結(jié)點(diǎn)，

廣義表

簡介

這里注意 表尾：1.是除了第一個(gè)元素之外的所有元素組成的表
2.一定是一個(gè)表，所以求表尾第一步：先寫一個(gè)括號，之后看去掉表頭之后，剩什么就直接填入括號里

例如 第二題 表頭是第一個(gè)元素，第一個(gè)元素就是一個(gè)空括號 所以就是：（）
表尾 先寫一個(gè)空括號（），之后看除去表頭之后 什么也沒有了 就是空，所以 括號里什么都不寫 所以還是（）

第三題 表頭：a
表尾：先寫一個(gè)空括號，之后，將除去表頭的剩下的元素填入空表中，也就是（（b，c））

性質(zhì)

基本運(yùn)算

案例

循環(huán)m（模式串的長度）次，就可以將所有可能的情況都取得了文章來源地址http://www.zghlxwxcb.cn/news/detail-608047.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--串、數(shù)組、廣義表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！