數(shù)據(jù)結(jié)構(gòu)課件

1、數(shù)據(jù)結(jié)構(gòu)Data Structures課程簡介與教學(xué)要求清華大學(xué)計算機(jī)系 殷人昆 王宏 2012年春季學(xué)期.數(shù)據(jù)結(jié)構(gòu)Data Structures課程簡介與教學(xué)要求學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的背景系統(tǒng)程序與應(yīng)用程序的規(guī)模和復(fù)雜性激增數(shù)據(jù)的表示和組織直接關(guān)系到問題求解的效率。必須分析待處理對象的特征及各對象間存在的關(guān)系。必須深入研究 數(shù)據(jù)在計算機(jī)中存儲、組織、傳遞和轉(zhuǎn)換的過程及方法。一門重要的計算機(jī)專業(yè)（能力考查）課程 全國研考CN-29，OS-35，CP-41，DS-45.學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的背景系統(tǒng)程序與應(yīng)用程序的規(guī)模和復(fù)雜性激增.數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展 形成階段： 60年代初期，“數(shù)據(jù)結(jié)構(gòu)”有關(guān)的內(nèi)容散見于

2、操作系統(tǒng)、編譯原理和表處理語言等課程。 1968年，“數(shù)據(jù)結(jié)構(gòu)”作為一門獨立課程被列入美國一些大學(xué)計算機(jī)科學(xué)系的教學(xué)計劃由唐歐克努特（D. E. Knuth，The Art of Computer Programming的作者，圖靈獎得主）開創(chuàng)其最初體系。發(fā)展階段： 數(shù)據(jù)結(jié)構(gòu)的概念不斷擴(kuò)充，包括了集合論、代數(shù)結(jié)構(gòu)、圖論等“離散數(shù)學(xué)結(jié)構(gòu)”的內(nèi)容。 70年代后期，我國高校陸續(xù)開設(shè)該課程。.數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展 形成階段： .數(shù)據(jù)結(jié)構(gòu)課程的地位 介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件三者之間的一門核心課程。關(guān)系機(jī)器組織存儲軟件 硬件對象關(guān)系操作數(shù)學(xué).數(shù)據(jù)結(jié)構(gòu)課程的地位 介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件

3、三者之間數(shù)據(jù)結(jié)構(gòu)是一門側(cè)重研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象及其之間關(guān)系與操作的學(xué)科。不僅是復(fù)雜程序設(shè)計的基礎(chǔ)，也是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。N. Wirth早在20世紀(jì)70年代就曾形象描述Algorithm + Data Structure = Program .數(shù)據(jù)結(jié)構(gòu)是一門側(cè)重研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作程序設(shè)計與問題求解數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)離散數(shù)學(xué) 1離散數(shù)學(xué) 2計算機(jī)科學(xué)基礎(chǔ)計算機(jī)系統(tǒng)原理與匯編算法設(shè)計與分析編譯原理操作系統(tǒng)軟件工程計算機(jī)組織與結(jié)構(gòu)必修課課程設(shè)置與數(shù)據(jù)結(jié)構(gòu)的關(guān)系 .程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)離散數(shù)學(xué)

4、1離散數(shù)學(xué) 2計算機(jī)科學(xué)基礎(chǔ)選修課課程設(shè)置與數(shù)據(jù)結(jié)構(gòu)的關(guān)系 數(shù)據(jù)結(jié)構(gòu)計算機(jī)科學(xué)基礎(chǔ)算法與復(fù)雜性數(shù)據(jù)庫（文件處理）人工智能計算機(jī)網(wǎng)絡(luò)圖形學(xué)多媒體技術(shù) .選修課課程設(shè)置與數(shù)據(jù)結(jié)構(gòu)的關(guān)系 數(shù)據(jù)結(jié)構(gòu)計算機(jī)科學(xué)基礎(chǔ)算法與數(shù)值計算問題求解的一般步驟建立數(shù)學(xué)模型選擇計算機(jī)語言與算法 編寫程序測試（調(diào)試）最終解答。 數(shù)值計算的關(guān)鍵是：如何歸納出數(shù)學(xué)模型（方程）？ 程序設(shè)計人員關(guān)注的是模型的建立與算法的選擇 典型問題： 電路分析與模擬大壩（應(yīng)力與應(yīng)變）結(jié)構(gòu)分析彈道仿真程序 天氣預(yù)報等.數(shù)值計算問題求解的一般步驟建立數(shù)學(xué)模型選擇計算機(jī)語言與算法非數(shù)值計算問題數(shù)據(jù)元素之間的相互關(guān)系有時無法或很難用數(shù)學(xué)方程加以描述。

