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