面向?qū)ο蟮臄?shù)據(jù)結(jié)構(gòu)

1、面向?qū)ο蟮臄?shù)據(jù)結(jié)構(gòu)面向?qū)ο蟮臄?shù)據(jù)結(jié)構(gòu) 山西省高校計(jì)算機(jī)精品課程及優(yōu)質(zhì)教學(xué)資源山西省高校計(jì)算機(jī)精品課程及優(yōu)質(zhì)教學(xué)資源建設(shè)與共享研討會山西山西 太原太原 20082008年年4 4月月2020日日 問我祖先在何處，山西洪洞大槐樹問我祖先在何處，山西洪洞大槐樹 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 2山西太原（交城）古郊麻會村山西太原（交城）古郊麻會村 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 3內(nèi)容提要內(nèi)容提要n1. 教學(xué)內(nèi)容教學(xué)內(nèi)容n2. 數(shù)據(jù)的定義數(shù)據(jù)的定義n3. 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n4. 教學(xué)案例教學(xué)案例n5. 網(wǎng)絡(luò)教學(xué)資源網(wǎng)絡(luò)教學(xué)資源數(shù)據(jù)結(jié)構(gòu)在

2、計(jì)算機(jī)學(xué)科中的地位數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)學(xué)科中的地位n最重要的主干基礎(chǔ)課程最重要的主干基礎(chǔ)課程n就是就是“最最”，沒有，沒有“之一之一”n承前啟后的重要作用承前啟后的重要作用n程序設(shè)計(jì)能力程序設(shè)計(jì)能力“質(zhì)的飛躍質(zhì)的飛躍”n操作系統(tǒng)、編譯器、數(shù)據(jù)庫系統(tǒng)、操作系統(tǒng)、編譯器、數(shù)據(jù)庫系統(tǒng)、 網(wǎng)絡(luò)、軟件工程網(wǎng)絡(luò)、軟件工程 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 4 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 5 圖 4.1 計(jì)算機(jī)科學(xué)技術(shù)學(xué)科課程體系 專專 業(yè)業(yè) 基基 礎(chǔ)礎(chǔ) 課課 專 業(yè) 選修 課 學(xué)學(xué)院院平平臺臺課課 信息科學(xué)技術(shù)概論 數(shù)學(xué)基礎(chǔ)數(shù)學(xué)基礎(chǔ) 數(shù)學(xué)分析 I/II

3、/III, 高等數(shù)學(xué) I/II 高等代數(shù) I / II , 線性代數(shù) 理論基礎(chǔ)理論基礎(chǔ) 集合論與圖論 代數(shù)結(jié)構(gòu)與組合數(shù)學(xué) 數(shù)理邏輯 概率統(tǒng)計(jì) A 算法設(shè)計(jì)與分析 硬件基礎(chǔ)硬件基礎(chǔ) 數(shù)字邏輯設(shè)計(jì) * 數(shù)字邏輯設(shè)計(jì)實(shí)驗(yàn) 微機(jī)原理 * 微機(jī)實(shí)驗(yàn) 計(jì)算機(jī)組織與體系結(jié)構(gòu) * 計(jì)算機(jī)組織與體系結(jié)構(gòu)實(shí)驗(yàn) 計(jì)算機(jī)理論計(jì)算機(jī)理論 理論計(jì)算機(jī)科學(xué)基礎(chǔ) 初等數(shù)論及其應(yīng)用 隨機(jī)過程引論 軟件工程軟件工程 軟件工程 面向?qū)ο蠹夹g(shù)引論 中間件技術(shù)導(dǎo)論 軟件測試 面向服務(wù)的架構(gòu) 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò) 計(jì)算機(jī)網(wǎng)絡(luò) Web技術(shù)概論 網(wǎng)絡(luò)與 Web 程序設(shè)計(jì) 網(wǎng)絡(luò)協(xié)議分析與設(shè)計(jì) 信息安全引論 計(jì)算機(jī)體系結(jié)構(gòu)計(jì)算機(jī)體系結(jié)構(gòu) 匯編程

4、序設(shè)計(jì) 嵌入式系統(tǒng)概論 數(shù)字信號與多媒體處理器 數(shù)據(jù)管理數(shù)據(jù)管理 數(shù)據(jù)庫概論 數(shù)據(jù)庫原理與技術(shù) 數(shù)據(jù)倉庫與數(shù)據(jù)挖掘 空間與多媒體數(shù)據(jù)庫 Web 數(shù)據(jù)管理 自然語言處理自然語言處理 自然語言處理導(dǎo)論語言統(tǒng)計(jì)分析 現(xiàn)代信息檢索導(dǎo)論 信息檢索導(dǎo)論 信息檢索導(dǎo)論年數(shù)據(jù)庫概論 數(shù)據(jù)倉庫與數(shù)據(jù)挖掘 計(jì)算智能與知識發(fā)現(xiàn)計(jì)算智能與知識發(fā)現(xiàn) 智能信息處理 機(jī)器學(xué)習(xí)概論 智能信息系統(tǒng)實(shí)驗(yàn) 數(shù)字媒體與人機(jī)交互數(shù)字媒體與人機(jī)交互 數(shù)字媒體技術(shù)基礎(chǔ) 數(shù)字視頻處理與分析 計(jì)算機(jī)圖形學(xué) 視覺計(jì)算與處理 數(shù)字化藝術(shù) 人機(jī)交互 物理基礎(chǔ)物理基礎(chǔ) 力學(xué)(A,B) 電磁學(xué)(A,B) 物理 C 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ) 計(jì)算概論 程

