数据结构c++(王红梅)课件1--副本.ppt

1、数据结构（数据结构（C版）版）清华大学出版社清华大学出版社主教材主教材王红梅王红梅.数据结构（数据结构（C版）版）.清华大学出版社清华大学出版社辅导及实验教材辅导及实验教材王红梅王红梅.数据结构学习辅导与实验指导数据结构学习辅导与实验指导.清华大学出版社清华大学出版社参考教材参考教材1. 严蔚敏严蔚敏.数据结构数据结构.清华大学出版社清华大学出版社.19972. 王晓东王晓东.数据结构与算法设计数据结构与算法设计.电子工业出版社电子工业出版社.20023. 曹宏庆译曹宏庆译.如何求解问题如何求解问题.中国水利水电出版社中国水利水电出版社.2003关于教材关于教材数据结构（数据结构（C版）版）清

2、华大学出版社清华大学出版社课程性质课程性质 数据结构是计算机专业的专业基础课数据结构是计算机专业的专业基础课 公共基础课、专业基础课、专业方向课、专业选修课公共基础课、专业基础课、专业方向课、专业选修课 在教学计划中的地位：核心、承上启下在教学计划中的地位：核心、承上启下 前导课：高等数学、离散数学、程序设计语言前导课：高等数学、离散数学、程序设计语言 后续课：数据库、操作系统、编译原理后续课：数据库、操作系统、编译原理 属于武术中的属于武术中的“练功练功”科目科目 “练武不练功，到头一场空练武不练功，到头一场空” 考研考研数据结构（数据结构（C版）版）清华大学出版社清华大学出版社学习目标学习

3、目标掌握基本的数据结构掌握基本的数据结构 工具箱工具箱复用、修改、重组复用、修改、重组培养算法设计能力、程序设计能力培养算法设计能力、程序设计能力 算法算法程序的灵魂程序的灵魂 问题求解过程：问题问题求解过程：问题想法想法算法算法程序程序 程序设计研究的层次：算法程序设计研究的层次：算法方法学方法学语言语言工具工具培养算法分析能力培养算法分析能力 评价算法、改进算法评价算法、改进算法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社学习要求学习要求 循序渐进，切忌心浮气躁循序渐进，切忌心浮气躁 提高课外学习的时间和内容提高课外学习的时间和内容 理解科学而不是背诵科学理解科学而不是背诵科

4、学读书读书 正确对待考试正确对待考试 作习题作习题 华罗庚：华罗庚：“学数学不做习题等于入宝山而空返学数学不做习题等于入宝山而空返” 作实验作实验 计算机学科是一门科学性与工程性并重的学科，计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。表现为理论和实践紧密结合的特征。 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何使用立体化教材如何使用立体化教材 主教材主教材 思想火花、人物小传思想火花、人物小传 辅导教材辅导教材 知识结构、学习要点、重点难点释疑、习知识结构、学习要点、重点难点释疑、习题解析题解析 实验教材实验教材 验证实验验证实验综合实验综合实验

5、设计实验设计实验 网站网站 学校精品课程网站学校精品课程网站数据结构（数据结构（C版）版）清华大学出版社清华大学出版社成绩组成成绩组成 实验成绩实验成绩 30：出勤程序报告：出勤程序报告 期末考试成绩期末考试成绩 70：接近同类学校考研水平：接近同类学校考研水平 课程设计课程设计 成绩：优、良、中、及、不及成绩：优、良、中、及、不及数据结构（数据结构（C版）版）清华大学出版社清华大学出版社第第 1 章章 绪绪 论论数据结构的兴起和发展数据结构的兴起和发展数据结构的研究对象数据结构的研究对象 数据结构的基本概念数据结构的基本概念算法及算法分析算法及算法分析本章的基本内容是：本章的基本内容是：数据

6、结构（数据结构（C版）版）清华大学出版社清华大学出版社1938年出生，年出生，25岁毕业于加州理工岁毕业于加州理工学院数学系，博士毕业后留校任教，学院数学系，博士毕业后留校任教，28岁任副教授。岁任副教授。30岁时，加盟斯坦岁时，加盟斯坦福大学计算机系，任教授。从福大学计算机系，任教授。从31岁岁起，开始出版他的历史性经典巨著：起，开始出版他的历史性经典巨著：The Art of Computer Programming他计划共写他计划共写7卷，然而出版三卷之后，卷，然而出版三卷之后，已震惊世界，使他获得计算机科学已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年界的最高荣誉图灵奖，

