王平数据结构第一章课件.ppt

数 据 结 构,主讲教师：王平 Email :,参考资料,数据结构题集严蔚敏 清华大学出版社 数据结构算法实现及解析高一凡 西安电子科技大学出版社 数据结构课程设计苏仕华 机械工业出版社,第一章 绪论,主要知识点,1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析,教学要求,1、熟悉数据结构用到的一些基本术语、名词的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系，分清哪些是逻辑结构的性质，哪些是物理结构的性质。 2、了解抽象数据类型的定义、表示和实现方法。 3、理解算法五个要素（特性）的确切含义。 4、掌握计算语句频度和估算算法时间复杂度的方法以及算法分析中O(f(n)符号的含义。 5、熟悉一种算法描述语言（类C）的书写规范，特别要注意输入、输出的方法以及错误处理方式。,教学重点,数据结构的概念； 算法分析；,1.1 什么是数据结构,明确计算机解决问题的几个步骤 理解数据结构的含义,问题描述,1.1 什么是数据结构,计算机解决问题的几个步骤：, 数学模型： 数值问题与非数值问题,1）数值问题 例 已知：游泳池的长len和宽wide，求面积area,设计 求解问题的方法 编程 main ( ) int len, wide ,area ; scanf (“%d %d%n”, , 建模型： 问题涉及的对象：游泳池的长len 宽wide，面积area； 对象之间的关系：area=lenwide,1.1 什么是数据结构,例子1-1 书目检索系统 例子1-2人机对奕问题 例子1-3 多叉路口交通灯问题,1）非数值问题,1.1 什么是数据结构,书目文件,例子1-1 书目检索系统,例子1-2人机对奕问题,例子1-3 多叉路口交通灯问题,数据结构的研究问题： 非数值数据之间的结构关系， 及如何表示，如何存储，如何处理。 本课程讨论的问题： 应用中常用的几种数据间的结构关系， 及如何表示,如何存储，如何处理。,数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的 操作对象及它们之间的关系和操作等的学科,1.1 什么是数据结构,1.1 什么是数据结构,数据结构所处的地位P4,1.2 基本概念和术语,数据：客观对象的符号表示。 数据元素：数据的基本单位。相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。 数据对象：性质相同的数据元素的集合. 例如: 所有班名相同的记录集。,1.2 基本概念和术语,数据结构：是相互间存在关系的数据元素集合。 数据的逻辑结构：数据元素之间的关系；通常有四种基本结构： 集合 线性结构 树型结构 图结构,1.2 基本概念和术语,数据结构有两个要素： 数据元素的集合 关系的集合。 数据结构的形式定义为：数据结构是一个二元组： Data_Structure （D，R） 其中，D是数据元素的有限集，R是D上关系的有限集。,数据结构的形式定义：,1.2 基本概念和术语,例1-4：复数的数据结构 Complex=(C，R) 其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系C1，C2。 例1-5：研究课题小组的数据结构 数据的逻辑结构有两个要素:数据元素和关系.,1.2 基本概念和术语,对每种数据结构，主要讨论如下两方面的问题： 1） 数据的逻辑结构，数据结构的基本操作； 2） 数据的存储结构，数据结构基本操作的实现；,数据的存储（物理）结构,数据元素的表示 用位串在内存中实现数据结构的数据元素 数据元素之间关系的表示 顺序存储结构 借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 链式存储结构 借助指示元素存储地址的指针表示数据元素间的逻辑关系,例子：复数的存储结构,Z=3-2i,逻辑结构,顺序存储结构,链式存储结构,位 置 相 邻,指针,存储结构的描述,借用高级语言的“数据类型”来描述 顺序存储结构：数组 链式存储结构：指针,数据类型,数据结构密切相关，最早出现在高程，用以刻画操作对象的特性； 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。,高级语言的数据类型,例子：C语言中 基本数据类型：int, char, float, double等， 整型 取值范围：16位 操作：+、-、*、/、MOD、DIV 构造数据类型：数组、结构体、共用体、枚举 指针类型 空(void)类型 用户也可用typedef 自己定义数据类型,数据类型的分类,原子类型 原子类型的值是不可分解的。如C语言中整型、字符型、浮点型、双精度型等基本类型，分别用保留字int、char、float、double标识。 结构类型 结构类型是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。,抽象数据类型,是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。 注意：抽象数据类型和数据类型实质是一个概念,抽象数据类型的分类,原子类型 例子：整数，实数，字符 结构类型 固定聚合类型 例子：复数 可变聚合类型 例子：有序整数序列,抽象数据类型的形式定义,（D，S，P） D：数据对象 S：D上的关系集 P：对D的基本操作集 ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名 基本操作的定义格式 基本操作名 （参数表） 初始条件：初始条件描述 操作结果：操作结果描述,例子,用抽象数据类型三元组定义p9,1.3 抽象数据类型的表示和实现,抽象数据类型可通过固有的数据类型来表示和实现； 本书采用类C语言作为描述工具,例子,用抽象数据类型三元组的表示和实现p12,C实现抽象数据类型三元组（部分）,#include #include typedef int *Triplet; Triplet InitTriplet(int v1, int v2, int v3); main() int i; Triplet t; t = InitTriplet(1,2,3); printf(“the three is:n%d,%d,%dnn“,t0,t1,t2); getch(); Triplet InitTriplet(int v1, int v2,int v3) Triplet t; t = (int *)malloc(3*sizeof(int); if(!t) exit(0); t0=v1; t1=v2; t2=v3; return t; ,1.4 算法和算法分析,算法（algorithm）,解决某一特定问题的具体步骤的描述，是指令的有限序列,其中每条指令表示一个或多个操作。 算法示例： 求两个正整数 m，n 中的最大数MAX的算法 （1）若 m n 则 max=m （2）若 m = n 则 max=n 算法的基本特征： 1）输入：0个或多个输入； 2）输出：1个或多个输出； 3）有穷性：算法必须在有限步内结束； 4）确定性：组成算法的操作必须清晰无二义性。 5）可行性：组成算法的操作必须能够在计算机上实现。,补充：算法与程序的区别与联系,一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。 算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 一个算法若用程序设计语言来描述，则它就是一个程序。,算法设计的要求,算法的评价衡量算法优劣的标准 (1) 正确性(Correctness ) 算法应满足具体问题的需求。 (2)可读性(Readability) 算法应该好读。 (3)健状性(Robustness) 算法应具有容错处理。 (4)效率与存储量需求 一般与问题的规模有关。,算法效率的度量,事后统计利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分。 缺点：必须先运行依据算法编制的程序；所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣 事前分析估计一个用高级语言程序在计算机上运行所消耗的时间取决于： 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度,存在的问题及解决之道,注意：同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同。 结论：所以使用绝对时间单位衡量算法效率不合适（例如：50毫秒） 解决方法：撇开与计算机硬件、软件相关的因素，认为算法的“运行工作量”大小，只依赖与问题的规模。 问题的规模通常用n来表示,基本操作的原操作,算法的效率取决于基本操作重复执行的次数 算法的基本控制结构 顺序 分支 循环 结论：取基本操作的重复执行次数作为算法的时间量度,例子,N X N矩阵相乘 for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; ,基本 操作,基本操作重复执行的次数：n3，整个算法的执行时间与该 基本操作重复执行的次数n3成正比，记作T(n)=o(f(n3)。,算法的时间量度的表示,一般来说，算法基本操作的重复执行次数是问题规模n的某个函数f(n),算法的时间量度记作： T(n)=o(f(n) 它表示随着问题规模的增大，算法执行时间的增长率和f(n)的增长率相同，称为算法的渐近时间复杂度，简称时间复杂度,例子,NXN矩阵相乘 for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; ,如何选择基本操作,多数情况下选择最深层循环内的语句中的基本操作（原操作）， 原操作的执行次数和包含它的语句频度相同。 语句频度 语句重复执行的次数 一般情况下，对一个算法只需选择一种基本操作来讨论算法的时间复杂度。,例子, +x, s=0 将x自增看成是基本操作，则语句频度为，即时间复杂度为O（1）常量阶 For (i=1;i=n;+i) +x; s+=x x:=x+1的频度为n ，其时间复杂度为： O（n）线性阶 For (j=1;j=n;+j) +x; For (k=1;k=n; +k) s+=x; x:=x+1的频度为n2 ，其时间复杂度为： O（n2）平方阶,常见时间复杂度的比较,(1)(log2n)(n)(nlog2n)(n2)(n3)(2n),时间复杂度的近似计算,无法精确计算基本操作执行次数 取表达式中增长最快的项 如果我们能用一个多项式PK(n)来描述算法所需要的时间,则算法的时间复杂度是O(nk);若 PK(n)=aknk+a1n+a0 是k次多项式,则 T(n)= O(nk) 基本操作重复执行次数随问题的输入数据集不同而不同 取平均或分析最坏情况,实例：冒泡排序算法的时空复杂度事前分 void bubble_ sort( int a , int n) /将a中整数序列重新排列成自小到大的整数序列。 for ( I=n-1,change=TRUE;I=1 / bubble_ sort 1）时间复杂度分析 算法的基本操作：“交换序列中相邻两个整数” 最好情况：数组元素初始序列已为自小到大排列，基本操作执行次数为0； 最坏情况：数组元素初始序列已为自大到小排列，基本操作执行次数为: n*(n-1)，T(n)=O(n2)； 平均情况：假设数组元素初始序列可能出现n!种的排列情况的概率相等， T(n)=O(n2)。,算法的存储空间要求,一个程序的空间复杂度（Space complexity）是指程序运行从开始到结束所需的存储量。 空间复杂度：s(n)=o(f(n),程序运行所需的存储空间分类,固定部分 主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。这部分空间与所处理数据的大小和个数无关。 可变部分 例如100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。,void bubble_ sort( int a , int n) /将a中整数序列重新排列成自小到大的整数序列。 for ( I=n-1,change=TRUE;I=1 / bubbl