5、例如，電話號碼查詢問題按順序存儲方式：遍歷表按姓氏索引方式：索引表是否可以利用性能更優(yōu)的查找算法，取決于這張表的組織結(jié)構(gòu)及存儲方式。數(shù)據(jù)元素的結(jié)構(gòu)和存儲方式?jīng)Q定了查找與維護(hù)（算法）的效率。.非數(shù)值計算問題數(shù)據(jù)元素之間的相互關(guān)系有時無法或很難用數(shù)學(xué)方程 2011人機(jī)大戰(zhàn) 電腦完勝. 2011人機(jī)大戰(zhàn) 電腦完勝. 歷史時刻2011年2月142月16日，在美國家喻戶曉的電視智力競賽節(jié)目Jeopardy! (危險或危機(jī)邊緣)中，IBM超級計算機(jī)系統(tǒng) WATSON (沃森)戰(zhàn)勝了該節(jié)目有史以來最優(yōu)秀的兩位人類冠軍Ken Jennings（詹寧斯）和Brad Rutter（拉特），圓滿結(jié)束了這場歷時三天的

6、人機(jī)大戰(zhàn)。第一回合 沃森：5000分，詹寧斯：2000分，拉特：5000分第二回合的比賽，30個問題中，沃森答對24個，詹寧斯和拉特分別答對3個和2個。答對問題價值總計： 沃森：77147 詹寧斯：24000 拉特：21600. 歷史時刻2011年2月14“危機(jī)邊緣”是一款智力問答節(jié)目，國內(nèi)類似的節(jié)目有“開心辭典”等，但是二者之間具有明顯的區(qū)別。“開心辭典”是主持人提出問題，選手給出問題的答案，并且問題相對簡單，涉及較為基礎(chǔ)的科技與人文知識?！拔C(jī)邊緣”則不同，主持人有時給出的是一個問題的答案，而選手需要給出答案所對應(yīng)的問題。比如主持人說： “這是一種冷血的、無足的并且進(jìn)行冬眠的動物”， 選手

7、應(yīng)回答的則是該句對應(yīng)的問題：“什么是蛇?”有多名選手同時參加節(jié)目，問題涉及歷史、時事、科學(xué)、藝術(shù)、體育、地理、流行文化、文學(xué)與語言、文字游戲等等，且每個領(lǐng)域還對應(yīng)問題的難度等級，等級越高獎金越高，倘若答錯，則罰金同樣水漲船高。思考：機(jī)器用何種方式理解問題？.“危機(jī)邊緣”是一款智力問答節(jié)目，國內(nèi)類似的節(jié)目有“開心辭典” 理解超群主持人在向人類選手念出問題的同時，WATSON會收到題目的文本，并在得出答案后以語音的方式讀出（無視覺與聽覺功能）。令人驚嘆的是WATSON能領(lǐng)會題目中不少雙關(guān)語、反話、謎語、諷刺口吻等微妙的表達(dá)方式并給出正確答案。做到這一點顯然比讓機(jī)器戰(zhàn)勝國際象棋大師更具挑戰(zhàn)性，更考驗

