数据结构实用教程
数据结构实用教程
内容安排 第一章绪论 第二章线性表 第三章栈与队列 第四章串 m第五章数组与广义表 口第六章树
内容安排 第一章 绪论 第二章 线性表 第三章 栈与队列 第四章 串 第五章 数组与广义表 第六章 树
内容安排 第七章图 第八章查找 第九章内部排序 口第十章综合实训
内容安排 第七章 图 第八章 查找 第九章 内部排序 第十章 综合实训
教据结构 第一章绪论
数据结构 第一章 绪论
基本概念和相关术语 据 所有能输入到计算机之中,并能被计算机程序所处理的符号 的总称。如数字,字母,标点符号、图形图像、声音等 ■数据元素 描述数据的基本单位(数据项) 数据对象 性质相同的一类数据元素的集合 数据逻辑结构 数据元素之间的组织形式:集合、线性结构、树形结构 网状结构
基本概念和相关术语 ◼ 数据 所有能输入到计算机之中，并能被计算机程序所处理的符号 的总称。如数字，字母，标点符号、图形图像 、声音等。 ◼ 数据元素 描述数据的基本单位(数据项) ◼ 数据对象 性质相同的一类数据元素的集合 ◼ 数据逻辑结构 数据元素之间的组织形式：集合、 线性结构、树形结构 网状结构
基本概念和相关术语 物理结构 数据在计算机内部的实际存储结构 结点 存储在内存中的数据元素 域 数据元素中的每个数据项 线性存储结构 用物理地址相邻来表示数据元素在逻辑上的相邻关系 ■链式存储结构 元素之间逻辑上的相邻关系物理地址上不一定相邻 而是通过指针来描述
基本概念和相关术语 ◼ 物理结构 数据在计算机内部的实际存储结构 ◼ 结点 存储在内存中的数据元素 ◼ 域 数据元素中的每个数据项 ◼ 线性存储结构 用物理地址相邻来表示数据元素在逻辑上的相邻关系。 ◼ 链式存储结构 元素之间逻辑上的相邻关系物理地址上不一定相邻， 而是通过指针来描述
抽象数据类型 数据类型是和数据结构密切相关的 个概念。不同的数据类型拥有不同的取值 范围和允许的操作。从硬件的角度来看, 数据类型涉及具体存储单位。如int型占用 两个字节的存储空间,foa型占用4个字节 的存储空间,可以帮助程序开发人员了解 内存的使用情况
抽象数据类型 数据类型是和数据结构密切相关的一 个概念。不同的数据类型拥有不同的取值 范围和允许的操作。从硬件的角度来看， 数据类型涉及具体存储单位。如int型占用 两个字节的存储空间，float型占用4个字节 的存储空间，可以帮助程序开发人员了解 内存的使用情况
抽象数据类型 抽象数据类型( Abstract Data Type,ADT) 原子类型 固定聚合类型 可变聚合类型 ■抽象数据类型的组成(三元组DSP) D表示数据对象 S是D上的数据关系 P表示D的基本操作
抽象数据类型 ◼ 抽象数据类型（Abstract Data Type，ADT） 原子类型 固定聚合类型 可变聚合类型 ◼ 抽象数据类型的组成（三元组 D S P） D表示数据对象 S是D上的数据关系 P表示D的基本操作
算法分析 ■算法 对特定问题求解步骤的一种描述,然后再依据算法编 制程序完成要求。 特性 有穷性确定性可行性输入输出 好的算法特性 正确性可读性健壮性高效率低存储
算法分析 ◼ 算法 对特定问题求解步骤的一种描述，然后再依据算法编 制程序完成 要求。 ◼ 特性 有穷性 确定性 可行性 输入 输出 ◼ 好的算法特性 正确性 可读性 健壮性 高效率 低存储
算法的时间复杂度分析 ■事后统计法 直接比较运行时间 ■事先分析法 用数学方法直接对算法的效率进行分析 指令的执行次数 抛弃特定的软硬件配置有关的因素,直接求出算法中 加法和乘法的执行次数
算法的时间复杂度分析 ◼ 事后统计法 直接比较运行时间 ◼ 事先分析法 用数学方法直接对算法的效率进行分析 ◼ 指令的执行次数 抛弃特定的软硬件配置有关的因素，直接求出算法中 加法和乘法的执行次数