5、序設(shè)計(jì)實(shí)習(xí) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 A A 數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí) 電子學(xué)基礎(chǔ)電子學(xué)基礎(chǔ) 微電子與電路基礎(chǔ) 基礎(chǔ)電路實(shí)驗(yàn) 程序設(shè)計(jì)程序設(shè)計(jì) 問題求解與程序設(shè)計(jì) Linux 程序設(shè)計(jì) Windows 程序設(shè)計(jì) Java 程序設(shè)計(jì) 信息檢索導(dǎo)論 信息檢索導(dǎo)論年數(shù)據(jù)庫概論 數(shù)據(jù)倉庫與數(shù)據(jù)挖掘 智能基礎(chǔ)智能基礎(chǔ) 腦與認(rèn)知科學(xué) 信息論基礎(chǔ) 人工智能基礎(chǔ) 數(shù)值計(jì)算方法 信號與系統(tǒng) 軟件基礎(chǔ)軟件基礎(chǔ) 編譯技術(shù) 操作系統(tǒng) 編譯實(shí)習(xí) 操作系統(tǒng)實(shí)習(xí) 程序設(shè)計(jì)語言原理 科技交流與寫作 先進(jìn)技術(shù)專題 計(jì)算機(jī)科學(xué)技術(shù)導(dǎo)論 智能科學(xué)技術(shù)導(dǎo)論 編譯技術(shù) 編譯實(shí)習(xí) 操作系統(tǒng) 操作系統(tǒng)實(shí)習(xí) 計(jì)算機(jī)網(wǎng)絡(luò)概論

6、計(jì)算機(jī)網(wǎng)絡(luò)實(shí)習(xí) 數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí) 智能感知智能感知 模式識別導(dǎo)論 生物信息處理 數(shù)字信號處理 語音信號處理 數(shù)字圖像處理 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 6數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)概率統(tǒng)計(jì)概率統(tǒng)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)學(xué)分析高等數(shù)學(xué)數(shù)學(xué)分析高等數(shù)學(xué)集合論與圖論集合論與圖論算法分析與設(shè)計(jì)算法分析與設(shè)計(jì)程序設(shè)計(jì)實(shí)習(xí)程序設(shè)計(jì)實(shí)習(xí)高等代數(shù)線性代數(shù)高等代數(shù)線性代數(shù)計(jì)算概論計(jì)算概論程序設(shè)計(jì)語言原理程序設(shè)計(jì)語言原理數(shù)據(jù)庫概論數(shù)據(jù)庫概論編譯原理編譯原理操作系統(tǒng)操作系統(tǒng)軟件工程軟件工程計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò) 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 71. 數(shù)

7、據(jù)結(jié)構(gòu)課程的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容n理論理論n算法的數(shù)學(xué)基礎(chǔ)算法的數(shù)學(xué)基礎(chǔ)n算法的時間和空間度量算法的時間和空間度量n抽象抽象n排序、檢索等重要問題類的有效算法排序、檢索等重要問題類的有效算法n重要數(shù)據(jù)結(jié)構(gòu)技術(shù)重要數(shù)據(jù)結(jié)構(gòu)技術(shù)n設(shè)計(jì)設(shè)計(jì)n算法的選擇、實(shí)現(xiàn)和測試算法的選擇、實(shí)現(xiàn)和測試 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 82. 數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)的定義n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)n圖圖 樹樹 二叉樹二叉樹 線性表線性表n數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)n順序方法、鏈接方法順序方法、鏈接方法n索引方法、散列方法索引方法、散列方法 n數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算n增、刪、查

8、、改、排序、檢索增、刪、查、改、排序、檢索存存儲儲數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)邏邏輯輯運(yùn)運(yùn)算算 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 93. 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型ADTn抽象數(shù)據(jù)類型是定義了一組運(yùn)算抽象數(shù)據(jù)類型是定義了一組運(yùn)算的數(shù)學(xué)模型的數(shù)學(xué)模型n把數(shù)據(jù)結(jié)構(gòu)的存儲與實(shí)現(xiàn)細(xì)節(jié)剝把數(shù)據(jù)結(jié)構(gòu)的存儲與實(shí)現(xiàn)細(xì)節(jié)剝離離n在適當(dāng)?shù)某橄髮哟紊峡紤]程序的在適當(dāng)?shù)某橄髮哟紊峡紤]程序的結(jié)構(gòu)和算法結(jié)構(gòu)和算法n封裝和信息隱蔽封裝和信息隱蔽 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 10棧的抽象數(shù)據(jù)類型棧的抽象數(shù)據(jù)類型 template class Stack/ 棧的元素類型為棧的元素類型

9、為ELEMStack(int s); /創(chuàng)建棧的實(shí)例創(chuàng)建棧的實(shí)例Stack(); /該實(shí)例消亡該實(shí)例消亡 void Push(ELEM item);/ item壓入棧頂壓入棧頂 ELEM Pop(); / 返回棧頂內(nèi)容，并從棧頂彈出返回棧頂內(nèi)容，并從棧頂彈出 ELEM GetTop(); / 返回棧頂內(nèi)容，但不彈出返回棧頂內(nèi)容，但不彈出 void MakeEmpty();/ 變?yōu)榭諚Ｗ優(yōu)榭諚?Boolean IsEmpty(); / 返回真，若棧已空返回真，若棧已空 Boolean IsFull(); / 返回真，若棧已滿返回真，若棧已滿; 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 P

10、age 11 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 124. 實(shí)踐環(huán)節(jié)的訓(xùn)練實(shí)踐環(huán)節(jié)的訓(xùn)練n數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法， 3學(xué)分學(xué)分/周周3學(xué)時學(xué)時n每周布置每周布置3-4道書面作業(yè)或小程序?qū)嵙?xí)道書面作業(yè)或小程序?qū)嵙?xí)n數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)，2學(xué)分學(xué)分/周周2學(xué)時學(xué)時 n一個學(xué)期一個學(xué)期6-8道道ACM競賽題競賽題n3-5道綜合上機(jī)實(shí)習(xí)題道綜合上機(jī)實(shí)習(xí)題n上機(jī)實(shí)習(xí)時間，上機(jī)實(shí)習(xí)時間，120小時小時/學(xué)生學(xué)生 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 135. 網(wǎng)絡(luò)教學(xué)資源網(wǎng)絡(luò)教學(xué)資源n建立了高質(zhì)量的建立了高質(zhì)量的 n1500ppt, 46