8、電腦的“智商” （1997年，IBM的深藍(lán)以 3.5:2.5 戰(zhàn)勝卡斯帕羅夫）。. 理解超群主持人在向人類選手念 題目管窺問題舉例：阿根廷一家美術(shù)館1987年失竊的一件藏品答案：西班牙國王菲利普二世的肖像。該題機(jī)器和人均未答對。. 題目管窺問題舉例：. 低級錯誤盡管WATSON“聰明絕頂”，但偶爾會犯一些低級錯誤。如問題：美國某城市的最大機(jī)場以二戰(zhàn)中的一名英雄命名，而該城市的第二大機(jī)場以二戰(zhàn)中的一場戰(zhàn)役命名。正確答案是芝加哥，而WATSON的回答竟是加拿大城市多倫多。. 低級錯誤盡管WATSON“聰 求解淺析盡管存儲了大量的百科全書和其他信息，但危機(jī)邊緣的問題并不會讓沃森輕易地找到答案，同時尋

9、找答案從來就不是計算機(jī)的強(qiáng)項。搜索引擎無法回答問題，只能給出符合搜索關(guān)鍵詞的成千上萬個似是而非的可能答案。沃森則要通過各種不同的算法對所有的候選答案獲取更多的證據(jù)支持，再根據(jù)證據(jù)的強(qiáng)度對每個候選答案給出其置信度，最后根據(jù)置信度來決定是否向用戶提供置信度最高的唯一答案。這一過程極其復(fù)雜，因此需要動用幾千個處理器的超級計算機(jī)來處理一個問題。. 求解淺析盡管存儲了大量 WATSON 其身IBM超級計算機(jī)系統(tǒng)沃森“以 IBM 創(chuàng)始人 Thomas J. Watson 的姓氏命名。由10 臺 IBM POWER 7 系統(tǒng)組成（每個系統(tǒng)機(jī)架體積有冰箱大小）運(yùn)行 Linux 操作系統(tǒng)包含 15 TB 內(nèi)存和

10、 2880 個處理器內(nèi)核（90臺服務(wù)器，每臺有4個8核中央處理器）運(yùn)行速度高達(dá) 80 Teraflops，即每秒執(zhí)行 80 萬億次浮點運(yùn)算。研制小組為以CMU埃里克.尼貝里教授為首多個研究機(jī)構(gòu)的20多名專家，耗時4年。. WATSON 其身IBM超級計 分析引擎與DeepQA問答系統(tǒng)除強(qiáng)大的硬件資源外，沃森能夠快速回答棘手的問題還得益于采用了 IBM POWER 7 系統(tǒng)作為分析引擎。POWER 7 系統(tǒng)經(jīng)過專門的工作負(fù)載優(yōu)化，能夠同時處理大量信息并且運(yùn)行數(shù)千個分析任務(wù)，以便跟上參賽者的速度。沃森能夠在不到三秒鐘的時間內(nèi)研讀存儲在內(nèi)存中的約 2 億頁自然語言內(nèi)容(相當(dāng)于100萬本書)，并找到問

11、題的確切答案。沃森的DeepQA(深度開放域問答系統(tǒng))采用突破性分析技術(shù)，能夠理解問題的內(nèi)容，搜索海量的信息，分析相應(yīng)的證據(jù)，給出最佳的答案。. 分析引擎與DeepQA問答系統(tǒng)除強(qiáng)大的硬件資源外 專家評價WATSON獲勝標(biāo)志人工智能領(lǐng)域的歷史性時刻但電腦的勝利歸根到底是人類的勝利計算機(jī)技術(shù)的進(jìn)步讓人更加珍視人類的獨特之處研制者：計算機(jī)可以變得越來越聰明，但是要讓它真正具備人類的智能可能永遠(yuǎn)也做不到有價值的設(shè)想：構(gòu)建一個系統(tǒng)，將人類所長和WATSON所長結(jié)合在一起，解決那些單獨一方不能解決的難題。. 專家評價WATSON獲勝標(biāo)志非數(shù)值計算問題求解須考慮的問題主要解決如何設(shè)計出適宜的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)

