数据结构第01章课件.ppt

1、数据结构与算法（数据结构与算法（C版）版）关于本课程关于本课程 课程性质：必修必修 课程纪律：严禁旷课、迟到；课前请关闭手机或调至振动，严禁课堂接听或拔打电话；要独立思考，按时完成作业。在自己不会解答时可参考其他资料或他人答案，在分析别人的处理思路之后自己动手，鼓励相互讨论，严禁抄袭；上机实验前应先就要处理的问题写出自己的解决思路和大纲，严禁在机房游戏、网上聊天、流览不相关的网页；上机程序要现场验收、严禁拷贝他人程序及报告。中南大学余腊生12023-2-6数据结构与算法（数据结构与算法（C版）版）成绩组成成绩组成 平时成绩平时成绩 20：出勤作业报告：出勤作业报告 实验成绩实验成绩 10：出勤

2、程序报告：出勤程序报告 期末考试成绩期末考试成绩 60：接近同类学校考研水平：接近同类学校考研水平 课程展示课程展示 10：课程论文：课程论文+答辩答辩中南大学余腊生22023-2-6数据结构与算法（数据结构与算法（C版）版）1.数据结构（基于数据结构（基于C模板的实现），余腊生，人民邮电出版社模板的实现），余腊生，人民邮电出版社2.数据结构（数据结构（C语言版），严蔚敏语言版），严蔚敏 吴伟民，清华大学出版社，吴伟民，清华大学出版社，2001.6 3.Data Structures and Algorithm Analysis in C+（英文版（英文版.第第3版），版），Mark Alle

3、n Weiss，人民邮电出版社，人民邮电出版社，2006.114.数据结构与程序设计数据结构与程序设计C+语言描述语言描述(影印版影印版)，Robert L.Kruse,Alexander J.Ryba，高等教育出版社，高等教育出版社，2001.55.数据结构、算法与应用数据结构、算法与应用+语言描述语言描述（英文版），（英文版），Sartaj Sahni，机械工业出版社，机械工业出版社，1999.3 关于教材关于教材主教材主教材数据结构与算法，余腊生，天津大学出版社数据结构与算法，余腊生，天津大学出版社参考教材参考教材中南大学余腊生32023-2-6数据结构与算法（数据结构与算法（C版）版）

4、课程性质课程性质 数据结构是计算机专业的专业基础课数据结构是计算机专业的专业基础课 公共基础课、专业基础课、专业方向课、专业选修课公共基础课、专业基础课、专业方向课、专业选修课 在教学计划中的地位：核心、承上启下在教学计划中的地位：核心、承上启下 前导课：高等数学、概率论、离散数学、程序设计语言前导课：高等数学、概率论、离散数学、程序设计语言 后续课：数据库、操作系统、编译原理后续课：数据库、操作系统、编译原理 属于武术中的属于武术中的“练功练功”科目科目 “练武不练功，到头一场空练武不练功，到头一场空”考研考研/就业的面试就业的面试中南大学余腊生42023-2-6数据结构与算法（数据结构与算

5、法（C版）版）课程特点课程特点 很强的理论性本课程不是以掌握应用性知识为目的，而是以掌本课程不是以掌握应用性知识为目的，而是以掌握基本理论，基本方法，基本技能为目的。让学生把握基本理论，基本方法，基本技能为目的。让学生把握解决什么样的问题，用什么思想，采用什么方法解握解决什么样的问题，用什么思想，采用什么方法解决，以及用什么方法最优解决等一系列问题决，以及用什么方法最优解决等一系列问题。很强的概念性本课程要求学生不但应该深刻理解某些概念的所本课程要求学生不但应该深刻理解某些概念的所有要素有要素,同时也要求理解为什么要引入某些概念，这些同时也要求理解为什么要引入某些概念，这些概念的形成过程，以及

6、引入这些概念解决什么样的问概念的形成过程，以及引入这些概念解决什么样的问题题。中南大学余腊生52023-2-6数据结构与算法（数据结构与算法（C版）版）课程特点课程特点(续续)很强的连贯性本课程结构紧凑，每部分所述问题层层推进，逐步深入。全课程本课程结构紧凑，每部分所述问题层层推进，逐步深入。全课程始终是以数据间的关系即始终是以数据间的关系即“结构结构”为主线索展开。其中为主线索展开。其中“基本数据结构基本数据结构”部分围饶数据结构三要素即逻辑结构、物理结构、运算特性展开，部分围饶数据结构三要素即逻辑结构、物理结构、运算特性展开，辅以一定该数据结构基本应用的讲述；而辅以一定该数据结构基本应用的

