数据结构课件.pptx

1、数据结构Data Structures课程简介与教学要求 清华大学计算机清华大学计算机系系 殷人昆殷人昆 王宏王宏 20122012年年春季学期春季学期.学习数据结构的背景学习数据结构的背景系统程序与应用程序的规模和复杂性激增系统程序与应用程序的规模和复杂性激增数据的表示和组织直接关系到问题求解的数据的表示和组织直接关系到问题求解的效率。效率。必须分析待处理对象的特征及各对象间存必须分析待处理对象的特征及各对象间存在的关系。在的关系。必须深入研究必须深入研究 数据在计算机中存储、组织、数据在计算机中存储、组织、传递和转换的过程及方法。传递和转换的过程及方法。一门重要的计算机专业（能力考查）课程

2、一门重要的计算机专业（能力考查）课程 全国研考全国研考CN-29，OS-35，CP-41，DS-45.形成阶段形成阶段：60年代初期年代初期，“数据结构数据结构”有关的内容散见于操作系有关的内容散见于操作系统、编译原理和表处理语言等课程。统、编译原理和表处理语言等课程。1968年年，“数据结构数据结构”作为一门独立课程作为一门独立课程被列入美国被列入美国一些大学计算机科学系的教学计划一些大学计算机科学系的教学计划由唐由唐欧欧克努特克努特（D.E.Knuth，The Art of Computer Programming的作者，图灵奖得主的作者，图灵奖得主）开创其最初体系开创其最初体系。发展阶段

3、发展阶段：数据结构的概念不断扩充，包括了集合论、代数结构、数据结构的概念不断扩充，包括了集合论、代数结构、图论等图论等“离散数学结构离散数学结构”的内容。的内容。70年代后期年代后期，我国高校陆续开设该课程。，我国高校陆续开设该课程。.数据结构课程的地位数据结构课程的地位 关系关系机器机器组织组织存储存储对象对象关系关系操作操作数学数学.数据结构是一门侧重数据结构是一门侧重研究研究非数值计算非数值计算的的程序设计问题中计算机的操作对象及其程序设计问题中计算机的操作对象及其之间关系与操作的学科之间关系与操作的学科。不仅是复杂程序设计的基础，也是设计不仅是复杂程序设计的基础，也是设计和实现编译程序

4、、操作系统、数据库系和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重统及其它系统程序和大型应用程序的重要基础。要基础。N.Wirth早在早在20世纪世纪70年代就曾形象描述年代就曾形象描述Algorithm+Data Structure=Program .程序设计与程序设计与问题求解问题求解数据结构基础数据结构基础离散数学离散数学 1离散数学离散数学 2计算机科学基础计算机科学基础计算机系统计算机系统原理与汇编原理与汇编算法设计算法设计与分析与分析编译原理编译原理操作系统操作系统软件工程软件工程计算机组计算机组织与结构织与结构必修课课程设置与数据结构的关系必修课课程设置与数

5、据结构的关系.选修课课程设置与数据结构的关系选修课课程设置与数据结构的关系 数据结构数据结构计算机科学基础计算机科学基础算法与复杂性算法与复杂性数据库数据库（文件处理）（文件处理）人工智能人工智能计算机网络计算机网络图形学图形学多媒体技术多媒体技术.建立数学模型建立数学模型选择计算机语言与算法选择计算机语言与算法 编写程序编写程序测试（调试）测试（调试）最终解答。最终解答。数值计算的关键是：如何归纳出数学模型数值计算的关键是：如何归纳出数学模型（方程）？（方程）？程序设计人员关注的是程序设计人员关注的是模型的建立与算法的模型的建立与算法的选择选择 典型问题典型问题：l电路分析与模拟电路分析与模

6、拟l大坝（应力与应变）结构分析大坝（应力与应变）结构分析l弹道仿真程序弹道仿真程序 天气预报等天气预报等.数据元素之间的相互关系有时无法或很难用数据元素之间的相互关系有时无法或很难用数学方程加以描述。数学方程加以描述。例如，例如，电话号码查询问题电话号码查询问题 按顺序存储方式：遍历表按顺序存储方式：遍历表 按姓氏索引方式：索引表按姓氏索引方式：索引表是否可以利用性能更优的查找算法，取决于是否可以利用性能更优的查找算法，取决于这张表的组织结构及存储方式这张表的组织结构及存储方式。数据数据元素元素的结构和存储方式决定了查找与维的结构和存储方式决定了查找与维护（算法）的效率。护（算法）的效率。.2