12、的算法抽象邏輯結(jié)構(gòu)基本運(yùn)算（確定限制）實現(xiàn)存儲結(jié)構(gòu)算法評價不同結(jié)構(gòu)的比較與分析認(rèn)真考慮各種數(shù)據(jù)如何表示、組織和存儲？ 隨著面向?qū)ο蠹夹g(shù)的應(yīng)用，數(shù)據(jù)結(jié)構(gòu)從定義、分類、構(gòu)成，到設(shè)計、實現(xiàn)與分析的模式與方法都有了長足的發(fā)展；現(xiàn)代數(shù)據(jù)結(jié)構(gòu)更加注重和強(qiáng)調(diào)數(shù)據(jù)結(jié)構(gòu)的整體性、通用性、復(fù)用性、安全性。.非數(shù)值計算問題求解須考慮的問題主要解決如何設(shè)計出適宜的數(shù)據(jù)結(jié)教材和教學(xué)參考書主教材 數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ê虲+語言描述）（第2版），殷人昆主編，清華大學(xué)出版社, 請選2009年9月第5（ 5）次印刷，￥ 39。輔助教材數(shù)據(jù)結(jié)構(gòu)習(xí)題解析（用面向?qū)ο蠓椒ㄅcC+語言描述），殷人昆、徐孝凱編著，清華大學(xué)出版社。20

13、08年2月第14次印刷，￥ 26。其它 J. R. Hubbard, Data Structures with C+, 機(jī)械工業(yè)出版社影印, 中譯名數(shù)據(jù)結(jié)構(gòu) 習(xí)題與解答 C+版。￥40.教材和教學(xué)參考書主教材.新版教材與習(xí)題集.新版教材與習(xí)題集.過去使用的老版本教材.過去使用的老版本教材. 其它參考書數(shù)據(jù)結(jié)構(gòu)（C語言版）, 嚴(yán)蔚敏,吳偉民編著, 清華大學(xué)出版社. 2006年5月以后印刷的版本。334頁， ￥30。數(shù)據(jù)結(jié)構(gòu)（C+語言版）, 鄧俊輝編, 清華大學(xué)出版社，2011年11月，419頁，￥39。數(shù)據(jù)結(jié)構(gòu)與算法分析C語言描述（Data Structures and Algorithm An

14、alysis in C）（英文版 第2版）原著Mark Allen Weiss，陳越 改編。人民郵電出版社，2005年12月。501頁，￥ 49。算法I-IV（C+實現(xiàn)）基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、排序和搜索（Algorithms in C+, Parts 1-4，F(xiàn)undamentals, Data Structures, Sorting, Searching） (第三版)，Robert Sedgewick著，張銘澤等譯。中國電力出版社，2005年1月。532頁， ￥55。Data Structures with C+ Using STL（英文影印版），數(shù)據(jù)結(jié)構(gòu) C+語言描述 應(yīng)用標(biāo)準(zhǔn)模板庫（STL）第

15、2版，William Ford, William Topp著, 清華大學(xué)出版社. 2003年1月第1版. 1037頁，￥86。*. 其它參考書數(shù)據(jù)結(jié)構(gòu)（C教學(xué)內(nèi)容和安排緒論3 學(xué)時線性表（順序表與鏈表）5 學(xué)時棧、隊列與遞歸、表達(dá)式計算6 學(xué)時數(shù)組、字符串與廣義表6學(xué)時樹與二叉樹、堆、Huffman樹9學(xué)時搜索結(jié)構(gòu)、搜索樹 6學(xué)時集合與散列（散列表與散列函數(shù)）6學(xué)時圖結(jié)構(gòu)（遍歷、生成樹、最短路徑）8學(xué)時內(nèi)部排序8學(xué)時外部排序與動態(tài)搜索3學(xué)時.教學(xué)內(nèi)容和安排緒論3 學(xué)時線性表（順序表與鏈表）5 學(xué)時棧、教學(xué)目標(biāo)掌握數(shù)據(jù)結(jié)構(gòu)的表示、實現(xiàn)方法和基本操作了解主要（基本）算法與不同數(shù)據(jù)結(jié)構(gòu)之間的內(nèi)在聯(lián)系