7、讲述；而“应用数据结构部分应用数据结构部分”以基以基本概念、基本方法、性能分析的顺序展开，使全课程大量庞杂的内本概念、基本方法、性能分析的顺序展开，使全课程大量庞杂的内容条理分明，轮廓分明容条理分明，轮廓分明。容易混淆性本课程中有一些容易混淆的基本概念，也有很多算法，状态等本课程中有一些容易混淆的基本概念，也有很多算法，状态等等一系列问题都容易混淆。比如要解决某类问题，也许有很多方法等一系列问题都容易混淆。比如要解决某类问题，也许有很多方法和很多途径，每种方法和途径适用于什么场合，各自存在什么优缺和很多途径，每种方法和途径适用于什么场合，各自存在什么优缺点（例如点（例如“内部排序内部排序”这一

8、章中各中内排方法的比较与应用），都容这一章中各中内排方法的比较与应用），都容易产生相互混淆易产生相互混淆。中南大学余腊生62023-2-6数据结构与算法（数据结构与算法（C版）版）学习目标学习目标 掌握基本的数据结构掌握基本的数据结构 复用、修改、重组复用、修改、重组 培养算法设计能力、程序设计能力培养算法设计能力、程序设计能力 算法算法程序的灵魂程序的灵魂 程序设计研究的层次：算法程序设计研究的层次：算法方法学方法学语言语言工具工具 培养算法分析能力培养算法分析能力 评价算法、改进算法评价算法、改进算法 根据应用进行数据结构的选择或设计根据应用进行数据结构的选择或设计 结构与算法的扩展应用结

9、构与算法的扩展应用 培养软件工程的规范，养成良好的程序设计风格培养软件工程的规范，养成良好的程序设计风格 编码风格、文档规格编码风格、文档规格 问题求解过程（每阶段都要考虑测试）：问题求解过程（每阶段都要考虑测试）：问题分析问题分析总体设计总体设计详细设计详细设计程序编码程序编码调试、测试调试、测试-维护维护/文档文档中南大学余腊生72023-2-6数据结构与算法（数据结构与算法（C版）版）第一项修炼 第一项修炼：自我超越(Personal Mastery)“自我超越”的修炼是学习不断理清并加深个人的真正愿望，集中精力，培养耐心，并客观地观察现实的过程。它是学习型组织的精神基础。精通“自我超越

10、”的人，能够不断实现他们内心深处最想实现的愿望，他们对生命的态度就如同艺术家对于艺术一样，全心投入、锲而不舍，并不断追求超越自我。有了这种精神动力，个人的学习就不是一个一蹴而就的项目，而是一个永无尽头的持续不断的过程。而组织学习根植于个人对于学习的意愿与能力，也会不断学习。中南大学余腊生82023-2-6数据结构与算法（数据结构与算法（C版）版）第二项修炼 第二项修炼：改善心智模式(Improving Mental Models)“改善心智模式”的修炼是把镜子转向自己，发掘自己内心世界深处的秘密，并客观地审视，借以改善自身的心智模式，更利于自己深入地学习中南大学余腊生92023-2-6数据结构

