第1章绪论(修订).ppt

1、数 据 结 构,教师：代文征 电话2,课程安排,学时分配：共80学时，其中理论课68学时，上机12学时。本科 学时分配：共60学时，其中理论课50学时，上机10学时。专科 课程设计,3,参考书： 1李春葆.数据结构（C语言版）.清华大学出版社 2 许卓群等. 数据结构与算法.高等教育出版社 3 薛超英.数据结构（第二版）.华中科技大学出版社,4,内 容 安 排,5,数据结构课程的地位,针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。 是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,关系,对象 关系 操作,对象 关系 操作,6,第

2、1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组与矩阵 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序,目 录,7,第1章绪论,1.1 数据结构基本概念 1.2 数据结构研究的主要内容 1.3 算法和算法分析,8,数据所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。 数据元素是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。 数据项构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。,三者之间的关系：数据 数据元素 数据项,例：班级通讯录 个人记录 姓名、年龄,1.1 数据结构

3、基本概念,9,例、学生健康情况登记表如下：,10,数据结构定义：,按照某种逻辑关系组织起来的一批数据（数据元素），将其按照某种存储方式存储到计算机中，并对其施加一定的运算（操作）的描述。,是指同一数据元素类型中各元素之间存在的关系。,元素有限集,关系有限集,Data_Structure=（D, R）,11,1.2 数据结构研究的内容,12,集合结构： 仅同属一个集合 线性结构: 一对一（1:1) 树 结 构: 一对多（1:n) 图 结 构: 多对多 (m:n),非线性,线 性,逻辑结构可细分为4类：,逻辑结构指数据元素之间的逻辑关系。即从逻辑关系上描述数据。,A 、数据的逻辑结构,注意：它与数

4、据的存储无关，是独立于计算机的。,逻辑关系：前驱，后继,13,线性结构,树形结构,树 二叉树 二叉搜索树,14,13,12,11,2,3,4,5,6,7,8,9,10,3,1,5,8,7,10,11,9,9,8,7,4,5,6,6,2,3,13,1,bin,dev,etc,lib,user,1,14,图结构 网络结构,1,2,5,6,4,3,1,2,5,4,3,6,11,33,18,14,6,6,5,16,19,21,15,（1） S=(D, R) D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d),解： 上述表达式可用图形表示为：,

5、b c a e f d,此结构为线性的。,例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。,描述方式：1.图形表示法，2.数学符号法,描述数据结构,16,d1 d5 d2 d4 d3,该结构是非线性的。,解：上述表达式可用图形表示为：,（2） S=(D, R) D=di | 1i5 R=(di , dj ), ij,17,物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。,有2种基本存储方法：,顺序、链式,B、数据的物理结构,它依赖于计算机。,顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。 顺序存储

6、结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。,18,链式存储方法对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示，由此得到的存储表示称为链式存储结构。 链式存储结构通常借助于程序设计语言中的指针类型来实现。,19,在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。,最常用的数据运算有 5 种：,插入、删除、修改、查找、排序,C、数据的运算,数据结构的三个研究内容之间具有一定关系：数据逻辑结构独立于存贮结构，数据的存贮结构是数据胡逻辑结构在计算机中的实现，而数据的运算定义于逻辑结构实现于存贮结构。,20,算法是执行特定计算的有穷

7、过程。 算法有五个特点： 1. 有穷性 2.确定性 3.输入 4.输出 5.可行性,1.3 算法与算法分析,21,常用时间复杂度来衡量,算法评价指标：,正确性、可读性、健壮性、高效率与低存储量,常用空间复杂度来衡量,算法分析：,22,时间复杂度,一般情况下，算法中基本操作重复执行 的时间是问题规模n的某个函数f(n)，算法的时间量度记作：T(n) = O(f(n)，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。,算法的时空效率性,23,怎样计算某算法的时间复杂度？,1.选取语句频度最大的语句作为基本语句； 2.计算其在数据输入规

8、模n的情况下的语句频度f(n)； 3.计算T(n)=O(f(n),24,例1:循环次数间接依赖规模n,x=1; for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) x+;,该算法段中频度最大的语句是x+; 内层循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的直接次数直接与n有关。因此可以从内层向外逐层计算语句x+的频度：f(n) = (n(n+1)(2n+1)/6 + n(n+1)/2)/2 T(n)=O(n3)。,25,空间复杂度,（1）存储算法本身所占用的空间 （2）算法的输入/输出数据占用的空间 （3）算法在运行过程中临时占用的辅助空间,26,空间复杂度S(n)按数量级递增顺序也与上表类似。,复杂度高,复杂度低,时间复杂