第二章线性数据结构第二章 线性数据结构
2.1 数据结构概述数据结构是一门研究数据的 逻辑关系,存储方法 和 基本运算 的一般方法的学科。
1.数据 (Data)
数据是指所有能输入计算机并能被计算机识别、存储和加工处理的符号的总称。
例如：数字、字符、声音、图形、图像等。
2.1.1 基本概念和术语
2.数据元素 (Data Element)
数据元素是数据的基本单位，即数据集合中的个体。
例如：一组整数中的一个整数、一组图书信息中一本图书的信息等。
2.1.1 基本概念和术语
3.数据项 (Data Item)
有时一个数据元素可由若干数据项组成。数据项是数据的最小单位。
例如：一本图书的信息可能包含以下四项信息。
4.数据结构 (Data Structure)
指存在特定关系的数据元素的集合。
主要包括逻辑结构和物理结构两个方面。
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A,线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
A
B
C
D
E
线性结构示意图
主要特点：
元素间呈现出一对一 的联系。
线性结构举例：
学 生 成 绩 表
86胡孝臣9861103
95刘忠赏9861107
100张卓9861109
成绩姓名学号
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
B C D
E HF
A
G I
树结构示意图
主要特点：
元素间呈现出一对多 的联系。
树结构举例：
全校学生档案管理的组织方式
计算机文件管理系统也是典型的树结构 。
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
1 4
2 3
2
1
3
图结构示意图
主要特点：
元素间呈现出多对多 的联系。
图结构举例：城市公路网、电网。
1．数据的逻辑结构
2,数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
元素 n
……..
元素 i
……..
元素 2
元素 1L
o
Lo+m
Lo+(i-1)*m
Lo+（ n-1)*m
存储地址 存储内容
Loc(ai)=Lo+（ i-1)*m
顺序存储每个元素所占用的存储单元个数元素 n
……..
元素 i
……..
元素 2
元素 1
存储内容?顺序存储结构的特点：
常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。
顺序存储结构的弱点：
1.作插入或删除操作时，需移动大量元素。
2.长度变化较大时，需按最大空间分配。
3.表的容量难以扩充。 内存示意图
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
1536元素 21400元素 1 1352元素 3 ∧元素 4
1348
h 链式存储每个结点都由两部分组成,数据域 和 指针域 。
数据域 存放元素本身的数据，
指针域 存放和该元素有逻辑关系的其它元素的地址。
数据元素之间逻辑上的联系由指针来体现 。
链式存储结构的特点：
各个数据元素不占用连续的存储单元存储，可分散在存储空间中的任意单元中。
元素 4
元素 2
元素 3
1348
1352
1536
1400 ……
……
……
……
内存示意图元素 1
链式存储结构的特点：
各个数据元素不占用连续的存储单元存储，可分散在存储空间中的任意单元中。
元素 1 1400
元素 4 空指针元素 2 1536
元素 3
1348
1352
1536
1400 ……
……
……
……
为了能够在存储结构中反映出元素之间的逻辑关系，在存储每个元素值的同时，专门用一个指针类型的数据项存放与该元素有逻辑关系的元素的内存地址。
1352
内存示意图链式存储
1.可充分利用存储空间中的零散单元。
2.插入、删除灵活
(不必移动结点，只要改变结点中的指针 )。
3.结点空间在程序运行期间随时申请，随时释放。
链式存储结构优点：
2.1.2 算法及其描述
算法：是对特定问题求解步骤的一种描述 。
算法的五个特性：
有穷性,确定性,可行性,输入和输出 。
评价算法：
正确性、易读性、健壮性、运行时间（时间复杂度）及占用空间（空间复杂度） 。
算法的描述方法：
自然语言,专用工具,计算机语言 。
2.1 数据结构概述数据结构是一门研究数据的 逻辑关系,存储方法 和 基本运算 的一般方法的学科。
1.数据 (Data)
数据是指所有能输入计算机并能被计算机识别、存储和加工处理的符号的总称。
例如：数字、字符、声音、图形、图像等。
2.1.1 基本概念和术语
2.数据元素 (Data Element)
数据元素是数据的基本单位，即数据集合中的个体。
例如：一组整数中的一个整数、一组图书信息中一本图书的信息等。
2.1.1 基本概念和术语
3.数据项 (Data Item)
有时一个数据元素可由若干数据项组成。数据项是数据的最小单位。
例如：一本图书的信息可能包含以下四项信息。
4.数据结构 (Data Structure)
指存在特定关系的数据元素的集合。
主要包括逻辑结构和物理结构两个方面。
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A,线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
A
B
C
D
E
线性结构示意图
主要特点：
元素间呈现出一对一 的联系。
线性结构举例：
学 生 成 绩 表
86胡孝臣9861103
95刘忠赏9861107
100张卓9861109
成绩姓名学号
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
B C D
E HF
A
G I
树结构示意图
主要特点：
元素间呈现出一对多 的联系。
树结构举例：
全校学生档案管理的组织方式
计算机文件管理系统也是典型的树结构 。
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
1 4
2 3
2
1
3
图结构示意图
主要特点：
元素间呈现出多对多 的联系。
图结构举例：城市公路网、电网。
1．数据的逻辑结构
2,数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
元素 n
……..
元素 i
……..
元素 2
元素 1L
o
Lo+m
Lo+(i-1)*m
Lo+（ n-1)*m
存储地址 存储内容
Loc(ai)=Lo+（ i-1)*m
顺序存储每个元素所占用的存储单元个数元素 n
……..
元素 i
……..
元素 2
元素 1
存储内容?顺序存储结构的特点：
常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。
顺序存储结构的弱点：
1.作插入或删除操作时，需移动大量元素。
2.长度变化较大时，需按最大空间分配。
3.表的容量难以扩充。 内存示意图
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树结构图结构数据结构的三个方面
(亦称物理结构 )
1536元素 21400元素 1 1352元素 3 ∧元素 4
1348
h 链式存储每个结点都由两部分组成,数据域 和 指针域 。
数据域 存放元素本身的数据，
指针域 存放和该元素有逻辑关系的其它元素的地址。
数据元素之间逻辑上的联系由指针来体现 。
链式存储结构的特点：
各个数据元素不占用连续的存储单元存储，可分散在存储空间中的任意单元中。
元素 4
元素 2
元素 3
1348
1352
1536
1400 ……
……
……
……
内存示意图元素 1
链式存储结构的特点：
各个数据元素不占用连续的存储单元存储，可分散在存储空间中的任意单元中。
元素 1 1400
元素 4 空指针元素 2 1536
元素 3
1348
1352
1536
1400 ……
……
……
……
为了能够在存储结构中反映出元素之间的逻辑关系，在存储每个元素值的同时，专门用一个指针类型的数据项存放与该元素有逻辑关系的元素的内存地址。
1352
内存示意图链式存储
1.可充分利用存储空间中的零散单元。
2.插入、删除灵活
(不必移动结点，只要改变结点中的指针 )。
3.结点空间在程序运行期间随时申请，随时释放。
链式存储结构优点：
2.1.2 算法及其描述
算法：是对特定问题求解步骤的一种描述 。
算法的五个特性：
有穷性,确定性,可行性,输入和输出 。
评价算法：
正确性、易读性、健壮性、运行时间（时间复杂度）及占用空间（空间复杂度） 。
算法的描述方法：
自然语言,专用工具,计算机语言 。
