課程名稱：數(shù)據(jù)結(jié)構(gòu)（Data Structure）
任課教師：常寶寶（北京大學(xué)計(jì)算語言學(xué)研究所副教授）
學(xué)時(shí)：4學(xué)時(shí)/周 （2學(xué)時(shí)授課，2學(xué)時(shí)上機(jī)）
課程概要：
以C++語言為基礎(chǔ)，重點(diǎn)介紹線性表、棧、對(duì)列、樹和二叉樹等基本數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法、各種檢索和排序算法。概要介紹圖結(jié)構(gòu)和相關(guān)算法。除詳細(xì)講授數(shù)據(jù)基本概念和具體算法外，對(duì)每種數(shù)據(jù)結(jié)構(gòu)給出其C++語言實(shí)現(xiàn)，并給出定性或定量的算法分析。
課程目標(biāo)：
（1） 進(jìn)一步培養(yǎng)學(xué)生的程序設(shè)計(jì)能力，加深對(duì)C++語言的掌握和運(yùn)用。
（2） 培養(yǎng)學(xué)生學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)以及相應(yīng)的算法。
（3） 初步掌握算法的時(shí)間分析和空間分析的技巧。
（4） 通過同步上機(jī)實(shí)習(xí)，進(jìn)一步鍛煉學(xué)生的動(dòng)手能力，培養(yǎng)學(xué)生解決實(shí)際問題的能力。
1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 1.2 什么是數(shù)據(jù)結(jié)構(gòu) 1.3 抽象數(shù)據(jù)類型 1.4 算法的特性及分類 1.5 算法的效率度量 1.6 數(shù)據(jù)結(jié)構(gòu)的選擇和評(píng)價(jià)
北京大學(xué)信息學(xué)院 版權(quán)所有,轉(zhuǎn)載或翻印必究 Page 12
1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)
計(jì)算機(jī)軟件與理論學(xué)科的專業(yè)基礎(chǔ)課程 后續(xù)專業(yè)課程學(xué)習(xí)的必要知識(shí)與技能準(zhǔn)備
編譯技術(shù)要使用棧,散列表及語法樹 操作系統(tǒng)中用隊(duì)列,存儲(chǔ)管理表及目錄樹 數(shù)據(jù)庫(kù)系統(tǒng)運(yùn)用線性表,多鏈表,及索引樹 etc.
增強(qiáng)讀者求解復(fù)雜問題的能力
北京大學(xué)信息學(xué)院 版權(quán)所有,轉(zhuǎn)載或翻印必究 Page 13
1.2 什么是數(shù)據(jù)結(jié)構(gòu) (data structure)
數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算
北京大學(xué)信息學(xué)院 版權(quán)所有,轉(zhuǎn)載或翻印必究 Page 14
1.2.1 數(shù)據(jù)的邏輯結(jié)構(gòu)
反映了我們對(duì)數(shù)據(jù)含義的解釋 數(shù)據(jù)的邏輯結(jié)構(gòu)可以用一組數(shù)據(jù)(表示為結(jié)點(diǎn)集合 K),以及這些數(shù)據(jù)之間的一組二元關(guān)系(關(guān)系集合 R)來表示:( K ,R )
K是由有限個(gè)結(jié)點(diǎn)組成的集合,每一個(gè)結(jié)點(diǎn)都代表一個(gè)數(shù)據(jù) 或一組有明確結(jié)構(gòu)的數(shù)據(jù) 而關(guān)系集R是定義在集合K上的一組關(guān)系,其中每個(gè)關(guān)系 (relation) r(r∈R)都是K×K上的二元關(guān)系,用它描述結(jié) 點(diǎn)數(shù)據(jù)之間的邏輯關(guān)系
北京大學(xué)信息學(xué)院 版權(quán)所有,轉(zhuǎn)載或翻印必究 Page 15
數(shù)據(jù)的邏輯結(jié)構(gòu)(示例)
家族人員
把每個(gè)成員個(gè)體的屬性描述作為數(shù)據(jù)結(jié)點(diǎn),而全部人員組成 結(jié)點(diǎn)集K 家族的各類親屬關(guān)系就是一組關(guān)系R, 其中如母系血緣關(guān)系 r,遠(yuǎn)親關(guān)系r*,和非血緣的親情關(guān)系r"等等,每一個(gè)關(guān)系要 給出具體人員的關(guān)系元組 例如:母子關(guān)系(王愛蓮,張選) 兄弟關(guān)系(張選,張立) 妯娌關(guān)系 (王愛蓮,李美英)
北京大學(xué)信息學(xué)院 版權(quán)所有,轉(zhuǎn)載或翻印必究 Page 16
結(jié)點(diǎn)的類型
基本數(shù)據(jù)類型
整數(shù)類型(integer):該類型規(guī)定了所能表示的整數(shù)范圍, 在計(jì)算機(jī)中一般使用1個(gè)字節(jié)到4個(gè)字節(jié)來存儲(chǔ)整數(shù) 實(shí)數(shù)類型(real):計(jì)算機(jī)的浮點(diǎn)數(shù)據(jù)類型所能表示的數(shù)值范 圍和精度是有限的. 機(jī)器一般使用4個(gè)字節(jié)到8個(gè)字節(jié)來存 儲(chǔ)浮點(diǎn)數(shù) 布爾類型(boolean):取值為真(true)和假(false),在 C++語言中一般使用整數(shù)0表示false,用非0表示真
北京大學(xué)信息學(xué)院 版權(quán)所有,轉(zhuǎn)載或翻印必究 Page 17
結(jié)點(diǎn)的類型
基本數(shù)據(jù)類型
字符類型(char):用單個(gè)字節(jié)(8bit,最高位bit為 0)表示ASCII字符集中的字符.
漢字符號(hào)需要使用2個(gè)字節(jié)(每個(gè)字節(jié)的最高位bit為1) 的編碼,單個(gè)字節(jié)對(duì)于漢字是沒有獨(dú)立含義的.
北京大學(xué)信息學(xué)院
版權(quán)所有,轉(zhuǎn)載或翻印必究
Page 18
在C++中把雙字節(jié)表示中文符號(hào)的字節(jié)類型稱 為w_char類型(wide character). 目前國(guó)際上已經(jīng)采用了統(tǒng)一的擴(kuò)展字符集合標(biāo)準(zhǔn) UNICODE,這一標(biāo)準(zhǔn)允許英,日,韓,阿拉伯 語等文字的混合文字處理
北京大學(xué)信息學(xué)院
版權(quán)所有,轉(zhuǎn)載或翻印必究
Page 19
結(jié)點(diǎn)的類型
基本數(shù)據(jù)類型
指針類型(pointer):用于表示機(jī)器內(nèi)存地址,指 針表示指向某一內(nèi)存單元的地址.
由于機(jī)器的指令系統(tǒng)一般采用32 bit或64bit的地址長(zhǎng) 度,所以指針類型也相應(yīng)地用4個(gè)字節(jié)或8個(gè)字節(jié)來表示 一個(gè)指針.
北京大學(xué)信息學(xué)院 版權(quán)所有,轉(zhuǎn)載或翻印必究 Page 20
指針值的存儲(chǔ)和指針值的運(yùn)算方式,在形式上與 正整數(shù)相似. 但指針的運(yùn)算一般僅限于兩個(gè)指針地址的比較, 加減,或?qū)σ粋�(gè)指針增減一個(gè)整數(shù)量等
北京大學(xué)信息學(xué)院
版權(quán)所有,轉(zhuǎn)載或翻印必究
Page 21
結(jié)點(diǎn)的類型
復(fù)合數(shù)據(jù)類型
復(fù)合類型是由基本數(shù)據(jù)類型組合而成的數(shù)據(jù)結(jié)構(gòu)類型.例 如:在程序語言中常用的數(shù)組類型,結(jié)構(gòu)(記錄)類型等皆 屬?gòu)?fù)合數(shù)據(jù)類型 復(fù)合數(shù)據(jù)類型本身,又可以參與定義結(jié)構(gòu)更為復(fù)雜的結(jié)點(diǎn)類 型. 結(jié)點(diǎn)的類型不限于基本數(shù)據(jù)類型,可以根據(jù)應(yīng)用的需要來靈 活定義
北京大學(xué)信息學(xué)院 版權(quán)所有,轉(zhuǎn)載或翻印必究 Page 22
結(jié)構(gòu)的分類
討論邏輯結(jié)構(gòu)(K,R)的分類,一般把討論重點(diǎn)放在 關(guān)系集R上.用R的性質(zhì)來刻劃數(shù)據(jù)結(jié)構(gòu)的特點(diǎn),并對(duì) 數(shù)據(jù)結(jié)構(gòu)進(jìn)行分類
線性結(jié)構(gòu)(linear structure) 樹型結(jié)構(gòu)(tree structure) 圖結(jié)構(gòu)(graph structure)
北京大學(xué)信息學(xué)院 版權(quán)所有,轉(zhuǎn)載或翻印必究 Page 23
線性結(jié)構(gòu)
這種結(jié)構(gòu)在程序設(shè)計(jì)中應(yīng)用最多. 它的關(guān)系r 是一種線性關(guān)系,或稱為"前后關(guān)系",有時(shí) 也稱為"大小關(guān)系".關(guān)系r是有向的,且滿足全序性和 單索性等約束條件
全序性是指,線性結(jié)構(gòu)的全部結(jié)點(diǎn)兩兩皆可以比較前后(關(guān) 系r) 單索性是指,每一個(gè)結(jié)點(diǎn)x都存在唯一的一個(gè)直接后繼結(jié)點(diǎn) y.如果其他結(jié)點(diǎn)z在y之前,則這個(gè)z也一定在x之前,不會(huì) 在x,y之間
