【正文】 算法與數(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ī)中的數(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ù)項 是具有獨立含義的數(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ù)元素是對客觀世界中某個獨立個體的數(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ī)中它是集合 {minint… maxint}上的整數(shù) （ 其中 minint和 maxint分別是最小整數(shù)和最大整數(shù) ， 在不同的計算機(jī)中表示的值不同；且這個集合是有窮集合 ，是數(shù)學(xué)意義上的無窮集合的一個子集 ） ， 在這個集合上可以進(jìn)行的操作有加 、 減 、 乘 、 整除和求模等算術(shù)運算以及等于 、 不等于 、 大于 、 小于 、 大于等于和小于等于等關(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)造機(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)系中推斷出來 ， 無須了解在程序運行時計算出的具體值 。 ?每一種操作都要求一定類型的操作數(shù)據(jù) ， 且得出一定類型的操作結(jié)果 。 ?一種類型的值及其在該類型上規(guī)定的基本操作的性質(zhì)可由一組公理來闡明 。 ?高級程序設(shè)計語言使用類型信息去防止程序中出現(xiàn)無意義的結(jié)構(gòu) ， 又由類型信息確定在計算機(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ī)程序中所操作的對象 ——數(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) ， 而不管其存儲方式 ， 可用一個二元組給出如下的形式定義： DataStructure ＝ （ 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)酱鎯?兩種 ， 此外還有 索引存儲 和 散列存儲 等其它方式 。 ?從邏輯結(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)上進(jìn)行 。 ?常用的運算有檢索 、 插入 、 刪除 、 更新 、 排序等 。 ?在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義數(shù)據(jù)的運算時 ， 只考慮這些運算是 “ 做什么 ” ， 而不考慮它 “ 如何做 ” ， 是抽象運算；只有在選定了某種數(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） ， 也有且僅有一個直接后繼 （ 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é)點 葉結(jié)點 非線性結(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)的存儲 。 其他的存儲表示方式 ?存儲表示方式還有 索引存儲 方式和 散列存儲 方式 ，通常是為了檢索的方便所采用的存儲表示方法 。 ?一般地說 ， 這幾種基本的存儲表示方法 ， 既可以單獨使用 ， 也可以組合起來使用 。 ?選擇何種存儲結(jié)構(gòu)要依具體問題的要求而定 ， 既要考慮問題表示和運算的方便性 ， 也還會考慮到實現(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ù)時的組織 、 管理 、 存儲 、 運算和處理的方法和技術(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ù)類型 。 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù) 、 數(shù)據(jù)元素與數(shù)據(jù)類型