11、多小時多小時rm（全程錄像）（全程錄像）n還有其他補(bǔ)充錄像還有其他補(bǔ)充錄像n標(biāo)準(zhǔn)標(biāo)準(zhǔn)C+模板編寫的可執(zhí)行的源程序代碼模板編寫的可執(zhí)行的源程序代碼n9209代碼總行數(shù)，非注釋行代碼總行數(shù)，非注釋行7498n習(xí)題和上機(jī)題及其參考答案習(xí)題和上機(jī)題及其參考答案 nBBS討論版討論版(2008年年4月數(shù)據(jù)月數(shù)據(jù))n18萬位會員，帖子總數(shù)萬位會員，帖子總數(shù)8375 篇篇 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 14 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 15網(wǎng)站內(nèi)容網(wǎng)站內(nèi)容n概述、前測概述、前測n知識點(diǎn)詳解知識點(diǎn)詳解n動畫動畫n習(xí)題解、新習(xí)題習(xí)題解、新習(xí)題n電子教

12、案電子教案npdf、視頻、視頻n擴(kuò)展資源擴(kuò)展資源n參考網(wǎng)站、論文、講義參考網(wǎng)站、論文、講義 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 16 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 17新教材新教材n張銘、王騰蛟、趙海燕，張銘、王騰蛟、趙海燕，數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)與算法算法，高等教育出版社，高等教育出版社，2008年年6月月國家級國家級“十一五十一五”規(guī)劃教材規(guī)劃教材n書號書號: ISBN 978-70-4-023961-4n張銘、趙海燕、王騰蛟、宋國杰，張銘、趙海燕、王騰蛟、宋國杰，數(shù)數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)教程據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)教程，高等教育出，高等教育出版社，版

13、社，2009年年6月月國家級國家級“十一五十一五”規(guī)劃教材規(guī)劃教材老教材老教材n許卓群、楊冬青、唐世渭、張銘，許卓群、楊冬青、唐世渭、張銘，數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出，高等教育出版社，版社，2004年年 7月。月。n張銘、趙海燕、王騰蛟，張銘、趙海燕、王騰蛟，數(shù)據(jù)結(jié)數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)指導(dǎo)與習(xí)題解構(gòu)與算法學(xué)習(xí)指導(dǎo)與習(xí)題解析析，高等教育出版社，高等教育出版社，2005年年 9月。月。n書號書號: ISBN 7-04-017829-X 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 18參考教材參考教材n1. Thomas H.Cormen, Charles E.Leise

14、rson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MTI Press. 高等教育出版社影印。高等教育出版社影印。n2. M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 電子工業(yè)出版社電子工業(yè)出版社影印，影印，2003年年1月。月。n3. Sartaj Sahni, Data Structures, Algorithms, and Applications in C+. 機(jī)機(jī)械工業(yè)出版社影印版。械工業(yè)出版社影印版。 n4. William

15、Ford ， Data Structure with C+，清華大學(xué)出版社影印版清華大學(xué)出版社影印版 參考教材參考教材n5. 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅc用面向?qū)ο蠓椒ㄅcC+語言描述語言描述)第第2版版,殷人昆主編殷人昆主編, 清華大學(xué)出版社清華大學(xué)出版社,2007年年6月月.n清華大學(xué)信息學(xué)院計(jì)算機(jī)系、軟件學(xué)院教材清華大學(xué)信息學(xué)院計(jì)算機(jī)系、軟件學(xué)院教材n清華考研第一參考書清華考研第一參考書 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 21教學(xué)討論教學(xué)討論1n算法描述語言算法描述語言n自然語言自然語言n類類Pascaln類類Cn類類C+n類類Javan尺有所長、寸有所短尺

16、有所長、寸有所短括號匹配括號匹配n問題：檢查程序文件中的括號是否匹配問題：檢查程序文件中的括號是否匹配n括號包括：括號包括：,(,),.n算法思想算法思想n逐個讀入字符，忽略非括號字符逐個讀入字符，忽略非括號字符n如果是左括號，記下來如果是左括號，記下來n如果是右括號，檢查是否與最近讀入的左括號如果是右括號，檢查是否與最近讀入的左括號匹配；如果不匹配，則匹配失敗匹配；如果不匹配，則匹配失敗n重復(fù)上述過程，如果讀到文件尾部時，沒有未重復(fù)上述過程，如果讀到文件尾部時，沒有未匹配的左括號留下，則匹配成功，否則，匹配匹配的左括號留下，則匹配成功，否則，匹配失敗失敗 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)

17、載或翻印必究 Page 22自然語言描述的算法自然語言描述的算法采用棧保存中間數(shù)據(jù)采用棧保存中間數(shù)據(jù)n(1) 從左至右掃描表達(dá)式從左至右掃描表達(dá)式, 讀取字符讀取字符cn(2) 如果如果c是非括號字符是非括號字符, 繼續(xù)步驟繼續(xù)步驟1n(3) 否則否則, 如果如果c是左括號是左括號, 則入棧則入棧; n(4) 如果如果c是右括號是右括號, 則與棧頂元素比較則與棧頂元素比較n若?？杖魲？?右括號富余右括號富余), 或左右括號匹配不匹配，則結(jié)束或左右括號匹配不匹配，則結(jié)束n否則，符號目前還匹配否則，符號目前還匹配, 則繼續(xù)掃描步驟則繼續(xù)掃描步驟1n(5) 如果遇到掃描符如果遇到掃描符, 則判斷棧是

