数据结构wu.pptVIP

数据结构课程的内容 第5章 数组和广义表（Arrays Lists） 5.1 数组的定义 二维数**组的特点： N维数组的数据类型定义 5.2 数组的顺序存储表示和实现 补充：计算二维数组元素地址的通式设一般的二维数组是A[c1..d1, c2..d2]，这里c1,c2不一定是0。 例2：已知二维数组Am,m按行存储的元素地址公式是： Loc(aij)= Loc(a11)+[(i-1)*m+(j-1)]*K , 按列存储的公式是？ Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K （尽管是方阵，但公式仍不同） 若是N维数组，其中任一元素的地址该如何计算？ Loc(j1,j2,…jn)=LOC(0,0,…0)＋ N维数组的顺序存储表示（见教材P93） 顺序存储方式：按低地址优先（或高地址优先）顺序存入一维数组。 5.3 矩阵的压缩存储 一、稀疏矩阵的压缩存储 例1 ： 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。 法三：用带辅助向量的三元组表示。 方法： 增加2个辅助向量： ① 记录每行非0元素个数，用NUM（i）表示； ② 记录稀疏矩阵中每行第一个非0元素在三元组中的行号，用POS（i）表示。 法四：用十字链表表示 二、稀疏矩阵的操作 方法1：压缩转置 方法2 快速转置 设计思路： 令：M中的列变量用col表示； num[ col ]：存放M中第col 列中非0元素个数， cpot[ col ]：存放M中第col列的第一个非0元素的位置， （即b.data中待计算的“恰当”位置所需参考点） 5.4 广义表的定义 2、特点： 有次序性 有长度 有深度 可递归 可共享 5.5 广义表的存储结构 讨论：按列优先的辅助向量求出后，下一步该如何操作？ 由a.data中每个元素的列信息，即可直接查出b.data中的重要参考点之位置，进而可确定当前元素之位置！ 0 1 1 2 2 2 num[col] 6 5 4 3 1 cpot[col] 2 1 col 规律： cpot(1)＝1 cpot[col] ＝ cpot[col-1] + num[col-1] 0 12 9 0 0 0 0 0 0 0 0 0 -3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 0 M 3 5 7 8 8 col 1 2 3 4 5 6 Status FastTransposeSMatrix（TSMatirx M, TSMatirx T） { T.mu = M.nu ;T .nu = M.mu ; T.tu = M.tu ; if ( T.tu ) { for(col = 1; col =M.nu; col++) num[col] =0; for( i = 1; i =M.tu; i ++) {col =M.data[ i ] .j ; ++num [col] ;} cpos[ 1 ] =1; for(col = 2; col =M.nu; col++) cpos[col ]=cpos[col-1]+num [col-1 ] ; for( p =1; p =M.tu ; p ++ ) { col =M.data[ p ]. j ; q =cpos [ col ]; T.data[q].i = M.data[p]. j; T.data[q].j = M.data[p]. i; T.data[q]. value = M.data[p]. value; + + cpos[col] ; } //for } //if return OK; } //FastTranposeSMatrix; 快速转置算法描述： //M用顺序存储表示，求M的转置矩阵T //先统计每列非零元素个数 //再生成每列首元位置辅助向量表 //p指向a.data，循环次数为非0元