第1章线性数据结构（一）1.ppt

第1章 线性数据结构（一） 教材: 1.1 数据结构概述 1.2 线性表 教学目标： ? 了解数据结构的有关概念 ? 了解线性DS的概念、特点 ? 掌握线性表的逻辑结构、物理结构以及操作 学习要求 1. 掌握以下基本概念 数据元素、DS、逻辑结构、物理结构 2. DS的分类及特点、时间复杂度等 3. 线性DS的常用存储结构 顺序、链表、索引、散列存储结构 单向、双向、循环链表等 4. 线性DS的有关算法 增、删、改 1.1 数据结构概述 一、基本概念 1. 数据（Data） 存储在计算机中、并被计算机处理的符号的集合,是客观事物的符号表示。 2. 数据元素（Element） 组成数据的基本单位 可由若干个数据项组成 数据集合中的个体,对应结点(节点)。 二. 数据结构 1. 数据结构（Data Structure） 1) 研究数据及数据元素之间的关系. 2) 组成要素： DS=数据的逻辑结构+ 存储结构+ 数据的运算 2. 数据的逻辑结构 1) 描述数据间的逻辑关系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存放。 2) 定义: DS=（D，R） 其中： D：数据元素的有限集合； R：数据元素之间关系的集合。 3.数据结构分类 4. 数据的存储结构 又称物理结构 是指数据结构在计算机中的表示(又称映象),即数据在计算机中的存放方式。 逻辑结构和物理结构的关系 1. 逻辑结构 从逻辑关系上观察数据，独立于计算机；可以在理论上、形式上进行研究、推理、运算等各种操作。 2. 存储结构 逻辑结构在计算机中的实现，依赖于计算机。 3. 任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。 数据存储结构分类 顺序存储结构 链式存储结构 索引存储结构 散列存储结构 (1) 顺序存储结构 把数据元素按某种顺序存放在一块连续的存储单元中。 结点结构: 特点: 1) 连续存放,逻辑上相邻,物理上也相邻。 2) 结构简单，易实现。 3) 插入、删除操作不便（需大量移动元素） (2) 链式存储结构 数据元素存放在任意存储单元中，可连续存放，也可以不连续存放，用指针实现链表间的联系。 结点结构: 特点: 1) 插入、删除操作只要修改指针即可 2) 结构较复杂，需要额外存储空间。 (3) 索引存储结构 存储两部分内容： 数据元素序列和索引表 索引表组成: 数据元素的某个数据项和该元素存储地址 结点结构: 序号： 1 2 3 4 5 6 7 数据项： 索引号： 特点： ? 非连续存放 ? 增 、删操作简单 ? 检索速度快 ④ 数据元素长度可不等 (4) 散列存储结构 在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到它的存储地址，即D=F（E）。 特点： （1）数据元素间无内在联系 （2）存储形式不定 实例：哈希查找中的哈希表 5. 数据运算 （1）数据运算 是指对存放在物理结构上的数据,按定义的逻辑结构进行的各种操作。 （2）每个数据结构都有一个运算的集合 （3）常见操作 检索、插入、删除、修改 三、算法与算法分析 1. 算法（Algorithm） 是对特定问题求解步骤的一种描述； 2. 算法和运算的关系 运算依赖于逻辑结构 算法依赖于存储结构 3. 研究算法追求的目标 时间和空间的适当和谐 4. 算法的特性 有穷性 一个算法必须总是在执行有穷步后结束，且每一步都可在有穷时间内完成； 确定性 算法中的每一个指令必须有明确的含义，不能有二义性； 可行性 算法中描述的操作都是可通过已经实现的基本运算、执行有限次实现的； 输入 一个算法应有0个或多个输入； 输出 一个算法应有1个或多个输出。 5. 算法的描述方式 (1) 自然语言 (2) 流程图 用特定图形符号进行算法描述 (3) 伪语言 包括程序设计语言的三大基本结构及自然语言的一种语言 (4) 类语言 类似高级语言的语言，例如类PASCAL、类C语言。 6.算法的评价