11、与算法（数据结构与算法（C版）版）第三项修炼 第三项修炼：建立共同愿景(Building Shared Vision)孙子兵法计篇：“道者，令民与上同意者也，可与之死，可与之生，民弗诡也。”故“上下同欲者胜”。惟有有了衷心渴望实现的共同目标，大家才会发自内心地努力工作、努力学习、追求卓越，从而使组织欣欣向荣。否则，一个缺乏共同愿景的组织必定人心涣散，相互掣肘，难成大器。共同的愿景常以一位伟大的领袖为中心，或激发自一件共同的危机。但是，很多组织缺乏将个人愿景整合为共同愿景的修炼。中南大学余腊生102023-2-6数据结构与算法（数据结构与算法（C版）版）第四项修炼 第四项修炼：团队学习(Team

12、 Learning)团队中的成员互相学习，取长补短，不仅使团队整体的绩效大幅提升，而且使团队中的成员成长得更快 团队学习存在局限性，以至于在实践中出现了团队中每个人的智商都在120以上，而集体的智商却只有62的窘境 团队学习的修炼从“对话”(dialogue)开始。所谓“对话”，指的是团队中的所有成员敞开心扉，进行心灵的沟通，从而进入真正统一思考的方法或过程。另外，“对话”也可以找出有碍学习的互动模式 在现代组织中，学习的基本单位是团队而非个人。除非团队能学习，否则组织就无法学习 中南大学余腊生112023-2-6数据结构与算法（数据结构与算法（C版）版）第五项修炼 第五项修炼：系统思考(Sy

13、stems Thinking)企业与人类社会都是一种“系统”，是由一系列微妙的、彼此息息相关的因素所构成的有机整体。这些因素通过各不相同的模式或渠道相互影响，“牵一发而动全身”。但是，这种影响并不是立杆见影、一一对应的，而常常是要经年累月才完全展现出来。身处系统中的一小部分，人们往往不由自主地倾向于关注系统中的某一片段（或局部），而无法真正把握整体。系统思考的修炼就在于扩大人们的视野，让人们“见树又见林”中南大学余腊生122023-2-6数据结构与算法（数据结构与算法（C版）版）团体学习的最佳单位 海森堡：“科学根源于交谈，在不同的人的合作之下，可能孕育出极为重要的科学成果。”彼得圣吉：学习型

14、组织是这么一种组织，“在其中，大家得以不断突破自己的能力上限，创造真心向往的结果，培养全新、前瞻而开阔的思考方式，全力实现共同的抱负，以及不断一起学习如何共同学习”我们的学习方式 三人行，必有我师 成立3-4人学习小组 变适应性学习为创造性学习中南大学余腊生132023-2-6数据结构与算法（数据结构与算法（C版）版）本课程学习方法本课程学习方法 循序渐进学习法由于本课程很强的理论性、概念性和连贯性，所由于本课程很强的理论性、概念性和连贯性，所以学习过程中要从概念入手，逐段、逐节、逐章深刻以学习过程中要从概念入手，逐段、逐节、逐章深刻理解和掌握，层层推进，从基础到应用，最后达到完理解和掌握，层

15、层推进，从基础到应用，最后达到完全掌握该课程内容的要求，加强上机实践环节是非常全掌握该课程内容的要求，加强上机实践环节是非常必要的，能增强对数据结构的理解和应用能力必要的，能增强对数据结构的理解和应用能力。概括提炼学习法每学完一节、一章内容，都要从中概括提炼出本每学完一节、一章内容，都要从中概括提炼出本部分内容的要点和重点。一则可以达到内容总结、有部分内容的要点和重点。一则可以达到内容总结、有效复习的目的，二则可以自检学习中存在的问题效复习的目的，二则可以自检学习中存在的问题。中南大学余腊生142023-2-6数据结构与算法（数据结构与算法（C版）版）课程学习方法课程学习方法(续续)归纳对比学

16、习法针对课程中容易混淆的概念以及课程中同类、非针对课程中容易混淆的概念以及课程中同类、非同类容易混淆的问题，进行归纳和比较，从中找出它同类容易混淆的问题，进行归纳和比较，从中找出它们的异同点、优缺点。这种方法不仅能搞清楚容易混们的异同点、优缺点。这种方法不仅能搞清楚容易混淆的问题，而且能更深刻理解本课程的内容实质淆的问题，而且能更深刻理解本课程的内容实质。循环学习法由于课程中许多基本概念和复杂算法在顺序地学由于课程中许多基本概念和复杂算法在顺序地学习过程中并不能达到准确、透彻地理解的程度，有些习过程中并不能达到准确、透彻地理解的程度，有些概念和方法可以应用在多种场合，对这些内容，在学概念和方法

17、可以应用在多种场合，对这些内容，在学习时就需要循环往复，借助后续内容的信息来全面把习时就需要循环往复，借助后续内容的信息来全面把握握。中南大学余腊生152023-2-6数据结构与算法（数据结构与算法（C版）版）学习要求学习要求 循序渐进，切忌心浮气躁循序渐进，切忌心浮气躁 提高课外学习的时间和内容提高课外学习的时间和内容（1：3）理解科学而不是背诵科学理解科学而不是背诵科学读书读书 正确对待考试正确对待考试 至少准备一本笔记本至少准备一本笔记本 作习题作习题 华罗庚：华罗庚：“学数学不做习题等于入宝山而空返学数学不做习题等于入宝山而空返”至少准备两本作业本和一本课堂讨论用本至少准备两本作业本和

