Chap 2 Array (陣列)

抽象資料型態 C++中, 類別(class)包含四個元件: 類別名稱 資料成員 : the data that makes up the class 成員函數 : the set of operations that may be applied to the objects of class 程式可被使用程度 : public, protected and private.

Definition of Rectangle #ifndef RECTANGLE_H #define RECTANGLE_H Class Rectangle{ Public: Rectangle(); ~Rectangle(); int GetHeight(); int GetWidth(); Private: int xLow, yLow, height, width; }; #endif

Array char A[3][4]; // row-major 邏輯結構 實際結構 映射: A[i][j]=A[0][0]+i*4+j 1 邏輯結構 實際結構 1 2 3 A[0][0] A[0][1] 1 A[0][2] 2 A[0][3] A[1][0] A[2][1] A[1][1] A[1][2] A[1][3] 映射: A[i][j]=A[0][0]+i*4+j

Array 一維陣列的運算 儲存 將新值寫入陣列中某個位置 A[3] = 45 O(1) 1 2 3 A 45 ...

多項式表示法 Representation 1 private: int degree; // degree ≤ MaxDegree float coef [MaxDegree + 1]; Representation 2 int degree; float *coef; Polynomial::Polynomial(int d) { degree = d; coef = new float [degree+1]; } Representation 3 class Polynomial; // forward delcaration class term { friend Polynomial; float coef; // coefficient int exp; // exponent }; static term termArray[MaxTerms]; static int free; int Start, Finish; term Polynomial:: termArray[MaxTerms]; Int Polynomial::free = 0; // location of next free location in temArray

利用陣列表達多項式 利用陣列表示以下兩個多項式: A(x) = 2x1000 + 1 B(x) = x4 + 10x3 + 3x2 + 1 A.Start A.Finish B.Start B.Finish free coef 2 1 10 3 exp 1000 4 5 6

多項式相加 只存非零值(non-zero)：一元多項式 兩個多項式相加: A(x) = 2x1000 + 1 B(x) = x4 + 10x3 + 3x2 + 1 1 2 1 2 3 4 A_coef 2 2 1 B_coef 4 1 10 3 1 A_exp 1000 B_exp 4 3 2 1 2 3 4 5 C_coef 5 2 1000 1 4 10 3 3 2 2 C_exp

多項式相加 O(m+n) Polynomial Polynomial:: Add(Polynomial B) // return the sum of A(x) ( in *this) and B(x) { Polynomial C; int a = Start; int b = B.Start; C.Start = free; float c; while ((a <= Finish) && (b <= B.Finish)) switch (compare(termArray[a].exp, termArray[b].exp)) { case ‘=‘: c = termArray[a].coef +termArray[b].coef; if ( c ) NewTerm(c, termArray[a].exp); a++; b++; break; case ‘<‘: NewTerm(termArray[b].coef, termArray[b].exp); b++; case ‘>’: NewTerm(termArray[a].coef, termArray[a].exp); a++; } // end of switch and while // add in remaining terms of A(x) for (; a<= Finish; a++) // add in remaining terms of B(x) for (; b<= B.Finish; b++) C.Finish = free – 1; return C; } // end of Add O(m+n)

多項式中新增一項 void Polynomial::NewTerm(float c, int e) // Add a new term to C(x) { if (free >= MaxTerms) { cerr << “Too many terms in polynomials”<< endl; exit(); } termArray[free].coef = c; termArray[free].exp = e; free++; } // end of NewTerm

利用陣列表達多項式的缺點 若原本配置給陣列的空間隨著多項式的項目增加而不足時? 放棄 或者重新宣告陣列記憶體的大小(收集記憶體中剩餘的可用空間)，但此舉非常耗時 若一開始時配置過大陣列空間儲存多項式時可能會造成浪費記憶體

Sparse Matrices

稀疏矩陣表示法 使用三元組<row, column, value>來表示矩陣中的任何一個元素 依列的順序來儲存 在同一列中, 三元組依照行的順序來儲存 必須知道矩陣中列、行以及非零元素的個數

稀疏矩陣表示法(續) class SparseMatrix; // forward declaration class MatrixTerm { friend class SparseMatrix private: int row, col, value; }; In class SparseMatrix: int Rows, Cols, Terms; MatrixTerm smArray[MaxTerms];

矩陣轉置 最容易的方式: 較有效率的方式: for (each row i) take element (i, j, value) and store it in (j, i, value) of the transpose 較有效率的方式: for (all elements in column j) place element (i, j, value) in position (j, i, value)

矩陣轉置 The Operations on 2-dim Array Transpose for (i = 0; i < rows; i++ ) for (j = 0; j < columns; j++ ) B[j][i] = A[i][j];

