數(shù)據(jù)結(jié)構(gòu)（C語言版）課件 第4章串、數(shù)組和廣義表

棧和隊列第4章數(shù)據(jù)結(jié)構(gòu)（C語言版）可表示為：（a1,a2,……,an）第2章線性表第3章棧和隊列（操作受限）第4章串（內(nèi)容受限）、數(shù)組和廣義表線性結(jié)構(gòu)補充：C語言中常用的串運算串比較，strcmp(chars1,chars2)串復制，strcpy(charto,charfrom)串連接，strcat(charto,charfrom)求串長，strlen(chars)……調(diào)用標準庫函數(shù)#include<string.h>掌握串的存儲方法，掌握BF算法和KMP算法。明確數(shù)組和廣義表這兩種數(shù)據(jù)結(jié)構(gòu)的特點，掌握數(shù)組地址計算方法，掌握幾種特殊矩（對稱矩陣，對角矩陣，三角矩陣，稀疏矩陣等）壓縮存儲方法。掌握廣義表的求表頭和求表尾基本操作。01OPTION02OPTION03OPTIONtarget目標目錄導航4.14.24.34.44.54.64.7串案例引入串的類型定義、存儲結(jié)構(gòu)及運算數(shù)組廣義表案例分析與實現(xiàn)LeetCode算法練習題Contents串的定義串(String)----零個或多個字符組成的有限序列。串名串值串長n空串n=0a=‘BEI’,b=‘JING’c=‘BEIJING’d=‘BEIJING’子串字符位置主串子串位置串相等空格串串的定義a、b、c、d的長度分別為3、4、7、8；a和b都是c和d的子串；a在c和d中的位置都是1；b在c中的位置都是4，在d中的位置是5。目錄導航4.14.24.34.44.54.64.7串案例引入串的類型定義、存儲結(jié)構(gòu)及運算數(shù)組廣義表案例分析與實現(xiàn)LeetCode算法練習題Contents研究人員不斷從蘋果、桑樹等樹種中檢測到新的雙生病毒案例引入--病毒感染檢測參考文獻：SunS,RenY,WangD,etal.AgroupIWRKYtranscriptionfactorregulatesmulberrymosaicdwarf‐associatedvirus‐triggeredcelldeathinNicotianabenthamiana[J].MolecularPlantPathology,2022,23(2):237-253.病毒DNA序列：單鏈環(huán)狀樹種DNA序列：為鏈狀案例引入--病毒感染檢測利用專業(yè)知識解決林草領(lǐng)域應用問題。培養(yǎng)農(nóng)林信息化研究能力、創(chuàng)新精神、生態(tài)文明理念、綠色環(huán)保意識。研究者將病毒DNA和植物的DNA均表示成由字母組成的字符串序列。檢測某種病毒DNA序列是否在植物的DNA序列中出現(xiàn)過。出現(xiàn)過，已感染未出現(xiàn)，未感染。案例引入--病毒感染檢測baa感染bbbbaa感染aaabbb未感染babbbabaa案例引入--病毒感染檢測

存在存在未存在bbbbaaaaabbbbabbba子串：baa主串1主串2主串3案例引入--病毒感染檢測案例引入--模式匹配算法存在時，返回子串的位置。不存在，返回0。--檢測一個主串中是否存在一個給定的子串（模式）模式匹配算法應用--網(wǎng)絡(luò)入侵檢測模式匹配算法應用--網(wǎng)絡(luò)入侵檢測模式匹配算法應用--網(wǎng)絡(luò)入侵檢測知法守法樹立健康的網(wǎng)絡(luò)道德觀具有科技報國的社會責任感和愛國主義情操嚴謹求實、勇于創(chuàng)新“共建網(wǎng)絡(luò)安全，共享網(wǎng)絡(luò)文明“網(wǎng)絡(luò)安全人人有責、人人參與模式匹配算法應用--網(wǎng)絡(luò)入侵檢測模式匹配算法應用--網(wǎng)絡(luò)入侵檢測根據(jù)入侵行為的特征，按照一定的規(guī)范將這些特征編寫成規(guī)則。通過檢測網(wǎng)絡(luò)數(shù)據(jù)與規(guī)則數(shù)據(jù)庫中的規(guī)則是否匹配，來判斷入侵與否。模式匹配算法應用--信息檢索模式匹配算法應用--信息檢索模式匹配算法——Index(S,T,p)初始條件1≤p≤StrLength(S)操作結(jié)果主串S中是否存在子串T：存在，返回S中的第p個字符之后T第一次出現(xiàn)的位置；不存在，返回0。目錄導航4.14.24.34.44.54.64.7串案例引入串的類型定義、存儲結(jié)構(gòu)及運算數(shù)組廣義表案例分析與實現(xiàn)LeetCode算法練習題Contents串的類型定義、存儲結(jié)構(gòu)及運算數(shù)據(jù)對象:數(shù)據(jù)關(guān)系:基本操作:(1)StrAssign(&T,chars)//串賦值(2)StrCompare(S,T)//串比較(3)StrLength(S)//求串長(4)Concat(&T,S1,S2)//串聯(lián)ADTString{(5)SubString(&Sub,S,pos,len)//求子串

(6)StrCopy(&T,S)//串拷貝

(7)StrEmpty(S)//串判空

(8)ClearString(&S)//清空串

(9)Index(S,T,p)//子串的位置

(11)Replace(&S,T,V)//串替換

(12)StrInsert(&S,pos,T)//子串插入

(12)StrDelete(&S,pos,len)//子串刪除

