《《数据结构绪论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构绪论》PPT课件.ppt（55页珍藏版）》请在金锄头文库上搜索。
1、课程性质课程性质数据结构是计算机专业的专业基础课数据结构是计算机专业的专业基础课 公共基础课、专业基础课、专业方向课、专业选修课公共基础课、专业基础课、专业方向课、专业选修课在教学计划中的地位：核心、承上启下在教学计划中的地位：核心、承上启下 前导课：高等数学、离散数学、程序设计语言前导课：高等数学、离散数学、程序设计语言 后续课：数据库、操作系统、编译原理后续课：数据库、操作系统、编译原理学习目标学习目标掌握基本的数据结构掌握基本的数据结构 工具箱工具箱复用、修改、重组复用、修改、重组培养算法设计能力、程序设计能力培养算法设计能力、程序设计能力 算法算法程序的灵魂程序的灵魂 问题求解过程：问
2、题问题求解过程：问题想法想法算法算法程序程序 程序设计研究的层次：算法程序设计研究的层次：算法方法学方法学语言语言工具工具培养算法分析能力培养算法分析能力 评价算法、改进算法评价算法、改进算法课时分配课时分配理论课理论课 64学时学时实验课实验课 16学时学时集中实训集中实训 24学时学时期末成绩组成期末成绩组成理论课理论课 出勤（迟到、早退）出勤（迟到、早退） 10 课堂表现（提问、纪律）课后作业完成情况课堂表现（提问、纪律）课后作业完成情况 5实验课实验课 出勤（迟到、早退）课堂表现出勤（迟到、早退）课堂表现 5 实验报告实验报告 10期末卷面成绩期末卷面成绩 70实训成绩组成实训成绩组成
3、出勤（迟到、早退）出勤（迟到、早退）+实训表现实训表现 30%实训报告实训报告 70%最终成绩分为以下等级最终成绩分为以下等级： 优秀：优秀：91-100分分 良好：良好：81-90分分 中等：中等：71-80分分 及格：及格：60-70分分 不及格：不及格：0-59分分第第 1 章章 绪绪 论论数据结构的兴起和发展数据结构的兴起和发展数据结构的研究对象数据结构的研究对象 数据结构的基本概念数据结构的基本概念算法及算法分析算法及算法分析本章的基本内容是：本章的基本内容是：1938年出生，年出生，25岁毕业于加州理工岁毕业于加州理工学院数学系，博士毕业后留校任教，学院数学系，博士毕业后留校任教，
4、28岁任副教授。岁任副教授。30岁时，加盟斯坦岁时，加盟斯坦福大学计算机系，任教授。从福大学计算机系，任教授。从31岁岁起，开始出版他的历史性经典巨著：起，开始出版他的历史性经典巨著：The Art of Computer Programming他计划共写他计划共写7卷，然而出版三卷之后，卷，然而出版三卷之后，已震惊世界，使他获得计算机科学已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年界的最高荣誉图灵奖，此时，他年仅仅36岁。岁。数据结构的创始人数据结构的创始人数据结构的创始人数据结构的创始人克努思克努思克努思克努思1.1 数据结构的兴起和发展数据结构的兴起和发展 程序设计的实质
5、是什么程序设计的实质是什么?数据表示数据处理数据表示数据处理数据表示的核心任务：数据表示的核心任务：数据结构的设计；数据结构的设计；数据处理的核心任务：数据处理的核心任务：算法设计；算法设计；数据结构课程主要讨论数据表示和数据处理的基数据结构课程主要讨论数据表示和数据处理的基本问题，也就是数据结构和算法的设计问题；本问题，也就是数据结构和算法的设计问题；结论：数据结构问题起源于程序设计结论：数据结构问题起源于程序设计 数据结构随着程序设计的发展而发展数据结构随着程序设计的发展而发展 数据结构的发展并未终结数据结构的发展并未终结1. 无结构阶段无结构阶段2. 结构化阶段：数据结构算法程序结构化阶
6、段：数据结构算法程序3. 面向对象阶段：面向对象阶段： （数据结构算法）程序（数据结构算法）程序1.1 数据结构的兴起和发展数据结构的兴起和发展 1.2 数据结构的研究对象数据结构的研究对象计算机求解问题计算机求解问题: 问题问题抽象出问题的模型抽象出问题的模型求模型的解求模型的解问题问题数值问题、非数值问题数值问题、非数值问题 数数 值值 问问 题题数学方程数学方程 非数值问题非数值问题数据结构数据结构例例1 学籍管理问题学籍管理问题表结构表结构学号学号姓名姓名性别性别出生日期出生日期政治面貌政治面貌0001王王 军军男男1983/09/02团员团员0002李李 明明男男1982/12/25
7、党员党员0003汤晓影汤晓影女女1984/03/26团员团员1.2 数据结构的研究对象数据结构的研究对象完成什么功能完成什么功能?各表项之间是什么关系？各表项之间是什么关系？例例2 人机对弈问题人机对弈问题树结构树结构1.2 数据结构的研究对象数据结构的研究对象如何实现对弈如何实现对弈?各格局之间是什么关系？各格局之间是什么关系？.例例3 教学计划编排问题教学计划编排问题图结构图结构C4, C5, C6数据库原理数据库原理C7C2, C4计算机原理计算机原理C6C3, C4数据结构数据结构C5C1, C2程序设计程序设计C4C1离散数学离散数学C3无无计算机导论计算机导论C2无无高等数学高等数
8、学C1先修课先修课课程名称课程名称编号编号1.2 数据结构的研究对象数据结构的研究对象C1C2C3C4C6C5C7如何表示课程之间的先修关系？如何表示课程之间的先修关系？ 数据结构是研究数据结构是研究非数值非数值问题中计问题中计算机的算机的操作对象操作对象以及它们之间的以及它们之间的关系关系和和操作操作的学科。的学科。1.2 1.2 数据结构的研究对象数据结构的研究对象1.3 数据结构的基本概念数据结构的基本概念数据数据：所有能：所有能输入输入到计算机中并能被计算机程序到计算机中并能被计算机程序识别识别和处理和处理的符号集合。的符号集合。 数值数据：整数、实数等数值数据：整数、实数等 非数值数
9、据：图形、图象、声音、文字等非数值数据：图形、图象、声音、文字等 数据元素数据元素：数据的：数据的基本基本单位，在计算机程序中通常作单位，在计算机程序中通常作为一个为一个整体整体进行考虑和处理。进行考虑和处理。数据项数据项：构成数据元素的不可分割的最小单位。：构成数据元素的不可分割的最小单位。数据对象数据对象：具有相同：具有相同性质性质的数据元素的集合。的数据元素的集合。 数据结构的基本概念数据结构的基本概念数据、数据元素、数据项之间的关系数据、数据元素、数据项之间的关系包含关系：数据是由数据元素组成，数据元包含关系：数据是由数据元素组成，数据元素是由数据项组成。素是由数据项组成。数据元素数据
10、元素是讨论数据结构时涉及的最小数据是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。单位，其中的数据项一般不予考虑。1.3 数据结构的基本概念数据结构的基本概念数据结构数据结构：相互之间存在一定：相互之间存在一定关系关系的数据元素的集合。的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念关联方式或邻接关系关联方式或邻接关系关联方式或邻接关系关联方式或邻接关系数据
11、的逻辑结构是从具体问题抽象出来的数据的逻辑结构是从具体问题抽象出来的数据模型数据模型学籍管理问题中，表项之间的逻辑关系指的是什么？学籍管理问题中，表项之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？教学计划编排问题中，课程之间的逻辑关系指的是什么？教学计划编排问题中，课程之间的逻辑关系指的是什么？数据结构数据结构：相互之间存在一定：相互之间存在一定关系关系的数据元素的集合。的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑结构：指数据
12、元素之间逻辑关系逻辑关系的整体。的整体。存储结构：又称为物理结构，是数据及其逻辑结构在存储结构：又称为物理结构，是数据及其逻辑结构在计算机计算机中的表示。中的表示。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念内存内存内存内存存储结构实质上是内存分配，存储结构实质上是内存分配，在具体实现时，依赖于计算机语言。在具体实现时，依赖于计算机语言。数据结构从逻辑上分为四类：数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合” ；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构
13、从逻辑上分为四类：数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合” ； 线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类：数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合” ； 线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系； 树结构：数据元素之间存在树结构：数据元素之间存在 着一对多的层
14、次关系；着一对多的层次关系；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类：数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合” ； 线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系； 树结构：数据元素之间存在树结构：数据元素之间存在 着一对多的层次关系；着一对多的层次关系； 图结构：数据元素之间存在图结构：数据元素之间存在 着多对多的任意关系。着多对多的任意关系。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本
15、概念通常有两种存储结构：通常有两种存储结构：1. 顺序存储结构：用一组顺序存储结构：用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元数据元素之间的逻辑关系由元素的素的存储位置存储位置来表示。来表示。batcateat起始地址起始地址例：（例：（bat, cat, eat）1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念通常有两种存储结构：通常有两种存储结构：1. 顺序存储结构：用一组顺序存储结构：用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元数据元素之间的逻辑关系由
16、元素的素的存储位置存储位置来表示。来表示。2. 链接存储结构：用一组链接存储结构：用一组任意任意的存储单元存储数据元素，数的存储单元存储数据元素，数据元素之间的逻辑关系用据元素之间的逻辑关系用指针指针来表示来表示 。例：（例：（bat, cat, eat）1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念0200020803000325 bat0200 cat0325 eat 逻辑结构和存储结构之间的关系逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，是数据的逻辑结构属于用户视图，是面向问题面向问题的，的，反映了数据内部的构成方式；数据的存储结构反映了数
17、据内部的构成方式；数据的存储结构属于具体实现的视图，是属于具体实现的视图，是面向计算机面向计算机的。的。 一种数据的逻辑结构可以用多种存储结构来存一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效储，而采用不同的存储结构，其数据处理的效率往往是不同的。率往往是不同的。 1.3 数据结构的基本概念数据结构的基本概念数据结构的访问接口数据结构的访问接口对数据结构的对数据结构的访问访问是指对数据的读取、修改、是指对数据的读取、修改、加工、处理等操作。加工、处理等操作。数据结构的数据结构的基本操作基本操作：各种应用都能通过这些：各种应用都能通过这些操作实现对数据结构的各种
18、访问。操作实现对数据结构的各种访问。 基本操作的特性：抽象性、基本性、完备性、一般性基本操作的特性：抽象性、基本性、完备性、一般性 访问接口访问接口：操作的调用形式与规范（例如形参：操作的调用形式与规范（例如形参表、返回类型等）。表、返回类型等）。数据结构的访问接口数据结构的访问接口：数据结构基本操作接口：数据结构基本操作接口的全体。的全体。 1.3 数据结构的基本概念数据结构的基本概念抽象数据类型抽象数据类型1. 数据类型数据类型（Data Type）：一组）：一组值值的集合以及定义的集合以及定义于这个值集上的一组于这个值集上的一组操作操作的总称。的总称。 例如：例如：C+中的整型变量中的整
19、型变量 2. 抽象抽象（Abstract）:抽出问题本质的特征而忽略非本抽出问题本质的特征而忽略非本质的细节。质的细节。 例如：例如： 地图、驾驶汽车地图、驾驶汽车3. 抽象数据类型抽象数据类型（Abstract Data Type，ADT）:一个一个数据结构数据结构以及定义在该结构上的以及定义在该结构上的一组操作一组操作的总称。的总称。 1.3 数据结构的基本概念数据结构的基本概念ADT是对数据类型的进一步抽象是对数据类型的进一步抽象 ADT逻逻 辑辑 结结构构操作集合操作集合数据结构数据结构存储结构存储结构算法设计算法设计类类成员变量成员变量成员函数成员函数(a)使用视图使用视图 (b)
20、设计视图设计视图 (c) 实现视图实现视图ADT的定义的定义 ADT的设计的设计 ADT的实现的实现 ADT的不同视图的不同视图1.3 数据结构的基本概念数据结构的基本概念ADT 抽象数据类型名抽象数据类型名Data 数据元素之间逻辑关系的定义数据元素之间逻辑关系的定义Operation 操作操作1 前置条件前置条件：执行此操作前数据所必须的状态：执行此操作前数据所必须的状态 输输 入入：执行此操作所需要的输入：执行此操作所需要的输入 功功 能能：该操作将完成的功能：该操作将完成的功能 输输 出出：执行该操作后产生的输出：执行该操作后产生的输出 后置条件后置条件：执行该操作后数据的状态：执行该
21、操作后数据的状态 操作操作2 操作操作n endADT ADT的定义形式的定义形式1.3 数据结构的基本概念数据结构的基本概念1.3 1.3 数据结构的基本概念（小结）数据结构的基本概念（小结）数据的操作：插入、删除、修改、检索、排序等数据的操作：插入、删除、修改、检索、排序等 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 顺序存储顺序存储链式存储链式存储集合集合线性结构线性结构树结构树结构图结构图结构 非数值问题非数值问题 数数据据表表示示算法的相关概念算法的相关概念1.算算法法（Algorithm）:是是对对特特定定问问题题求求解解步步骤骤的的一种描述，是一种描述，是指令指令
22、的的有限序列有限序列。2. 程序程序（Program）:是对一个算法使用某种程序是对一个算法使用某种程序设计语言的具体实现。设计语言的具体实现。1.4 算法及算法分析算法及算法分析算法的相关概念算法的相关概念3. 算法的五大特性：算法的五大特性： 输入输入：一个算法有零个或多个输入。：一个算法有零个或多个输入。 输出输出：一个算法有一个或多个输出。：一个算法有一个或多个输出。 有穷性有穷性：一个算法必须总是在执行有穷步之后结束，且：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。每一步都在有穷时间内完成。 确定性确定性：算法中的每一条指令必须有确切的含义，对于：算法中的每一条
23、指令必须有确切的含义，对于相同的输入只能得到相同的输出。相同的输入只能得到相同的输出。 可行性可行性：算法描述的操作可以通过已经实现的基本操作：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。执行有限次来实现。1.4 算法及算法分析算法及算法分析什么是好的算法什么是好的算法 一个好的算法具备的其它特性：一个好的算法具备的其它特性： 正确性正确性：对于任何合法输入都会得出正确结果。：对于任何合法输入都会得出正确结果。 鲁棒性鲁棒性：对非法输入的抵抗能力。：对非法输入的抵抗能力。 简单性简单性：算法容易理解和实现。：算法容易理解和实现。 抽象分级抽象分级：算法中的每个模块表示一种抽象。：
24、算法中的每个模块表示一种抽象。 高效性高效性：时间效率和空间效率。：时间效率和空间效率。1.4 算法及算法分析算法及算法分析mnr例：欧几里德算法例：欧几里德算法辗转相除法辗转相除法求两个自然数求两个自然数 m 和和 n 的最大公约数的最大公约数1.4 算法及算法分析算法及算法分析算法的描述方法算法的描述方法自然语言自然语言 优点：容易理解优点：容易理解缺点：冗长、二义性缺点：冗长、二义性使用方法：粗线条描述算法思想使用方法：粗线条描述算法思想 注意事项：避免写成自然段注意事项：避免写成自然段1.4 算法及算法分析算法及算法分析 输入输入m 和和n； 求求m除以除以n的余数的余数r； 若若r等
25、等于于0 0，则则n为为最最大大公公约约数数，算法结束；否则执行第算法结束；否则执行第步；步； 将将n的的值值放放在在m中中，将将r的的值值放放在在n中；中； 重新执行第重新执行第步。步。例：欧几里德算法例：欧几里德算法自然语言1.4 算法及算法分析算法及算法分析优点：流程直观优点：流程直观 缺点：缺少严密性、灵活性缺点：缺少严密性、灵活性使用方法：描述简单算法使用方法：描述简单算法注意事项：注意抽象层次注意事项：注意抽象层次算法的描述方法算法的描述方法流程图流程图 1.4 算法及算法分析算法及算法分析N开始输入m和n r=m % nr=0m=n；n=r 输出n结束Y流 程 图例：欧几里德算法
26、例：欧几里德算法1.4 算法及算法分析算法及算法分析优点：能由计算机执行优点：能由计算机执行 缺点：抽象性差，对语言要求高缺点：抽象性差，对语言要求高使用方法：算法需要验证使用方法：算法需要验证注意事项：将算法写成子函数注意事项：将算法写成子函数算法的描述方法算法的描述方法程序设计语言程序设计语言 1.4 算法及算法分析算法及算法分析#include int CommonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return n;void main( ) coutCommonFactor(63, 54)e
27、ndl;程序设计语言例：欧几里德算法例：欧几里德算法1.4 算法及算法分析算法及算法分析1.1.1.1.4 4 4 4 算法及算法分析算法及算法分析算法及算法分析算法及算法分析伪代码伪代码（Pseudocode）：介于自然语言和）：介于自然语言和程序设计语言之间的方法，它采用某一程序程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自设计语言的基本语法，操作指令可以结合自然语言来设计。然语言来设计。优点：表达能力强，抽象性强，容易理解优点：表达能力强，抽象性强，容易理解算法的描述方法算法的描述方法伪代码伪代码 1.4 算法及算法分析算法及算法分析 1. r = m %
28、n; 2. 循环直到循环直到 r 等于等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出输出 n ;伪 代 码上述伪代码再具体一些，可用上述伪代码再具体一些，可用C+的函数的函数来描述。来描述。例：欧几里德算法例：欧几里德算法1.4 算法及算法分析算法及算法分析算法分析算法分析度量算法效率的方法：度量算法效率的方法： 事后统计事后统计：将算法实现，测算其时间和空间开销。：将算法实现，测算其时间和空间开销。 缺点：缺点： 编写程序实现算法将花费较多的时间和精力；编写程序实现算法将花费较多的时间和精力； 所得实验结果依赖于计算机的软硬件等环境因素。所得实验
29、结果依赖于计算机的软硬件等环境因素。 事事前前分分析析：渐渐进进复复杂杂度度（asymptotic complexity）分析方法，是对算法所消耗资源的一种估算方法。分析方法，是对算法所消耗资源的一种估算方法。1.4 算法及算法分析算法及算法分析算法分析算法分析算算法法分分析析（Algorithm Analysis）：对对算算法法所所需需要要的的计计算机资源算机资源时间时间和和空间空间进行估算。进行估算。 时间复杂性（时间复杂性（Time Complexity） 空间复杂性（空间复杂性（Space Complexity）1.4 算法及算法分析算法及算法分析算法的时间复杂度分析算法的时间复杂度分
30、析1.4 算法及算法分析算法及算法分析算法分析算法分析算法的算法的执行时间执行时间每条语句执行时间之和每条语句执行时间之和执行次数执行次数执行一次的时间执行一次的时间指令系统、编译的代码质量指令系统、编译的代码质量单位时间单位时间每条语句每条语句执行次数执行次数之和之和for (i=1; i=n; i+) for (j=1; j=n; j+) x+;基本语句基本语句的执行的执行次数次数问题规模：问题规模：输入量的多少。输入量的多少。基基本本语语句句：是是执执行行次次数数与与整整个个算算法法的的执执行行次次数数成成正比的操作指令。正比的操作指令。for (i=1; i=n; i+) for (j
31、=1; j=n; j+) x+;问题规模：n基本语句：x+1.4 算法及算法分析算法及算法分析算法分析算法分析定义定义 若存在两个正的常数若存在两个正的常数c和和n0，对于任意对于任意nn0，都有都有T( (n)cf( (n) )，则称则称T( (n) )=O( (f( (n)n0问题规模问题规模n执执行行次次数数n0之之前前的的情情况况无无关关紧要紧要T( (n) )cf( (n) )v当问题规模充分大时当问题规模充分大时T(n)在渐近意义下的阶在渐近意义下的阶1.4 算法及算法分析算法及算法分析算法分析算法分析算法分析算法分析大大O符号符号定定理理：若若A(n)=amnm+am-1nm-1
32、+a1n+a0是是一一个个m次多项式，则次多项式，则A(n)=O(nm)。说明：在计算算法时间复杂度时，可以说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。忽略所有低次幂和最高次幂的系数。1.4 算法及算法分析算法及算法分析算法分析算法分析算法分析算法分析大大O符号符号例例1-5 +x; 例例1-6 for ( (i=1; i=n; +i) ) +x; 例例1-7 for (i=1; i=n; +i) for (j=1; j=n; +j) +x; 例例1-9 for (i=1; i=n; +i) for (j=1; j=i-1; +j) +x;1.4 算法及算法分析算法及算法
33、分析算法分析算法分析算法分析算法分析例例1-8 for (i=1; i=n; +i) for (j=1; j=n; +j) cij=0; for (k=1; k=n; +k) cij+=aik*bkj; 例例1-10 for (i=1; i=n; i=2*i) +x;(1)(log2n)(n)(nlog2n)(n2)(n3) (2n)(n!) 1.4 算法及算法分析算法及算法分析算法分析算法分析算法分析算法分析最好情况、最坏情况、平均情况最好情况、最坏情况、平均情况例：在一维整型数组例：在一维整型数组A n 中顺序查找与给定值中顺序查找与给定值k相等的相等的元素（假设该数组中有且仅有一个元素值
34、为元素（假设该数组中有且仅有一个元素值为k）。 int Find( (int A , int n) ) for ( (i=0; in; i+) ) if ( (Ai= =k) ) break; return i; 1.4 算法及算法分析算法及算法分析基本语句的执行次数是否只和问题规模有关？基本语句的执行次数是否只和问题规模有关？最好情况：出现概率较大时分析最好情况：出现概率较大时分析最差情况：实时系统最差情况：实时系统平均情况：已知输入数据是如何分布的，平均情况：已知输入数据是如何分布的， 通常假设等概率分布通常假设等概率分布结论结论：如果问题规模相同，时间代价与输入数据有：如果问题规模相同，
35、时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。关，则需要分析最好情况、最坏情况、平均情况。1.4 算法及算法分析算法及算法分析最好情况、最坏情况、平均情况最好情况、最坏情况、平均情况算法的空间复杂度分析算法的空间复杂度分析1.4 算法及算法分析算法及算法分析算法分析算法分析算算法法的的空空间间复复杂杂度度是是指指在在算算法法执执行行的的过过程程中中，需需要的辅助空间数量。要的辅助空间数量。辅辅助助空空间间是是除除算算法法本本身身和和输输入入输输出出数数据据所所占占据据的的空间外，算法空间外，算法临时开辟临时开辟的存储空间。的存储空间。通常记作：通常记作： S( (n) )=O( (f( (n)其其中中，n为为问问题题规规模模，分分析析方方法法与与算算法法的的时时间间复复杂杂度类似。度类似。本章小结本章小结知识结构图知识结构图绪绪绪绪 论论论论数据结构数据结构数据结构数据结构算算算算 法法法法基基本本概概念念逻逻辑辑结结构构存存储储结结构构数据数据数据元素数据元素数据对象数据对象ADT逻辑结构逻辑结构数据结构数据结构的分类的分类存储结构存储结构常用存储常用存储方法方法基基本本概概念念算算法法分分析析算法算法算法特性算法特性评价算法评价算法描述算法描述算法问题规模问题规模基本语句基本语句时间复杂度时间复杂度大大O记号记号关关 系系