矩陣轉置 O(terms*columns) SparseMatrix SparseMatrix::Transpose() // return the transpose of a (*this) { SparseMatrix b; b.Rows = Cols; // rows in b = columns in a b.Cols = Rows; // columns in b = rows in a b.Terms = Terms; // terms in b = terms in a if (Terms > 0) // nonzero matrix int CurrentB = 0; for (int c = 0; c < Cols; c++) // transpose by columns for (int i = 0; i < Terms; i++) // find elements in column c if (smArray[i].col == c) { b.smArray[CurrentB].row = c; b.smArray[CurrentB].col = smArray[i].row; b.smArray[CurrentB].value = smArray[i].value; CurrentB++; } } // end of if (Terms > 0) } // end of transpose O(terms*columns)

快速矩陣轉置 The O(terms*columns) time => O(rows*columns2) when terms is the order of rows*columns A better transpose function in Program 2.11. It first computes how many terms in each columns of matrix a before transposing to matrix b. Then it determines where is the starting point of each row for matrix b. Finally it moves each term from a to b.

快速矩陣轉置 SparseMatrix SparseMatrix::Transpose() // The transpose of a(*this) is placed in b and is found in Q(terms + columns) time. { int *Rows = new int[Cols]; int *RowStart = new int[Rows]; SparseMatrix b; b.Rows = Cols; b.Cols = Rows; b.Terms = Terms; if (Terms > 0) // nonzero matrix // compute RowSize[i] = number of terms in row i of b for (int i = 0; I < Cols; i++) RowSize[i] = 0; // Initialize for ( I = 0; I < Terms; I++) RowSize[smArray[i].col]++; // RowStart[i] = starting position of row i in b RowStart[0] = 0; for (i = 0; i < Cols; i++) RowStart[i] = RowStart[i-1] + RowSize[i-1]; O(columns) O(terms) O(columns-1)

for (i = 1; I < Terms; i++) // move from a to b 快速矩陣轉置 for (i = 1; I < Terms; i++) // move from a to b { int j = RowStart[smArray[i].col]; b.smArray[j].row = smArray[i].col; b.smArray[j].col = smArray[i].row; b.smArray[j].value = smArray[i].value; RowStart[smArray[i].col]++; } // end of for } // end of if delete [] RowSize; delete [] RowStart; return b; } // end of FastTranspose O(terms) O(row * column)

矩陣乘法 定義: 給定 A 與 B 兩個矩陣, 其中 A 的大小為 m x n 而 B 的大小為 n x p, 乘積矩陣result 的大小為m x p且它的 第[i][j] 元素為 0 ≤ i < m 且 0 ≤ j < p.

陣列表示法 多維陣列的實作方式通常是把所有的元素對應放入一個一維陣列裡。儲存方式可分成以列為優先或以行為優先. 範例: 一維陣列 A[0] α α+1 α+2 α+3 α+4 α+5 α+6 α+7 α+8 α+9 α+10 α+12 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] A[11]

二為陣列(列主序) X X X X X X X X X X X X i * u2 element u2 u2 elements Col 0 Col 1 Col 2 Col u2 - 1 Row 0 X X X X Row 1 X X X X Row u1 - 1 X X X X u2 elements u2 elements Row 0 Row 1 Row i Row u1 - 1 i * u2 element

記憶體對應 char A[3][4]; // row-major logical structure physical structure 1 2 3 A[0][0] A[0][1] 1 A[0][2] 2 A[0][3] A[1][0] A[2][1] A[1][1] A[1][2] A[1][3] Mapping: A[i][j]=A[0][0]+i*4+j

二維陣列中元素對應的位址 二維陣列宣告為A[r][c]，每個陣列元素佔len bytes，且其元第1個元素A[0][0]的記憶體位址為，並以列為主(row major)來儲存此陣列，則 A[0][3]位址為+3*len A[3][0]位址為+(3*r+0)*len ... A[m][n]位址為+(m* r + n)*len A[0][0]位址為，目標元素A[m][n]位址的算法 Loc(A[m][n]) = Loc(A[0][0]) + [(m0)*r+(n0)]*元素大小

String 通常利用字元陣列來表達一個字串. 字串的運算鐘一般包含字串比較、字串連接、複製、插入、尋找字串樣本等. H e l l o W d \0

字串樣本搜尋：Knuth-Morris-Pratt 演算法 定義: 假若 p = p0p1…pn-1 是一個字串樣本, 那麼它的失敗函數, f, 定義為 如果已經找到部分匹配的字串 si-j … si-1 = p0p1…pj-1 而且 si ≠ pj，那麼如果j ≠ 0則我們可以直接比對 si 與 pf(j–1)+1 以繼續我們的比對.

快速比對範例 假設字串 s 與 字串pat = ‘abcabcacab’, 今目的為搜尋 s 中是否存在 字串pat . j 0 1 2 3 4 5 6 7 8 9 pat a b c a b c a c a b f -1 -1 -1 0 1 2 3 -1 0 1 s = ‘- a b c a ? ? . . . ?’ pat = ‘a b c a b c a c a b’ ‘a b c a b c a c a b’ j = 4, pf(j-1)+1 = p1 New start matching point