数据结构：第1章 绪论

1、说明：1、本课程的先修课程是程序设计和离散数学 2、本课程是操作系统和数据库的基础数据结构数据结构讨论的范畴基本概念 算法及性能分析第一章 绪论1.1 数据结构讨论的范畴非数值计算型问题算法+数据结构=程序程序：为计算机处理问题编制的一组指令集。算法：处理问题的策略。数据结构：待处理问题的数学模型，或者说信息是如何表示的。数值计算型问题解一元二次方程 ax2+bx+c=0桥梁设计中结构应力分析数学模型为线性代数方程组预报人口增长情况数学模型为微分方程然而，更多的非数值计算问题无法用数学方程加以描述。非数值计算型问题图书档案 在书目检索系统中可以建立一张按登录号顺序排列的书目文件。 登陆号 书名

2、 作者 分类号 001 高等数学 樊映川 S01 002 理论力学 罗远祥 L01 003 高等数学 华罗庚 S01 004 线形代数 栾汝书 S02 算法：需要管理的项目、如何管理、与用户的接口数学模型：表格，数据库人机对弈树算法：对弈的规则和策略数学模型(数据结构)：棋盘、棋子的表示方法。多叉路口交通灯管理问题图ABACADBABCBDDADBDCEAEBECEDCEDAB算法：管理路口图的着色数据模型：路口图数值计算型计算数学非数值计算型数据结构概括的说：数据结构是描述现实世界实体（非数值计算问题）的数学模型，及其上的操作。即现实世界实体在计算机中的表示和操作。数据（data）数据是所有

3、能输入到计算机中，被计算机程序识别和处理的符号的集合。 随着技术的发展，数据的内容在不断扩大。（数值音频等）1.2 数据结构的基本概念 数据元素 (data element)是数据(集合)中的一个个体，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的基本单位。有时一个数据元素可以由若干数据项(Data Item)组成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录。如：每本书的信息、棋盘中每个格局数据数据元素数据项实数集单个实数单个实数复数集单个复数实部、虚部学生信息单个学生记录姓名、性别、班级数据对象 (data object)数据对象是具有相同性质的数据元素

4、的集合。整数数据对象 N = 0, 1, 2, 如:学生档案组成一个数据对象 棋所有格局构成一个数据对象数 据 结 构定义: 是相互之间存在一种或多种特定关系的数据元素的集合。（带结构的数据元素集合）数据结构的形式定义为一个二元组 Data_Structure = D, S 其中，D 是数据元素的有限集， S是D上关系的有限集。例如：含有12位数的十进制数用三个4位的十进制表示：1234 5678 9012 a1=1234 a2=5678 a3=9012 a1、a2、a3存在次序关系 数据结构主要研究三方面内容：数据元素间的逻辑关系，即数据的逻辑结构；数据元素及其关系在计算机存储内的表示，即数

5、据的存储结构；数据的运算，即对数据元素施加的操作。数据的逻辑结构逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示；D=a1，a2， a3，a4， a5，a6 2行3列的数组可以表示为row= ， ， col= ， 一维数组可以表示为S= | i=1，2，3，4，5不同的关系构成不同的结构线性结构树形结构a1a2a3a4 a5101413121123456789110125643图结构集合数据的存储结构 数据元素及其关系在计算机存储器内的表示 数据元素的映像方法：在计算机中，我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素。例如（3

6、0）10 =（36）8 =（00111000）2关系的映像方法：所有的关系都可以用有序对 ()表示。有序对 ()在计算机中有两种表示方法：1、顺序映像 借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。2、链式映像 借助指示元素存储地址的指针(Pointer)表示数据元素之间的逻辑关系。a1 a2 a3 a4 a5 a6 1 2 3 4 5 6a0a1a2a3a4数据的逻辑结构与数据的存储结构之间的关系 同一种逻辑结构可以映象成不同的存储结构数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据(逻辑)结构，而算法的实现依赖于采用的存储结构。抽象数据类型（ab

7、stract data type,简称ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型可以用三元组表示： （D，S，P)其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本运算：基本运算的定义 ADT抽象数据类型名复数的抽样数据类型ADT Complex 数据对象：D = e1,e2 | e1,e2 RealSet 数据关系：R1 = | e1是复数的实部，e2是复数的虚部 基本操作：InitComplex( &Z, v1, v2 )操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2

