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

张成文北京邮电大学计算机学院,算法与数据结构,平时(作业+实验+期中)：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 女 19840417 623 002 李恒 01 男 19831211 679 003 陈诚 02 男 19840910 638 数据结构 具有结构的数据元素的集合。它包括数据对象的逻辑结构、存储结构和相适应的运算（结构的行为特征）。,数据元素,数据结构-第1章 绪论,14,四种基本的逻辑结构,(1)集合结构 数据元素除了“属于同一集合”的联系之外，没有其它的关系。(2)线性结构 数据元素之间存在一对一的关系。(3)树型结构 数据元素之间存在一对多的关系。(4)图状结构或网状结构 数据元素之间存在多对多的关系。,成员关系,长幼关系,管理关系,朋友关系,逻辑结构 数据元素之间的逻辑关系，与计算机无关。,数据结构-第1章 绪论,15,存储结构（物理结构）：指数据的逻辑结构在计算机存储器中的映象表示。数据元素的映象关系的映象,数据结构-第1章 绪论,16,数据存储方式（数据元素关系的存储）的四种常用结构,(1)顺序存储：数据元素依次放在连续的存储单元中。a1 a2.ai.an(2)链式存储：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。a1 1220.a3 1342.a2 1072.,1000 1004,1000 1004 1072 1076 1220 1224,指针,结点,结点,数据结构-第1章 绪论,17,(3)索引存储：将数据元素分为若干子表，子表的开始位置存放在索引表中。索引表 班级 addr 主表 01 1 02 31 03 54(4)散列存储：根据数据元素的关键字值，由散列函数计算出存储地址。LOC(ai)=H(key)432 713 王小二 李一凡,1 a12 a2 31 a31,数据结构-第1章 绪论,18,运算（操作）：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。,数据结构-第1章 绪论,19,数据的逻辑结构+运算的定义-面向用户（抽象数据类型）概念层 数据的存储结构+运算的实现-面向计算机 实现层按照面向对象程序设计的观点，一种数据结构就是一个抽象数据类型的体现。在面向对象程序设计语言中，一种数据结构通常使用一个类（Class）进行封装。在非面向对象程序设计语言中，通常用结构（Structure）封装数据的存储结构，用函数（Function）封装一个运算的实现。,分层模型,数据类型（data type）,一组值的集合以及定义在这个值集上的一组操作的总称。在高级语言中，数据类型通常又分为原子类型（atomic data type）和结构类型（structural data type）。,原子类型（atomic data type）,不可进一步分解的数据类型。,结构类型（structural data type）,可进一步分解为原子类型或其它结构类型的数据类型。根据数据元素数目的不同又可分为固定聚合类型（fixed-aggregate data type）和可变聚合类型（variable-aggregate data type)。,抽象数据类型（Abstract Data Type-ADT）,定义在一个抽象的数学模型上的数据类型及相应操作。它只取决于数据类型的逻辑特性，而与数据类型在计算机内的表示和实现无关。,数据结构-第1章 绪论,22,抽象数据类型的描述方法,其中基本操作的定义格式为:,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,基本操作名（参数表）初始条件：初始条件描述 操作结果：操作结果描述,数据结构-第1章 绪论,23,例 抽象数据类型“复数”的定义,ADT Complex 数据对象：De1,e2e1,e2RealSet 数据关系：R1|e1是复数的实数部分,|e2 是复数的虚数部分 基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数 Z,其实部和虚部分别被 赋以参数 v1 和 v2 的值。DestroyComplex(&Z)操作结果：复数 Z 被销毁。GetReal(Z,&realPart)初始条件：复数 Z 已存在。操作结果：用 realPart 返回复数 Z 的实部值。ADT Complex,数据结构-第1章 绪论,24,1.3 算法的描述和分析,1.3.1 算法的概念 建立在数据结构基础上的、求解问题的一系列确切的步骤。一个算法必须满足以下五个重要特性有穷性：对任何合法输入执行有穷步后能结束。确定性：每条指令必须有确切的含义。可行性：算法的每一条指令均能执行。输入：有零个或多个输入。输出：有一个或多个输出。,数据结构-第1章 绪论,25,评价算法优劣的基本标准正确性可读性健壮性高效性（高效率与低存储量）算法效率的度量时间复杂度空间复杂度,数据结构-第1章 绪论,26,1.3.2 算法的描述,数据结构是算法处理的对象，也是实现算法的基础。选择描述工具的原则 不依赖于具体计算机与具体程序设计语言的一种形式化语言，可用于描述或表达算法思想。本课程采用类 C语言 或 伪码语言特点 它描述的算法自然易懂，具有较好的可移植性。算法格式 void 函数名(参数表)返回值的类型 函数名(参数表)/算法说明/算法说明 语句序列 语句序列/函数名/函数名,包括顺序、判定和重复三种基本控制结构和自然语言成分,数据结构-第1章 绪论,27,赋值语句,变量名=表达式；变量名1=变量名2=变量名n=表达式；(变量名1,变量名2,变量名n)=(表达式1,表达式2,表达式n)；结构变量名=(成员1值,成员2值,成员n值)；数组变量名1下标1.下标2=数组变量名2下标3.下标4；变量名1 变量名2；变量名=条件表达式？表达式T：表达式F；,条件语句,if(条件表达式)语句;else 语句;,if(条件表达式)语句;,数据结构-第1章 绪论,28,分情况语句（分支语句）,switch(表达式)case 值1：语句序列1；break;case 值2：语句序列2；break;case 值n：语句序列n；break;default:语句n+1；,switch case 条件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，使得当n n0时，0 T(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,例2 nn矩阵相乘的算法语句 for(i=1;i=n;i+)n+1 for(j=1;j=n;j+)n(n+1)ci,j=0;n2 for(k=1;k=n;k+)n2(n+1)ci,j=ci,j+ai,k*bk,j;n3 解：语句频度 T(n)=2 n3+3 n2+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=数据本身存储量/实际所占存储量,空间复杂度度量,存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过malloc和free命令动态使用的空间,若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作.若所需存储量依赖于特定的输入,则通常按最坏情况考虑。,