7、011人机大战人机大战 电脑完胜电脑完胜.历史时刻 2011年年2月月142月月16日，在美国家喻户晓的电视智力竞赛节日，在美国家喻户晓的电视智力竞赛节目目Jeopardy!(危险或危机边缘危险或危机边缘)中，中，IBM超级计算机系超级计算机系统统 WATSON(沃森沃森)战胜了该节目有史以来最优秀的两位人战胜了该节目有史以来最优秀的两位人类冠军类冠军Ken Jennings（詹宁斯詹宁斯）和和Brad Rutter（拉特拉特），圆，圆满结束了这场历时三天的人机大战。满结束了这场历时三天的人机大战。第一回合第一回合 沃森沃森：5000分，分，詹宁斯詹宁斯：2000分，分，拉特拉特：5000分分

8、 第二回合的比赛，第二回合的比赛，30个问题中，个问题中，沃森沃森答对答对24个，个，詹宁斯詹宁斯和和拉拉特特分别答对分别答对3个和个和2个。个。答对问题价值总计：答对问题价值总计：沃森沃森：77147 詹宁斯詹宁斯：24000 拉特拉特：21600.“危机边缘危机边缘”是一款智力问答节目，国内类似的节目有是一款智力问答节目，国内类似的节目有“开心辞典开心辞典”等，但是二者之间具有明显的区别。等，但是二者之间具有明显的区别。“开心辞典开心辞典”是主持人提出问题，选手给出问题的答案，是主持人提出问题，选手给出问题的答案，并且问题相对简单，涉及较为基础的科技与人文知识。并且问题相对简单，涉及较为基

9、础的科技与人文知识。“危机边缘危机边缘”则不同则不同，主持人有时给出的是一个问题的答，主持人有时给出的是一个问题的答案，而选手需要给出答案所对应的问题。比如主持人说：案，而选手需要给出答案所对应的问题。比如主持人说：“这是一种冷血的、无足的并且进行冬眠的动物这是一种冷血的、无足的并且进行冬眠的动物”，选手应回答的则是该句对应的问题：选手应回答的则是该句对应的问题：“什么是蛇什么是蛇?”有多名选手同时参加节目，问题涉及历史、时事、科学、有多名选手同时参加节目，问题涉及历史、时事、科学、艺术、体育、地理、流行文化、文学与语言、文字游戏等艺术、体育、地理、流行文化、文学与语言、文字游戏等等，且每个领

10、域还对应问题的难度等级，等级越高奖金越等，且每个领域还对应问题的难度等级，等级越高奖金越高，倘若答错，则罚金同样水涨船高。高，倘若答错，则罚金同样水涨船高。思考：机器用何种方式理解问题？思考：机器用何种方式理解问题？.理解超群 主持人在向人类选手念出问题的同时，主持人在向人类选手念出问题的同时，WATSON会收到题目的文本，并在得出答案后以语音的方会收到题目的文本，并在得出答案后以语音的方式读出（无视觉与听觉功能）。式读出（无视觉与听觉功能）。令人惊叹的是令人惊叹的是WATSON能领会题目中不少双关语能领会题目中不少双关语、反话、谜语、讽刺口吻等微妙的表达方式并给、反话、谜语、讽刺口吻等微妙的

11、表达方式并给出正确答案。出正确答案。做到这一点显然比让机器战胜国际象棋大师更具做到这一点显然比让机器战胜国际象棋大师更具挑战性，更考验电脑的挑战性，更考验电脑的“智商智商”（1997年，年，IBM的的深蓝以深蓝以 3.5:2.5 战胜卡斯帕罗夫战胜卡斯帕罗夫）。.题目管窥 问题举例问题举例：阿根廷一家美术馆阿根廷一家美术馆1987年失窃的一件藏年失窃的一件藏品品 答案：答案：西班牙国王菲利普二世的肖像。西班牙国王菲利普二世的肖像。该题机器和人均未答对。该题机器和人均未答对。.低级错误 尽管尽管WATSON“聪明绝顶聪明绝顶”，但偶尔会，但偶尔会犯一些低级错误。犯一些低级错误。如问题：如问题：美