(13)DestroyString(&S)//串銷毀}ADTString串的類型定義、存儲結(jié)構(gòu)及運算串的存儲結(jié)構(gòu)鏈式存儲順序存儲#defineMAXLEN255//串的最大長度typedefstruct{charch[MAXLEN+1];//存儲串的一維數(shù)組intlength;//串的當前長度}SString;

串的定長順序存儲結(jié)構(gòu)typedefstruct{char*ch;//若串非空,則按串長分配存儲區(qū),//否則ch為NULLintlength;//串長度}HString;

串的堆式順序存儲結(jié)構(gòu)鏈式存儲表示#defineCHUNKSIZE80//可由用戶定義的塊大小typedefstructChunk{charch[CHUNKSIZE];

structChunk*next;}Chunk;typedefstruct{Chunk*head,*tail;//串的頭指針和尾指針

intcurlen;//串的當前長度}LString;串的鏈式存儲結(jié)構(gòu)優(yōu)點：操作方便。缺點：存儲密度較低?？蓪⒍鄠€字符存放在一個結(jié)點中，以克服其缺點。實際分配的存儲位串值所占的存儲位存儲密度=鏈式存儲表示串的模式匹配算法算法目的：算法種類：AB確定主串中所含子串第一次出現(xiàn)的位置（定位）。BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）KMP算法（特點：速度快）S:ababcabcacbabT:abcijS:ababcabcacbab T:abcS:ababcabcacbabT:abci

指針回溯模式匹配算法——BF（BruteForce）算法——窮舉、經(jīng)典、古典算法BF算法步驟執(zhí)行循環(huán)：將主串的第p個字符和子串的第1個字符比較相等，繼續(xù)逐個比較后續(xù)字符；不等，回溯到主串的下一個字符，重新與子串的第1個字符比較。退出循環(huán)成功：返回S中與T匹配的子序列第1個字符的序號；失?。悍祷?。

intIndex_BF(SStringS,SStringT,intp)i=p;j=1; while(i＜=S.length&&j＜=T.length))

//兩個串均未到達串尾{if(S.ch[i]==T.ch[j]){++i;++j;}

//相等，繼續(xù)比較后續(xù)字符

else{i=i-j+2;;j=1;}

//不等，指針后退重新開始匹配}if(j＞T.length)returni-T.length;

//成功elsereturn0;

//失敗

}?i=i-j+2BF算法實現(xiàn)

BF算法分析--算法分析S：aaaaabaT：aaaaaaaaabaaaba主串S長n，子串T長m?可能匹配成功的位置（1~)n-m+1aaaaabaaaaaaaaaaabaaaaabaaaaabaaaaban=7，m=5

BF算法分析--最好情況（平均）每趟不成功的匹配都發(fā)生在T的第一個字符與S相應字符的比較。第i個位置匹配成功，比較了（i-1+m）次假定每個位置上匹配成功的概率相等S：aaaaabaT：ba則平均比較次數(shù)最好情況下平均時間復雜度O(n+m)

BF算法分析--最壞情況（極端）aaaaaabaabaaaaaabaab1234567aaaaaabaab第5個位置匹配成功比較了次？？？(5?1)*3+3=5*3=15——子串位于主串的末尾(i?1)*m+m=i*maaaaaabaabaaaaaabaabn=7，m=3最后一個位置匹配成功比較了次？？？(7?3)*3+3=5*3=15(n-m)*m+m=(n-m+1)*m

每趟不成功的匹配都發(fā)生在T的最后一個字符與S相應字符的比較第i個位置匹配成功，比較了i*m次假定每個位置上匹配成功的概率相等則平均比較次數(shù)最壞情況下平均時間復雜度O(n*m)（通常m<<n）BF算法分析--最壞情況

