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

1、第1章 绪论1章 绪论 张成文张成文 sfds_ 北京邮电大学计算机学院北京邮电大学计算机学院 算法与数据结构算法与数据结构 第1章 绪论1章 绪论 n平时平时(作业作业+实验实验+期中期中)：40% n期末考试期末考试(闭卷闭卷)：60% 成绩评定标准成绩评定标准 第1章 绪论1章 绪论 n作业作业 ：概念，作业本：概念，作业本 n实验实验 ：编程，电子版：编程，电子版 两个要素两个要素 第1章 绪论1章 绪论 关于实验报告关于实验报告 电子版形式电子版形式 统一实验报告格式统一实验报告格式 每次实验每人写一个实验报告每次实验每人写一个实验报告 每次实验报告在下次上课前提交每次实验报告在下次

2、上课前提交 第1章 绪论1章 绪论 实验报告文档命名实验报告文档命名 个人个人word文档命名方式例子：文档命名方式例子： “实验实验1-班级班级-学号学号-名字名字.doc” 按班级统一压缩文档命名方式例子：按班级统一压缩文档命名方式例子： “实验实验1-班级班级.rar” 按班级统一发到指定邮箱，邮件标题例子：按班级统一发到指定邮箱，邮件标题例子： “实验实验1-班级班级” 每次实验登记每次实验登记“学习登记表学习登记表”，并一同发送，并一同发送 到指定邮箱到指定邮箱 第1章 绪论1章 绪论 实验报告内容要求实验报告内容要求 问题描述、算法描述、附加了足够注问题描述、算法描述、附加了足够注

3、 释的程序代码释的程序代码 算法中使用的函数、过程、参数、变算法中使用的函数、过程、参数、变 量的命名要能表示含义量的命名要能表示含义 注意算法格式注意算法格式(层次嵌套、不同功能层次嵌套、不同功能 块之间留空块之间留空) 第1章 绪论1章 绪论 实验报告实验报告评分标准评分标准 文档命名文档命名 报告内容是否齐全报告内容是否齐全 报告内容是否正确报告内容是否正确 第1章 绪论1章 绪论数据结构-第1章 绪论8 第第1 1章章 绪绪 论论 第1章 绪论1章 绪论数据结构-第1章 绪论9 1.1 学习数据结构的作用和意义学习数据结构的作用和意义 是为研究和解决如何有效地组织和处理是为研究和解决如

4、何有效地组织和处理非数值数据非数值数据而而 产生的理论、技术和方法。产生的理论、技术和方法。 数据结构数据结构:问题的数学模型 算法算法:处理问题的策略 程序设计程序设计: :为计算机处理问题编制的一组指令集 第1章 绪论1章 绪论10 例例 查找某人的社会关系查找某人的社会关系 计算机中如何表示计算机中如何表示/存储和操作？存储和操作？ 张三 李四 王五 陈六 赵七 第1章 绪论1章 绪论11 1.2 基本概念和术语基本概念和术语 数据数据 被计算机加工处理的对象。 数据元素数据元素 数据的基本单位基本单位，是数据集合中的一个个体。 一个数据元素可由若干个数据项数据项组成。 数据项数据项 数

5、据结构中讨论的数据的最小单位最小单位。 组合项组合项 年 月 日 学 号 姓 名 班 号 性别 出生日期 入学成绩 原子项原子项 第1章 绪论1章 绪论12 数据对象数据对象 性质相同的数据元素的集合，是数据的一个子 集。 学号 姓名 班号 性别 出生日期 入学成绩 001 刘影 01 女 19840417 623 002 李恒 01 男 19831211 679 003 陈诚 02 男 19840910 638 数据结构数据结构 具有结构的数据元素的集合。它包括数据对象 的逻辑结构逻辑结构、存储结构存储结构和相适应的运算运算（结构的行为 特征）。 数据元素 第1章 绪论1章 绪论 第1章 绪

6、论1章 绪论14 四种基本的逻辑结构四种基本的逻辑结构 (1)集合结构集合结构 数据元素除了“属于同一集合”的联系之外， 没有其它的关系。 (2)线性结构线性结构 数据元素之间存在一对一的关系。 (3)树型结构树型结构 数据元素之间存在一对多的关系。 (4)图状结构图状结构或网状结构网状结构 数据元素之间存在多对多的关系。 成员关系 长幼关系 管理关系 朋友关系 逻辑结构逻辑结构 数据元素之间的逻辑关系，与计算机无关。 第1章 绪论1章 绪论15 存储结构存储结构（物理结构物理结构）：指数据的逻辑结构 在计算机存储器中的映象表示。 数据元素的映象数据元素的映象 关系的映象关系的映象 第1章 绪

