数据结构：第1章 绪论

1、数据结构数据结构n平时平时(实验实验)：40% n期末考试期末考试(闭卷闭卷)：60%成绩评定标准成绩评定标准关于实验报告关于实验报告 电子版形式电子版形式 统一实验报告格式统一实验报告格式 每次实验写一个实验报告每次实验写一个实验报告 每次实验报告在下次上课前提交每次实验报告在下次上课前提交实验报告文档命名实验报告文档命名 个人个人word文档命名方式例子：文档命名方式例子： “实验实验1-班级班级-学号学号-名字名字.doc” 按班级统一压缩文档命名方式例子：按班级统一压缩文档命名方式例子： “实验实验1-班级班级.rar” 按班级统一发到指定邮箱，邮件标题例子：按班级统一发到指定邮箱，邮

2、件标题例子： “实验实验1-班级班级” 每次实验登记每次实验登记“学习登记表学习登记表”，并一同发送，并一同发送到指定邮箱到指定邮箱实验报告内容要求实验报告内容要求 问题描述、算法描述、附加了足够注问题描述、算法描述、附加了足够注释的程序代码释的程序代码 算法中使用的函数、过程、参数、变算法中使用的函数、过程、参数、变量的命名要能表示含义量的命名要能表示含义 注意算法格式注意算法格式(层次嵌套、不同功能层次嵌套、不同功能块之间留空块之间留空)实验报告实验报告评分标准评分标准 文档命名文档命名 报告封面内容是否齐全报告封面内容是否齐全 报告格式是否正确报告格式是否正确 报告内容是否齐全报告内容是

3、否齐全 报告内容是否正确报告内容是否正确数据结构-第1章 绪论7 第第1 1章章 绪绪 论论数据结构-第1章 绪论81.1 学习数据结构的作用和意义学习数据结构的作用和意义 是为研究和解决如何有效地组织和处理是为研究和解决如何有效地组织和处理非数值数据非数值数据而而产生的理论、技术和方法。产生的理论、技术和方法。 是计算机科学中的一门是计算机科学中的一门综合综合性的专业性的专业基础基础课。课。 涉及计算机软件、硬件以及数学等涉及计算机软件、硬件以及数学等 数据结构在软件开发中的地位：数据结构在软件开发中的地位： 系统分析系统分析 系统设计系统设计 系统实现系统实现 系统维护系统维护 (Nikl

4、aus Wirth：数据结构+算法=程序)数据结构数据结构:问题的数学模型算法算法:处理问题的策略程序设计程序设计: :为计算机处理问题编制的一组指令集 数据结构-第1章 绪论9例例 查找某人的社会关系查找某人的社会关系计算机中如何表示计算机中如何表示/存储和操作？存储和操作？张三李四王五陈六赵七数据结构-第1章 绪论10 输入 输出CPU 控制器 运算器寄存器(组)内存储器外存储器控制器：控制系统一步步从存储器中取出指令、译码运算器：根据指令完成算术/逻辑运算寄存器：保持程序运行状态、存储当前指令信息 及下一条指令地址等0OxFF操作系统内存内存（文件）（文件）数据结构-第1章 绪论11存储

5、方案存储方案1： 存储方案存储方案2： 存储方案存储方案3： 张三.王五李四陈六李四王五.204020802120张三.234李四王五.204020802120(1)(2)(3)40Byte张三.311830601596王五李四.204030603118数据结构-第1章 绪论12数据结构的作用范畴数据结构的作用范畴 抽象数据对象的数学模型（逻辑结构） 例：图状结构 明确操作（运算的定义） 例：查找、插入、 在存储结构上映射数据（物理/存储结构） 例：顺序存储 实现操作数据结构-第1章 绪论141.2 基本概念和术语基本概念和术语数据数据 被计算机加工处理的对象。数据元素数据元素（记录记录、表目

6、表目） 数据的基本单位基本单位，是数据集合中的一个个体。 一个数据元素可由若干个数据项数据项组成。数据项是数据结构中讨论的数据的最小单位最小单位。 组合项组合项 年 月 日学 号 姓 名 班 号 性别 出生日期 入学成绩原子项原子项数据结构-第1章 绪论15数据对象数据对象 是性质相同的数据元素的集合，是数据的一个子集。 学号 姓名 班号 性别 出生日期 入学成绩 001 刘影 01 女 19840417 623 002 李恒 01 男 19831211 679 003 陈诚 02 男 19840910 638 数据结构数据结构 具有结构的数据元素的集合。它包括数据对象的逻辑结构逻辑结构、存储