18、一本课堂讨论用本 作实验作实验 计算机学科是一门科学性与工程性并重的学科，表现为计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。理论和实践紧密结合的特征。中南大学余腊生162023-2-6数据结构与算法（数据结构与算法（C版）版）如何使用教材如何使用教材 主教材主教材 思想火花思想火花 参考教材参考教材 知识结构、学习要点、重点难点释疑、习题解析知识结构、学习要点、重点难点释疑、习题解析 实验指导教材实验指导教材 验证实验验证实验设计实验设计实验综合实验综合实验 网站网站 中南大学信息学院中南大学信息学院/本科教学本科教学/精品课程精品课程/数据结数据结构构 教学资源

19、及交流邮箱教学资源及交流邮箱:assignment_中南大学余腊生172023-2-6数据结构与算法（数据结构与算法（C版）版）第第 1 章章 绪绪 论论数据结构的兴起和发展数据结构的兴起和发展数据结构的研究对象数据结构的研究对象 数据结构的基本概念数据结构的基本概念算法的概念及特性算法的概念及特性本章的基本内容是：本章的基本内容是：中南大学余腊生182023-2-6数据结构与算法（数据结构与算法（C版）版）1938年出生，年出生，25岁毕业于加州理工岁毕业于加州理工学院数学系，博士毕业后留校任教，学院数学系，博士毕业后留校任教，28岁任副教授。岁任副教授。30岁时，加盟斯坦岁时，加盟斯坦福大

20、学计算机系，任教授。从福大学计算机系，任教授。从31岁岁起，开始出版他的历史性经典巨著：起，开始出版他的历史性经典巨著：The Art of Computer Programming他计划共写他计划共写7卷，然而出版三卷之后，卷，然而出版三卷之后，已震惊世界，使他获得计算机科学已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年界的最高荣誉图灵奖，此时，他年仅仅36岁。岁。数据结构的创始人数据结构的创始人克努思克努思中南大学余腊生192023-2-6数据结构与算法（数据结构与算法（C版）版）1.1 数据结构的兴起和发展数据结构的兴起和发展 程序设计的实质是什么程序设计的实质是什么?数据

21、表示：数据表示：将数据存储在计算机中将数据存储在计算机中数据处理：数据处理：处理数据，求解问题处理数据，求解问题数据结构问题起源于程序设计数据结构问题起源于程序设计 中南大学余腊生202023-2-6数据结构与算法（数据结构与算法（C版）版）数据结构随着程序设计的发展而发展数据结构随着程序设计的发展而发展 数据结构的发展并未终结数据结构的发展并未终结 问题问题数值问题、非数值问题数值问题、非数值问题 数数 值值 问问 题题数学方程数学方程 非数值问题非数值问题数据结构数据结构1.无结构阶段无结构阶段2.结构化阶段：数据结构算法程序结构化阶段：数据结构算法程序3.面向对象阶段：面向对象阶段：（数

22、据结构算法）程序（数据结构算法）程序1.1 数据结构的兴起和发展数据结构的兴起和发展 中南大学余腊生212023-2-6数据结构与算法（数据结构与算法（C版）版）计算机解决问题的过程具体问题数学模型抽象建模数据结构数据结构算法数据结构算法分析与设计程序设计程序问题求解描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。1.2 数据结构的研究对象数据结构的研究对象中南大学余腊生222023-2-6数据结构与算法（数据结构与算法（C版）版）例例1 学籍管理问题学籍管理问题表结构表结构学号学号姓名姓名性别性别出生日期出生日期政治面貌政治面貌0001王王 军军男男1983/0

23、9/02团员团员0002李李 明明男男1982/12/25党员党员0003汤晓影汤晓影女女1984/03/26团员团员1.2 数据结构的研究对象数据结构的研究对象完成什么功能完成什么功能?各表项之间是什么关系？各表项之间是什么关系？中南大学余腊生232023-2-6数据结构与算法（数据结构与算法（C版）版）例例2 人机对弈问题人机对弈问题树结构树结构1.2 数据结构的研究对象数据结构的研究对象如何实现对弈如何实现对弈?各格局之间是什么关系？各格局之间是什么关系？.中南大学余腊生242023-2-6数据结构与算法（数据结构与算法（C版）版）说明说明通常这种关系不是线性的，即从一个棋盘格局可以派生