18、否空則判斷棧是否空n空空, 則說明匹配則說明匹配n否則否則, 說明左括號富余說明左括號富余 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 23張銘張銘編寫編寫 版版權(quán)所有，轉(zhuǎn)載或翻印必究權(quán)所有，轉(zhuǎn)載或翻印必究 Page 244* x*2a+-）c（ 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 25語言描述，語言描述，C+代碼和注釋代碼和注釋n1. 語言描述和注釋足夠表達(dá)思想；語言描述和注釋足夠表達(dá)思想；n2. 代碼段可以培養(yǎng)學(xué)生嚴(yán)謹(jǐn)?shù)乃惴ùa段可以培養(yǎng)學(xué)生嚴(yán)謹(jǐn)?shù)乃惴ū硎瞿芰?；表述能力；n算法分析教材的太抽象算法分析教材的太抽象n3. C+n非常適宜于表達(dá)抽象數(shù)據(jù)類

19、型非常適宜于表達(dá)抽象數(shù)據(jù)類型nC+, Java是主流的編程語言是主流的編程語言n簡化了輸入輸出簡化了輸入輸出 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 26計(jì)算機(jī)過時技能計(jì)算機(jī)過時技能TOP10 n1.Cobol 、2. Nonrelational DBMS（非關(guān)系數(shù)據(jù)庫管理系統(tǒng)）（非關(guān)系數(shù)據(jù)庫管理系統(tǒng)） n3. Non-IP networks（非（非IP網(wǎng)絡(luò)）、網(wǎng)絡(luò)）、4. CC:Mail n5. ColdFusion n6. C 語言設(shè)計(jì)語言設(shè)計(jì) n7. PowerBuilder、8. CNE（NetWare認(rèn)證工程師）認(rèn)證工程師） n9. PC網(wǎng)絡(luò)管理員、網(wǎng)絡(luò)管理員、1

20、0. OS/2 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 27抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n實(shí)質(zhì)為實(shí)質(zhì)為“邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) + 運(yùn)算運(yùn)算/操作操作”n隱蔽了存儲實(shí)現(xiàn)細(xì)節(jié)隱蔽了存儲實(shí)現(xiàn)細(xì)節(jié)n上層算法以一致的形式調(diào)用底層數(shù)據(jù)結(jié)構(gòu)上層算法以一致的形式調(diào)用底層數(shù)據(jù)結(jié)構(gòu)n例如在例如在STL C+中中nStack.push(x)n順序棧，鏈?zhǔn)綏ｍ樞驐?，鏈?zhǔn)綏上層調(diào)用語句不需要改變上層調(diào)用語句不需要改變 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 28純純C語言的棧抽象數(shù)據(jù)類型？語言的棧抽象數(shù)據(jù)類型？nInitStack(S) nClearStack

21、(S) nIsEmpty(S) nIsFull(S) nPush(S,x) nPop(S,x) nGetTop(S,x) 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 29C順序棧的進(jìn)棧操作順序棧的進(jìn)棧操作ntypedef struct StackElementType elemStack_Size; /*用來存放棧中元素的一維數(shù)組用來存放棧中元素的一維數(shù)組*/ int top; /*用來存放棧頂元素的下標(biāo)用來存放棧頂元素的下標(biāo)*/ SeqStack;nint Push(SeqStack * S, StackElementType x) if (S-top= Stack_Size

22、) return(FALSE); /*棧已滿棧已滿*/ S-top+; S-elemS-top=x; return(TRUE); 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 30C順序棧的出棧操作順序棧的出棧操作int Pop(SeqStack * S, StackElementType *x) if(S-top=-1) /*棧為空棧為空*/ return(FALSE); else *x= S-elemS-top; S-top-; /* 修改棧頂指針修改棧頂指針 */ return(TRUE); 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 31C鏈棧定義鏈棧定義

