數據結構課件

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

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

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

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

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

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

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

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

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

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

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

12、的算法抽象邏輯結構基本運算（確定限制）實現存儲結構算法評價不同結構的比較與分析認真考慮各種數據如何表示、組織和存儲？ 隨著面向對象技術的應用，數據結構從定義、分類、構成，到設計、實現與分析的模式與方法都有了長足的發(fā)展；現代數據結構更加注重和強調數據結構的整體性、通用性、復用性、安全性。.非數值計算問題求解須考慮的問題主要解決如何設計出適宜的數據結教材和教學參考書主教材 數據結構（用面向對象方法和C+語言描述）（第2版），殷人昆主編，清華大學出版社, 請選2009年9月第5（ 5）次印刷，￥ 39。輔助教材數據結構習題解析（用面向對象方法與C+語言描述），殷人昆、徐孝凱編著，清華大學出版社。20

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

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

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

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

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

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