数据结构与STL-第4章-多维数组与广义表

1、第四章 多维数组数据结构(sh j ji u)与STL共三十一页数据结构(sh j ji u)与STL2第四章 多维数组和广义(gungy)表学习内容：4.1 多维数组 4.2 矩阵的压缩存储 4.3 广义表 (略) 4.4 实例分析4.5 使用STL操作多维数组共三十一页数据结构(sh j ji u)与STL34.1 多维数组 由类型相同的数据元素(yun s)构成的有序集合。 对于k 维数组，每个元素都要受k个线性关系的约束。 数组一般不执行删除和插入操作，所以常采用顺序存储方法来存储数组。通常有两种存储方式：行优先存储和列优先存储。共三十一页数据结构(sh j ji u)与STL4 行优

2、先存储(cn ch) 按行存储，即存完第i行再接着存储第i+1行。按行优先顺序存储二维数组Amn，线性a11,a12,a1n,a21,a22,a2n,am1,am2,amnLoc(aij) =Loc(a11) + (i-1)*n + j-1)*c 在C+、PASCAL等语言中，数组都是按行优先存储的 共三十一页数据结构(sh j ji u)与STL5 列优先存储 按列存储，即存完第i列再接着(ji zhe)存储第i+1列。 存储二维数组Amn，按列优先顺序存储的线性序列为： a11,a21,am1,a12,a22,am2,a1n,a2n,amnLoc(aij)=Loc(a11)+ (i-1 +

3、 m*(j-1)*c 在FORTRAN语言中，数组是按列优先存储的共三十一页三维数组示意(shy)：Amnp m-片，n-行，p-列 行优先方式(fngsh)：先排最右端的下标，从右向左。12mnp先排第一片第一行 第一片第二行 第n行 第二片第一行 第二行 m共三十一页数据结构(sh j ji u)与STL7多维数组的存储(cn ch) C+中设三维数组Amnp，第一个元素为a000，若按行优先存储，则aijk前面共有inp+jp+k个元素;若按列优先存储，则aijk前面共有i+mj+mnk个元素; 试分析四维数组或更高维数组的行优先存储和列优先存储。 共三十一页数据结构(sh j ji u

4、)与STL8第四章 多维数组学习内容：4.1 多维数组 4.2 矩阵的压缩存储 4.3 广义表 4.4 实例分析4.5 使用(shyng)STL操作多维数组共三十一页数据结构(sh j ji u)与STL94.2 矩阵(j zhn)的压缩存储 矩阵是一种常见的处理对象 矩阵可看作是二维数组 对于一些数据元素具有特殊规律的矩阵，常常采用一些特殊的存储方法以节省存储空间 对称矩阵特殊矩阵压缩存储 三角矩阵 对角矩阵 稀疏矩阵压缩存储 共三十一页数据结构(sh j ji u)与STL10 对称(duchn)矩阵 共需要存储的元素数目 设所有元素存储到一维数组Sa中，aij存储在Sak中，k 与 ij

5、 的关系？ k = i(i+1)/2 + j （ij）若aij位于矩阵的上三角，如何存储？共三十一页数据结构(sh j ji u)与STL11 上三角中的元素aij（ij），因为aij aji ， 则访问(fngwn)和它对应的元素aji即可： kj(j1)/2i 。思考：设n阶对称矩阵按行优先方式存储下三角元素，元素a00存储在Sa0元素中，元素aij存储在Sa100元素中，则下标i、j的值为多少？共三十一页数据结构(sh j ji u)与STL12三角(snjio)矩阵 三角矩阵分为上三角矩阵和下三角矩阵。设n阶方阵A，若其下三角的元素除对角线外均为常数c，即aij=c，0jin，则称该方

6、阵为 上三角矩阵 对于n阶三角矩阵，需要存储n(n+1)/2+1个元素 共三十一页数据结构(sh j ji u)与STL13 按行优先存储n阶上三角(snjio)矩阵，设aij存储到sak中 若aij位于矩阵上三角，有0ijn，则在存储aij之前， sa数组中首先要存储前i行上三角的元素，然后再存储aij所在行从aii到ai,j-1的元素 ： 若aij位于矩阵下三角，有0jin，此时所有的aij具有相同的值，只需保存1个值 k = n(n+1)/2 (0jin)共三十一页数据结构(sh j ji u)与STL14思 考 按行优先存储n阶下三角矩阵时，首先存储下三角的元素，最后(zuhu)存储上

7、三角的常数项c。给出aij与sak的对应关系。 对于按列优先方式存储的n阶三角矩阵，请推导元素存储位置k与下标i、j的对应关系 共三十一页数据结构(sh j ji u)与STL15对角(du jio)矩阵 所有非零元素都集中在对角线附近的方阵 三对角矩阵 在存储对角矩阵时，可将对角线附近的带状区域元素立起来，形成一个列数较少的新矩阵，然后可按行优先方式存储这个新矩阵。 共三十一页数据结构(sh j ji u)与STL16 n 维 m 对角矩阵A（m为奇数），设其对角线附近的元素aij存储到一维数组元素sak中。由于aij在对角线附近，因此有：max(i-(m-1)/2,0)jmin(i+(m-

8、1)/2,n-1) aij之前共有i行，每行m个元素，因此首先要存储这mi个元素。在aij所在(suzi)行上，aij之前共有j-i+(m-1)/2个元素。因此在存储aij之前，总共要存储mi+j-i+(m-1)/2个元素，即有：k=mi+j-i+(m-1)/2=(m-1)i+j+(m-1)/2共三十一页数据结构(sh j ji u)与STL174.2.2 稀疏(xsh)矩阵压缩存储 矩阵Amn中的非零元素个数s 远远小于矩阵元素的总数mn 存储稀疏矩阵时，只需要存储非零元素。 常见的稀疏矩阵压缩方法：三元组表和十字链表 稀疏矩阵中每个非零元素的行号、列号及值构成一个三元组（3-triples

9、） 共三十一页数据结构(sh j ji u)与STL18#define MAX_ELEMENT_NUMBER 1000template struct MatrixNode /定义三元组结构int row;/非零元素(yun s)的行号int col;/非零元素的列号T value;/非零元素的值;template struct SpareMatrix/定义三元组表结构int m;/稀疏矩阵的行数int n;/稀疏矩阵的列数int t;/稀疏矩阵非零元素的个数MatrixNode dataMAX_ELEMENT_NUMBER; /存储非零元素对应的三元组;共三十一页数据结构(sh j ji u)

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

11、t(SpareMatrix * OrigMat, SpareMatrix * TransMat) TransMat-m = OrigMat-n; /设置转置矩阵的行数 TransMat-n = OrigMat-m; /设置转置矩阵的列数 TransMat-t = 0; /初始时转置矩阵的非零元素个数为 for (int col=0;coln;col+) for (int j=0;jt;j+)if (OrigMat-dataj.col = col) /找出列号为col的三元组 TransMat-dataTransMat-t.col = OrigMat-dataj.row ; TransMat-d

12、ataTransMat-t.row = OrigMat-dataj.col ; TransMat-dataTransMat-t.value = OrigMat-dataj.value ; TransMat-t+; /非零元素个数增共三十一页数据结构(sh j ji u)与STL22快速稀疏矩阵转置(zhun zh)算法时间复杂度为O(n+t) 在原始三元组表（设为A）依次取每个三元组，交换其行号和列号后，直接存放到转置矩阵的三元组表（设为B）中的适当位置。 关键的问题：如何确定三元组在B中的位置 A中第0列的第一个非零元素一定存储在B中下标为0的位置上，该列中其它非零元素应存放在B0后面连续的

13、位置上。 第1列的第一个非零元素在B中的位置便等于第0列的第一个非零元素在B中的位置加上第0列的非零元素的个数。共三十一页数据结构(sh j ji u)与STL23引入两个数组作为辅助数据结构(sh j ji u)：numbern： 存储矩阵A中每列非零元素的个数；positionn：初始值表示矩阵A中每列的第一个非零 元素在B中的位置 共三十一页数据结构(sh j ji u)与STL24A=15 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0number 0 0 15 0 3 22 0 5 -15 1 1 11 1

14、 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 矩阵的行数5 矩阵的列数6 非零元个数7row col item0123456Max-1position21120123466 空 空 空 闲 闲 闲 矩阵的行数6 矩阵的列数5 非零元个数7row col item0123456Max-10015010 1 2 3 4 53022550-157111132134326604912共三十一页数据结构(sh j ji u)与STL25算法(sun f)伪代码1. 设置转置矩阵B的行数、列数和非零元素的个数；2. 计算A中每一列的非零元素个数，存储到number数组；3. 计算A中每一列的

15、第一个非零元素在B中的下标，存储到position数组；4. 依次取A中的每一个非零元素对应的三元组； 4.1 确定该元素在B中的下标pb； 4.2 将该元素的行号列号交换后存入B中pb的位置； 4.3 预置该元素所在列的下一个元素的存放位置；共三十一页数据结构(sh j ji u)与STL26十字(sh z)链表 每个非零元素，采用一个五元组结点表示 template struct snode/十字链表五元组结点int row,col;/行号与列号T val;/值struct snode * cnext, rnext;/列指针与行指针;同一行的非零元素构成一个带头结点的循环链表，同一列的非零

16、元素也构成一个带头结点的循环链表。 共三十一页数据结构(sh j ji u)与STL27共三十一页数据结构(sh j ji u)与STL28第四章 多维数组和广义(gungy)表学习内容：4.1 多维数组 4.2 矩阵的压缩存储 4.3 广义表 （略） 4.4 实例分析4.5 使用STL操作多维数组共三十一页数据结构(sh j ji u)与STL294.5 使用(shyng)STL操作多维数组 STL本身并没有二维、三维等多维数组的概念，但并不能说STL不支持多维数组 vector vector ivv; 对象ivv是向量的向量，相当于一个二维数组，但各维上元素的数目可以不同。 注意：“ ”非

17、“” 如果希望向量各维上的元素数目都相同，可以基于vector单独设计一个二维数组的类来完成此功能。见教材对C2DVector类的定义。C2DVector my2DArray(3,4); /建立一个 34 的数组。My2DArray.GrowCol(5); /动态增加到 5 列。类中已经重载了操作符 ，因此它可以像常规 C/C+ 二维数组一样使用。my2DArrayxy = 5；共三十一页数据结构(sh j ji u)与STL30本章(bn zhn)小结多维数组广义表实例分析操作多维数组逻辑结构存储结构存储寻址行优先存储列优先存储对称矩阵三角矩阵对角矩阵逻辑结构存储结构稀疏矩阵三元组表STL矩阵压缩十字链表广义链表BMP文件操作图像平滑转置算法共三十一页内容摘要第四章 多维数组。对于k 维数组，每个元素(yun s)都要受k个线性关系的约束。行优先存储。列优先存储。若按行优先存储，则aijk前面共