baa感染bbbbaa感染aaabbb未感染babbbabaa--BF算法循環(huán)m次如何取得每個長度為m的環(huán)狀字符串？案例實現(xiàn)--病毒感染檢測案例實現(xiàn)--病毒感染檢測baabaabaabaabaaaabababaa依次檢測每對病毒DNA和人的DNA是否匹配，循環(huán)執(zhí)行：分別讀取一對病毒DNA序列和人的DNA序列；設(shè)置flag，初始為0，表示未匹配；病毒DNA長度是m，連續(xù)存儲兩次擴大為2m；循環(huán)m次，重復執(zhí)行以下操作：依次取得每個長度為m的病毒DNA環(huán)狀字符串；將此字符串作模式串，將人的DNA作主串，調(diào)用BF，將結(jié)果返回flag；若flag非0，表示匹配成功。退出循環(huán)時，若flag非0，輸出“YES”，否則，輸出“NO”。案例實現(xiàn)--病毒感染檢測案例實現(xiàn)--病毒感染檢測醫(yī)學研究者最近發(fā)現(xiàn)了某些新病毒，通過對這些病毒的分析，得知它們的DNA序列都是環(huán)狀的?，F(xiàn)在研究者收集了大量的病毒DNA和人的DNA數(shù)據(jù)，想快速檢測出這些人是否感染了相應的病毒。為方便研究，研究者將人的DNA和病毒的DNA均表示成由一些小寫字母組成的字符串，然后檢測某種病毒的DNA序列是否在患者的DNA序列中出現(xiàn)過，如果出現(xiàn)過，則此人感染了病毒，否則沒有感染。注意：人的DNA序列是線性的，而病毒的DNA序列是環(huán)狀的。任務描述對于每組數(shù)據(jù)輸出一行，若患者感染了病毒輸出“YES”，否則輸出“NO”。輸入輸出多組數(shù)據(jù)，每組數(shù)據(jù)有一行，為序列A和B，A對應病毒的DNA序列，B對應人的DNA序列。A和B都為“0”時輸入結(jié)束。案例實現(xiàn)--病毒感染檢測案例實現(xiàn)--網(wǎng)絡(luò)入侵檢測隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)安全問題日益嚴重。入侵檢測技術(shù)是一種積極主動防御的安全保障技術(shù)，而Snort是其中基于規(guī)則匹配的一種入侵檢測技術(shù)。Snort自1998年被發(fā)明以來，歷經(jīng)數(shù)年的迭代更新，Snort已成為一個具有多平臺(Multi-Platform)、實時(Real-Time)流量分析、網(wǎng)絡(luò)IP數(shù)據(jù)包(Pocket)記錄等特性的強大的網(wǎng)絡(luò)入侵檢測/防御系統(tǒng)(NetworkIntrusionDetection/PreventionSystem)，即NIDS/NIPS。Snort首先需要使用者根據(jù)入侵行為的特征，按照一定的規(guī)范將這些特征編寫成規(guī)則，最后通過檢測網(wǎng)絡(luò)數(shù)據(jù)與規(guī)則數(shù)據(jù)庫中的規(guī)則是否匹配來判斷入侵與否。在Snort入侵檢測系統(tǒng)中，規(guī)則的匹配效率是影響Snort檢測效率的關(guān)鍵。而規(guī)則匹配的核心技術(shù)是模式匹配算法。請實現(xiàn)一個模式匹配算法，用于網(wǎng)絡(luò)入侵行為的檢測。若檢在網(wǎng)絡(luò)日志中檢測到任何一條檢測規(guī)則中的ip地址，則輸出“Networkintrusiondetected.”，反之輸出“Nothingdetected.”任務描述案例實現(xiàn)--網(wǎng)絡(luò)入侵檢測輸出一行，若在網(wǎng)絡(luò)日志中檢測到任何一條檢測規(guī)則中的ip地址，則輸出“Networkintrusiondetected.”，反之輸出“Nothingdetected.”。輸入輸出輸入共n+m+1行，第1行兩個整數(shù)n,m(n,m≤100)2～n+1行每行為一條檢測規(guī)則。規(guī)則的格式為:protocol:網(wǎng)絡(luò)協(xié)議ip:ip地址msg:"附加信息"n+2～n+m+1行共m行，為網(wǎng)絡(luò)日志內(nèi)容。案例實現(xiàn)--網(wǎng)絡(luò)入侵檢測測試輸入：`33``protocol:tcpip:225.93.118.39msg:"Networkintrusiondetected."``protocol:tcpip:152.213.218.150msg:"Networkintrusiondetected."``protocol:tcpip:181.164.101.231msg:"Networkintrusiondetected."``ProtoRecv-QSend-QLocal-AddressForeign-AddressState``tcp0036.51.200.67:9540340.56.49.213:29716LAST_ACK``tcp00215.142.133.153:49323106.54.135.230:18487CLOSED`預期輸出：`No

Intrusion.`案例實現(xiàn)--網(wǎng)絡(luò)入侵檢測模式匹配算法小結(jié)模式匹配知真酌，入侵檢測衛(wèi)家國模擬數(shù)據(jù)無量著，

式子算法何其多。

匹配相合題相似，

配出相同知真灼。

入心付血輔新秀，

侵解內(nèi)核吾存憂。

檢驗真知迎風浪，

測病防疫衛(wèi)家國。S:ababcabcacbabT:abcijS:ababcabcacbab T:abcS:ababcabcacbabT:abci指針回溯BF算法低效KMP（KnuthMorrisPratt）算法《計算機程序設(shè)計藝術(shù)第1卷基本算法》

《計算機程序設(shè)計藝術(shù)第2卷半數(shù)值算法》《計算機程序設(shè)計藝術(shù)第3卷排序與查找》《計算機程序設(shè)計藝術(shù)第4卷組合算法》BF缺陷：s的指針i回溯，已經(jīng)被檢索過的部分主串被重復檢索。同時，t的指針j也會回溯到起始位置。babcadcbcbcdijstKMP算法KMP改進：如何避免指針i回溯。在BF中，指針i回溯的目的？不回溯可能會錯過一些匹配。KMP算法設(shè)計思想bcaaadcbcaadijstbcaaadcbcaadijstKMP算法設(shè)計思想指針i不動？子串向右滑動，即找到j(luò)移動的位置，使得新的指針j之前的字符能夠自動匹配。j應該移動到的位置k有什么特點？abababcabaijstbckdeKMP算法設(shè)計思想abababcabaijstbckde

而滑動之前已匹配過的字符能告訴我們什么信息呢？KMP算法設(shè)計思想主串的k-1位后綴與子串的k-1位前綴相同！

abababcabaijstbcde

KMP算法設(shè)計思想只需要比較子串的前后綴就可以了，無需主串！最長相同前綴和后綴KMP算法設(shè)計思想

abajtbc