23、typedef struct node StackElementType data; struct node *next; LinkStackNode; typedef LinkStackNode *LinkStack; 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 32C鏈棧的進(jìn)棧操作鏈棧的進(jìn)棧操作int Push(LinkStack top, StackElementType x) /* 將數(shù)據(jù)元素將數(shù)據(jù)元素x壓入棧壓入棧top中中 */ LinkStackNode * temp; temp=(LinkStackNode * )malloc(sizeof(LinkStackN

24、ode); if (temp=NULL) return(FALSE); /* 申請空間失敗申請空間失敗 */ temp-data=x; temp-next=top-next; top-next=temp; /* 修改當(dāng)前棧頂指針修改當(dāng)前棧頂指針 */ return(TRUE); 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 33C鏈棧的出棧操作鏈棧的出棧操作int Pop(LinkStack top, StackElementType *x) /* 將棧將棧top的棧頂元素彈出，放到的棧頂元素彈出，放到x所指的存儲空間所指的存儲空間中中 */ LinkStackNode * te

25、mp; temp=top-next; if(temp=NULL) /*棧為空棧為空*/ return(FALSE); top-next=temp-next; *x=temp-data; free(temp); /* 釋放存儲空間釋放存儲空間 */ return(TRUE); 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 34順序棧：順序棧：C版本括號匹配算法版本括號匹配算法void BracketMatch(char *str) SeqStack S; int i; char ch; InitStack(&S); for(i=0; stri!=0; i+) switch(

26、stri) case (: case : case : Push(&S,stri); break; case ): case : case : if (IsEmpty(&S) printf(n右括號多余右括號多余!); return; else GetTop (&S,&ch); if (Match(ch,stri) Pop(&S,&ch); else printf(n括號不匹配括號不匹配!); return; /*else*/ /*switch*/ /*for*/ if (IsEmpty(&S) printf(n括號匹配括號匹配!); e

27、lse printf(n左括號多余左括號多余 ); 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 35鏈棧：鏈棧：C版本括號匹配算法版本括號匹配算法void BracketMatch(char *str) LinkStack S; int i; char ch; InitStack(/*&*/S); for(i=0; stri!=0; i+) switch(stri) case (: case : case : Push(/*&*/S, stri); break; case ): case : case : if (IsEmpty(S) printf(n右括號多余

28、右括號多余!); return; else GetTop (/*&*/S,&ch); if (Match(ch,stri) Pop(/*&*/S,&ch); else printf(“n括號不匹配括號不匹配!); return; /*else*/ /*switch*/ /*for*/ if (IsEmpty(/*&*/S) printf(n括號匹配括號匹配!); else printf(n左括號多余左括號多余 ); 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 36C數(shù)據(jù)類型的問題數(shù)據(jù)類型的問題n1. 在同一個程序中，如果棧的在同一個程序中

29、，如果棧的StackElementType 不同不同n需要定義不同的棧需要定義不同的棧n2. 從順序棧改為鏈?zhǔn)綏捻樞驐８臑殒準(zhǔn)綏上層調(diào)用語句一定要改變上層調(diào)用語句一定要改變n程序中所有的變量定義都需要修改程序中所有的變量定義都需要修改n函數(shù)參數(shù)傳遞也要改變函數(shù)參數(shù)傳遞也要改變n3. 最嚴(yán)重的問題最嚴(yán)重的問題n勉強(qiáng)用結(jié)構(gòu)化的勉強(qiáng)用結(jié)構(gòu)化的C來描述來描述ADT, 造成學(xué)生的困惑造成學(xué)生的困惑 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 37用用C+講授數(shù)據(jù)類型的好處講授數(shù)據(jù)類型的好處n1. 在同一個程序中，如果棧的在同一個程序中，如果棧的StackElementType 不同不

30、同n不需要定義不同的棧不需要定義不同的棧, template n程序中所有的變量定義都不需要修改程序中所有的變量定義都不需要修改n2. 從順序棧改為鏈?zhǔn)綏捻樞驐８臑殒準(zhǔn)綏只需要改變對頭文件的引用只需要改變對頭文件的引用, 程序代碼完全不變程序代碼完全不變n真正的軟件復(fù)用真正的軟件復(fù)用n真正的抽象數(shù)據(jù)類型真正的抽象數(shù)據(jù)類型ADTn3. 最大的好處最大的好處n給學(xué)生更好的抽象能力訓(xùn)練給學(xué)生更好的抽象能力訓(xùn)練, 并且與主流技術(shù)一致并且與主流技術(shù)一致 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 38C+C+棧的抽象數(shù)據(jù)類型棧的抽象數(shù)據(jù)類型 template class Stack/

31、 棧的元素類型為棧的元素類型為ELEMStack(int s); /創(chuàng)建棧的實(shí)例創(chuàng)建棧的實(shí)例Stack(); /該實(shí)例消亡該實(shí)例消亡 void Push(ELEM item);/ item壓入棧頂壓入棧頂 ELEM Pop(); / 返回棧頂內(nèi)容，并從棧頂彈出返回棧頂內(nèi)容，并從棧頂彈出 ELEM GetTop(); / 返回棧頂內(nèi)容，但不彈出返回棧頂內(nèi)容，但不彈出 void MakeEmpty();/ 變?yōu)榭諚Ｗ優(yōu)榭諚?Boolean IsEmpty(); / 返回真，若棧已空返回真，若棧已空 Boolean IsFull(); / 返回真，若棧已滿返回真，若棧已滿; 版權(quán)所有，轉(zhuǎn)載或翻印必究

32、版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 39C+C+順序棧順序棧 template class Stack private:ELEM *ElmList; / 存放數(shù)據(jù)元素的指針變量存放數(shù)據(jù)元素的指針變量 int top; / 棧頂在的位置，即下標(biāo)值棧頂在的位置，即下標(biāo)值 / 當(dāng)新元素壓入或棧內(nèi)容彈出，當(dāng)新元素壓入或棧內(nèi)容彈出，top值隨之增減值隨之增減 int maxsize; / 棧的最大長度棧的最大長度 /構(gòu)建棧的實(shí)例，向量空間長度為構(gòu)建棧的實(shí)例，向量空間長度為size public: Stack(int size); ; 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 40壓入棧

33、頂壓入棧頂 template void Stack:Push(ELEM item)/判非棧滿，否則棧溢出，退出運(yùn)行判非棧滿，否則棧溢出，退出運(yùn)行assert(!IsFull(); top+; /棧頂棧頂ElmListtop=item; 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 41從棧頂彈出從棧頂彈出 template ELEM Stack:Pop()/判棧非空，否則斷言棧空異常，判棧非空，否則斷言棧空異常， /退出運(yùn)行退出運(yùn)行assert(!IsEmpty(); return ElmListtop-; 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 42順序棧：

34、壓入棧頂順序棧：壓入棧頂 template void Stack:Push(ELEM item)assert(!IsFull(); / 棧滿，則退出棧滿，則退出top+; / 棧頂指針移位棧頂指針移位ElmListtop=item; 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 43順序棧：從棧頂彈出順序棧：從棧頂彈出 template ELEM Stack:Pop()assert(!IsEmpty(); / 棧空，則退出?？眨瑒t退出return ElmListtop-; 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 44C+C+鏈?zhǔn)綏ｆ準(zhǔn)綏?template st

35、ruct ListNode ELEM data; ListNode * link;template class Stack private: ListNode *top; int size; / Count number of elementspublic: Stack(int sz = LIST_SIZE) top = NULL; size = 0; 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 45鏈?zhǔn)綏＃簤喝霔ｍ旀準(zhǔn)綏＃簤喝霔ｍ?void Push(const ELEM & item) ListNode *temp;temp = new ListNode; / 若無

36、存儲空間則異常，程序退出運(yùn)行若無存儲空間則異常，程序退出運(yùn)行assert(!temp=NULL); size+;temp-data = item;temp-link = top; / 老棧頂指針老棧頂指針top = temp;/ 新棧頂指針新棧頂指針 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 46鏈?zhǔn)綏＃簭臈ｍ攺棾鲦準(zhǔn)綏＃簭臈ｍ攺棾?ELEM Pop() /判棧非空，否則斷言?？债惓?，程序退出判棧非空，否則斷言?？债惓?，程序退出assert(!IsEmpty(); ELEM result = top-data; /暫存棧頂內(nèi)容暫存棧頂內(nèi)容ListNode * temptr;t

37、emptr = top; /老棧頂指針老棧頂指針top = top-link ; /新棧頂指針新棧頂指針 size-;delete temptr; /釋放空間釋放空間return result; /返回的是彈出內(nèi)容返回的是彈出內(nèi)容 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 47C+版本括號匹配算法版本括號匹配算法void BracketMatch(char *str) Stack S; int i; char ch; / 自動初始化自動初始化 for(i=0; stri!=0; i+) switch(stri) case (: case : case : S.Push(str

38、i); break; case ): case : case : if (S.IsEmpty( ) cout右括號多余右括號多余!; return; else ch = S.GetTop( ); if (Match(ch,stri) ch = S.Pop( ); else cout 括號不匹配括號不匹配!; return; /*else*/ /*switch*/ /*for*/ if (S.IsEmpty( ) cout括號匹配括號匹配!; else cout左括號多余左括號多余 ; 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 48教學(xué)討論教學(xué)討論2n算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系？算法

39、和數(shù)據(jù)結(jié)構(gòu)的關(guān)系？n基本數(shù)據(jù)結(jié)構(gòu)和算法的重現(xiàn)？基本數(shù)據(jù)結(jié)構(gòu)和算法的重現(xiàn)？n怎樣訓(xùn)練綜合能力？怎樣訓(xùn)練綜合能力？n實(shí)踐教學(xué)？實(shí)踐教學(xué)？n怎樣怎樣減少減少抄襲？抄襲？天網(wǎng)公司總裁天網(wǎng)公司總裁 雷凱雷凱北大北大94級級n張老師在整個課程的教學(xué)中，通過其張老師在整個課程的教學(xué)中，通過其精心選擇精心選擇的課程教材，認(rèn)真精辟的課堂講解，引人入勝的課程教材，認(rèn)真精辟的課堂講解，引人入勝的案例分析，巧妙的教學(xué)思路設(shè)計(jì)，豐富系統(tǒng)的案例分析，巧妙的教學(xué)思路設(shè)計(jì)，豐富系統(tǒng)的訓(xùn)練方法，和細(xì)致入微的與學(xué)生互動教學(xué)的訓(xùn)練方法，和細(xì)致入微的與學(xué)生互動教學(xué)，真正的體現(xiàn)了一位導(dǎo)師給每一位渴望知識的學(xué)真正的體現(xiàn)了一位導(dǎo)師給每一位

40、渴望知識的學(xué)生生“授之以漁授之以漁”的教學(xué)精神，將的教學(xué)精神，將數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)與算法算法的知識和精髓由一本本經(jīng)典的理論著作，的知識和精髓由一本本經(jīng)典的理論著作，轉(zhuǎn)化成學(xué)生所需要的，活生生有實(shí)踐意義的知轉(zhuǎn)化成學(xué)生所需要的，活生生有實(shí)踐意義的知識，深深地印在了每一位學(xué)生的心里。識，深深地印在了每一位學(xué)生的心里。 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 49徐穎徐穎北大北大94本，本，00碩碩2003級美國斯坦福大學(xué)計(jì)算機(jī)系博士級美國斯坦福大學(xué)計(jì)算機(jī)系博士WebVLDB、CIKM、PODSn我進(jìn)入我進(jìn)入斯坦福斯坦福的第一個學(xué)期就選的第一個學(xué)期就選擇了直接考試，而且驚喜地發(fā)現(xiàn)，

41、擇了直接考試，而且驚喜地發(fā)現(xiàn)，算法與數(shù)據(jù)結(jié)構(gòu)考試的知識點(diǎn)和算法與數(shù)據(jù)結(jié)構(gòu)考試的知識點(diǎn)和張銘老師在北大開設(shè)課程的講授張銘老師在北大開設(shè)課程的講授內(nèi)容十分一致內(nèi)容十分一致，所以張銘老師的，所以張銘老師的課程講義和錄像就成為我的主要課程講義和錄像就成為我的主要復(fù)習(xí)資料復(fù)習(xí)資料 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 50陳華陳華97本，本，01碩碩酷訊公司總裁酷訊公司總裁n張老師給我們年級帶了張老師給我們年級帶了計(jì)算引論計(jì)算引論和和數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)。這兩門課程共同的特就是創(chuàng)造性思維的刺激和超強(qiáng)。這兩門課程共同的特就是創(chuàng)造性思維的刺激和超強(qiáng)度的大項(xiàng)目實(shí)習(xí)度的大項(xiàng)目實(shí)習(xí)n張老師在張老

42、師在計(jì)算引論計(jì)算引論給我們打下了雄厚的給我們打下了雄厚的Pascal結(jié)結(jié)構(gòu)化程序設(shè)計(jì)功底。構(gòu)化程序設(shè)計(jì)功底。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課程采用了張老師課程采用了張老師翻譯的面向?qū)ο蠓g的面向?qū)ο驝+版版數(shù)據(jù)結(jié)構(gòu)與算法分析數(shù)據(jù)結(jié)構(gòu)與算法分析新教新教材材n由于是主講老師親自翻譯的教材，她對教材有著深刻由于是主講老師親自翻譯的教材，她對教材有著深刻的理解，上課時能夠?qū)栴}講述得非常清晰。我們在的理解，上課時能夠?qū)栴}講述得非常清晰。我們在張老師帶領(lǐng)下，張老師帶領(lǐng)下，幾周內(nèi)從幾周內(nèi)從Pascal轉(zhuǎn)換到轉(zhuǎn)換到C+，對我們，對我們以后很快接受新理論、新技術(shù)，是一種很好的鍛煉以后很快接受新理論、新技術(shù)，是一種很好的鍛

43、煉 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 51梅俏竹梅俏竹北大北大99級級UIUC計(jì)算機(jī)系博士生計(jì)算機(jī)系博士生SIGKDD、SIGIR、WWW，ACM TKDDn記得記得當(dāng)年數(shù)據(jù)結(jié)構(gòu)的大實(shí)習(xí)作業(yè)是設(shè)計(jì)并實(shí)現(xiàn)一個簡當(dāng)年數(shù)據(jù)結(jié)構(gòu)的大實(shí)習(xí)作業(yè)是設(shè)計(jì)并實(shí)現(xiàn)一個簡單的搜索引擎單的搜索引擎。n而當(dāng)時只不過是而當(dāng)時只不過是2000年，現(xiàn)在搜索引擎的巨頭年，現(xiàn)在搜索引擎的巨頭Google遠(yuǎn)未上市，百度則剛剛成立，微軟和雅虎甚至遠(yuǎn)未上市，百度則剛剛成立，微軟和雅虎甚至還沒開始研發(fā)自己的搜索引擎。還沒開始研發(fā)自己的搜索引擎。n北大的本科生課程實(shí)習(xí)就能有這樣的前瞻性的問題絕北大的本科生課程實(shí)習(xí)

44、就能有這樣的前瞻性的問題絕對是值得稱道的。對是值得稱道的。n 大家都不約而同地提到數(shù)據(jù)結(jié)構(gòu)這門課程對自己的影大家都不約而同地提到數(shù)據(jù)結(jié)構(gòu)這門課程對自己的影響。歸結(jié)起來，大家都認(rèn)為張銘老師的響。歸結(jié)起來，大家都認(rèn)為張銘老師的“數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)與算法課程算法課程”內(nèi)容細(xì)致實(shí)用，講授深入淺出，課程實(shí)習(xí)內(nèi)容細(xì)致實(shí)用，講授深入淺出，課程實(shí)習(xí)精巧而具前瞻性，對培養(yǎng)學(xué)生分析和解決問題，創(chuàng)造精巧而具前瞻性，對培養(yǎng)學(xué)生分析和解決問題，創(chuàng)造性思考，和團(tuán)隊(duì)合作的能力都有很好的作用性思考，和團(tuán)隊(duì)合作的能力都有很好的作用 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 52銀平銀平00本，本，04碩，助教

