中国计量学院数据结构第1章 绪论

1、数据结构数据结构信息工程学院曾宪庭课时安排：讲授40学时上机24学时考核平时及实验30%，期末考试70%教材：数据结构 严蔚敏 清华大学出版社参考书：数据结构 唐策善 高等教育出版社1 绪论绪论1.1 什么是数据结构什么是数据结构1.2 基本概念和术语基本概念和术语1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1.4 算法和算法分析算法和算法分析31.1 什么是数据结构什么是数据结构u是计算机存储、组织数据的方式是计算机存储、组织数据的方式精心选择的数据结构可以带来更高的运精心选择的数据结构可以带来更高的运行效率或者存储效率行效率或者存储效率u由若干数据元素依据某种关系组织由若干数据

2、元素依据某种关系组织起来起来41.2 基本概念和术语基本概念和术语u数据数据l数据元素数据元素数据的基本单位，数据中的一个数据的基本单位，数据中的一个“个体个体”由若干个由若干个数据项数据项组成组成l数据对象数据对象性质相同的数据元素的集合性质相同的数据元素的集合u结构结构数据元素之间的关系数据元素之间的关系5u逻辑结构逻辑结构对数据元素间逻辑关系的描述对数据元素间逻辑关系的描述u物理结构物理结构数据结构在计算机中的实现，又称数据结构在计算机中的实现，又称存储结构存储结构u如无特殊说明，一般所说的数据结构，如无特殊说明，一般所说的数据结构，是指逻辑结构是指逻辑结构u算法的设计取决于数据结构，而

3、算法的算法的设计取决于数据结构，而算法的实现依赖于采用的存储结构实现依赖于采用的存储结构67数据结构数据结构可归结为以下四类四类: :线性线性结构树形树形结构图图/ /网状网状结构集合集合结构数据结构的形式定义数据结构的形式定义u二元组二元组uData_Structures = (D, S)u其中: D 是数据元素的有限集数据元素的有限集，u S 是 D上关系的有限集关系的有限集8数据结构的形式定义数据结构的形式定义复数复数9 C C是含两个实数的集合：是含两个实数的集合： C Cc1,c2c1,c2RealSet R R是定义在集合是定义在集合C C上的关系的集合：上的关系的集合： R |

4、c1是复数的实部 | c2 是复数的虚部 Complex = ( C, R )u数据类型数据类型描述操作对象的特性描述操作对象的特性C语言：语言：int char float double u抽象数据类型抽象数据类型Abstract Data Type (ADT)一个数学模型及定义在该模型上的一组操作一个数学模型及定义在该模型上的一组操作10u抽象数据类型抽象数据类型实际上就是对某种数据结构的定义实际上就是对某种数据结构的定义 它定义了一个数据的逻辑结构以及在此结构它定义了一个数据的逻辑结构以及在此结构上的一组算法或操作上的一组算法或操作 11抽象数据类型的表示抽象数据类型的表示u三元组三元组

5、 ( D, S, P )D：数据对象：数据对象S：D上的关系集上的关系集P：对：对D的基本操作集的基本操作集12抽象数据类型的表示抽象数据类型的表示ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：用伪码描述用伪码描述数据关系：数据关系：用伪码描述用伪码描述基本操作：基本操作： ADT 抽象数据类型名抽象数据类型名13抽象数据类型的表示抽象数据类型的表示基本操作的定义格式：基本操作的定义格式：基本操作名（参数表）基本操作名（参数表）初始条件：初始条件：操作结果：操作结果：14抽象数据类型的表示抽象数据类型的表示引用参数：引用参数：变量名前加变量名前加 &除了提供输入值外，还能返

6、回操除了提供输入值外，还能返回操作结果作结果15复数复数的抽象数据类型定义16 数据对象：数据对象： De1, e2e1, e2RealSet 数据关系：数据关系： R1 | e1是复数的实数部分 | e2 是复数的虚数部分 ADT Complex 17基本操作：基本操作： Assign ( &Z, realval, imagval )操作结果：构造复数 Z,其实部和虚部 分别赋以参数realval和imagval的值 Destroy ( &Z)操作结果：复数Z被销毁。 GetReal( Z, &realPart )初始条件：复数Z已存在。操作结果：用realPart返

7、回复数Z的实部值。18 GetImag( Z, &ImagPart )初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。 Add( z1, z2, &sum )初始条件：z1, z2是复数。操作结果：用sum返回复数z1与z2 的和。 ADT Complex19假设:z1和z2是上述定义的复数则 Add(z1, z2, z3) 操作的结果z3 = z1 + z21.3 抽象数据类型的表示与实现抽象数据类型的表示与实现u抽象数据类型需要通过固有数据类型固有数据类型来实现2021typedef struct complex float realpart； flo

