《数据结构chapter》课件.ppt

第五章 数组和广义表 5.1 数组的定义 2、稀疏矩阵的压缩存储方法 3、求转置矩阵 4、十字链表 （5）E=（a,E）——这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,…)))). （6）若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表。对非空广义表：称第一个元素为表头，其余元素组成的表称为表尾。 广义表最重要的两个基本操作：1） 取表头；2） 取表尾。 特点： 有次序性 有长度 有深度 可递归 可共享 广义表的存储结构 这种存储结构的特点是： 最上层的表结点数即为广义表的长度； 层次清楚； 表结点数目多，与广义表中括号对的数目不匹配。 广义表的存储结构 2. 同层结点链存储结构 有两类结点：表结点和单元素结点。 ┌────┬───┬───┐ │ tag=1 │ hp │ tp │ 表结点 └────┴───┴───┘ ┌────┬───┬───┐ │ tag=0 │ data │ tp │ 单元素结点 └────┴───┴───┘ tp为链接同层下一结点的指针域，其它域的含义同表头表尾链结构。 广义表的存储结构 同层结点链结构的特点是： 表结点的数目与广义表的括号对数目一致； 写递归算法不方便。 本章小结 实现：需要附设num和cpot两个数组。 num[col]：表示矩阵M中第col列中非零元个数； cpot[col]：指示M中第col列第一个非零元在mb中位置 显然有： cpot[1]=1; cpot[col]=cpot[col-1]+num[col-1]; (2?col ?a.nu) 1 3 5 7 8 8 9 col num[col] cpot[col] 1 2 2 2 3 2 4 1 5 0 6 1 7 0 方法2：快速转置算法 快速转置算法 Status FastTransmatrix ( TSMatrix M, TSMatrix 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 (t=1;t=M.tu;++t) ++num[M.data[t].j]; // 求M中每一列含非零元个数 cpot[1]=1; //求第col列中第1个非零元素在b.data中的序号，因为data[0]未用，所以从1开始。 修改向量内容（列坐标加1，给同列的下一非零元素定位用 快速转置算法 for (col=2;col=M.nu;++col) cpot[col]=cpot[col-1]+num[col-1]; for(p=1; p=M.tu; p++) { col=M.data[p].j; q=cpot[col]; } //if return OK; }//FastTransposeSMatrix T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++cpot[col]; } //for 得到被考察元素在新表中的位置 这个算法仅比前一个算法多用了两个辅助数组。 快速转置算法分析 从时间上看，算法中有四个并列的单循环，循环次数分别为nu和tu，因而总的时间复杂度为O（nu＋tu）。 在M的非零元素个数tu和mu×nu等数量级时，其时间复杂度为O（mu×nu），和经典算法的时间复杂度相同。 6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v 0 1 2 3 4 5 6 7 8 ma i j v 0 1 2 3 4 5 6 7 8 mb col num[col] cpot[col] 1 1 2 2 3 2 3 5 2 4 7 1 5 8 0 6 8 1 7 9 0 7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18