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