《算法與數(shù)據(jù)結(jié)構(gòu)》第2章常用數(shù)據(jù)結(jié)構(gòu)ppt.ppt

《《算法與數(shù)據(jù)結(jié)構(gòu)》第2章常用數(shù)據(jù)結(jié)構(gòu)ppt.ppt》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第2章常用數(shù)據(jù)結(jié)構(gòu)ppt.ppt（113頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、算法與數(shù)據(jù)結(jié)構(gòu),第2章 常用數(shù)據(jù)結(jié)構(gòu),第2章 常用數(shù)據(jù)結(jié)構(gòu),2.1 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 2.2 數(shù)組 2.3 串,2.1 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu),2.1.1 數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)類型 2.1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 2.1.3 抽象數(shù)據(jù)類型,數(shù)據(jù),計算機中的數(shù)據(jù)在計算機內(nèi)的最原始形式僅是一組組二進制代碼，程序設(shè)計語言以這種代碼為基礎(chǔ)建立起了所有的數(shù)據(jù)。 數(shù)據(jù)的概念不再只是那些用數(shù)字組合而成的各種數(shù)據(jù)了，如整數(shù)、小數(shù)、實數(shù)、虛數(shù)、復(fù)數(shù)、指數(shù)和對數(shù)等。 隨著計算機科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)的概念也相應(yīng)地發(fā)生了一些重要的變化。,數(shù)據(jù)（續(xù)）,數(shù)據(jù)（Data）是信息的載體，是對自然界客觀事物的符號表示。 在計算機

2、科學(xué)與技術(shù)學(xué)科，數(shù)據(jù)泛指那些能夠被計算機接收、識別、存儲、加工和處理的對象的全體。 換句話說，數(shù)據(jù)是對那些能夠有效地輸入到計算機中并且能夠被計算機程序所加工和處理的符號全體的總稱。 只要是能被計算機識別、存儲、加工和處理的都屬于數(shù)據(jù)的范疇。,數(shù)據(jù)元素,數(shù)據(jù)的基本單位是數(shù)據(jù)元素（Data Element），有時也稱作元素、結(jié)點、頂點、記錄等。 一個數(shù)據(jù)元素也可以由若干個數(shù)據(jù)項（Data Item）組成。 數(shù)據(jù)項是具有獨立含義的數(shù)據(jù)的不可再分割的最小標(biāo)識單位。例如，一個單位的職工花名冊中，每一位職工的信息就是一個數(shù)據(jù)元素；職工信息中包含有職工編號、姓名、性別、民族、年齡、政治面貌、參加工作時間、工

3、資級別、職稱、職務(wù)等項目，這每一個項目都是某個職工數(shù)據(jù)元素中的一個數(shù)據(jù)項。,數(shù)據(jù)組織的三個層次,數(shù)據(jù)組織的三個層次分別是數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項。 數(shù)據(jù)可以由若干個數(shù)據(jù)元素組成，數(shù)據(jù)元素又可以由若干個數(shù)據(jù)項組成。 數(shù)據(jù)項是對數(shù)據(jù)元素屬性的描述，數(shù)據(jù)元素是對客觀世界中某個獨立個體的數(shù)據(jù)描述。 在C語言中，數(shù)據(jù)元素可以用結(jié)構(gòu)體來描述，每個數(shù)據(jù)項則是結(jié)構(gòu)體中的一個分量。,數(shù)據(jù)元素與數(shù)據(jù)對象,計算機中的數(shù)據(jù)可以按類型來劃分，劃分的結(jié)果就是數(shù)據(jù)對象。 所謂數(shù)據(jù)對象（Data Object），是指具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如整數(shù)數(shù)據(jù)對、字母字符數(shù)據(jù)對象。 在一個具體問題中，數(shù)據(jù)元素具有

4、相同性質(zhì)，屬于同一數(shù)據(jù)對象，數(shù)據(jù)元素是數(shù)據(jù)對象的一個實例。如在前述的職工花名冊中，所有的職工是一個數(shù)據(jù)對象，不同的職工的信息是不同的數(shù)據(jù)元素，它們都是職工數(shù)據(jù)對象的不同實例，其數(shù)據(jù)元素值是各數(shù)據(jù)項的一個具體描述。,數(shù)據(jù)類型,數(shù)據(jù)類型（Data Type）是對在計算機中表示的同一數(shù)據(jù)對象及其在該數(shù)據(jù)對象上的一組操作的總稱。 如整數(shù)數(shù)據(jù)，在計算機中它是集合minintmaxint上的整數(shù)（其中minint和maxint分別是最小整數(shù)和最大整數(shù)，在不同的計算機中表示的值不同；且這個集合是有窮集合，是數(shù)學(xué)意義上的無窮集合的一個子集），在這個集合上可以進行的操作有加、減、乘、整除和求模等算術(shù)運算以及等于

5、、不等于、大于、小于、大于等于和小于等于等關(guān)系運算。 數(shù)據(jù)對象整數(shù)以及在整數(shù)集合上的算術(shù)運算和關(guān)系運算等操作一起構(gòu)成了整型這個數(shù)據(jù)類型。,數(shù)據(jù)類型（續(xù)）,數(shù)據(jù)類型有簡單（或原子）數(shù)據(jù)類型和結(jié)構(gòu)數(shù)據(jù)類型之分。 簡單數(shù)據(jù)類型是由程序設(shè)計語言提供的一些基本類型。如整型、實型、布爾型和字符型等，其值不可再分解。 結(jié)構(gòu)數(shù)據(jù)類型是由程序設(shè)計語言中提供的構(gòu)造機制來定義的數(shù)據(jù)類型。如數(shù)組、文件、結(jié)構(gòu)體、共用體等，其值可以再分解；它的構(gòu)成成分可以是簡單數(shù)據(jù)類型，也可以是結(jié)構(gòu)數(shù)據(jù)類型。 數(shù)據(jù)類型的概念，是程序設(shè)計語言和程序設(shè)計過程中的一個非常重要的概念。,數(shù)據(jù)類型的特征,類型決定了變量或表達式所有可能取值的全體成

6、員集合。 每一個值隸屬于且僅隸屬于某一類型。 任何常量、變量或表達式的類型，都可以從其形式上或所處的上下文關(guān)系中推斷出來，無須了解在程序運行時計算出的具體值。 每一種操作都要求一定類型的操作數(shù)據(jù)，且得出一定類型的操作結(jié)果。 一種類型的值及其在該類型上規(guī)定的基本操作的性質(zhì)可由一組公理來闡明。 高級程序設(shè)計語言使用類型信息去防止程序中出現(xiàn)無意義的結(jié)構(gòu)，又由類型信息確定在計算機中的數(shù)據(jù)表示和數(shù)據(jù)處理方法。,2.1 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu),2.1.1 數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)類型 2.1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 2.1.3 抽象數(shù)據(jù)類型,數(shù)據(jù)結(jié)構(gòu)的基本概念,數(shù)據(jù)結(jié)構(gòu)（Data Structure）是指計算機程

7、序中所操作的對象數(shù)據(jù)以及數(shù)據(jù)元素之間的相互關(guān)系和運算。 在任何問題中，數(shù)據(jù)元素之間都不會是獨立的，總是存在著這樣或那樣的關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系也稱作結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)包含以下三個方面的內(nèi)容： 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運算及實現(xiàn),數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。 它只抽象地反映數(shù)據(jù)元素集合的結(jié)構(gòu)，而不管其存儲方式，可用一個二元組給出如下的形式定義： Data-Structure （D,R） 其中： D是數(shù)據(jù)元素的集合； R是D上關(guān)系的集合。 從結(jié)構(gòu)的觀點出發(fā)，一般可將數(shù)據(jù)結(jié)構(gòu)分為兩大類： 線性結(jié)構(gòu) 如線性表、棧、隊列、串、數(shù)組和文件等； 非線性結(jié)構(gòu)

