Microsoft PowerPoint - Chapter5.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - Chapter5.ppt"

菀殷
7 years ago
Views:

1 第五章数组和特殊矩阵 5.1 数组数组的基本概念数组的存储结构 5.2 特殊矩阵的压缩存储对称矩阵的压缩存储三角矩阵的压缩存储对角矩阵的压缩存储稀疏矩阵的压缩存储 1

2 5.1.1 数组的基本概念数组是程序设计中的常用数据类型它分为一维数组二维数组和多维数组一维数组是一个线性表二维数组和多维数组可看成是一维数组的推广例如, 二维数组 : A mn = a 11 a 12 a 1n a 21 a 22 a 2n a m1 a m2 a mn 二维数组可以看成是由多个行向量组成的向量, 也可以看成是个列向量组成的向量 2

3 在 C++ 语言中, 一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型, 也就是说, typedef int array2[m][n]; 等价于 : typedef int array1[n]; typedef array1 array2[m]; 3

4 二维数组三维数组行向量下标 i 页向量下标 i 列向量下标 j 行向量下标 j 列向量下标 k 4

5 5.1.2 数组的存储结构由于对数组一般不做插入和删除操作, 也就是说, 数组一旦建立, 结构中的元素个数和元素间的关系就不再发生变化因此, 一般都是采用顺序存储的方法来表示数组由于计算机的内存结构是一维的, 因此用一维内存来表示多维数组, 就必须按某种次序将数组元素排成一列序列, 然后将这个线性序列存放在存储器中 5

6 通常有两种顺序存储方式 : ⑴ 行优先顺序将数组元素按行排列, 第 i+1 个行向量紧接在第 i 个行向量后面以二维数组为例, 按行优先存储的线性序列为 : a 11,a 12,,a 1n,a 21,a 22, a 2n,,a m1,a m2,,a mn ⑵ 列优先顺序将数组元素按列向量排列, 第 j+1 个列向量紧接在第 j 个列向量之后如二维数组 A 的 m*n 个元素按列优先存储的线性序列为 : a 11,a 21,,a m1,a 12,a 22, a m2,,a n1,a n2,,a nm 6

7 以上规则可以推广到多维数组的情况 : 行优先顺序可规定为先排最右的下标, 从右到左, 最后排最左下标 : 列优先顺序先排最左下标, 从左向右, 最后排最右下标 7

8 a a a L a , p 1 a a a L a , p 1 KKKKKKKK a a a L a 0, n 1,0 0, n 1,1 0, n 1,2 0, n 1, p 1 a a a L a , p 1 a a a L a , p 1 KKKKKKKK a a a L a 1, n 1,0 1, n 1,1 1, n 1,2 1, n 1, p 1 M i i = = 1 0 a a a L a m 1,00 m 1,01 m 1,02 m 1,0, p 1 a a a L a m 1,10 m 1,11 m 1,12 m 1,1, p 1 KKKKKKKK a a a L a m 1, n 1,0 m 1, n 1,1 m 1, n 1,2 m 1, n 1, p 1 i = m 1

9 地址计算方法二维数组元素 a ij 的地址计算函数为 : 行优先 :LOC(a ij )=LOC(a 00 )+(i*n+j)*d 三维数组元素 A ijk 的地址计算函数为 : 行优先 :LOC(a ijk )=LOC(a 000 )+(i*n*p+j*p+k)*d 9

10 5.2 特殊矩阵的压缩存储在科学与工程计算问题中, 矩阵是一种常用的数学对象, 在高级语言编制程序时, 常将一个矩阵描述为一个二维数组当矩阵中的非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下, 会占用许多单元去存储重复的非零元素或零元素, 这对高阶矩阵会造成极大的浪费为了节省存储空间, 我们可以对这类矩阵进行压缩存储 : 即为多个相同的非零元素只分配一个存储空间 ; 对零元素不分配空间 10

11 5.2.1 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵 1 对称矩阵在一个 n 阶方阵 A 中, 若元素满足下述性质 : a ij = a ji 0 i,j n-1 则称 A 为对称矩阵对称矩阵中的元素关于主对角线对称, 故只要存储矩阵中上三角或下三角中的元素, 这样, 能节约近一半的存储空间 11

12 a 00 a 10 a 11 a 20 a 21 a 23.. a n-1 1 a n-1 2 a n-1 n-1 图对称矩阵我们可以按行优先顺序将这些元素存放在一个向量 sa[n(n+1)/2] 中 a 00 a 10 a 11 a 20 a n-1 0 a n-1,n-1 矩阵元素 a ij 和数组分量 sa[k] 之间的对应关系如下 : - k = i*(i+1)/2+j 若 i >= j - k = j*(j+1)/2+i 若 i < j 12