KMP算法設(shè)計思想KMP算法設(shè)計思想intindex_KMP(SStringS,SStringT,intpos){

i=pos;j=1;while(i<=S.length&&j<=T.length){if(j==0||S.ch[i]==T.ch[j])++i;++j;}elsej=next[j];}if(j>T.length)returni-T.length;elsereturn0;}若s[i]和t[j]相等，則比較s[i+1]和t[j+1]若s[i]和t[j]不等，則j回退到next[j]所指的位置k，繼續(xù)比較s[i]和t[k]；當s[i]和t[1]不等，則比較s[i+1]和t[1]所以next[1]=0。acabaabaaabbaaccab第一趟：從s[1]和t[1]開始匹配i=2j=2，j=next[2]=1下一次將會進行s[2]和t[1]的比較主串模式串此時發(fā)生失配aabcacj12345678模式串a(chǎn)baabcacnext[j]01122312KMP算法設(shè)計思想KMP算法設(shè)計思想acabaabaaabbaaccab第二趟：從s[2]和t[1]開始匹配i=2模式串此時發(fā)生失配aabcacj=1,j=next[1]=0下一步將會進行s[3]和t[1]的比較主串j12345678模式串a(chǎn)baabcacnext[j]01122312acabaabaaabbaaccab第三趟：從s[3]和t[1]開始匹配模式串a(chǎn)abcac主串i=8發(fā)生失配j=6，j=next[6]=3下一步將進行s[8]和t[3]的比較j12345678模式串a(chǎn)baabcacnext[j]01122312KMP算法設(shè)計思想acabaabaaabbaaccab第四趟：從s[8]和t[3]開始匹配模式串a(chǎn)abcac主串i=8j=9(j>8,匹配成功）j12345678模式串a(chǎn)baabcacnext[j]01122312KMP算法設(shè)計思想失配時，i不變，j回退next[j]重新匹配。當j退到0，i和j需要同時加1（即主串的第i個字符和模式的第1個字符不等時，應從主串的第i+1個字符起重新進行匹配)。KMP算法設(shè)計思想若next[j]=k，子串起始的k-1個字符與j之前的k-1個字符匹配。next[j]存儲著指針j之前的字符信息，而與j所指字符無關(guān)。要保證j能夠回溯，應該讓k<j，有j-k+1>1，j之前這一組字符最多從第二個開始。KMP算法設(shè)計思想abajtbc

kfej=2時，需要用到next[2]，意味著模式串已經(jīng)向右滑動到j(luò)指向第2個字符，仍然不能與主串中i所指字符產(chǎn)生匹配。接下來需要讓指針j回溯到1，再進行比較。此時會使用j=next[j]，而next[2]正是用來存儲需要回溯的位置，所以next[2]=1。KMP算法設(shè)計思想aabdcijsabdt用肉眼求一些next[]數(shù)值KMP算法設(shè)計思想1?????01123nextabcabcft已知next[j]=k，求next[j+1]的值當t[j]==t[k]時，next[j+1]=next[j]+1，也就是k+1。只要j對應的k是最大的，j+1對應的k+1也必然是最大的。KMP算法設(shè)計思想?4abcabcfj011123abc

tknext

k

j+1KMP算法設(shè)計思想已知next[j]=k，求next[j+1]的值當t[j]!=t[k]時，想要找到j(luò)+1之前最長的字符匹配，應該讓模式串起始部分向右滑動到正確位置，然后對位置j的字符進行比較。那么應該滑動到什么位置呢？?abcabafj011123abc

tknextkj+1如果把這里的整個模式串看做主串，模式串的起始部分看做子串，這正是一個主串與模式串匹配的過程。尋找子串向右滑動的位置，或者說指針k回溯的位置，這正是next[]數(shù)組的目的。答案顯而易見：k=next[k]。KMP算法設(shè)計思想?abcabafj011123abc

tknextkj+1通過比較發(fā)現(xiàn)t[j]==t[k]，那么next[j+1]就同樣會等于k+1，只不過現(xiàn)在的k已經(jīng)是回溯過后的。KMP算法設(shè)計思想?2abcabafj011123abc

tknextkj+1如果一次滑動不行，那就繼續(xù)滑動，繼續(xù)比較，可能直到滑動到頭也沒能找到匹配。KMP算法設(shè)計思想?abcabdfj011123abc

tknextkj+1挨著j+1這個位置之前，完全找不到任何能與起始部分匹配的字符。如果在j+1這個位置失配，即使不回溯i，也不會出現(xiàn)錯過匹配的現(xiàn)象，直接從模式串的第一個位置開始匹配即可。next[j+1]=1，此時k=0，next[j+1]=k+1。KMP算法設(shè)計思想?1abcabdfj011123abc

tknextkj+1因為next[j]=k代表了j需要回溯的位置，所以j一定大于k。而在可能會進行的多次k=next[k]過程中，假設(shè)next[k]=k1，next[k1]=k2……同理可得j>k>k1>k2……只要知道了j+1之前的所有位置的next[]數(shù)值，就一定可以求出next[j+1]的數(shù)值。KMP算法設(shè)計思想?abcabdfj011123abc

