【正文】 t的第一個字符在主串 s中的下標；若比較完主串 s的所有字符序列，不存在一個和模式串 t相等的子串，則模式匹配失敗，函數(shù)返回 1。 塊鏈就是每個結(jié)點的數(shù)據(jù)元素域包括若干個字符。 有單字符結(jié)點鏈和塊鏈兩種。 其中， value為存儲串值的字符類型數(shù)組名， count表示串值的長度。 串值長度的第一種表示方法下，串的成員變量應包括如下兩項： char[] value。 表示串的長度通常有兩種方法： （ 1）設置一個串的長度參數(shù)。 （ 9）查找子串 index(subStr, start)：在當前對象串的start下標開始，查找是否存在子串 subStr。 （ 7）刪除子串 delete(beginIndex, endIndex)：刪除當前對象串中從 beginIndex下標開始、至 endIndex下標的前一下標止的子串 。 （ 4）取子串 substring(beginIndex, endIndex)：取當前對象串中從 beginIndex下標開始、至 endIndex下標的前一下標止的子串 （ 5）連接 concat(str)：把串 str連接到當前對象串的末尾。 （ 2）求長度 length()：返回串的長度。 串的抽象數(shù)據(jù)類型 數(shù)據(jù)集合： 串的數(shù)據(jù)集合可以表示為字符序列 s0, s1,… , sn 1， 每個數(shù)據(jù)元素的數(shù)據(jù)類型為字符類型。 一個字符在一個串中的位置序號（為大于等于 0的正整數(shù)）稱為該字符在串中的 位置 。 一個串中任意個連續(xù)的字符組成的子序列稱為該串的子串 。當優(yōu)先級隊列中有若干個進程排隊等待系統(tǒng)響應，并且 CPU資源空閑時，進程管理系統(tǒng)就可從優(yōu)先級隊列中找出優(yōu)先級最高的進程首先出隊列，從而既達到了當系統(tǒng)繁忙時，所有進程都排隊等待，又達到了實時性要求高的進程先被服務的雙重要求。 優(yōu)先級隊列的應用 操作系統(tǒng)中的進程管理軟件中就使用了優(yōu)先級隊列。 （ 2）對于順序優(yōu)先級隊列來說，數(shù)據(jù)元素由兩部分組成，一部分是原先意義上的數(shù)據(jù)元素，另一部分是優(yōu)先級。 用鏈式存儲結(jié)構(gòu)存儲的優(yōu)先級隊列稱作 鏈式優(yōu)先級隊列 。 1 鏈式隊列的存儲結(jié)構(gòu) 0a. . .1a 1?na∧ 2?na r e a rf r o n t 優(yōu)先級隊列 優(yōu)先級隊列 是帶有優(yōu)先級的隊列。amp。設計數(shù)器為 count，初始時置count=0；每當入隊列操作成功就使 count加 1；每當出隊列操作成功就使 count減 1。amp。amp。設標志位為 tag，初始時置 tag=0；每當入隊列操作成功就置 tag=1；每當出隊列操作成功就置 tag=0。這樣，就不會出現(xiàn)順序隊列數(shù)組的頭部已空出許多存儲空間，但隊尾卻因數(shù)組下標越界而引起溢出的假溢出問題。因此，解決的方法是把順序隊列所使用的存儲空間構(gòu)造成一個邏輯上首尾相連的循環(huán)隊列。 43210=5frontrearCBA432105front=rear=C432105front=rear=EDC432105front=rear=(a) (b) (c) (d)2 順序隊列的“假溢出”問題 順序隊列因多次入隊列和出隊列操作后出現(xiàn)的有存儲空間但不能進行入隊列操作的溢出稱作 假溢出 。 public boolean notEmpty()。 public Object delete() throws Exception。若隊列非空，則函數(shù)返回 true，否則函數(shù)返回 false。 （ 3）取隊頭數(shù)據(jù)元素 getFront()：取隊頭數(shù)據(jù)元素并由函數(shù)返回。 2 操作集合 （ 1）入隊列 append(obj)：把數(shù)據(jù)元素 obj插入隊尾。 下圖是一個依次向隊列中插入數(shù)據(jù)元素 a0,a1,...,an1后的示意圖，其中， a0是當前隊頭數(shù)據(jù)元素， an1是當前隊尾數(shù)據(jù)元素。 隊列中允許進行插入操作的一端稱為隊尾，允許進行刪除操作的一端稱為隊頭。括號匹配和表達式計算是編譯軟件中的基本問題 ， 其軟件設計中都需要使用堆棧 。 依次向鏈式堆棧入棧數(shù)據(jù)元素 a0, a1, a2, ..., an1后，鏈式堆棧的示意圖如圖所示。 堆棧有兩端 ， 插入數(shù)據(jù)元素和刪除數(shù)據(jù)元素的一端為棧頂 ， 另一端為棧底 。 0 1 2 3 4 5m a x S t a c k S i z e 1=棧 頂s t a c kt o p棧 底 0a 1a 2a 4a3a 鏈式堆棧 鏈式存儲結(jié)構(gòu)的堆棧稱作 鏈式堆棧 。 順序堆棧 1 順序堆棧的存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)的堆棧稱作 順序堆棧 。 （ 3）取棧頂數(shù)據(jù)元素 getTop()：取堆棧當前棧頂?shù)臄?shù)據(jù)元素并由函數(shù)返回。 ２操作集合 （ 1）入棧 push(obj)：把數(shù)據(jù)元素 obj插入堆棧。 從輸入和輸出數(shù)據(jù)元素的位置關系看 ， 堆棧的功能和一種火車調(diào)度裝置的功能類同 。 堆棧中允許進行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。這樣，軟件工業(yè)將擺脫了小作坊工作方式，像現(xiàn)代的其他工業(yè)一樣，可以進行大規(guī)模的協(xié)作生產(chǎn)或開發(fā)。不僅如此，面向?qū)ο笤O計方法的模塊化軟件、數(shù)據(jù)封裝、信息隱藏等特點，還可以使軟件設計可以像其他工業(yè)產(chǎn)品一樣，可以大規(guī)模協(xié)作開發(fā)。這樣，就可以用仿真指針構(gòu)造仿真的單鏈表（或仿真的雙向鏈表）。方法是在數(shù)組中增加一個（或兩個） int類型的變量域，這些變量用來表示后一個（或前一個）數(shù)據(jù)元素在數(shù)組中的下標。 ... 1?ia ...1?na① ② 1?naheadp1?iaia 循環(huán)雙向鏈表的刪除過程 仿真鏈表 在鏈式存儲結(jié)構(gòu)中，我們實現(xiàn)數(shù)據(jù)元素之間的次序關系依靠指針。 0a ia . . . 1?na. . .x1?ia. . .① ② ③ ④ ph e a ds圖 215 循環(huán)雙向鏈表的插入過程 循環(huán)雙向鏈表的刪除過程如圖 216所示 。 ia1?ia 1?iap圖 214 雙向鏈表的關系 循環(huán)雙向鏈表的插入過程如圖 215所示 。 帶頭結(jié)點的循環(huán)雙向鏈表 （ a）空鏈表；（ b）非空鏈表 0a 1a ...(a)(b)1?naheadhead 在雙向鏈表中 ， 有如下關系：設對象引用 p表示雙向鏈表中的第 i個結(jié)點 ， 則 i+1個結(jié)點 ， i個結(jié)點 ， 即 == p；同樣地 ， i1個結(jié)點 ， i個結(jié)點 ， 即 == p。 p r i o r n e x td a t a 雙向鏈表結(jié)點的圖示結(jié)構(gòu) 圖 213是帶頭結(jié)點的循環(huán)雙向鏈表的圖示結(jié)構(gòu)。 雙向鏈表 在雙向鏈表中，每個結(jié)點包括三個域，分別是 element域、 next域和 prior域，其中 element域為數(shù)據(jù)元素域， next域為指向后繼結(jié)點的對象引用， prior域為指向前驅(qū)結(jié)點的對象引用。 雙向鏈表 是每個結(jié)點除后繼指針外還有一個前驅(qū)指針 。 帶頭結(jié)點的循環(huán)單鏈表結(jié)構(gòu)如下： ...0a 1a 1?na(a) (b)head head（ a）空鏈表；（ b）非空鏈表 帶頭結(jié)點的循環(huán)單鏈表的操作實現(xiàn)方法和帶頭結(jié)點的單鏈表的操作實現(xiàn)方法類同 ， 差別僅在于： （ 1） 在構(gòu)造函數(shù)中 ， 要加一條 = head 語句 ， 把初始時的帶頭結(jié)點的循環(huán)單鏈表設計成圖 211 （ a） 所示的狀態(tài) 。 當要處理的數(shù)據(jù)元素序列具有環(huán)型結(jié)構(gòu)特點時 ， 適合于采用循環(huán)單鏈表 。 循環(huán)單鏈表是單鏈表的另一種形式 ， 其結(jié)構(gòu)特點是鏈表中最后一個結(jié)點的指針不再是結(jié)束標記 ， 而是指向整個鏈表的第一個結(jié)點 ， 從而使單鏈表形成一個環(huán) 。 單鏈表的主要缺點是每個結(jié)點中要有一個指針，因此單鏈表的空間利用率略低于順序表的。 和順序表相比，單鏈表的主要優(yōu)點是不需要預先給出數(shù)據(jù)元素的最大個數(shù)。當實際的數(shù)據(jù)元素個數(shù)超過了預先給出的個數(shù)，會發(fā)生異常。另外，單鏈表取數(shù)據(jù)元素操作的時間復雜度也為 O（ n）。 但是 ， 如果再增加一個表示單鏈表當前結(jié)點位置的成員變量 ， 則有些成員函數(shù)的設計將更加方便 。 結(jié)點類的成員變量有兩個：一個是數(shù)據(jù)元素 ， 另一個是表示下一個結(jié)點的對象引用 （ 即指針 ） 。 在帶頭結(jié)點單鏈表中第一個數(shù)據(jù)元素結(jié)點前插入一個新結(jié)點的過程如圖所示 。 而如果采用帶頭結(jié)點的單鏈表結(jié)構(gòu) ， 算法實現(xiàn)時 ， p指向頭結(jié)點 ， 改變的是 p指針的 next指針的值 ， 而頭指針 head的值不變 。另外，還有一些不同情況需要考慮。算法實現(xiàn)時，首先把插入位置定位在要插入結(jié)點的前一個結(jié)點位置，然后把 s表示的新結(jié)點插入單鏈表中。當選用帶頭結(jié)點的單鏈表時，插入和刪除操作的實現(xiàn)方法比不用帶頭結(jié)點單鏈表的實現(xiàn)方法簡單。 存放第一個數(shù)據(jù)元素的結(jié)點稱作第一個數(shù)據(jù)元素結(jié)點 ， 或稱首元結(jié)點 。 我們把指向單鏈表的指針稱為單鏈表的 頭指針 。 單鏈表的結(jié)構(gòu) 單鏈表 是構(gòu)成鏈表的每個結(jié)點只有一個指向直接后繼結(jié)點的指針 。 根據(jù)結(jié)點構(gòu)造鏈的方法不同，鏈表主要有單鏈表、單循環(huán)鏈表和循環(huán)雙向鏈表三種。 鏈式存儲結(jié)構(gòu) 是用指針把相互直接關聯(lián)的結(jié)點（即直接前驅(qū)結(jié)點或直接后繼結(jié)點）鏈接起來。 鏈式存儲結(jié)構(gòu)是基于指針實現(xiàn)的。 順序表的主要缺點是：需要預先給出（很難準確）數(shù)組的最大數(shù)據(jù)元素個數(shù)，另外，插入和刪除操作時需要移動較多的數(shù)據(jù)元素。 順序表支持隨機讀取，因此，順序表取數(shù)據(jù)元素的時間復雜度為 O（ 1）。 循環(huán)移動數(shù)據(jù)元素的效率和插入的位置 i有關 ， 最壞情況是 i = 0， 需移動 size個數(shù)據(jù)元素；最好情況是 i = size， 需移動 0個數(shù)據(jù)元素 。 順序表的效率分析 插入和刪除是順序表中時間復雜度最高的成員函數(shù) 。順序表類實現(xiàn)接口 List。 . . .1a 2a 3a 4a 5am a x S i z e 1l i s t A r r a y0 1 2 3 4 5 6s i z e = 60a 順序表類 類包含成員變量和成員函數(shù)。 順序表 順序表的存儲結(jié)構(gòu)如圖所示 。 對于線性表 ， 數(shù)組把線性表的數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存單元中 。 操作集合 （ 1）求當前數(shù)據(jù)元素個數(shù) length() （ 2）插入數(shù)據(jù)元素 insert(i, obj) （ 3）刪除數(shù)據(jù)元素 delete(i) （ 4）取數(shù)據(jù)元素 getData(i) （ 5）線性表是否空 isEmpty() 線性 表抽象數(shù)據(jù)類型 順序存儲結(jié)構(gòu)的線性表稱作 順序表 。 空線性 表用符號（ ） 表示 。 線性 表 是一種可以在任意位置進行插入和刪除數(shù)據(jù)元素操作的 、 由 n（ n ≥ 0） 個相同類型數(shù)據(jù)元素 a0, a1, a2, ..., an1組成的線性結(jié)構(gòu) 。 第 2章 線性表 線性表 順序表 單鏈表 循環(huán)單鏈表 雙向鏈表 仿真鏈表 面向?qū)ο蟮能浖O計方法 本章主要知識點： ● 線性表的定義，順序存儲結(jié)構(gòu)，鏈式存儲結(jié)構(gòu) ● 順序表類的設計方法，順序表插入和刪除操作的實現(xiàn)方法，順序表插入和刪除操作的時間復雜度 ● 單鏈表類的設計方法，單鏈表插入和刪除操作的實現(xiàn)方法，單鏈表插入和刪除操作的時間復雜度，順序表和單鏈表的特點對比 ● 循環(huán)單鏈表和循環(huán)雙向鏈表的結(jié)構(gòu)和特點 線性 表 線性 表的定義 如果一個數(shù)據(jù)元素序列滿足： （ 1）除第一個和最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素只有一個前驅(qū)數(shù)據(jù)元素和一個后繼數(shù)據(jù)元素； （ 2）第一個數(shù)據(jù)元素沒有前驅(qū)數(shù)據(jù)元素； （ 3）最后一個數(shù)據(jù)元素沒有后繼數(shù)據(jù)元素。 Java類庫 （ 即 Java API） 提供了許多系統(tǒng)定義的包 。 Java語言的工具包 數(shù)據(jù)結(jié)構(gòu)課程討論的數(shù)據(jù)結(jié)構(gòu)問題