商大数据结构.doc

第一章 绪论 1.1 基本概念和术语 1.2 算法和算法分析 1.1 基本概念和术语 1.基本概念 2.数据的逻辑结构 3.数据的存储结构 1.基本概念 数据： 概念： 对客观事物的符号表示； 被计算机处理的符号的总称； 计算机程序加工的“原料”； 内容： 数值、字符、图象、动画、声音等； 数据元素： 数据的基本单位； 在程序中作为一个整体而加以考虑和处理。 数据元素又称元素、结点、顶点或记录。 数据项： 数据元素可由数据项若干组成； 数据项是数据不可分割的最小单位； 又称字段或域。 数据对象： 性质相同数据元素的集合； 举例：整数的集合、字母的集合等； 数据结构：Data Structure 简单解释： 相互之间存在一种或多种特定关系的数据元素的集合； 定义：二元组 data_structure=(D,S) D是数据元素的有限集； S是D上关系的有限集； 四类基本结构： 集合、线性、树形、网状结构 2.数据的逻辑结构 逻辑关系： 数据元素之间的关联方式。 一个结点代表一个元素，结点之间的连线代表逻辑关系。 参图1－5四类基本结构关系图。 逻辑结构： 概念： 数据元素之间逻辑关系称为数据的逻辑结构； 从具体问题抽象出来的数学模型。 数据结构的数学描述； 分类： 集合、线性、树形、网状 逻辑结构的特性： 逻辑结构与数据元素本身的形式、内容无关。 逻辑结构与数据元素的相对位置无关。 逻辑结构与所含结点个数无关。 独立于计算机的硬件结构。 逻辑结构的作用：即数学模型 重新组织数据 进行算法设计 构造数据的机内表示提供“依据” 3.数据的存储结构 存储结构：物理结构； 数据结构在计算机中的表示； 包括数据元素和关系的表示 数据单位： 位和字节 数据域：字段； 结点：一个记录； 存储结构的分类： 顺序存储结构：借助元素在存储器的相对位置来表示数据元素之间的逻辑关系； 链式存储结构：借助元素存储地址(指针)来表示数据元素之间的逻辑关系； 散列存储结构 索引存储结构 存储结构的描述：数据类型(C语言) 数组：描述顺序存储结构 指针：描述链式存储结构 存储结构和逻辑结构的关系： 算法的设计取决于逻辑结构 算法的实现取决于存储结构 1.2 算法和算法分析 1.算法 2.算法的设计要求 3.算法的时间复杂度 4.算法的空间复杂度 1.算法 概念：algorithm 对特定问题求解的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作； 程序：完成既定任务的一组指令序列； 5个重要特性： 有穷性 确定性 可行性 输入 输出 算法描述： 自然语言 数学公式 流程图 伪代码 程序设计语言 C语言作为算法描述：程序； 算法性能分析： 时间的度量：时间复杂度； 事后统计 事前分析估算 空间度量：空间复杂度 算法与程序： 算法的含义与程序十分相似，但又有区别： 程序必须是机器可执行的，算法无此限制； 算法代表对问题的求解，而程序则是算法在计算机上的特定实现； 算法用C语言描述，就是程序; 2.算法设计要求 正确性 可读性 健壮性 高效性：时空性能 时间性能：指算法包含的计算量。 空间性能：指算法需要的存储量。 3.算法效率的度量 度量程序执行时间 事后分析 事前分析估算 算法度量： 时间复杂度 空间复杂度 4.算法的时间复杂度 时间复杂度： 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，记做T(n) =O(f(n))；它表示随问题规模的增大，算法执行时间的增长率和f(n)相同。 常用时间复杂度： 常量阶：O(1) 线性阶：O(n) 平方阶：O(n2) 对数阶：O(log n) 指数阶：O(2n) 5.算法的空间复杂度 空间复杂度： 表示：S(n)=O(f(n)) n表示问题规模的大小。 评价： 数据占有存储的空间； 附加的存储空间。 第二章 线性表 2.1 线性表的定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.1 线性表的定义 线性结构： 基本特征： 除第一个和最后一个数据元素，每个结点至多只有一个直接前驱并且只有一个直接后继； 结点要求： 一个结点代表一个元素； 所有结点具有相同的特性； 线性表定义：P18 最简单、最基本、最常用的一种数据结构；它的逻辑结构是线性结构； 定义：n(≥0)个数据元素的有限系列。 同一线性表中的元素具有相同的特性； 所含结点个数为线性表的长度； 结点数为0的线性表为空表； 举例： 例1：26个英文字母组成的线性表； (简单) 例2：整数组成的线性表； (简单) 例3：学生纪录组成的线性表；(复杂) 线性表表示：（a1,…，ai-1,ai,ai+1,…，an） ai是线性表的i个元素； i为ai在线性表的位序； ai-1,是a