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