【文章內(nèi)容簡介】 3 6 4 0 91 空 空 空 閑 閑 閑 row col item 0 1 2 3 4 5 6 MaxTerm1 5（矩陣的行數(shù)） 6（矩陣的列數(shù)） 7（非零元個數(shù)） row col item 0 1 2 3 4 5 6 MaxTerm1 6（矩陣的行數(shù)） 5（矩陣的列數(shù)） 7（非零元個數(shù)） 在矩陣 A中查找第 3列非零元，順序存儲到矩陣 B中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 數(shù)據(jù)結構（ C++版） 清華大學出版社 矩陣的壓縮存儲 0 0 15 0 3 22 0 5 15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 閑 閑 閑 row col item 0 1 2 3 4 5 6 MaxTerm1 5（矩陣的行數(shù)） 6（矩陣的列數(shù)） 7（非零元個數(shù)） row col item 0 1 2 3 4 5 6 MaxTerm1 6（矩陣的行數(shù)） 5（矩陣的列數(shù)） 7（非零元個數(shù)） 在矩陣 A中查找第 4列非零元，順序存儲到矩陣 B中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 數(shù)據(jù)結構（ C++版） 清華大學出版社 矩陣的壓縮存儲 0 0 15 0 3 22 0 5 15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 閑 閑 閑 row col item 0 1 2 3 4 5 6 MaxTerm1 5（矩陣的行數(shù)） 6（矩陣的列數(shù)） 7（非零元個數(shù)） row col item 0 1 2 3 4 5 6 MaxTerm1 6（矩陣的行數(shù)） 5（矩陣的列數(shù)） 7（非零元個數(shù)） 在矩陣 A中查找第 5列非零元，順序存儲到矩陣 B中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 15 數(shù)據(jù)結構（ C++版） 清華大學出版社 矩陣的壓縮存儲 0 0 15 0 3 22 0 5 15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 閑 閑 閑 row col item 0 1 2 3 4 5 6 MaxTerm1 5（矩陣的行數(shù)） 6（矩陣的列數(shù)） 7（非零元個數(shù)） row col item 0 1 2 3 4 5 6 MaxTerm1 6（矩陣的行數(shù)） 5（矩陣的列數(shù)） 7（非零元個數(shù)） 在矩陣 A中查找第 6列非零元，順序存儲到矩陣 B中 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 15 數(shù)據(jù)結構（ C++版） 清華大學出版社 1. 設置轉(zhuǎn)置后矩陣 B的行數(shù) 、 列數(shù)和非零元個數(shù)； 2. 在 B中設置初始存儲位置 pb； 3. for (col=最小列號 。 col=最大列號 。 col++) 在 A中查找列號為 col的三元組； 交換其行號和列號 ， 存入 B中 pb位置； pb++； 矩陣的壓縮存儲 三元組順序表轉(zhuǎn)置算法 Ⅰ —— 偽代碼 數(shù)據(jù)結構（ C++版） 清華大學出版社 分析 ： A中第 0列的第一個非零元素一定存儲在 B中下標為 0的位置上，該列中其它非零元素應存放在 B中后面連續(xù)的位置上，那么第 1列的第一個非零元素在B中的位置便等于第 0列的第一個非零元素在 B中的位置加上第 0列的非零元素的個數(shù)，以此類推。 基本思想： 順序取，直接存。 即 在 A中依次取三元組，交換其行號和列號放到 B 中 適當 位置。 矩陣的壓縮存儲 三元組順序表轉(zhuǎn)置算法 —— 算法 Ⅱ 如何確定當前從 A中取出的三元組在 B中的位置？ 數(shù)據(jù)結構（ C++版） 清華大學出版社 矩陣的壓縮存儲 三元組順序表轉(zhuǎn)置算法 —— 算法 Ⅱ row col item 0 1 2 3 4 5 6 MaxTerm1 6（矩陣的行數(shù)） 5（矩陣的列數(shù)） 7（非零元個數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 15 第 0列第 1個非零元素 第 0列有 2個非零元素 第 1列第 1個非零元素 數(shù)據(jù)結構（ C++版） 清華大學出版社 引入兩個數(shù)組作為輔助數(shù)據(jù)結構： num[nu]： 存儲矩陣 A中某列的非零元素的個數(shù)； cpot[nu]： 初值表示矩陣 A中某列的第一個非零元素在 B中的位置。 數(shù)據(jù)結構設計： cpot[0]=0； cpot[col]=cpot[col1]+num[col1]； 1≤col＜ nu num與 cpot存在如下遞推關系： 矩陣的壓縮存儲 三元組順序表轉(zhuǎn)置算法 —— 算法 Ⅱ 數(shù)據(jù)結構（ C++版） 清華大學出版社 0 0 15 0 3 22 0 5 15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 閑 閑 閑 row col item 0 1 2 3 4 5 6 MaxTerm1 5（矩陣的行數(shù)） 6（矩陣的列數(shù)） 7（非零元個數(shù)） 矩陣的壓縮存儲 col 0 1 2 3 4 5 num[col] 2 1 1 2 0 1 cpot[col] 0 2 3 4 6 6 根據(jù)矩陣 A計算 num和 cpot 數(shù)據(jù)結構（ C++版） 清華大學出版社 0 0 15 0 3 22 0 5 15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 閑 閑 閑 row col item 0 1 2 3 4 5 6 5（矩陣的行數(shù)） 6（矩陣的列數(shù)） 7（非零元個數(shù)） 矩陣的壓縮存儲 將矩陣 A中 col列元素存放在 B中下標為 cpot[col]的位置 row col item 0 1 2 3 4 5 6 6（矩陣的行數(shù)） 5（矩陣的列數(shù)） 7（非零元個數(shù)） cpot[0] cpot[1] cpot[2] cpot[3] cpot[4] cpot[5] 0 0 15 cpot[0] 數(shù)據(jù)結構（ C++版） 清華大學出版社 0 0 15 0 3 22 0 5 15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 閑 閑 閑 row col item 0 1 2 3 4 5 6 5（矩陣的行數(shù)） 6（矩陣的列數(shù)） 7（非零元個數(shù)） 矩陣的壓縮存儲 將矩陣 A中 col列元素存放在 B中下標為 cpot[col]的位置 row col item 0 1 2 3 4 5 6 6（矩陣的行數(shù)） 5（矩陣的列數(shù)） 7（非零元個數(shù)） cpot[1] cpot[2] cpot[3] cpot[4] cpot[5] 0 0 15 cpot[0] 3 0 22 cpot[3] 數(shù)據(jù)結構（ C++版） 清華大學出版社 0 0 15 0 3 22 0 5 15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 閑 閑 閑 row col item 0 1 2 3 4 5 6 5（矩陣的行數(shù)） 6（矩陣的列數(shù)） 7（非零元個數(shù)） 矩陣的壓縮存儲 將矩陣 A中 col列元素存放在 B中下標為 cpot[col]的位置 row col item 0 1 2 3 4 5 6 6（矩陣的行數(shù)） 5（矩陣的列數(shù)） 7（非零元個數(shù)） cpot[1] cpot[2] cpot[4] 0 0 15 cpot[0] 3 0 22 cpot[3] 5 0 15 cpot[5] cpot[5] 數(shù)據(jù)結構（ C++版） 清華大學出版社 0 0 15 0 3