数据结构第1章数据结构.ppt

教材： 安训国 刘俞主编，数据结构（第三版)， 大连理工大学出版社，2007年 数数 据据 结结 构构 1 1 2 2 数据结构课程的地位数据结构课程的地位 它是计算机专业及相关专业的核心课 程之一，是计算机及相关专业的重要骨干 基础课程。 它针对非数值计算的程序设计问题， 研究计算机的操作对象以及它们之间的关 系和操作。即其研究目的是研究有效地组 织和处理非数值类型数据的理论、技术和 方法。 3 3 数据结构的核心研究内容数据结构的核心研究内容 数据的逻辑结构、存储结构及它们之 间的关系和相应的基本操作运算的定义和 实现。 本书围绕数据结构的三种基本结构： 线性结构、树形结构和图形结构展开讨论 ，研究解决如下问题：一个具体问题的逻 辑数据结构是什么？适宜选用什么样的存 储结构？采用什么样的操作实现算法效率 更高？ 4 4 1、上课认真听讲，适当做好笔记，按时交 作业。 2、考试成绩分两部分：平时成绩（包括出 勤和上机实验）占40%，期末成绩占60% 。 3、课后需要多读课文和参考书，上网查看 相关内容，在理解基本内容的基础上， 多看、多做习题。 4、上机实验十分重要，一定要在上机前做 好充分准备，多采用不同的数据存储结 构和不同的实现算法解决一个问题。 对学生的几点要求对学生的几点要求 5 5 第1章 绪 论 讨论5个问题： 1.1 数据结构 的基本概念 1.2 学习数据 结构的意义 1.3 数据结构 涵盖的主要内 容 1.4 算法效率 的度量 6 6 1.1 数据结构的基本概念 1、举例 建立一个学生档案。学生表包括 学号、姓名、性别、籍贯。要求： 查找“王红”是否存在。 解决的方法步骤： 如 何记录所有学生记录 （及选择何种逻辑数 据结构）？ 选 择何种存储结构？ v若 把所有记录依次存 储在一个数组中 采用顺序存储结 构 v若 采用指针链表 采用链式存储结构 7 7 2、基本术语 (1)数据：所有能被计算机识别、存储和处 理的符号的集合（包括数字、字符、声音 、图像等信息 ）。 (2)数据元素:是数据的基本单位，具有完整 确定的实际意义。在计算机程序中通常作 为一个整体进行考虑和处理。一个数据元 素可由若干个数据项组成。 (3)数据项:构成数据元素的项目。它是数据 不可分割的最小单位。 (4)数据类型：指一个类型和定义在这个类 型上的操作集合。例：C语言（基本类型 ：整型、浮点型、字符型等构造类型：数 组、结构、联合、指针、枚举等） (5)抽象数据元素：抽象定义的、没有实际 含义的数据元素。 (6)抽象数据类型：用户自己定义的数据类 型。 8 8 2、基本术语 (续） (7)数据结构：是相互之间存在一种或多种特定关系的数据元素 的集合。或按照一定逻辑关系组织，并按一定存储方法存储 的数据的集合，且需要定义一系列运算。逻辑结构、存储结 构和运算合称为三要素。表示为： Data_Structure=（D, R） 其中，D元素有限集，R关系有限集 9 9 程序设计好算法好结构程序设计好算法好结构 同样的数据对象，用不同的数据结构来表 示，运算效率可能有明显的差异。 1.2 学习数据结构的意义 计算机内的数值运算依靠方程式，而非数值运算（如 表、树、图等）则要依靠数据结构。 数据结构是一门学科，针对非数值计算的程序设计问 题，研究计算机的操作对象以及它们之间的关系和操作 等等。 1010 1.3 数据结构涵盖的内容 1111 集合结构： 仅同属一个集合 线性结构: 一对一（1:1) 树 结 构: 一对多（1:n) 图 结 构: 多对多 (m:n) 非线性 线 性 逻辑结构可细分为4类： 指数据元素之间的逻辑关系。即从逻辑关系上描述数据 ，它与数据的存储无关，是独立于计算机的。 解释1： 什么叫数据的逻辑结构？ 1212 （1） S=(D, R) D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d) 解： 上述表达式可用图形表示为： b c a e f d 此结构为线性的。 例：用图形表示下列数据结构，并指出它们是属于线 性结构还是非线性结构。 1313 d1 d5 d2 d4 d3 该结构是非线性的。 解：上述表达式可用图形表示为： （2） S=(D, R) D=di | 1i5 R=(di , dj ), ij 1414 物理结构亦称存储结构，是数据的 逻辑结构在计算机存储器内的表示（ 或映像）。它依赖于计算机。 存储结构可分为4大类： 例：复数3.02.3i 的两种存储方式： 顺序、链式、索引、散列 2.30302 3.00300 04150302 3.00300 0415 2.3 法1：地址 内容法2：地址 内容 2字节 解释2：什么叫数据的物理结构？ 1515 在数据的逻辑结构上定义的操作 算法。 它在数据的存储结构上实现。 最常用的数据运算有 5 种： 插入、删除、修改、查找、排序 解释3：什么是数据的运算？ 1616 1.4 算法效率的度量 1 什么是算法？如何评判算法的好 坏？ 2 时间复杂度和空间复杂度如何表 示？ 3 计算举例 讨论： 1717 1 什么是算法？如何评判一个算法的好坏？ 常用时间复杂度来衡量 算法的基本特性： 算法评价指标： 有穷性、确定性、可行性、必有输出 正确性、可读性、健壮性、高效率与低存储量需求 常用空间复杂度来衡量 好的程序设计：好算法好结构 算法：是对特定问题求解步骤的一种描述，它是指令 的有限序列，是一系列输入转换为输出的计算步骤。 1818 注： 1） O（）为渐近符号。 2） 空间复杂度S(n)按数量级递增顺序也与上表类似。 复杂度高复杂度低 时间复杂度T(n)按数量级递增顺序为： 2 时间复杂度和空间复杂度如何表示？ 多项式阶 1919 3n+2=O(n) 因为 3n+24n for n2 6*2n+n2=O(2n) 因为6*2n+n2 7*2n for n4 例： 渐进符号（O）的定义：当且仅当存在一个正的常 数 C，使得对所有的 n n0 ，有 f(n) Cg(n) ，则： f(n) = O(g(n) 2020 该算法的运行时间由程序中所有语句的频度（即该语 句重复执行的次数）之和构成。 解 ： 分析：显然，语句的频度是1。设语句2的频度是f(n)，则有： 算法的时间复杂度由嵌套最深层语句的频度决定 例：分析以下程序段的时间复杂度。 i=1; while(i=n) i=i*2; 即f(n)log2n，取最大值f(n)=log2n 所以该程序段的时间复杂度T(n)=1+f(n)=1+ log2n= O( log2n) 3 计算举例 2121 该算法的运行时间由程序中所有语句的频度（即该语 句重复执行的次数）之和构成。 解 ： 例：分析以下程序段的时间复杂度。 i=1; k=0; while(in) k=k+10*i;i+; 即f(n)log2n，取最大值f(n)=log2n 所以该程序段的时间复杂度T(n)=1+f(n)=1+ log2n= O( log2n) 3 计算举例 2222 T(n)=1+1+n+(n-1)+(n-1)=3n 可表示为T(n)=O(n) 3 分析 i=1; /1 k=0; /1 while(in) /n k=k+10*i; /n-1 i+; /n-1 2323 本章小结 数据结构课程 数据结构算法 程序，涉及数学、计算机硬件 和软件。 数据结构定