《算法與數(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》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第2章常用數(shù)據(jù)結(jié)構(gòu)ppt.ppt（113頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、 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(xy) 返回0 else 返回x-y end ADT NaturalNumber;,抽象數(shù)據(jù)類(lèi)型（續(xù)）,抽象數(shù)據(jù)類(lèi)型是算法設(shè)計(jì)和程序設(shè)計(jì)中的重要概念，這個(gè)概念明確地把數(shù)據(jù)結(jié)

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

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

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

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

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

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

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

26、oc(a11)+(i-1)*n+j-1)*e 同理可推出以列為主序優(yōu)先存儲(chǔ)的地址計(jì)算公式為 loc(aij)= loc(a11)+(j-1)*m+i-1)*e,元素存儲(chǔ)地址計(jì)算公式（續(xù)）,前面討論的公式是假設(shè)了數(shù)組的下標(biāo)下界均為1時(shí)的計(jì)算公式。 對(duì)于一般情況下的數(shù)組Ac1d1,c2d2 在行為主序之下aij的地址計(jì)算公式為 loc(aij)= loc(a11)+(i-c1)*(d2-c2+1)+j-c2)*e 在列為主序之下aij的地址計(jì)算公式為 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ù)組的順

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

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

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

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

31、矩陣的壓縮存儲(chǔ),在n階矩陣中，若元素滿(mǎn)足aij=aji則稱(chēng)之為對(duì)稱(chēng)矩陣。 由于對(duì)稱(chēng)矩陣中元素關(guān)于主對(duì)角線對(duì)稱(chēng)，因此只需要存儲(chǔ)其上三角中的元素或下三角中的元素，使對(duì)稱(chēng)元素共享同一存儲(chǔ)空間。 假如只存儲(chǔ)下三角中的元素，則需存儲(chǔ)元素總數(shù)為n*(n+1)/2個(gè)，按行為主序順序存儲(chǔ)，其映像關(guān)系為 也可以給出一個(gè)統(tǒng)一的對(duì)應(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ù)類(lèi)型與數(shù)據(jù)結(jié)構(gòu) 2.2 數(shù)組 2.3 串,2.3 串,所謂串，就是我們?cè)诟呒?jí)語(yǔ)言程序設(shè)計(jì)課程中學(xué)習(xí)和使用過(guò)的字符串，是大家熟知的概念。 串是許多軟件系統(tǒng)的操作對(duì)象，

32、如字符編輯系統(tǒng)、情報(bào)檢索系統(tǒng)、詞法分析系統(tǒng)、符號(hào)處理系統(tǒng)、語(yǔ)言翻譯系統(tǒng)等，有著十分廣泛的應(yīng)用。 本節(jié)著重討論串的存儲(chǔ)結(jié)構(gòu)以及主要運(yùn)算的實(shí)現(xiàn)，如順序存儲(chǔ)分配的三種方式、堆式存儲(chǔ)分配策略以及在“向量存儲(chǔ)，定長(zhǎng)結(jié)構(gòu)”基礎(chǔ)上幾種串運(yùn)算的實(shí)現(xiàn)算法，并簡(jiǎn)要介紹漢字串的概念。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長(zhǎng)順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動(dòng)態(tài)存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 2.3.5 漢字串,串的基本概念,串（String）是由零個(gè)或多個(gè)字符組成的有限序列。 記作: s=“a1a2an” (n0) 其中：s是串名，用雙引號(hào)括起來(lái)的字符序列是串的值（不含雙引號(hào)）；ai

