算法與數(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ù),計算機(jī)中的數(shù)據(jù)在計算機(jī)內(nèi)的最原始形式僅是一組組二進(jìn)制代碼，程序設(shè)計語言以這種代碼為基礎(chǔ)建立起了所有的數(shù)據(jù)。 數(shù)據(jù)的概念不再只是那些用數(shù)字組合而成的各種數(shù)據(jù)了，如整數(shù)、小數(shù)、實數(shù)、虛數(shù)、復(fù)數(shù)、指數(shù)和對數(shù)等。 隨著計算機(jī)科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)的概念也相應(yīng)地發(fā)生了一些重要的變化。,數(shù)據(jù)（續(xù)）,數(shù)據(jù)（Data）是信息的載體，是對自然界客觀事物的符號表示。 在計算機(jī)科學(xué)與技術(shù)學(xué)科，數(shù)據(jù)泛指那些能夠被計算機(jī)接收、識別、存儲、加工和處理的對象的全體。 換句話說，數(shù)據(jù)是對那些能夠有效地輸入到計算機(jī)中并且能夠被計算機(jī)程序所加工和處理的符號全體的總稱。 只要是能被計算機(jī)識別、存儲、加工和處理的都屬于數(shù)據(jù)的范疇。,數(shù)據(jù)元素,數(shù)據(jù)的基本單位是數(shù)據(jù)元素（Data Element），有時也稱作元素、結(jié)點、頂點、記錄等。 一個數(shù)據(jù)元素也可以由若干個數(shù)據(jù)項（Data Item）組成。 數(shù)據(jù)項是具有獨(dú)立含義的數(shù)據(jù)的不可再分割的最小標(biāo)識單位。例如，一個單位的職工花名冊中，每一位職工的信息就是一個數(shù)據(jù)元素；職工信息中包含有職工編號、姓名、性別、民族、年齡、政治面貌、參加工作時間、工資級別、職稱、職務(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ù)元素是對客觀世界中某個獨(dú)立個體的數(shù)據(jù)描述。 在C語言中，數(shù)據(jù)元素可以用結(jié)構(gòu)體來描述，每個數(shù)據(jù)項則是結(jié)構(gòu)體中的一個分量。,數(shù)據(jù)元素與數(shù)據(jù)對象,計算機(jī)中的數(shù)據(jù)可以按類型來劃分，劃分的結(jié)果就是數(shù)據(jù)對象。 所謂數(shù)據(jù)對象（Data Object），是指具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如整數(shù)數(shù)據(jù)對、字母字符數(shù)據(jù)對象。 在一個具體問題中，數(shù)據(jù)元素具有相同性質(zhì)，屬于同一數(shù)據(jù)對象，數(shù)據(jù)元素是數(shù)據(jù)對象的一個實例。如在前述的職工花名冊中，所有的職工是一個數(shù)據(jù)對象，不同的職工的信息是不同的數(shù)據(jù)元素，它們都是職工數(shù)據(jù)對象的不同實例，其數(shù)據(jù)元素值是各數(shù)據(jù)項的一個具體描述。,數(shù)據(jù)類型,數(shù)據(jù)類型（Data Type）是對在計算機(jī)中表示的同一數(shù)據(jù)對象及其在該數(shù)據(jù)對象上的一組操作的總稱。 如整數(shù)數(shù)據(jù)，在計算機(jī)中它是集合minintmaxint上的整數(shù)（其中minint和maxint分別是最小整數(shù)和最大整數(shù)，在不同的計算機(jī)中表示的值不同；且這個集合是有窮集合，是數(shù)學(xué)意義上的無窮集合的一個子集），在這個集合上可以進(jìn)行的操作有加、減、乘、整除和求模等算術(shù)運(yùn)算以及等于、不等于、大于、小于、大于等于和小于等于等關(guān)系運(yùn)算。 數(shù)據(jù)對象整數(shù)以及在整數(shù)集合上的算術(shù)運(yùn)算和關(guān)系運(yù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)造機(jī)制來定義的數(shù)據(jù)類型。如數(shù)組、文件、結(jié)構(gòu)體、共用體等，其值可以再分解；它的構(gòu)成成分可以是簡單數(shù)據(jù)類型，也可以是結(jié)構(gòu)數(shù)據(jù)類型。 數(shù)據(jù)類型的概念，是程序設(shè)計語言和程序設(shè)計過程中的一個非常重要的概念。,數(shù)據(jù)類型的特征,類型決定了變量或表達(dá)式所有可能取值的全體成員集合。 每一個值隸屬于且僅隸屬于某一類型。 任何常量、變量或表達(dá)式的類型，都可以從其形式上或所處的上下文關(guān)系中推斷出來，無須了解在程序運(yùn)行時計算出的具體值。 每一種操作都要求一定類型的操作數(shù)據(jù)，且得出一定類型的操作結(jié)果。 一種類型的值及其在該類型上規(guī)定的基本操作的性質(zhì)可由一組公理來闡明。 高級程序設(shè)計語言使用類型信息去防止程序中出現(xiàn)無意義的結(jié)構(gòu)，又由類型信息確定在計算機(jī)中的數(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）是指計算機(jī)程序中所操作的對象數(shù)據(jù)以及數(shù)據(jù)元素之間的相互關(guān)系和運(yùn)算。 在任何問題中，數(shù)據(jù)元素之間都不會是獨(dú)立的，總是存在著這樣或那樣的關(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ù)的運(yùn)算及實現(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) 如樹、圖和集合等。,數(shù)據(jù)的存儲結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)及數(shù)據(jù)元素之間的關(guān)系在計算機(jī)內(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)上所定義的運(yùn)算的算法也隨之改變了。,數(shù)據(jù)的運(yùn)算及實現(xiàn),數(shù)據(jù)的運(yùn)算及實現(xiàn)。程序中的數(shù)據(jù)運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的運(yùn)算，但運(yùn)算的實現(xiàn)要在相應(yīng)的存儲結(jié)構(gòu)上進(jìn)行。 常用的運(yùn)算有檢索、插入、刪除、更新、排序等。 在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義數(shù)據(jù)的運(yùn)算時，只考慮這些運(yùn)算是“做什么”，而不考慮它“如何做”，是抽象運(yùn)算；只有在選定了某種數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)時，才去考慮如何具體實現(xiàn)這些運(yùn)算，即運(yùn)算的實現(xiàn)。 運(yù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），也有且僅有一個直接后繼（immediate 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é)點）。 樹的例子很多，如族譜中的家族樹、政府機(jī)構(gòu)中的行政樹、計算機(jī)文件管理中的目錄樹、編譯程序中用到的語法樹等。,樹型結(jié)構(gòu)示意圖,非線性結(jié)構(gòu)圖型結(jié)構(gòu),非線性結(jié)構(gòu)中的圖結(jié)構(gòu)，其數(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)來表示集合。,存儲表示方式順序存儲,順序存儲方式，是在計算機(jī)內(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)進(jìn)行線性化處理后也可實現(xiàn)順序存儲。,存儲表示方式鏈?zhǔn)酱鎯?鏈?zhǔn)酱鎯Ψ绞剑前褦?shù)據(jù)元素和反映元素間關(guān)系（后繼和/或前趨）的地址一塊存儲在計算機(jī)內(nèi)；它不要求在內(nèi)存儲器中開辟的存儲單元地址連續(xù)，數(shù)據(jù)元素可以存放在內(nèi)存儲器中的任意位置，借助指示數(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)的存儲。,其他的存儲表示方式,存儲表示方式還有索引存儲方式和散列存儲方式，通常是為了檢索的方便所采用的存儲表示方法。 一般地說，這幾種基本的存儲表示方法，既可以單獨(dú)使用，也可以組合起來使用。 選擇何種存儲結(jié)構(gòu)要依具體問題的要求而定，既要考慮問題表示和運(yùn)算的方便性，也還會考慮到實現(xiàn)算法的時間和空間效率要求。,數(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ù)在作為計算機(jī)程序數(shù)據(jù)時的組織、管理、存儲、運(yùn)算和處理的方法和技術(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.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ì)的細(xì)節(jié)。 數(shù)據(jù)類型是對同一數(shù)據(jù)對象及其在該數(shù)據(jù)對象上的一組操作的抽象，抽象的結(jié)果是把用戶不必了解的一切細(xì)節(jié)都封裝在類型之中，對使用數(shù)據(jù)類型的用戶來說是實現(xiàn)了信息隱藏（Information Hiding）。 用戶在使用數(shù)據(jù)類型時，既不需要了解該數(shù)據(jù)類型在計算機(jī)內(nèi)部是如何表示的，也不需要知道其操作是如何實現(xiàn)的，只須集中精力考慮所要求解的問題應(yīng)該如何去解決。 抽象數(shù)據(jù)類型的概念，是我們熟知的數(shù)據(jù)類型概念的引伸和發(fā)展，是數(shù)據(jù)抽象和運(yùn)算抽象緊密結(jié)合的產(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)上的一組運(yùn)算；這種情況是我們討論和學(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)造最終的問題求解算法。,抽象數(shù)據(jù)類型的定義,抽象數(shù)據(jù)類型的定義，僅取決于它的一組邏輯特性，而與它在計算機(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, 1xmaxint 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<y) 返回0 else 返回x-y end ADT NaturalNumber;,抽象數(shù)據(jù)類型（續(xù)）,抽象數(shù)據(jù)類型是算法設(shè)計和程序設(shè)計中的重要概念，這個概念明確地把數(shù)據(jù)結(jié)構(gòu)與作用在該結(jié)構(gòu)上的運(yùn)算緊密地聯(lián)系起來。 數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算依賴于其具體表示，有了數(shù)據(jù)結(jié)構(gòu)的具體表示和運(yùn)算的具體實現(xiàn)，運(yùn)算的效率隨之確定。 需要指出的是，基本數(shù)據(jù)類型已隱含著數(shù)據(jù)結(jié)構(gòu)和定義在該結(jié)構(gòu)上的運(yùn)算的統(tǒng)一，只是當(dāng)時尚未形成抽象數(shù)據(jù)類型的概念罷了。 每一種基本數(shù)據(jù)類型都連帶著一組基本運(yùn)算，只是由于這些基本數(shù)據(jù)類型中數(shù)據(jù)結(jié)構(gòu)的具體表示和基本運(yùn)算的具體實現(xiàn)都很規(guī)范，都通過內(nèi)置而隱藏起來使人們看不到它們的封裝，人們習(xí)慣于在算法與程序設(shè)計中使用基本數(shù)據(jù)類型名和相關(guān)的運(yùn)算名而不問其究竟。,抽象數(shù)據(jù)類型（續(xù)）,抽象數(shù)據(jù)類型的設(shè)計和實現(xiàn)不可能象基本數(shù)據(jù)類型那樣可以規(guī)范、內(nèi)置和一勞永逸。 首先要根據(jù)問題的具體要求，定義該抽象數(shù)據(jù)類型需要包含哪些信息，并根據(jù)功能確定公共界面的服務(wù)，使用者可以使用公共界面中的服務(wù)對該抽象數(shù)據(jù)類型進(jìn)行操作。 另一方面，把抽象數(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ù)組的必要性，如需要記住一組值等； 基于問題求解算法的效率考慮，引入數(shù)組可使算法效率更高； 基于概念上或運(yùn)算處理上的自然、簡單和方便性方面考慮需要引入數(shù)組。,2.2 數(shù)組,2.2.1 數(shù)組及其運(yùn)算 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ù)組元素可以隨機(jī)訪問。 所以，可以說數(shù)組結(jié)構(gòu)是一個線性的、均勻的、其元素可以隨機(jī)訪問的數(shù)據(jù)結(jié)構(gòu)。也可以說數(shù)組是由數(shù)組元素和下標(biāo)構(gòu)成的有序?qū)Y(jié)構(gòu)，結(jié)構(gòu)中的每一個數(shù)據(jù)元素都與一組下標(biāo)有關(guān)。,數(shù)組的運(yùn)算,對于數(shù)組結(jié)構(gòu)的運(yùn)算操作，是對其數(shù)據(jù)元素的操作。通常只有賦值和讀取數(shù)組元素兩種操作： 賦值：給定一組下標(biāo)，把指定值（如初始值、修改值、運(yùn)算值等）存入相應(yīng)的數(shù)組元素中； 讀?。航o定一組下標(biāo)，讀取相應(yīng)的數(shù)組元素（通常是為了使用其值或打印輸出等目的）。,數(shù)組,在程序設(shè)計語言中，與數(shù)組結(jié)構(gòu)對應(yīng)的數(shù)據(jù)類型是數(shù)組類型，即在程序中引入數(shù)組要用語言中提供的數(shù)組類型說明方法說明。 如在C語言中，int A8就說明了一個一維整型數(shù)組A；進(jìn)而就可以對A施加不同的操作，一般方法是利用循環(huán)控制變量值的變化，從下標(biāo)下界到上界之間（或相反次序）訪問相應(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ù)組及其運(yùn)算 2.2.2 數(shù)組的順序存儲結(jié)構(gòu) 2.2.3 特殊矩陣的壓縮存儲,數(shù)組的順序存儲結(jié)構(gòu),順序存儲結(jié)構(gòu)，是指在計算機(jī)內(nèi)存中安排一片地址連續(xù)的空間存儲數(shù)據(jù)。 數(shù)組的線性的、均勻的結(jié)構(gòu)和計算機(jī)內(nèi)存單元的一維結(jié)構(gòu)，決定了對數(shù)組采用順序存儲結(jié)構(gòu)是最佳選擇。 對于一維數(shù)組，按下標(biāo)順序分配存儲空間是很自然的。 對于二維數(shù)組和多維數(shù)組。就有一個把數(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行中元素的后面；同一行中的元素以列下標(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個元素；由每個元素占用空間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+1)+i-c1)*e,2.2 數(shù)組,2.2.1 數(shù)組及其運(yùn)算 2.2.2 數(shù)組的順序存儲結(jié)構(gòu) 2.2.3 特殊矩陣的壓縮存儲,特殊矩陣的壓縮存儲,在科學(xué)計算和工程應(yīng)用中，常常要用到矩陣的概念。由于矩陣具有元素個數(shù)固定且下標(biāo)有序排列的特點，使用二維數(shù)組表示既自然又可方便矩陣的各種運(yùn)算。但是在有些情況下，如特殊矩陣和稀疏矩陣，采用二維數(shù)組的存儲方式會浪費(fèi)大量存儲空間。為了節(jié)省空間，對這類矩陣可壓縮存儲。 所謂壓縮存儲，是指為多個值相同的元素只分配一個元素的存儲空間，對零元素不分配存儲空間。 所謂特殊矩陣是指矩陣中元素分布有一定規(guī)律，如對角矩陣、三對角矩陣、上三角矩陣、下三角矩陣、對稱矩陣等。,1.對角矩陣的壓縮存儲,對角矩陣的特點是除了主對角線上的元素外其余元素都為零。 對于n階方陣，只有n個非零元素，只需要n個元素空間順序存儲即可。其非零元素壓縮存儲位置k與矩陣下標(biāo)的對應(yīng)關(guān)系為k=i或k=j，通過這個關(guān)系可對矩陣中的非零元素隨機(jī)存取。,壓縮存儲,2.三對角矩陣的壓縮存儲,三對角矩陣是除主對角線及主對角線上下各一個元素外，其余元素都為零的矩陣。 對三對角矩陣的壓縮存儲方法是，按行為主序優(yōu)先存儲方法把非零區(qū)的三對角元素依次順序存儲到一片連續(xù)的存儲空間中。 其映像關(guān)系可以這樣來分析：對處于三對角區(qū)的元素aij，它前面的i-1行中有非零元素3*(i-1)-1個，它處于本行中的第j-i+2個非零元素處，所以為第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ū)，值必為常數(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處于存儲分配區(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 串,所謂串，就是我們在高級語言程序設(shè)計課程中學(xué)習(xí)和使用過的字符串，是大家熟知的概念。 串是許多軟件系統(tǒng)的操作對象，如字符編輯系統(tǒng)、情報檢索系統(tǒng)、詞法分析系統(tǒng)、符號處理系統(tǒng)、語言翻譯系統(tǒng)等，有著十分廣泛的應(yīng)用。 本節(jié)著重討論串的存儲結(jié)構(gòu)以及主要運(yùn)算的實現(xiàn)，如順序存儲分配的三種方式、堆式存儲分配策略以及在“向量存儲，定長結(jié)構(gòu)”基礎(chǔ)上幾種串運(yùn)算的實現(xiàn)算法，并簡要介紹漢字串的概念。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長順序存儲及運(yùn)算實現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動態(tài)存儲及運(yùn)算實現(xiàn) 2.3.5 漢字串,串的基本概念,串（String）是由零個或多個字符組成的有限序列。 記作: s=“a1a2an” (n0) 其中：s是串名，用雙引號括起來的字符序列是串的值（不含雙引號）；ai（1in）是相應(yīng)程序設(shè)計語言中允許使用的字符集中的任意字符；n為串中的字符個數(shù)，稱作串的長度。 零個字符的串稱作空串，它的長度為零，串內(nèi)無任何字符。 要注意空串與空格串的區(qū)別，空格串中有一個或多個空格字符，串的長度大于零。,串的基本概念（續(xù)）,串中任意多個連續(xù)字符組成的子序列稱作該串的子串（Substring），包含子串的串稱作該子串的主串。字符在串中的序號稱作該字符在串中的位置，子串在主串中的位置用子串的第一個字符在主串中的位置來表示。 兩個串相等是指這兩個串的值相等，即兩個串長度相等且對應(yīng)字符都相同時才相等。 串結(jié)構(gòu)的形式化定義為 string=(D,R) 其中：D= aiaicharacter，i=1,2n，n0, R=ai-1,aiD，i=1,2n 。,串的基本運(yùn)算（六種）,StrAssign(s,chars)：串賦值。把字符串常量chars的值賦給串變量s。 StrCopy(s,t)：串復(fù)制。把串變量t的值復(fù)制到串變量s中。 StrCompare(s,t)：串比較。若st返回值0，若s=t返回值=0，若s<t 返回值<0。 StrLenth(s)：求串長。返回值為串s中字符的個數(shù)（串長）。 StrConcat(l,s,t)：串聯(lián)接。把串t的值緊接著串s的值之后形成的新串值存入串變量l中返回。例如，若s=“baodao”，t=“taiwan”，則l=“baodaotaiwan”。 SubString(t,s,i,len)：求子串。把串s 中第i個字符開始的長度為len的字符序列存入串變量t中返回。該運(yùn)算要求1iStrLength(s)+1且0lenStrLength(s)- i +1。,串的其它運(yùn)算（四種）,其它的串運(yùn)算都可以由這六種基本運(yùn)算來實現(xiàn)。 下面四種其它的串運(yùn)算都有著重要的應(yīng)用： StrInsert(s,i,t)：串插入。運(yùn)算的結(jié)果是把t串插入到s串中第i個字符之前得到的新串。其中，1iStrLength(s)+1。 StrDelete(s,i,len)：串刪除。運(yùn)算的結(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)：子串替換。運(yùn)算的結(jié)果是以串v替換所有在串s中出現(xiàn)的和非空串t相等的不重疊的子串后得到的新串。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長順序存儲及運(yùn)算實現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動態(tài)存儲及運(yùn)算實現(xiàn) 2.3.5 漢字串,串的定長順序存儲,當(dāng)一維數(shù)組的基類型是字符類型，形成的字符數(shù)組即字符串或串。 在高級程序設(shè)計語言中，大都為字符串設(shè)立了專門的數(shù)據(jù)類型。 在C語言中，有串常量和串變量的概念。用雙引號括起來的字符序列為字符串常量，也可以用宏定義#define來定義字符串常量的標(biāo)識符，如 #define CITY shanghai 對于字符串變量，C語言的說明為一維字符型數(shù)組，如 static char C100； 為字符串分配一個固定長度的一組地址連續(xù)的存儲單元的存儲分配方法稱之為定長順序存儲分配。,定長順序存儲緊縮方式,計算機(jī)按字編址、每個單元存放四個字符。 如串s=“data structure 2.3”的緊縮存儲如下： 其中字符串長度18存儲在開始處，“ ”表示空格字符，共占用五個存儲單元。 緊縮方式對串長是顯式地直接存儲，字符依次順序放在連續(xù)的幾個單元中。這種存儲方式的優(yōu)點是充分地利用了空間，然而四個字符一個地址運(yùn)算不太方便。,定長順序存儲非緊縮方式,計算機(jī)按字編址，每個單元存放一個字符。串的長度不顯式存儲，由串中字符占存儲單元的數(shù)目來隱式確定。 非緊縮存儲方式方便了串運(yùn)算，但存儲空間沒有得到有效利用。 例如對串s=“data structure 2.3”的非緊縮存儲如右圖所示。,定長順序存儲單字節(jié)存儲方式,計算機(jī)按字節(jié)編址，每個字節(jié)存放一個字符。 每個地址對應(yīng)一個字節(jié)，一個字節(jié)正好存放一個字符。這時的串長度也不必存儲，由串占用的字節(jié)數(shù)隱式確定；也可用特殊字符作為串的結(jié)束標(biāo)志，如用“0”作結(jié)束標(biāo)志。 這種存儲方式既不浪費(fèi)空間，又使串中每個字符與惟一地址對應(yīng)方便了運(yùn)算，對于按字節(jié)編址的計算機(jī)而言是非常合適的。 例如對串s=“data structure 2.3”的單字節(jié)存儲方式如右圖所示。,定長順序存儲結(jié)構(gòu)的運(yùn)算實現(xiàn),為了方便討論，我們把串的類型說明改寫成如下形式： #define STRINGLEN 81 struct string int len; static char chSTRINGLEN； typedef struct string STRING； 并假定串尾以“0”作結(jié)束標(biāo)志。 由于串賦值和串復(fù)制在高級程序設(shè)計語言中是通過賦值語句來完成的，所以在這里只討論其余四種基本運(yùn)算，即串比較、求串長、串聯(lián)接和求子串運(yù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故可直接返回其值即可。 算法描述如下： 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)接,在實現(xiàn)串的聯(lián)接運(yù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; l-len=s-len+t-len; ,3.串聯(lián)接（續(xù)）,該算法的時間開銷主要在于復(fù)制兩個串中字符到結(jié)果串中，其復(fù)制字符個數(shù)為兩個串的長度之和，故其時間復(fù)雜度為O(s-len+t-len)。 串的聯(lián)接運(yùn)算不滿足交換律，這一點由串聯(lián)接的定義是顯而易見的。 然而，串的聯(lián)接運(yùn)算是滿足結(jié)合律的；在多個串聯(lián)接時，只要位置次序不變，先聯(lián)接哪兩個都無所謂，最終結(jié)果都是一樣的。,4.求子串,在設(shè)計求子串算法時要注意算法的健壯性要求，即要檢查子串開始位置i和子串長度len的合法性。 當(dāng)ilen時，子串開始位置非法； 當(dāng)lens-len-i時，子串的長度非法。 對于這些非法的數(shù)據(jù)（參數(shù)），要給出相應(yīng)的錯誤信息。 求子串的算法描述如下： 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è)置子串長度*/ 該算法的主要時間開銷在于從主串s中取出子串存于t中，而子串的最大長度等于主串，主串最長為預(yù)先定義好的定長STRINGLEN，所以其時間復(fù)雜度為O(STRINGLEN)。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長順序存儲及運(yùn)算實現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動態(tài)存儲及運(yùn)算實現(xiàn) 2.3.5 漢字串,模式匹配,子串的定位操作通常稱作模式匹配，子串t稱作模式，在主串s中確定t的位置的過程稱作匹配過程。 模式匹配在文本編輯、文件檢索和各種串處理系統(tǒng)中有著廣泛的應(yīng)用，因此它是最重要的串運(yùn)算之一。然而模式匹配不是串的基本運(yùn)算，它可以借用串的基本運(yùn)算來實現(xiàn)。 利用串比較、求串長和求子串三種基本操作實現(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ù)逐個比較后續(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)用場合如文本編輯等，匹配效率也較高。 在這樣一種較好的匹配情況下，即每趟中不成功的匹配都發(fā)生在第一對字符比較時，其時間復(fù)雜度為O(n+m)。 然而在最壞情況下，即每趟不成功的匹配都發(fā)生在模式串t中最后一個字符時，其時間復(fù)雜度為O(n*m)，算法效率很低。,一種改進(jìn)的模式匹配算法,這種改進(jìn)的模式匹配算法是D.E.Knuth與J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)的，因此人們稱它為克努特莫里斯普拉特算法，簡稱為KMP算法。 該算法可以在O(n+m)的時間數(shù)量級上完成串的模式匹配運(yùn)算。 其改進(jìn)思想是充分利用部分匹配的信息，不需回溯主串指示器變量i，而是在匹配過程中出現(xiàn)字符比較不等時，將模式串t盡可能遠(yuǎn)地向右滑動一段距離后繼續(xù)進(jìn)行比較。,一種改進(jìn)的模式匹配算法（續(xù)）,回顧前述的匹配過程示例，在第三趟的匹配中當(dāng)i=6、j=4比較字符不等時，又從i=3、j=0重新開始比較。仔細(xì)觀察可以發(fā)現(xiàn)，在i=3和j=0、i=4和j=0、i=5和j=0這三次比較都是不必進(jìn)行的；這是由于從第三趟部分匹配的結(jié)果就可以得出主串中的第4、5和6個字符（即i=3、4和5）和模式串中的第2、3和4個字符（即j=1、2和3）相同為b、c和a，而模式串中的第一個字符（即j=0）是a無需再和這三個字符進(jìn)行比較，僅需將模式串向右滑動三個字符的位置進(jìn)行i=6、j=1時的字符比較即可。同理，在第一趟匹配中出現(xiàn)字符不等時，僅需將模式串向右滑動兩個字符位置進(jìn)行i=2、j=0時的字符比較。,一種改進(jìn)的模式匹配的匹配過程,值得注意的是在整個匹配過程中i指示器變量的值沒有回溯。,改進(jìn)的模式匹配的一般化思路,對于模式串t=“t0t1tm-1”和主串s=“s0s1sn-1”，當(dāng)匹配過程中sitj產(chǎn)生失配時，模式串向右滑動多遠(yuǎn)距離？ 或者說失配時i指示器變量不回溯，主串中第i個字符應(yīng)該與模式串中哪個字符再繼續(xù)比較？ 設(shè)此時應(yīng)該與模式串中第k(k<j)個字符比較，則模式t中前k-1個字符的子串應(yīng)該滿足如下關(guān)系： “t0t1tk-2”=“si-k+1si-k+2si-1” 且不存在大于k的這樣的關(guān)系式。而已得到的部分匹配結(jié)果可表示為： “tj-k+1tj-k+2tj-1”=“si-k+1si-k+2si-1” 由前面兩式可以推出下式： “t0t1tk-2”=“tj-k+1tj-k+2tj-1”,改進(jìn)的模式匹配的一般化思路,“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，則可引出next函數(shù)的定義如下：,改進(jìn)的模式匹配的一般化思路,由next函數(shù)的定義可推出模式“abaabcac”的next函數(shù)值為： 有了next函數(shù)之后，匹配過程可以這樣進(jìn)行：令指示器變量i和j的值都為0，若在匹配過程中si=tj；則i和j分別加1，否則i不變而j退到nextj的位置再比較；若相等i和j各加1，否則j退到下一個next值的位置，依此類推直到下面兩種可能： 一是退到某next值（nextnextnextj）時字符比較相等，指示器變量值各加1后繼續(xù)比較； 另一種是退到值為零（即模式的第一個字符失配），此時需將模式繼續(xù)向右滑動一個位置，從主串的下一個字符si+1重新開始匹配。,改進(jìn)的模式匹配的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) ,運(yùn)用算法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; /*初始化指示器變量并給next0賦零值*/ while(i len) if(j=0)|(t-chi=t-chj) i+; j+; nexti=j; else j=nextj; ,一種改進(jìn)的模式匹配算法（續(xù)）,算法getnext的時間復(fù)雜度為O(m)。通常模式串的長度m要比主串的長度n小得多，因此對整個匹配算法KMP來說增加這點求next函數(shù)的時間是值得的。 需要說明的是，算法index的時間復(fù)雜度雖然是O(m*n)，但在一般情況下其實際執(zhí)行時間近似于O(m+n)，所以至今仍被采用。 算法index_KMP僅當(dāng)模式串與主串之間存在許多部分匹配的情況下才顯得比算法index快得多。 index_KMP算法的最大特點是不需回溯主串的指示器變量i，整個匹配過程只需從頭到尾掃描主串一遍，特別適用于從外設(shè)讀入龐大文件邊讀入邊匹配，無需回頭重讀。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長順序存儲及運(yùn)算實現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動態(tài)存儲及運(yùn)算實現(xiàn) 2.3.5 漢字串,串的堆式動態(tài)存儲,在處理串的應(yīng)用程序中，所處理的串的長度相差往往較大，處理過的串值長度變化往往也較大。 采用定長順序存儲在多數(shù)串的串長較小時其空間利用率低，且使某些運(yùn)算如串聯(lián)接和串置換等受到限制或產(chǎn)生錯誤結(jié)果。 因此，在許多實際應(yīng)用的串處理系統(tǒng)中采用的是堆式動態(tài)存儲分配策略。,堆式動態(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指示串值序列的長度， 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; /*定義串類型標(biāo)識符為STRING*/ char storeMAXSIZE; /*定義堆為一維數(shù)組store*/ int free; /*堆store中尚未分配區(qū)間的開始地址指示器變量*/,堆式動態(tài)存儲的串賦值算法,該運(yùn)算把存儲于字符串?dāng)?shù)組chars中的字符串常量存入堆store中，并為s建立存儲映像。在邏輯上即為串變量s賦一個字符串常量值。 其算法描述如下： void StrAssign(s,chars) STRING *s; char chars; int i,len; i=0; /*為統(tǒng)計字符串常量中的字符個數(shù)初始化*/ while(charsi!=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ù)制算法,該運(yùn)算把堆中的串t復(fù)制到s中去。算法如下： void StrCopy(s,t) STRING *s,*t; int i; if(free-1+t-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ù)制運(yùn)算也可以共享堆中t的存儲空間，只建立s的存儲映像，但若對其中之一修改就會影響到另一個。,堆式動態(tài)存儲的串聯(lián)接算法,只要分別將s串和t串復(fù)制到store中為l開辟的存儲區(qū)，并建立l的存儲映像即可完成串聯(lián)接運(yùn)算。算法如下： 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ù)制運(yùn)算一樣，求子串運(yùn)算也有復(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 串的定長順序存儲及運(yùn)算實現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動態(tài)存儲及運(yùn)算實現(xiàn) 2.3.5 漢字串,漢字串,漢字是一種拼形和表意文字。 無論是西文還是漢字，計算機(jī)系統(tǒng)均應(yīng)具有輸入、加工處理和輸出的功能，并能在不同的系統(tǒng)之間進(jìn)行信息交換。 對應(yīng)于不同的功能，在計算機(jī)系統(tǒng)中用不同的代碼來表示： 用戶在輸入設(shè)備上輸入文字信息時，由輸入設(shè)備產(chǎn)生相應(yīng)的代碼稱作輸入碼或外部碼； 在計算機(jī)內(nèi)部存儲和處理文字信息所采用的代碼稱作機(jī)內(nèi)碼； 為了表示文字字形，通常是設(shè)計表示不同字形的字模點陣，這種碼稱作字模點陣碼； 在系統(tǒng)之間傳輸和交換信息的代碼稱作交換碼。,漢字串（續(xù)）,對于西文來說，由于借助于拼音規(guī)則可只用少量字母拼成文字，因而其機(jī)內(nèi)碼、輸入碼和交換碼等的數(shù)據(jù)結(jié)構(gòu)都比較簡單； 在設(shè)計這些代碼時已盡可能做到相互一致，代碼間的轉(zhuǎn)換也非常簡單。 目前大多數(shù)計算機(jī)均以ASCII碼作為西文的機(jī)內(nèi)碼，也有用EBCDIC碼作機(jī)內(nèi)碼的，它們都是按每個字節(jié)存放一個字符設(shè)計的。 當(dāng)向計算機(jī)輸入西文信息時，只要在鍵盤上按不同的鍵就可產(chǎn)生不同的輸入代碼，這些輸入碼集可以簡單地等同于機(jī)內(nèi)碼集。 因此，當(dāng)構(gòu)成串的字符集限于西文字母、數(shù)字和其它字符時，往往不考慮它的機(jī)內(nèi)碼而直接討論串值的存儲結(jié)構(gòu)。,漢字代碼轉(zhuǎn)換關(guān)系示意圖,采用漢字串標(biāo)識法的七位碼方法,以ASCII碼集或其子集作為基集，由兩個或兩相以上的ASCII字符構(gòu)成一個漢字機(jī)內(nèi)碼。 例如，用電報碼作為漢字機(jī)內(nèi)碼。電報碼是以ASCII字符集的子集C=0,1,29為基集，由四個09的數(shù)字字符構(gòu)成一個漢字機(jī)內(nèi)碼。為了與西文ASCII字符區(qū)分，可選用“（”來表示西文串的標(biāo)記符而用“）”表示漢字串的標(biāo)記符；這樣使得括號以內(nèi)的符號全部保留ASCII碼集字符的意義，而括號以外的符號就是漢字串的機(jī)內(nèi)碼了。如下圖 這種存儲方法，對于順序地從前向后逐個處理的運(yùn)算操作是很適用的，但對于某些隨機(jī)性的操作卻不很方便。,采用代碼標(biāo)識法的八位碼方法,以我國“信息交換用漢字編碼字符集基本集GB2312-80”為基礎(chǔ)，在每個漢字代碼中設(shè)標(biāo)志作為漢字機(jī)內(nèi)碼。 國標(biāo)交換碼規(guī)定由兩個字節(jié)構(gòu)成一個漢字交換碼，每個字節(jié)都用七位，最高位均為0。 現(xiàn)將國標(biāo)交換碼每個字節(jié)的最高位均置1以形成八位碼來作漢字機(jī)內(nèi)碼。以漢字“大”為例，其機(jī)內(nèi)碼如下圖。,采用代碼標(biāo)識法的八位碼方法(續(xù)),除了采用國標(biāo)碼外，還有使用國標(biāo)區(qū)位碼的方案。 區(qū)位碼中，每個漢字對應(yīng)四個十進(jìn)制數(shù)字，前兩位是區(qū)號共94個區(qū)，每區(qū)94位。 國標(biāo)區(qū)位碼和國標(biāo)碼之間可用計算公式相互轉(zhuǎn)換。 區(qū)位碼轉(zhuǎn)換為國標(biāo)碼的方法是，先將十進(jìn)制區(qū)位碼轉(zhuǎn)換成十六進(jìn)制，然后在兩個字節(jié)上分別加20（十六進(jìn)制）就得到國標(biāo)碼。 在國標(biāo)碼的兩個字節(jié)上各加80（十六進(jìn)制）就轉(zhuǎn)換為漢字機(jī)內(nèi)碼了。 目前應(yīng)用較為廣泛的是采用國標(biāo)碼和區(qū)位碼進(jìn)行代碼標(biāo)識，形成兩字節(jié)漢字機(jī)內(nèi)碼。這種兩字節(jié)的漢字機(jī)內(nèi)碼，可以很方便地從漢字的序數(shù)計算出該漢字在字符串中的存儲位置。,漢字區(qū)位碼轉(zhuǎn)換為機(jī)內(nèi)碼的過程,以漢字“雹”為例的轉(zhuǎn)換過程如下：,采用漢字標(biāo)識法的多個字節(jié)代碼,在每個漢字代碼前增加一個標(biāo)識字節(jié)，就形成所謂多字節(jié)的漢字機(jī)內(nèi)碼。例如將漢字國標(biāo)碼轉(zhuǎn)換成字母和數(shù)字表示的三個字節(jié)，然后在這三個字節(jié)之前增加一個漢字標(biāo)記字節(jié)，這種標(biāo)記字節(jié)可用來適應(yīng)各種不同的要求。但是這種機(jī)內(nèi)碼的編輯性較差，占用字節(jié)量大；一般用在要求較高的軟件系統(tǒng)中或傳輸過程中作為系統(tǒng)