算法与数据结构第1章节概论.ppt

算法与数据结构 算法与数据结构 课程名称：算法与数据结构 先修课程：C语言程序设计 后续课程：微机原理及应用 　　　　　 单片机原理及应用 教材：算法与数据结构-C语言描述 张乃孝编著 参考资料： 1、数据结构（C语言版） 严蔚敏 吴伟民 编著 2、数据结构题集（C语言版） 严蔚敏 吴伟民 编著 3、数据结构 唐策善等编 4、算法与数据结构 陈守孔等编 教师：电子信息教研室 许亮 课程成绩的考核 平时（出勤、作业、上课）占50%； 期末考试占50％； 第1章 概论 本章目录 1.1 从问题到程序 1.1.1 问题分析与抽象 1.1.2 程序的设计与实现 1.2 基本概念和术语 1.3 抽象数据类型 1.4 算法 1.4.1 算法 1.4.2 算法的设计 1.4.3 算法的精化 1.4.4 算法的分析 1.1从问题到程序 当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤： 实际　问题提出 需求模型 抽象　问题模型 数学模型 实现模型 程序 是使用程序设计语言精确描述的实现模型 1.1从问题到程序 计算机的用途： 微分方程 数值运算 数学模型 代数方程组等 非数值运算：数据结构讨论的内容（应用更为广泛） 1.1从问题到程序 为一个实际问题建立一个正确的求解程序，通常可以分成以下四个阶段： 分析阶段：建立模型（需求或数学模型） 设计阶段：算法和数据结构的设计（实现模型） 编码阶段：编写可执行程序 调试和维护 1.1.1问题分析与抽象 1.1.1问题分析与抽象 1.1.2程序的设计与实现 例1.1 考生录取信息系统 考生录取信息系统 计算机处理的对象是表 元素间的关系是线性关系 施加于对象上的操作有查询、插入、删除等 例1.2 人－机博弈 国际象棋 Deep Blue: 2亿结点/秒，60万种棋局，评价函数有8000个参数； 计算机预见10－15步，心理学家认为，人类选手只能预测3－5步； 棋局中期计算机往后看75步。 人－机博弈 计算机处理的对象是树型结构 元素间的关系是层次关系 施加于对象上的操作有查询、插入、删除等 例1.3 哥尼斯堡七桥问题 哥尼斯堡七桥问题 计算机处理的对象是图 元素间的关系是复杂的图形或网状关系 施加于对象上的操作有查询、插入、删除等 数据结构研究的内容 由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 1.2基本概念和术语 数据(Data)：客观事物在计算机中的符号表示，是能被计算机识别和处理的符号总称。 数据元素(Data Element)：数据的基本单位，用于完整地描述一个对象; (也称为：记录，元素，结点，顶点等） 数据项(Data Item)：组成数据元素的有特定意义的最小的不可分割的单位 。 1.2基本概念和术语 数据的三个层次 数据 数据元素 数据项 数据对象(Data Object)：具有相同特性的数据元素的集合，是数据的一个子集; 1.2基本概念和术语 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。 形式定义：数据结构是一个二元组Data_Structure ＝（D，R）,其中，D是数据元素的有限集，R是D上关系的有限集。 例 复数的数据结构定义如下： Complex=(C，R) 其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数 的实部和虚部。 R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。 1.2基本概念和术语 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。 形式定义：数据结构是一个二元组Data_Structure ＝（D，R）,其中，D是数据元素的有限集，R是D上关系的有限集。 “关系”：描述的是数据元素之间的逻辑关系，因此又称为逻辑结构 。算法的设计取决于选定的逻辑结构。 数据结构在计算机中的表示称为数据的物理结构，又称存储结构。算法的实现依赖于采用的存储结构。 逻辑结构：数据元素之间的逻辑关系 数据的逻辑结构是本质，可以分为： 线性结构和非线性结构， 也可以分为 集合： 线性结构： 树形结构： 图状结构：（复杂结构） 存储结构：数据结构在计算机中的表示。 物理（