7、此时，他年仅仅36岁。岁。数据结构的创始人数据结构的创始人克努特克努特数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.1 数据结构的兴起和发展数据结构的兴起和发展 程序设计的实质是什么程序设计的实质是什么?数据表示：数据表示：将数据存储在计算机中将数据存储在计算机中数据处理：数据处理：处理数据，求解问题处理数据，求解问题数据结构问题起源于程序设计数据结构问题起源于程序设计 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 数据结构随着程序设计的发展而发展数据结构随着程序设计的发展而发展 数据结构的发展并未终结数据结构的发展并未终结1. 无结构阶段无结构阶段2. 结构化阶

8、段：数据结构算法程序结构化阶段：数据结构算法程序3. 面向对象阶段：面向对象阶段： （数据结构算法）程序（数据结构算法）程序1.1 数据结构的兴起和发展数据结构的兴起和发展 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.2 数据结构的研究对象数据结构的研究对象 计算机求解问题计算机求解问题: 问题问题抽象出问题的模型抽象出问题的模型求模型的解求模型的解 问题问题数值问题、非数值问题数值问题、非数值问题 数数 值值 问问 题题数学方程数学方程 非数值问题非数值问题数据结构数据结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例例1 学籍管理问题学籍管理问题表结构表结构

9、学号学号姓名姓名性别性别出生日期出生日期政治面貌政治面貌0001王王 军军男男1983/09/02团员团员0002李李 明明男男1982/12/25党员党员0003汤晓影汤晓影女女1984/03/26团员团员1.2 数据结构的研究对象数据结构的研究对象完成什么功能完成什么功能?各表项之间是什么关系？各表项之间是什么关系？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例例2 人机对弈问题人机对弈问题树结构树结构1.2 数据结构的研究对象数据结构的研究对象如何实现对弈如何实现对弈?各格局之间是什么关系？各格局之间是什么关系？.数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例

10、例3 教学计划编排问题教学计划编排问题图结构图结构C4, C5, C6数据库原理数据库原理C7C2, C4计算机原理计算机原理C6C3, C4数据结构数据结构C5C1, C2程序设计程序设计C4C1离散数学离散数学C3无无计算机导论计算机导论C2无无高等数学高等数学C1先修课先修课课程名称课程名称编号编号1.2 数据结构的研究对象数据结构的研究对象C1C2C3C4C6C5C7如何表示课程之间的先修关系？如何表示课程之间的先修关系？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 数据结构是研究数据结构是研究非数值非数值问题中计问题中计算机的算机的操作对象操作对象以及它们之间的以及它们

11、之间的关系关系和和操作操作的学科。的学科。1.2 1.2 数据结构的研究对象数据结构的研究对象数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.3 数据结构的基本概念数据结构的基本概念数据数据：所有能：所有能输入输入到计算机中并能被计算机程序到计算机中并能被计算机程序识识别和处理别和处理的符号集合。的符号集合。 数值数据：整数、实数等数值数据：整数、实数等 非数值数据：图形、图象、声音、文字等非数值数据：图形、图象、声音、文字等 数据元素数据元素：数据的：数据的基本基本单位，在计算机程序中通常单位，在计算机程序中通常作为一个作为一个整体整体进行考虑和处理。进行考虑和处理。数据项数据

12、项：构成数据元素的不可分割的最小单位。：构成数据元素的不可分割的最小单位。数据对象数据对象：具有相同：具有相同性质性质的数据元素的集合。的数据元素的集合。 数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据、数据元素、数据项之间的关系数据、数据元素、数据项之间的关系包含关系：数据是由数据元素组成，数据包含关系：数据是由数据元素组成，数据元素是由数据项组成。元素是由数据项组成。数据元素数据元素是讨论数据结构时涉及的最小数是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。据单位，其中的数据项一般不予考虑。1.3 数据结构的基本概念数据结构

13、的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构数据结构：相互之间存在一定：相互之间存在一定关系关系的数据元素的集合。的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据的逻辑结构是从具体问题抽象出来的数据的逻辑结构是从具体问题抽象出来的数据模型数据模型学籍管理问题中，表项之间的逻辑关系指的是什么？学籍管理问题中，表项之间的逻辑关系指的是什么？

14、人机对弈问题中，格局之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？教学计划编排问题中，课程之间的逻辑关系指的是什么？教学计划编排问题中，课程之间的逻辑关系指的是什么？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构数据结构：相互之间存在一定：相互之间存在一定关系关系的数据元素的集合。的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。存储结构：又称为物理结构，是数据及其逻辑结构在存储结构：又称为物理结构，是数据