8、如樹、圖和集合等。,數(shù)據(jù)的存儲結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)及數(shù)據(jù)元素之間的關(guān)系在計算機內(nèi)存中的表示，也稱作數(shù)據(jù)的物理結(jié)構(gòu)或存儲映像。 主要的存儲方式有順序存儲和鏈?zhǔn)酱鎯煞N，此外還有索引存儲和散列存儲等其它方式。 從邏輯結(jié)構(gòu)到存儲結(jié)構(gòu)稱之為映像。 同一邏輯結(jié)構(gòu)采用不同的存儲結(jié)構(gòu)存儲，就會得到不同的數(shù)據(jù)結(jié)構(gòu)。這是因為映像變了，使結(jié)構(gòu)有了改變，使得實現(xiàn)邏輯結(jié)構(gòu)上所定義的運算的算法也隨之改變了。,數(shù)據(jù)的運算及實現(xiàn),數(shù)據(jù)的運算及實現(xiàn)。程序中的數(shù)據(jù)運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的運算，但運算的實現(xiàn)要在相應(yīng)的存儲結(jié)構(gòu)上進行。 常用的運算有檢索、插入、刪除、更新、排序等。 在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義數(shù)據(jù)的運算時，

9、只考慮這些運算是“做什么”，而不考慮它“如何做”，是抽象運算；只有在選定了某種數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)時，才去考慮如何具體實現(xiàn)這些運算，即運算的實現(xiàn)。 運算的實現(xiàn)依賴于所選取的存儲結(jié)構(gòu)，也依賴于所選用的程序設(shè)計語言。,線性結(jié)構(gòu),在線性結(jié)構(gòu)中，D中數(shù)據(jù)元素之間存在著一對一的次序關(guān)系。 其邏輯特征為： 存在一個惟一被稱作“第一個”的數(shù)據(jù)元素，它沒有前趨只有一個直接后繼；有時也稱作開始結(jié)點； 存在一個惟一被稱之為“最后一個”的數(shù)據(jù)元素，它沒有后繼只有一個直接前趨；有時也稱作終端結(jié)點； 其它數(shù)據(jù)元素都有且僅有一個直接前趨（immediate predecessor），也有且僅有一個直接后繼（immediat

10、e successor）。 如職工花名冊、學(xué)生成績表、向量、數(shù)組、購物時排的隊等都是線性結(jié)構(gòu)的例子。,非線性結(jié)構(gòu)樹型結(jié)構(gòu),在非線性結(jié)構(gòu)中，D中數(shù)據(jù)元素之間不存在一對一的次序關(guān)系。 樹型結(jié)構(gòu)中的數(shù)據(jù)元素之間，存在著一對多的層次關(guān)系，在樹型結(jié)構(gòu)中： 沒有直接前趨的結(jié)點稱之為根結(jié)點； 除根結(jié)點外每個結(jié)點有且僅有一個直接前趨（稱之為雙親結(jié)點）； 沒有直接后繼的結(jié)點稱之為葉結(jié)點，除葉結(jié)點外每個結(jié)點都有一個或多個直接后繼（稱之為孩子結(jié)點）。 樹的例子很多，如族譜中的家族樹、政府機構(gòu)中的行政樹、計算機文件管理中的目錄樹、編譯程序中用到的語法樹等。,樹型結(jié)構(gòu)示意圖,非線性結(jié)構(gòu)圖型結(jié)構(gòu),非線性結(jié)構(gòu)中的圖結(jié)構(gòu)，其

11、數(shù)據(jù)元素之間既不存在線性結(jié)構(gòu)中的一對一次序關(guān)系，也不存在樹型結(jié)構(gòu)中的一對多層次關(guān)系。 在圖型結(jié)構(gòu)中，D中數(shù)據(jù)元素之間的關(guān)系是多對多的網(wǎng)狀關(guān)系。 換句話說，圖是一種網(wǎng)狀結(jié)構(gòu)，任意兩個數(shù)據(jù)元素之間都可能相關(guān)；其中的每一個數(shù)據(jù)元素，既可以有多個直接前趨，也可以有多個直接后繼。 如交通網(wǎng)絡(luò)圖，課程之間的先后修關(guān)系圖，軟件開發(fā)過程中所用到的程序圖、控制流圖、數(shù)據(jù)流圖等都是圖型結(jié)構(gòu)的例子。,圖型結(jié)構(gòu)示意圖,非線性結(jié)構(gòu)集合結(jié)構(gòu),非線性結(jié)構(gòu)中的集合結(jié)構(gòu)，其D中數(shù)據(jù)元素之間的關(guān)系是“屬于同一個集合”。 集合是數(shù)據(jù)元素關(guān)系極為松散的一種結(jié)構(gòu)。通常是用其它結(jié)構(gòu)來表示集合。,存儲表示方式順序存儲,順序存儲方式，是在計

12、算機內(nèi)存儲器中開辟一片地址連續(xù)的存儲單元順序存放數(shù)據(jù)中的各個元素；它把邏輯上相鄰的數(shù)據(jù)元素存放在物理上相鄰的存儲單元中，利用物理上的鄰接關(guān)系表示邏輯上的先后次序關(guān)系，這種存儲表示方式稱作順序存儲結(jié)構(gòu)（Sequential Storage Structure）。 順序存儲結(jié)構(gòu)是一種最基本的存儲方法，通常借助于程序設(shè)計語言中的數(shù)組來實現(xiàn)。 主要用于線性數(shù)據(jù)結(jié)構(gòu)的存儲，對于非線性結(jié)構(gòu)進行線性化處理后也可實現(xiàn)順序存儲。,存儲表示方式鏈?zhǔn)酱鎯?鏈?zhǔn)酱鎯Ψ绞?，是把?shù)據(jù)元素和反映元素間關(guān)系（后繼和/或前趨）的地址一塊存儲在計算機內(nèi)；它不要求在內(nèi)存儲器中開辟的存儲單元地址連續(xù)，數(shù)據(jù)元素可以存放在內(nèi)存儲器中的任

13、意位置，借助指示數(shù)據(jù)元素存儲地址的指針表示元素間的邏輯關(guān)系，這種存儲表示方式稱作鏈?zhǔn)酱鎯Y(jié)構(gòu)（Linked Storage Structure）。 鏈?zhǔn)酱鎯Y(jié)構(gòu)也是一種基本的存儲表示方法，通常借助于程序設(shè)計語言中的指針來實現(xiàn)。 主要用于樹型結(jié)構(gòu)和圖型結(jié)構(gòu)數(shù)據(jù)的存儲，為了某種特殊的需要也常用于一些線性結(jié)構(gòu)的存儲。,其他的存儲表示方式,存儲表示方式還有索引存儲方式和散列存儲方式，通常是為了檢索的方便所采用的存儲表示方法。 一般地說，這幾種基本的存儲表示方法，既可以單獨使用，也可以組合起來使用。 選擇何種存儲結(jié)構(gòu)要依具體問題的要求而定，既要考慮問題表示和運算的方便性，也還會考慮到實現(xiàn)算法的時間和空間

