【正文】 )。 while ( i n ) { int x = (i)。 //在 B中搜索它 if ( k == 1 ) { (i)。 } else i++。 ? 系數(shù) a0, a1, a2, …, an ? 指數(shù) 0, 1, 2, …, n。 //構(gòu)造函數(shù) int operator ! ( )。 int LeadExp ( )。 Polynomial Mult (Polynomial poly)。 //求值 } 多項(xiàng)式 (Polynomial)的抽象數(shù)據(jù)類型 include class power { double x。 double mul。 //構(gòu)造函數(shù) double get_power ( ) { return mul。 創(chuàng)建 power類，計(jì)算 x的冪 power :: power (double val, int exp) { //按 val值計(jì)算乘冪 x = val。 mul = 。 for ( 。 exp) mul = mul * x。 cout ( ) “\n”。 組表示 ) float coef [maxDegree+1]。 組表示 ) float * coef。 coef = new float [degree + 1]。但對于指數(shù)不全的多項(xiàng)式如 P101(x) = 3 + 5x50 14x101, 不經(jīng)濟(jì)。 class term { //多項(xiàng)式的項(xiàng)定義 friend Polynomial。 //系數(shù) int exp。 a0 a1 a2 …… ai …… am e0 e1 e2 …… ei …… em coef exp 0 1 2 i m class Polynomial { //多項(xiàng)式定義 public: …… private: static term termArray[MaxTerms]。 //當(dāng)前空閑位置指針 // term Polynomial::termArray[MaxTerms]。 int start, finish。若未變成 0，則將結(jié)果加到結(jié)果多項(xiàng)式。 ? 若有一個(gè)多項(xiàng)式已檢測完，將另一個(gè)多項(xiàng)式剩余部分復(fù)制到結(jié)果多項(xiàng)式。 int a = start。 = free。 while ( a = finish amp。 b = ) Switch ( pare ( termArray[a].exp, termArray[b].exp) ) { //比較對應(yīng)項(xiàng)指數(shù) case ?=? : //指數(shù)相等 c = termArray[a].coef + //系數(shù)相加 termArray[b].coef。 a++。 break。 b++。 case 39。: //a指數(shù)小 , 建立新項(xiàng) NewTerm ( termArray[a].coef, termArray[a].exp )。 } for ( 。 a++ ) //a未檢測完時(shí) NewTerm ( termArray[a].coef, termArray[a].exp )。 b = 。 = free1。 } 在多項(xiàng)式中加入新的項(xiàng) void Polynomial :: NewTerm ( float c, int e ) { //把一個(gè)新的項(xiàng)加到多項(xiàng)式 C(x)中 if ( free = maxTerms ) { cout Too many terms in polynomials” endl。 } termArray[free].coef = c。 free++。 ? 為節(jié)省存儲空間，應(yīng)只存儲非零元素。 ? 每一個(gè)非零元素由一個(gè)三元組唯一確定： ( 行號 row, 列號 col, 值 value ) 稀疏矩陣的抽象數(shù)據(jù)類型 templateclass Type class SparseMatrix。 //非零元素行號 /列號 Type value。 //行 /列 /非零元素?cái)?shù) TritupleType smArray[MaxTerms]。 SparseMatrixTypeamp。)。 Add (SparseMatrix Type a, SparseMatrixType b)。 Multiply(SparseMatrix Type a, SparseMatrixType b)。 即矩陣 A 的行成為矩陣 B 的列，矩陣 A 的列成為矩陣 B 的行。當(dāng)行號相同時(shí)，按列號遞增的順序存放。 0000280000000091039000000006000017000110150022022?????????????????????稀疏矩陣 行行(( rr oo w )) 列列(( cc oo ll )) 值值(( vv aa ll uu ee )) [0] 00 33 22 22 [1] 00 66 11 55 [2] 11 11 11 11 [3] 11 55 11 77 [4] 22 33 66 [5] 33 55 33 99 [6] 44 00 99 11 [7] 55 22 22 88???????????????????????0000015003901700000000006022280000000001100910000 轉(zhuǎn)置矩陣 行行(( rr oo ww )) 列列(( cc oo ll )) 值值(( vv aa ll uu ee )) [0] 00 44 99 11 [1] 11 11 11 11 [2] 22 55 22 88 [3] 33 00 22 22 [4] 33 22 66 [5] 55 11 11 77 [6] 55 33 33 99 [7] 66 00 11 66用三元組表表示的稀疏矩陣及其轉(zhuǎn)置 行行(( rr oo ww )) 列列(( cc oo ll )) 值值(( vv aa ll uu ee )) 行行(( rr oo ww )) 列列(( cc oo ll )) 值值(( vv aa ll uu ee )) [0] 00 33 22 22 [0] 00 44 99 11 [1] 00 66 11 55 [1] 11 11 11 11 [2] 11 11 11 11 [2] 22 55 22 88 [3] 11 55 11 77 [3] 33 00 22 22 [4] 22 33 66 [4] 33 22 66 [5] 33 55 33 99 [5] 55 11 11 77 [6] 44 00 99 11 [6] 55 33 33 99 [7] 55 22 22 88 [7] 66 00 11 66稀疏矩陣轉(zhuǎn)置算法思想 ? 設(shè)矩陣列數(shù)為 Cols，對矩陣三元組表掃描 Cols 次。 ? 第 k 次掃描找尋所有列號為 k 的項(xiàng)，將其行號變列號、列號變行號，順次存于轉(zhuǎn)置矩陣三元組表。 SparseMatrixType :: Transpose (SparseMatrixTypeamp。 = 。 = 。 //轉(zhuǎn)置三元組表存放指針 for ( int k = 0。 k++ ) //對所有列號處理一遍 for ( int i = 0。 i++ ) if ( [i].col == k ) { [CurrentB].row = k。 [CurrentB].value= [i].value。 } } return b。 ? 若矩陣有 200 行， 200 列， 10,000 個(gè)非零元素，總共有 2,000,000 次處理。 ? 掃描矩陣三元組表，根據(jù)某項(xiàng)列號，確定它轉(zhuǎn)置后的行號 , 查 rowStart 表 , 按查到的位置直接將該項(xiàng)存入轉(zhuǎn)置三元組表中 [0] [1] [2] [3] [4] [5] [6] 語 義row Siz e 1 1 1 2 0 2 1 矩陣 A 各列非 零元素個(gè)數(shù)row Start 0 1 2 3 5 5 7 矩陣 B 各行開 始存放位置 for ( int i = 0。 i++ ) rowSize[i] = 0。 i 。 rowStart[0] = 0。 i Cols。 稀疏矩陣的快速轉(zhuǎn)置 template class Type SparseMatrixTypeamp。 a) { int *rowSize = new int[]。 SparseMatrixType b ( , )。 = 。 if ( 0 ) { for (int i = 0。 i++) rowSize[i] = 0。 i Terms。 rowStart[0] = 0。 i 。 for ( i = 0。 i++ ) { int j = rowStart[[i].col]。 [j].col = [i].row。 rowStart[[i].col]++。 delete [ ] rowStart。 } 字符串 (String) 字符串是