24、出几个格局通常这种关系不是线性的，即从一个棋盘格局可以派生出几个格局。这棵对奕树的。这棵对奕树的“树根树根”是对弈开始时的棋盘格局，而所有的是对弈开始时的棋盘格局，而所有的“叶子叶子”就是可能出现的结局，就是可能出现的结局，“树树”可以是某些非数值计算问题的数学模可以是某些非数值计算问题的数学模型，它也是一种数据结构。型，它也是一种数据结构。中南大学余腊生252023-2-6数据结构与算法（数据结构与算法（C版）版）例例3 田径赛的时间安排问题田径赛的时间安排问题图结构图结构1.2 数据结构的研究对象数据结构的研究对象如何表示项目之间的约束关系？如何表示项目之间的约束关系？中南大学余腊生262

25、023-2-6ABACADAEAFA安排竞赛项目的数据结构模型姓名项目1项目2项目3丁一跳高跳远马刚标枪铅球-张明标枪李远强铅球跳高王立跳远-参赛选手比赛项目表数据结构与算法（数据结构与算法（C版）版）例4多叉路口交通灯的管理问题 在多叉路口设置几种颜色的交通灯才能既使车辆相互不碰撞在多叉路口设置几种颜色的交通灯才能既使车辆相互不碰撞,又能达又能达到车辆的最大流通。到车辆的最大流通。假设有如下所示的五叉路口：假设有如下所示的五叉路口：B BA AE ED DC C中南大学余腊生272023-2-61.2 数据结构的研究对象数据结构的研究对象数据结构与算法（数据结构与算法（C版）版）说明：两条道

26、路之间有通路表示为：两条道路之间有通路表示为：XYXY两条通路有矛盾以图两条通路有矛盾以图中两个顶点连线表示，没有矛盾则可使用同一种信号灯。中两个顶点连线表示，没有矛盾则可使用同一种信号灯。通常通常这类交通、道路问题的数学模型是一种称谓这类交通、道路问题的数学模型是一种称谓“图图”的数据结构。的数据结构。设置交通灯问题等设置交通灯问题等价为对图的顶点染价为对图的顶点染色问题，要求对图色问题，要求对图上的每一顶点染一上的每一顶点染一种颜色，并且要求种颜色，并且要求有线相连的两个顶有线相连的两个顶点不能具有相同颜点不能具有相同颜色，而总的颜色种色，而总的颜色种类应尽可能少。类应尽可能少。中南大学余

27、腊生282023-2-61.2 数据结构的研究对象数据结构的研究对象数据结构与算法（数据结构与算法（C版）版）综上例子可见综上例子可见,描述这类非数值计算描述这类非数值计算问题的数学模型不采用数学方程，而问题的数学模型不采用数学方程，而是诸如表、树和图之类的数据结构。是诸如表、树和图之类的数据结构。因此数据结构是研究因此数据结构是研究非数值非数值问题中计问题中计算机的算机的操作对象操作对象以及它们之间的以及它们之间的关系关系和和操作操作的学科。的学科。中南大学余腊生292023-2-61.2 数据结构的研究对象数据结构的研究对象数据结构与算法（数据结构与算法（C版）版）1.3 数据结构的基本概

28、念数据结构的基本概念数据数据：所有能：所有能输入输入到计算机中并能被计算机程序到计算机中并能被计算机程序识别和处识别和处理理的符号集合。的符号集合。数值数据：整数、实数等数值数据：整数、实数等 非数值数据：图形、图象、声音、文字等非数值数据：图形、图象、声音、文字等 数据元素（实例）数据元素（实例）：数据的：数据的基本基本单位，在计算机程序中通单位，在计算机程序中通常作为一个常作为一个整体整体进行考虑和处理。进行考虑和处理。数据项数据项：构成数据元素的不可分割的最小单位。：构成数据元素的不可分割的最小单位。数据对象数据对象：具有相同：具有相同性质性质的数据元素的集合。的数据元素的集合。数据结构

