Chap1算法与数据结构—C语言描述(第2版)张乃孝编课件【荐】.ppt

算法的空间复杂度 算法的空间复杂度 算法的空间复杂度是指解决问题的算法在执行时所占用的存储空间。再具体一些，也就是我们编程序时，程序的存储空间、变量占用空间、系统堆栈的使用空间等等。也正由此，空间复杂度的度量分为两个部分：固定部分和可变部分。 for(k=1; k=n; k++) { s=s+10; } for(j=1; j=n; j++) for(k=1; k=n; k++) { s=s+10; } T(n)=O( n ) n=1 执行1次; n=10 执行10次; n=100 执行100次; for(i=1; i=n; i++) for(j=1; j=n; j++) for(k=1;k=n;k++) { s=s+10; } T(n)=O( n3 ) n=1 执行1次; n=10 执行1000次; n=100 执行1000000次; T(n)=O( n2 ) n=1 执行1次; n=10 执行100次; n=100 执行10000次; 复杂度函数的增长率 1log2n n n log2n n2 n3 2n 10n * * 数据结构的地位 “数据结构”在计算机科学中是一门综合性的专业基础课。 数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。 程序 = 数据结构 + 算法 课程目的 能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存储结构及其相应的算法； 学习一些常用的算法； 复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读； 初步掌握算法的时间分析和空间分析技术； 第一章 概论 问题和实例 数据结构？ 抽象数据类型ADT 类C描述 算法和算法分析 问题和实例(1) 当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤： 问题 抽象 数据结构 算法 程序 问题和实例(2) 快速送达疫苗 已知有临近的五个村子发生了疫情，我们要用汽车快速地将疫苗送达到5个村子。目标是寻找一条耗时最少的路线。 胜利 发生疫情的五个村子 河源 长利 太华 桦南 1 2 7 5 3 4 4 1 2 3 村子联系网络 v1 v5 v2 v4 v3 1 2 7 5 4 1 3 4 3 2 耗时矩阵 穷举法 贪心算法 数据结构 是一门研究非数值计算的程序设计问题中，计算机操作的对象以及它们之间的关系和操作的学科 例子 书目自动检索系统 人机对奕问题 快速送达疫苗问题 例1 书目自动检索系统 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目卡片 书目文件 按书名 按作者名 按分类号 索引表 线性表 数据结构 例2 人机对奕问题 树 …….. …….. …... …... …... …... 例3： 问题：快速送达疫苗 模型：图形结构 图形结构 胜利 发生疫情的五个村子 河源 长利 太华 桦南 1 2 7 5 3 4 4 1 2 3 图 数据结构 基本概念和术语 数据(Data)：客观事物在计算机中的符号表示，是能被计算机识别和处理的符号总称。(数值型、非数值型) 数据元素(Data Element)：数据的基本单位，用于完整地描述一个对象; 数据项(Data Object)：组成数据元素的有特定意义的最小单位 。 数据对象(Data Object)：相同特性数据元素的集合，是数据的一个子集合。 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。 根据数据元素间关系的基本特性，有四种基本数据结构 （集合）——数据元素间除“同属于一个集合”外，无其它关系 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图状结构——多个对多个，如图 基本概念和术语 基本概念和术语 形式定义：数据结构是一个二元组Data_Structure ＝（D，R）,其中，D是数据元素的有限集，R是D上关系的有限集。 数据结构主要关心的是下面三个方面 ： 结构中各元素之间的逻辑关系 线性结构：如图书馆的书目索引 树形结构：如人机对奕问题 图形结构：交通图 2. 结构中各元素的存储方式(物理结构) 3. 结构具有的行为特征(关系与操作) 基本概念和术语 存储结构(物理结构)数据结构在计算机中的表示。 顺序存储结构：借助元素