自考数据结构ppt课件 第一章 绪论.ppt

数据结构,教材: 自考数据结构 苏仕华 编著,授课教师：涂风华开始日期：2014年3月1日,1.1 基本概念和术语 1.2 学习数据结构的意义 1.3 算法的描述和分析,第1章 概论,数据（data)是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的原料。 数据元素（data element）是数据的基本单位，由若干个数据项组成，也称结点、元素、顶点或记录。数据项（data item）是具有独立含义的最小标识单位，有时也称为域（field），即数据表中的字段。,1.1 基本概念和术语,数据结构(data structure)：指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括以下三方面内容： 数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）； 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）； 数据的运算，即对数据施加的操作。,数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我们只知道这些操作是做什么，而无须考虑如何做。只有确定了存储结构之后，才考虑如何具体实现这些运算。 3,为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。【例11】 学生成绩表，见下表。 （1）逻辑结构表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor）最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor）也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中李四所在结点的直接前趋结点和直接后继结点分别是张三和王五所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。,（2）存储结构该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？（3）数据的运算在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查找、删除、插入，这就是数据的运算问题。 搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。,2数据的逻辑结构分类 在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类： （1）线性结构 线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 线性表是一个典型的线性结构。栈、队列、串等都是线性结构。（2）非线性结构 非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。,3数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到：（1）顺序存储方法 该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。 由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。（2）链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure）,通常借助于程序语言的指针类型描述。,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,（3）索引存储方法 该方法通常在储存结点信息的同时，还建立附加的索引表。 索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(Spare Index)。索引项的一般形式是： (关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法 该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。 四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。,4数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。 存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。 【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。 数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。 【例】若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列或链队列。,5数据类型和抽象数据类型数据类型（Data Type） 自20世纪70年代以来，几乎所有的高级程序设计语言都提供了这一概念。在用高级语言编写的程序中间，程序中出现的每个变量，常量或表达式，都必须事先说明它们所属的数据类型，每个类型都明显或隐含的规定了在程序执行期间它的变量，它的表达式所允许取值的范围，以及允许进行的操作，因此所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。【例12】C语言的整数类型就定义了一个整数可取值的范围（其最大值INT-MAX依赖于具体机器）以及对整数可施加的加、减、乘、除和取模等操作。 按值是否可分解，可将数据类型划分为两类：原子类型：其值不可分解。通常是由语言直接提供。 【例】C语言的整型、字符型等标准类型及指针等简单的导出类型；结构类型：其值可分解为若干个成分（或称为分量）。是用户借助于语言提供的描述机制自己定义的，它通常是由标准类型派生的，故它也是一种导出类型。 【例】C的数组、结构等类型。,用户也可用typedef 自己定义数据类型,typedef struct int num; char name20; float score; STUDENT;STUDENT stu1,stu2, *p;,抽象数据类型ADT（Abstract Data Type),定义：是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 数据结构+定义在此数据结构上的一组操作 = 抽象数据类型,一个ADT可描述为：ADT ADT-Name Data: /数据说明 数据元素之间逻辑关系的描述 Operations: /操作说明 Operation1: /操作1，它通常可用C或C的函数原型来描述 Input:对输入数据的说明 Preconditions:执行本操作前系统应满足的状态/可看作初始条件 Process:对数据执行的操作 Output:对返回数据的说明 Postconditions:执行本操作后系统的状态/系统可看作某个数据结构 Operation2:/操作2 /ADT,描述方法形式定义：我们用一个三元组 （D，S，P）来表示一个 抽象数据类型 ，其中D是数据对象，S是D上的关系集，P是对D的基本操作集。 格式： ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,基本操作的定义格式： 基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述,赋值参数引用参数，以“”打头,例：抽象数据类型三元组的定义： ADT Triplet 数据对象：D=e1,e2,e3 |e1,e2,e3Elemset 数据关系：R1=, 基本操作： InitTriplet(&T,v1,v2,v3) 操作结果：构造了三元组T， 元素e1，e2和e3分别被赋以 参数v1,v2和v3的值。,DestroyTriplet（&T） 操作结果：三元组T被销毁。 Get（T,i,&e） 初始条件：三元组T已存在， 1=i=3. 操作结果：用e返回T的第i元的值。 Put(&T,i,e) 初始条件：三元组T已存在，1=i=3. 操作结果：改变T的第i元的值为e。 IsAscending(T) 初始条件：三元组T已存在。 操作结果：如果T的3个元素按升序排列，则返回1，否则返回0。,IsDescending(T) 初始条件：三元组T已存在。 操作结果：如果T的3个元素按降序排列，则 返回1，否则返回0。Max(T,&e) 初始条件：三元组T已存在。 操作结果：用e返回T的3个元素中的最大值。Min(T,&e) 初始条件：三元组T已存在。 操作结果：用e返回T的3个元素中的最小值。ADT Triplet,抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。在C中，我们可以用类（包括模板类）的说明来表示ADT，用类的实现来实现ADT。因此，C中实现的类相当于是数据的存储结构及其在存储结构上实现的对数据的操作。ADT和类的概念实际上反映了程序或软件设计的两层抽象：ADT相当于是在概念层（或称为抽象层）上描述问题，而类相当于是在实现层上描述问题。此外，C中的类只是一个由用户定义的普通类型，可用它来定义变量（称为对象或类的实例）。因此，在C中，最终是通过操作对象来解决实际问题的，所以我们可将该层次看作是应用层。例如，main程序就可看作是用户的应用程序。由于C语言中没有提供类这一数据类型，因此无法实现ADT，故我们不采用ADT的形式来描述数据结构，以节省篇幅。大家只要记住，它实际上等价于我们定义的数据的逻辑结构以及在逻辑结构上定义的抽象操作。,1.2 学习数据结构的意义,著名计算机科学家、Pascal语言发明者N.沃思教授提出： 程序 = 算法 + 数据结构 程序: 处理问题编制一组指令集 算法: 处理问题的策略数据结构: 问题的数学模型也就是说，计算机按照程序所描述的算法对某种结构的数据进行加工处理。,1 计算机处理问题的分类 （1）数值计算问题 在计算机发展初期，人们使用计算机主要是处理数值计算问题。【例】线性方程的求解 该类问题涉及的运算对象是简单的整型、实型或布尔型数据。程序设计者的主要精力集中于程序设计的技巧，无须重视数据结构。,随着计算机应用领域的扩大和软、硬件的发展，“非数值性问题”越来越显得重要。据统计，当今处理非数值性问题占用了90%以上的机器时间，这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决此类问题的关键已不再是分析数学和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。 程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。,（2）非数值计算的程序设计问题：,例1 书目自动检索系统,书目文件,算法：需要检索的书目？如何检索？用户界面？ 模型：？,例2 人机对奕问题,算法：对奕的规则 和策略模型：？,例3 教学计划编排问题,算法：如何确定课程的次序关系? 模型：？,从上述例子不难看出：解决问题的一个关键步骤是，选取合适的数据结构表示该问题，然后才能写出有效的算法。,1.3 算法的描述和分析,有穷性：对于任意一组合法输入值，在执行有穷步之后结束，且算法中的每个步骤都能在有限时间内完成；确定性：每条指令都有确切的含义，在任何条件下算法都只有一条执行路径；,算法五个重要特性：,算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。,可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；输入：有零个或多个输入，取自特定的对象集合输出：有一个或多个输出，是算法进行信息加工后得到的结果。,二、算法分析1评价算法好坏的标准求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？ 选用的算法首先应该是正确的。此外，主要考虑如下三点： 执行算法所耗费的时间； 执行算法所耗费的存储空间，其中主要考虑辅助存储空间； 算法应易于理解，易于编码，易于调试等等。,2算法性能选择一个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时相互抵触：要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的计算时间。因此我们只能根据具体情况有所侧重： 若该程序使用次数较少，则力求算法简明易懂； 对于反复多次使用的程序，应尽可能选用快速的算法； 若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。,3算法的时间性能分析（1）算法耗费的时间和语句频度一个算法所耗费的时间=算法中每条语句的执行时间之和每条语句的执行时间=语句的执行次数(即频度(Frequency Count)语句执行一次所需时间 算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。 若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。,算法执行时间的衡量方法和准则 有两种衡量算法效率的方法: 1.事后统计法：利用计算机内记时功能，用一组或多组相同的统计数据区分。 2.事前分析估计法：求出算法的一个时间界限函数。,和算法执行时间相关的因素： 算法选用的策略 问题的规模 书写程序的语言 编译程序产生机器代码质量 机器执行指令速度,（2）时间复杂度：程序运行从开始到结束所需要的时间。 设解决一个问题的规模为n，基本操作被重复执行的次数是n的一个函数 f（n），假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： T (n) = O(f(n) 其中T(n)叫算法的渐进时间复杂度，简称时间复杂度。P8,例1：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; ,显然，被称做问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下是最深层循环内的语句中的原操作，它的执行次数和包含它的语句频度相同。,例2+x;s=0;例for(i=1; i=n; +i) +x; s+=x;例. for(i=2; i=n; +i) for(j=2; j=i-1; +j) +x; ai,j=x;,T(n)=(1) 常量阶,T(n)= O(n) 线性阶,+x语句频度为：1+2+3+n-2 =(n-1)(n-2)/2 =(n2-3n+2)/2 T(n)= O(n2) 平方阶,(1)(log2n)(n) (n2)(n3)(2n),例5：Void bubble-sort(int a ，int n) for( i=n-1,change=TURE; i=1 change=TURE； ,最好情况：1次最坏情况：（n-1）+（ n-2） +1 = n(n-1)/2平均时间复杂度为：O(n2),空间复杂度：算法所需存储空间的度量，记作： S(n)=O(f(n) 算法的存储量包括：（1）输入数据所占空间； （2）程序本身所占空间； （3）辅助变量所占空间。,注意：算法的所有性能之间都存在着或多或少的相互影响，因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素，才能设计出比较好的算法。,（3）算法的存储空间需求,1. 熟悉各名词、术语的含义，掌握基本概念。,2. 理解学习数据结构的意义。,本章学习要点,3. 掌握计算语句频度和估算算法时间复杂度的方法。,