14、效率要求。,數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是密切相關(guān)的兩個方面： 算法的設(shè)計都取決于所選定的數(shù)據(jù)的邏輯結(jié)構(gòu)； 算法的實現(xiàn)則依賴于所采用的存儲結(jié)構(gòu)。 各種數(shù)據(jù)結(jié)構(gòu)，分別提供了不同類型的數(shù)據(jù)在作為計算機程序數(shù)據(jù)時的組織、管理、存儲、運算和處理的方法和技術(shù)。 有些數(shù)據(jù)結(jié)構(gòu)，在程序設(shè)計語言中已經(jīng)實現(xiàn)了或提供了定義數(shù)據(jù)類型的方法或手段。如各種基本類型，數(shù)組、字符串等 有些數(shù)據(jù)結(jié)構(gòu)，在程序設(shè)計語言中沒有實現(xiàn)，要靠程序設(shè)計人員利用語言中提供的某些設(shè)施去實現(xiàn)或模擬實現(xiàn)，如棧、隊列、樹、二叉樹、圖、網(wǎng)絡(luò)等。 在程序設(shè)計語言中實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)稱之為數(shù)據(jù)類型。,2.1 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu),2.1

15、.1 數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)類型 2.1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 2.1.3 抽象數(shù)據(jù)類型,抽象數(shù)據(jù)類型,抽象的本質(zhì)就是抽取反映問題本質(zhì)的東西，忽略掉非本質(zhì)的細節(jié)。 數(shù)據(jù)類型是對同一數(shù)據(jù)對象及其在該數(shù)據(jù)對象上的一組操作的抽象，抽象的結(jié)果是把用戶不必了解的一切細節(jié)都封裝在類型之中，對使用數(shù)據(jù)類型的用戶來說是實現(xiàn)了信息隱藏（Information Hiding）。 用戶在使用數(shù)據(jù)類型時，既不需要了解該數(shù)據(jù)類型在計算機內(nèi)部是如何表示的，也不需要知道其操作是如何實現(xiàn)的，只須集中精力考慮所要求解的問題應(yīng)該如何去解決。 抽象數(shù)據(jù)類型的概念，是我們熟知的數(shù)據(jù)類型概念的引伸和發(fā)展，是數(shù)據(jù)抽象和運算抽象緊密結(jié)合的

16、產(chǎn)物。,抽象數(shù)據(jù)類型（續(xù)）,抽象數(shù)據(jù)類型（Abstract Data Type簡記為ADT）是指一個數(shù)據(jù)模型以及定義在該數(shù)據(jù)模型上的一組操作。這里的數(shù)據(jù)模型，是要求解問題中的各種數(shù)據(jù)的總和；通常，把這些數(shù)據(jù)可以組織成為一個或多個數(shù)據(jù)結(jié)構(gòu)。 當(dāng)數(shù)據(jù)模型表現(xiàn)為一個數(shù)據(jù)結(jié)構(gòu)時，抽象數(shù)據(jù)類型就是這個數(shù)據(jù)結(jié)構(gòu)以及定義在這個數(shù)據(jù)結(jié)構(gòu)上的一組運算；這種情況是我們討論和學(xué)習(xí)抽象數(shù)據(jù)類型概念的基礎(chǔ)，也是數(shù)據(jù)結(jié)構(gòu)課程對抽象數(shù)據(jù)類型定義的根本要求。 當(dāng)數(shù)據(jù)模型表現(xiàn)為多個數(shù)據(jù)結(jié)構(gòu)時，我們可以先定義以單個數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)的各個抽象數(shù)據(jù)類型，然后在此基礎(chǔ)上（需要的話）定義抽象級別更高的抽象數(shù)據(jù)類型，并利用它們構(gòu)造最終的問題

17、求解算法。,抽象數(shù)據(jù)類型的定義,抽象數(shù)據(jù)類型的定義，僅取決于它的一組邏輯特性，而與它在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。 也就是說不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用；如同數(shù)據(jù)類型一樣，是使用與實現(xiàn)分離、實行封裝和信息隱藏。 抽象數(shù)據(jù)類型可以通過已有的數(shù)據(jù)類型來表示和實現(xiàn)，利用已有的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，利用已經(jīng)實現(xiàn)了的操作來完成新的操作。,抽象數(shù)據(jù)類型自然數(shù)的ADT描述,ADT NaturalNumber Data Objects:D=xxNaturalNumber,0 xmaxint Data Relation:R=xNaturalNumber, 1xmaxi

18、nt Elementary Operation: Zero( ) 返回0 IsZero(x) If(x==0) 返回True else 返回False Add(x,y) If(x+y<=maxint) 返回x+y else 返回maxint Equal(x,y) If(x==y) 返回True else 返回False Successor(x) If(x==maxint) 返回x else 返回x+1 Subtract(x,y) If(x

19、型是算法設(shè)計和程序設(shè)計中的重要概念，這個概念明確地把數(shù)據(jù)結(jié)構(gòu)與作用在該結(jié)構(gòu)上的運算緊密地聯(lián)系起來。 數(shù)據(jù)結(jié)構(gòu)上的運算依賴于其具體表示，有了數(shù)據(jù)結(jié)構(gòu)的具體表示和運算的具體實現(xiàn)，運算的效率隨之確定。 需要指出的是，基本數(shù)據(jù)類型已隱含著數(shù)據(jù)結(jié)構(gòu)和定義在該結(jié)構(gòu)上的運算的統(tǒng)一，只是當(dāng)時尚未形成抽象數(shù)據(jù)類型的概念罷了。 每一種基本數(shù)據(jù)類型都連帶著一組基本運算，只是由于這些基本數(shù)據(jù)類型中數(shù)據(jù)結(jié)構(gòu)的具體表示和基本運算的具體實現(xiàn)都很規(guī)范，都通過內(nèi)置而隱藏起來使人們看不到它們的封裝，人們習(xí)慣于在算法與程序設(shè)計中使用基本數(shù)據(jù)類型名和相關(guān)的運算名而不問其究竟。,抽象數(shù)據(jù)類型（續(xù)）,抽象數(shù)據(jù)類型的設(shè)計和實現(xiàn)不可能象基本

20、數(shù)據(jù)類型那樣可以規(guī)范、內(nèi)置和一勞永逸。 首先要根據(jù)問題的具體要求，定義該抽象數(shù)據(jù)類型需要包含哪些信息，并根據(jù)功能確定公共界面的服務(wù)，使用者可以使用公共界面中的服務(wù)對該抽象數(shù)據(jù)類型進行操作。 另一方面，把抽象數(shù)據(jù)類型的實現(xiàn)作為私有部分封裝在其實現(xiàn)模塊內(nèi)，讓使用者看不到，也不能直接操作該類型所存儲的數(shù)據(jù)，只能通過界面中的服務(wù)來訪問這些數(shù)據(jù)。,第2章 常用數(shù)據(jù)結(jié)構(gòu),2.1 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 2.2 數(shù)組 2.3 串,2.2 數(shù)組,數(shù)組（Arrays）是程序設(shè)計語言中最基本和最重要的數(shù)據(jù)結(jié)構(gòu)，也是程序設(shè)計實踐中最常用的數(shù)據(jù)結(jié)構(gòu)。 在程序中引入數(shù)組的充分理由是： 為了求解問題有引入數(shù)組的必要性，如需要

21、記住一組值等； 基于問題求解算法的效率考慮，引入數(shù)組可使算法效率更高； 基于概念上或運算處理上的自然、簡單和方便性方面考慮需要引入數(shù)組。,2.2 數(shù)組,2.2.1 數(shù)組及其運算 2.2.2 數(shù)組的順序存儲結(jié)構(gòu) 2.2.3 特殊矩陣的壓縮存儲,數(shù)組的概念和特點,把具有相同性質(zhì)的一組元素組織在一起形成數(shù)組結(jié)構(gòu)。 數(shù)組結(jié)構(gòu)的特點是： 數(shù)組元素的個數(shù)固定，元素間的邏輯關(guān)系由數(shù)組元素的序號（即數(shù)組的下標(biāo)）來體現(xiàn)。 每一個數(shù)組元素都具有相同的結(jié)構(gòu)。 數(shù)組元素的下標(biāo)具有上下界約束且下標(biāo)有序，下標(biāo)與數(shù)組元素的對應(yīng)關(guān)系使得數(shù)組元素可以隨機訪問。 所以，可以說數(shù)組結(jié)構(gòu)是一個線性的、均勻的、其元素可以隨機訪問的數(shù)據(jù)

22、結(jié)構(gòu)。也可以說數(shù)組是由數(shù)組元素和下標(biāo)構(gòu)成的有序?qū)Y(jié)構(gòu)，結(jié)構(gòu)中的每一個數(shù)據(jù)元素都與一組下標(biāo)有關(guān)。,數(shù)組的運算,對于數(shù)組結(jié)構(gòu)的運算操作，是對其數(shù)據(jù)元素的操作。通常只有賦值和讀取數(shù)組元素兩種操作： 賦值：給定一組下標(biāo)，把指定值（如初始值、修改值、運算值等）存入相應(yīng)的數(shù)組元素中； 讀取：給定一組下標(biāo)，讀取相應(yīng)的數(shù)組元素（通常是為了使用其值或打印輸出等目的）。,數(shù)組,在程序設(shè)計語言中，與數(shù)組結(jié)構(gòu)對應(yīng)的數(shù)據(jù)類型是數(shù)組類型，即在程序中引入數(shù)組要用語言中提供的數(shù)組類型說明方法說明。 如在C語言中，int A8就說明了一個一維整型數(shù)組A；進而就可以對A施加不同的操作，一般方法是利用循環(huán)控制變量值的變化，從下標(biāo)下