33、（1in）是相應(yīng)程序設(shè)計(jì)語(yǔ)言中允許使用的字符集中的任意字符；n為串中的字符個(gè)數(shù)，稱(chēng)作串的長(zhǎng)度。 零個(gè)字符的串稱(chēng)作空串，它的長(zhǎng)度為零，串內(nèi)無(wú)任何字符。 要注意空串與空格串的區(qū)別，空格串中有一個(gè)或多個(gè)空格字符，串的長(zhǎng)度大于零。,串的基本概念（續(xù)）,串中任意多個(gè)連續(xù)字符組成的子序列稱(chēng)作該串的子串（Substring），包含子串的串稱(chēng)作該子串的主串。字符在串中的序號(hào)稱(chēng)作該字符在串中的位置，子串在主串中的位置用子串的第一個(gè)字符在主串中的位置來(lái)表示。 兩個(gè)串相等是指這兩個(gè)串的值相等，即兩個(gè)串長(zhǎng)度相等且對(duì)應(yīng)字符都相同時(shí)才相等。 串結(jié)構(gòu)的形式化定義為 string=(D,R) 其中：D= aiaicharac

34、ter，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，若st 返回值0。 StrLenth(s)：求串長(zhǎng)。返回值為串s中字符的個(gè)數(shù)（串長(zhǎng)）。 StrConcat(l,s,t)：串聯(lián)接。把串t的值緊接著串s的值之后形成的新串值存入串變量l中返回。例如，若s=“baodao”，t=“taiwan”，則l=“baodaotaiwan”

35、。 SubString(t,s,i,len)：求子串。把串s 中第i個(gè)字符開(kāi)始的長(zhǎng)度為len的字符序列存入串變量t中返回。該運(yùn)算要求1iStrLength(s)+1且0lenStrLength(s)- i +1。,串的其它運(yùn)算（四種）,其它的串運(yùn)算都可以由這六種基本運(yùn)算來(lái)實(shí)現(xiàn)。 下面四種其它的串運(yùn)算都有著重要的應(yīng)用： StrInsert(s,i,t)：串插入。運(yùn)算的結(jié)果是把t串插入到s串中第i個(gè)字符之前得到的新串。其中，1iStrLength(s)+1。 StrDelete(s,i,len)：串刪除。運(yùn)算的結(jié)果是從s串中刪去自第i個(gè)字符起的len 個(gè)字符后得到的新串。其中，1iStrLengt

