【正文】 算法與數(shù)據(jù)結(jié)構(gòu) 第 2章 常用數(shù)據(jù)結(jié)構(gòu) 第 2章 常用數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 數(shù)組 串 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù) 、 數(shù)據(jù)元素與數(shù)據(jù)類型 數(shù)據(jù)結(jié)構(gòu)的基本概念 抽象數(shù)據(jù)類型 數(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ī)科學(xué)與技術(shù)學(xué)科 ， 數(shù)據(jù)泛指那些能夠被計(jì)算機(jī)接收 、 識(shí)別 、 存儲(chǔ) 、 加工和處理的對(duì)象的全體 。 ?換句話說(shuō) ， 數(shù)據(jù)是對(duì)那些能夠有效地輸入到計(jì)算機(jī)中并且能夠被計(jì)算機(jī)程序所加工和處理的符號(hào)全體的總稱 。 ?只要是能被計(jì)算機(jī)識(shí)別 、 存儲(chǔ) 、 加工和處理的都屬于數(shù)據(jù)的范疇 。 數(shù)據(jù)元素 ?數(shù)據(jù)的基本單位是 數(shù)據(jù)元素 （ Data Element） ， 有時(shí)也稱作元素 、 結(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í)間 、 工資級(jí)別 、 職稱 、 職務(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)劃分 ， 劃分的結(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ù)元素具有相同性質(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ù)類型 ?數(shù)據(jù)類型 （ Data Type） 是對(duì)在計(jì)算機(jī)中表示的同一數(shù)據(jù)對(duì)象及其在該數(shù)據(jù)對(duì)象上的一組操作的總稱 。 ?如整數(shù)數(shù)據(jù) ， 在計(jì)算機(jī)中它是集合 {minint… maxint}上的整數(shù) （ 其中 minint和 maxint分別是最小整數(shù)和最大整數(shù) ， 在不同的計(jì)算機(jī)中表示的值不同；且這個(gè)集合是有窮集合 ，是數(shù)學(xué)意義上的無(wú)窮集合的一個(gè)子集 ） ， 在這個(gè)集合上可以進(jìn)行的操作有加 、 減 、 乘 、 整除和求模等算術(shù)運(yùn)算以及等于 、 不等于 、 大于 、 小于 、 大于等于和小于等于等關(guān)系運(yùn)算 。 ?數(shù)據(jù)對(duì)象整數(shù)以及在整數(shù)集合上的算術(shù)運(yùn)算和關(guān)系運(yùn)算等操作一起構(gòu)成了整型這個(gè)數(shù)據(jù)類型 。 數(shù)據(jù)類型（續(xù)） ?數(shù)據(jù)類型有簡(jiǎn)單 （ 或原子 ） 數(shù)據(jù)類型和結(jié)構(gòu)數(shù)據(jù)類型之分 。 ?簡(jiǎn)單數(shù)據(jù)類型 是由程序設(shè)計(jì)語(yǔ)言提供的一些基本類型 。如整型 、 實(shí)型 、 布爾型和字符型等 ， 其值不可再分解 。 ?結(jié)構(gòu)數(shù)據(jù)類型 是由程序設(shè)計(jì)語(yǔ)言中提供的構(gòu)造機(jī)制來(lái)定義的數(shù)據(jù)類型 。 如數(shù)組 、 文件 、 結(jié)構(gòu)體 、 共用體等 ， 其值可以再分解；它的構(gòu)成成分可以是簡(jiǎn)單數(shù)據(jù)類型 ， 也可以是結(jié)構(gòu)數(shù)據(jù)類型 。 ? 數(shù)據(jù)類型的概念 ， 是程序設(shè)計(jì)語(yǔ)言和程序設(shè)計(jì)過(guò)程中的一個(gè)非常重要的概念 。 數(shù)據(jù)類型的特征 ?類型決定了變量或表達(dá)式所有可能取值的全體成員集合 。 ?每一個(gè)值隸屬于且僅隸屬于某一類型 。 ?任何常量 、 變量或表達(dá)式的類型 ， 都可以從其形式上或所處的上下文關(guān)系中推斷出來(lái) ， 無(wú)須了解在程序運(yùn)行時(shí)計(jì)算出的具體值 。 ?每一種操作都要求一定類型的操作數(shù)據(jù) ， 且得出一定類型的操作結(jié)果 。 ?一種類型的值及其在該類型上規(guī)定的基本操作的性質(zhì)可由一組公理來(lái)闡明 。 ?高級(jí)程序設(shè)計(jì)語(yǔ)言使用類型信息去防止程序中出現(xiàn)無(wú)意義的結(jié)構(gòu) ， 又由類型信息確定在計(jì)算機(jī)中的數(shù)據(jù)表示和數(shù)據(jù)處理方法 。 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù) 、 數(shù)據(jù)元素與數(shù)據(jù)類型 數(shù)據(jù)結(jié)構(gòu)的基本概念 抽象數(shù)據(jù)類型 數(shù)據(jù)結(jié)構(gòu)的基本概念 ?數(shù)據(jù)結(jié)構(gòu) （ Data Structure） 是指計(jì)算機(jī)程序中所操作的對(duì)象 ——數(shù)據(jù)以及數(shù)據(jù)元素之間的相互關(guān)系和運(yùn)算 。 ?在任何問(wèn)題中 ， 數(shù)據(jù)元素之間都不會(huì)是獨(dú)立的 ， 總是存在著這樣或那樣的關(guān)系 ， 這種數(shù)據(jù)元素之間的關(guān)系也稱作結(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è)二元組給出如下的形式定義： DataStructure ＝ （ D,R） 其中： ?D是數(shù)據(jù)元素的集合； ?R是 D上關(guān)系的集合 。 ?從結(jié)構(gòu)的觀點(diǎn)出發(fā) ， 一般可將數(shù)據(jù)結(jié)構(gòu)分為兩大類： ?線性結(jié)構(gòu) 如線性表 、 棧 、 隊(duì)列 、 串 、 數(shù)組和文件等； ?非線性結(jié)構(gòu) 如樹(shù) 、 圖和集合等 。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) ?數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) 是指數(shù)據(jù)及數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)內(nèi)存中的表示 ， 也稱作數(shù)據(jù)的物理結(jié)構(gòu)或存儲(chǔ)映像 。 ?主要的存儲(chǔ)方式有 順序存儲(chǔ) 和 鏈?zhǔn)酱鎯?chǔ) 兩種 ， 此外還有 索引存儲(chǔ) 和 散列存儲(chǔ) 等其它方式 。 ?從邏輯結(jié)構(gòu)到存儲(chǔ)結(jié)構(gòu)稱之為 映像 。 ?同一邏輯結(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í) ， 只考慮這些運(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)依賴于所選取的存儲(chǔ)結(jié)構(gòu) ， 也依賴于所選用的程序設(shè)計(jì)語(yǔ)言 。 線性結(jié)構(gòu) ?在線性結(jié)構(gòu)中 ， D中數(shù)據(jù)元素之間存在著一對(duì)一的次序關(guān)系 。 ?其邏輯特征為： ?存在一個(gè)惟一被稱作 “ 第一個(gè) ” 的數(shù)據(jù)元素 ， 它沒(méi)有前趨只有一個(gè)直接后繼；有時(shí)也稱作開(kāi)始結(jié)點(diǎn)； ?存在一個(gè)惟一被稱之為 “ 最后一個(gè) ” 的數(shù)據(jù)元素 ， 它沒(méi)有后繼只有一個(gè)直接前趨；有時(shí)也稱作終端結(jié)點(diǎn)； ?其它數(shù)據(jù)元素都有且僅有一個(gè)直接前趨 （ immediate predecessor） ， 也有且僅有一個(gè)直接后繼 （ immediate 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)稱之為 根結(jié)點(diǎn) ； ?除根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前趨 （ 稱之為 雙親結(jié)點(diǎn) ） ； ?沒(méi)有直接后繼的結(jié)點(diǎn)稱之為 葉結(jié)點(diǎn) ， 除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)都有一個(gè)或多個(gè)直接后繼 （ 稱之為 孩子結(jié)點(diǎn) ） 。 ?樹(shù)的例子很多 ， 如族譜中的家族樹(shù) 、 政府機(jī)構(gòu)中的行政樹(shù) 、 計(jì)算機(jī)文件管理中的目錄樹(shù) 、 編譯程序中用到的語(yǔ)法樹(shù)等 。 樹(shù)型結(jié)構(gòu)示意圖 根結(jié)點(diǎn) 葉結(jié)點(diǎn) 非線性結(jié)構(gòu) ——圖型結(jié)構(gòu) ?非線性結(jié)構(gòu)中的 圖結(jié)構(gòu) ， 其數(shù)據(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)系 。 ?換句話說(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ì)算機(jī)內(nèi)存儲(chǔ)器中開(kāi)辟一片地址連續(xù)的存儲(chǔ)單元順序存放數(shù)據(jù)中的各個(gè)元素；它把邏輯上相鄰的數(shù)據(jù)元素存放在物理上相鄰的存儲(chǔ)單元中 ， 利用物理上的鄰接關(guān)系表示邏輯上的先后次序關(guān)系 ， 這 種 存 儲(chǔ) 表 示 方 式 稱 作 順 序 存 儲(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ǔ)器中的任意位置 ， 借助指示數(shù)據(jù)元素存儲(chǔ)地址的指針表示元素間的邏輯關(guān)系 ， 這種存儲(chǔ)表示方式稱作 鏈?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í)間和空間效率要求 。 數(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)則依賴于所采用的存儲(chǔ)結(jié)構(gòu) 。 ?各種數(shù)據(jù)結(jié)構(gòu) ， 分別提供了不同類型的數(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ù)類型的方法或手段 。 如各種基本類型 ， 數(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)稱之為數(shù)據(jù)類型 。 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù) 、 數(shù)據(jù)元素與數(shù)據(jù)類型