tknextkk1k21j+1KMP算法設(shè)計思想voidget_next(SStringT,intnext[]){i=1;j=0;next[1]=0;while(i<T.length){if(j==0||T.ch[i]==T.ch[j]){++i;++j;next[i]=j;}elsej=next[j];}}t[i]=t[j],next[i+1]=j+1;//初始化t[i]≠t[j],j往前滑動到next[j]所指向的位置重復上述過程直到t[i]=t[j]；若找不到，j最終會滑到0，next[i+1]=1。求出next[1]=0，next[2]=1這兩個特殊起始位置的數(shù)值。通過循環(huán)，可以求出next[3]、next[4]……最終求出整個next[]數(shù)組。在這個過程中模式串t，既做了主串又做了模式串，求next[]的過程還是一個模式匹配的問題。以abaabc為例跟蹤程序運行結(jié)果j=0—>i=2,j=1,next[2]=1下一步進行t[2]和t[1]的比較KMP算法設(shè)計思想abaabcabaabc主串模式串t[2]≠t[1],j=next[1]=0——>j=1，i=3，next[3]=1;下一次將會進行t[3]和t[1]的比較。t[3]和t[1]的比較KMP算法設(shè)計思想abaabcabaabc主串模式串t[3]=t[1]——>i=4,j=2,next[4]=2;下一步進行t[4]和t[2]的比較。t[4]≠t[2]——>j=next[2]=1;下一步進行t[4]和t[1]。t[4]和t[1]的比較KMP算法設(shè)計思想abaabcabaabc主串模式串t[4]=t[1]——>i=5,j=2,next[5]=2，下一步t[5]和t[2]會進行比較。t[5]=t[2]——>i=6，j=3,next[6]=3i=T.length循環(huán)結(jié)束KMP算法設(shè)計思想求next[k+1]，其中k+1=17j1234567891011121413151617k+1pnext[j]KMP算法設(shè)計思想已知next[16]=8，則元素有以下關(guān)系：j1234567891011121413151617k+1Pnext[j]8若P8=P16，則next[17]=8+1=9這兩部分重合KMP算法設(shè)計思想j1234567891011121413151617k+1Pnext[j]8若P8≠P16，且next[8]=4，則有以下關(guān)系：這兩部分重合4這兩部分重合KMP算法設(shè)計思想j1234567891011121413151617k+1Pnext[j]8若P8≠P16，且next[8]=4，則有以下關(guān)系：這兩部分重合4這四部分重合KMP算法設(shè)計思想j1234567891011121413151617k+1Pnext[j]8若P8≠P16，且next[8]=44若P16=P4，則next[17]=4+1=5KMP算法設(shè)計思想j1234567891011121413151617k+1Pnext[j]8這兩部分重合4這兩部分重合若P16≠P4，若next[4]=2，則有以下關(guān)系：這兩個數(shù)重合2KMP算法設(shè)計思想j1234567891011121413151617k+1Pnext[j]8這兩部分重合4這兩部分重合若P16=P2，則next[17]=2+1=3，否則繼續(xù)取next[2]=1、next[1]=0；遇到0時還沒有出結(jié)果，則遞推結(jié)束，此時next[17]=1。這兩個數(shù)重合2next數(shù)組的缺陷KMP算法設(shè)計思想aaabaaaabisaaajtab01234next前面全都是‘a(chǎn)’，卻要一個一個全部和‘b’比較一次。KMP算法設(shè)計思想aaabaaaabisaaajtab01234next為什么會發(fā)生這種情況呢？KMP算法設(shè)計思想abcabxyisabcjtab01112next3cz當檢測到‘c’和‘x’不同時，j會回溯為next[6]=3。此時t[j]仍為‘c’。已經(jīng)得知‘c’!=‘x’，但仍需要再次判斷后，才能讓j回溯到正確的位置next[3]=1。KMP算法設(shè)計思想abcabxyisabcjtab01112next3cz發(fā)現(xiàn)t[6]=t[3]時，直接使next[6]=next[3]=1。next[]數(shù)組的修正值nextval[]：在j++以及k++之后，在向nextval[]數(shù)組中填入數(shù)值時，如果t[j]==t[k]，直接使next[j]=next[k]即可。KMP算法設(shè)計思想abcitabnextval0c11111jvoidget_nextval(SStringT,intnextval[]){i=1;nextval[1]=0;j=0;while(i<T.length){if(j==0||T.ch[i]==T.ch[j]){++i;++j;