15、及其逻辑结构在计算机计算机中的表示。中的表示。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念存储结构实质上是内存分配，存储结构实质上是内存分配，在具体实现时，依赖于计算机语言。在具体实现时，依赖于计算机语言。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构从逻辑上分为四类：数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合” ；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构从逻辑上分为四类：

16、数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合” ； 线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构从逻辑上分为四类：数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合” ； 线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系； 树结构：数据元素之间存

17、在树结构：数据元素之间存在 着一对多的层次关系；着一对多的层次关系；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构从逻辑上分为四类：数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合” ； 线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系； 树结构：数据元素之间存在树结构：数据元素之间存在 着一对多的层次关系；着一对多的层次关系； 图结构：数据元素之间存在图结构：数据元素之间存在 着多对多的任意关系

18、。着多对多的任意关系。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社通常有两种存储结构：通常有两种存储结构：1. 顺序存储结构：用一组顺序存储结构：用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元数据元素之间的逻辑关系由元素的素的存储位置存储位置来表示。来表示。batcateat起始地址起始地址例：（例：（bat, cat, eat）1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社

19、清华大学出版社通常有两种存储结构：通常有两种存储结构：1. 顺序存储结构：用一组顺序存储结构：用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元数据元素之间的逻辑关系由元素的素的存储位置存储位置来表示。来表示。2. 链接存储结构：用一组链接存储结构：用一组任意任意的存储单元存储数据元素，数的存储单元存储数据元素，数据元素之间的逻辑关系用据元素之间的逻辑关系用指针指针来表示来表示 。例：（例：（bat, cat, eat）1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念0200020803000325 bat0200

20、cat0325 eat 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社逻辑结构和存储结构之间的关系逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，是数据的逻辑结构属于用户视图，是面向问题面向问题的，的，反映了数据内部的构成方式；数据的存储结构反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是属于具体实现的视图，是面向计算机面向计算机的。的。 一种数据的逻辑结构可以用多种存储结构来存一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效储，而采用不同的存储结构，其数据处理的效率往往是不同的。率往往是不同的。 1.3 数据结构的基本概念数

21、据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构的访问接口数据结构的访问接口 对数据结构的对数据结构的访问访问是指对数据的读取、修改、是指对数据的读取、修改、加工、处理等操作。加工、处理等操作。 数据结构的数据结构的基本操作基本操作：各种应用都能通过这些：各种应用都能通过这些操作实现对数据结构的各种访问。操作实现对数据结构的各种访问。 基本操作的特性：抽象性、基本性、完备性、一般性基本操作的特性：抽象性、基本性、完备性、一般性 访问接口访问接口：操作的调用形式与规范（例如形参：操作的调用形式与规范（例如形参表、返回类型等）。表、返回类型等）。 数据结构的访问接

22、口数据结构的访问接口：数据结构基本操作接口：数据结构基本操作接口的全体。的全体。 1.3 数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社抽象数据类型抽象数据类型1. 数据类型数据类型（Data Type）：一组）：一组值值的集合以及定义的集合以及定义于这个值集上的一组于这个值集上的一组操作操作的总称。的总称。 例如：例如：C+中的整型变量中的整型变量 2. 抽象抽象（Abstract）:抽出问题本质的特征而忽略非抽出问题本质的特征而忽略非本质的细节。本质的细节。 例如：例如： 地图、驾驶汽车地图、驾驶汽车3. 抽象数据类型抽象数据类型（Abstr

23、act Data Type，ADT）:一个一个数据结构数据结构以及定义在该结构上的以及定义在该结构上的一组操作一组操作的总称。的总称。 1.3 数据结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ADT是对数据类型的进一步抽象是对数据类型的进一步抽象 ADT逻辑结构逻辑结构操作集合操作集合数据结构数据结构存储结构存储结构算法设计算法设计类类成员变量成员变量成员函数成员函数(a)使用视图使用视图 (b) 设计视图设计视图 (c) 实现视图实现视图ADT的定义的定义 ADT的设计的设计 ADT的实现的实现 ADT的不同视图的不同视图1.3 数据结构的基本概

24、念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ADT 抽象数据类型名抽象数据类型名Data 数据元素之间逻辑关系的定义数据元素之间逻辑关系的定义Operation 操作操作1 前置条件前置条件：执行此操作前数据所必须的状态：执行此操作前数据所必须的状态 输输 入入：执行此操作所需要的输入：执行此操作所需要的输入 功功 能能：该操作将完成的功能：该操作将完成的功能 输输 出出：执行该操作后产生的输出：执行该操作后产生的输出 后置条件后置条件：执行该操作后数据的状态：执行该操作后数据的状态 操作操作2 操作操作n endADT ADT的定义形式的定义形式1.3 数据

