第2讲_线性数据结构(一)顺序表_线性链表_.ppt

第2单元 线性数据结构（一） 教学目标： ? 了解数据结构的有关概念 什么是线性DS、线性表 ? 了解线性DS的特点 ? 了解线性DS的逻辑结构、物理结构以及操作 通过本单元的学习，了解并掌握： ? 有关数据结构（DS）的基本概念 数据元素、DS、逻辑结构、物理结构、DS的分类及特点、算法、时间复杂度等 ? 线性DS的常用存储结构 顺序、链表、索引、散列存储结构 单向、双向、循环链表等 ? 线性DS的有关算法 增、删、改 涉及的章节 第2章的 2.1 数据结构概述 (P22~P24) 2.2 线性表 (P25~P34) 数据结构问题的由来 计算机求解问题过程步骤： 实际 问题 求解 问题 模型 算法 问题模型 结构分析—— 线性方程组 人口预报—— 微分方程 优化问题—— 线性规划、非线性规划 振动问题—— 矩阵分析；特征值、特征向量 信息管理—— 二维数据表 下棋 —— 人工智能(树型结构) 交通管理——最佳道路选择(图型结构) 一、基本概念 P22 数据（Data） 是信息的载体，它可以用计算机表示并加工，如数、字符、符号等的集合。 数据元素（ Data Element） 是数据的基本单位、数据集合中的个体。 数据对象（ Data Object） 具有相同性质的数据元素的集合。 数据结构（Data Structure） 是指同一数据对象中各数据元素间存在的关系。它有三个要素： DS=数据的逻辑结构+存储结构+数据的运算 数据结构是以数据为加工对象，研究数据组织方式和相关操作方法的学问。也可以说：怎样去组织一批特定的数据。 数据结构分类 1. 数据的逻辑结构 它是描述数据间的顺序（逻辑）关系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存放。一般用下列二元组来描述： DS=（D，R） 其中： D：是数据元素的有限集合； R：是数据元素之间关系的集合。 举例 课题组由1名教师、1~3名研究生、1~6名本科生组成；成员关系是：教师指导研究生、研究生指导1~2名本科生。 定义DS如下： Group=（D，R） 其中： D={T，G1，…,Gn,S11,…Snm} 1 ? n ? 3 , 1 ? m ? 2 R={R1,R2} R1={T,Gi|1 ? i ? n , 1 ? n ? 3} R2={Gi,Sij|1?i?n ,1? j ? m , 1 ? n ? 3 , 1 ? m ? 2 } 2. 数据的存储结构 又称物理结构 是指数据结构在计算机中的表示(又称映象)，即数据在计算机中的存放。 逻辑结构和物理结构的关系 ? 数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进 行 研究、推理、运算等各种操作。 ? 数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无 法进行 任 何 操作。 ? 任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。 数据存储结构分类 顺序存储结构 链式存储结构 索引存储结构 散列存储结构 顺序存储结构 把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。数据结点结构: 特点: ? 连续存放；逻辑上相邻，物理上也相邻。 ? 结构简单，易实现。 ? 插入、删除操作不便（需大量移动元素）。 链式存储结构 以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。数据结点结构: 特点: ? 非连续存放,借助指针来表示元素间的关系; ? 插入、删除操作简单，只要修改指针即可； ? 结构较复杂，需要额外存储空间。 散列存储结构 在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到它的存储地址，即D=F（E）。 哈希查找中的哈希表就是这样一种存储结构。 特点： ? 数据元素间无内在联系； ? 存储形式不定。 索引存储 除建立存储结点信息外，还建立附加的索引表来