南京大学：《数据结构 Data Structures》课程教学资源（PPT课件讲稿）Chapter 1 基本概念和算法分析

DATA STRUCTURES Chapter l基本概念和算法分析 什么是数据结构 抽象数据类型及面向对象概念 模板 算法定义 算法性能分析与度量 Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES ◼ 什么是数据结构 ◼ 抽象数据类型及面向对象概念 ◼ 模板 ◼ 算法定义 ◼ 算法性能分析与度量 Chapter 1 基本概念和算法分析

DATA SIRUCTURES 1.1什么是数据结构 数据:数据是信息的载体,是描述客观事物的 数、字符、以及所有能输入到计算机中并被计 算机程序识别和处理的符号的集合。P2 数值数据,非数值性数据 数据对象:数据的子集。具有相同性质的数据 成员(数据元素)的集合。 整数数据对象N={0,1,2,} 学生数据对象 Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 1.1 什么是数据结构 ◼ 数据：数据是信息的载体，是描述客观事物的 数、字符、以及所有能输入到计算机中并被计 算机程序识别和处理的符号的集合。P.2 ——数值数据, 非数值性数据 ◼ 数据对象：数据的子集。具有相同性质的数据 成员（数据元素）的集合。 ——整数数据对象 N = { 0, 1, 2, … } ——学生数据对象

DATA SIRUCTURES 什么是数据结构? 定义:由某一数据对象及该对象中所有数 据成员之间的关系组成。记为: Data Structure=D, Ri 其中,D是某一数据对象,R是该对象 中所有数据成员之间的关系的有限集合 Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 什么是数据结构？ 定义: 由某一数据对象及该对象中所有数 据成员之间的关系组成。记为： Data_Structure = {D, R} 其中，D是某一数据对象，R是该对象 中所有数据成员之间的关系的有限集合

DATA SIRUCTURES 如 n个网站之间的连通关系 树形关系 网状关系 复数的数据结构定义如下: Complex=(c, r) C是包含两个实数的集合【C1,C2} R={P},P是定义在集合上的一种关系 {(C1,C2)} ( Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 如： • n个网站之间的连通关系 树形关系 网状关系 1 5 2 6 4 3 1 5 2 6 4 3 • 复数的数据结构定义如下： Complex=(C，R) C是包含两个实数的集合﹛C1，C2} R={P}，P是定义在集合上的一种关系 {〈C1，C2〉}

DATA SIRUCTURES 数据结构是数据的组织形式 包括三个方面: 数据元素间的逻辑关系,即数据的逻辑结构; 数据元素及其关系在计算机存储内的表示,即数 据的存储表示; 数据的运算,即对数据元素施加的操作。 Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 数据结构是数据的组织形式 ◼ 包括三个方面： ◆ 数据元素间的逻辑关系，即数据的逻辑结构； ◆ 数据元素及其关系在计算机存储内的表示，即数 据的存储表示； ◆ 数据的运算，即对数据元素施加的操作

DATA SIRUCTURE 相关 逻辑结构 物理结构 相关操作 实现 Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 相关： • 逻辑结构 • 物理结构 • 相关操作 • 实现

DATA SIRUCTURES 数据的逻辑结构 数据的逻辑结构从逻辑关系上描述数据,与数据 的存储无关; 数据的逻辑结构可以看作是从具体问题抽象出来 的数据模型; 数据的逻辑结构与数据元素本身的形式、内容无 关 数据的逻辑结构与数据元素的相对存储位置无关。 Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 数据的逻辑结构 ◼ 数据的逻辑结构从逻辑关系上描述数据，与数据 的存储无关； ◼ 数据的逻辑结构可以看作是从具体问题抽象出来 的数据模型； ◼ 数据的逻辑结构与数据元素本身的形式、内容无 关； ◼ 数据的逻辑结构与数据元素的相对存储位置无关

DATA SIRUCTURE 数据的逻辑结构分类 ■线性结构 线性表 非线性结构 ◆树 图(或网络) Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 数据的逻辑结构分类 ◼ 线性结构 ◆ 线性表 ◼ 非线性结构 ◆ 树 ◆ 图（或网络）

DATA SIRUCTURES 线性结构 dev( lib user Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 线性结构 bin dev etc lib user

DATA SIRUCTURES 树形结构 树 二叉树 二孓拽案树 9 (3 3 5)(6 8)(9)10 (5 12314⑦8 9 ④(⑦⑩ Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 树形结构 树 二叉树 二叉搜索树 11 12 13 14 2 3 4 5 6 7 8 9 10 3 1 5 8 7 10 11 9 7 8 9 4 5 6 2 3 6 13 1 1