12、国某城市的最大机场以二战美国某城市的最大机场以二战中的一名英雄命名，而该城市的第二大中的一名英雄命名，而该城市的第二大机场以二战中的一场战役命名机场以二战中的一场战役命名。正确答案是正确答案是芝加哥芝加哥，而，而WATSON的回答的回答竟是加拿大城市多伦多。竟是加拿大城市多伦多。.求解浅析 尽管存储了大量的百科全书和其他信息，但尽管存储了大量的百科全书和其他信息，但危机边缘危机边缘的问题并不会让的问题并不会让沃森沃森轻易地找到答案，同时寻找答案从来轻易地找到答案，同时寻找答案从来就不是计算机的强项。就不是计算机的强项。搜索引擎无法回答问题，只能给出符合搜索关键词的成千搜索引擎无法回答问题，只能

13、给出符合搜索关键词的成千上万个似是而非的可能答案。上万个似是而非的可能答案。沃森沃森则要通过各种不同的算法对所有的候选答案获取更多则要通过各种不同的算法对所有的候选答案获取更多的证据支持，再根据证据的强度对每个候选答案给出其置的证据支持，再根据证据的强度对每个候选答案给出其置信度，最后根据置信度来决定是否向用户提供置信度最高信度，最后根据置信度来决定是否向用户提供置信度最高的唯一答案。的唯一答案。这一过程极其复杂，因此需要动用几千个处理器的超级计这一过程极其复杂，因此需要动用几千个处理器的超级计算机来处理一个问题。算机来处理一个问题。.WATSON 其身 IBM超级计算机系统超级计算机系统沃森

14、沃森“以以 IBM 创始人创始人 Thomas J.Watson 的姓氏命名。的姓氏命名。由由10 台台 IBM POWER 7 系统系统组成（每个系统机架体积有组成（每个系统机架体积有冰箱大小）冰箱大小）运行运行 Linux 操作系统操作系统 包含包含 15 TB 内存内存和和 2880 个处理器内核个处理器内核（90台服务器，每台服务器，每台有台有4个个8核核中央处理器）中央处理器）运行速度高达运行速度高达 80 Teraflops，即，即每秒执行每秒执行 80 万亿次浮点运万亿次浮点运算算。研制小组为以研制小组为以CMU埃里克埃里克.尼贝里教授为首多个研究机构尼贝里教授为首多个研究机构的

15、的20多名专家，耗时多名专家，耗时4年。年。.分析引擎与DeepQA问答系统 除强大的硬件资源外，除强大的硬件资源外，沃森沃森能够快速回答棘手的问题还得能够快速回答棘手的问题还得益于采用了益于采用了 IBM POWER 7 系统作为分析引擎。系统作为分析引擎。POWER 7 系统经过专门的工作负载优化，能够同时处理系统经过专门的工作负载优化，能够同时处理大量信息并且运行数千个分析任务，以便跟上参赛者的速大量信息并且运行数千个分析任务，以便跟上参赛者的速度。度。沃森沃森能够在不到三秒钟的时间内研读存储在内存中的约能够在不到三秒钟的时间内研读存储在内存中的约 2 亿页自然语言内容亿页自然语言内容(

16、相当于相当于100万本书万本书)，并找到问题的确切，并找到问题的确切答案。答案。沃森沃森的的DeepQA(深度开放域问答系统深度开放域问答系统)采用突破性分析技采用突破性分析技术，能够术，能够理解问题的内容，搜索海量的信息，分析相应的理解问题的内容，搜索海量的信息，分析相应的证据，给出最佳的答案证据，给出最佳的答案。.专家评价 WATSON获胜标志获胜标志人工智能领域的历史性时刻人工智能领域的历史性时刻 但电脑的胜利归根到底是人类的胜利 计算机技术的进步让人更加珍视人类的独特之处计算机技术的进步让人更加珍视人类的独特之处 研制者：研制者：计算机可以变得越来越聪明，但是要让计算机可以变得越来越聪

17、明，但是要让它真正具备人类的智能可能永远也做不到它真正具备人类的智能可能永远也做不到 有价值的设想有价值的设想：构建一个系统，将人类所长和：构建一个系统，将人类所长和WATSON所长结合在一起，解决那些单独一方不所长结合在一起，解决那些单独一方不能解决的难题。能解决的难题。.主要解决如何设计出主要解决如何设计出适宜的数据结构及相应的算法适宜的数据结构及相应的算法抽象逻辑结构抽象逻辑结构基本运算（确定限制）基本运算（确定限制）实现存储结构算法实现存储结构算法评价不同结构的比较与分析评价不同结构的比较与分析认真考虑认真考虑各种数据如何表示各种数据如何表示、组织和存储组织和存储？随着面向对象技术的应