8、的值。 DestroyComplex( &Z)初始条件：复数已存在。操作结果：复数Z被销毁。GetReal( Z, &realPart )初始条件：复数已存在。操作结果：用 realPart 返回复数Z的实部值。 GetImag( Z, &ImagPart )初始条件：复数已存在。操作结果：用 ImagPart 返回复数Z的虚部值。 Add( z1,z2, &sum )初始条件：z1，z2 是复数。操作结果：用sum返回两个复数z1，z2的和值。 ADT Complex1.3 算法及性能分析定义：是对特定问题求解步骤的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。特性：(

9、1)有穷性 一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成； (2)确定性 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 (3)可行性 一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 (4)输入 一个算法有零个或多个的输入。 (5)输出 一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。算法设计的要求(1)正确性 算法应当满足具体问题的需求。 “正确”一词的含义在通常的用法中有很大差别，大体可分为以

10、下四个层次： a. 程序不含语法错误； b. 程序对于几组输入数据能够得出满足规格说明要求的结果； c. 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果； d. 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。 (2) 可读性 可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误难以调试和修改。(3) 健壮性 当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。(4) 效率与低存储量需求 通俗地说，效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行过程中

11、所需要的最大存储空间。效率与低存储量需求这两者都与问题的规模有关。 算法与程序算法是独立于具体的计算机 与具体的程序设计语言 程序是利用具体的计算机语言 来描述算法算法效率的度量 算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法： (1)事后统计的方法。 因为很多计算机内部都有计时功能，不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。但这种方法有两个缺陷： 一、必须先运行依据算法编制的程序； 二、所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用另一种事前分析估算的方法。(2

12、)事前分析估算的方法。 一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素： a依据的算法选用何种策略； b问题的规模，例如求100以内还是1000以内的素数； c书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率就越低； d编译程序所产生的机器代码的质量； e机器执行指令的速度。 一个算法是由控制结构(顺序、分支和循环三种)和原操作(指固有数据类型的操作)构成的，则算法时间取决于两者的综合效果。 为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 这种

13、衡量效率的办法所得出的不是时间量，而是一种增长趋势的度量。它与软硬件环境无关，只暴露算法本身执行效率的优劣。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作 T(n)=O(f(n) 它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。 显然，被称作问题的基本操作的原操作应是，重复执行次数和算法的执行时间成正比的原操作，多数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。 语句的频度指的是该语句重复执行的次数，例如：在下列三个程序段中， (a) +x； s = 0

14、； (b) for (i = 1；i=n；+i) + x； s + = x； (c) for (i = 1；i=n；+i) for (k = 1；k=n；+k) + x；s + = x； 含基本操作“x增1”的语句的频度分别为1，n和n2，则这三个程序段的时间复杂度分别为O(1)，O(n)和O(n2)，分别称为常量阶、线性阶和平方阶。算法还可能呈现的时间复杂度有：对数阶O(1og n)，指数阶O(2n)等。 在如下所示的两个NN矩阵相乘的算法中， for(i = 1；i = n；+i) for(j = 1；j = n；+j) cij = 0； for(k = 1；k = n；+k) cij +

15、 = aik * bki “乘法”运算是“矩阵相乘问题”的基本操作。整个算法的执行时间与该基本操作(乘法)重复执行的次数 n3 成正比，记作T(n) = O(n3)。 一般情况下，对一个问题(或类算法)只需选择一种基本操作来讨论算法的时间复杂度即可。 由于算法的时间复杂度考虑的只是对于问题规模n的增长率，则在难以精确计算基本操作执行次数(或语句频度)的情况下，只需求出它关于n的增长率或阶即可。例如，在下列程序段中 for (i = 2；i=n；+i) for (j = 1；j=i-1；+j) + x；aij = x； 语句+x的执行次数关于n的增长率为n2，它是语句频度表达式(n-1)(n-2

16、)2中增长最快的项。设 n 为正整数。试确定下列各程序段中前置以记号 的语句的频度 i=1; k=0;while ( i=n-1) k += 10 * i; i+;n-1 i=1; k=0;do k +=10 * i; i+; while(i=n-1); n-1,但n=1时特殊,是1次算法的存储空间需求 一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。 通常，只有完成同一功能的几个算法之间才具有可比性，

17、因此这些输入数据所占用的空间不用进行比较，因此只需比较那些辅助的或附加的存储空间。 类似于算法的时间复杂度，一般我们以空间复杂度作为算法所需存储空间的量度，记作 S(n) = O(g(n) 表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。本 章 小 结数据组织的三个层次：数据、数据元素和数据项数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。数据结构的研究目的和研究内容 目的：寻求有效地组织和处理非数值数据的理论、技术和方法。这类数据具有量大且具有一定内在逻辑关系的特点。 内容：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。逻辑结构的四种基本形态 （1）集合结构：数据元素之间除了“属于同一集合”的联系之外，没有其他关系。 （2）线性结构：数据元素之间存在一对一的关系。 （3）树形结构：数据元素之间存在一个对多个的关系。 （4）图状(网状)结构：数据元素之间存在多对多的关系。数据存储结构的基本组织方式