- Array: a set of index and value
- ADT( abstract data type):
For each index, there is a value associated with that index. (Their relationship is the linear.)
- Representation (possible)
Implemented by using consecutive memory.
(item1, item2, item3, …, itemn)
Operations on Ordered List ( Linear List)
(1) Finding the length, n , of the list. (找list長度)
(2) Reading the items in a list from left to right (or right to left).
(從左讀到右)
(3) Retrieving the ith element from a list, 0 ≦i<n. (抓第i個)
(4) Replacing (Storing) the item in the ith position of a list,
0≦i<n. (存到第i個)
(5) Inserting a new item in the ith position of list, 0 ≦i ≦n. The items previously numbered i, i+1, …, n-1 to become items numbered i+1, i+2, …, n (插入新item到第i個)
(6) Deleting an item from the ith position of a list, 0 ≦i<n. The items numbered i+1, …, n-1 to become items numbered i, i+1, …, n-2. (刪除第i個item)
Polynomial(多項式)
Example:
A(X)=3X200+2X2+4, B(X)=X4+10X3+3X2+1
class polynomial
{
objects: a1xe1+…+anxen; a set of ordered pairs of <ei ,ai> where ai∈Coefficient and ei∈ Exponent We assume that Exponent consists of integers ≥ 0
public:
Polynomial();
// return the polynomial p(x) = 0
int operator!();
// if *this is the zero polynomial, return 1; else return 0;
Coefficient Coef(Exponent e);
// return the coefficient of e in *this
Exponent LeadExp();
// return the largest exponent in *this
Polynomial Add(Polynomial poly);
// return the sum of the polynomials *this and poly
Polynomial Mult(Polynomial poly);
// return the product of the polynomials *this and poly
float Eval(float f);
// Evaluate the polynomial *this at f and return the result
}; end of Polynomial
Polynomial Representation I
(浪費空間 ＝＞ 當多項式是sparse時)
#define MAX_Degree 201
Private:
int degree;
float coef[MAX_DEGREE+1];
B(X)=X4+10X3+3X2+1
Waste space when the degree of the polynomial is much smaller than Max_Degree
A(X)=3X200+2X2+4
Polynomial Representation II
#define MAX_TERMS 100 /* size of terms array */
Class polynomial;//forward declaration
Class term {
friend polynomial;
private: float coef;
int expon;
};
Class Polynomial { private: term terms[MAX_TERMS];
int avail = 0, int start, finish;
}
twice as much as 1 when all the items are nonzero
Sparse Matrix(稀疏矩陣)
A matrix is called sparse if it consists of many zero entries (矩陣內很多0 稱稀疏矩陣)
用二維陣列會浪費空間
Space complexity is O(m×n)
Sparse Matrix Representation
- Use triple <row, column, value>
- Store triples row by row (按照列一列一列儲存)
- For all triples within a row, their colum indices are in ascending order. (相同row,儲存順序依照column由小到大來存放)
- Must know the numbers of rows and columns and the number of nonzero elements (必須知道row, col,及非零項有那些)
Class term
{
friend
Class SparseMatrix;
private:
int col;
int row;
int value;
}
In class SparseMatrix
{
private:
int Rows, Cols, Terms;
term sA[MaxTerms];
}
創作內容
University - Array
讀書心得 (2)