36、h(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 串的定長(zhǎng)順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動(dòng)態(tài)存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 2.3.5 漢字串,串的定長(zhǎng)順序存儲(chǔ),當(dāng)一維數(shù)組的基類(lèi)型是字符類(lèi)型，形成的字符數(shù)組即字符串或串。 在高級(jí)程序設(shè)計(jì)語(yǔ)言中，大都為字符

37、串設(shè)立了專(zhuān)門(mén)的數(shù)據(jù)類(lèi)型。 在C語(yǔ)言中，有串常量和串變量的概念。用雙引號(hào)括起來(lái)的字符序列為字符串常量，也可以用宏定義#define來(lái)定義字符串常量的標(biāo)識(shí)符，如 #define CITY shanghai 對(duì)于字符串變量，C語(yǔ)言的說(shuō)明為一維字符型數(shù)組，如 static char C100； 為字符串分配一個(gè)固定長(zhǎng)度的一組地址連續(xù)的存儲(chǔ)單元的存儲(chǔ)分配方法稱(chēng)之為定長(zhǎng)順序存儲(chǔ)分配。,定長(zhǎng)順序存儲(chǔ)緊縮方式,計(jì)算機(jī)按字編址、每個(gè)單元存放四個(gè)字符。 如串s=“data structure 2.3”的緊縮存儲(chǔ)如下： 其中字符串長(zhǎng)度18存儲(chǔ)在開(kāi)始處，“ ”表示空格字符，共占用五個(gè)存儲(chǔ)單元。 緊縮方式對(duì)串長(zhǎng)是顯式地

38、直接存儲(chǔ)，字符依次順序放在連續(xù)的幾個(gè)單元中。這種存儲(chǔ)方式的優(yōu)點(diǎn)是充分地利用了空間，然而四個(gè)字符一個(gè)地址運(yùn)算不太方便。,定長(zhǎng)順序存儲(chǔ)非緊縮方式,計(jì)算機(jī)按字編址，每個(gè)單元存放一個(gè)字符。串的長(zhǎng)度不顯式存儲(chǔ)，由串中字符占存儲(chǔ)單元的數(shù)目來(lái)隱式確定。 非緊縮存儲(chǔ)方式方便了串運(yùn)算，但存儲(chǔ)空間沒(méi)有得到有效利用。 例如對(duì)串s=“data structure 2.3”的非緊縮存儲(chǔ)如右圖所示。,定長(zhǎng)順序存儲(chǔ)單字節(jié)存儲(chǔ)方式,計(jì)算機(jī)按字節(jié)編址，每個(gè)字節(jié)存放一個(gè)字符。 每個(gè)地址對(duì)應(yīng)一個(gè)字節(jié)，一個(gè)字節(jié)正好存放一個(gè)字符。這時(shí)的串長(zhǎng)度也不必存儲(chǔ)，由串占用的字節(jié)數(shù)隱式確定；也可用特殊字符作為串的結(jié)束標(biāo)志，如用“0”作結(jié)束標(biāo)志。

39、這種存儲(chǔ)方式既不浪費(fèi)空間，又使串中每個(gè)字符與惟一地址對(duì)應(yīng)方便了運(yùn)算，對(duì)于按字節(jié)編址的計(jì)算機(jī)而言是非常合適的。 例如對(duì)串s=“data structure 2.3”的單字節(jié)存儲(chǔ)方式如右圖所示。,定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)的運(yùn)算實(shí)現(xiàn),為了方便討論，我們把串的類(lèi)型說(shuō)明改寫(xiě)成如下形式： #define STRINGLEN 81 struct string int len; static char chSTRINGLEN； typedef struct string STRING； 并假定串尾以“0”作結(jié)束標(biāo)志。 由于串賦值和串復(fù)制在高級(jí)程序設(shè)計(jì)語(yǔ)言中是通過(guò)賦值語(yǔ)句來(lái)完成的，所以在這里只討論其余四種基本運(yùn)算，即串

40、比較、求串長(zhǎng)、串聯(lián)接和求子串運(yùn)算。,1.串比較,int StrCompare(s,t) /*串的比較，若st返回值0，若s=t返回值=0，否則返回值chi=t-chi) 該算法的主要時(shí)間開(kāi)銷(xiāo)在于兩串相等時(shí)的逐個(gè)字符比較，比較次數(shù)為字符串的長(zhǎng)度，所以在最壞情況下的時(shí)間復(fù)雜度為O(mins-len,t-len)；在最好情況下是當(dāng)兩串的第一個(gè)字符不等時(shí)，只需要O(1)的時(shí)間，與問(wèn)題規(guī)模即串的長(zhǎng)度無(wú)關(guān)。,2.求串長(zhǎng)（1）,按假設(shè)的串類(lèi)型說(shuō)明，由于有串長(zhǎng)域len故可直接返回其值即可。 算法描述如下： int StrLength(s)/*求串長(zhǎng)即串s中字符的個(gè)數(shù)*/ STRING *s; return s

41、-len; /*直接返回串長(zhǎng)域的值即可*/,2.求串長(zhǎng)（2）,在C語(yǔ)言中是沒(méi)有設(shè)串長(zhǎng)域的，需要對(duì)一維字符數(shù)組中的字符個(gè)數(shù)統(tǒng)計(jì)結(jié)果。 所以改寫(xiě)算法為： int StrLength(s) STRING *s; int i=0; /*初始化數(shù)組下標(biāo)和串長(zhǎng)域len*/ s-len=0; while(s-chi!=0) s-len+； return s-len； 該算法的主要時(shí)間開(kāi)銷(xiāo)在于逐個(gè)字符統(tǒng)計(jì)串長(zhǎng)度的循環(huán)，其時(shí)間復(fù)雜度為O(s-len)。,3.串聯(lián)接,在實(shí)現(xiàn)串的聯(lián)接運(yùn)算時(shí)，要注意兩串s和t聯(lián)接后的結(jié)果串L超過(guò)定長(zhǎng)的問(wèn)題，即：s-len+t-len=STRINGLEN時(shí)結(jié)果串超過(guò)定長(zhǎng)STRINGLE