29、的基本概念数据结构的基本概念中南大学余腊生302023-2-6数据结构与算法（数据结构与算法（C版）版）数据、数据元素、数据项之间的关系数据、数据元素、数据项之间的关系包含关系：数据是由数据元素组成，数据包含关系：数据是由数据元素组成，数据元素是由数据项组成。元素是由数据项组成。数据元素数据元素是讨论数据结构时涉及的最小数是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。据单位，其中的数据项一般不予考虑。1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生312023-2-6数据结构与算法（数据结构与算法（C版）版）数据结构数据结构：相互之间存在一定：相互之间存在一定关系关系

30、的数据元素的集合。的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据的逻辑结构是从具体问题抽象出来的数据的逻辑结构是从具体问题抽象出来的数据模型数据模型学籍管理问题中，表项之间的逻辑关系指的是什么？学籍管理问题中，表项之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？运动项目编排问题中，项目之间的逻辑关

31、系指的是什么？运动项目编排问题中，项目之间的逻辑关系指的是什么？中南大学余腊生322023-2-6数据结构与算法（数据结构与算法（C版）版）数据结构数据结构：相互之间存在一定：相互之间存在一定关系关系的数据元素的集合。的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。存储结构：又称为物理结构，是数据及其逻辑结构在存储结构：又称为物理结构，是数据及其逻辑结构在计算机计算机中的表示。中的表示。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数

32、据结构的基本概念存储结构实质上是内存分配，存储结构实质上是内存分配，在具体实现时，依赖于计算机语言。在具体实现时，依赖于计算机语言。中南大学余腊生332023-2-6数据结构与算法（数据结构与算法（C版）版）1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生342023-2-6数据结构与算法（数据结构与算法（C版）版）1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念逻辑结构逻辑结构描述性定义描述性定义：用自然语言描述相互之间存在一种或多种特定关系的数据元素的集合。形式化定义形式化定义：Data_Structure=（D，S）D=数据元素的有限集合S=D上

33、关系的有限集合中南大学余腊生352023-2-6数据结构与算法（数据结构与算法（C版）版）1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念逻辑结构逻辑结构中南大学余腊生362023-2-6数据结构与算法（数据结构与算法（C版）版）数据结构从逻辑上分为四类：数据结构从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生372023-2-6数据结构的基本概念数据结构的基本概念逻辑结构逻辑结构数据结构与算法（数据结构与算法（C版）版）数据结构从逻辑上分为四类：数据结构

34、从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生382023-2-6数据结构的基本概念数据结构的基本概念逻辑结构逻辑结构数据结构与算法（数据结构与算法（C版）版）数据结构从逻辑上分为四类：数据结构从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；树结构：数

35、据元素之间存在树结构：数据元素之间存在 着一对多的层次关系；着一对多的层次关系；1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生392023-2-6数据结构的基本概念数据结构的基本概念逻辑结构逻辑结构数据结构与算法（数据结构与算法（C版）版）数据结构从逻辑上分为四类：数据结构从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；树结构：数据元素之间存在树结构：数据元素之间存在 着一对多的层次关系；着一对多的层次关系；图结构：数据元素之间存在图结构：

36、数据元素之间存在 着多对多的任意关系。着多对多的任意关系。1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生402023-2-6数据结构的基本概念数据结构的基本概念逻辑结构逻辑结构数据结构与算法（数据结构与算法（C版）版）1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念存储结构存储结构描述方式描述方式：*数据元素数据元素用高级语言中的“数据类型”来描述数据元素间的关系数据元素间的关系用数据元素间的存储相对位置关系(顺序存储结构)或在数据元素上增加指针(链式存储结构)来表达数据的存储结构是逻辑结构用计算机语言的实现；数据的存储结构是逻辑结构用计算机语言的实

37、现；数据的存储结构依赖于计算机语言数据的存储结构依赖于计算机语言 顺序存储表示顺序存储表示 链接存储表示链接存储表示 索引存储表示索引存储表示 散列存储表示散列存储表示主要用于内存的存储表示主要用于内存的存储表示主要用于外存主要用于外存(文件文件)的存储表示的存储表示中南大学余腊生412023-2-6数据结构与算法（数据结构与算法（C版）版）通常有两种存储结构：通常有两种存储结构：1.顺序存储结构：用一组顺序存储结构：用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元数据元素之间的逻辑关系由元素的素的存储位置存储位置来表示。来表示。batcatea