25、结构的基本概念数据结构的基本概念数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.3 1.3 数据结构的基本概念（小结）数据结构的基本概念（小结）数据的操作：插入、删除、修改、检索、排序等数据的操作：插入、删除、修改、检索、排序等 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 顺序存储顺序存储链式存储链式存储集合集合线性结构线性结构树结构树结构图结构图结构 非数值问题非数值问题 数数据据表表示示数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.算法算法（Algorithm）:是对是对特定问题特定问题求解步骤的求解步骤的一种描述，是一种描述，是指令指令的的有

26、限序列有限序列。2. 算法的五大特性：算法的五大特性： 输入输入：一个算法有零个或多个输入。：一个算法有零个或多个输入。 输出输出：一个算法有一个或多个输出。：一个算法有一个或多个输出。 有穷性有穷性：一个算法必须总是在执行有穷步之后结束，且：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。每一步都在有穷时间内完成。 确定性确定性：算法中的每一条指令必须有确切的含义，对于：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。相同的输入只能得到相同的输出。 可行性可行性：算法描述的操作可以通过已经实现的基本操作：算法描述的操作可以通过已经实现的基本操作执行有限

27、次来实现。执行有限次来实现。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 欧几里德算法mnr例：欧几里德算法例：欧几里德算法辗转相除法辗转相除法求两个自然数求两个自然数 m 和和 n 的最大公约数的最大公约数数据结构（数据结构（C版）版）清华大学出版社清华大学出版社算法的描述方法算法的描述方法自然语言自然语言 优点：容易理解优点：容易理解缺点：冗长、二义性缺点：冗长、二义性使用方法：粗线条描述算法思想使用方法：粗线条描述算法思想 注意事项：避免写成自然段注意事项：避免写成自然段数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 输入输入m 和和n； 求求m除以除以n的余数

28、的余数r； 若若r等于等于0 0，则，则n为最大公约数，为最大公约数，算法结束；否则执行第步；算法结束；否则执行第步； 将将n的值放在的值放在m中，将中，将r的值放的值放在在n中；中； 重新执行第步。重新执行第步。例：欧几里德算法例：欧几里德算法自然语言数据结构（数据结构（C版）版）清华大学出版社清华大学出版社优点：流程直观优点：流程直观 缺点：缺少严密性、灵活性缺点：缺少严密性、灵活性使用方法：描述简单算法使用方法：描述简单算法注意事项：注意抽象层次注意事项：注意抽象层次算法的描述方法算法的描述方法流程图流程图 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社N开始输入m和n r=

29、m % nr=0m=n；n=r 输出n结束Y流 程 图例：欧几里德算法例：欧几里德算法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社优点：能由计算机执行优点：能由计算机执行 缺点：抽象性差，对语言要求高缺点：抽象性差，对语言要求高使用方法：算法需要验证使用方法：算法需要验证注意事项：将算法写成子函数注意事项：将算法写成子函数算法的描述方法算法的描述方法程序设计语言程序设计语言 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社#include int CommonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r;

30、 r=m % n; return n;void main( ) coutCommonFactor(63, 54)endl;程序设计语言例：欧几里德算法例：欧几里德算法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构（数据结构（C版）版）清华大学出版社清华大学出版社伪代码伪代码（Pseudocode）：介于自然语言和）：介于自然语言和程序设计语言之间的方法，它采用某一程序程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自设计语言的基本语法，操作指令可以结合自然语言来设计。然语言来设计。优点：表达能力强，抽象性强，容易理解优点：表达能力强，抽象性强，容易

31、理解算法的描述方法算法的描述方法伪代码伪代码 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 1. r = m % n; 2. 循环直到循环直到 r 等于等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出输出 n ;伪 代 码上述伪代码再具体一些，用上述伪代码再具体一些，用C+的函数来的函数来描述。请同学们自行完成！描述。请同学们自行完成！例：欧几里德算法例：欧几里德算法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社度量算法效率的方法：度量算法效率的方法： 事后统计事后统计：将算法实现，测算其时间和空间开销。：将算法实现，测算其

32、时间和空间开销。 缺点：缺点： 编写程序实现算法将花费较多的时间和精力；编写程序实现算法将花费较多的时间和精力； 所得实验结果依赖于计算机的软硬件等环境因素。所得实验结果依赖于计算机的软硬件等环境因素。 事前分析事前分析：对算法所消耗资源的一种估算方法。：对算法所消耗资源的一种估算方法。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社算法分析算法分析（Algorithm Analysis）：对算法所需要的）：对算法所需要的计算机资源计算机资源时间时间和和空间空间进行估算。进行估算。 时间复杂性（时间复杂性（Time Complexity） 空间复杂性（空间复杂性（Space Comp