42、N，此時(shí)算法中輸出相應(yīng)提示信息。 其算法描述如下： void StrConcat(l,s,t) STRING *l,*s,*t; int i,j; if(s-len+t-lenSTRINGLEN) printf(“結(jié)果串L的長(zhǎng)度超過(guò)串的定長(zhǎng)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ù)）,該算法的時(shí)間開(kāi)銷(xiāo)主要在于復(fù)制兩個(gè)串中字符到結(jié)果串中，其復(fù)制字符個(gè)數(shù)為兩個(gè)串的長(zhǎng)度之和，故其時(shí)間復(fù)雜度為O(

43、s-len+t-len)。 串的聯(lián)接運(yùn)算不滿(mǎn)足交換律，這一點(diǎn)由串聯(lián)接的定義是顯而易見(jiàn)的。 然而，串的聯(lián)接運(yùn)算是滿(mǎn)足結(jié)合律的；在多個(gè)串聯(lián)接時(shí)，只要位置次序不變，先聯(lián)接哪兩個(gè)都無(wú)所謂，最終結(jié)果都是一樣的。,4.求子串,在設(shè)計(jì)求子串算法時(shí)要注意算法的健壯性要求，即要檢查子串開(kāi)始位置i和子串長(zhǎng)度len的合法性。 當(dāng)ilen時(shí)，子串開(kāi)始位置非法； 當(dāng)lens-len-i時(shí)，子串的長(zhǎng)度非法。 對(duì)于這些非法的數(shù)據(jù)（參數(shù)），要給出相應(yīng)的錯(cuò)誤信息。 求子串的算法描述如下： void SubString(t,s,i,len) STRING *t,*s; int i,len; int j; if(i=s-len)