38、t起始地址起始地址例：（例：（bat,cat,eat）1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生422023-2-6数据结构的基本概念数据结构的基本概念存储结构存储结构数据结构与算法（数据结构与算法（C版）版）1.顺序存储结构：用一组顺序存储结构：用一组连续连续的存储单元的存储单元依次依次存储存储数据元素，数据元素之间数据元素，数据元素之间的逻辑关系由元素的的逻辑关系由元素的存储存储位置位置来表示。来表示。2.链接存储结构：用一组链接存储结构：用一组任意任意的存储单元存储数据的存储单元存储数据元素，数据元素之间的逻元素，数据元素之间的逻辑关系用辑关系用指针指针来表示来表示。例：

39、（例：（bat,cat,eat）1.3 数据结构的基本概念数据结构的基本概念0200020803000325 bat0200 cat0325 eat 中南大学余腊生432023-2-6数据结构的基本概念数据结构的基本概念存储结构存储结构数据结构与算法（数据结构与算法（C版）版）逻辑结构和存储结构之间的关系逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，是数据的逻辑结构属于用户视图，是面向问题面向问题的，反映了数据内部的构成方式；数据的存储的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是结构属于具体实现的视图，是面向计算机面向计算机的。的。一种数据的逻辑结构可以用多种

40、存储结构来一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的存储，而采用不同的存储结构，其数据处理的效率往往是不同的。效率往往是不同的。1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生442023-2-6数据结构与算法（数据结构与算法（C版）版）数据结构的访问接口数据结构的访问接口 对数据结构的对数据结构的访问访问是指对数据的读取、修改、是指对数据的读取、修改、加工、处理等操作。加工、处理等操作。数据结构的数据结构的基本操作基本操作：各种应用都能通过这些：各种应用都能通过这些操作实现对数据结构的各种访问。操作实现对数据结构的各种访问。基本操作的特性：抽象性

41、、基本性、完备性、一般性基本操作的特性：抽象性、基本性、完备性、一般性 访问接口访问接口：操作的调用形式与规范（例如形参：操作的调用形式与规范（例如形参表、返回类型等）。表、返回类型等）。数据结构的访问接口数据结构的访问接口：数据结构基本操作接口：数据结构基本操作接口的全体。的全体。1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生452023-2-6数据结构与算法（数据结构与算法（C版）版）抽象数据类型抽象数据类型1.数据类型数据类型（Data Type）：一组）：一组值值的集合以及定义的集合以及定义于这个值集上的一组于这个值集上的一组操作操作的总称。的总称。例如：例如：C+中的整型

42、变量中的整型变量分类：分类：*原子类型原子类型：值不可分解，如整型、指针类型等。*结构类型结构类型：值由若干成分按照某种结构组成，如数组、结构（记录）等。1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生462023-2-6数据结构与算法（数据结构与算法（C版）版）47n数据类型就是数据结构，不过它是从编程数据类型就是数据结构，不过它是从编程者的角度来使用的。者的角度来使用的。n数据类型是模板，必须定义属于某种数据数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。类型的变量，才能参加运算。数据结构与算法（数据结构与算法（C版）版）抽象数据类型抽象数据类型2.抽象抽象（Abs

43、tract）:抽出问题本质的特征而忽略非本质的细抽出问题本质的特征而忽略非本质的细节。节。例如：例如：地图、驾驶汽车地图、驾驶汽车3.抽象数据类型抽象数据类型（Abstract Data Type，ADT）:一个一个数据结构数据结构以及定义在该结构上的以及定义在该结构上的一组操作一组操作的总称。的总称。ADT比数据类型的范畴更广，除了具有固有数据类型的特性之外，还包比数据类型的范畴更广，除了具有固有数据类型的特性之外，还包括用户在设计软件系统时自己定义的数据类型。括用户在设计软件系统时自己定义的数据类型。由用户定义，用以表示应用问题的数据模型由用户定义，用以表示应用问题的数据模型由基本的数据类

