数据结构第01章

《数据结构第01章》由会员分享，可在线阅读，更多相关《数据结构第01章（70页珍藏版）》请在金锄头文库上搜索。

1、关于本课程,课程性质：必修 课程纪律： 严禁旷课、迟到； 课前请关闭手机或调至振动，严禁课堂接听或拔打电话； 要独立思考，按时完成作业。在自己不会解答时可参考其他资料或他人答案，在分析别人的处理思路之后自己动手，鼓励相互讨论，严禁抄袭； 上机实验前应先就要处理的问题写出自己的解决思路和大纲，严禁在机房游戏、网上聊天、流览不相关的网页； 上机程序要现场验收、严禁拷贝他人程序及报告。,中南大学余腊生,1,2019/4/17,成绩组成,平时成绩 20：出勤作业报告 实验成绩 10：出勤程序报告 期末考试成绩 60：接近同类学校考研水平 课程展示 10：课程论文+答辩,中南大学余腊生,2,2019/4

2、/17,数据结构（基于C模板的实现），余腊生，人民邮电出版社 数据结构（C语言版），严蔚敏 吴伟民，清华大学出版社，2001.6 Data Structures and Algorithm Analysis in C+（英文版.第3版），Mark Allen Weiss，人民邮电出版社，2006.11 数据结构与程序设计C+语言描述(影印版)，Robert L.Kruse,Alexander J.Ryba，高等教育出版社，2001.5 数据结构、算法与应用+语言描述（英文版），Sartaj Sahni，机械工业出版社，1999.3,关于教材,主教材,数据结构与算法，余腊生，天津大学出版社,参考

3、教材,中南大学余腊生,3,2019/4/17,课程性质,数据结构是计算机专业的专业基础课 公共基础课、专业基础课、专业方向课、专业选修课 在教学计划中的地位：核心、承上启下 前导课：高等数学、概率论、离散数学、程序设计语言 后续课：数据库、操作系统、编译原理 属于武术中的“练功”科目 “练武不练功，到头一场空” 考研/就业的面试,中南大学余腊生,4,2019/4/17,课程特点,很强的理论性 本课程不是以掌握应用性知识为目的，而是以掌握基本理论，基本方法，基本技能为目的。让学生把握解决什么样的问题，用什么思想，采用什么方法解决，以及用什么方法最优解决等一系列问题。 很强的概念性 本课程要求学生

4、不但应该深刻理解某些概念的所有要素,同时也要求理解为什么要引入某些概念，这些概念的形成过程，以及引入这些概念解决什么样的问题。,中南大学余腊生,5,2019/4/17,课程特点(续),很强的连贯性 本课程结构紧凑，每部分所述问题层层推进，逐步深入。全课程始终是以数据间的关系即“结构”为主线索展开。其中“基本数据结构”部分围饶数据结构三要素即逻辑结构、物理结构、运算特性展开，辅以一定该数据结构基本应用的讲述；而“应用数据结构部分”以基本概念、基本方法、性能分析的顺序展开，使全课程大量庞杂的内容条理分明，轮廓分明。 容易混淆性 本课程中有一些容易混淆的基本概念，也有很多算法，状态等等一系列问题都容

5、易混淆。比如要解决某类问题，也许有很多方法和很多途径，每种方法和途径适用于什么场合，各自存在什么优缺点（例如“内部排序”这一章中各中内排方法的比较与应用），都容易产生相互混淆。,中南大学余腊生,6,2019/4/17,学习目标,掌握基本的数据结构 复用、修改、重组 培养算法设计能力、程序设计能力 算法程序的灵魂 程序设计研究的层次：算法方法学语言工具 培养算法分析能力 评价算法、改进算法 根据应用进行数据结构的选择或设计 结构与算法的扩展应用 培养软件工程的规范，养成良好的程序设计风格 编码风格、文档规格 问题求解过程（每阶段都要考虑测试）： 问题分析总体设计详细设计程序编码调试、测试- 维护