44、printf(“子串的開(kāi)始位置i越界錯(cuò)誤n”);,4.求子串（續(xù)）,else if(lens-len-i) printf(“子串的長(zhǎng)度len越過(guò)主串錯(cuò)誤n”); else for(j=0;jchj=s-chi /*將所求子串存入t串中*/ t-chj=0; /*為子串t添加結(jié)束標(biāo)志*/ t-len=len; /*設(shè)置子串長(zhǎng)度*/ 該算法的主要時(shí)間開(kāi)銷(xiāo)在于從主串s中取出子串存于t中，而子串的最大長(zhǎng)度等于主串，主串最長(zhǎng)為預(yù)先定義好的定長(zhǎng)STRINGLEN，所以其時(shí)間復(fù)雜度為O(STRINGLEN)。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長(zhǎng)順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 2.3.3 模式匹配

45、 2.3.4 串的堆式動(dòng)態(tài)存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 2.3.5 漢字串,模式匹配,子串的定位操作通常稱(chēng)作模式匹配，子串t稱(chēng)作模式，在主串s中確定t的位置的過(guò)程稱(chēng)作匹配過(guò)程。 模式匹配在文本編輯、文件檢索和各種串處理系統(tǒng)中有著廣泛的應(yīng)用，因此它是最重要的串運(yùn)算之一。然而模式匹配不是串的基本運(yùn)算，它可以借用串的基本運(yùn)算來(lái)實(shí)現(xiàn)。 利用串比較、求串長(zhǎng)和求子串三種基本操作實(shí)現(xiàn)模式匹配的算法描述： int StrIndex(s,t) /*匹配成功返回子串位置，否則返回-1*/ STRING *s,*t; int n,m,i,bool; STRING *l; n=StrLength(s); /*求主串s的長(zhǎng)度于n*/

46、,模式匹配（續(xù)）,m=StrLength(t); /*求模式串t的長(zhǎng)度于m*/ i=0; bool=-1; while(i0) return i; else return -1; ,簡(jiǎn)單的模式匹配算法,簡(jiǎn)單的模式匹配算法的思想是： 從主串s的第一個(gè)字符開(kāi)始和模式t的第一個(gè)字符比較， 若相等則繼續(xù)逐個(gè)比較后續(xù)字符， 若某一次對(duì)應(yīng)字符不相等則從主串s 中的第二個(gè)字符起再重新和模式t的每個(gè)字符逐個(gè)比較。 依次類(lèi)推，直到模式t中每個(gè)字符都和主串s中的一個(gè)連續(xù)字符序列對(duì)應(yīng)相等則匹配成功，函數(shù)值為模式t中第一個(gè)字符所對(duì)應(yīng)的字符在主串s中的序號(hào)； 若掃描完主串s后還未找到模式t 的出現(xiàn)則匹配失敗，函數(shù)值為-

47、1。,簡(jiǎn)單的模式匹配的過(guò)程描述,對(duì)于模式串t=“abcac”和主串s=“ababcabcacbab”使用算法Index(s,t)的匹配過(guò)程如下：,簡(jiǎn)單的模式匹配的過(guò)程描述(續(xù)),簡(jiǎn)單的模式匹配的算法（續(xù)）,算法Index(s,t)簡(jiǎn)單，算法思想自然，匹配過(guò)程容易理解。 在許多應(yīng)用場(chǎng)合如文本編輯等，匹配效率也較高。 在這樣一種較好的匹配情況下，即每趟中不成功的匹配都發(fā)生在第一對(duì)字符比較時(shí)，其時(shí)間復(fù)雜度為O(n+m)。 然而在最壞情況下，即每趟不成功的匹配都發(fā)生在模式串t中最后一個(gè)字符時(shí)，其時(shí)間復(fù)雜度為O(n*m)，算法效率很低。,一種改進(jìn)的模式匹配算法,這種改進(jìn)的模式匹配算法是D.E.Knuth

48、與J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)的，因此人們稱(chēng)它為克努特莫里斯普拉特算法，簡(jiǎn)稱(chēng)為KMP算法。 該算法可以在O(n+m)的時(shí)間數(shù)量級(jí)上完成串的模式匹配運(yùn)算。 其改進(jìn)思想是充分利用部分匹配的信息，不需回溯主串指示器變量i，而是在匹配過(guò)程中出現(xiàn)字符比較不等時(shí)，將模式串t盡可能遠(yuǎn)地向右滑動(dòng)一段距離后繼續(xù)進(jìn)行比較。,一種改進(jìn)的模式匹配算法（續(xù)）,回顧前述的匹配過(guò)程示例，在第三趟的匹配中當(dāng)i=6、j=4比較字符不等時(shí)，又從i=3、j=0重新開(kāi)始比較。仔細(xì)觀察可以發(fā)現(xiàn)，在i=3和j=0、i=4和j=0、i=5和j=0這三次比較都是不必進(jìn)行的；這是由于從第三趟部分匹配的結(jié)果就可以得出主串中的

49、第4、5和6個(gè)字符（即i=3、4和5）和模式串中的第2、3和4個(gè)字符（即j=1、2和3）相同為b、c和a，而模式串中的第一個(gè)字符（即j=0）是a無(wú)需再和這三個(gè)字符進(jìn)行比較，僅需將模式串向右滑動(dòng)三個(gè)字符的位置進(jìn)行i=6、j=1時(shí)的字符比較即可。同理，在第一趟匹配中出現(xiàn)字符不等時(shí)，僅需將模式串向右滑動(dòng)兩個(gè)字符位置進(jìn)行i=2、j=0時(shí)的字符比較。,一種改進(jìn)的模式匹配的匹配過(guò)程,值得注意的是在整個(gè)匹配過(guò)程中i指示器變量的值沒(méi)有回溯。,改進(jìn)的模式匹配的一般化思路,對(duì)于模式串t=“t0t1tm-1”和主串s=“s0s1sn-1”，當(dāng)匹配過(guò)程中sitj產(chǎn)生失配時(shí)，模式串向右滑動(dòng)多遠(yuǎn)距離？ 或者說(shuō)失配時(shí)i指示

