数据结构与STL_第4章_多维数组与广义表(2)

1、第四章第四章 多维数组多维数组数据结构与数据结构与STL数据结构与STL2第四章第四章 多维数组和广义表多维数组和广义表学习内容：学习内容：4.1 4.1 多维数组多维数组 4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4 4.4 .4 实例分析实例分析4.5 4.5 使用使用STLSTL操作多维数组操作多维数组数据结构与STL34.1 4.1 多维数组多维数组 由类型相同的数据元素构成的有序集合。 对于k 维数组，每个元素都要受k个线性关系的约束。 111212121211.nnmnmmmnaaaaaaAaaa 数组一般不执行删除和插入操作，所以常采用顺序存储方法来存储数组。通常有两种存储方

2、式：行优先存储和列优先存储。数据结构与STL4 行优先存储 按行存储，即存完第i行再接着存储第i+1行。按行优先顺序存储二维数组Amn，线性a a1111, ,a a1212,a a1 1n n, ,a a2121, ,a a2222,a a2 2n n,a am m1 1, ,a am m2 2,a amnmnLoc(aij) =Loc(a11) + (i-1)*n + j-1)*c 在C+、PASCAL等语言中，数组都是按行优先存储的 数据结构与STL5 列优先存储 按列存储，即存完第i列再接着存储第i+1列。 存储二维数组Amn，按列优先顺序存储的线性序列为： a a1111, ,a a

