北京邮电大学计算机学院数据结构第一章课件

张成文sfds_bupt北京邮电大学计算机学院,算法与数据结构,平时(作业+实验+期中)：40%期末考试(闭卷)：60%,成绩评定标准,作业：概念，作业本实验：编程，电子版,两个要素,关于实验报告,电子版形式统一实验报告格式每次实验每人写一个实验报告每次实验报告在下次上课前提交,实验报告文档命名,个人word文档命名方式例子：“实验1-班级-学号-名字.doc”按班级统一压缩文档命名方式例子：“实验1-班级.rar”按班级统一发到指定邮箱，邮件标题例子：“实验1-班级”每次实验登记“学习登记表”，并一同发送到指定邮箱,实验报告内容要求,问题描述、算法描述、附加了足够注释的程序代码算法中使用的函数、过程、参数、变量的命名要能表示含义注意算法格式(层次嵌套、不同功能块之间留空),实验报告评分标准,文档命名报告内容是否齐全报告内容是否正确,数据结构-第1章绪论,8,第1章绪论,数据结构-第1章绪论,9,1.1学习数据结构的作用和意义,是为研究和解决如何有效地组织和处理非数值数据而产生的理论、技术和方法。,数据结构:问题的数学模型算法:处理问题的策略程序设计:为计算机处理问题编制的一组指令集,数据结构-第1章绪论,10,例查找某人的社会关系,计算机中如何表示/存储和操作？,张三,李四,王五,陈六,赵七,数据结构-第1章绪论,11,1.2基本概念和术语,数据被计算机加工处理的对象。数据元素数据的基本单位，是数据集合中的一个个体。一个数据元素可由若干个数据项组成。数据项数据结构中讨论的数据的最小单位。,原子项,数据结构-第1章绪论,12,数据对象性质相同的数据元素的集合，是数据的一个子集。学号姓名班号性别出生日期入学成绩001刘影01女19840417623002李恒01男19831211679003陈诚02男19840910638数据结构具有结构的数据元素的集合。它包括数据对象的逻辑结构、存储结构和相适应的运算（结构的行为特征）。,数据元素,数据结构-第1章绪论,14,四种基本的逻辑结构,(1)集合结构数据元素除了“属于同一集合”的联系之外，没有其它的关系。(2)线性结构数据元素之间存在一对一的关系。(3)树型结构数据元素之间存在一对多的关系。(4)图状结构或网状结构数据元素之间存在多对多的关系。,成员关系,长幼关系,管理关系,朋友关系,逻辑结构数据元素之间的逻辑关系，与计算机无关。,数据结构-第1章绪论,15,存储结构（物理结构）：指数据的逻辑结构在计算机存储器中的映象表示。数据元素的映象关系的映象,数据结构-第1章绪论,16,数据存储方式（数据元素关系的存储）的四种常用结构,(1)顺序存储：数据元素依次放在连续的存储单元中。a1a2.ai.an(2)链式存储：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。a11220.a31342.a21072.,10001004,100010041072107612201224,指针,结点,结点,数据结构-第1章绪论,17,(3)索引存储：将数据元素分为若干子表，子表的开始位置存放在索引表中。索引表班级addr主表01102310354(4)散列存储：根据数据元素的关键字值，由散列函数计算出存储地址。LOC(ai)=H(key)432713王小二李一凡,1a12a231a31,数据结构-第1章绪论,18,运算（操作）：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。,数据结构-第1章绪论,19,数据的逻辑结构+运算的定义-面向用户（抽象数据类型）概念层数据的存储结构+运算的实现-面向计算机实现层按照面向对象程序设计的观点，一种数据结构就是一个抽象数据类型的体现。在面向对象程序设计语言中，一种数据结构通常使用一个类（Class）进行封装。在非面向对象程序设计语言中，通常用结构（Structure）封装数据的存储结构，用函数（Function）封装一个运算的实现。,分层模型,数据类型（datatype）,一组值的集合以及定义在这个值集上的一组操作的总称。在高级语言中，数据类型通常又分为原子类型（atomicdatatype）和结构类型（structuraldatatype）。,原子类型（atomicdatatype）,不可进一步分解的数据类型。,结构类型（structuraldatatype）,可进一步分解为原子类型或其它结构类型的数据类型。根据数据元素数目的不同又可分为固定聚合类型（fixed-aggregatedatatype）和可变聚合类型（variable-aggregatedatatype)。,抽象数据类型（AbstractDataType-ADT）,定义在一个抽象的数学模型上的数据类型及相应操作。它只取决于数据类型的逻辑特性，而与数据类型在计算机内的表示和实现无关。,数据结构-第1章绪论,22,抽象数据类型的描述方法,其中基本操作的定义格式为:,ADT抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义ADT抽象数据类型名,基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述,数据结构-第1章绪论,23,例抽象数据类型“复数”的定义,ADTComplex数据对象：De1,e2e1,e2RealSet数据关系：R1|e1是复数的实数部分,|e2是复数的虚数部分基本操作：AssignComplex(else语句;,if(条件表达式)语句;,数据结构-第1章绪论,28,分情况语句（分支语句）,switch(表达式)case值1：语句序列1；break;case值2：语句序列2；break;case值n：语句序列n；break;default:语句n+1；,switchcase条件1：语句序列1；break;case条件2：语句序列2；break;case条件n：语句序列n；break;default:语句n+1；,数据结构-第1章绪论,29,循环语句,while（条件表达式）语句；,do语句序列；while（条件表达式）；,break；/强制循环结束,continue；/强制循环继续,for（赋初值表达式；条件；修改表达式）语句；,数据结构-第1章绪论,30,输入输出语句,scanf(变量表)；,printf(变量表)；,转移语句,goto语句标号；,引用语句,函数名(参量表)；,变量名=函数名(参量表)；,返回语句,return；,Return表达式；,exit(异常代码)；,注释语句,/注释内容,/*注释内容*/,数据结构-第1章绪论,31,1.3.3算法分析算法效率的度量,一个具体问题的数据对象往往可以采用多种存储方式的一种，一个问题的解决又常常有多种可用的算法。,数据结构-第1章绪论,32,通常有两种衡量算法效率的方法:,事后统计法利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分,事前分析估算法时间复杂度(渐进时间复杂度)空间复杂度,缺点：必须执行程序其它因素掩盖算法本质,如何估算算法的时间复杂度？,从算法中选取一种对所研究的问题来说执行最频繁的基本操作为原操作,当问题规模n相当大时,该原操作执行时间占算法总执行时间的绝大部分,所以,把该原操作在算法中重复执行的次数(频度)作为算法运行时间的衡量准则。可近似认为：算法的执行时间与原操作的频度成正比估算时间复杂度时取频度的阶次,时间复杂度,n问题规模，一般为数据的输入量算法的时间复杂度算法中各语句的频度之和T(n)T(n)=O(f(n)大O表示法,时间复杂度,O的含义存在正的常数c和n0，使得当nn0时，0T(n)c*f(n)表示随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,称f(n)为算法的渐近时间复杂度，简称时间复杂度，即，当n时T(n)/f(n)常数。,数据结构-第1章绪论,36,例1交换i和j的内容(1)temp=i;(2)i=j;(3)j=temp;解：T(n)=3记作T(n)=O(1),常用的时间复杂度频率计数,算法中常用的时间复杂度频率计数有7种:,O(1)常数型O(n)线性型O(n2)平方型O(n3)立方型O(2n)指数型O(log2n)对数型O(nlog2n)二维型,按时间复杂度由小到大排列的频率表为：,时间复杂度曲线,O(1)O(log2n)O(n)O(nlog2n)(n2)O(n3)O(2n),1、计算T(n)2、从T(n)中推断f(n),时间复杂度计算步骤,数据结构-第1章绪论,40,例2nn矩阵相乘的算法语句for(i=1;i=n;i+)n+1for(j=1;j=n;j+)n(n+1)ci,j=0;n2for(k=1;k=n;k+)n2(n+1)ci,j=ci,j+ai,k*bk,j;n3解：语句频度T(n)=2n3+3n2+2n+1当nn0=1时，有T(n)8n3，即c=8，由此取f(n)=n3则T(n)=O(n3)算法中存在循环时，通常由嵌套层数最深的循环语句的最内层语句决定,1、问题的规模2、输入实例的初态,影响算法时间复杂度的因素,最坏时间复杂度,定义：算法在最坏情况下的时间复杂度，即为分析估计算法在最坏情况下执行时间的上界。,数据结构-第1章绪论,43,例3在数组A1.n查找给定值K(1)i=n;(2)while(i1)解：最好情况的时间复杂度T(n)=O(1)最坏情况的时间复杂度T(n)=O(n)平均时间复杂度：所有可能的输入实例以等概率出现的情况T(n)=(1+2+.+n)/n=O(n)算法与数据状态有关时，需讨论不同情况,1,n,数据结构-第1章绪论,44,2）空间复杂度算法的存储空间输入数据所占空间程序本身所占空间辅助变量所占空间空间复杂度S(n)=O(f(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。存储密度d=数据本身存储量/实际所占存储量,空间复杂度度量,存储空间的固定部分程序指令代码的