1、1第第5 5章章 多维数组和广义表多维数组和广义表5.1 多维多维数组数组5.2 特殊特殊矩阵矩阵的压缩存储的压缩存储5.3 稀疏稀疏矩阵矩阵的压缩存储的压缩存储5.4 广义表的概念广义表的概念25.1 数组数组 一、数组的定义一、数组的定义数组：它是数组：它是n（n1)个相同数据类型的数据元素个相同数据类型的数据元素a0,a1,a2,an-1构成的占用一块地址连续的内存单元的有限序列。构成的占用一块地址连续的内存单元的有限序列。数组的下标：数组元素的位置。数组的下标：数组元素的位置。注意：注意：(1)C语言的数组定义下标从语言的数组定义下标从0开始。开始。(2) 数组的处理相比其它复杂的结构
2、要简单。数组的处理相比其它复杂的结构要简单。 数组中各元素具有数组中各元素具有统一的类型统一的类型； 数组元素的下标一般具有数组元素的下标一般具有固定的上界和下界固定的上界和下界，即数组一旦，即数组一旦被定义，它的维数和维界被定义，它的维数和维界(上下界上下界)就不再改变。就不再改变。 数组的数组的基本操作比较简单基本操作比较简单，除了结构的初始化和销毁之外，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。只有存取元素和修改元素值的操作。(3)一个二维数组可以看作每个数据元素是一个一维数组的一维一个二维数组可以看作每个数据元素是一个一维数组的一维数组。数组。二维数组是两维的，内存单
3、元是一维的，存在向内存存储二维数组是两维的，内存单元是一维的，存在向内存存储时二维数组中数据元素的存储方法问题，时二维数组中数据元素的存储方法问题，C语言采用以行序为主语言采用以行序为主序的方法存储。序的方法存储。3问题：数组与线性表的区别与联系问题：数组与线性表的区别与联系相同之处：相同之处：它们都是若干个它们都是若干个相同数据类型相同数据类型的数据元素的数据元素a a0 0,a,a1 1,a,a2 2, ,，a an-1n-1构成的有限序列。构成的有限序列。不同之处：不同之处：(1)(1)数组要求其元素占用一块数组要求其元素占用一块地址连续地址连续的内存单元空间，的内存单元空间，而线性表无
4、此要求；而线性表无此要求；(2)(2)线性表的元素是线性表的元素是逻辑意义上不可再分的元素逻辑意义上不可再分的元素，而数组，而数组中的每个中的每个元素还可以是一个数组元素还可以是一个数组；(3)(3)数组的数组的操作操作主要是向某个下标的数组元素中存放数据主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这与线性表的插入和删除操作和取某个下标的数组元素，这与线性表的插入和删除操作不不同同。4二、数组的实现机制二、数组的实现机制、一维数组（一维数组（n n个元素）中任一元素个元素）中任一元素a ai i LOC(ai)=LOC(a)+i*k (0i n)、一个、一个m行行n列的二维数组
5、列的二维数组LOC(aij)=LOC(a00)+(i*n+j)*k (0im， 0jn)注：注：C语言中数组元素采用行主序的存放方法，即语言中数组元素采用行主序的存放方法，即行优先行优先顺序顺序。a的内存单元地址的内存单元地址每个元素所需的字节个数每个元素所需的字节个数每个元素所需的字节个数每个元素所需的字节个数a0的内存单元地址的内存单元地址一个一个mn的二维数组可以的二维数组可以看成是看成是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=5对于行优
6、先顺序：先排最右的下标，从右往左，对于行优先顺序：先排最右的下标，从右往左，最后排最左下标；最后排最左下标；对于列优先顺序：先排最左的下标，从左往右，对于列优先顺序：先排最左的下标，从左往右，最后排最右下标；最后排最右下标；6注：只要知道以下三要素便可随时求出任一元素的地址注：只要知道以下三要素便可随时求出任一元素的地址（意（意义：数组中的任一元素可随机存取）义：数组中的任一元素可随机存取）开始结点的存放首字节地址（即基地址）；开始结点的存放首字节地址（即基地址）；维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数。每个数组元素所占用的单元数。例例软考题：软考题：一个二维数
7、组一个二维数组A A，行下标的范围是，行下标的范围是1 1到到6 6，列下标的范围是，列下标的范围是0 0到到7 7，每个数组元素用相邻的，每个数组元素用相邻的6 6个字节存储，存储器按字节编址。那么，这个个字节存储，存储器按字节编址。那么，这个数组的体积是数组的体积是 个字节。个字节。答：答： Volume=mVolume=m* *n n* *L=(6-1L=(6-1+1+1) )* *(7- 0 (7- 0 +1+1) )* *6=486=48* *6=2886=288例例 设数组设数组aa60, 60, 7070的基地址为的基地址为20482048，每个元素占，每个元素占2 2个存储单元
8、，个存储单元，若以行序为主序顺序存储，则元素若以行序为主序顺序存储，则元素a32,58a32,58的存储地址的存储地址为为 。答：答：根据行优先公式根据行优先公式 LOC(aLOC(aijij)=LOC(a)=LOC(a0000)+(i)+(i* *n+j)n+j)* *k k (0(0i im，0 0j jn)n)得：得：LOC(aLOC(a32,5832,58)=2048+()=2048+(3232* *71+71+5858) )* *2 22887二维数组二维数组Amn按行优先顺序存储按行优先顺序存储元素元素aij的存储地址为数组的基地址加上排在的存储地址为数组的基地址加上排在aij前面
9、的元素前面的元素所占用的单元数。因为所占用的单元数。因为aij位于第位于第i行，第行，第j列列,前面前面i行一共有行一共有i*n个元素，第个元素，第i行上行上aij前面又有前面又有j个元素，故它前面一共有个元素，故它前面一共有i *n+j个元素，因此，个元素，因此，aij的地址计算函数为：的地址计算函数为： Loc(aij)= Loc(a00)+i *n+j*d8三、三、数组抽象数据类型数组抽象数据类型数据集合数据集合： a0,a1,a2,an-1 每个数据类型为抽象数据元素每个数据类型为抽象数据元素类型类型操作集合操作集合: :(1)(1)求求数组元素个数数组元素个数 ArrayLength
10、(DArrayLength(D) ) (2) (2)存数组元素存数组元素Storage(D,i,x)Storage(D,i,x) (3) (3)取数组元素取数组元素Get(D,i,x)Get(D,i,x)95.2 5.2 特殊矩阵的压缩存储特殊矩阵的压缩存储 特殊矩阵特殊矩阵: :指有许多值相同的元素或有许多零元素、且值相同的元素或零指有许多值相同的元素或有许多零元素、且值相同的元素或零元素的分布有一定规律的矩阵。元素的分布有一定规律的矩阵。 下面我们讨论几种特殊矩阵的压缩存储。下面我们讨论几种特殊矩阵的压缩存储。1 1、n n阶对称矩阵阶对称矩阵 在一个在一个n n阶方阵阶方阵A A中，若元
11、素满足下述性质：中，若元素满足下述性质： a aijij=a=ajiji （1i,jn1i,jn） 则称则称A A为为n n阶对称矩阵阶对称矩阵。 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 图 5.1 对称矩阵 n n阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，
12、能节约近一半的存储空间。不失一般性，我们按能节约近一半的存储空间。不失一般性，我们按“行优先行优先顺序顺序”存储主存储主对角线（包括对角线）以下的元素。对角线（包括对角线）以下的元素。10 i(i+1)/2+j i(i+1)/2+j 当当ijij j(j+1)/2+i j(j+1)/2+i 当当i ij jk= 在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i i个元素，元素总数为个元素，元素总数为n(n+1)/2n(n+1)/2，这，这样就可将样就可将n n2 2个数据元素压缩存储在个数据元素压缩存储在n(n+1)/2n(n+1)/2个存储单元中。个存储单元中。 假设以一维数
13、组假设以一维数组vava作为作为n n阶对称矩阵阶对称矩阵A A的压缩存储单元，的压缩存储单元，k k为一维数组为一维数组vava的下标序号，的下标序号，a aijij为为n n阶对称矩阵阶对称矩阵A A中中i i行行j j列的数据元素列的数据元素( (其中其中1i,jn 1i,jn ），），其数学映射关系为：其数学映射关系为： 令令I=max(i,j), J=min(i,jI=max(i,j), J=min(i,j),),则则k k和和i,ji,j的对应关系可统一为：的对应关系可统一为： k=Ik=I* *(I+1)/2+J 0(I+1)/2+J 0kn(n+1)/22 2、n n阶三角矩阵
14、阶三角矩阵 以主对角线划分，以主对角线划分， n n阶三角矩阵有阶三角矩阵有n n阶上三角矩阵和阶上三角矩阵和n n阶下三角矩阵阶下三角矩阵两种。两种。 n n阶上三角矩阵如图阶上三角矩阵如图5.2(a)5.2(a)所示，它的下三角（不包括主对角线）所示，它的下三角（不包括主对角线）中的元素均为中的元素均为0 0（或常数）。（或常数）。n n阶下三角矩阵正好相反，它的主对角线上阶下三角矩阵正好相反，它的主对角线上方均为方均为0 0（或常数），如图（或常数），如图5.2(b)5.2(b)所示。所示。 注：在大多数情况下，注：在大多数情况下， n n阶三角矩阵常数为零。阶三角矩阵常数为零。 11
15、a11 a12 a 1n a11 c c c a22 a 2n a21 a22 c . c c a nn an1 an2 an n (a)(a)上三角矩阵上三角矩阵 (b)(b)下三角矩阵下三角矩阵 图图5.2 5.2 三角矩阵三角矩阵i(i-1)/2+j-1 i(i-1)/2+j-1 当当ijijn(n+1)/2n(n+1)/2 （或空）（或空） 当当i imd = da.nddb-md = da.nd; /; /* *行数值转为列数值行数值转为列数值* */ /db-nd = da.mddb-nd = da.md; /; /* *列数值转为行数值列数值转为行数值* */ /db-td =
16、da.tddb-td = da.td; ;/ /* *非零元个数不变非零元个数不变* */ /if (da.tdif (da.td=0)=0)return;return;elseelse q = 0;q = 0; / /* *q q为为b-listb-list的下标值的下标值* */ / for (v=1;v=da.nd;v for (v=1;v=da.nd;v+)+) for(p = 0; p da.td for(p = 0; p listq. b-listq.i i = a.listp. = a.listp.j j; /; /* *列号转为行号列号转为行号* */ / b-listq. b
17、-listq.j j = a.listp.= a.listp.i i; /; /* *行号转为列号行号转为列号* */ / b-listq.d = a.listp.d; / b-listq.d = a.listp.d; /* *数组元素复制数组元素复制* */ / q+; q+; 20三、稀疏矩阵的三元组链表三、稀疏矩阵的三元组链表1、三元组链表、三元组链表 用链表存储的三元组线性表。用链表存储的三元组线性表。2、行指针数组结构的三元组链表、行指针数组结构的三元组链表 把每行非零元素三元组组织成一个单链表，再设计把每行非零元素三元组组织成一个单链表，再设计一个指针类型的数组存储所有单链表的头指
18、针。一个指针类型的数组存储所有单链表的头指针。3、三元组十字链表、三元组十字链表 把非零元素三元组按行和按列组织成单链表，这样把非零元素三元组按行和按列组织成单链表，这样稀疏矩阵中的每个非零元素三元组结点都将既勾链稀疏矩阵中的每个非零元素三元组结点都将既勾链在行单链表上，又勾链在列单链表上，形成十字形在行单链表上，又勾链在列单链表上，形成十字形状。状。21广义表广义表广义表是线性表的推广。线性表的元素仅限于广义表是线性表的推广。线性表的元素仅限于原子项（结构上不可分割，可以是一个数或原子项（结构上不可分割，可以是一个数或一个结构），若而广义表容许他们具有其自一个结构），若而广义表容许他们具有其自身结构。身结构。广义表是广义表是n(n0)个元素个元素a1,a2,an的有限序列，的有限序列，其中其中ai或者是原子或者是一个广义表。或者是原子或者是一个广义表。记作：记作： LS=(a1,a2,an) 若广义表若广义表LS非空非空(即即n1),则则a1是是LS的表头，其的表头，其余元素组成的表余元素组成的表(a1,a2,an)称为称为LS的表尾。的表尾。
