集合。
数据结构是研究数据和数据之间关系的一门
学科，它包括三个方面。 学科，它包括三个方面。 （1）数据集合中各数据元素之间所固有的逻 ） 辑关系，即数据的逻辑结构； 辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计 ）在对数据进行处理时， 算机中的存储关系，即数据的存储结构； 算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 ）对各种数据结构进行的运算。 第15页 1. 逻辑结构
数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构包含： 数据的逻辑结构包含： （1）表示数据元素的信息； ）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 ）表示各数据元素之间的前后件关系。 例：
1. 一年四季的数据结构 B=(D,R) D={春，夏，秋，冬} 春 R={(春，夏) ,(夏，秋),(秋，冬)} 春 夏 秋 2. 家庭成员的数据结构 B=(D,R) D={父亲，儿子，女儿 父亲， 父亲 儿子，女儿} R={(父亲，儿子 ,(父亲，女儿 父亲， 父亲， 父亲 儿子) 父亲 女儿)} 春 数据结构的图形表示 夏 父亲 秋 冬 儿子 女儿 第16页
常见的逻辑结构有： 线性结构、树形结构和图形结构。 线性结构、树形结构和图形结构。
图 形 结 线性结构 树形结构 构 线性结构 结构 的 的 的 树形结构 结构 的 图形结构
6
结构
的 线形结构。 线形结构。 图形 。 的 。 结构 第17页
结构 的 树形结构和图形结构 2. 存储结构（物理结构） 存储结构（
计算机在实际进行数据处理时， 计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计 算机的存储空间中，并且， 算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与 它们的逻辑关系不一定是相同的，而且一般也不可能相同。 它们的逻辑关系不一定是相同的，而且一般也不可能相同。 如：一年四季 家庭成员 计算机存储空间怎样存放？
存储结构指数据结构在计算机存储空间中的具体实现。 存储结构指数据结构在计算机存储空间中的具体实现。
常见的存储结构有： 常见的存储结构有： 顺序存储结构 链式存储结构 索引存储结构 存储结构
只抽象地反映数据元素之间的关 系的结构， 系的结构，而不管其存储方式的 数据结构称为逻辑结构。 数据结构称为逻辑结构。 ? 一种数据结构可以根据需要表示 一种数据结构可以根据需要表示 成一种或多种存储结构。 成一种或多种存储结构。 第18页
通常，一个数据结构中的元素结点可能是动态变化的。 通常，一个数据结构中的元素结点可能是动态变化的。根 据需要或在处理过程中， 据需要或在处理过程中，可以在一个数据结构中增加一个新结 插入运算），也可以删除某个结点（删除运算）， ），也可以删除某个结点 ），除此之 点（插入运算），也可以删除某个结点（删除运算），除此之 对数据结构的运算还有查找、分类、合并、分解、 外，对数据结构的运算还有查找、分类、合并、分解、复制和 修改。 修改。 在对数据结构的处理过程中， 在对数据结构的处理过程中，不仅数据结构中结点的个数 在动态变化，而且， 在动态变化，而且，各数据元素之间的关系也有可能在动态地 变化。 变化。如：无序表变有序表 3. 数据的运算 检索 插入 删除 更新 排序
数据结构是研究数据和数据之间 关系的一门学科， 关系的一门学科，研究以下三方面 内容： 内容：
7
数据的逻辑结构 数据的存储结构 数据的运算 第19页 常见的数据结构
1.线性表 线性表 2.栈和队列 栈和队列 3.树 树 上一页 下一页 停止放映 第20|92页 20|92页 |92
１． 线性表（Linear List） 线性表（ List） 线性表是由n（ 线性表是由 （n≥0）个数据元素
a1，a2，…，ai，…，an组成的一个有限序列。 ， ， 组成的一个有限序列。 简单的线性表 春 夏 秋 冬 复杂的线性表
记录1 记录 记录2 记录 记录3 记录 记录4 记录 第21页 02011001 张三 男 李四 女 … … 02011003
线性表的存储结构
线性表的存储结构有两种： 线性表的存储结构有两种： 顺序存储结构 链式存储结构 存储地址 2000 2004 …
a1 a2 … ai … an … 占4个字节 个字节 线性表的顺序存储结构
顺序存储结构把逻辑上相邻的 顺序存储结构把逻辑上相邻的 逻辑上相邻 数据元素存储在物理上相邻 物理上相邻的存 数据元素存储在物理上相邻的存 储单元里，顺序存储结构只存储 储单元里，顺序存储结构只存储 结点的值，不存储结点间的关系， 结点的值，不存储结点间的关系， 结点间的关系由存储单元的邻接 关系来体现。 关系来体现。 …
8
2000+4*(i-1) …
2000+4*(n-1)
Loa（ Loa（ai）=Loa（a1）+L*（i-1） =Loa（ +L*（
第i个数的地址 第一个数的地址 L为该类型数所占的字节 第22页 顺序表的插入和删除运算
线性表的顺序存储结构称为顺序表。 线性表的顺序存储结构称为顺序表。 顺序表的插入运算 顺序表的删除运算 在线性表顺序存储情况下， 在线性表顺序存储情况下，要插入或删除一个元 素，都会由于数据元素的移动而消耗大量的处理时间， 都会由于数据元素的移动而消耗大量的处理时间， 所以这种存储方式对于小线性表或其中数据元素不经 常变动的线性表是合适的。 常变动的线性表是合适的。 第23页
线性表的链式存储结构
线性表的链式存储结构称为线性链表。 线性表的链式存储结构称为线性链表。 链式存储结构不要求逻辑上相邻的数据元素物理位 置也相邻，而且各数据元素的存储顺序也是任意的。 置也相邻，而且各数据元素的存储顺序也是任意的。 各数据元素的先后关系是由各结点的指针域指示。 各数据元素的先后关系是由各结点的指针域指示。 链式存储结构的每一个存储结点不仅存储结点的值， 链式存储结构的每一个存储结点不仅存储结点的值， 而且存储结点之间的关系： 而且存储结点之间的关系： 数据域 指针域 第24页
线性链表的物理状态 线性链表的物理状态
应用举例—— 应用举例——线性链表的存储结构 ——线性链表的存储结构 设线性表为（a1，a2，a3，a4，a5） 1 a1
线性表的顺 线性表的顺 序存储结构 序存储结构 HEAD
1 2 3 4 5 6 7 8 9 10 3 a2 a1 a4
9
9 1 10
2 a2 3 a3 4 a4 5 a5 6 7 3 1
注意:1 2 3 此类编号不 代表所在的 地址单元的 地址编码 a3 a5 10 5 0 9 5 HEAD a1 a2 a3 a4 a5 第25页
线性链表的逻辑状态 线性链表的插入和删除运算
单链表的插入运算 单链表的删除运算 采用链式存储结构，存储空间开销较大， 采用链式存储结构，存储空间开销较大，但是进行插 入和删除运算不会造成大量元素的移动。 入和删除运算不会造成大量元素的移动。 循环链表是加一种形式的链式存储结构。 循环链表是加一种形式的链式存储结构。它的特点是 表中最后一个结点的指针域指向头结点。 表中最后一个结点的指针域指向头结点。 3 HEAD 1 9 5 10 a1 a2 a3 a4 a5 第26页
10