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