第3章多维数组和广义表.pptVIP

第三章 多维数组和广义表; 数组的两种顺序存储结构 以行序为主序（行优先顺序） 以列序为主序（列优先顺序）;Loc( aij)=Loc(a11)+[(i-1)*n+(j-1)]*d ;??按列序为主序存放;3.2 矩阵的压缩存储;2. 三角矩阵(下三角); 三角矩阵(上三角);3 对角矩阵;3.2.2 特殊矩阵的抽象数据类型;3.2.3 特殊矩阵基本算法描述; ElemType GetMatrixElem (Matrix m, int i, int j); { //取特殊矩阵元素 if(m.type= =1) { //对称矩阵 if(i=j) return m.data[i?(i+1)/2+j]; else return m.data[j?(j+1)/2+i]; } else if(m.type= =2) { //下三角矩阵 if(i=j) return m.data[i?(i+1)/2+j)]; else return m.data[m.size?(m.size+1)/2]; } else { //上三角矩阵 if(j=i) return m.data[i?(2?m.size-i+1)/2+j-i]; else return m.data[m.size?(m.size+1)/2]; } };Void SetMatrixElem (Matrix m, int i, int j, ElemType v) { //赋特殊矩阵元素值 if(m.type= =1) { //对称矩阵 if(i=j) m.data[i?(i+1)/2+j]=v; else m.data[j?(j+1)/2+i]=v; } else if(m.type= =2) { //下三角矩阵 if(i=j) m.data[i?(i+1)/2+j)]=v; else m.data[m.size?(m.size+1)/2]=v; } else { //上三角矩阵 if(j=i) m.data[i?(2?m.size-i+1)/2+j-i]=v; else m.data[m.size?(m.size+1)/2]=v; } };Void ClearMatrix (Matrix m) //清除特殊矩阵 { m.type=-1; m.size=0; delete [ ] m.data; }; 稀疏矩阵的压缩存储原则：只存矩阵的行列数和每个非零元的行列下 标及其值。矩阵M可由{(0,1,12), (0,2,9), (2,0,-3), (2,5,14), (3,2,24), (4,1,18), (5,0,15), (5,3,-7) } 和矩阵行列数(6,7)唯一确定。;稀疏矩阵的压缩存储方法 1. 三元组表（顺序存储结构）;;求转置矩阵 问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。 问题分析：转置矩阵B中的元素bij即为矩阵A中的元素aji。B的行数等于A的列数，B的列数等于A的行数 ，将A三元组中的i和j互换后拷贝到B三元组中，重排B三元组次序，使其中元素以i（行)为主序。;1;SMatrix *TransMat(SMatrix *a) //求矩阵a转置矩阵b { int col, n; SMatrix *b=new SMatrix[1]; //为转置矩阵B申请内存 b?m=a?n; b?n=a?m; b?t=a?t; if(b?t= =0) return b; for(col=1, n=1; col=a?m; col++) //按A的列次序拷贝 for(int k=1; k=a?t; k++) //扫描整个三元组 if( a?data[k].col= =col ) //拷贝第col列的三元组 { b?data[n].col=a?data[k].row; b?data[n].row=a?data[k].col; b?data[n].val=a?data[k].val;