44、型组成由基本的数据类型组成,并包括一组相关的服务（或称操作）并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离信息隐蔽和数据封装，使用与实现相分离1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生482023-2-6数据结构与算法（数据结构与算法（C版）版）49抽抽象象数数据据类类型型查找查找 登录登录 删除删除 修改修改 符符 号号 表表数据结构与算法（数据结构与算法（C版）版）ADT是对数据类型的进一步抽象是对数据类型的进一步抽象 ADT逻辑结构逻辑结构操作集合操作集合数据结构数据结构存储结构存储结构算法设计算法设计类类成员变量成员变量成员函数成员函数(a)使用视

45、图使用视图 (b)设计视图设计视图 (c)实现视图实现视图ADT的定义的定义 ADT的设计的设计 ADT的实现的实现 ADT的不同视图的不同视图1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生502023-2-6数据结构与算法（数据结构与算法（C版）版）ADT 抽象数据类型名抽象数据类型名Data 数据元素及数据元素之间逻辑关系的定义数据元素及数据元素之间逻辑关系的定义Operation 操作操作1 前置条件前置条件：执行此操作前数据所必须的状态：执行此操作前数据所必须的状态 输输 入入：执行此操作所需要的输入：执行此操作所需要的输入 功功 能能：该操作将完成的功能：该操作将完成的功

46、能 输输 出出：执行该操作后产生的输出：执行该操作后产生的输出 后置条件后置条件：执行该操作后数据的状态：执行该操作后数据的状态 操作操作2 操作操作n endADT ADT的定义形式的定义形式1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生512023-2-6数据结构与算法（数据结构与算法（C版）版）ADT Triplet 数据对象：D=e1,e2,e3|e1,e2,e3属于ElemSet 数据关系：R=,基本操作：InitTriplet(&T,v1,v2,v3)DestroyTriplet(&T)Get(T,i,&e)Put(&T,i,e)ADT Triplet ADT的定义示例

47、的定义示例1.3 数据结构的基本概念数据结构的基本概念中南大学余腊生522023-2-6数据结构与算法（数据结构与算法（C版）版）1.3 1.3 数据结构的基本概念数据结构的基本概念抽象数据类型分类分类标准：按照值的不同特性分类标准：按照值的不同特性 原子类型原子类型：变量的值不可分解 固定聚合类型固定聚合类型：变量的值成分的数目确定 可变聚合类型可变聚合类型：变量的值成分的数目不确定 多形数据类型多形数据类型：变量的值成分不确定（成分类型可变）抽象数据类型表示与实现抽象数据类型表示与实现抽象数据类型通过固有数据类型来抽象数据类型表示与实现抽象数据类型通过固有数据类型来表示和实现。即利用处理器

48、中已存在的数据类型来说明新的结构，表示和实现。即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。用已经实现的操作来组合新的操作。C+语言的描述语法使用使用C+语言的一个核心子集。如：存储结构用语言的一个核心子集。如：存储结构用typedef；数据元素类型约定为数据元素类型约定为ElemType；在形参表中，以在形参表中，以&打头的参数打头的参数为引用参数；等等。为引用参数；等等。中南大学余腊生532023-2-6数据结构与算法（数据结构与算法（C版）版）1.3 1.3 数据结构的基本概念（小结）数据结构的基本概念（小结）数据的操作：插入、删除、修改、检索、排序等数据

49、的操作：插入、删除、修改、检索、排序等 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 顺序存储顺序存储链式存储链式存储集合集合线性结构线性结构树结构树结构图结构图结构 非数值问题非数值问题 数数据据表表示示中南大学余腊生542023-2-6数据结构与算法（数据结构与算法（C版）版）1.算法算法（Algorithm）:是对是对特定问题特定问题求解步骤的一种描述，求解步骤的一种描述，是是指令指令的的有限序列有限序列。2.算法的五大特性：算法的五大特性：输入输入：一个算法有零个或多个输入。：一个算法有零个或多个输入。输出输出：一个算法有一个或多个输出。：一个算法有一个或多个输出。有穷性

50、有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。有穷时间内完成。确定性确定性：算法中的每一条指令必须有确切的含义，对于相同的输入：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。只能得到相同的输出。可行性可行性：算法描述的操作可以通过已经实现的基本操作执行有限次：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。来实现。中南大学余腊生552023-2-6数据结构与算法（数据结构与算法（C版）版）1、正确性、正确性Correctness：在给定有效的输入数据后，算法：在给定有效的输入数据后