6、/文档,中南大学余腊生,7,2019/4/17,第一项修炼,第一项修炼：自我超越( Personal Mastery ) “自我超越”的修炼是学习不断理清并加深个人的真正愿望，集中精力，培养耐心，并客观地观察现实的过程。它是学习型组织的精神基础。精通“自我超越”的人，能够不断实现他们内心深处最想实现的愿望，他们对生命的态度就如同艺术家对于艺术一样，全心投入、锲而不舍，并不断追求超越自我。有了这种精神动力，个人的学习就不是一个一蹴而就的项目，而是一个永无尽头的持续不断的过程。而组织学习根植于个人对于学习的意愿与能力，也会不断学习。,中南大学余腊生,8,2019/4/17,第二项修炼,第二项修炼：

7、改善心智模式( Improving Mental Models ) “改善心智模式”的修炼是把镜子转向自己，发掘自己内心世界深处的秘密，并客观地审视，借以改善自身的心智模式，更利于自己深入地学习,中南大学余腊生,9,2019/4/17,第三项修炼,第三项修炼：建立共同愿景( Building Shared Vision ) 孙子兵法计篇：“道者，令民与上同意者也，可与之死，可与之生，民弗诡也。”故“上下同欲者胜”。惟有有了衷心渴望实现的共同目标，大家才会发自内心地努力工作、努力学习、追求卓越，从而使组织欣欣向荣。否则，一个缺乏共同愿景的组织必定人心涣散，相互掣肘，难成大器。 共同的愿景常以一位

8、伟大的领袖为中心，或激发自一件共同的危机。但是，很多组织缺乏将个人愿景整合为共同愿景的修炼。,中南大学余腊生,10,2019/4/17,第四项修炼,第四项修炼：团队学习( Team Learning ) 团队中的成员互相学习，取长补短，不仅使团队整体的绩效大幅提升，而且使团队中的成员成长得更快 团队学习存在局限性，以至于在实践中出现了团队中每个人的智商都在120以上，而集体的智商却只有62的窘境 团队学习的修炼从“对话”( dialogue ) 开始。所谓“对话”，指的是团队中的所有成员敞开心扉，进行心灵的沟通，从而进入真正统一思考的方法或过程。另外，“对话”也可以找出有碍学习的互动模式 在现

9、代组织中，学习的基本单位是团队而非个人。除非团队能学习，否则组织就无法学习,中南大学余腊生,11,2019/4/17,第五项修炼,第五项修炼：系统思考( Systems Thinking ) 企业与人类社会都是一种“系统”，是由一系列微妙的、彼此息息相关的因素所构成的有机整体。这些因素通过各不相同的模式或渠道相互影响，“牵一发而动全身”。但是，这种影响并不是立杆见影、一一对应的，而常常是要经年累月才完全展现出来。身处系统中的一小部分，人们往往不由自主地倾向于关注系统中的某一片段（或局部），而无法真正把握整体。系统思考的修炼就在于扩大人们的视野，让人们“见树又见林”,中南大学余腊生,12,201

10、9/4/17,团体学习的最佳单位,海森堡： “科学根源于交谈，在不同的人的合作之下，可能孕育出极为重要的科学成果。” 彼得圣吉： 学习型组织是这么一种组织，“在其中，大家得以不断突破自己的能力上限，创造真心向往的结果，培养全新、前瞻而开阔的思考方式，全力实现共同的抱负，以及不断一起学习如何共同学习” 我们的学习方式 三人行，必有我师 成立3-4人学习小组 变适应性学习为创造性学习,中南大学余腊生,13,2019/4/17,本课程学习方法, 循序渐进学习法 由于本课程很强的理论性、概念性和连贯性，所以学习过程中要从概念入手，逐段、逐节、逐章深刻理解和掌握，层层推进，从基础到应用，最后达到完全掌握