if(T.ch[i]!=T.ch[j])nextval[i]=j;elsenextval[i]==nextval[j];}elsej=nextval[j];}}voidget_next(SStringT,intnext[]){i=1;j=0;next[1]=0;while(i<T.length){if(j==0||T.ch[i]==T.ch[j]){++i;++j;next[i]=j;}elsej=next[j];}}KMP算法設(shè)計思想使用nextval[修正數(shù)組實現(xiàn)KMP算法時，不會出多次無用比較的現(xiàn)象。nextval數(shù)組中nextval[2]不一定等于1，且可能會有多個0出現(xiàn)。while(i<T.length){if(j==0||T.ch[i]==T.ch[j])

{++i;++j;if(T.ch[i]!=T.ch[j])nextval[i]=j;elsenextval[i]==nextval[j];

}elsej=nextval[j];}KMP算法設(shè)計思想aaaitabnextval00004j設(shè)主串長度為n，模式串長度為m，求nextval數(shù)組的過程循環(huán)了m-1次，與主串的匹配過程也比較了m次，最好時間復雜度為：O(m)。KMP算法時間復雜度---最好aaaabcdsaaaaitanextval0000jO(m+n)=O([m,2m]+[n,2n])

計算next數(shù)組的時間復雜度+遍歷比較的復雜度1.當前字符匹配時，同時移動i++，j++；2.當前字符不匹配，且j=0時，只移動i++，j=0不動；3.當前字符不匹配，且j!=0時，i不變，strM[j]回跳，最多跳j次。但j由前面匹配的情況1確定，而情況1總共不可能出現(xiàn)超過n次，所以總回跳不會超過n次。最壞情況：i++次數(shù)（情況一+情況二）+j回跳（情況3）=n+最壞n=2n[m,2m]也可以類似證明KMP算法時間復雜度---最壞設(shè)主串s的長度為n，模式串t長度為m，在KMP算法中求next數(shù)組的時間復雜度為O(m)，在后面的匹配中因主串s的下標不減即不回溯，比較次數(shù)可記為n，所以KMP算法總的時間復雜度為O(n+m)。KMP算法改進--BM（BoyerMoore）算法文獻1：BoyerRS,MooreSJ.Afaststringsearchingalgorithm.CommunicationsoftheACM[J].1977,20(10):762-772.速度快于KMP3-4倍，用于文本編輯器的查找功能文獻2：FengD.Aneffectivepatternmatchingalgorithmforintrusiondetection[C]//InternationalConferenceonComputerScience&ElectronicsEngineering.IEEE,2012.BM算法的改進目錄導航4.14.24.34.44.54.64.7串案例引入串的類型定義、存儲結(jié)構(gòu)及運算數(shù)組廣義表案例分析與實現(xiàn)LeetCode算法練習題Contents本節(jié)所討論的數(shù)組與高級語言中的數(shù)組區(qū)別：數(shù)組高級語言中的數(shù)組是順序結(jié)構(gòu)；而本章的數(shù)組既可以是順序，也可以是鏈式結(jié)構(gòu)。數(shù)組的抽象數(shù)據(jù)類型數(shù)據(jù)對象:數(shù)據(jù)關(guān)系:ADTArray{(1)InitArray(&A,n,bound1,boundn)//構(gòu)造數(shù)組A(2)DestroyArray(&A)//銷毀數(shù)組A(3)Value(A,&e,index1,…,indexn)//取數(shù)組元素值

(4)Assign(A,&e,index1,…,indexn)//給數(shù)組元素賦值基本操作:}ADTArray數(shù)組的抽象數(shù)據(jù)類型一維數(shù)組352749186054778341020123456789ll

l

l

l

l

l

l

l

l

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=LOC(i-1)+l=a+i*l,i>0a,i

=0

a+i*la二維數(shù)組以行序為主序C,PASCAL數(shù)組的順序存儲以列序為主序FORTRAN數(shù)組的順序存儲

a[n][m]設(shè)數(shù)組開始存放位置LOC(0,0)=a

LOC(j,k)=a+j*m+k二維數(shù)組的行序優(yōu)先表示三維數(shù)組按頁/行/列存放，頁優(yōu)先的順序存儲

①②③a[m1][m2][m3]

各維元素個數(shù)為m1,m2,m3

下標為i1,i2,i3的數(shù)組元素的存儲位置：

LOC(i1,i2,i3)=a+

i1*m2*m3+i2*m3+i3前i1頁總元素個數(shù)第i1頁的前i2行總元素個數(shù)第i2行前i3列元素個數(shù)三維數(shù)組各維元素個數(shù)為m1,m2,m3,…,mn下標為i1,i2,i3,…,in

的數(shù)組元素的存儲位置：n維數(shù)組n維數(shù)組設(shè)有一個二維數(shù)組A[m][n]按行優(yōu)先順序存儲，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。設(shè)數(shù)組元素A[i][j]存放在起始地址為Loc(i,j)的存儲單元中∵Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.∴n=(676-2-644)/2=15∴Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.練習設(shè)有二維數(shù)組A[10,20]，其每個元素占兩個字節(jié)，A[0][0]存儲地址為100，若按行優(yōu)先順序存儲，則元素A[6,6]的存儲地址為

，按列優(yōu)先順序存儲，元素A[6,6]的存儲地址為

。練習352232(6*20+6)*2+100=352(6*10+6)*2+100=232特殊矩陣的壓縮存儲12什么是壓縮存儲？若多個數(shù)據(jù)元素的值都相同，則只分配一個元素值的存儲空間，且零元素不占存儲空間。什么樣的矩陣能夠壓縮？一些特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，稀疏矩陣等。什么叫稀疏矩陣？矩陣中非零元素的個數(shù)較少（一般小于5%）。3[特點]

在n×n的矩陣a中，滿足如下性質(zhì)：aij=aji(1≤i,j≤n)[存儲方法]

只存儲下(或者上)三角(包括主對角線)的數(shù)據(jù)元素

共占用n(n+1)/2個元素空間。

i(i-1)/2+j當i≥jj(j-1)/2+i當i<ja11a21a22a31

aij(aji)ann

k1234n(n+1)/2saajiaij1.對稱矩陣k=2.三角矩陣

上三角矩陣下三角矩陣(i-1)(2n-i+2)/2+j-i+1i≤ji(i-1)/2+ji≥jn(n+1)/2+1i>j

n(n+1)/2+1i<jCC上三角矩陣下三角矩陣k=k=[特點]

對角線以下(或者以上)的數(shù)據(jù)元素(不包括對角線)全部為常數(shù)c。[存儲方法]

重復元素c共享一個元素存儲空間，共占用n(n+1)/2+1個元素

空間：

sa[1..n(n+1)/2+1]。3.對角矩陣（帶狀矩陣）

823000

420300

577680096915006142000283五對角矩陣

338520612827943476185962s[-2..2;1..6]-2-1012123456i1=i-jj1=j|i-j|(L-1)/2k1n*Lsak=(i1+2)*n+j1=(i-j+2)*n+j|i-j|(L-1)/2[特點]

在n×n的方陣中，非零元素集中在主對角線及其兩側(cè)共L（奇數(shù)）

條對角線的帶狀區(qū)域內(nèi)—L對角矩陣。[存儲方法]以對角線的順序存儲

823000

420300

577680096915006142000283823420357768969156142283sak12345678910111213141516171819202122232425263.對角矩陣（帶狀矩陣）只存儲帶狀區(qū)內(nèi)的元素除首行和末行，按每行L個元素，共(n-2)L+(L+1)個元素。sa[1..(n-1)L+1]k=(i-1)L+1+(j-i)|i-j|(L-1)/24.稀疏矩陣[特點]

大多數(shù)元素為零。6×6順序存儲：三元組表鏈式存儲：十字(正交)鏈表

[常用存儲方法]

只記錄每一非零元素(i,j,aij)節(jié)省空間，但喪失隨機存取功能。1500220-15011

3000000-600000000

91

000000028000目錄導航4.14.24.34.44.54.64.7串案例引入串的類型定義、存儲結(jié)構(gòu)及運算數(shù)組廣義表案例分析與實現(xiàn)LeetCode算法練習題Contents

LS是表名，ai是表元素，它可以是表(稱為子表)，可以是數(shù)據(jù)元素(稱為原子)。n為表的長度。n=0的廣義表為空表。廣義表

廣義表（列表）：n(

0)個表元素組成的有限序列，記作LS=(a0,a1,a2,…,an-1)線性表的成分都是結(jié)構(gòu)上不可分的單元素。廣義表的成分可是單元素，也可是有結(jié)構(gòu)的表。線性表是一種特殊的廣義表。廣義表不一定是線性表，也不一定是線性結(jié)構(gòu)。廣義表與線性表的區(qū)別？廣義表的基本運算求表頭GetHead(L)01非空廣義表的第一個元素，可以是一個單元素，也可以是一個子表。求表尾GetTail(L)02非空廣義表除去表頭元素以外其它元素所構(gòu)成的表。表尾一定是一個表。練習A=()

GetHead和GetTail均無定義A=(a,b)

GetHead(A)=aGetTail(A)=(b)

A=(a)

GetHead(A)=aGetTail(A)=()

A=((a))

GetHead(A)=(a)GetTail(A)=()

GetHead(GetTail(GetHead(GetTail(GetTail(A)))))

A=(a,b,(c,d),(e,(f,g)))

d有次序性有長度有深度可遞歸可共享一個直接前驅(qū)和一個直接后繼＝表中元素個數(shù)＝表中括號的重數(shù)自己可以作為自己的子表可以為其他廣義表所共享廣義表的特點E=(a,E)=(a,(a,E))=(a,(a,(a,…….)))，E為遞歸表1）A=()2）B=(e)3）C=(a,(b,c,d))4）D=(A,B,C)5）E=(a,E)n=0，因為A是空表n=1，表中元素e是原子n=2，a為原子，(b,c,d)為子表n=3，3個元素都是子表n=2，a為原子，E為子表D=(A,B,C)=((),(e),(a,(b,c,d)))，共享表練習：求下列廣義表的長度目錄導航4.14.24.34.44.54.64.7串案例引入串的類型定義、存儲結(jié)構(gòu)及運算數(shù)組廣義表案例分析與實現(xiàn)LeetCode算法練習題Contents醫(yī)學研究者最近發(fā)現(xiàn)了某些新病毒，通過對這些病毒的分析，得知它們的DNA序列都是環(huán)狀的?，F(xiàn)在研究者收集了大量的病毒DNA和人的DNA數(shù)據(jù)，想快速檢測出這些人是否感染了相應的病毒。為方便研究，研究者將人的DNA和病毒的DNA均表示成由一些小寫字母組成的字符串，然后檢測某種病毒的DNA序列是否在患者的DNA序列中出現(xiàn)過，如果出現(xiàn)過，則此人感染了病毒，否則沒有感染。注意：人的DNA序列是線性的，而病毒的DNA序列是環(huán)狀的。任務描述對于每組數(shù)據(jù)輸出一行，若患者感染了病毒輸出“YES”，否則輸出“NO”。輸入輸出多組數(shù)據(jù)，每組數(shù)據(jù)有一行，為序列A和B，A對應病毒的DNA序列，B對應人的DNA序列。A和B都為“0”時輸入結(jié)束。案例實現(xiàn)--病毒感染檢測案例實現(xiàn)--網(wǎng)絡(luò)入侵檢測隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)安全問題日益嚴重。入侵檢測技術(shù)是一種積極主動防御的安全保障技術(shù)，而Snort是其中基于規(guī)則匹配的一種入侵檢測技術(shù)。Snort自1998年被發(fā)明以來，歷經(jīng)數(shù)年的迭代更新，Snort已成為一個具有多平臺(Multi-Platform)、實時(Real-Time)流量分析、網(wǎng)絡(luò)IP數(shù)據(jù)包(Pocket)記錄等特性的強大的網(wǎng)絡(luò)入侵檢測/防御系統(tǒng)(NetworkIntrusionDetection/PreventionSystem)，即NIDS/NIPS。Snort首先需要使用者根據(jù)入侵行為的特征，按照一定的規(guī)范將這些特征編寫成規(guī)則，最后通過檢測網(wǎng)絡(luò)數(shù)據(jù)與規(guī)則數(shù)據(jù)庫中的規(guī)則是否匹配來判斷入侵與否。在Snort入侵檢測系統(tǒng)中，規(guī)則的匹配效率是影響Snort檢測效率的關(guān)鍵。而規(guī)則匹配的核心技術(shù)是模式匹配算法。請實現(xiàn)一個模式匹配算法，用于網(wǎng)絡(luò)入侵行為的檢測。若檢在網(wǎng)絡(luò)日志中檢測到任何一條檢測規(guī)則中的ip地址，則輸出“Networkintrusiondetected.”，反之輸出“Nothingdetected.”任務描述輸出一行，若檢在網(wǎng)絡(luò)日志中檢測到任何一條檢測規(guī)則中的ip地址，則輸出“Networkintrusiondetected.”，反之輸出“Nothingdetected.”。輸入輸出輸入共n+m+1行，第1行兩個整數(shù)n,m(n,m≤100)2～n+1行每行為一條檢測規(guī)則。規(guī)則的格式為:protocol:網(wǎng)絡(luò)協(xié)議ip:ip地址msg:"附加信息"n+2～n+m+1行共m行，為網(wǎng)絡(luò)日志內(nèi)容。案例實現(xiàn)--網(wǎng)絡(luò)入侵檢測目錄導航4.14.24.34.44.54.64.7串案例引入串的類型定義、存儲結(jié)構(gòu)及運算數(shù)組廣義表案例分析與實現(xiàn)LeetCode算法練習題Contents【算法練習題4.1】LeetCode125驗證回文串【問題描述】【輸入輸出示例】給定一個字符串s，判斷其是否為回文串，若是，返回true，否則返回false。其中，回文串是指將字符串中所有大寫字母轉(zhuǎn)換為小寫字母，并移除所有非字母數(shù)字字符之后，正讀和反讀相同的字符串。字母和數(shù)字都屬于字母數(shù)字字符。輸入:"Aman,aplan,acanal:Panama"輸出：true解釋："amanaplanacanalpanama"是回文串?！舅惴ň毩曨}4.1】LeetCode125驗證回文串【問題分析】【算法練習題4.1】LeetCode125驗證回文串【算法步驟】①定義left和right兩個指針，初始時left指向第一個字符，right指向最后一個字符。②遍歷字符串s，當left<right時，循環(huán)執(zhí)行以下操作：若left所指字符為非字母數(shù)字字符，則將其向右移動一步，并循環(huán)執(zhí)行此操作，直到left所指字符為字母或數(shù)字字符；若right所指字符為非字母數(shù)字字符，則將其向左移動一步，并循環(huán)執(zhí)行此操作，直到right所指字符為字母數(shù)字字符；若left和right所指字符轉(zhuǎn)換為小寫后不同，則返回false；若left和right所指字符轉(zhuǎn)換為小寫后相同，則left向右移動一步，right向左移動一步。③left>=right，遍歷完字符串s，返回true?！舅惴ň毩曨}4.1】LeetCode125驗證回文串【算法描述】【算法練習題4.1】LeetCode125驗證回文串【算法分析】最壞情況下，需遍歷字符串s的每個字符，時間復雜度為O(n)；只需要兩個指針的額外空間，空間復雜度為O(1)?！舅惴ň毩曨}4.2】LeetCode566重塑矩陣【問題描述】【輸入輸出示例】MATLAB中有一個非常有用的函數(shù)reshape()，該函數(shù)可以將一個m×n的矩陣重塑為一個r×c的新矩陣，且仍保留原始數(shù)據(jù)。給定一個由二維數(shù)組mat表示的m×n矩陣，以及兩個正整數(shù)r和c，分別表示重塑矩陣的行數(shù)和列數(shù)。重塑矩陣時需要將原矩陣的所有元素以相同的行遍歷順序填充。如果給定參數(shù)的reshape操作是可行且合理的，則輸出新的重塑矩陣；否則輸出原矩陣。輸入：mat=[[1,2],[3,4]]，r=1,c=4輸出：[[1,2,3,4]]【算法練習題4.2】LeetCode566重塑矩陣【問題分析】判斷給定參數(shù)的reshape操作是否可行且合理。若不合理，說明無法進行重塑，直接返回原始矩陣mat。若合理，則可以直接從二維矩陣mat得到r行c列的重塑矩陣。若reshape操作可行，可以將二維數(shù)組mat映射為一個一維數(shù)組，可以直接將元素mat[x/n,x%n]直接賦值給重塑矩陣ans[x/c,x%c]，最后返回重塑矩陣ans即可?！舅惴ň毩曨}4.2】LeetCode566重塑矩陣【算法步驟】①初始化，得到原矩陣的行數(shù)和列數(shù)。②若m×n和r×c不相等，則直接返回原矩陣。③若m×n和r×c相等，首先對重塑矩陣進行初始化，然后對于任意的x∈[0,m×n)，循環(huán)執(zhí)行以下操作：將元素mat[x/n,x%n]賦值給重塑矩陣ans[x/c,x%c]。④返回重塑矩陣ans?！舅惴ň毩曨}4.2】LeetCode566重塑矩陣【算法描述】【算法練習題4.2】LeetCode566重塑矩陣【算法分析】在重塑矩陣成功的前提下,時間復雜度為O(rc)，否則直接返回原矩陣，時間復雜度為O(1)；不需要額外空間，空間復雜度為O(1)?！舅惴ň毩曨}4.3】LeetCode3無重復字符的最長子串【問題描述】【輸入輸出示例】給定一個字符串s，請找出其中不含有重復字符的最長子串的長度。輸入:s="abcabcbb"輸出:3解釋:因為無重復字符的最長子串是"abc"，所以其長度為3。【算法練習題4.3】LeetCode3無重復字符的最長子串【問題分析】【算法練習題4.3】LeetCode3無重復字符的最長子串【問題分析】【算法練習題4.3】LeetCode3無重復字符的最長子串【問題分析】【算法練習題4.3】LeetCode3無重復字符的最長子串【問題分析】【算法練習題4.3】LeetCode3無重復字符的最長子串