23、界到上界之間（或相反次序）訪問相應(yīng)的數(shù)組元素，其一般格式是 for(i=0; i<8; i++) 對A的第i個元素執(zhí)行某個指定的操作 當(dāng)數(shù)組的下標(biāo)為一個時，稱之為一維數(shù)組 當(dāng)數(shù)組的下標(biāo)為兩個或兩個以上時，稱之為二維數(shù)組或多維數(shù)組。,2.2 數(shù)組,2.2.1 數(shù)組及其運算 2.2.2 數(shù)組的順序存儲結(jié)構(gòu) 2.2.3 特殊矩陣的壓縮存儲,數(shù)組的順序存儲結(jié)構(gòu),順序存儲結(jié)構(gòu)，是指在計算機內(nèi)存中安排一片地址連續(xù)的空間存儲數(shù)據(jù)。 數(shù)組的線性的、均勻的結(jié)構(gòu)和計算機內(nèi)存單元的一維結(jié)構(gòu)，決定了對數(shù)組采用順序存儲結(jié)構(gòu)是最佳選擇。 對于一維數(shù)組，按下標(biāo)順序分配存儲空間是很自然的。 對于二維數(shù)組和多維數(shù)組。就

24、有一個把數(shù)組元素按照某種方式排成一個線性序列的問題，即次序約定問題。,二維數(shù)組的順序存儲結(jié)構(gòu)舉例,二維數(shù)組可以把它看作是由每一行元素作為一個元素構(gòu)成的一維數(shù)組（行為主序）， 二維數(shù)組也可以看作是由每一列元素作為一個元素構(gòu)成的一維數(shù)組（列為主序）。 一種約定，就可以得到二維數(shù)組所有元素的一個惟一的線性排列：a11a12a1na21a22a2nam1am2amn或a11a21am1a12a22am2a1na2namn。 若選定一種約定，則每個數(shù)組元素相對于存儲區(qū)域起始地址的位置也就隨之確定了。,行為主序的優(yōu)先存儲策略,行為主序的優(yōu)先存儲策略是將數(shù)組元素按行優(yōu)先關(guān)系排列，第i+1行的元素緊跟在第i行

25、中元素的后面；同一行中的元素以列下標(biāo)次序排列。,列為主序的優(yōu)先存儲策略,列為主序的優(yōu)先存儲策略是將數(shù)組元素按列優(yōu)先關(guān)系排列，第j+1列中的元素緊跟在第j列中元素的后面；同一列中的元素以行下標(biāo)次序排列。,二維數(shù)組的元素存儲地址計算公式,我們設(shè)每個數(shù)組元素需要e個存儲單元存放；并記第一個數(shù)組元素的存儲地址為loc(a11)，即存儲區(qū)間的起始地址，也稱作數(shù)組的基地址。 若以行為主序優(yōu)先存儲，考慮數(shù)組元素aij的地址計算公式。因為aij是第i行第j列的數(shù)組元素，其前面已經(jīng)存放了i-1行共（i-1）*n個元素，在第j行中前面已經(jīng)存放了j-1個元素，故在aij前面共存放了（i-1）*n+ j-1個元素；由

26、每個元素占用空間e和基地址loc(a11)可得 loc(aij)= loc(a11)+((i-1)*n+j-1)*e 同理可推出以列為主序優(yōu)先存儲的地址計算公式為 loc(aij)= loc(a11)+((j-1)*m+i-1)*e,元素存儲地址計算公式（續(xù)）,前面討論的公式是假設(shè)了數(shù)組的下標(biāo)下界均為1時的計算公式。 對于一般情況下的數(shù)組Ac1d1,c2d2 在行為主序之下aij的地址計算公式為 loc(aij)= loc(a11)+((i-c1)*(d2-c2+1)+j-c2)*e 在列為主序之下aij的地址計算公式為 loc(aij)= loc(a11)+((i-c2)*(d1-c1+

27、1)+i-c1)*e,2.2 數(shù)組,2.2.1 數(shù)組及其運算 2.2.2 數(shù)組的順序存儲結(jié)構(gòu) 2.2.3 特殊矩陣的壓縮存儲,特殊矩陣的壓縮存儲,在科學(xué)計算和工程應(yīng)用中，常常要用到矩陣的概念。由于矩陣具有元素個數(shù)固定且下標(biāo)有序排列的特點，使用二維數(shù)組表示既自然又可方便矩陣的各種運算。但是在有些情況下，如特殊矩陣和稀疏矩陣，采用二維數(shù)組的存儲方式會浪費大量存儲空間。為了節(jié)省空間，對這類矩陣可壓縮存儲。 所謂壓縮存儲，是指為多個值相同的元素只分配一個元素的存儲空間，對零元素不分配存儲空間。 所謂特殊矩陣是指矩陣中元素分布有一定規(guī)律，如對角矩陣、三對角矩陣、上三角矩陣、下三角矩陣、對稱矩陣等。,1.

28、對角矩陣的壓縮存儲,對角矩陣的特點是除了主對角線上的元素外其余元素都為零。 對于n階方陣，只有n個非零元素，只需要n個元素空間順序存儲即可。其非零元素壓縮存儲位置k與矩陣下標(biāo)的對應(yīng)關(guān)系為k=i或k=j，通過這個關(guān)系可對矩陣中的非零元素隨機存取。,壓縮存儲,2.三對角矩陣的壓縮存儲,三對角矩陣是除主對角線及主對角線上下各一個元素外，其余元素都為零的矩陣。 對三對角矩陣的壓縮存儲方法是，按行為主序優(yōu)先存儲方法把非零區(qū)的三對角元素依次順序存儲到一片連續(xù)的存儲空間中。 其映像關(guān)系可以這樣來分析：對處于三對角區(qū)的元素aij，它前面的i-1行中有非零元素3*(i-1)-1個，它處于本行中的第j-i+2個非