50、器變量不回溯，主串中第i個(gè)字符應(yīng)該與模式串中哪個(gè)字符再繼續(xù)比較？ 設(shè)此時(shí)應(yīng)該與模式串中第k(kj)個(gè)字符比較，則模式t中前k-1個(gè)字符的子串應(yīng)該滿(mǎn)足如下關(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”等式說(shuō)明，在某趟匹配過(guò)程中sitj失配時(shí)，如果模式串中前j-1個(gè)字符

51、中存在首尾相同的最大子串長(zhǎng)度為k-1，即模式t中前k-1個(gè)字符與tj前的k-1個(gè)字符對(duì)應(yīng)相等時(shí)，模式t就可以向右滑動(dòng)k個(gè)字符位置即si與tk繼續(xù)比較了。 模式t中的每一個(gè)tj都對(duì)應(yīng)一個(gè)k值，這個(gè)k值表示當(dāng)在tj處失配時(shí)模式t應(yīng)向右滑動(dòng)的字符數(shù)，它僅依賴(lài)于模式t而與主串s無(wú)關(guān)。 令nextj=k，則可引出next函數(shù)的定義如下：,改進(jìn)的模式匹配的一般化思路,由next函數(shù)的定義可推出模式“abaabcac”的next函數(shù)值為： 有了next函數(shù)之后，匹配過(guò)程可以這樣進(jìn)行：令指示器變量i和j的值都為0，若在匹配過(guò)程中si=tj；則i和j分別加1，否則i不變而j退到nextj的位置再比較；若相等i和

52、j各加1，否則j退到下一個(gè)next值的位置，依此類(lèi)推直到下面兩種可能： 一是退到某next值（nextnextnextj）時(shí)字符比較相等，指示器變量值各加1后繼續(xù)比較； 另一種是退到值為零（即模式的第一個(gè)字符失配），此時(shí)需將模式繼續(xù)向右滑動(dòng)一個(gè)位置，從主串的下一個(gè)字符si+1重新開(kāi)始匹配。,改進(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的匹配過(guò)程,求模式串t的next函數(shù)值的

53、算法,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的時(shí)間復(fù)雜度為O(m)。通常模式串的長(zhǎng)度m要比主串的長(zhǎng)度n小得多，因此對(duì)整個(gè)匹配算法KMP來(lái)說(shuō)增加這點(diǎn)求next函數(shù)的時(shí)間是值得的。 需要說(shuō)明的是，算法index的時(shí)間復(fù)雜度雖然是O(

54、m*n)，但在一般情況下其實(shí)際執(zhí)行時(shí)間近似于O(m+n)，所以至今仍被采用。 算法index_KMP僅當(dāng)模式串與主串之間存在許多部分匹配的情況下才顯得比算法index快得多。 index_KMP算法的最大特點(diǎn)是不需回溯主串的指示器變量i，整個(gè)匹配過(guò)程只需從頭到尾掃描主串一遍，特別適用于從外設(shè)讀入龐大文件邊讀入邊匹配，無(wú)需回頭重讀。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長(zhǎng)順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動(dòng)態(tài)存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 2.3.5 漢字串,串的堆式動(dòng)態(tài)存儲(chǔ),在處理串的應(yīng)用程序中，所處理的串的長(zhǎng)度相差往往較大，處理過(guò)的串值長(zhǎng)度變化往往也較大。 采

55、用定長(zhǎng)順序存儲(chǔ)在多數(shù)串的串長(zhǎng)較小時(shí)其空間利用率低，且使某些運(yùn)算如串聯(lián)接和串置換等受到限制或產(chǎn)生錯(cuò)誤結(jié)果。 因此，在許多實(shí)際應(yīng)用的串處理系統(tǒng)中采用的是堆式動(dòng)態(tài)存儲(chǔ)分配策略。,堆式動(dòng)態(tài)存儲(chǔ)的思想,應(yīng)用系統(tǒng)在內(nèi)存中開(kāi)辟一個(gè)容量很大且地址連續(xù)的一片存儲(chǔ)空間，作為存放所有串值的可利用空間即堆空間。 例如一維數(shù)組store char storemaxsize 表示堆空間，其中maxsize表示這片連續(xù)存儲(chǔ)空間的最大容量。 設(shè)整形變量free指示該空間中尚未分配區(qū)間的開(kāi)始地址（初始值為1）。 每當(dāng)產(chǎn)生一個(gè)串時(shí)，應(yīng)用程序就在執(zhí)行過(guò)程中動(dòng)態(tài)地從free指示的位置為串值分配一個(gè)長(zhǎng)度與串長(zhǎng)相同的存儲(chǔ)空間，并相應(yīng)修改

56、free的值； 同時(shí)建立該串的一個(gè)描述，指示串的長(zhǎng)度和該串在store中的第一個(gè)字符位置。,串的堆式動(dòng)態(tài)存儲(chǔ)分配示意圖,其中：length指示串值序列的長(zhǎng)度， start指示串值序列在store中的開(kāi)始地址。,串的存儲(chǔ)映像,借助length和start在堆結(jié)構(gòu)的串名與串值之間建立起一個(gè)對(duì)應(yīng)關(guān)系，稱(chēng)作串名的存儲(chǔ)映像。 所有的串名存儲(chǔ)映像構(gòu)成了一張為系統(tǒng)中所有串名和串值之間建立一一對(duì)應(yīng)關(guān)系的映像表（或符號(hào)表）。,堆式動(dòng)態(tài)存儲(chǔ)的串的類(lèi)型說(shuō)明,#define MAXSIZE 10000 /*MAXSIZE為堆的最大容量*/ struct string /*定義串為結(jié)構(gòu)體*/ int length; /

57、*串長(zhǎng)度*/ int start; /*串在堆中的開(kāi)始位置*/ typedef struct string STRING; /*定義串類(lèi)型標(biāo)識(shí)符為STRING*/ char storeMAXSIZE; /*定義堆為一維數(shù)組store*/ int free; /*堆store中尚未分配區(qū)間的開(kāi)始地址指示器變量*/,堆式動(dòng)態(tài)存儲(chǔ)的串賦值算法,該運(yùn)算把存儲(chǔ)于字符串?dāng)?shù)組chars中的字符串常量存入堆store中，并為s建立存儲(chǔ)映像。在邏輯上即為串變量s賦一個(gè)字符串常量值。 其算法描述如下： void StrAssign(s,chars) STRING *s; char chars; int i,len

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

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