3、2121,a am m1 1, ,a a1212, ,a a2222,a am m2 2,a a1 1n n, ,a a2 2n n,a amnmnLoc(aij)=Loc(a11)+ (i-1 + m*(j-1)*c 在在FORTRAN语言中，数组是按列优先存储的语言中，数组是按列优先存储的三维数组示意：Amnp m-片，n-行，p-列 行优先方式：先排最右端的下标，从右向左。12mnp先排第一片第一行 第一片第二行 第n行 第二片第一行 第二行 m数据结构与STL7多维数组的存储多维数组的存储 C+中设三维数组Amnp，第一个元素为a000，若按行优先存储，则aijk前面共有inp+jp+

4、k个元素;若按列优先存储，则aijk前面共有i+mj+mnk个元素; 试分析四维数组或更高维数组的行优先存储和列优先存储。 数据结构与STL8第四章第四章 多维数组多维数组学习内容：学习内容：4.1 4.1 多维数组多维数组 4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4.3 4.3 广义表广义表 4 4.4 .4 实例分析实例分析4.5 4.5 使用使用STLSTL操作多维数组操作多维数组数据结构与STL94.2 4.2 矩阵的压缩存储矩阵的压缩存储 矩阵是一种常见的处理对象矩阵是一种常见的处理对象 矩阵可看作是二维数组矩阵可看作是二维数组 对于一些数据元素具有特殊规律的矩阵，常常采用对于

5、一些数据元素具有特殊规律的矩阵，常常采用一些特殊的存储方法以节省存储空间一些特殊的存储方法以节省存储空间 对称矩阵特殊矩阵压缩存储 三角矩阵 对角矩阵 稀疏矩阵压缩存储 数据结构与STL10 对称矩阵对称矩阵 1(1)2nkn nk共需要存储的元素数目 设所有元素存储到一维数组设所有元素存储到一维数组Sa中，中，aij存储在存储在Sak中，中，k 与与 ij 的关系？的关系？ k = i(i+1)/2 + j （ij）若aij位于矩阵的上三角，如何存储？数据结构与STL11 上三角中的元素aij（ij），因为aij aji ， 则访问和它对应的元素aji即可： kj(j1)/2i 。思考：设n

6、阶对称矩阵按行优先方式存储下三角元素，元素a00存储在Sa0元素中，元素aij存储在Sa100元素中，则下标i、j的值为多少？数据结构与STL12三角矩阵三角矩阵 三角矩阵分为三角矩阵分为上三角矩阵上三角矩阵和和下三角矩阵下三角矩阵。设设n n阶方阵阶方阵A A，若其下三角的元素除对角线外均为常数，若其下三角的元素除对角线外均为常数c c，即即a aijij= =c c，00j ji in n，则称该方阵为，则称该方阵为 上三角矩阵上三角矩阵 对于对于n阶三角矩阵，需要存储阶三角矩阵，需要存储n(n+1)/2+1个元素个元素 数据结构与STL13 按行优先存储按行优先存储n n阶上三角矩阵，设

7、阶上三角矩阵，设a aijij存储到存储到sasa k k 中中 若若aij位于矩阵上三角，有位于矩阵上三角，有0ijn，则在存储，则在存储aij之前，之前， sa数组中首先要存储前数组中首先要存储前i行上三角的元素，然后再存储行上三角的元素，然后再存储aij所所在行从在行从aii到到ai,j-1的元素的元素 ：120()()/2ilknljiniiij 若若aij位于矩阵下三角，有位于矩阵下三角，有0jin，此时所有的，此时所有的aij具有相同的值，只需保存具有相同的值，只需保存1 1个值个值 k = n(n+1)/2 (0jin)数据结构与STL14思思 考考 按行优先存储按行优先存储n

8、n阶下三角矩阵时，首先存储下三阶下三角矩阵时，首先存储下三角的元素，最后存储上三角的常数项角的元素，最后存储上三角的常数项c c。给出。给出a aijij与与sasa k k 的对应关系。的对应关系。 对于按列优先方式存储的对于按列优先方式存储的n阶三角矩阵，请推导阶三角矩阵，请推导元素存储位置元素存储位置k与下标与下标i、j的对应关系的对应关系 数据结构与STL15对角矩阵对角矩阵 所有非零元素都集中在对角线附近的方阵所有非零元素都集中在对角线附近的方阵 三对角矩阵 在存储对角矩阵时，可将对角线附近的带状区域在存储对角矩阵时，可将对角线附近的带状区域元素立起来，形成一个列数较少的新矩阵，然后

9、可按元素立起来，形成一个列数较少的新矩阵，然后可按行优先方式存储这个新矩阵。行优先方式存储这个新矩阵。 数据结构与STL16 n n 维维 m m 对角矩阵对角矩阵A A（m m为奇数），设其对角线附为奇数），设其对角线附近的元素近的元素a aijij存储到一维数组元素存储到一维数组元素sasa k k 中。由于中。由于a aijij在在对角线附近，因此有：对角线附近，因此有：m maxax( (i i-(-(m m-1)/2,0)j-1)/2,0)jminmin( (i i+(+(m m-1)/2,-1)/2,n n-1)-1) a aijij之前共有之前共有i i行，每行行，每行m m个元

10、素，因此首先个元素，因此首先要存储这要存储这mimi个元素。在个元素。在a aijij所在行上，所在行上，a aijij之前共有之前共有j j- -i i+(+(m m-1)/2-1)/2个元素。因此在存储个元素。因此在存储a aijij之前，总共要存储之前，总共要存储mimi+ +j j- -i i+(+(m m-1)/2-1)/2个元素，即有：个元素，即有：k k= =mimi+ +j j- -i i+(+(m m-1)/2=(-1)/2=(m m-1)-1)i i+ +j j+(+(m m-1)/2-1)/2数据结构与STL174.2.2 4.2.2 稀疏矩阵压缩存储稀疏矩阵压缩存储 矩

11、阵Amn中的非零元素个数s 远远小于矩阵元素的总数mn 存储稀疏矩阵时，只需要存储非零元素。 常见的稀疏矩阵压缩方法：三元组表和十字链表 稀疏矩阵中每个非零元素的行号、列号及值构成一个三元组（3-triples） 数据结构与STL18#define#define MAX_ELEMENT_NUMBER 1000 MAX_ELEMENT_NUMBER 1000templatetemplate Tstructstruct MatrixNode MatrixNode /定义三元组结构定义三元组结构 intint row; row;/非零元素的行号非零元素的行号intint col; col;/非零元素

12、的列号非零元素的列号T value;T value;/非零元素的值非零元素的值;templatetemplate Tstructstruct SpareMatrix SpareMatrix/定义三元组表结构定义三元组表结构 intint m; m; /稀疏矩阵的行数稀疏矩阵的行数intint n; n; /稀疏矩阵的列数稀疏矩阵的列数intint t; t; /稀疏矩阵非零元素的个数稀疏矩阵非零元素的个数MatrixNode dataMAX_ELEMENT_NUMBER;MatrixNode dataMAX_ELEMENT_NUMBER; /存储非零元素对应的三元组存储非零元素对应的三元组;数

13、据结构与STL19稀疏矩阵的转置操作稀疏矩阵的转置操作 转置数据结构与STL20稀疏矩阵简单转置算法稀疏矩阵简单转置算法 遍历n 趟三元组表： 第一趟遍历找出列号为0的三元组，并将其行号和列号对调，添加到转置矩阵对应的三元组表中。 第二趟遍历找出列号为1的三元组并进行相同操作， 依次类推，最后一趟遍历找出列号为n-1的三元组。 由于每趟遍历都需要比较所有的t个三元组的列号，因此算法的时间复杂度为O(nt)。 数据结构与STL21简单转置算法简单转置算法/将稀疏矩阵将稀疏矩阵OrigMatOrigMat转置为转置为TransMatTransMattemplatetemplate Tvoidvoi

14、d TransMat(SpareMatrix TransMat(SpareMatrix * * OrigMat, SpareMatrix OrigMat, SpareMatrix * * TransMat) TransMat) TransMat-m = OrigMat-n; TransMat-m = OrigMat-n; /设置转置矩阵的行数设置转置矩阵的行数 TransMat-n = OrigMat-m; TransMat-n = OrigMat-m; /设置转置矩阵的列数设置转置矩阵的列数 TransMat-t = 0; TransMat-t = 0; /初始时转置矩阵的非零元素个数为初始

15、时转置矩阵的非零元素个数为 forfor ( (intint col=0;coln;col+) col=0;coln;col+) forfor ( (intint j=0;jt;j+) j=0;jt;j+)ifif (OrigMat-dataj.col = col) (OrigMat-dataj.col = col) /找出列号为找出列号为colcol的三元组的三元组 TransMat-dataTransMat-t.col = OrigMat-dataj.row ; TransMat-dataTransMat-t.col = OrigMat-dataj.row ; TransMat-dataT

16、ransMat-t.row = OrigMat-dataj.col ; TransMat-dataTransMat-t.row = OrigMat-dataj.col ; TransMat-dataTransMat-t.value = OrigMat-dataj.value ; TransMat-dataTransMat-t.value = OrigMat-dataj.value ; TransMat-t+; TransMat-t+; /非零元素个数增非零元素个数增 数据结构与STL22快速稀疏矩阵转置算法快速稀疏矩阵转置算法时间复杂度为O(n+t) 在原始三元组表（设为A）依次取每个三元组，

17、交换其行号和列号后，直接存放到转置矩阵的三元组表（设为B）中的适当位置。 关键的问题：如何确定三元组在B中的位置 A中第0列的第一个非零元素一定存储在B中下标为0的位置上，该列中其它非零元素应存放在B0后面连续的位置上。 第1列的第一个非零元素在B中的位置便等于第0列的第一个非零元素在B中的位置加上第0列的非零元素的个数。数据结构与STL23引入两个数组作为辅助数据结构：numbern： 存储矩阵A中每列非零元素的个数；positionn：初始值表示矩阵A中每列的第一个非零 元素在B中的位置 数据结构与STL24A=15 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6

18、0 0 0 0 0 0 0 0 91 0 0 0 0 0numbernumber 0 0 15 0 3 22 0 5 - -15 1 1 11 1 2 3 2 3 6 4 0 91 空空 空空 空空 闲闲 闲闲 闲闲 矩阵的行数矩阵的行数5 矩阵的列数矩阵的列数6 非零元个数非零元个数7row col item0123456Max- -1positionposition2 21 11 12 20 01 12 23 34 46 66 6 空空 空空 空空 闲闲 闲闲 闲闲 矩阵的行数矩阵的行数6 矩阵的列数矩阵的列数5 非零元个数非零元个数7row col item0123456Max- -10

19、 00 015150 0 1 10 1 2 3 4 50 1 2 3 4 53 30 022225 55 50 0-15-157 71 11 111113 32 21 13 34 43 32 26 66 60 04 491912 2数据结构与STL25算法伪代码算法伪代码1. 设置转置矩阵B的行数、列数和非零元素的个数；2. 计算A中每一列的非零元素个数，存储到number数组；3. 计算A中每一列的第一个非零元素在B中的下标，存储到position数组；4. 依次取A中的每一个非零元素对应的三元组； 4.1 确定该元素在B中的下标pb； 4.2 将该元素的行号列号交换后存入B中pb的位置；

20、4.3 预置该元素所在列的下一个元素的存放位置；数据结构与STL26十字链表十字链表 每个非零元素，采用一个五元组结点表示每个非零元素，采用一个五元组结点表示 templatetemplate Tstructstruct snode snode/十字链表五元组结点十字链表五元组结点 intint row,col; row,col;/行号与列号行号与列号T val;T val;/值值structstruct snode snode * * cnext, rnext; cnext, rnext;/列指针与行指针列指针与行指针;同一行的非零元素构成一个带头结点的循环链表，同一列的非零元素也构成一个带头结点的循环链表。 数据结构与STL27数据结构与STL28第四章第四章 多维数组和广义表多维数组和广义表学习内容：学习内容：4.1 4.1 多维数组多维数组 4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4.3 4.3 广义表广义表 （略）（略） 4 4.4 .4 实例分析实例分析4.5 4