29、零元素處，所以為第3*( i-1)-1+ j-i+2=2*( i-1)+ j個非零元素，此式也正好符合第一行的兩個非零元素的情況。故有 k=2*( i-1)+ j,三對角矩陣的壓縮存儲圖示,壓縮存儲,3.上三角矩陣的壓縮存儲,上三角矩陣是指矩陣的主對角線以下的所有元素均為同一常數(shù)c或零的n階矩陣。 對上三角矩陣的壓縮存儲方法是，對處于下三角（不含主對角線）的常數(shù)c，在最后分配一個元素空間；對處于上三角（含主對角線）的每個元素按行為主序優(yōu)先存儲方法依次順序存儲分配空間，需要n*(n+1)/2個元素空間；共需要n*(n+1)/2+1個元素空間。 其映像關(guān)系為，若ij，aij處于下三角區(qū)，值必為

30、常數(shù)c，存儲分配在n*(n+1)/2+1處；若ij，aij處在上三角區(qū)，在前i-1行共存儲的元素數(shù)為n+(n-1)++(n-i+2)=(i-1)*(2n-i+2)/2個，在第i行它是第j-i+1個，故aij為第(i-1)*(2n-i+2)/2+ j-i+1=(i-1)*(2n-i)/2+j個存儲分配的元素。所以有,上三角矩陣的壓縮存儲圖示,壓縮存儲,4.下三角矩陣的壓縮存儲,下三角矩陣與上三角矩陣對應(yīng)，其常數(shù)在上三角區(qū)（不含主對角線），壓縮存儲方法也類似，以行為主序存儲下三角部分。 處在下三角的元素aij，其前i-1行共有i*(i-1)/2個元素，在第i行它處于第j個位置，即aij處于存儲分配

31、區(qū)的第i*(i-1)/2+j個。于是我們有,下三角矩陣的壓縮存儲圖示,壓縮存儲,5.對稱矩陣的壓縮存儲,在n階矩陣中，若元素滿足aij=aji則稱之為對稱矩陣。 由于對稱矩陣中元素關(guān)于主對角線對稱，因此只需要存儲其上三角中的元素或下三角中的元素，使對稱元素共享同一存儲空間。 假如只存儲下三角中的元素，則需存儲元素總數(shù)為n*(n+1)/2個，按行為主序順序存儲，其映像關(guān)系為 也可以給出一個統(tǒng)一的對應(yīng)關(guān)系為 k= I*(I-1)/2+J 其中，I=max(i,j)，J=min(i,j)。,第2章 常用數(shù)據(jù)結(jié)構(gòu),2.1 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 2.2 數(shù)組 2.3 串,2.3 串,所謂串，就是我

32、們在高級語言程序設(shè)計課程中學(xué)習(xí)和使用過的字符串，是大家熟知的概念。 串是許多軟件系統(tǒng)的操作對象，如字符編輯系統(tǒng)、情報檢索系統(tǒng)、詞法分析系統(tǒng)、符號處理系統(tǒng)、語言翻譯系統(tǒng)等，有著十分廣泛的應(yīng)用。 本節(jié)著重討論串的存儲結(jié)構(gòu)以及主要運算的實現(xiàn)，如順序存儲分配的三種方式、堆式存儲分配策略以及在“向量存儲，定長結(jié)構(gòu)”基礎(chǔ)上幾種串運算的實現(xiàn)算法，并簡要介紹漢字串的概念。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長順序存儲及運算實現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動態(tài)存儲及運算實現(xiàn) 2.3.5 漢字串,串的基本概念,串（String）是由零個或多個字符組成的有限序列。 記作: s=

33、“a1a2an” (n0) 其中：s是串名，用雙引號括起來的字符序列是串的值（不含雙引號）；ai（1in）是相應(yīng)程序設(shè)計語言中允許使用的字符集中的任意字符；n為串中的字符個數(shù)，稱作串的長度。 零個字符的串稱作空串，它的長度為零，串內(nèi)無任何字符。 要注意空串與空格串的區(qū)別，空格串中有一個或多個空格字符，串的長度大于零。,串的基本概念（續(xù)）,串中任意多個連續(xù)字符組成的子序列稱作該串的子串（Substring），包含子串的串稱作該子串的主串。字符在串中的序號稱作該字符在串中的位置，子串在主串中的位置用子串的第一個字符在主串中的位置來表示。 兩個串相等是指這兩個串的值相等，即兩個串長度相等且對應(yīng)字符

34、都相同時才相等。 串結(jié)構(gòu)的形式化定義為 string=(D,R) 其中：D= aiaicharacter，i=1,2n，n0, R=ai-1,aiD，i=1,2n 。,串的基本運算（六種）,StrAssign(s,chars)：串賦值。把字符串常量chars的值賦給串變量s。 StrCopy(s,t)：串復(fù)制。把串變量t的值復(fù)制到串變量s中。 StrCompare(s,t)：串比較。若st返回值0，若s=t返回值=0，若s

35、存入串變量l中返回。例如，若s=“baodao”，t=“taiwan”，則l=“baodaotaiwan”。 SubString(t,s,i,len)：求子串。把串s 中第i個字符開始的長度為len的字符序列存入串變量t中返回。該運算要求1iStrLength(s)+1且0lenStrLength(s)- i +1。,串的其它運算（四種）,其它的串運算都可以由這六種基本運算來實現(xiàn)。 下面四種其它的串運算都有著重要的應(yīng)用： StrInsert(s,i,t)：串插入。運算的結(jié)果是把t串插入到s串中第i個字符之前得到的新串。其中，1iStrLength(s)+1。 StrDelete(s,i,len

36、)：串刪除。運算的結(jié)果是從s串中刪去自第i個字符起的len 個字符后得到的新串。其中，1iStrLength(s)，0lenStrLength(s)- i +1。 StrIndex(s,t)：子串定位。若在主串s中存在等于t的子串，則返回t在s中首次出現(xiàn)的位置，否則返回值為-1。其中要求子串t為非空串。 StrReplace(s,t,v)：子串替換。運算的結(jié)果是以串v替換所有在串s中出現(xiàn)的和非空串t相等的不重疊的子串后得到的新串。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長順序存儲及運算實現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動態(tài)存儲及運算實現(xiàn) 2.3.5 漢字串,串的

37、定長順序存儲,當(dāng)一維數(shù)組的基類型是字符類型，形成的字符數(shù)組即字符串或串。 在高級程序設(shè)計語言中，大都為字符串設(shè)立了專門的數(shù)據(jù)類型。 在C語言中，有串常量和串變量的概念。用雙引號括起來的字符序列為字符串常量，也可以用宏定義#define來定義字符串常量的標(biāo)識符，如 #define CITY shanghai 對于字符串變量，C語言的說明為一維字符型數(shù)組，如 static char C100； 為字符串分配一個固定長度的一組地址連續(xù)的存儲單元的存儲分配方法稱之為定長順序存儲分配。,定長順序存儲緊縮方式,計算機按字編址、每個單元存放四個字符。 如串s=“data structure 2.3”

38、的緊縮存儲如下： 其中字符串長度18存儲在開始處，“ ”表示空格字符，共占用五個存儲單元。 緊縮方式對串長是顯式地直接存儲，字符依次順序放在連續(xù)的幾個單元中。這種存儲方式的優(yōu)點是充分地利用了空間，然而四個字符一個地址運算不太方便。,定長順序存儲非緊縮方式,計算機按字編址，每個單元存放一個字符。串的長度不顯式存儲，由串中字符占存儲單元的數(shù)目來隱式確定。 非緊縮存儲方式方便了串運算，但存儲空間沒有得到有效利用。 例如對串s=“data structure 2.3”的非緊縮存儲如右圖所示。,定長順序存儲單字節(jié)存儲方式,計算機按字節(jié)編址，每個字節(jié)存放一個字符。 每個地址對應(yīng)一個字節(jié)，一個字節(jié)正好存放