45、碩，助教酷訊公司酷訊公司n張銘老師課堂上引導(dǎo)以及深刻講解讓我張銘老師課堂上引導(dǎo)以及深刻講解讓我對這門課程產(chǎn)生了濃厚興趣，并極大的對這門課程產(chǎn)生了濃厚興趣，并極大的訓(xùn)練了我的思維能力。數(shù)據(jù)結(jié)構(gòu)的幾個訓(xùn)練了我的思維能力。數(shù)據(jù)結(jié)構(gòu)的幾個大的實(shí)習(xí)讓我打下了堅(jiān)實(shí)的算法與工程大的實(shí)習(xí)讓我打下了堅(jiān)實(shí)的算法與工程基礎(chǔ)?；A(chǔ)。n 這門課程幾乎年年都有所變動這門課程幾乎年年都有所變動，如降低，如降低作業(yè)的數(shù)量但提高作業(yè)的質(zhì)量，將實(shí)習(xí)作業(yè)的數(shù)量但提高作業(yè)的質(zhì)量，將實(shí)習(xí)課程分離，采用課程分離，采用ACM的題目等等。的題目等等。 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 53趙翔宇趙翔宇01本，本，0

46、5碩，助教碩，助教n最重要的是，我們要看同學(xué)們做作業(yè)的時候是否是獨(dú)最重要的是，我們要看同學(xué)們做作業(yè)的時候是否是獨(dú)立完成，立完成，張老師的誠實(shí)代碼張老師的誠實(shí)代碼宣言相信每一個選過這門宣言相信每一個選過這門課的同學(xué)都會牢記在心中，先成人，再成才，這也是課的同學(xué)都會牢記在心中，先成人，再成才，這也是張老師在上這門課時教給我們很重要的一點(diǎn)。張老師在上這門課時教給我們很重要的一點(diǎn)。n無論平時的研究、項(xiàng)目，還是求職，甚至以后的工作無論平時的研究、項(xiàng)目，還是求職，甚至以后的工作生涯，我們都會體會到數(shù)據(jù)結(jié)構(gòu)和算法的重要性。生涯，我們都會體會到數(shù)據(jù)結(jié)構(gòu)和算法的重要性。n在今年的求職過程中，無論碰到怎樣復(fù)雜的數(shù)

