资源描述
数据结构,主讲教师：孙丽云 Email:,2,1、该课程共72学时，其中上课56学时，上机16学时； 2、最终成绩包括平时成绩（上课及作业情况）、上机成绩、期中成绩、期末成绩； 3、答疑； 4、公共邮箱： 用户名： 密码：xinxi007 5、一定要记笔记！,课时安排与成绩组成,3,1、求从键盘输入的任意两个数的和； 2、若从键盘输入+，则计算键盘输入的两个数的和，若从键盘输入*，则计算键盘输入的两个数的乘积； 3、求从键盘输入的10个整型数的和（用循环结构实现） 思考：若要求数据输入在主函数中，求和在自定义函数中，该如何实现？,复习C自定义函数,4,熟悉利用数组名作为函数的参数：从键盘输入十个同学的成绩，找出90分以上（包括90分）的同学的人数，找出最高分，并计算出平均分（输出结果保留2位小数）。 要求：（1）每个问题都用自定义函数实现； （2）试着将数据输入也用自定义函数实现。,第1次上机内容 （复习C数组名做函数参数）：,5,本章主题：数据结构的基本概念和术语 教学目的：了解数据结构的基本概念，理解常用术语 教学重点：熟悉数据结构常用术语，掌握基本概念，了解算法时间复杂度和空间复杂度的分析与评价 教学难点：数据元素间的 4 种结构关系。 主要内容： 1.1 什么是数据结构 1.2 算法描述 1.3 算法分析与评价,6,计算机科学技术发展速度惊人，它的广泛应用已从传统的数值计算领域发展到各种非数值计算领域，如用于控制和管理； 计算机加工处理的对象已从简单的数值发展到字符、表格和图象等各种具有一定结构的非数值性数据。,引 言,7,针对每一种新的应用领域的处理对象： 如何选择合适的数据表示（结构）； 如何有效地组织计算机存储； 在此基础上又如何有效地实现对象之间的“运算”关系； 数据结构就是研究和解决这些问题的重要基础理论。 因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。,引 言,8,1.1 什么是数据结构,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 它主要研究数据的逻辑结构、数据在计算机中的组织方式（存储结构）以及对数据进行的各种非数值运算的方法和算法。 数据结构主要有3方面的内容：数据的逻辑结构、数据的存储结构和对数据的算法。,9,一个含12位数的十进制数可以用三个4位的十进制数表示 3214,6587,9345 a1(3214),a2(6587),a3(9345) 在a1、a2和a3 之间存在“次序”关系 、 3214，6587，9345 6587，3214，9345 a1 a2 a3 a2a1 a3,非数值计算的程序设计问题 例1: 求一组(n个)整数中的最大值 算法: 基本操作是“比较两个数的大小” 数据结构：？,若整数为12位数，在计算机中如何表示该数？,1.1 什么是数据结构,10,例2、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的信息。,算法的实现，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。,1.1 什么是数据结构,11,数据结构在程序设计中的地位： 程序设计 = 算法 + 数据结构 数据结构是关于数据组织和处理的基本技术的一门学科，是程序设计的中级课程，主要培养我们分析数据、组织数据的能力，告诉我们如何编写效率高、结构好的程序。,1.1 什么是数据结构,12,1数据(Data) 数据(Data)：是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。包括文字、表格、图象等。 如一个图书管理程序所要处理的数据可能是一张表格。如P2表11,1.1.2 基本概念和术语,13,2数据元素(Data Element) 数据元素(Data Element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。,1.1.2 基本概念和术语,数据元素是数据项的集合。例： 运动员（数据元素）,14,3数据对象(Data Object) 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。,1.1.2 基本概念和术语,概念之间的关系：,数据,数据对象,数据元素,数据项,15,4数据类型(Data Type) 是一组性质相同的值的集合以及定义在这个值集合上的一组操作的总称。 例如，整型、字符型、浮点型、双精度型等数据类型，分别是一组相同结构的值以及在这些值上允许进行操作的总称。,1.1.2 基本概念和术语,16,5抽象数据类型（Abstruct Data Type，简称ADT） ADT是指一个数学模型以及定义在该模型上的一组操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。,1.1.2 基本概念和术语,17,数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构包括3方面内容：逻辑结构、存储结构（或称物理结构）、数据运算。 逻辑结构：描述数据元素间的逻辑关系，与数据的存储无关。 数据逻辑结构可以用二元组（D，R）描述D：数据元素定义域集合R：数据元素上的关系集合 关系中，a称为b的前驱，b称为a的后继,1.1.3 数据结构(Data Structure),18,根据数据元素间的逻辑关系的特点，可将基本逻辑结构分为： 集合结构：结构中的数据元素除了同属于一种类型外，别无其它关系。较少使用 线性结构：结构中的数据元素之间存在一对一的关系。 树型结构：结构中的数据元素之间存在一对多的关系。 图形结构（或称网状结构）：结构中的数据元素之间存在多对多的关系。,1.1.3 数据结构(Data Structure),19,线性结构,树型结构,图形结构,集合结构,P6例15，16,20,物理结构（存储结构）：数据结构在计算机中的存储表示。它包括数据元素的表示和关系的表示。 基本物理结构 顺序存储结构 链式存储结构,1.1.3 数据结构(Data Structure),索引与散列暂时不看。,21,顺序结构空间示意图,链式结构空间示意图,数组,指针,1.1.3 数据结构(Data Structure),22,1.1.3 数据结构(Data Structure),3数据的运算 数据运算定义在数据的逻辑结构上，即施加于数据的操作。 例如对一张表的记录进行查找、增加、删除、修改，这就是对数据的运算。 算法的实现与数据的存储结构密切相关。,23,4数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算三方面构成一个数据结构的整体。 存储结构是对数据项的存储。同一逻辑结构可用不同存储结构,就对应不同的存储标识。 例如，线性表若采用顺序存储方式，称为顺序表；若采用链式存储方式，称为链表。 逻辑结构决定了算法的设计。 物理结构决定了算法的实现。,1.1.3 数据结构(Data Structure),24,1.2 算法描述,算法：是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。,例：烧开水的步骤（算法）： E1：清洗水壶； E2：将水壶灌入适量的水； E3：把水壶放到灶上； E4：打开火； E5：注意倾听，直到听到水开的声音； E6：关火； E7：把开水灌入开水瓶中；,25,算法的重要特性 有穷性：算法总在执行有穷步后结束，且每一步都在有穷时间内完成。 确定性：不存在二义性，且相同的输入一定得到相同的输出。 可行性：算法描述的操作都可通过已经实现的基本运算执行有限次来实现。 输入：一个算法有零个或多个输入。 输出：一个算法有一个或多个输出。,1.2 算法描述,26,1用自然语言描述算法 2用流程图描述算法 但用这两种方法描述的算法不能直接在计算机上执行，必须通过编程将它转换成可执行程序。 3用程序设计（C或C+）语言描述算法 4用类语言描述算法 类语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而且比自然语言更接近程序设计语言。它虽然不能直接执行但很容易被转换成高级语言。,1.2 算法描述,27,算法设计的要求 正确性：算法应满足具体问题的需求。 可读性：便于理解、调试程序和维护。 健状性：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。,1.3 算法分析与评价,28,算法效率的度量时间复杂度,算法的时间复杂度 是指算法运行从开始到结束所需要的时间； 是对算法运行时间长短的相对度量； 是用算法包含的简单操作的次数度量，是处理问题规模的一个函数，常采用数量级的形式表示； 假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： T (n) = O(f(n) 称T (n) 为算法的(渐近)时间复杂度,29,算法效率的度量时间复杂度,例：求下列算法的时间复杂度： for(I=1;I=n;+I) s+=x;,O(n),30,例:+x;s=0; 基本操作就是两条语句，所以语句频度为，其时间复杂度为(1)，即常量阶。 例:for(I=1;I=n;+I) +x; s+=x; 语句频度为：2n，其时间复杂度为：O(n) 即时间复杂度为线性阶。,算法效率的度量 时间复杂度,31,算法效率的度量 时间复杂度,例：for(I=1,I=n;+I) for(j=1;j=n;+j) cIj=0; for(k=1;k=n;+k) cIj+=aIk*bkj; 由于是一个三重循环，每个循环从1到n，则基本操作乘法运算的总次数为: nnn=n3 时间复杂度为T(n)=O(n3),32,例:计算f=1！+2！+3！+n！，用C语言描述。 void factorsum（int n） int i,j,f,w； f=0； for（i=1;i=n;i+） w=1； for（j=1;j=i;j+） w=w*j； f=f+w； return； ,33,上述算法所用到的运算有乘法、加法、赋值和比较，其基本运算为乘法操作。在上述算法的执行过程中，对外循环变量i的每次取值，内循环变量j循环i次。因为内循环每执行一次，内循环体语句w=w*j只作一次乘法操作，即当内循环变量j循环i次时，内循环体的语句w=w*j作i次乘法。所以，整个算法所作的乘法操作总数是：f（n）=1+2+3+n=n（n+1）/2。,算法效率的度量 时间复杂度,34,有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如： Void bubble-sort(int a，int n) for(I=n-1，change=1;I1 change=1； ,最好情况：0次; 最坏情况：1+2+3+n-1 =n(n-1)/2 以最坏的情况为依据计算时间复杂度为:O(n2),将a中整数序列重新排列成自小至大 (起泡排序),算法效率的度量 时间复杂度,35,算法的空间复杂度 S(n) = O(g(n) 表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。 算法的存储量包括: 1输入数据所占空间; 2程序本身所占空间； 3辅助变量所占空间。,算法效率的度量 空间复杂度,36,若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。,算法效率的度量 空间复杂度,37,算法复杂度的意义 算法复杂度反映了随着问题规模的增加，算法在时间或空间上的消耗的增加度。,算法A的执行时间函数为：2n3+n，阶为O(n3),算法B的执行时间函数为：1000n+50，阶为O(n),哪一个算法更快呢？,算法效率的度量,1数据的逻辑结构、数据的存储结构及数据的运算三方面构成一个数据结构的整体。 2数据结构研究的是数据的表示和数据之间的关系。从逻辑上讲，数据有集合、线性、树和图四种结构。从存储结构上讲，数据有顺序结构、链接结构、索引结构和散列结构四种。理论上，任一种数据逻辑结构都可以用任一种存储结构来实现。 3算法的评价指标主要为正确性、健壮性、可读性和有效性四个方面。有效性又包括时间复杂度(性)和空间复杂度(性)两个方面。一个算法的时间和空间复杂度越好，就越节省时间和空间，则表明该算法越有效。,本章重点,39,作业,P12-P13 一、二,
展开阅读全文