11、该课程内容的要求，加强上机实践环节是非常必要的，能增强对数据结构的理解和应用能力。 概括提炼学习法 每学完一节、一章内容，都要从中概括提炼出本部分内容的要点和重点。一则可以达到内容总结、有效复习的目的，二则可以自检学习中存在的问题。,中南大学余腊生,14,2019/4/17,课程学习方法(续), 归纳对比学习法 针对课程中容易混淆的概念以及课程中同类、非同类容易混淆的问题，进行归纳和比较，从中找出它们的异同点、优缺点。这种方法不仅能搞清楚容易混淆的问题，而且能更深刻理解本课程的内容实质。 循环学习法 由于课程中许多基本概念和复杂算法在顺序地学习过程中并不能达到准确、透彻地理解的程度，有些概念和

12、方法可以应用在多种场合，对这些内容，在学习时就需要循环往复，借助后续内容的信息来全面把握。,中南大学余腊生,15,2019/4/17,学习要求,循序渐进，切忌心浮气躁 提高课外学习的时间和内容 （1：3） 理解科学而不是背诵科学读书 正确对待考试 至少准备一本笔记本 作习题 华罗庚：“学数学不做习题等于入宝山而空返” 至少准备两本作业本和一本课堂讨论用本 作实验 计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。,中南大学余腊生,16,2019/4/17,如何使用教材,主教材 思想火花 参考教材 知识结构、学习要点、重点难点释疑、习题解析 实验指导教材 验证实验设计实验

13、综合实验 网站 中南大学信息学院/本科教学/精品课程/数据结构 教学资源及交流邮箱:assignment_,中南大学余腊生,17,2019/4/17,第 1 章 绪 论,数据结构的兴起和发展 数据结构的研究对象 数据结构的基本概念 算法的概念及特性,本章的基本内容是：,中南大学余腊生,18,2019/4/17,1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著： The Art of Computer Programming 他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计

14、算机科学界的最高荣誉图灵奖，此时，他年仅36岁。,数据结构的创始人克努思,中南大学余腊生,19,2019/4/17,1.1 数据结构的兴起和发展,程序设计的实质是什么?,数据表示：将数据存储在计算机中 数据处理：处理数据，求解问题,数据结构问题起源于程序设计,中南大学余腊生,20,2019/4/17,数据结构随着程序设计的发展而发展,数据结构的发展并未终结 问题数值问题、非数值问题 数 值 问 题数学方程 非数值问题数据结构,1. 无结构阶段 2. 结构化阶段：数据结构算法程序 3. 面向对象阶段： （数据结构算法）程序,1.1 数据结构的兴起和发展,中南大学余腊生,21,2019/4/17,

15、计算机解决问题的过程,具体 问题,描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。,1.2 数据结构的研究对象,中南大学余腊生,22,2019/4/17,例1 学籍管理问题表结构,1.2 数据结构的研究对象,完成什么功能?各表项之间是什么关系？,中南大学余腊生,23,2019/4/17,例2 人机对弈问题树结构,1.2 数据结构的研究对象,如何实现对弈?各格局之间是什么关系？,中南大学余腊生,24,2019/4/17,说明,通常这种关系不是线性的，即从一个棋盘格局可以派生出几个格局。这棵对奕树的“树根”是对弈开始时的棋盘格局，而所有的“叶子”就是可能出现的结局，“

16、 树”可以是某些非数值计算问题的数学模型，它也是一种数据结构。,中南大学余腊生,25,2019/4/17,例3 田径赛的时间安排问题图结构,1.2 数据结构的研究对象,如何表示项目之间的约束关系？,中南大学余腊生,26,2019/4/17,例4 多叉路口交通灯的管理问题,在多叉路口设置几种颜色的交通灯才能既使车辆相互不碰撞,又能达到车辆的最大流通。假设有如下所示的五叉路口：,B,A,E,D,C,中南大学余腊生,27,2019/4/17,1.2 数据结构的研究对象,说明：两条道路之间有通路表示为：XY两条通路有矛盾以图中两个顶点连线表示，没有矛盾则可使用同一种信号灯。通常这类交通、道路问题的数学模型是一种称谓“图”的数据结构。,设置交通灯问题等价为对图的顶点染色问题，要求对图上的每