33、lexity）数据结构（数据结构（C版）版）清华大学出版社清华大学出版社算法的时间复杂度分析算法的时间复杂度分析算法的算法的执行时间执行时间每条语句执行时间之和每条语句执行时间之和执行次数执行次数执行一次的时间执行一次的时间指令系统、编译的代码质量指令系统、编译的代码质量单位时间单位时间每条语句每条语句执行次数执行次数之和之和for (i=1; i=n; i+) for (j=1; j=n; j+) x+;基本语句基本语句的执行次数的执行次数数据结构（数据结构（C版）版）清华大学出版社清华大学出版社问题规模：问题规模：输入量的多少。输入量的多少。基本语句：基本语句：是执行次数与整个算法的执行次

34、是执行次数与整个算法的执行次数成数成正比的操作指令。正比的操作指令。for (i=1; i=n; i+) for (j=1; j=n; j+) x+;问题规模：n基本语句：x+数据结构（数据结构（C版）版）清华大学出版社清华大学出版社定义定义 若存在两个正的常数若存在两个正的常数c和和n0，对于任意对于任意nn0，都有都有T( (n)cf( (n) )，则称则称T( (n) )=O( (f( (n)n0问题规模问题规模n执执行行次次数数n0之前的之前的情况无关情况无关紧要紧要T( (n) )cf( (n) )v当问题规模充分大时在渐近意义下的阶当问题规模充分大时在渐近意义下的阶大大O符号符号数

35、据结构（数据结构（C版）版）清华大学出版社清华大学出版社定理：若定理：若A(n)=amnm+am-1nm-1+a1n+a0是一个是一个m次多项式，则次多项式，则A(n)=O(nm)。说明：在计算算法时间复杂度时，可以说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。忽略所有低次幂和最高次幂的系数。大大O符号符号数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例例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-8 for (i=1;

36、i=n; +i) for (j=1; j=i-1; +j) +x;数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例例1-9 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!) 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社最好情况、最坏情况、平均情况最好情况、最坏情况、平均情况例：在一维整型数组例：在一维整型数组A n 中顺序查

37、找与给定值中顺序查找与给定值k相等相等的元素（假设该数组中有且仅有一个元素值为的元素（假设该数组中有且仅有一个元素值为k）。 int Find( (int A , int n) ) for ( (i=0; in; i+) ) if ( (Ai= =k) ) break; return i; 基本语句的执行次数是否只和问题规模有关？基本语句的执行次数是否只和问题规模有关？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社最好情况：出现概率较大时分析最好情况：出现概率较大时分析最差情况：实时系统最差情况：实时系统平均情况：已知输入数据是如何分布的，平均情况：已知输入数据是如何分布的， 通常

38、假设等概率分布通常假设等概率分布结论结论：如果问题规模相同，时间代价与输入数据有：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。关，则需要分析最好情况、最坏情况、平均情况。最好情况、最坏情况、平均情况最好情况、最坏情况、平均情况数据结构（数据结构（C版）版）清华大学出版社清华大学出版社绪绪 论论数据结构数据结构算算 法法基基本本概概念念逻逻辑辑结结构构存存储储结结构构数据数据数据元素数据元素数据对象数据对象ADT逻辑结构逻辑结构数据结构数据结构的分类的分类存储结构存储结构常用存储常用存储方法方法基基本本概概念念算算法法分分析析算法算法算法特性算法特性评价算法

39、评价算法描述算法描述算法问题规模问题规模基本语句基本语句时间复杂度时间复杂度大大O记号记号关关 系系数据结构（数据结构（C版）版）清华大学出版社清华大学出版社作业：作业：公元公元5世纪末，我国古代数学家张丘建在它所撰定的世纪末，我国古代数学家张丘建在它所撰定的算经中，提出这样一个问题：算经中，提出这样一个问题：“鸡翁一，值钱五鸡翁一，值钱五；鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，；鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、母、雏各几何？问鸡翁、母、雏各几何？”意思是说公鸡每只意思是说公鸡每只5元，元，母鸡每只母鸡每只3元，小鸡元，小鸡3只只1元，用元，用100元钱买元钱买100只鸡，只鸡，求公鸡、母鸡、小鸡的只数。试设计算法求解该问题求公鸡、母鸡、小鸡的只数。试设计算法求解该问题，并分析你所设计的算法的时间复杂度。（要求：算，并分析你所设计的算法的时间复杂度。（要求：算法分别用伪代码和法分别用伪代码和C描述）描述）