,數(shù)組串廣義表,數(shù)組,數(shù)組是由n個(gè)相同類型的數(shù)據(jù)元素構(gòu)成的有限序列，每個(gè)數(shù)據(jù)元素稱為一個(gè)數(shù)組元素，每個(gè)元素受n個(gè)線性關(guān)系的約束，每個(gè)元素在n個(gè)線性關(guān)系中的序號(hào)稱為該元素的下標(biāo)，并稱該數(shù)組為n維數(shù)組。數(shù)組與線性表的關(guān)系：數(shù)組是線性表的推廣。一維數(shù)組可以看做是一個(gè)線性表；二維數(shù)組可以看做元素是線性表的線性表，以此類推。數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只會(huì)有存取元素和修改元素的操作。,數(shù)組的存儲(chǔ)結(jié)構(gòu),一個(gè)數(shù)組的所有元素在內(nèi)存中占用一段連續(xù)的存儲(chǔ)空間。二維數(shù)組具有兩種存儲(chǔ)方式：1、以行為主順序優(yōu)先存儲(chǔ)：,數(shù)組的存儲(chǔ)結(jié)構(gòu),2、以列為主順序優(yōu)先存儲(chǔ)：,數(shù)組（真題檢測(cè)）,1.設(shè)有一個(gè)二維數(shù)組A108,采用以行序?yàn)橹餍虻拇鎯?chǔ)方式存放于一個(gè)連續(xù)的存儲(chǔ)空間中，若A00的存儲(chǔ)地址是1000，且每個(gè)數(shù)組元素占4個(gè)字節(jié)，求數(shù)組元素A64的內(nèi)存地址。,分析：從A00到A64總共是6*8+5-1=52個(gè)數(shù)組單元，又每個(gè)數(shù)組元素占4個(gè)字節(jié)，所以一共占52*4=208個(gè)字節(jié)。又A00的存儲(chǔ)地址是1000，故A64的內(nèi)存地址為1000+208=1208,矩陣的壓縮存儲(chǔ)（對(duì)稱矩陣）,矩陣的壓縮存儲(chǔ)：將矩陣的元素按照某種分布規(guī)律存儲(chǔ)在較小的存儲(chǔ)單元中。,1、對(duì)稱矩陣的壓縮存儲(chǔ)n階對(duì)稱矩陣：一個(gè)n階的矩陣A中的元素滿足a(ij)=a(ji)(0t的矩陣稱為稀疏矩陣。數(shù)據(jù)對(duì)象集合表示：稀疏矩陣可以使用三元組順序表表示，其中三元組格式為(i,j,e)記錄了非零元素的行號(hào)、列號(hào)以及非零元素。,矩陣的壓縮存儲(chǔ)（真題檢測(cè)）,1.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是（）A.便于進(jìn)行矩陣運(yùn)算B.便于輸入和輸出C.節(jié)省存儲(chǔ)空間D.降低運(yùn)算的時(shí)間復(fù)雜度2.稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即（）。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表3.對(duì)n階對(duì)陣矩陣壓縮存儲(chǔ)時(shí)，需要表長(zhǎng)為（）的順序表A.n/2B.n2/2C.n(n+1)/2D.n(n-1)/2,答案：CC(十字鏈表在后面課程將會(huì)介紹)C,串,字符串簡(jiǎn)稱串，是一種特殊的線性表，它的數(shù)據(jù)元素僅由一個(gè)字符組成。串(String)是由零個(gè)或多個(gè)字符組成的有限序列。串中字符的個(gè)數(shù)稱為串的長(zhǎng)度，含有零個(gè)元素的串叫空串。串中任意連續(xù)的字符組成的子序列稱為該串的子串,包含子串的串稱為主串,某個(gè)字符在串中的序號(hào)稱為這個(gè)字符的位置。通常用子串第一個(gè)字符的位置作為子串在主串中的位置。要注意的是,空格也是串字符集合的一個(gè)元素,由一個(gè)或者多個(gè)空格組成的串稱為空格串(注意,空格串不是空串)。串的邏輯結(jié)構(gòu)和線性表類似,串是限定了元素為字符的線性表。從操作集上講,串和線性表有很大的區(qū)別,線性表的操作主要針對(duì)表內(nèi)的某一個(gè)元素,而串操作主要針對(duì)串內(nèi)的一個(gè)子串。注意：空串和空白串的不同，例如“”和“”分別表示長(zhǎng)度為1的空白串和長(zhǎng)度為0的空串。,串,子串(substring)：串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。子串的序號(hào)：將子串在主串中首次出現(xiàn)時(shí)的該子串的首字符對(duì)應(yīng)在主串中的序號(hào)，稱為子串在主串中的序號(hào)（或位置）。例如，設(shè)有串A和B分別是：A=“這是字符串”，B=“是”則B是A的子串，A為主串。B在A中出現(xiàn)了一次，其中首次出現(xiàn)所對(duì)應(yīng)的主串位置是3。因此，稱B在A中的序號(hào)為3。特別地，空串是任意串的子串，任意串是其自身的子串。串相等：如果兩個(gè)串的串值相等(相同)，稱這兩個(gè)串相等。換言之，只有當(dāng)兩個(gè)串的長(zhǎng)度相等，且各個(gè)對(duì)應(yīng)位置的字符都相同時(shí)才相等。通常在程序中使用的串可分為兩種：串變量和串常量。串常量和整常數(shù)、實(shí)常數(shù)一樣，在程序中只能被引用但不能不能改變其值，即只能讀不能寫。通常串常量是由直接量來表示的，例如語句錯(cuò)誤(“溢出”)中“溢出”是直接量。串變量和其它類型的變量一樣，其值是可以改變。,串,串的存儲(chǔ)表示和實(shí)現(xiàn),串是一種特殊的線性表，其存儲(chǔ)表示和線性表類似，但又不完全相同。串的存儲(chǔ)方式取決于將要對(duì)串所進(jìn)行的操作。串在計(jì)算機(jī)中有3種表示方式：定長(zhǎng)順序存儲(chǔ)表示：將串定義成字符數(shù)組，利用串名可以直接訪問串值。用這種表示方式，串的存儲(chǔ)空間在編譯時(shí)確定，其大小不能改變。堆分配存儲(chǔ)方式：仍然用一組地址連續(xù)的存儲(chǔ)單元來依次存儲(chǔ)串中的字符序列，但串的存儲(chǔ)空間是在程序運(yùn)行時(shí)根據(jù)串的實(shí)際長(zhǎng)度動(dòng)態(tài)分配的。塊鏈存儲(chǔ)方式：是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。,定長(zhǎng)順序存儲(chǔ)表示：這種存儲(chǔ)結(jié)構(gòu)又稱為串的順序存儲(chǔ)結(jié)構(gòu)。是用一組連續(xù)的存儲(chǔ)單元來存放串中的字符序列。所謂定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)，是直接使用定長(zhǎng)的字符數(shù)組來定義，數(shù)組的上界預(yù)先確定。,串,串的堆分配存儲(chǔ)表示：實(shí)現(xiàn)方法：系統(tǒng)提供一個(gè)空間足夠大且地址連續(xù)的存儲(chǔ)空間(稱為“堆”)供串使用。可使用C語言的動(dòng)態(tài)存儲(chǔ)分配函數(shù)malloc()和free()來管理。特點(diǎn)是：仍然以一組地址連續(xù)的存儲(chǔ)空間來存儲(chǔ)字符串值，但其所需的存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配，故是動(dòng)態(tài)的，變長(zhǎng)的。串的鏈?zhǔn)酱鎯?chǔ)表示：串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和線性表的串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類似，采用單鏈表來存儲(chǔ)串，結(jié)點(diǎn)的構(gòu)成是：data域：存放字符，data域可存放的字符個(gè)數(shù)稱為結(jié)點(diǎn)的大?。籲ext域：存放指向下一結(jié)點(diǎn)的指針。若每個(gè)結(jié)點(diǎn)僅存放一個(gè)字符，則結(jié)點(diǎn)的指針域就非常多，造成系統(tǒng)空間浪費(fèi)，為節(jié)省存儲(chǔ)空間，考慮串結(jié)構(gòu)的特殊性，使每個(gè)結(jié)點(diǎn)存放若干個(gè)字符，這種結(jié)構(gòu)稱為塊鏈結(jié)構(gòu)。如圖4-1是塊大小為3的串的塊鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖。,串,如圖4-1是塊大小為3的串的塊鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖。,在這種存儲(chǔ)結(jié)構(gòu)下，結(jié)點(diǎn)的分配總是完整的結(jié)點(diǎn)為單位，因此，為使一個(gè)串能存放在整數(shù)個(gè)結(jié)點(diǎn)中，在串的末尾填上不屬于串值的特殊字符，以表示串的終結(jié)。當(dāng)一個(gè)塊(結(jié)點(diǎn))內(nèi)存放多個(gè)字符時(shí)，往往會(huì)使操作過程變得較為復(fù)雜，如在串中插入或刪除字符操作時(shí)通常需要在塊間移動(dòng)字符。,串,串的模式匹配算法,模式匹配(模范匹配)：子串在主串中的定位稱為模式匹配或串匹配(字符串匹配)。模式匹配成功是指在主串S中能夠找到模式串T，否則，稱模式串T在主串S中不存在。模式匹配的應(yīng)用在非常廣泛。例如，在文本編輯程序中，我們經(jīng)常要查找某一特定單詞在文本中出現(xiàn)的位置。顯然，解此問題的有效算法能極大地提高文本編輯程序的響應(yīng)性能。模式匹配是一個(gè)較為復(fù)雜的串操作過程。迄今為止，人們對(duì)串的模式匹配提出了許多思想和效率各不相同的計(jì)算機(jī)算法。介紹兩種主要的模式匹配算法。,串,簡(jiǎn)單模式匹配算法對(duì)一個(gè)串中某子串的定位操作稱為串的模式匹配,其中待定位的子串稱為模式串。算法的基本思想從主串的第一個(gè)位置起和模式串的第一個(gè)字符開始比較,如果相等,則繼續(xù)逐一比較后續(xù)字符:否則從主串的第二個(gè)字符開始,再重新用上一步的方法與模式串中的字符做比較,以此類推,直到比較完模式串中的所有字符。若匹配成功,則返回模式串在主串中的位置:若匹配不成功,則返回一個(gè)可區(qū)別于主串所有位置的標(biāo)記,如“0”,串,串,該算法簡(jiǎn)單，易于理解。在一些場(chǎng)合的應(yīng)用里，如文字處理中的文本編輯，其效率較高。該算法的時(shí)間復(fù)雜度為O(n*m)，其中n、m分別是主串和模式串的長(zhǎng)度。通常情況下，實(shí)際運(yùn)行過程中，該算法的執(zhí)行時(shí)間近似于O(n+m)。理解該算法的關(guān)鍵點(diǎn)當(dāng)?shù)谝淮蝧ktj時(shí)：主串要退回到k-j+1的位置，而模式串也要退回到第一個(gè)字符（即j=0的位置）。比較出現(xiàn)sktj時(shí)：則應(yīng)該有sk-1=tj-1，sk-j+1=t1，sk-j=t0。,串,KMP算法：該改進(jìn)算法是由D.E.Knuth，J.H.Morris和V.R.Pratt提出來的，簡(jiǎn)稱為KMP算法。其改進(jìn)在于：每當(dāng)一趟匹配過程出現(xiàn)字符不相等時(shí)，主串指示器不用回溯，而是利用已經(jīng)得到的“部分匹配”結(jié)果，將模式串的指示器向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。例：設(shè)有串s=“abacabab”，t=“abab”。則第一次匹配過程如圖所示。,s=“abcbb”i=3|匹配失敗t=“abb”j=3,在i=3和j=3時(shí)，匹配失敗。但重新開始第二次匹配時(shí)，不必從i=1，j=0開始。因?yàn)閟1=t1，t0t1，必有s1t0，又因?yàn)閠0=t2，s2=t2，所以必有s2=t0。由此可知，第二次匹配可以直接從i=3、j=1開始?？傊谥鞔畇與模式串t的匹配過程中，一旦出現(xiàn)sitj，主串s的指針不必回溯，而是直接與模式串的tk(0kj進(jìn)行比較，而k的取值與主串s無關(guān)，只與模式串t本身的構(gòu)成有關(guān)，即從模式串t可求得k值。),串,串,串,KMP算法的思想是：設(shè)目標(biāo)串(主串)為s，模式串為t，并設(shè)i指針和j指針分別指示目標(biāo)串和模式串中正待比較的字符，設(shè)i和j的初值均為1。若有si=tj，則i和j分別加1。否則，i不變，j退回到j(luò)=nextj的位置，再比較si和tj，若相等，則i和j分別加1。否則，i不變，j再次退回到j(luò)=nextj的位置，依此類推。直到下列兩種可能：(1)j退回到某個(gè)下一個(gè)j值時(shí)字符比較相等，則指針各自加1繼續(xù)進(jìn)行匹配。退回到j(luò)=0，將i和j分別加1，即從主串的下一個(gè)字符si+1模式串的t1重新開始匹配和模式串有關(guān)系,串,串（真題檢測(cè)）,1.（判斷題）空格串和空串是相同的（）2.串是一種特殊的線性表，其特殊性表現(xiàn)在（）A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符3.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為（）A.連接B.模式匹配C.求字串D.求串長(zhǎng)4.（填空）串的兩種最基本的存儲(chǔ)方式是：5.兩個(gè)串相等的充分必要條件是（）A.兩串長(zhǎng)度相等B.兩串所包含的字符集合相等C.兩串長(zhǎng)度相等且對(duì)應(yīng)位置的字符相等D.兩串長(zhǎng)度相等且所包含的字符集合相等,答案：錯(cuò)BB順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式C,串（真題檢測(cè)）,1.設(shè)串S1=datastructureswithjava，S2=it，則子串定位函數(shù)index（S1，S2）的值為（）A.15B.16C.18D.192.在用KMP算法進(jìn)行模式匹配時(shí)，模式串“ababaaababaa”的next數(shù)組值為（）A.0，1，2，3，4，5，6，7，8，9，9，9B.0，1，2，1，2，1，1，1，1，2，1，2C.0，1，1，2，3，4，2，2，3，4，5，6D.0，1，2，3，0，1，2，3，2，2，3，43.子串“str”在主串“datastructure”中的位置是:,答案：CC5,廣義表,廣義表簡(jiǎn)稱表，它是線性表的推廣。一個(gè)廣義表是n（n0）個(gè)元素的一個(gè)序列，若n=0時(shí)則稱為空表。由于廣義表中有兩種數(shù)據(jù)元素，因此需要有兩種結(jié)構(gòu)的節(jié)點(diǎn)一種是表結(jié)點(diǎn)，一種是原子結(jié)點(diǎn)。廣義表具有如下重要的特性：（1）廣義表中的數(shù)據(jù)元素有相對(duì)次序；（2）廣義表的廣度定義為最外層包含元素個(gè)數(shù)；（3）廣義表的深度定義為所含括弧的重?cái)?shù)。其中原子的深度為0，空表的深度為1；（4）廣義表可以共享；一個(gè)廣義表可以為其他廣義表共享；這種共享廣義表稱為再入表；（5）廣義表可以是一個(gè)遞歸的表。一個(gè)廣義表可以是自已的子表。這種廣義表稱為遞歸表。遞歸表的深度是無窮值,長(zhǎng)度是有限值；（6）任何一個(gè)非空廣義表GL均可分解為表頭head(GL)=a1和表尾tail(GL)=(a2,an)兩部分。（重點(diǎn)！）,廣義表的表示,我們規(guī)定用小寫字母表示原子，用大寫字母表示廣義表的表名。例如：A=()B=(e)C=(a,(b,c,d)D=(A,B,C)=(),(e),(a,(b,c,d)E=(a,(a,b),(a,b),c)其中A是一個(gè)空表，其長(zhǎng)度為0；B是只含有單個(gè)原子e的表，其長(zhǎng)度為1；C有兩個(gè)元素，一個(gè)是原子a，另一個(gè)是子表，其長(zhǎng)度為2；D有三個(gè)元素，每個(gè)元素都是一個(gè)表，其長(zhǎng)度為3；E中只含有一個(gè)元素，是一個(gè)表，它的長(zhǎng)度為1；,廣義表的存儲(chǔ)結(jié)構(gòu),廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu),廣義表中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)，因此，難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素可用一個(gè)節(jié)點(diǎn)表示。由于廣義表中有兩種數(shù)據(jù)元素，因此需要有兩種結(jié)構(gòu)的節(jié)點(diǎn)一種是表結(jié)點(diǎn)，一種是原子結(jié)點(diǎn)。表結(jié)點(diǎn)由三個(gè)域組成：標(biāo)志域、指示表頭的指針的指針域和指示表尾的指針域；而原子域只需兩個(gè)域：標(biāo)志域和值域。注意：表結(jié)點(diǎn)的tag=1，原子結(jié)點(diǎn)的tag=0,廣義表的存儲(chǔ)結(jié)構(gòu),廣義表中的head與tail運(yùn)算,根據(jù)表頭、表尾的定義可知：任何一個(gè)非空廣義表的表頭是表中第一個(gè)元素，它可以是原子，也可以是子表，而其表尾必定是子表。也就是說，廣義表的head操作，取出的元素是什么，那么結(jié)果就是什么。但是tail操作取出的元素外必須加一個(gè)表“（）“舉一個(gè)簡(jiǎn)單的列子：已知廣義表LS=(a,b,c),(d,e,f),如果需要取出這個(gè)e這個(gè)元素，那么使用tail和head如何將這個(gè)取出來。利用上面說的，tail取出來的始終是一個(gè)表，即使只有一個(gè)簡(jiǎn)單的一個(gè)元素，tail取出來的也是一個(gè)表，而head取出來的可以是一個(gè)元素也可以是一個(gè)表。解：tail(LS)=(d,e,f)head(tail(LS)=(d,e,f)tail(head(tail(LS)=(e,f)/無論如何都會(huì)加上這個(gè)()括號(hào)head(tail(head(tail(LS)=e/head可以去除單個(gè)元素,廣義表（真題檢測(cè)）,1.廣義表A=(a,b,(c,d),(e,(f,g),則head(tail(head(tail(tail(A)=（）A.(g)B.(d)C.cD.d,分析：head-tail操作取廣義表中元素操