数组与串(完)要点.pptVIP

1.5 数组 一、数组的定义及运算 二、数组的顺序存储结构 三、稀疏矩阵的存储表示 四、规则矩阵的压缩存储 1.5 数组 一、数组的定义及运算 1、定义 是同类数据的有序集合 特征：下标与值一一对应 1.5 数组 2、运算 存储：根据给定的下标和值存入或修改相应的数组元素 查找：根据给定的下标查找相应数组元素的值 矩阵相关操作，如矩阵相加、相乘、转置 1.5 数组 二、数组的顺序存储结构 1.5 数组 二、数组的顺序存储结构 1、一维数组的顺序存储结构 与顺序表的地址计算相同 1.5 数组 三、稀疏矩阵的存储表示 1、稀疏矩阵定义 非零元素个数远少于矩阵元素个数的矩阵,且非零元素的分布无规律 1.5 数组 三、稀疏矩阵的存储表示 2、稀疏矩阵的三元组表示法 存储原则：只存储非零元素的信息，不为零元素分配空间 实现方式：三元组存储法 三元组(用行号,列号,值)唯一确定一个元素 行号 i 列号 j 值 value 1.5 数组 三、稀疏矩阵的存储表示 稀疏矩阵三元组的表示： 将矩阵的所有非零元素以某种次序 （行主序或列主序）排列 （行号，列号，值） 1.5 数组 三、稀疏矩阵的存储表示 1.5 数组 3、三元组顺序表 定义：使用顺序存储结构表示的三元组表 例1 ： 例1: 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。 法三：用带辅助向量的三元组表示。 方法： 增加2个辅助向量： ① 记录每行非0元素个数，用NUM（i）表示； ② 记录稀疏矩阵中每行第一个非0元素在三元组中的行号，用POS（i）表示。 四.稀疏矩阵的操作 方法1：压缩转置 函数实现 void transpose(SparseMatrix *a, SparseMatrix *b){ int col,i,k;k=1;/*转置矩阵的当前结点*/ /*转置矩阵特性的初始化*/ b-rows=a-cols;b-cols=a-rows;b-terms=a-terms; for(col=0;cola-cols;col++){ for(i=1;i=a-terms;i++) if(a-smArray[i].col==col){ b-smArray[k].row=a-smArray[i].col; b-smArray[k].col=a-smArray[i].row; b-smArray[k].value=a-smArray[i].value; k++; } } } 方法2 快速转置 设计思路： 令：M中的列变量用col表示； num[ col ]：存放M中第col 列中非0元素个数， cpot[ col ]：存放M中第col列的第一个非0元素 在转置矩阵的三元组数组中的位置， （即b.data中待计算的“恰当”位置 所需参考点） 函数实现 void fasttranspose(SparseMatrix *a, SparseMatrix *b){ int i,j,rowSize[MAXROWS],rowStart[MAXROWS]; b-rows=a-cols;b-cols=a-rows;b-terms=a-terms; for (i = 0; i a-Cols; i++) rowSize[i] = 0; for (i = 0; i a-Terms;i++) rowSize[a-smArray[i].col]++; rowStart[0] = 0; for(i=1;ia-Cols;i++) rowStart[i]=rowStart[i-1]+rowSize[i-1]; for ( i = 0; i a-Terms; i++ ) { j = rowStart[a-smArray[i].col]; b-smArray[j].row = a-smArray[i].col; b-smArray[j].col = a-smArray[i].row; b-smArray[j].value=a-smArray[i].value; rowStart[a-smArray[i].col]++; }}} 1.5 数组 五、规则矩阵的压缩存储(自学) 1、下三角矩阵的压缩存储 下三角阵 1.5 数组 五、规则矩阵的压缩存储 问：上三角矩阵的压缩存储