资源描述
2020/7/23,柳 青 Email: School of Software , Yunnan University,数据结构 (Data Structure),2020/7/23,数据结构 （C语言版） 严蔚敏 吴伟民 清华大学出版社 数据结构题集 严蔚敏 吴伟民 清华大学出版社 数据结构习题与解析 （C语言篇） 李春葆 清华大学出版社,数据结构教材及参考材料,2020/7/23,数据结构是计算机类本科专业的一门必修课程，同时也是很多非计算机类本科专业的主要选修课程，属于综合性的专业基础课。 数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，具有很强的理论性和实践性。 数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统和其他系统程序和大型应用程序的重要基础。,数据结构课程性质及特点,2020/7/23,第一章 绪 论,1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求,2020/7/23,计算机的程序是对信息（数据）进行加工处理。信息的表示和处理直接关系到程序的效率。在大多数情况下，信息之间往往具有重要的结构关系，这就是数据结构的内容。 例1、电话号码查询系统：设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1) (a2，b2)(an，bn), 其中ai，bi (i=1，2n) 分别表示某人的名字和对应的电话号码。 要求设计算法：（1）当给定任何一个人的名字时能够给出此人的电话号码；（2）加入一个新的人的名字和其相应的电话号码；（3）删除一个不需要的人的名字和其相应的电话号码。,1.1 什么是数据结构,2020/7/23,1.1 什么是数据结构,算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算。 数据结构的三个方面： 1 逻辑结构数据之间的逻辑关系 2 物理结构数据在计算机中如何表示 3 运算 问题逻辑结构（模型）物理结构（存储） 运算（算法）,2020/7/23,数据(Data):是对客观事物的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 Eg. 75, “软件”，08/08/2008。 在计算机科学中，数据的含义极为广泛，包括数值型、非数值型、多媒体数据等。 数据元素(Data Element): 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。Eg. “图”中的圆圈。 一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。 Eg. “书目”中的书名。 数据对象(Data Object) : 是性质相同的数据元素的集合。是数据的一个子集。 Eg. C= “ A, “ B”, , “ Z ” ,1.2 基本概念和术语,2020/7/23,数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构。通常分为四类基本结构： 1、集合 数据元素除了同属于一种类型外，别无其它关系。 2、线性结构 数据元素之间存在一对一的关系。 3、树形结构 数据元素之间存在一对多的关系。 4、图状结构 数据元素之间存在多对多的关系。,1.2 基本概念和术语,集合,线性结构,树形结构,图状结构,2020/7/23,数据结构的形式定义为：数据结构是一个二元组 Data-Structure = (D，S) 其中，D是数据元素的有限集，S是D上关系的有限集。 例： 复数的数据结构定义如下： Complex=(C，R) 其中，C是含两个实数的集合C1，C2，R=P，P是定义在集合C上的一种关系 C1，C2， 其中C1，C2表示复数的实部和虚部。,1.2 基本概念和术语,2020/7/23,数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。数据结构在计算机中有两种不同的表示方法： 顺序存储结构： 用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。,1.2 基本概念和术语,2020/7/23,数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。在程序设计语言中，用以刻画操作对象的特性。 Eg. C语言的数据类型：基本类型和构造类型。 基本类型：整型、浮点型、字符型。 构造类型：数组、结构、联合、指针等。 数据对象：是某种数据类型元素的集合。 Eg. 整数的数据对象是-2，-1，0，1，2， 英文字符类型的数据对象是A，B，C，D，E，F， 数据对象可以是有限的，也可以是无限的。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。,1.2 基本概念和术语,2020/7/23,抽象数据类型ADT（Abstract Data Type)：指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型ADT实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。 用三元组描述为：（，） 其中D是数据对象，S是D上的关系集，P是对D的基本操作集。Eg. P9.,1.2 基本概念和术语,2020/7/23,抽象数据类型ADT可以看作是描述问题的模型，它独立于具体实现。 ADT的优点是将数据和操作封装在一起，从而实现了信息隐蔽。 在面向对象语言中，可以用类的说明来表示ADT，用类的实现来实现ADT。 ADT相当于是在概念层（抽象层）上描述问题，而类相当于是在实现层（应用层）上描述问题。,1.2 基本概念和术语,2020/7/23,ADT 可通过固有数据类型来表示和实现。本书采用介于伪码和C语言之间的类C语言作为描述工具。P10-11 预定义常量和类型 #define typedef 用于定义数据结构的存储结构 算法用函数描述 赋值语句：简单、串联、成组、交换、条件赋值 选择语句：if then、switch case 循环语句：for、while、do-while 结束语句: return、break、exit 输入输出语句: scanf、printf 注释：/ 基本函数: max、min、abs、floor、ceil、eof、eoln 逻辑运算： s=0; 将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)。如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。 例2 for (i=1; i=n ; +i) +x; s+=x; 语句频度为2n，其时间复杂度为O(n)，即线性阶。,1.4 算法和算法分析,2020/7/23,例3 for(i=1; i=n; +i) for(j=1; j=n; +j) +x; s+=x; 语句频度为：2n2，其时间复杂度为：O(n2)。 即时间复杂度为平方阶。 定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一个m次多项式，则A(n)=O(n m)证略。,1.4 算法和算法分析,2020/7/23,例4 for(i=2; i=n; +i) for(j=2; j=i-1; +j) +x; aij=x; 语句频度为：1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 = n2-3n+2 时间复杂度为O(n2) 即此算法的时间复杂度为平方阶。 一个时间复杂度为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。,1.4 算法和算法分析,2020/7/23,以下是最常用的计算算法时间的多项式，其关系为： O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) O(2n)O(n!)O(nn),2n,2,5n2,100n,200log2n,n3,1.4 算法和算法分析,2020/7/23,有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如： void bubble-sort(int a ，int n) for(i=n-1;change=TURE;i1 change=TURE 最好情况：0次 最坏情况：1+2+3+n-1=n(n-1)/2 平均时间复杂度为:O(n2),1.4 算法和算法分析,2020/7/23,1.4.4 算法的存储空间需求 空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n) 其中n为问题的规模(或大小)。 例：数组逆序问题。 算法1：for(i=0; in; i+) bn-i-1=ai; for(i=0; in; i+) ai=bi; 该算法需额外使用n个存储单元，S(n)=O(n) 算法2：for(i=0; in/2; i+) x=ai; ai=an-i-1; an-i-1=x; 该算法需额外使用1个存储单元，S(n)=O(1),1.4 算法和算法分析,2020/7/23,本章习题,“数据结构题集（C 语言版）” P7-9 2、6、7、10、13 单周星期一交作业！,
展开阅读全文