7、论1章 绪论16 数据存储方式（数据元素关系的存储）的四种常用结构数据存储方式（数据元素关系的存储）的四种常用结构 (1)顺序存储顺序存储：数据元素依次放在连续的存储单元中。 a1 a2 . ai . an (2)链式存储链式存储：在存储结点中增加若干指针域，记录后继 或者相关结点的地址（指针）。 a1 1220 . a3 1342 . a2 1072 . 1000 1004 1000 1004 1072 1076 1220 1224 指针 结点 结点 第1章 绪论1章 绪论17 (3)索引存储索引存储：将数据元素分为若干子表，子表的开始位 置存放在索引表中。 索引表 班级 addr 主表 0

8、1 1 02 31 03 54 (4)散列存储散列存储：根据数据元素的关键字值，由散列函数计 算出存储地址。LOC(ai)=H(key) 432 713 王小二 李一凡 1 a1 2 a2 31 a31 第1章 绪论1章 绪论18 运算运算（操作操作）：在数据逻辑结构上定义的 一组数据被使用的方式，其具体实现要 在存储结构上进行。 第1章 绪论1章 绪论数据结构-第1章 绪论19 数据的逻辑结构+运算的定义-面向用户 （抽象数据类型） 概念层 数据的存储结构+运算的实现-面向计算机 实现层 按照面向对象程序设计的观点，一种数据结构就是一个抽 象数据类型的体现。 在面向对象程序设计语言中，一种数

9、据结构通常使用一个 类（Class）进行封装。 在非面向对象程序设计语言中，通常用结构（Structure） 封装数据的存储结构，用函数（Function）封装一个运算 的实现。 分层模型分层模型 第1章 绪论1章 绪论 数据类型（数据类型（data type） 一组值的集合以及定义在这个值集上的一组操作的 总称。在高级语言中，数据类型通常又分为原子类型 （atomic data type）和结构类型（structural data type）。 原子类型（原子类型（atomic data type） 不可进一步分解的数据类型。 结构类型（结构类型（structural data type）

10、可进一步分解为原子类型或其它结构类型的数据类型。 根据数据元素数目的不同又可分为固定聚合类型（fixed- aggregate data type）和可变聚合类型（variable-aggregate data type)。 第1章 绪论1章 绪论 抽象数据类型（抽象数据类型（Abstract Data Type-ADT） 定义在一个抽象的数学模型上的数据类型及相应操作。 它只取决于数据类型的逻辑特性，而与数据类型在计算机 内的表示和实现无关。 第1章 绪论1章 绪论22 抽象数据类型的描述方法抽象数据类型的描述方法 其中基本操作的定义格式为: ADT 抽象数据类型名抽象数据类型名 数据对象：