39、一個字符。這時的串長度也不必存儲，由串占用的字節(jié)數(shù)隱式確定；也可用特殊字符作為串的結(jié)束標(biāo)志，如用“0”作結(jié)束標(biāo)志。 這種存儲方式既不浪費空間，又使串中每個字符與惟一地址對應(yīng)方便了運算，對于按字節(jié)編址的計算機而言是非常合適的。 例如對串s=“data structure 2.3”的單字節(jié)存儲方式如右圖所示。,定長順序存儲結(jié)構(gòu)的運算實現(xiàn),為了方便討論，我們把串的類型說明改寫成如下形式： #define STRINGLEN 81 struct string int len; static char chSTRINGLEN； typedef struct string STRING；

40、 并假定串尾以“0”作結(jié)束標(biāo)志。 由于串賦值和串復(fù)制在高級程序設(shè)計語言中是通過賦值語句來完成的，所以在這里只討論其余四種基本運算，即串比較、求串長、串聯(lián)接和求子串運算。,1.串比較,int StrCompare(s,t) /*串的比較，若st返回值0，若s=t返回值=0，否則返回值chi=t-chi) 該算法的主要時間開銷在于兩串相等時的逐個字符比較，比較次數(shù)為字符串的長度，所以在最壞情況下的時間復(fù)雜度為O(mins-len,t-len)；在最好情況下是當(dāng)兩串的第一個字符不等時，只需要O(1)的時間，與問題規(guī)模即串的長度無關(guān)。,2.求串長（1）,按假設(shè)的串類型說明，由于有串長域len故可直接

41、返回其值即可。 算法描述如下： int StrLength(s)/*求串長即串s中字符的個數(shù)*/ STRING *s; return s-len; /*直接返回串長域的值即可*/,2.求串長（2）,在C語言中是沒有設(shè)串長域的，需要對一維字符數(shù)組中的字符個數(shù)統(tǒng)計結(jié)果。 所以改寫算法為： int StrLength(s) STRING *s; int i=0; /*初始化數(shù)組下標(biāo)和串長域len*/ s-len=0; while(s-chi!=0) s-len++； return s-len； 該算法的主要時間開銷在于逐個字符統(tǒng)計串長度的循環(huán)，其時間復(fù)雜度為O(s-len)。,3.串聯(lián)接,

42、在實現(xiàn)串的聯(lián)接運算時，要注意兩串s和t聯(lián)接后的結(jié)果串L超過定長的問題，即：s-len+t-len=STRINGLEN時結(jié)果串超過定長STRINGLEN，此時算法中輸出相應(yīng)提示信息。 其算法描述如下： void StrConcat(l,s,t) STRING *l,*s,*t; int i,j; if(s-len+t-lenSTRINGLEN) printf(“結(jié)果串L的長度超過串的定長STRINGLEN!n”); else for(i=0;s-chi!=0;i++) l-chi=s-chi; for(j=0;t-chj!=0;j++) l-chi+j=t-cht; li+j=0;

43、 l-len=s-len+t-len; ,3.串聯(lián)接（續(xù)）,該算法的時間開銷主要在于復(fù)制兩個串中字符到結(jié)果串中，其復(fù)制字符個數(shù)為兩個串的長度之和，故其時間復(fù)雜度為O(s-len+t-len)。 串的聯(lián)接運算不滿足交換律，這一點由串聯(lián)接的定義是顯而易見的。 然而，串的聯(lián)接運算是滿足結(jié)合律的；在多個串聯(lián)接時，只要位置次序不變，先聯(lián)接哪兩個都無所謂，最終結(jié)果都是一樣的。,4.求子串,在設(shè)計求子串算法時要注意算法的健壯性要求，即要檢查子串開始位置i和子串長度len的合法性。 當(dāng)ilen時，子串開始位置非法； 當(dāng)lens-len-i時，子串的長度非法。 對于這些非法的數(shù)據(jù)（參數(shù)），要給出相應(yīng)的錯誤信

