《数据结构》课程教学资源（PPT课件）第四章 数组、集合和矩阵

第4章类数组、集合和矩阵4.1 数组4.2特殊矩阵4.3稀疏矩阵4.4集合

第4章 数组、集合和矩阵 4.1 数组 4.2 特殊矩阵 4.3 稀疏矩阵 4.4 集合

4.1数组4.1.1数组的定义数组是n（n≥1）个相同数据类型的数据元素a0,al,a2.an-1构成的占用一块地址连续的内存单元的有限集合

4.1 数组 4.1.1 数组的定义 数组是n（n≥1）个相同数据类型的数据元素 a0,a1,a2,.,an-1构成的占用一块地址连续的内存单元的 有限集合

问题：数组与线性表的区别与联系相同之处：它们都是若干个相同数据类型的数据元素ao,a1,a2，…，an-1构成的有限序列。不同之处：（1）数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求：(2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组：（3）数组的操作主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这与线性表的插入和删除操作不同

问题：数组与线性表的区别与联系 相同之处： 它们都是若干个相同数据类型的数据元素a0,a1,a2,.，an-1 构成的有限序列。 不同之处： (1)数组要求其元素占用一块地址连续的内存单元空间，而 线性表无此要求； (2)线性表的元素是逻辑意义上不可再分的元素，而数组中 的每个元素还可以是一个数组； (3)数组的操作主要是向某个下标的数组元素中存放数据和 取某个下标的数组元素，这与线性表的插入和删除操作不同

数组的实现机制4.1.21、一维数组（n个元素）中任一元素a；的内存单元地址LOC(ai)=LOC(a。)+i*k(0≤i<n)a的内存单元地址每个元素所需的字节个数2、一个m行n列的二维数组LOC(ai)=LOC(aoo)+(i*n+i)*k(0<i<m , 0j<n)aon的内存单元地址每个元素所需的字节个数ao,o ao,1ao,n-1一个m×n的二维数组可以a1,0 a1,1a1,n-1A看成是m行的一维数组，或·者n列的一维数组am-1,0 am-1,1 ... am-1,n-1

4.1.2 数组的实现机制 １、一维数组（n个元素）中任一元素ai的内存单元地址 LOC(ai)=LOC(a０)+i*k (0≤i <n) ２、一个m行n列的二维数组 LOC(aij)=LOC(a00)+(i*n+j)*k (0≤i<m， 0≤j<n) a０的内存单元地址 每个元素所需的字节个数 a０0的内存单元地址 每个元素所需的字节个数 一个m×n的二维数组可以 看成是m行的一维数组，或 者n列的一维数组。 a0,0 a0,1 . a0,n-1 a1,0 a1,1 . a1,n-1 . . . . am-1,0 am-1,1 . am-1,n-1 Amn =

下标下标1100241第1行1第1列72322323434565518第2行44第2列Q5658736687第3行76第3列8989(b)(c)(a）二维数组的逻辑结构行优先顺序存储结构列优先顺序存储结构二维数组的顺序存储结构

1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9 (b) 行优先顺序存储结构 (c) 列优先顺序存储结构 1 2 3 4 5 6 7 8 9 第1行 第2行 第3行 第1列 第2列 第3列 (a) 二维数组的逻辑结构 下标 0 2 8 7 6 5 4 3 1 下标 0 2 8 7 6 5 4 3 1 二维数组的顺序存储结构

注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机存取）①开始结点的存放地址（即基地址）：②维数和每维的上、下界；③每个数组元素所占用的单元数例1：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是_288个字节。答：Volume=m*n*L=(6-1+1)*(7-0 +1)*6=48*6=288例2设数组a［0..60，0..69]的基地址为2048，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32，581的存储地址6644为答：根据行优先公式LOC(aij)=L0C(aoo)+(i*n+j)*k（0≤i<m，0≤j<n）得：L0C(a32.58)=2048+(32*70+58)*2=6644

注：只要知道以下三要素便可随时求出任一元素的地址（意义： 数组中的任一元素可随机存取） ①开始结点的存放地址（即基地址）； ②维数和每维的上、下界； ③每个数组元素所占用的单元数 例１：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数 组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积 是 个字节。 例２ 设数组a[０.60, ０.69]的基地址为2048，每个元素占2个存储单元， 若以行序为主序顺序存储，则元素a[32,58]的存储地址 为 。 288 6644 答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288 答：根据行优先公式 LOC(aij)=LOC(a00)+(i*n+j)*k (0≤i<m，0≤j<n) 得：LOC(a32,58)=2048+(32*70+58)*2＝6644

数组抽象数据类型4.1.3数据集合数组的数据集合可以表示为a0,al,a2，an-1且限定数组元素必须存储在地址连续的内存单元中。操作集合：（1）分配内存空间acclocateO：为数组分配用户所需的内存空间。（2）取数组长度getLengthO：取数组的长度。（3）存数组元素set(i,x)：把数据元素x存入下标为i的数组中。其约束条件为：0<i<getLengthO-1。（4）取数组元素get(i)：取出数组中下标为的数据元素。其约束条件为：0≤i≤getLengthO-1

4.1.3 数组抽象数据类型 数据集合 数组的数据集合可以表示为a0, a1, a2, ., an-1， 且限定数组元素必须存储在地址连续的内存单元中。 操作集合： （1）分配内存空间acclocate()：为数组分配用户所需的内存 空间。 （2）取数组长度getLength()：取数组的长度。 （3）存数组元素set(i, x)：把数据元素x存入下标为i的数组中。 其约束条件为：0≤i≤getLength()-1。 （4）取数组元素get(i)：取出数组中下标为i的数据元素。其 约束条件为：0≤i≤getLength()-1

4.2特殊矩阵特殊矩阵是指这样一类矩阵，其中有许多值相同的元素或有许多零元素，且值相同的元素或零元素的分布有一定规律。一般采用二维数组来存储矩阵元素。但是，对于特殊矩阵，可以通过找出矩阵中所有值相同元素的数学映射公式，只存储相同元素的一个副本，从而达到压缩存储数据量的目的

4.2 特殊矩阵 特殊矩阵是指这样一类矩阵，其中有许多值相同 的元素或有许多零元素，且值相同的元素或零元素的 分布有一定规律。 一般采用二维数组来存储矩阵元素。但是，对于 特殊矩阵，可以通过找出矩阵中所有值相同元素的数 学映射公式，只存储相同元素的一个副本，从而达到 压缩存储数据量的目的

特殊矩阵压缩存储方式有两种：1.只存储相同矩阵元素的一个副本2.采用不等长的二维数组

特殊矩阵压缩存储方式有两种: 1.只存储相同矩阵元素的一个副本； 2.采用不等长的二维数组

（1）n阶对称矩阵在一个n阶方阵A中，若元素满足下述性质：(1≤i,j≤n)aijaji则称A为n阶对称矩阵。下图是一个5阶对称矩阵。53177ail85000a21 a22896-2a31 a32a330532102631anlan2an3...annn阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素

（1）n阶对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji （1≦i,j≦n） 则称A为n阶对称矩阵。下图是一个5阶对称矩阵。 1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 . 7 0 6 1 3 an1 an2 an3 .a nn n阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三 角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样， 能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主 对角线（包括对角线）以下的元素