11、数据对象：数据对象的定义 数据关系：数据关系：数据关系的定义 基本操作：基本操作：基本操作的定义 ADT 抽象数据类型名 基本操作名基本操作名（参数表） 初始条件：初始条件：初始条件描述 操作结果操作结果：操作结果描述 第1章 绪论1章 绪论23 例例 抽象数据类型“复数复数”的定义 ADT Complex 数据对象：数据对象： De1,e2e1,e2RealSet 数据数据关系：关系： R1 | e1是复数的实数部分, | e2 是复数的虚数部分 基本操作：基本操作： AssignComplex( else 语句; if (条件表达式 ) 语句; 第1章 绪论1章 绪论28 分情况语句（分支

12、语句）分情况语句（分支语句） 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章 绪论1章 绪论29 循环语句循环语句 while （条件表达式 ） 语句； do 语句序列； while （条件表达式）； break；/强制循环结束 continue；/

13、强制循环继续 for （赋初值表达式；条件；修改表达式） 语句； 第1章 绪论1章 绪论30 输入输出语句输入输出语句 scanf (变量表)； printf (变量表)； 转移语句转移语句 goto 语句标号； 引用语句引用语句 函数名(参量表)； 变量名=函数名(参量表)； 返回语句返回语句 return； Return 表达式 ； exit (异常代码)； 注释语句注释语句 /注释内容 /* 注释内容 */ 第1章 绪论1章 绪论31 1.3.3 算法分析算法分析 算法效率的度量算法效率的度量 一个具体问题的数据对象往往可以采用多种存储方 式的一种，一个问题的解决又常常有多种可用的算法。

14、 第1章 绪论1章 绪论数据结构-第1章 绪论32 通常有两种衡量算法效率的方法通常有两种衡量算法效率的方法: 事后统计法事后统计法 利用计算机内记时功能，不同算法的程利用计算机内记时功能，不同算法的程 序可以用一组或多组相同的统计数据区分序可以用一组或多组相同的统计数据区分 事前分析估算法事前分析估算法 时间复杂度时间复杂度(渐进时间复杂度) 空间复杂度空间复杂度 缺点：必须执行程序缺点：必须执行程序 其它因素掩盖算法本质其它因素掩盖算法本质 第1章 绪论1章 绪论 如何估算算法的时间复杂度？如何估算算法的时间复杂度？ 从算法中选取一种对所研究的问题来说从算法中选取一种对所研究的问题来说 执

15、行最频繁的执行最频繁的基本操作基本操作为原操作为原操作, 当问题规当问题规 模模 n 相当大时相当大时, 该原操作执行时间占算法总该原操作执行时间占算法总 执行时间的绝大部分执行时间的绝大部分, 所以所以, 把该原操作在把该原操作在 算法中重复执行的次数算法中重复执行的次数 (频度频度) 作为算法运行作为算法运行 时间的衡量准则时间的衡量准则。 可近似认为：可近似认为：算法的执行时间算法的执行时间 与与 原操作的频度原操作的频度 成正比成正比 估算时间复杂度时取频度的阶次估算时间复杂度时取频度的阶次 第1章 绪论1章 绪论 时间复杂度时间复杂度 n 问题规模，一般为数据的输入量 算法的时间复杂

16、度算法的时间复杂度 算法中各语句的频度之和T(n) T(n)=O( f(n) ) 大O表示法 第1章 绪论1章 绪论 时间复杂度时间复杂度 O的含义 存在正的常数c和n0，使得当n n0时， 0 T(n) c* f(n) 表示随着问题规模表示随着问题规模 n n 的增长的增长, , 算法执行时间算法执行时间 的增长率和的增长率和 f(n) f(n) 的增长率相同的增长率相同, , 称称 f(n) f(n) 为算为算 法的法的渐近时间复杂度，简称时间复杂度，渐近时间复杂度，简称时间复杂度，即，即， 当当 n n 时时 T (n) /f(n)T (n) /f(n)常数常数 。 第1章 绪论1章 绪

17、论数据结构-第1章 绪论36 例例1 交换i和j的内容 (1) temp=i; (2) i=j; (3) j=temp; 解：T(n)=3 记作T(n)= O(1) 第1章 绪论1章 绪论 常用的时间复杂度频率计数常用的时间复杂度频率计数 算法中常用的时间复杂度频率计数有算法中常用的时间复杂度频率计数有7 7种种: : O(1)O(1)常数型常数型 O(n)O(n)线性型线性型 O(nO(n2 2) )平方型平方型 O(nO(n3 3) )立方型立方型 O(2O(2n n) )指数型指数型 O(log2n)O(log2n)对数型对数型 O(nlog2n)O(nlog2n)二维型二维型 按时间复

18、杂度由小到大排列的频率表为：按时间复杂度由小到大排列的频率表为： 第1章 绪论1章 绪论 时间复杂度曲线时间复杂度曲线 O(1)O(log2n)O(n)O(nlog2n)(n2)O(n3) O(2n) 第1章 绪论1章 绪论 1、计算T(n) 2、从T(n)中推断f(n) 时间复杂度计算步骤时间复杂度计算步骤 第1章 绪论1章 绪论数据结构-第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+a

19、i, 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章 绪论1章 绪论 1、问题的规模 2、输入实例的初态 影响算法时间复杂度的因素影响算法时间复杂度的因素 第1章 绪论1章 绪论 最坏时间复杂度最坏时间复杂度 定义：定义： 算法在最坏情况下的时间复杂度算法在最坏情况下的时间复杂度 ，即为分析估计算法在最坏情况下执行，即为分析估计算法在最坏情况下执行 时间的上界。时间的上界。 第1章 绪论1章 绪论43 例例3 在数组A1.n查找给定值K (1) i=n; (2) while (i1) (4) return(i); 解：最好情况的时间复杂度 T(n)=O(1) 最坏情况的时间复杂度 T(n)=O(