18、用，数据结构从定义、分类、随着面向对象技术的应用，数据结构从定义、分类、构成，到设计、实现与分析的模式与方法都有了长构成，到设计、实现与分析的模式与方法都有了长足的发展；足的发展；现代数据结构更加注重和强调现代数据结构更加注重和强调数据结构的数据结构的整体性、整体性、通用性、复用性、安全性通用性、复用性、安全性。.主教材主教材 数据结构数据结构（用面向对象方法和（用面向对象方法和C+语言描述）（第语言描述）（第2版），殷人昆主编，清华大学出版社版），殷人昆主编，清华大学出版社,请选请选2009年年9月第月第5（5）次印刷，）次印刷，￥39。辅助教材辅助教材数据结构习题解析数据结构习题解析（用面

19、向对象方法与（用面向对象方法与C+语言描语言描述），殷人昆、徐孝凯编著，清华大学出版社。述），殷人昆、徐孝凯编著，清华大学出版社。2008年年2月第月第14次印刷次印刷，￥26。其它其它 J.R.Hubbard,Data Structures with C+,机械工业出版社影印机械工业出版社影印,中译名中译名数据结构数据结构 习题与解答习题与解答 C+版版。￥40.过去使用的老过去使用的老版本教材版本教材.数据结构（数据结构（C语言版）语言版）,严蔚敏严蔚敏,吴伟民编著吴伟民编著,清华大学出版社清华大学出版社.2006年年5月以后印刷的版本。月以后印刷的版本。334页，页，￥30。数据结构（数

20、据结构（C+语言版）语言版）,邓俊辉编邓俊辉编,清华大学出版社，清华大学出版社，2011年年11月，月，419页，页，￥39。数据结构与算法分析数据结构与算法分析C语言描述语言描述（Data Structures and Algorithm Analysis in C）（）（英文版英文版 第第2版版）原著原著Mark Allen WeissMark Allen Weiss，陈越陈越 改编改编。人民邮电出版社人民邮电出版社，2005年年12月。月。501页，页，￥49。算法算法I-IV（C+实现）实现）基础、数据结构、排序和搜索（基础、数据结构、排序和搜索（Algorithms in C+,Pa

21、rts 1-4，Fundamentals,Data Structures,Sorting,Searching）(第三版第三版)，Robert SedgewickRobert Sedgewick著，张铭泽等译著，张铭泽等译。中国电力出版社中国电力出版社，2005年年1月。月。532页，页，￥55。Data Structures with C+Using STL（英文影印版英文影印版），），数据结构数据结构 C+语言描述语言描述 应用标准模板库应用标准模板库（STL）第第2 2版，版，William Ford,William William Ford,William ToppTopp著著,清华大学

22、出版社清华大学出版社.2003年年1月第月第1版版.1037页，页，￥86。*.教学内容和安排教学内容和安排绪论绪论3 学时学时线性表（顺序表与链表）线性表（顺序表与链表）5 学时学时栈、队列与递归、表达式计算栈、队列与递归、表达式计算6 学时学时数组、字符串与广义表数组、字符串与广义表6学时学时树与二叉树、堆、树与二叉树、堆、Huffman树树9学时学时搜索结构、搜索树搜索结构、搜索树 6学时学时集合与散列（散列表与散列函数）集合与散列（散列表与散列函数）6学时学时图结构（遍历、生成树、最短路径）图结构（遍历、生成树、最短路径）8学时学时内部排序内部排序8学时学时外部排序与动态搜索外部排序与

23、动态搜索3学时学时.教学目标教学目标 掌握数据结构的表示、实现方法和基本掌握数据结构的表示、实现方法和基本操作操作 了解主要（基本）算法与不同数据结构了解主要（基本）算法与不同数据结构之间的内在联系之间的内在联系 了解数据结构的主要应用背景了解数据结构的主要应用背景 灵活地选用各类（基本）算法及对应的灵活地选用各类（基本）算法及对应的数据结构，解决实际问题数据结构，解决实际问题.数据结构与算法数据结构与算法 数据结构：线性表数据结构：线性表 /栈栈 /队列队列 /树树 /散列表散列表 /优优先队列先队列 /图图 /./.算法：枚举算法：枚举 /查找查找 /排序排序 /遍历遍历 /散列散列 /最