8、at imagpart；complex；/ -存储结构的定义存储结构的定义void Assign( complex &Z, float realval, float imagval )；/ 构造复数 Z,其实部和虚部分别赋以参数 / realval 和 imagval 的值22float GetReal( complex Z )； / 返回复数 Z 的实部值float GetImag( complex Z )； / 返回复数 Z 的虚部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回两个复数 z1, z2

9、 的和 23/ -基本操作的实现基本操作的实现void add( complex z1, complex z2, complex &sum ) / 以 sum 返回两个复数 z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 1.4 算法和算法分析算法和算法分析u算法算法(algorithm)对特定问题求解步骤的一种描述是指令的有限序列u算法特性算法特性有穷性、确定性、可行性、输入、输出有穷性、确定性、可行性、输入、输出24算法设计的要求算法设计的要求

10、u正确性正确性不含语法错误不含语法错误对于某种输入数据能够得出满足要求的结果对于某种输入数据能够得出满足要求的结果对于精心选择的典型、苛刻而带有刁难性的对于精心选择的典型、苛刻而带有刁难性的输入数据能够得出满足要求的结果输入数据能够得出满足要求的结果对于一切合法的输入数据都能得出满足要求对于一切合法的输入数据都能得出满足要求的结果的结果25算法设计的要求算法设计的要求u可读性可读性u健壮性健壮性当输入数据非法时，程序也能适当地做出反当输入数据非法时，程序也能适当地做出反应或精心处理，而不会产生莫名其妙的输出应或精心处理，而不会产生莫名其妙的输出结果结果u效率与低存储量需求效率与低存储量需求26

11、算法效率的度量算法效率的度量u1. 事后统计事后统计必须执行程序依赖于计算机的硬件和软件等环境因素，可能会掩盖算法本身的优劣27算法效率的度量算法效率的度量u程序执行时间取决与如下因素时间取决与如下因素算法选用的策略算法选用的策略问题的规模问题的规模编写程序的语言编写程序的语言编译程序产生的机器代码的质量编译程序产生的机器代码的质量计算机执行指令的速度计算机执行指令的速度28同一个算法用不同的语言、或不同同一个算法用不同的语言、或不同的编译程序、或不同的计算机上运的编译程序、或不同的计算机上运行时，效率是不相同的行时，效率是不相同的算法效率的度量算法效率的度量u2. 事前分析估算事前分析估算一

12、个算法的一个算法的“运行工作量运行工作量”的大小，只依赖的大小，只依赖于于问题的规模问题的规模（通常用整数（通常用整数n表示），或者表示），或者说，它是问题规模的函数。说，它是问题规模的函数。时间复杂度时间复杂度f(n)： 基本操作基本操作的重复执行次数的重复执行次数T(n) = O ( f(n) ) 随着随着n的增大，执行次数的增大，执行次数T(n)的增长率和的增长率和f(n)的增长率相同，则的增长率相同，则f(n)称为称为 f(n)其实是其实是T(n)的数量级的数量级29int sum = 0;for (i=1; i=n; i+) sum += i;基本操作：基本操作： 加法加法T(n)

13、= n = O(n)30 for (i=1; i=n; i+)for (j=1; j=n; j+) cij = 0;for (k=1; k=n; k+)cij += aik * bkj; 基本操作：基本操作： 乘法乘法T(n) = n3 = O(n3)31int sum(int n)int s;s = 100*200;for (int i=1; i=n; i+)s += i;return s;32O（n）void f1(int a , int n)for (int i=0; in; i+)ai = 0;for (int i=0; in; i+)for (int j=0; jn; j+)ai +

14、= aj + i + j;33O（n2）递归递归阶乘阶乘long factorial(int n)if( n = 1 )return 1;elsereturn n * factorial( n - 1 );34O（n）关于时间复杂度的讨论关于时间复杂度的讨论u一般情况，对一个问题只需选择一种基一般情况，对一个问题只需选择一种基本操作来讨论算法的时间复杂度；本操作来讨论算法的时间复杂度；u但有时，也需要同时考虑几种基本操作，但有时，也需要同时考虑几种基本操作，甚至可以对不同操作赋予不同的权值，甚至可以对不同操作赋予不同的权值，以反映不同操作所需的相对时间，便于以反映不同操作所需的相对时间，便于综合比较不同的算法综合比较不同的算法35关于时间复杂度的讨论关于时间复杂度的讨论u同样的算法对不同的数据，其时间复杂同样的算法对不同的数据，其时间复杂度可能会不同，所以可采用如下度量方度可能会不同，所以可采用如下度量方法法u平均时间复杂度平均时间复杂度有时各种输入数据集出现的概率难以确定，有时各种输入数据集出现的概率难以确定，很难计算很难计算u最坏情况下的时间复杂度最坏情况下的时间复杂度更可行、更常用更