13 2 三角矩阵以主对角线划分, 三角矩阵有上三角和下三角两种上三角矩阵如图所示, 它的下三角 ( 不包括主对角线 ) 中的元素均为常数 a 00 a 01 a 0 n-1 a 00 c c c a 11 a 1 n-1 a 10 a 11 c.... c c a n-1 n-1 a n-1 0 a n-1 1 a n-1 n-1 (a) 上三角矩阵 (b) 下三角矩阵三角矩阵可压缩存储到向量 sa[n(n+1)/2+1] 中, 其中常数 c 存放在向量的最后一个分量中. 13

14 对于上三角矩阵, 若按行优先顺序存放矩阵中的元素 a ij 时,sa[k] 和 a ij 的对应关系是 : k= i(2n-i+1)/2+j-i 当 i<=j n(n+1)/2 当 i>j 下三角矩阵的存储和对称矩阵类似,sa[k] 和 a ij 对应关系是 : k= i(i+1)/2+j 当 i>=j n(n+1)/2 当 i<j 14

15 3 对角矩阵对角矩阵中, 所有的非零元素集中在以主对角线为中心的带状区域中, 即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外, 其余元素皆为零 a 00 a 01 a 10 a 11 a 12 a 21 a 22 a a n-2 n-3 a n-2 n-2 a n-2 n-1 a n-1 n-2 a n-1 n-1 15

16 一个 k 对角矩阵 (k 为奇数 )A 是满足下述条件的矩阵 : 若 i-j >(k-1)/2, 则元素 a ij =0 对角矩阵可按行优先顺序或对角线的顺序, 将其压缩存储到一个向量中, 并且也能找到每个非零元素和向量下标的对应关系例如 : 若将三对角矩阵中的元素按行优先顺序存放在数组 sa[3n-2] 中, 则 sa[k] 与三对角矩阵中的元素 a ij 存在的对应关系为 : k = 3i-1+j-(i-1)=2*i+j 16

17 5.2.2 稀疏矩阵设矩阵 A 中有 s 个非零元素, 若 s 远远小于矩阵元素的总数 ( 即 s m n), 则称 A 为稀疏矩阵 M= 若以常规方法, 即以二维数组表示, 则 : 1) 零值元素占的空间很大 ; 2) 计算中进行了很多和零值的运算 ; 17

18 解决问题的原则 : 1) 尽可能少存或不存零值元素 ; 2) 尽可能减少没有实际意义的运算 ; 3) 运算方便 ; 即 : 能尽可能快地找到与下标值 (i, j) 对应的非零值元 ; 能尽可能快地找到同一行或同一列的非零值元 ; 由于非零元素的分布一般是没有规律的, 因此在存储非零元素的同时, 还必须同时记下它所在的行和列的位置 (i,j) 反之, 一个三元组 (i,j,a ij ) 唯一确定了矩阵 A 的一个非零元因此, 稀疏矩阵可由表示非零元的三元组表及其行列数唯一确定 18

19 例如 : M= 可用下列三元组表 : ( (1,2,12), (1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18), (6,1,15),(6,4,-7) ) 加上 (6,7) 这一对行列值便可作为下列矩阵 M 的一种描述而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法 19

20 一三元组顺序表假设以顺序存储结构来表示三元组表, 则可得到稀疏矩阵的一种压缩存储方法三元顺序表 20