24、小生最小生成树成树 /最短路径最短路径 /./.算法设计策略：算法设计策略：/贪心贪心 /回溯回溯 /分治分治 /动态规划动态规划 /随机化随机化 /./.高效的算法，需要高效的数据结构加以支持高效的算法，需要高效的数据结构加以支持 学习数据结构，就是要学会学习数据结构，就是要学会 高效地利用计算机，有效地存储、组织、传递和转换高效地利用计算机，有效地存储、组织、传递和转换数据数据.学好一门课程，需要教师与学生双方的学好一门课程，需要教师与学生双方的共同努力与配合。课堂教学与课后钻研共同努力与配合。课堂教学与课后钻研理解相结合，同时还要不断练习，巩固理解相结合，同时还要不断练习，巩固提高、以深

25、入掌握课程的内容。提高、以深入掌握课程的内容。本着教学相长的精神，希望同学们经常本着教学相长的精神，希望同学们经常对教学效果作出反馈，提出宝贵意见，对教学效果作出反馈，提出宝贵意见，以便及时调整改进教学方法。以便及时调整改进教学方法。.课程学习要求与课程学习要求与完成作业方式完成作业方式遵守课堂纪律、不迟到，认真听课、及时复习；遵守课堂纪律、不迟到，认真听课、及时复习；按时按时、独立地独立地完成每次作业；完成每次作业；完成作业方式完成作业方式：1.大约每大约每4周提交一次作业周提交一次作业(由助教安排由助教安排)；2.作业分两部分：作业分两部分：第第1部分是纸面作业，要求用笔写部分是纸面作业，

26、要求用笔写,并不得复并不得复印和打印。印和打印。第第2部分是上机作业，要求用部分是上机作业，要求用C+语言编语言编程实现，并通过网络学堂提交其源程序及程实现，并通过网络学堂提交其源程序及可执行文件，参照助教的说明文件；可执行文件，参照助教的说明文件；.课程学习要求与成绩评定课程学习要求与成绩评定成绩评定标准成绩评定标准(暂定暂定)：1.平时作业平时作业（纸面与上机），总计占（纸面与上机），总计占35%；2.平时平时 3次次课堂测验课堂测验，占，占45%；3.课程设计课程设计（期末前交），占（期末前交），占20%。总成绩总成绩 =min(100,=min(100,作业总成绩作业总成绩*35%+3

27、5%+测验成绩测验成绩*45%+45%+课程设计课程设计*20%+20%+加分加分【1-51-5】).成绩评定成绩评定 如何获得加分如何获得加分 课堂积极参与课堂积极参与 作业有创意作业有创意 对教学与教材建设有贡献对教学与教材建设有贡献 (如经独立思考，发现教材、参考书、示例程序中的实质如经独立思考，发现教材、参考书、示例程序中的实质问题问题)独立完成或承担课外具有一定难度的题目或任务独立完成或承担课外具有一定难度的题目或任务(如最如最新国内外主要竞赛的命题与题解，针对某一问题的深入新国内外主要竞赛的命题与题解，针对某一问题的深入探讨探讨),并提交书面报告并提交书面报告 积极参与网络学堂讨论

28、，热心回答同学提出的问题积极参与网络学堂讨论，热心回答同学提出的问题，部部分内容有自己的深入理解分内容有自己的深入理解(将选择交流将选择交流)课程设计选题和完成情况好，并参加期末交流课程设计选题和完成情况好，并参加期末交流.教学组教师信息教学组教师信息王宏，主讲教师王宏，主讲教师 FIT楼楼1-508,13910922039，62796451(O), 殷人昆教授，教材主编，殷人昆教授，教材主编，62785601(O)邓俊辉，教师邓俊辉，教师 .课程助教信息课程助教信息王欢王欢,助教博士生助教博士生 办公地点：办公地点：FIT大楼大楼 1-511 手机：手机：15801402071 邮箱：邮箱：.同心协力同心协力 完成教学目标完成教学目标 充分发挥充分发挥三方面三方面的积极性的积极性 教学组教学组教师教师、助教助教以及以及学生学生的综合优势的综合优势 结合课程设计将安排同学在课上交流结合课程设计将安排同学在课上交流 及时沟通反馈，不断调整改进及时沟通反馈，不断调整改进 尽最大努力让同学满意，圆满完成教学尽最大努力让同学满意，圆满完成教学目标目标.Thanks for Coming!谢谢谢谢2012年年2月月20日日THU.