44、息。 求子串的算法描述如下： void SubString(t,s,i,len) STRING *t,*s; int i,len; int j; if((i=s-len)) printf(“子串的開始位置i越界錯誤n”);,4.求子串（續(xù)）,else if((lens-len-i)) printf(“子串的長度len越過主串錯誤n”); else for(j=0;jchj=s-chi /*將所求子串存入t串中*/ t-chj=0; /*為子串t添加結(jié)束標(biāo)志*/ t-len=len; /*設(shè)置子串長度*/ 該算

45、法的主要時間開銷在于從主串s中取出子串存于t中，而子串的最大長度等于主串，主串最長為預(yù)先定義好的定長STRINGLEN，所以其時間復(fù)雜度為O(STRINGLEN)。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長順序存儲及運算實現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動態(tài)存儲及運算實現(xiàn) 2.3.5 漢字串,模式匹配,子串的定位操作通常稱作模式匹配，子串t稱作模式，在主串s中確定t的位置的過程稱作匹配過程。 模式匹配在文本編輯、文件檢索和各種串處理系統(tǒng)中有著廣泛的應(yīng)用，因此它是最重要的串運算之一。然而模式匹配不是串的基本運算，它可以借用串的基本運算來實現(xiàn)。 利用串比較、求串長和

46、求子串三種基本操作實現(xiàn)模式匹配的算法描述： int StrIndex(s,t) /*匹配成功返回子串位置，否則返回-1*/ STRING *s,*t; int n,m,i,bool; STRING *l; n=StrLength(s); /*求主串s的長度于n*/,模式匹配（續(xù)）,m=StrLength(t); /*求模式串t的長度于m*/ i=0; bool=-1; while((i0) return i; else return -1; ,簡單的模式匹配算法,簡單的模式匹配算法的思想是： 從主串s的第一個字符開始和模式t的第一個字符比較， 若相等則繼續(xù)逐個比較

47、后續(xù)字符， 若某一次對應(yīng)字符不相等則從主串s 中的第二個字符起再重新和模式t的每個字符逐個比較。 依次類推，直到模式t中每個字符都和主串s中的一個連續(xù)字符序列對應(yīng)相等則匹配成功，函數(shù)值為模式t中第一個字符所對應(yīng)的字符在主串s中的序號； 若掃描完主串s后還未找到模式t 的出現(xiàn)則匹配失敗，函數(shù)值為-1。,簡單的模式匹配的過程描述,對于模式串t=“abcac”和主串s=“ababcabcacbab”使用算法Index(s,t)的匹配過程如下：,簡單的模式匹配的過程描述(續(xù)),簡單的模式匹配的算法（續(xù)）,算法Index(s,t)簡單，算法思想自然，匹配過程容易理解。 在許多應(yīng)用場合如文本編輯等，匹配效

48、率也較高。 在這樣一種較好的匹配情況下，即每趟中不成功的匹配都發(fā)生在第一對字符比較時，其時間復(fù)雜度為O(n+m)。 然而在最壞情況下，即每趟不成功的匹配都發(fā)生在模式串t中最后一個字符時，其時間復(fù)雜度為O(n*m)，算法效率很低。,一種改進的模式匹配算法,這種改進的模式匹配算法是D.E.Knuth與J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)的，因此人們稱它為克努特莫里斯普拉特算法，簡稱為KMP算法。 該算法可以在O(n+m)的時間數(shù)量級上完成串的模式匹配運算。 其改進思想是充分利用部分匹配的信息，不需回溯主串指示器變量i，而是在匹配過程中出現(xiàn)字符比較不等時，將模式串t盡可能遠地向右滑動一段

49、距離后繼續(xù)進行比較。,一種改進的模式匹配算法（續(xù)）,回顧前述的匹配過程示例，在第三趟的匹配中當(dāng)i=6、j=4比較字符不等時，又從i=3、j=0重新開始比較。仔細觀察可以發(fā)現(xiàn)，在i=3和j=0、i=4和j=0、i=5和j=0這三次比較都是不必進行的；這是由于從第三趟部分匹配的結(jié)果就可以得出主串中的第4、5和6個字符（即i=3、4和5）和模式串中的第2、3和4個字符（即j=1、2和3）相同為b、c和a，而模式串中的第一個字符（即j=0）是a無需再和這三個字符進行比較，僅需將模式串向右滑動三個字符的位置進行i=6、j=1時的字符比較即可。同理，在第一趟匹配中出現(xiàn)字符不等時，僅需將模式串向右滑動兩個字

50、符位置進行i=2、j=0時的字符比較。,一種改進的模式匹配的匹配過程,值得注意的是在整個匹配過程中i指示器變量的值沒有回溯。,改進的模式匹配的一般化思路,對于模式串t=“t0t1tm-1”和主串s=“s0s1sn-1”，當(dāng)匹配過程中sitj產(chǎn)生失配時，模式串向右滑動多遠距離？ 或者說失配時i指示器變量不回溯，主串中第i個字符應(yīng)該與模式串中哪個字符再繼續(xù)比較？ 設(shè)此時應(yīng)該與模式串中第k(k

51、j-k+2tj-1”=“si-k+1si-k+2si-1” 由前面兩式可以推出下式： “t0t1tk-2”=“tj-k+1tj-k+2tj-1”,改進的模式匹配的一般化思路,“t0t1tk-2”=“tj-k+1tj-k+2tj-1”等式說明，在某趟匹配過程中sitj失配時，如果模式串中前j-1個字符中存在首尾相同的最大子串長度為k-1，即模式t中前k-1個字符與tj前的k-1個字符對應(yīng)相等時，模式t就可以向右滑動k個字符位置即si與tk繼續(xù)比較了。 模式t中的每一個tj都對應(yīng)一個k值，這個k值表示當(dāng)在tj處失配時模式t應(yīng)向右滑動的字符數(shù)，它僅依賴于模式t而與主串s無關(guān)。 令nextj=k，則

52、可引出next函數(shù)的定義如下：,改進的模式匹配的一般化思路,由next函數(shù)的定義可推出模式“abaabcac”的next函數(shù)值為： 有了next函數(shù)之后，匹配過程可以這樣進行：令指示器變量i和j的值都為0，若在匹配過程中si=tj；則i和j分別加1，否則i不變而j退到nextj的位置再比較；若相等i和j各加1，否則j退到下一個next值的位置，依此類推直到下面兩種可能： 一是退到某next值（nextnextnextj）時字符比較相等，指示器變量值各加1后繼續(xù)比較； 另一種是退到值為零（即模式的第一個字符失配），此時需將模式繼續(xù)向右滑動一個位置，從主串的下一個字符si+1重新開始匹配。,改進

53、的模式匹配的KMP算法描述,int index_KMP(s,t) STRING *s, *t; int i,j; if((t-len==0)||(s-lenlen)) return -1; else i=0; j=0; while((ilen) ,運用算法index_KMP的匹配過程,求模式串t的next函數(shù)值的算法,void getnext(STRING *t, int next) /*求模式串t的next函數(shù)值并存入數(shù)組next中*/ int i,j; i=0; j=-1; nexti=0; /*初始化指示器變量并給nex

54、t0賦零值*/ while(i len) if((j==0)||(t-chi==t-chj) i++; j++; nexti=j; else j=nextj; ,一種改進的模式匹配算法（續(xù)）,算法getnext的時間復(fù)雜度為O(m)。通常模式串的長度m要比主串的長度n小得多，因此對整個匹配算法KMP來說增加這點求next函數(shù)的時間是值得的。 需要說明的是，算法index的時間復(fù)雜度雖然是O(m*n)，但在一般情況下其實際執(zhí)行時間近似于O(m+n)，所以至今仍被采用。 算法index_KMP僅當(dāng)模式串與主串之間存在許多部分匹配的情況下才顯得比算法

55、index快得多。 index_KMP算法的最大特點是不需回溯主串的指示器變量i，整個匹配過程只需從頭到尾掃描主串一遍，特別適用于從外設(shè)讀入龐大文件邊讀入邊匹配，無需回頭重讀。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長順序存儲及運算實現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動態(tài)存儲及運算實現(xiàn) 2.3.5 漢字串,串的堆式動態(tài)存儲,在處理串的應(yīng)用程序中，所處理的串的長度相差往往較大，處理過的串值長度變化往往也較大。 采用定長順序存儲在多數(shù)串的串長較小時其空間利用率低，且使某些運算如串聯(lián)接和串置換等受到限制或產(chǎn)生錯誤結(jié)果。 因此，在許多實際應(yīng)用的串處理系統(tǒng)中采用的是堆式動態(tài)

56、存儲分配策略。,堆式動態(tài)存儲的思想,應(yīng)用系統(tǒng)在內(nèi)存中開辟一個容量很大且地址連續(xù)的一片存儲空間，作為存放所有串值的可利用空間即堆空間。 例如一維數(shù)組store char storemaxsize 表示堆空間，其中maxsize表示這片連續(xù)存儲空間的最大容量。 設(shè)整形變量free指示該空間中尚未分配區(qū)間的開始地址（初始值為1）。 每當(dāng)產(chǎn)生一個串時，應(yīng)用程序就在執(zhí)行過程中動態(tài)地從free指示的位置為串值分配一個長度與串長相同的存儲空間，并相應(yīng)修改free的值； 同時建立該串的一個描述，指示串的長度和該串在store中的第一個字符位置。,串的堆式動態(tài)存儲分配示意圖,其中：length指示串值序列的長

57、度， start指示串值序列在store中的開始地址。,串的存儲映像,借助length和start在堆結(jié)構(gòu)的串名與串值之間建立起一個對應(yīng)關(guān)系，稱作串名的存儲映像。 所有的串名存儲映像構(gòu)成了一張為系統(tǒng)中所有串名和串值之間建立一一對應(yīng)關(guān)系的映像表（或符號表）。,堆式動態(tài)存儲的串的類型說明,#define MAXSIZE 10000 /*MAXSIZE為堆的最大容量*/ struct string /*定義串為結(jié)構(gòu)體*/ int length; /*串長度*/ int start; /*串在堆中的開始位置*/ typedef struct string STRING;

58、 /*定義串類型標(biāo)識符為STRING*/ char storeMAXSIZE; /*定義堆為一維數(shù)組store*/ int free; /*堆store中尚未分配區(qū)間的開始地址指示器變量*/,堆式動態(tài)存儲的串賦值算法,該運算把存儲于字符串?dāng)?shù)組chars中的字符串常量存入堆store中，并為s建立存儲映像。在邏輯上即為串變量s賦一個字符串常量值。 其算法描述如下： void StrAssign(s,chars) STRING *s; char chars; int i,len; i=0; /*為統(tǒng)計字符串常量中的字符個數(shù)初始化*/ while(cha

59、rsi!=0) /*統(tǒng)計chars中字符個數(shù)*/ i++; len=i;,堆式動態(tài)存儲的串賦值算法(續(xù)),if((lenMAXSIZE)) printf(“串常量為空串或堆的尚未分配區(qū)間空間不足n”)； else for(i=0;istart=free; /*建立存儲映像*/ s-length=len; free=free+len; /*修改堆中的指示器變量free的值*/ ,堆式動態(tài)存儲的串復(fù)制算法,該運算把堆中的串t復(fù)制到s中去。算法如下： void StrCopy(s,t) STRING *s,*t; int i; if(free-1+t-

60、lengthMAXSIZE) printf(“堆中空間不足”)； else for(i=0;ilength;i++) /*逐字符復(fù)制* storefree+i=storet-start+i; s-length=t-length; /*建立存儲映像*/ s-start=free; free=free+t-length; 串復(fù)制運算也可以共享堆中t的存儲空間，只建立s的存儲映像，但若對其中之一修改就會影響到另一個。,堆式動態(tài)存儲的串聯(lián)接算法,只要分別將s串和t串復(fù)制到store中為l開辟的存儲區(qū)，并建立l的存儲映像即可完成串聯(lián)接運算。算法如下：

61、void StrConcat(l,s,t) STRING *l,*s,*t; STRING *p; /*設(shè)一個內(nèi)部串變量p*/ StrCopy(l,s); /*復(fù)制s到l中去*/ StrCopy(p,t); /*復(fù)制t到p中去*/ l-length=s-length+t-length; /*修改l的存儲映像中的串長*/ 注意，為什么算法中沒有修改l的開始位置？又為什么未見修改堆中指示器變量free的語句？這是因為第一個串復(fù)制語句已使l的開始位置到位，而第二個串復(fù)制語句已使free的值指向尚未分配區(qū)的開始位置，故只需修改串長即可。,堆式動態(tài)存儲的求子串算法,和串復(fù)制運算一樣，求子

62、串運算也有復(fù)制和共享兩種實現(xiàn)方法。這里給出共享實現(xiàn)算法如下： void SubString(t,s,i,len) /*將s中第i個字符開始的len個字符構(gòu)成的子串送到t中*/ STRING *t,*s; int i,len; if((is-length-i)) printf(“所給子串的位置或長度有錯誤n”); else t-length=len; /*建立子串t的存儲映像*/ t-start=s-start+i; ,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長順序存儲及運算實現(xiàn) 2.3.3 模式匹配 2.3.4 串的

63、堆式動態(tài)存儲及運算實現(xiàn) 2.3.5 漢字串,漢字串,漢字是一種拼形和表意文字。 無論是西文還是漢字，計算機系統(tǒng)均應(yīng)具有輸入、加工處理和輸出的功能，并能在不同的系統(tǒng)之間進行信息交換。 對應(yīng)于不同的功能，在計算機系統(tǒng)中用不同的代碼來表示： 用戶在輸入設(shè)備上輸入文字信息時，由輸入設(shè)備產(chǎn)生相應(yīng)的代碼稱作輸入碼或外部碼； 在計算機內(nèi)部存儲和處理文字信息所采用的代碼稱作機內(nèi)碼； 為了表示文字字形，通常是設(shè)計表示不同字形的字模點陣，這種碼稱作字模點陣碼； 在系統(tǒng)之間傳輸和交換信息的代碼稱作交換碼。,漢字串（續(xù)）,對于西文來說，由于借助于拼音規(guī)則可只用少量字母拼成文字，因而其機內(nèi)碼、輸入碼和交換碼等的數(shù)據(jù)結(jié)構(gòu)

64、都比較簡單； 在設(shè)計這些代碼時已盡可能做到相互一致，代碼間的轉(zhuǎn)換也非常簡單。 目前大多數(shù)計算機均以ASCII碼作為西文的機內(nèi)碼，也有用EBCDIC碼作機內(nèi)碼的，它們都是按每個字節(jié)存放一個字符設(shè)計的。 當(dāng)向計算機輸入西文信息時，只要在鍵盤上按不同的鍵就可產(chǎn)生不同的輸入代碼，這些輸入碼集可以簡單地等同于機內(nèi)碼集。 因此，當(dāng)構(gòu)成串的字符集限于西文字母、數(shù)字和其它字符時，往往不考慮它的機內(nèi)碼而直接討論串值的存儲結(jié)構(gòu)。,漢字代碼轉(zhuǎn)換關(guān)系示意圖,采用漢字串標(biāo)識法的七位碼方法,以ASCII碼集或其子集作為基集，由兩個或兩相以上的ASCII字符構(gòu)成一個漢字機內(nèi)碼。 例如，用電報碼作為漢字機內(nèi)碼。電報碼是以AS

65、CII字符集的子集C=0,1,29為基集，由四個09的數(shù)字字符構(gòu)成一個漢字機內(nèi)碼。為了與西文ASCII字符區(qū)分，可選用“（”來表示西文串的標(biāo)記符而用“）”表示漢字串的標(biāo)記符；這樣使得括號以內(nèi)的符號全部保留ASCII碼集字符的意義，而括號以外的符號就是漢字串的機內(nèi)碼了。如下圖 這種存儲方法，對于順序地從前向后逐個處理的運算操作是很適用的，但對于某些隨機性的操作卻不很方便。,采用代碼標(biāo)識法的八位碼方法,以我國“信息交換用漢字編碼字符集基本集GB2312-80”為基礎(chǔ)，在每個漢字代碼中設(shè)標(biāo)志作為漢字機內(nèi)碼。 國標(biāo)交換碼規(guī)定由兩個字節(jié)構(gòu)成一個漢字交換碼，每個字節(jié)都用七位，最高位均為0。 現(xiàn)將國標(biāo)交換碼

66、每個字節(jié)的最高位均置1以形成八位碼來作漢字機內(nèi)碼。以漢字“大”為例，其機內(nèi)碼如下圖。,采用代碼標(biāo)識法的八位碼方法(續(xù)),除了采用國標(biāo)碼外，還有使用國標(biāo)區(qū)位碼的方案。 區(qū)位碼中，每個漢字對應(yīng)四個十進制數(shù)字，前兩位是區(qū)號共94個區(qū)，每區(qū)94位。 國標(biāo)區(qū)位碼和國標(biāo)碼之間可用計算公式相互轉(zhuǎn)換。 區(qū)位碼轉(zhuǎn)換為國標(biāo)碼的方法是，先將十進制區(qū)位碼轉(zhuǎn)換成十六進制，然后在兩個字節(jié)上分別加20（十六進制）就得到國標(biāo)碼。 在國標(biāo)碼的兩個字節(jié)上各加80（十六進制）就轉(zhuǎn)換為漢字機內(nèi)碼了。 目前應(yīng)用較為廣泛的是采用國標(biāo)碼和區(qū)位碼進行代碼標(biāo)識，形成兩字節(jié)漢字機內(nèi)碼。這種兩字節(jié)的漢字機內(nèi)碼，可以很方便地從漢字的序數(shù)計算出該漢字在字符串中的存儲位置。,漢字區(qū)位碼轉(zhuǎn)換為機內(nèi)碼的過程,以漢字“雹”為例的轉(zhuǎn)換過程如下：,采用漢字標(biāo)識法的多個字節(jié)代碼,在每個漢字代碼前增加一個標(biāo)識字節(jié)，就形成所謂多字節(jié)的漢字機內(nèi)碼。例如將漢字國標(biāo)碼轉(zhuǎn)換成字母和數(shù)字表示的三個字節(jié)，然后在這三個字節(jié)之前增加一個漢字標(biāo)記字節(jié)，這種標(biāo)記字節(jié)可用來適應(yīng)各種不同的要求。但是這種機內(nèi)碼的編輯性較差，占用字節(jié)量大；一般用在要求較高的軟件系統(tǒng)中或傳輸過程中作為系統(tǒng)