21 template<class T> struct Triple{ int r, c; // 该非零元素的行下标与列下标 T elem; // 该非零元素的元素值 }; template<class T> class SparseMatrix{ vector<triple<t>> trilist; public: }; int rows, cols, num; // 三元组表 // 矩阵的行数列数和非零元素个数 SparseMatrix(); // 无参构造函数 SparseMatrix(Triple<T> *tlist, int rs, int cs, int n); // 构造函数 void trans(sparsematrix& B); // 矩阵转置运算 SparseMatrix& plus(sparsematrix& B); // 矩阵加法运算 SparseMatrix& mult(sparsematrix& B); // 矩阵乘法法运算 void print(); // 打印矩阵信息 21

22 例 : 稀疏矩阵的转置算法将一个 m n 的矩阵 A, 转置为一个 n m 的矩阵 B, 即将表示 A 的三元组表 a 转换为对应于 B 的三元组表 b 算法的处理步骤 : 1. 将矩阵行列值互换 2. 将每个三元组中 i 和 j 值互换 3. 重排三元组元素之间的次序 22

23 实现三元组次序元素重排的方法 : 1. 直接按 A.triList 中元素的列序进行转置 2. 按 B.triList 元素的行序进行转置, 但将转置后的三元组放入 B 中的适当位置 23

24 template<class T> void SparseMatrix<T>::trans(SparseMatrix<T>& B){ B.rows=cols; B.cols=rows; B.num=num; if(num==0) return; // 若非零元素个数为, 则转置结束 q = 0; for(col=0; col<cols; ++col) // 按矩阵 A 的列序进行转置 for(p=0; p<num; ++p) if( trilist[p].c == col ){ B.triList[q].r=triList[p].c; B.triList[q].c=triList[p].r; B.triList[q].elem=triList[p].elem; ++q; } } 24

25 快速矩阵转置算法基本思想 : 直接按矩阵 A 的行序进行转置, 即通过一趟扫描矩阵 A 的三元组表, 同时将每个非零元素转置后直接放入矩阵 B 的三元组表中的适当位置关键问题 : 每次从矩阵 A 的三元组表中取出一个非零元素后, 如何确定该元素转置后在矩阵 B 的三元组表中的相应位置? 如果能预先确定矩阵 A 的每一列的第一个非零元素在矩阵 B 三元组表中的位置, 每一列的其他非零元素则依次排在该位置的后面 25

26 快速矩阵转置算法为此, 需要引入两个辅助数组 : cnum[cols] 每个分量表示矩阵 A 的某一列的非零元素个数 cpot[cols] 每个分量的初始值表示矩阵 A 的某一列的第一个非零元素在矩阵 B 中的位置 26

27 template<class T> void SparseMatrix<T>::trans(SparseMatrix<T>& B){ B.rows=cols; B.cols=rows; B.num=num; if(num==0) return; // 若非零元素个数为零, 则转置结束 int *cnum=new int[cols]; int *cpot=new int[cols]; for(col=0; col<cols; ++col) cnum[col]=0; // 置初值 for(t=0; t<num; ++t) // 初始化数组 cnum 的元素值 ++cnum[trilist[t].c]; cpot[0] = 0; for(col=1; col<cols; ++col) // 初始化数组 cpot 的元素值 cpot[col] = cpot[col-1] + cnum[col-1];

28 } } for(p=0; p<num; ++p ) { col = trilist[p].c; // 取当前非零元素的列号 q = cpot[col]; // 取当前非零元素在 B 中的位置 B.triList[q].r = trilist[p].c; B.triList[q].c = trilist[p].r; B.triList[q].elem = trilist[p].elem; ++cpot[col cpot[col] ; // 预置本列的下一个非零元素在 B 中的位置 delete[] cnum; delete[] cpot;

29 二十字链表三元组表是用顺序方法来存储稀疏矩阵中的非零元素, 当非零元素的位置或个数经常发生变化时, 三元组表就不适合作稀疏矩阵的存储结构十字链表 : 每个非零元素值用含五个域的结点来表示即除行列和值本身之外, 增加了两个指针域 : - 行指针域 - 列指针域 29

30 M =

31 稀疏矩阵的十字链表存储表示 : template<class T> struct CrossNode{ int r, c; // 该非零元素所在的行号和列号 T elem; CrossNode *right, *down; }; template<class T> class CrossMatrix{ vector<crossnode<t>*> rheads, cheads; int rows, cols, num; // 矩阵的行数列数和非零元素个数 public: CrossMatrix(); // 无参构造函数 CrossMatrix(int r, int c, int n); // 构造函数 void trans(crossmatrix& B); // 矩阵转置运算 CrossMatrix& plus(crossmatrix& B); // 矩阵加法运算 CrossMatrix& mult(crossmatrix& B); // 矩阵乘法运算 void print(); // 打印矩阵信息 }; 31

32 32

2003年

2003年 00 年数学考研试卷 - 线性代数部分试卷一一填空题 ( 每小题 4 分 ) () 曲面 z x y 与平面 x 4y z 0 平行的切平面的方程是解 : x 4y z 5 设 ( x0, y0, z 0) 为与平面 x 4y z 0 平行的切平面的切点坐标, 则过 ( x0, y0, z 0) 的法向量为 { x0, y0, } 于是过 ( x0, y0, z 0) 的切平面方程为 x0 (