47、據(jù)結(jié)構(gòu)在今年的求職過程中，無論碰到怎樣復(fù)雜的數(shù)據(jù)結(jié)構(gòu)題，我都能輕松應(yīng)付，因?yàn)樵诮忸}前，我對自己有信題，我都能輕松應(yīng)付，因?yàn)樵诮忸}前，我對自己有信心，我有張老師為我打下的深厚基礎(chǔ)。心，我有張老師為我打下的深厚基礎(chǔ)。 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 54Honor Code（誠實(shí)代碼保證）n/ 我真誠地保證：我真誠地保證： n/ 我自己獨(dú)立地完成了整個程序從分析、設(shè)計(jì)到編碼的所有工作。我自己獨(dú)立地完成了整個程序從分析、設(shè)計(jì)到編碼的所有工作。n/ 如果在上述過程中，我遇到了什么困難而求教于人，如果在上述過程中，我遇到了什么困難而求教于人，n/ 那么，我將在程序?qū)嵙?xí)報告中詳

48、細(xì)地列舉我所遇到的問題，那么，我將在程序?qū)嵙?xí)報告中詳細(xì)地列舉我所遇到的問題，n/ 以及別人給我的提示。以及別人給我的提示。n/ 在此，我感謝在此，我感謝 XXX, , XXX對我的啟發(fā)和幫助。對我的啟發(fā)和幫助。n/ 我的程序里中凡是引用到其他程序或文檔之處，我的程序里中凡是引用到其他程序或文檔之處，n/ 例如教材、課堂筆記、網(wǎng)上的源代碼以及其他參考書上的代碼段例如教材、課堂筆記、網(wǎng)上的源代碼以及其他參考書上的代碼段,n/ 我都已經(jīng)在程序的注釋里很清楚地注明了引用的出處。我都已經(jīng)在程序的注釋里很清楚地注明了引用的出處。n/ 我從未沒抄襲過別人的程序，也沒有盜用別人的程序，我從未沒抄襲過別人的程序