60、,s,t) STRING *l,*s,*t; STRING *p; /*設(shè)一個(gè)內(nèi)部串變量p*/ StrCopy(l,s); /*復(fù)制s到l中去*/ StrCopy(p,t); /*復(fù)制t到p中去*/ l-length=s-length+t-length; /*修改l的存儲(chǔ)映像中的串長(zhǎng)*/ 注意，為什么算法中沒(méi)有修改l的開(kāi)始位置？又為什么未見(jiàn)修改堆中指示器變量free的語(yǔ)句？這是因?yàn)榈谝粋€(gè)串復(fù)制語(yǔ)句已使l的開(kāi)始位置到位，而第二個(gè)串復(fù)制語(yǔ)句已使free的值指向尚未分配區(qū)的開(kāi)始位置，故只需修改串長(zhǎng)即可。,堆式動(dòng)態(tài)存儲(chǔ)的求子串算法,和串復(fù)制運(yùn)算一樣，求子串運(yùn)算也有復(fù)制和共享兩種實(shí)現(xiàn)方法。這里給出共享實(shí)

61、現(xiàn)算法如下： void SubString(t,s,i,len) /*將s中第i個(gè)字符開(kāi)始的len個(gè)字符構(gòu)成的子串送到t中*/ STRING *t,*s; int i,len; if(is-length-i) printf(“所給子串的位置或長(zhǎng)度有錯(cuò)誤n”); else t-length=len; /*建立子串t的存儲(chǔ)映像*/ t-start=s-start+i; ,2.3 串,2.3.1 串的基本概念 2.3.2 串的定長(zhǎng)順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 2.3.3 模式匹配 2.3.4 串的堆式動(dòng)態(tài)存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 2.3.5 漢字串,漢字串,漢字是一種拼形和表意文字。 無(wú)論是西文還是漢字，計(jì)算機(jī)系統(tǒng)均應(yīng)

