《第7周数组和稀疏矩阵第2讲-稀疏矩阵.pdf》由会员分享，可在线阅读，更多相关《第7周数组和稀疏矩阵第2讲-稀疏矩阵.pdf（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一个阶数较大的矩阵中的非零元素个数一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的相对于矩阵元素的 总个数总个数t十分小时十分小时，即即st时时，称称该矩阵为该矩阵为稀疏矩阵稀疏矩阵。 例如例如一个一个100100的矩阵的矩阵，若其中只有若其中只有100个非零元素个非零元素，就就 可称其为稀疏矩阵可称其为稀疏矩阵。 稀疏矩阵的定义稀疏矩阵的定义 稀疏矩阵和特殊矩阵的稀疏矩阵和特殊矩阵的不同点不同点： 特殊矩阵的特殊元素（值相同元素、常量元素）分布特殊矩阵的特殊元素（值相同元素、常量元素）分布有规律有规律。 稀疏矩阵的特殊元素（非稀疏矩阵的特殊元素（非0元素）分布元素）分布没有规律没有规律。
2、 稀疏矩阵的压缩存储方法是只存储非零元素。稀疏矩阵的压缩存储方法是只存储非零元素。 稀疏矩阵稀疏矩阵中的每一个非零元素需由一个三元组：中的每一个非零元素需由一个三元组： (i ，j ，ai,j) 唯一确定唯一确定，稀疏矩阵中的所有非零元素构成稀疏矩阵中的所有非零元素构成三元组线性表三元组线性表。 6.2.1 稀疏矩阵的三元组表示稀疏矩阵的三元组表示 一个一个67阶稀疏矩阵阶稀疏矩阵A的的三元组三元组线性表线性表表示表示 4700000 0060000 0005000 0000003 0000020 0000100 76 A 一个稀疏矩阵一个稀疏矩阵A 稀疏矩阵三元组表示稀疏矩阵三元组表示的演示
3、的演示 (0,2,1)(1,1,2)(2,0,3)(3,3,5)(4,4,6)(5,5,7)(5,6,4) 三元组线性表：三元组线性表： (0,2,1)，(1,1,2)，(2,0,3)，(3,3,5)， (4,4,6)，(5,5,7)，(5,6,4) 把把稀疏矩阵的三元组线性表按顺序存储结构稀疏矩阵的三元组线性表按顺序存储结构存储存储，则则称为稀称为稀 疏矩阵的三元组顺序表疏矩阵的三元组顺序表。 #define MaxSize 100/矩阵中非零元素最多个数矩阵中非零元素最多个数 typedef struct int r;/行号行号 int c;/列号列号 ElemType d;/元素值元素值
4、 TupNode;/三元组定义三元组定义 typedef struct int rows;/行数值行数值 int cols;/列数值列数值 int nums;/非零元素个数非零元素个数 TupNode dataMaxSize; TSMatrix;/三元组顺序表定义三元组顺序表定义 存 放 一 个 非 0 元 素 存 放 整 个 稀 疏 矩 阵 4700000 0060000 0005000 0000003 0000020 0000100 76 A ijaij 021 112 203 335 446 557 564 （1）从一个二维矩阵创建其三元组表示）从一个二维矩阵创建其三元组表示 以行序方式
5、扫描二维矩阵以行序方式扫描二维矩阵A，将其非零的元素插入到三元组，将其非零的元素插入到三元组t 的后面。的后面。 t: 约定约定：data域中表示的非零元素通常域中表示的非零元素通常以行序为主序顺序排以行序为主序顺序排 列列，它是一种下标按行有序的存储结构它是一种下标按行有序的存储结构。 这种有序存储结构可简化大多数矩阵运算算法这种有序存储结构可简化大多数矩阵运算算法。 void CreatMat(TSMatrix t.rows=M; t.cols=N; t.nums=0; for (i=0;iM;i+) for (j=0;j=t.rows | j=t.cols) return false;
6、/失败时返回失败时返回false while (kt.datak.r) k+;/查找行查找行 while (kt.datak.c) k+; /查找查找列列 算法如下：算法如下： 在t中按行、列号查找 if (t.datak.r=i else/不存在这样的元素时插入一个元素不存在这样的元素时插入一个元素 for (k1=t.nums-1;k1=k;k1-) t.datak1+1.r=t.datak1.r; t.datak1+1.c=t.datak1.c; t.datak1+1.d=t.datak1.d; t.datak.r=i;t.datak.c=j;t.datak.d=x; t.nums+;
7、return true;/成功时返回成功时返回true 修 改 元 素 增 加 元 素 （3）将指定位置的元素值赋给变量）将指定位置的元素值赋给变量执行执行x=Aij boolAssign(TSMatrix t,ElemType if (i=t.rows | j=t.cols) return false;/失败时返回失败时返回false while (kt.datak.r) k+; /查找行查找行 while (kt.datak.c) k+;/查找查找列列 if (t.datak.r=i else x = 0; return true;/成功时返回成功时返回true 先在三元组先在三元组t中找
8、到指定的位置中找到指定的位置，再将该处的元素值赋给再将该处的元素值赋给x。 在t中按行、 列号查找 找到了非 0的元素 没有找到， 为0元素 void DispMat(TSMatrix t) int i; if (t.nums=0) return; printf(“t%dt%dt%dn,t.rows,t.cols,t.nums); printf( -n); for (i=0;it.nums;i+) printf(t%dt%dt%dn, t.datai.r,t.datai.c, t.datai.d); （4）输出三元组）输出三元组 从头到尾扫描三元组从头到尾扫描三元组t，依次输出元素值，依次输出
9、元素值。 对于一个对于一个mn的矩阵的矩阵Am n， ，其转置矩阵是一个其转置矩阵是一个nm的矩阵的矩阵Bn m, 满足满足bi,j=aj,i，其中其中0im- -1，0jn- -1。 ijaij 021 112 203 335 446 557 564 ijbij 023 112 201 335 446 557 654 （5）矩阵转置矩阵转置 A6 7= 0 0 10 0 0 0 0 20 0 0 0 0 30 0 0 0 0 0 0 0 0 50 0 0 0 0 0 0 60 0 0 0 0 0 0 7 4 B7 6= 0 0 30 0 0 0 20 0 0 0 10 0 0 0 0 0 0
10、 0 50 0 0 0 0 0 60 0 0 0 0 0 7 0 0 0 0 0 4 转置转置 一种非高效的算法：按第一种非高效的算法：按第0、1、2、 、n- -1列列进行转换进行转换 203 112 021 557 446 335 564 ijaij 201 112 023 557 446 335 654 ijbij 矩阵转置 void TranTat(TSMatrix t,TSMatrix /q为为tb.data的下标的下标 tb.rows=t.cols; tb.cols=t.rows; tb.nums=t.nums; if (t.nums!=0)/当存在非零元素时执行转置当存在非零元素
11、时执行转置 for (v=0;vt.cols;v+) /tb.dataq中记录以列序排列中记录以列序排列 for (p=0;p(N)?(M):(N) /矩阵行列较大者矩阵行列较大者 typedef struct mtxn int row;/行号行号 int col;/列号列号 struct mtxn *right,*down;/向右和向下的指针向右和向下的指针 union/共用体类型共用体类型 int value; struct mtxn *link; tag; MatNode;/十字十字链表节点类型链表节点类型声明声明 十字链表节点结构和头节点的数据结构可定义如下：十字链表节点结构和头节点的数据结构可定义如下： 有关算法不做介绍。有关算法不做介绍。 1011张三张三1013李四李四1班班 1028王五王五1029刘六刘六 2班班 1082陈功陈功1085许斌许斌 8班班 15届届 【例例6- -2】十字链表的启示：十字链表的启示：设计存储某年级所有学生的存储设计存储某年级所有学生的存储 结构：结构： h 通过通过h来唯一标识学生存储结构。来唯一标识学生存储结构。 本章完本章完