49、，也沒有盜用別人的程序，n/ 不管是修改式的抄襲還是原封不動的抄襲。不管是修改式的抄襲還是原封不動的抄襲。 n/ 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 55李逸男李逸男北大北大03級級香港科技大學(xué)博士香港科技大學(xué)博士本科兩篇本科兩篇SIGMOD07 Demo論文論文n起著承前啟后的重要作用起著承前啟后的重要作用。n在張老師的悉心指導(dǎo)和嚴(yán)格要求下，在張老師的悉心指導(dǎo)和嚴(yán)格要求下，經(jīng)過數(shù)據(jù)結(jié)構(gòu)課程的理論和經(jīng)過數(shù)據(jù)結(jié)構(gòu)課程的理論和實(shí)踐的磨練，同學(xué)們從剛剛會寫簡單的程序，迅速實(shí)踐的磨練，同學(xué)們從剛剛會寫簡單的程序，迅速“升級升級”為能為能夠完成各種復(fù)雜系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)的計(jì)算機(jī)高手夠

50、完成各種復(fù)雜系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)的計(jì)算機(jī)高手。我們在隨后的各。我們在隨后的各種課程中完成的迷你操作系統(tǒng)、編譯器、數(shù)據(jù)庫系統(tǒng)等課程設(shè)計(jì)種課程中完成的迷你操作系統(tǒng)、編譯器、數(shù)據(jù)庫系統(tǒng)等課程設(shè)計(jì)，很大深度依賴于在數(shù)據(jù)結(jié)構(gòu)這門課程所打下的堅(jiān)實(shí)的理論基礎(chǔ)，很大深度依賴于在數(shù)據(jù)結(jié)構(gòu)這門課程所打下的堅(jiān)實(shí)的理論基礎(chǔ)和動手能力。和動手能力。n國際最前沿的研究成果其實(shí)往往就是對相對基本的數(shù)據(jù)結(jié)構(gòu)和算國際最前沿的研究成果其實(shí)往往就是對相對基本的數(shù)據(jù)結(jié)構(gòu)和算法在某些特殊應(yīng)用背景進(jìn)行的一些有針對性的優(yōu)化和擴(kuò)展，而這法在某些特殊應(yīng)用背景進(jìn)行的一些有針對性的優(yōu)化和擴(kuò)展，而這些相對基本的數(shù)據(jù)結(jié)構(gòu)在張老師的課程中絕大多都有涉及，還有

51、些相對基本的數(shù)據(jù)結(jié)構(gòu)在張老師的課程中絕大多都有涉及，還有一些是張老師在課堂上加入的一些擴(kuò)展內(nèi)容。一些是張老師在課堂上加入的一些擴(kuò)展內(nèi)容。n細(xì)細(xì)回想起來，很多現(xiàn)在已經(jīng)非常熟悉的知識還都是在張老師的細(xì)細(xì)回想起來，很多現(xiàn)在已經(jīng)非常熟悉的知識還都是在張老師的數(shù)據(jù)結(jié)構(gòu)課上打下的基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課上打下的基礎(chǔ)。 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 56李浩源李浩源北大北大04級級2005年年ACM/ICPC 全球第十一名全球第十一名2006年年ACM/ICPC 全球第十三名全球第十三名即將赴美國即將赴美國Cornell攻讀計(jì)算機(jī)博士學(xué)位攻讀計(jì)算機(jī)博士學(xué)位n數(shù)據(jù)結(jié)構(gòu)還有一個很大的特色就

52、是它不單單講數(shù)據(jù)結(jié)構(gòu)還有一個很大的特色就是它不單單講授理論內(nèi)容，授理論內(nèi)容，張老師還配套開設(shè)了數(shù)據(jù)結(jié)構(gòu)實(shí)張老師還配套開設(shè)了數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)課程，以鍛煉提高學(xué)生的實(shí)踐能力習(xí)課程，以鍛煉提高學(xué)生的實(shí)踐能力。n在實(shí)習(xí)課上，同學(xué)把理論課上的很多算法得以在實(shí)習(xí)課上，同學(xué)把理論課上的很多算法得以實(shí)現(xiàn)，上課更加積極的討論。實(shí)現(xiàn)，上課更加積極的討論。n大家在歡樂的氣氛下達(dá)到了理論與實(shí)踐水平共大家在歡樂的氣氛下達(dá)到了理論與實(shí)踐水平共同提高目的，日后同學(xué)之間談起來，都很懷念。同提高目的，日后同學(xué)之間談起來，都很懷念。 版權(quán)所有，轉(zhuǎn)載或翻印必究版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 57柳明海柳明海北大北大04級級n這門課程的教材非常好，教材的深度和廣度都這門課程的教材非常好，教材的深度和廣度都很不錯，由于是主講老師自己編寫的教材，對很不錯，由于是主講老師自己編寫的教材，對教材有著深刻的理解，上課時能夠?qū)栴}講述教材有著深刻的理解，上課時能夠?qū)栴}講述得非常清晰，還能夠聯(lián)系實(shí)際應(yīng)用，而不是簡得非常清晰，還能夠聯(lián)系實(shí)際應(yīng)用，而不是簡單的學(xué)習(xí)。單的學(xué)習(xí)。 n課堂的氛圍非常的活潑，老師同