7、结构存储结构和相适应的运算运算（结构的行为特征）。数据元素数据结构-第1章 绪论16逻辑结构逻辑结构 数据元素之间的逻辑关系，与计算机无关。 可用一个二元组抽象表示：Data_Structure = (D,R) D数据元素的有穷集合，RD上关系的有穷集合。 例例 设有数据结构 B = (D,R) ， 其中 D= d1, d2, d3, d4, d5, d6， R=r， r=, , , , ， 试画出其逻辑结构图。 d1d2 d3 d4d5 d6数据结构-第1章 绪论17四种基本的逻辑结构四种基本的逻辑结构（以班级学生关系为例）(1)集合结构集合结构 数据元素除了“属于同一集合”的联系之外，没有

8、其它的关系。(2)线性结构线性结构 数据元素之间存在一对一的关系。(3)树型结构树型结构 数据元素之间存在一对多的关系。(4)图状结构图状结构或网状结构网状结构 数据元素之间存在多对多的关系。成员关系长幼关系管理关系朋友关系数据结构-第1章 绪论18例例 铺设城市通信管线，使总投资最少？逻辑结构：图状结构数据结构-第1章 绪论19存储结构存储结构（物理结构物理结构）：指数据的逻辑结构在计算机存储器中的映象表示。 数据元素的映象数据元素的映象 用二进制位(bit)的位串表示数据元素。 每个数据元素的映象称为结点结点 每个数据项的映象称为数据域数据域 关系的映象关系的映象两种基本方法及其组合使用。

9、 顺序映象：以相对的存储位置表示关系 链式映象：以附加信息(指针)表示关系在不同的编程环境下，存储结构有不同的描述方式。用高级程序语言编程时，通常可用其提供的数据类型描述。数据结构-第1章 绪论20数据存储方式的四种常用结构数据存储方式的四种常用结构(1)顺序存储顺序存储：数据元素依次放在连续的存储单元中。 a1 a2 . ai . an (2)链式存储链式存储：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。 a1 1220 . a3 1342 . a2 1072 .1000 1004 1000 1004 1072 1076 1220 1224指针结点结点数据结构-第1章 绪

10、论21(3)索引存储索引存储：将数据元素分为若干子表，子表的开始位置存放在索引表中。 索引表 班级 addr 主表 01 1 02 31 03 54 (4)散列存储散列存储：根据数据元素的关键字值，由散列函数计算出存储地址。LOC(ai)=H(key) 432 713 王小二 李一凡1 a12 a2 31 a31 数据结构-第1章 绪论22运算运算（操作操作）：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。几种常用的运算有： (1)建立数据结构 (6)检索* (2)清除数据结构 (7)更新 (3)插入数据元素 (8)判空和判满* (4)删除数据元素 (9)求长* (

11、5)排序 *操作为引用型操作引用型操作，即数据值不发生变化；其它为加加工型操作工型操作。数据结构-第1章 绪论23 数据的逻辑结构+运算的定义-面向用户 （抽象数据类型） 概念层 数据的存储结构+运算的实现-面向计算机 实现层分层模型分层模型数据结构-第1章 绪论241.3 算法的描述和分析算法的描述和分析1.3.1 算法的概念算法的概念 建立在数据结构基础上的、求解问题的一系列确切的步骤。一个算法必须满足以下一个算法必须满足以下五五个重要特性个重要特性 有穷性：对任何合法输入执行有穷步后能结束。 确定性：每条指令必须有确切的含义。 可行性：算法的每一条指令均能执行。 输入：有零个或多个输入。

12、 输出：有一个或多个输出。数据结构-第1章 绪论25评价算法优劣的基本标准评价算法优劣的基本标准 正确性 可读性 健壮性 高效性（高效率与低存储量）算法效率的度量算法效率的度量 时间复杂度 空间复杂度数据结构-第1章 绪论261.3.2 算法的描述算法的描述 数据结构是算法处理的对象，也是实现算法的基础。选择描述工具的原则选择描述工具的原则 不依赖于具体计算机与具体程序设计语言的一种形式化语言，可用于描述或表达算法思想。 本课程采用类 C语言 或 伪码语言特点特点 它描述的算法自然易懂，具有较好的可移植性。 算法格式算法格式 void 函数名(参数表) 返回值的类型 函数名(参数表) /算法说

13、明 /算法说明 语句序列 语句序列 /函数名 /函数名包括顺序、判定和重复三种基本控制结构和自然语言成分数据结构-第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章 绪论2

14、8 分情况语句（分支语句）分情况语句（分支语句）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；/强制循环结束continu

15、e；/强制循环继续for （赋初值表达式；条件；修改表达式） 语句；数据结构-第1章 绪论30 输入输出语句输入输出语句scanf (变量表)；printf (变量表)； 转移语句转移语句goto 语句标号； 引用语句引用语句函数名(参量表)；变量名=函数名(参量表)； 返回语句返回语句return；Return 表达式 ；exit (异常代码)； 注释语句注释语句/注释内容/* 注释内容 */例例 冒泡排序算法冒泡排序算法数据结构-第1章 绪论31void bubble_sort(int a , int n ) /将a中n个数据序列重新排列成自小至大有序的整数序列 for (i=n-1, c

16、hange=TRUE; i=1 & change; -i) change=FALSE; for ( j=0; jaj+1 ) aj aj+1; change=TRUE; /bubble_sort数据结构-第1章 绪论32 一些约定一些约定1）预定义常量和类型：/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/Status作为函数的类型，其值是函数结果状态代码typedef int Status;2）数据元素类型约定为ElemT