16、了解數(shù)據(jù)結(jié)構(gòu)的主要應(yīng)用背景靈活地選用各類（基本）算法及對應(yīng)的數(shù)據(jù)結(jié)構(gòu)，解決實際問題.教學(xué)目標(biāo)掌握數(shù)據(jù)結(jié)構(gòu)的表示、實現(xiàn)方法和基本操作.數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：線性表 / 棧 / 隊列 / 樹 / 散列表 / 優(yōu)先隊列 / 圖 / .算法：枚舉 / 查找 / 排序 / 遍歷 / 散列 / 最小生成樹 / 最短路徑 / .算法設(shè)計策略： / 貪心 / 回溯 / 分治 / 動態(tài)規(guī)劃 / 隨機(jī)化 / .高效的算法，需要高效的數(shù)據(jù)結(jié)構(gòu)加以支持學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，就是要學(xué)會高效地利用計算機(jī)，有效地存儲、組織、傳遞和轉(zhuǎn)換數(shù)據(jù).數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：線性表 / 棧 / 隊列 /教與學(xué)學(xué)好一門課程，需要教師與學(xué)生雙方

17、的共同努力與配合。課堂教學(xué)與課后鉆研理解相結(jié)合，同時還要不斷練習(xí)，鞏固提高、以深入掌握課程的內(nèi)容。本著教學(xué)相長的精神，希望同學(xué)們經(jīng)常對教學(xué)效果作出反饋，提出寶貴意見，以便及時調(diào)整改進(jìn)教學(xué)方法。.教與學(xué)學(xué)好一門課程，需要教師與學(xué)生雙方的共同努力與配合。課堂課程學(xué)習(xí)要求與完成作業(yè)方式遵守課堂紀(jì)律、不遲到，認(rèn)真聽課、及時復(fù)習(xí)； 按時、獨立地完成每次作業(yè)； 完成作業(yè)方式： 大約每4周提交一次作業(yè)(由助教安排)； 作業(yè)分兩部分：第1部分是紙面作業(yè)，要求用筆寫, 并不得復(fù)印和打印。第2部分是上機(jī)作業(yè)，要求用C+語言編程實現(xiàn)，并通過網(wǎng)絡(luò)學(xué)堂提交其源程序及可執(zhí)行文件，參照助教的說明文件；.課程學(xué)習(xí)要求與完成作

18、業(yè)方式遵守課堂紀(jì)律、不遲到，認(rèn)真聽課、及課程學(xué)習(xí)要求與成績評定成績評定標(biāo)準(zhǔn)(暫定)： 平時作業(yè)（紙面與上機(jī)），總計占35%；平時 3次課堂測驗，占45%；課程設(shè)計（期末前交），占20%?？偝煽?= min(100, 作業(yè)總成績*35% + 測驗成績*45% + 課程設(shè)計*20% + 加分【1-5】).課程學(xué)習(xí)要求與成績評定.成績評定如何獲得加分 課堂積極參與 作業(yè)有創(chuàng)意 對教學(xué)與教材建設(shè)有貢獻(xiàn) (如經(jīng)獨立思考，發(fā)現(xiàn)教材、參考書、示例程序中的實質(zhì)問題)獨立完成或承擔(dān)課外具有一定難度的題目或任務(wù)(如最新國內(nèi)外主要競賽的命題與題解，針對某一問題的深入探討), 并提交書面報告 積極參與網(wǎng)絡(luò)學(xué)堂討論，熱心回答同學(xué)提出的問題，部分內(nèi)容有自己的深入理解 (將選擇交流)課程設(shè)計選題和完成情況好，并參加期末交流.成績評定如何獲得加分.教學(xué)組教師信息王宏，主講教師 FIT樓1-508,62796451(O), wanghong 殷人昆教授，教材主編， 62785601