数据结构(C语言版)严尉敏编.pptVIP

空表 LS = NULL 若表头为原子，则为 tag=0 atom 否则，依次类推。 非空表 LS tag=1 指向表头的指针 指向表尾的指针 A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C ) B 1 ^ 0 e 1 1 ^ 1 1 ^ 1 0 a 0 b 0 d 0 c C 1 ^ 1 1 ^ D A=NULL 即: A ^ ls =( a , ( ) , ( ( b , c ) , d ) ) 1 1 ^ 1 ^ 1 1 ^ 1 1 ^ 0 a 0 b 0 c 0 d ls 2）广义表的扩展线性链表存储结构 typedef enum{ ATOM, LIST} ElemTag ; // typedef struct GLNode{ ElemTag tag;//公共部分，用于区分原子结点和表结点 union { AtomType atom ; //atom是原子结点的值域 struct GLNode *hp; }; // 表结点的表头指针 struct GLNode *tp; //相当于线性链表的next，指向下一个 //元素结点 } *Glist ;//广义表类型 原子结点： tag=1 hp tp tag=0 atom tp 表结点: A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C ) A 1 ^ ^ B 1 ^ 0 e ^ 1 ^ 1 1 ^ D 1 C 1 ^ 1 ^ 0 d 0 a 0 b 0 c 5.6 m元多项式的表示：P 110-112 自学！ Status TransposeSMattrix(TSMatrix M, TSMatrix T){ //采用三元组表存储表示，求稀疏矩阵的转置矩阵T T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; if(T.tu) { q=1; //q表示下一次找到的非零元在T.data中的下标 for(col=1;col=M.nu;col++) for(p=1;p=M.tu;p++) { if(M.data[p].j==col ){T.data[q].i=M.data[p].j; T.data[q].j= M.data[p].i; T.data[q].e= M.data[p].e; ++q;} } return OK; } // TransposeSMattrix 其时间复杂度为: O(M.nu×M.tu)， 若 M.tu 与M.mu?M.nu同数量级 时，有O(M.mu ×M.nu2 ) 方法二：快速转置 其基本思想是对M.data仅扫描一遍，在扫描到每一个元素时将其放在T.data的合适的位置上。 cpot[1]=1; cpot[col]=cpot[col-1]+num[col-1]; (2?col ?M.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（快速转置）： i j e 1 2 12 1 3 9 3 1 -3 6 14 3 24 5 2 18 1 15 6 4 -7 M.data M.mu=6 M.nu=7 M.tu=8 转置后 得T T.mu=7 T.nu=6 T.tu=8 T.data