《数据结构(C语言版)ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言版)ppt课件.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能总学时：总学时：32 讲课学时：讲课学时：24教材：数据结构教材：数据结构C语言版严蔚敏、吴伟民语言版严蔚敏、吴伟民 -清华大学出版社清华大学出版社 数据结构题集严蔚敏，数据结构题集严蔚敏，清华大学出版社清华大学出版社参考书：参考书：数据结构（用面向对象方法与数据结构（用面向对象方法与C+描述），殷人描述），殷人昆等，清华大学出版社昆等，清华大学出版社辅导辅导每周五下午每周五下午：信息科技大厦：信息科技大厦1901课程安排课程安排1为深入学习习近平新时代中国特色社会主义思想和党的十九大
2、精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能v编程基础编程基础v考研课程考研课程v计算机等级考试课程计算机等级考试课程v程序员考试课程程序员考试课程课程重要性课程重要性2为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第一章第一章 绪论绪论1.1 数据结构的概念数据结构的概念1.2 基本概念和术语基本概念和术语1.3 抽象数据类型抽象数据类型1.4 算法和算法分析算法和算法分析3为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&为什么要学习数据结构？为什么要学
3、习数据结构？&什么是程序、软件？什么是程序、软件？N.N.沃思（沃思（NiklausNiklaus Wirth)Wirth)教授提出：教授提出：1.1 数据结构的概念数据结构的概念程序程序=算法算法+数据结构数据结构 以上公式说明了如下两个问题：以上公式说明了如下两个问题：(1)(1)数据上的算法决定如何构造和组织数据数据上的算法决定如何构造和组织数据(算法算法数据结构数据结构)(2)(2)算法的选择依赖于作为基础的数据结构算法的选择依赖于作为基础的数据结构(数据结构数据结构算法算法)。软件软件=程序程序+文档（软件工程的观点）文档（软件工程的观点）4为深入学习习近平新时代中国特色社会主义思想
4、和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&电子计算机的主要用途：电子计算机的主要用途：早期：早期：主要用于数值计算。主要用于数值计算。后来：后来：处理逐渐扩大到非数值计算领域（能处理多种复杂处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。的具有一定结构关系的数据）。1.1 数据结构的概念数据结构的概念5为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&数值计算解决问题的一般步骤：数值计算解决问题的一般步骤：数学模型数学模型选择计算机语言选择计算机语言编出程序编出程序测试测试最最终解
5、答。终解答。数值计算的关键是：如何得出数学模型（方程）？数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。程序设计人员比较关注程序设计的技巧。&非数值计算问题：非数值计算问题：数据元素之间的相互关系一般无法用数学方程加以数据元素之间的相互关系一般无法用数学方程加以描述描述1.1 数据结构的概念数据结构的概念6为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例例 书目自动检索系统书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表7为深
6、入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能树.例例 井字棋井字棋8为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 例例 电话号码查询问题：电话号码查询问题：（1 1）按顺序存储方式：须遍历表）按顺序存储方式：须遍历表（2 2）按姓氏索引方式：）按姓氏索引方式：索引索引 要写出好的查找算法，取决于这张表的结构及存要写出好的查找算法，取决于这张表的结构及存储方式。储方式。电话号码表的结构和存储方式决定了查找（算法）电话号码表的结构和存储方式决定了查找（算法）的效率。的效率
7、。非数值计算问题：非数值计算问题：1.1 数据结构的概念数据结构的概念9为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例例 多叉路口交通灯管理问题多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图10为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 例例 田径赛的时间安排问题（无向图的着色问题）田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，设有六个比赛项目，规定每个选手至多可参加三个项目，
8、有五人报名参加比赛（如下表所示）设计比赛日程表，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。使得在尽可能短的时间内完成比赛。1.1 数据结构的概念数据结构的概念 非数值计算问题：非数值计算问题：11为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(1)设用如下六个不同的代号代表不同的项目：设用如下六个不同的代号代表不同的项目：跳高跳高 跳远跳远 标枪标枪 铅球铅球 100米米 200米米 A B C D E F(2)用顶点代表比赛项目用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。不能同
9、时进行比赛的项目之间连上一条边。(3)某选手比赛的项目必定有边相连某选手比赛的项目必定有边相连(不能同时比赛不能同时比赛)。非数值计算问题：非数值计算问题：-田径赛的时间安排问题解法田径赛的时间安排问题解法1.1 数据结构的概念数据结构的概念12为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能姓名姓名项目项目1项目项目2项目项目3丁一丁一 A B E马二马二 C D 张三张三 C E F李四李四 D F A王五王五 B FAEBFDC比赛时间比赛项目1A，C2B，D3E4F 只需安排四个单位时间进行比赛13为深入学习习近平新时代中国
10、特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能v在应用程序中涉及到各种各样的数据，如何在计在应用程序中涉及到各种各样的数据，如何在计算机中组织、存储、传递数据，需要讨论它们的算机中组织、存储、传递数据，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结归类及它们之间的关系，从而建立相应的数据结构，依此实现软件功能。构，依此实现软件功能。v综上，综上，描述这类非数值计算问题的数学模型不是描述这类非数值计算问题的数学模型不是数学方程数学方程,而是树、表和图之类的数据结构。而是树、表和图之类的数据结构。v因此从广义上讲，因此从广义上讲，数据结构描述现实世界
11、实体的数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现数学模型及其上的操作在计算机中的表示和实现.1.1 数据结构的概念数据结构的概念14为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&求解非数值计算的问题：求解非数值计算的问题：主要考虑的是设计出合适的数据结构及相应的算法。主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑即：首先要考虑对相关的各种信息如何表示、组织和对相关的各种信息如何表示、组织和存储？存储？因此，可以认为：因此，可以认为：数据结构数据结构是一门研究非数值计算是一门研究非数值计算的
12、程序设计问题中计算机的操作对象以及它们之间的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。的关系和操作的学科。1.1 数据结构的概念数据结构的概念15为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&数据结构课程的形成和发展：数据结构课程的形成和发展：形成阶段：形成阶段：6060年代初期，年代初期，“数据结构数据结构”有关的内容散见于操作有关的内容散见于操作系统、编译原理和表处理语言等课程。系统、编译原理和表处理语言等课程。19681968年，年，“数据结构数据结构”被列入美国一些大学计算机科学系的教被列入美国一些大
13、学计算机科学系的教学计划。学计划。发展阶段：发展阶段：数据结构的概念不断扩充，包括了网络、集合代数数据结构的概念不断扩充，包括了网络、集合代数论、关系等论、关系等“离散数学结构离散数学结构”的内容。的内容。7070年代后期，我国高校陆续开设该课程。年代后期，我国高校陆续开设该课程。1.1 数据结构的概念数据结构的概念16为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&数据结构课程数据结构课程 所处的地位：所处的地位：1.1 数据结构的概念数据结构的概念17为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会
14、精神,充分发挥中小学图书室育人功能数据数据(Data):对信息的一种符号表示。在计算机科学中是指所有对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总能输入到计算机中并被计算机程序处理的符号的总称。称。数值型数据数值型数据非数值型数据非数值型数据1.2 基本概念和术语基本概念和术语18为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能数据元素数据元素(Data Element):数据的数据的基本单位基本单位，在计算机程序中通常作为一个，在计算机程序中通常作为一个整体进行考虑和处理。整体进行考虑和处
15、理。一个数据元素可由若干个一个数据元素可由若干个数据项数据项组成。数据项组成。数据项是数据的不可分割的是数据的不可分割的最小标识单位最小标识单位。1.2 基本概念和术语基本概念和术语职职位位业业绩绩入队入队日期日期出生日期出生日期年年 月月 日日 俱乐俱乐部名部名称称姓姓名名19为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能数据对象数据对象(Data Object)：性质相同的数据元素的集合。是数据的一个子集。性质相同的数据元素的集合。是数据的一个子集。u整数数据对象整数数据对象 N=0,1,2,u字母字符数据对象字母字符数据对象
16、C=A,B,C,F 1.2 基本概念和术语基本概念和术语20为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&定义定义1-是相互之间存在一种或多种特定关系的数据元素的集是相互之间存在一种或多种特定关系的数据元素的集合。合。&定义定义2-按某种逻辑关系按某种逻辑关系组织起来的一批数据（或称带结构的组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并数据元素的集合）应用计算机语言并按一定的存储表按一定的存储表示示 方式方式把它们存储在计算机的存储器中，并把它们存储在计算机的存储器中，并在其上定在其上定义了一个运算的集合。义了
17、一个运算的集合。什么是数据结构什么是数据结构21为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&数据结构的三个方面的含义：数据结构的三个方面的含义：逻辑结构逻辑结构-数据元素间抽象化的相互关系（简称为数据结构）。数据元素间抽象化的相互关系（简称为数据结构）。与数据的存储无关，独立于计算机，它是从具体问题抽与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。象出来的数学模型。存储结构存储结构（物理结构）（物理结构）-数据元素及其关系在计算机存储器中的存储方式。数据元素及其关系在计算机存储器中的存储方式。是逻辑结构用计算
18、机语言的实现，它依赖于计算机语言。是逻辑结构用计算机语言的实现，它依赖于计算机语言。运算运算（算法）（算法）1.2 基本概念和术语基本概念和术语22为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：1.2 基本概念和术语基本
19、概念和术语23为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&数据结构数据结构3 3方面含义之方面含义之逻辑结构逻辑结构&逻辑结构逻辑结构-划分方法一划分方法一（1 1）线性结构线性结构-有且仅有一个开始和一个终端结点，并且所有结点有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。都最多只有一个直接前趋和一个后继。例如：线性表、栈、队列、串例如：线性表、栈、队列、串（2 2）非线性结构非线性结构-一个结点可能有多个直接前趋和直接后继。一个结点可能有多个直接前趋和直接后继。例如：树、图、多维数组、广义表等
20、。例如：树、图、多维数组、广义表等。1.2 基本概念和术语基本概念和术语24为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&逻辑结构逻辑结构-划分方法二划分方法二一、一、集合集合：结构中的数据元素除了同属于一种类型：结构中的数据元素除了同属于一种类型外，别无其它关系。外，别无其它关系。二、二、线性结构线性结构：结构中的数据元素之间存在一对一：结构中的数据元素之间存在一对一的关系，如线性表、栈、队列。的关系，如线性表、栈、队列。三、三、树型结构树型结构：结构中的数据元素之间存在一对多：结构中的数据元素之间存在一对多的关系，如树。的关
21、系，如树。四、四、图状结构或网状结构图状结构或网状结构：结构中的数据元素之间：结构中的数据元素之间存在多对多的关系，如图。存在多对多的关系，如图。1.2 基本概念和术语基本概念和术语25为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能四个基本结构四个基本结构集合集合线性结构线性结构树形结构树形结构 网状结构网状结构26为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能bindevetclibuser21141312112346789103158710119987456623
22、1315 5线性结构线性结构树形结构树形结构 树树 二叉树二叉树 二叉排序树二叉排序树27为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能堆结构堆结构123548711102916125643125436113318146651921图结构图结构 网络结构网络结构28为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&数据结构数据结构3方面含义之方面含义之存储结构存储结构l存储结构两方面的内容：存储结构两方面的内容：（1）数据元素自身值的表示（数据域）数据元素自身值的表示（
23、数据域）（2）该结点与其它结点关系的域（链域）该结点与其它结点关系的域（链域）l四种基本的存储方法：四种基本的存储方法：（1）顺序存储方法（结构）顺序存储方法（结构）（2）链接存储方法（链式存储结构）链接存储方法（链式存储结构）（3）索引存储方法）索引存储方法（4）散列存储方法）散列存储方法 同一种逻辑结构可采用不同的存储方法（以上四种之一或组同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。合），这主要考虑的是运算方便及算法的时空要求。1.2 基本概念和术语基本概念和术语29为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教
24、育大会精神,充分发挥中小学图书室育人功能元素元素n.元素元素i.元素元素2元素元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储30为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1536元素元素21400元素元素11346元素元素3 元素元素41345h存储地址存储地址 存储内容存储内容 指针指针 1345 元素元素1 1400 1346 元素元素4 .1400 元素元素2 1536 .1536 元素元素3 1346 链式存储链式存储
25、 h31为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&逻辑结构存储结构小结：逻辑结构存储结构小结：（1）数据的逻辑结构、存储结构和数据的运算（）数据的逻辑结构、存储结构和数据的运算（算算法法）构成了数据结构三个方面的含义。）构成了数据结构三个方面的含义。（2）程序设计的实质是对实际问题选择一个好的数）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。很大程度上取决于描述实际问题的数据结构。1.2 基本概念和术语基本概
26、念和术语32为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1.3 抽象数据类型抽象数据类型(ADT)数据类型：数据类型：在一种程序设计语言中，变量所具有的数在一种程序设计语言中，变量所具有的数据种类。据种类。例例1、在在FORTRAN语言中，变量的数据类型有整型、语言中，变量的数据类型有整型、实型、和复数型实型、和复数型 例例2、在、在C语言中语言中数据类型：基本类型和构造类型数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定构造类型：数组、结构、
27、联合、指针、枚举型、自定义义33为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1.3 抽象数据类型抽象数据类型(ADT)抽象数据类型抽象数据类型是是指指一一个个数数学学模模型型以以及及定定义义在在此此数数学学模模型型上上的的一一组操作组操作数数据据结结构构+定定义义在在此此数数据据结结构构上上的的一一组组操操作作=抽抽象数据类型象数据类型 例例如如：矩矩阵阵+（求求转转置置、加加、乘乘、求求逆逆、求求特特征征值）值）构成一个矩阵的抽象数据类型构成一个矩阵的抽象数据类型 34为深入学习习近平新时代中国特色社会主义思想和党的十九大精神
28、,贯彻全国教育大会精神,充分发挥中小学图书室育人功能抽象数据类型的描述抽象数据类型的描述抽象数据类型可用（抽象数据类型可用（D，S，P）三元组表示三元组表示其其中中，D是是数数据据对对象象，S是是D上上的的关关系系集集，P是是对对D的的基基本操作集。本操作集。ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 基本操作：基本操作的定义基本操作：基本操作的定义 ADT 抽象数据类型名抽象数据类型名1.3 抽象数据类型抽象数据类型(ADT)35为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教
29、育大会精神,充分发挥中小学图书室育人功能其中其中,数据对象、数据关系用伪码描述；基本操作定义格式为数据对象、数据关系用伪码描述；基本操作定义格式为基本操作名（参数表）基本操作名（参数表）初始条件：初始条件描述初始条件：初始条件描述操作结果：操作结果描述操作结果：操作结果描述l基基本本操操作作有有两两种种参参数数：赋赋值值参参数数只只为为操操作作提提供供输输入入值值；引引用用参数以参数以&打头，打头，除可提供输入值外，还将返回操作结果。除可提供输入值外，还将返回操作结果。l “初初始始条条件件”描描述述了了操操作作执执行行之之前前数数据据结结构构和和参参数数应应满满足足的的条件，若不满足，则操作
30、失败，并返回相应出错信息。条件，若不满足，则操作失败，并返回相应出错信息。l “操操作作结结果果”说说明明了了操操作作正正常常完完成成之之后后，数数据据结结构构的的变变化化状状况和应返回的结果。若初始条件为空，则省略之。况和应返回的结果。若初始条件为空，则省略之。1.3 抽象数据类型抽象数据类型(ADT)36为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&数据结构的三个方面的含义之数据结构的三个方面的含义之算法算法&算法的概念和描述：算法的概念和描述：&什么是算法？什么是算法？所谓所谓算法算法（Algorithm)是描述计算机解决
31、给定问题的是描述计算机解决给定问题的操作过程（解题方法），即为解决某一特定问题操作过程（解题方法），即为解决某一特定问题而由若干条指令组成的而由若干条指令组成的有穷序列有穷序列。1.4 算法和算法分析算法和算法分析37为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&算法的概念和描述：算法的概念和描述：一个算法必须满足以下五个准则：一个算法必须满足以下五个准则：（1 1）有穷性有穷性-执行了有限条指令后一定要终止。执行了有限条指令后一定要终止。（2 2）确定性确定性（无二义）（无二义）-算法的每一步操作都必须有确切算法的每一步操作都
32、必须有确切定义，不得有任何歧义性。定义，不得有任何歧义性。（3 3）可（能）行性可（能）行性-算法的每一步操作都必须是可行的，算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。即每步操作均能在有限时间内完成。（4 4）输入数据输入数据-一个算法有一个算法有n n（n=0)n=0)个初始数据的输入。个初始数据的输入。（5 5）输出数据输出数据-一个算法有一个或多个与输入有某种关系一个算法有一个或多个与输入有某种关系的有效信息的输出。的有效信息的输出。1.4 算法和算法分析算法和算法分析38为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小
33、学图书室育人功能l例例 一个不是算法的例子一个不是算法的例子(1)begin(2)n=0(3)n=n+1(4)repeat(3)(5)endl例例 一个不超过一个不超过100次计数的次计数的算法算法(1)begin(2)n=0(3)n=n+1(4)if n=100 do(5),else repeat(3)(5)output n(6)end1.4 算法和算法分析算法和算法分析39为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&算法的描述和实现算法的描述和实现 描述描述-可采用自然语言、数学语言或约定的符可采用自然语言、数学语言或约定
34、的符号语言。号语言。实现实现-必须借助程序设计语言提供的数据类型必须借助程序设计语言提供的数据类型及其运算。及其运算。本课的描述本课的描述-采用类采用类C语言。语言。1.4 算法和算法分析算法和算法分析40为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&算法的评价准则算法的评价准则（首先，算法必须是（首先，算法必须是“正确正确”的）的）（1 1）执行算法所耗费的时间（效率）执行算法所耗费的时间（效率 要高）。要高）。（2 2）执行算法所耗费的存储空间（主要考虑辅存）执行算法所耗费的存储空间（主要考虑辅存空间；低存储要求）。空间；低
35、存储要求）。（3 3）算法的可读性、易维护性要好（易于理解，）算法的可读性、易维护性要好（易于理解，易于编码，易于调试）。易于编码，易于调试）。1.4 算法和算法分析算法和算法分析41为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&程序正确性的四个层面：程序正确性的四个层面：（1 1）不含语法错误）不含语法错误（2 2）程序对于）程序对于n n组输入数据能够得出满足规格说明组输入数据能够得出满足规格说明要求的结果。要求的结果。（3 3）程序对于精心选择的典型、边界性的）程序对于精心选择的典型、边界性的n n组输入组输入数据能得出满
36、足规格说明要求的结果。数据能得出满足规格说明要求的结果。（4 4）程序对于一切合适的输入数据都能得出满足规）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。格说明要求的结果（穷举）。1.4 算法和算法分析算法和算法分析42为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&算法效率的度量算法效率的度量&1.程序运行所耗费的时间程序运行所耗费的时间(由下列因素决定由下列因素决定)：算法所选用的策略算法所选用的策略 问题的规模问题的规模 书写程序所采用的语言书写程序所采用的语言 编译程序所产生的机器代码的质量编译程序所产
37、生的机器代码的质量 机器执行指令的速度机器执行指令的速度 一个算法耗费的时间一个算法耗费的时间=算法中每条语句的执行时间之和。算法中每条语句的执行时间之和。若不考虑机器硬、软件因素，可以认为算法若不考虑机器硬、软件因素，可以认为算法“运行工作量运行工作量”的大小是问题规模的函数。的大小是问题规模的函数。1.4 算法和算法分析算法和算法分析43为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能&2.问题的规模（问题的规模（size)-算法求解问题的输入量（或初始数据量）。算法求解问题的输入量（或初始数据量）。&3.不考虑机器软硬件环境时
38、算法的时间耗费：不考虑机器软硬件环境时算法的时间耗费：设：执行每条语句所需时间为单位时间，则：设：执行每条语句所需时间为单位时间，则：一个算法耗费的时间一个算法耗费的时间=所有语句的频度之和。所有语句的频度之和。时间复杂度时间复杂度T(n)-即：时间耗费，它是算法求解问题即：时间耗费，它是算法求解问题n的函数。的函数。渐近时间复杂度渐近时间复杂度-即当问题的规模即当问题的规模n时的时间复杂度时的时间复杂度T(n)的数量级（阶），记作：的数量级（阶），记作：T(n)=O(f(n)评价一个算法的时间性能，主要标准是算法的渐近时间复杂度评价一个算法的时间性能，主要标准是算法的渐近时间复杂度1.4 算
39、法和算法分析算法和算法分析44为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能l例例 x=1;for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x+;l由于内循环的执行次数虽与规模由于内循环的执行次数虽与规模n无直接关系，但无直接关系，但与外循环的变量取值有关。因此与外循环的变量取值有关。因此从内层向外层循环从内层向外层循环分析执行次数分析执行次数。1.4 算法和算法分析算法和算法分析45为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人
40、功能 即即:T(n)=n(n+1)(2n+1)/6+n(n+1)/2/2 所以：所以：T(n)=O(n3/6+低次项低次项)取取T(n)的数量级阶，的数量级阶，得最后结果为：得最后结果为：T(n)=O(n3)=niijjknT1111)(1.4 算法和算法分析算法和算法分析46为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例例1.5 分析以下程序段的时间复杂度分析以下程序段的时间复杂度for(i=1;in;i+)y=y+1;for(j=0;j=(2*n);j+)x+;/*1 */*2 */1.4 算法和算法分析算法和算法分析47为
41、深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能分析分析：语句的：语句的频度频度指的是该语句重复执行的次数。一个指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。算法中所有语句的频度之和构成了该算法的运行时间。语句语句1的频度是：的频度是：n-1语句语句2的频度是：的频度是：则该程序段的则该程序段的时间复杂度时间复杂度：T(n)=1.4 算法和算法分析算法和算法分析48为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例例1.6 分析以下程序段的
42、时间复杂度分析以下程序段的时间复杂度i=1;while(i=n)i=i*2语句语句1的频度是：的频度是：1设语句设语句2的频度是的频度是f(n)，则有：则有：即即 ，取最大值，取最大值则该程序段的时间复杂度为：则该程序段的时间复杂度为：/*1 */*2 */1.4 算法和算法分析算法和算法分析49为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能l 常见函数的时间复杂度按常见函数的时间复杂度按数量递增排列及增长率数量递增排列及增长率。常数阶常数阶O(1)对数阶对数阶O(log2n)线性阶线性阶O(n)线性对数阶线性对数阶O(nlog2
43、n)平方阶平方阶O(n2)立方阶立方阶O(n3)k次方阶次方阶O(nk)指数阶指数阶O(2n)1.4 算法和算法分析算法和算法分析50为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 数据、数据结构等基本概念数据、数据结构等基本概念 数据结构的三个方面的内容数据结构的三个方面的内容 线性和非线性结构的逻辑特征线性和非线性结构的逻辑特征 数据存储的四种基本方法数据存储的四种基本方法 算法、算法的时间复杂度及其分析的简易方法算法、算法的时间复杂度及其分析的简易方法本章小结本章小结51为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 The End52