数据结构第1章数据结构

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