文档介绍：数据结构(C++版)二
第四章广义线性表
本章的基本内容是:
数组的逻辑结构特征
数组的存储方式及寻址方法
特殊矩阵和稀疏矩阵的压缩存储方法
广义表的基本概念和存储结构
第四章广义线性表
线性表——具有相同类型的数据元素的有限序列。
限制插入、删除位置
线性表——具有相同类型的数据元素的有限序列。
限制元素类型为字符
栈——仅在表尾进行插入和删除操作的线性表。
队列——在一端进行插入操作,而另一端进行删除操作的线性表。
串——零个或多个字符组成的有限序列。
特殊线性表
第四章广义线性表
线性表——具有相同类型的数据元素的有限序列。
将元素的类型进行扩充
广义线性表
(多维)数组——线性表中的数据元素可以是线性表,但所有元素的类型相同。
广义表——线性表中的数据元素可以是线性表,且元素的类型可以不相同。
数组的定义
数组是由一组类型相同的数据元素构成的有序集合,每个数据元素称为一个数组元素(简称为元素),每个元素受n(n≥1)个线性关系的约束,每个元素在n个线性关系中的序号i1、i2、…、in称为该元素的下标,并称该数组为 n 维数组。
数组的特点
元素本身可以具有某种结构,属于同一数据类型;
数组是一个具有固定格式和数量的数据集合。
广义线性表——多维数组
广义线性表——多维数组
a11 a12 … a1n
a21 a22 … a2n
…………
am1 am2 … amn
A=
例如,元素a22受两个线性关系的约束,在行上有一个行前驱a21和一个行后继a23,在列上有一个列前驱a12和和一个列后继a32。
数组示例
a11 a12 … a1n
a21 a22 … a2n
…………
am1 am2 … amn
A=
A=(A1,A2,……,An)
其中:
Ai=(a1i,a2i,……,ami)
(1≤i≤n)
数组——线性表的推广
二维数组是数据元素为线性表的线性表。
广义线性表——多维数组
数组的基本操作
广义线性表——多维数组
在数组中插入(或)一个元素有意义吗?
a11 a12 … a1n
a21 a22 … a2n
…………
am1 am2 … amn
A=
将元素 x 插入
到数组中第1行第2列。
x
a11 a12 … a1n
a21 a22 … a2n
…………
am1 am2 … amn
A=
删除数组中
第1行第2列元素。
数组的基本操作
⑴存取:给定一组下标,读出对应的数组元素;
⑵修改:给定一组下标,存储或修改与其相对应的数组元素。
存取和修改操作本质上只对应一种操作——寻址
数组应该采用何种方式存储?
数组没有插入和删除操作,所以,不用预留空间,适合采用顺序存储。
广义线性表——多维数组
数组的存储结构与寻址——一维数组
设一维数组的下标的范围为闭区间[l,h],每个数组元素占用 c 个存储单元,则其任一元素 ai 的存储地址可由下式确定:
Loc(ai)=Loc(al)+(i-l)×c
广义线性表——多维数组
c
al
ai-1
ai
……
ah
al+1
……
Loc(al)
Loc(ai)