电子科技大学：《软件技术基础 Fundamental of Software Technology》课程教学资源（课件讲稿）第三章 数据结构 3.1 数据结构基本概念

电子斜技大学 软件技术基础 3.1数据结构基本概念 主讲教师：刘民岷 航空航天学院 软件技术基础课程组

软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组

1、什么是数据结构 程序=数据结构+算法 数据结构的定义：讨论和研究计算机系统中数据的组织形式及 相互关系 数据：用计算机对客观事物进行识别、存储和加工所进行的描 述，统称为数据，其基本单位是数据元素（数据节点)，例如： 十进制，二进制常数、字母、字符、程序段、图形图像、语音 文件等 结构：指事物间的相互关系和约束 Nicklaus Wirth 电子科技大学刘民岷 数据结构基本概念 (Pascal之父)

电子科技大学 刘民岷 数据结构基本概念 2 程序 = 数据结构+算法 – 数据结构的定义：讨论和研究计算机系统中数据的组织形式及 相互关系 – 数据：用计算机对客观事物进行识别、存储和加工所进行的描 述，统称为数据，其基本单位是数据元素（数据节点）,例如： 十进制，二进制常数、字母、字符、程序段、图形图像、语音 文件等 – 结构：指事物间的相互关系和约束 Nicklaus Wirth (Pascal之父)

2、 数据结构三层次 1)数据的逻辑结构 数据元素间的逻辑关系 -线性结构：线性表 B 1 一非线性结构：数、图 2)数据的存储结构—数据在计算机中的存储方式 顺序存储：把逻辑上相邻的数据元素存储在物理位置上相邻的 存储单元中。 链接存储（数据项指针）：al,a2,a3..an 索引存储：建立索引表（关键字·地址），稠密索引(Dense Index)、 稀疏索引(Sparse Index) 一散列存储：关键字→地址 3)数据操作集合 一查找、排序、遍历、插入、更新、删除 电子科技大学刘民岷 数据结构基本概念 3

电子科技大学 刘民岷 数据结构基本概念 3 1）数据的逻辑结构——数据元素间的逻辑关系 – 线性结构：线性表 – 非线性结构：数、图 2）数据的存储结构——数据在计算机中的存储方式 – 顺序存储：把逻辑上相邻的数据元素存储在物理位置上相邻的 存储单元中。 – 链接存储(数据项|指针)：a1,a2,a3…an – 索引存储：建立索引表(关键字·地址)，稠密索引(Dense Index)、 稀疏索引(Sparse Index) – 散列存储：关键字→地址 3）数据操作集合 – 查找、排序、遍历、插入、更新、删除 B 1 2 3 E

3、 数据的常见物理存储结构 1)顺序存储结构 ·把数据元素按某种顺序存放在一块连续的存储单元中的 存储形式。数据结点结构： 数据域 dl d2 0t。4国 dn 特点： ■连续存放；逻辑上相邻，物理上也相邻。 ■结构简单，易实现。 ■插入、删除操作不便（需大量移动元素）。 电子科技大学刘民岷 数据结构基本概念 4

电子科技大学 刘民岷 数据结构基本概念 4 1）顺序存储结构 • 把数据元素按某种顺序存放在一块连续的存储单元中的 存储形式。数据结点结构: • 特点: ▪ 连续存放;逻辑上相邻,物理上也相邻。 ▪ 结构简单，易实现。 ▪ 插入、删除操作不便（需大量移动元素）。 d1 d2 …… dn 数据域

数据的常见物理存储结构（续） 2)链式存储结构 以链表形式将数据元素存放于任意存储单元中，可连续存放， 也可以不连续存放，以指针实现链表间的联系。数据结点结 构： 数据域 指针域 dl d2 dn 特点： ■非连续存放，借助指针来表示元素间的关系； ■插入、删除操作简单，只要修改指针即可； ■结构较复杂，需要额外存储空间。 电子科技大学刘民岷 数据结构基本概念 5

电子科技大学 刘民岷 数据结构基本概念 5 2）链式存储结构 • 以链表形式将数据元素存放于任意存储单元中，可连续存放， 也可以不连续存放，以指针实现链表间的联系。数据结点结 构: • 特点: ▪ 非连续存放,借助指针来表示元素间的关系; ▪ 插入、删除操作简单，只要修改指针即可； ▪ 结构较复杂，需要额外存储空间。 d1 d2 ... dn ^ 数据域 指针域

数据的常见物理存储结构（续） 3)索引存储结构 数据按索引形式存放。存储时分为：数据项和索引号；通过 索引表记录逻辑号（关键字)和物理号（地址)之间的对应 关系。数据结点结构： 关键字 地址 序 号： 2 3 4 5 6 7 地址： 12 21 35 2 45 5 10 关键字： 4 3 2 7 1 6 5 特点： ■非连续存放； ■ 检索速度快； ·增、删操作简单。 电子科技大学刘民岷 数据结构基本概念 6

电子科技大学 刘民岷 数据结构基本概念 6 3）索引存储结构 • 数据按索引形式存放。存储时分为：数据项和索引号；通过 索引表记录逻辑号（关键字）和物理号（地址）之间的对应 关系。数据结点结构: 序 号： 1 2 3 4 5 6 7 地址： 关键字： • 特点： ▪ 非连续存放； ▪ 检索速度快； ▪ 增、删操作简单。 12 21 35 2 45 5 10 4 3 2 7 1 6 5 关键字 地址

3、数据的常见物理存储结构（续） 4)散列存储结构 在数据元素与存储位置之间建立一种存储关系F，根据 这种关系F,已知元素E,就可以得到它的存储地址，即 D=F(E)。 ·哈希查找中的哈希表就是这样一种存储结构。 特点： 数据元素间无内在联系， ■存储形式不定。 电子科技大学刘民岷 数据结构基本概念 7

电子科技大学 刘民岷 数据结构基本概念 7 4）散列存储结构 • 在数据元素与存储位置之间建立一种存储关系F，根据 这种关系F，已知元素E，就可以得到它的存储地址，即 D=F(E)。 • 哈希查找中的哈希表就是这样一种存储结构。 特点： ▪ 数据元素间无内在联系； ▪ 存储形式不定