62、具有輸入、加工處理和輸出的功能，并能在不同的系統(tǒng)之間進(jìn)行信息交換。 對(duì)應(yīng)于不同的功能，在計(jì)算機(jī)系統(tǒng)中用不同的代碼來(lái)表示： 用戶(hù)在輸入設(shè)備上輸入文字信息時(shí)，由輸入設(shè)備產(chǎn)生相應(yīng)的代碼稱(chēng)作輸入碼或外部碼； 在計(jì)算機(jī)內(nèi)部存儲(chǔ)和處理文字信息所采用的代碼稱(chēng)作機(jī)內(nèi)碼； 為了表示文字字形，通常是設(shè)計(jì)表示不同字形的字模點(diǎn)陣，這種碼稱(chēng)作字模點(diǎn)陣碼； 在系統(tǒng)之間傳輸和交換信息的代碼稱(chēng)作交換碼。,漢字串（續(xù)）,對(duì)于西文來(lái)說(shuō)，由于借助于拼音規(guī)則可只用少量字母拼成文字，因而其機(jī)內(nèi)碼、輸入碼和交換碼等的數(shù)據(jù)結(jié)構(gòu)都比較簡(jiǎn)單； 在設(shè)計(jì)這些代碼時(shí)已盡可能做到相互一致，代碼間的轉(zhuǎn)換也非常簡(jiǎn)單。 目前大多數(shù)計(jì)算機(jī)均以ASCII碼作為

63、西文的機(jī)內(nèi)碼，也有用EBCDIC碼作機(jī)內(nèi)碼的，它們都是按每個(gè)字節(jié)存放一個(gè)字符設(shè)計(jì)的。 當(dāng)向計(jì)算機(jī)輸入西文信息時(shí)，只要在鍵盤(pán)上按不同的鍵就可產(chǎn)生不同的輸入代碼，這些輸入碼集可以簡(jiǎn)單地等同于機(jī)內(nèi)碼集。 因此，當(dāng)構(gòu)成串的字符集限于西文字母、數(shù)字和其它字符時(shí)，往往不考慮它的機(jī)內(nèi)碼而直接討論串值的存儲(chǔ)結(jié)構(gòu)。,漢字代碼轉(zhuǎn)換關(guān)系示意圖,采用漢字串標(biāo)識(shí)法的七位碼方法,以ASCII碼集或其子集作為基集，由兩個(gè)或兩相以上的ASCII字符構(gòu)成一個(gè)漢字機(jī)內(nèi)碼。 例如，用電報(bào)碼作為漢字機(jī)內(nèi)碼。電報(bào)碼是以ASCII字符集的子集C=0,1,29為基集，由四個(gè)09的數(shù)字字符構(gòu)成一個(gè)漢字機(jī)內(nèi)碼。為了與西文ASCII字符區(qū)分，可

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

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