2015_SHI_DS_线性表.ppt

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元素总个数tu //查辅助向量表得q，即T中位置 //重要语句！修改向量表中列坐标值，供同一列下一非零元素定位之用！ 1. 与常规算法相比，附加了生成辅助向量表的工作。增开了2个长度为列长的数组(num[ ]和cpos[ ]）。 传统转置：O(mu*nu) 压缩转置：O(mu*tu) 压缩快速转置：O(nu+tu)——牺牲空间效率换时间效率。 快速转置算法的效率分析： 2. 从时间上，此算法用了4个并列的单循环，而且其中前3个单循环都是用来产生辅助向量表的。 for(col = 1; col =M.nu; col++) 循环次数＝nu; for( i = 1; i =M.tu; i ++) 循环次数＝tu; for(col = 2; col =M.nu; col++) 循环次数＝nu; for( p =1; p =M.tu ; p ++ ) 循环次数＝tu; 该算法的时间复杂度＝(nu*2)+(tu*2)=O(nu+tu） 讨论：最恶劣情况是tu=nu*mu(即矩阵中全部是非零元素）， 而此时的时间复杂度也只是O(mu*nu)，并未超过传统转置算法的时间复杂度。 小结： 稀疏矩阵相乘的算法见教材P101-103 5.4 广义表的定义 广义表是线性表的推广，也称为列表（lists） 记为： LS = ( a1 , a2 , ……， an ) 广义表名 表头(Head） 表尾 (Tail) 1、定义： ① 第一个元素是表头，而其余元素组成的表称为表尾； ② 用小写字母表示原子类型，用大写字母表示列表。 n是表长 在广义表中约定： 讨论：广义表与线性表的区别和联系？ 广义表中元素既可以是原子类型，也可以是列表； 当每个元素都为原子且类型相同时，就是线性表。 2、特点： 有次序性 有长度 有深度 可递归 可共享 一个直接前驱和一个直接后继 ＝表中元素个数 ＝表中括号的重数 自己可以作为自己的子表 可以为其他广义表所共享 特别提示： 任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。 E=(a,E)=(a,(a,E))= (a,(a,(a,…….)))，E为递归表 1）A =( ) 2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C ) 5）E=(a, E) 例1：求下列广义表的长度。 n=0，因为A是空表 n=1，表中元素e是原子 n=2，a 为原子，(b,c,d)为子表 n=3，3个元素都是子表 n=2，a 为原子，E为子表 D=(A,B,C)=(( ),(e),(a,(b,c,d)))，共享表 讨论： next[ j ]有何物理意义？ next[j]函数表征着模式中两段字符之间相匹配的最大子串的长度（除串本身外）。 可见，模式中相似部分越