17、ype，使用时按需定义数据结构-第1章 绪论331.3.3 算法分析算法分析 算法效率的度量算法效率的度量 一个具体问题的数据对象往往可以采用多种存储方式的一种，一个问题的解决又常常有多种可用的算法。数据结构-第1章 绪论34通常有两种衡量算法效率的方法通常有两种衡量算法效率的方法: 事后统计法事后统计法 利用计算机内记时功能，不同算法的程利用计算机内记时功能，不同算法的程 序可以用一组或多组相同的统计数据区分序可以用一组或多组相同的统计数据区分事前分析估算法事前分析估算法时间复杂度时间复杂度(渐进时间复杂度)空间复杂度空间复杂度缺点：必须执行程序缺点：必须执行程序 其它因素掩盖算法本质其它因

18、素掩盖算法本质和算法执行时间相关的因素和算法执行时间相关的因素(1)程序运行时所需输入的数据总量程序运行时所需输入的数据总量 （问题规模）（问题规模）(2)对源程序进行编译所需时间对源程序进行编译所需时间(3)计算机执行每条指令所需时间计算机执行每条指令所需时间(4)程序中指令重复执行的次数程序中指令重复执行的次数 如何估算算法的时间复杂度？如何估算算法的时间复杂度？ 从算法中选取一种对所研究的问题来说从算法中选取一种对所研究的问题来说执行最频繁的执行最频繁的基本操作基本操作为原操作为原操作, 当问题规当问题规模模 n 相当大时相当大时, 该原操作执行时间占算法总该原操作执行时间占算法总执行时

19、间的绝大部分执行时间的绝大部分, 所以所以, 把该原操作在把该原操作在算法中重复执行的次数算法中重复执行的次数 (频度频度) 作为算法运行作为算法运行时间的衡量准则时间的衡量准则。 可近似认为：可近似认为：算法的执行时间算法的执行时间 与与 原操作的频度原操作的频度 成正比成正比 估算时间复杂度时取频度的阶次估算时间复杂度时取频度的阶次时间复杂度时间复杂度 n 问题规模，一般为数据的输入量 算法的时间复杂度算法的时间复杂度 算法中各语句的频度之和T(n) T(n)=O( f(n) ) 大O表示法时间复杂度时间复杂度 O的含义 存在正的常数c和n0，使得当n n0时， 0 T(n) c* f(n

20、) 表示随着问题规模表示随着问题规模 n n 的增长的增长, , 算法执行时间算法执行时间的增长率和的增长率和 f(n) f(n) 的增长率相同的增长率相同, , 称称 f(n) f(n) 为算为算法的法的渐近时间复杂度，简称时间复杂度，渐近时间复杂度，简称时间复杂度，即，即， 当当n n 时时 T (n) /f(n)T (n) /f(n)常数常数 。 常用的时间复杂度频率计数常用的时间复杂度频率计数 算法中常用的时间复杂度频率计数有算法中常用的时间复杂度频率计数有7 7种种: :O(1)O(1)常数型常数型 O(n)O(n)线性型线性型 O(nO(n2 2) )平方型平方型 O(nO(n3

21、3) )立方型立方型 O(2O(2n n) )指数型指数型 O(log2n)O(log2n)对数型对数型O(nlog2n)O(nlog2n)二维型二维型按时间复杂度由小到大排列的频率表为：按时间复杂度由小到大排列的频率表为：时间复杂度曲线时间复杂度曲线 O(1)O(log2n)O(n)O(nlog2n)(n2)O(n3)O(2n) 时间复杂度的求法时间复杂度的求法 计算T(n) 从T(n)中推断f(n)影响算法时间复杂度的因素影响算法时间复杂度的因素 问题的规模 输入实例的初态时间复杂度计算步骤时间复杂度计算步骤 最坏时间复杂度最坏时间复杂度 定义：定义： 算法在最坏情况下的时间复杂度算法在最

22、坏情况下的时间复杂度，即为分析估计算法在最坏情况下执行，即为分析估计算法在最坏情况下执行时间的上界。时间的上界。数据结构-第1章 绪论43例例1 交换i和j的内容 (1) temp=i; (2) i=j; (3) j=temp; 解：T(n)=3 记作T(n)= O(1)数据结构-第1章 绪论44例例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) 算法中存在循环时，通常算法中存在循环时，通常由嵌套层数最深的循环语句的由嵌套层数最深的循环语句的最