7.1 數(shù)組
7.1.1 抽象數(shù)據(jù)類型
抽象數(shù)據(jù)類型 Array
{
實(shí)例
形如（index，value）的數(shù)對(duì)集合，其中任意兩個(gè)數(shù)對(duì)的index值都各不相同. 操作
get（index）：返回索引為index的數(shù)對(duì)中的值
set（index，value）：加入一個(gè)新數(shù)對(duì)（index，value）
（如果索引index值相同的數(shù)對(duì)已存在，則用新數(shù)對(duì)覆蓋）
}
7.1.2 C++數(shù)組的索引
- K維數(shù)組的索引（或下標(biāo)）
- [ i 1 ] [ i 2 ] [ i 3 ] . . . [ i k ] [i_1][i_2][i_3]...[i_k] [i1?][i2?][i3?]...[ik?]
- k維數(shù)組創(chuàng)建：
- int score [ u 1 ] [ u 2 ] [ u 3 ] . . . [ u k ] [u_1][u_2][u_3]...[u_k] [u1?][u2?][u3?]...[uk?]（ u i u_i ui?—正的常量或有常量表示的表達(dá)式）
- 數(shù)組元素的個(gè)數(shù)：
- n = u 1 u 2 u 3 . . . u k n=u_1u_2u_3...u_k n=u1?u2?u3?...uk?
- 內(nèi)存空間：
- n x sizeof（int）字節(jié).
- c++ 編譯器為數(shù)組預(yù)留空間：
- start -----start + sizeof(score)-1
7.1.3 行主映射和列主映射
行主映射（按行的順序?qū)υ匾灰挥成洌┖土兄饔成洌ò戳械捻樞驅(qū)υ匾灰挥成洌?br>
以二維數(shù)組舉例
int s[ u 1 u_1 u1?] [ u 2 u_2 u2?] (令s[2] [3])
| 行主映射下： | 列主映射下： |
|---|---|
| map（ i 1 i_1 i1?, i 2 i_2 i2?) = u 2 u_2 u2? * i 1 i_1 i1? + i 2 i_2 i2? | map（ i 1 i_1 i1?, i 2 i_2 i2?) = u 1 u_1 u1? * i 2 i_2 i2? + i 1 i_1 i1? |
| s[0] [0] | s[0] [0] |
| s[0] [1] | s[1] [0] |
| s[0] [2] | s[0] [1] |
| s[1] [0] | s[1] [1] |
| s[1] [1] | s[0] [2] |
| s[1] [2] | s[1] [2] |
思考：
-
在C++使用的是行主映射
-
M 行 M_行 M行?= M 列 T M_列^T M列T?
-
k維數(shù)組行主映射：
m a p ( i 1 , i 2 , . . . , i k ) = ( i 1 ? u 2 ? u 3 . . . u k ) + ( i 2 ? u 3 . . . u k ) + . . . + ( i k ? 1 ? u k ) + ( i k ) map(i_1, i_2, ..., i_k) = (i_1*u_2*u_3 ... u_k)+(i_2*u_3 ... u_k)+...+(i_{k-1}*u_k)+(i_k) map(i1?,i2?,...,ik?)=(i1??u2??u3?...uk?)+(i2??u3?...uk?)+...+(ik?1??uk?)+(ik?)
-
k維數(shù)組列主映射：
m a p ( j 1 , j 2 , . . . j k ) = ( j 1 ? u 2 ? u 3 . . . u k ) + ( j 2 ? u 3 . . . u k ) + . . . + ( j k ? 1 ? u k ) + ( j k ) map(j_1,j_2,...j_k)= (j_1*u_2*u_3 ... u_k)+(j_2*u_3 ... u_k)+...+(j_{k-1}*u_k)+(j_k) map(j1?,j2?,...jk?)=(j1??u2??u3?...uk?)+(j2??u3?...uk?)+...+(jk?1??uk?)+(jk?)
注意，超過(guò)兩維就沒(méi)有列的概念了，因此高維的行、列主映射公式通用。
7.1.4 用數(shù)組的數(shù)組來(lái)描述
多維數(shù)組可以用數(shù)組的數(shù)組描述
-
占用空間：4×3×1 + 4×5×3
-
C++定位x[i] [j]的過(guò)程：
-
利用一維數(shù)組的映射函數(shù)找到指針x[i]
-
利用一維數(shù)組的映射函數(shù)找到指針x[i]所指的第i行中索引為j的元素
-
7.1.5 行主描述和列主描述
| 數(shù)組y | 以下就是int s[3] [5]的行主描述 | 以下就是int s[3] [5]的列主描述 |
|---|---|---|
| y[0] | s[0] [0] | s[0] [0] |
| y[1] | s[0] [1] | s[1] [0] |
| y[2] | s[0] [2] | s[2] [0] |
| y[3] | s[0] [3] | s[0] [1] |
| y[4] | s[0] [4] | s[1] [1] |
| y[5] | s[1] [0] | s[2] [1] |
| y[6] | s[1] [1] | s[0] [2] |
| y[7] | s[1] [2] | s[1] [2] |
| y[8] | s[1] [3] | s[2] [2] |
| y[9] | s[1] [4] | s[0] [3] |
| y[10] | s[2] [0] | s[1] [3] |
| y[11] | s[2] [1] | s[2] [3] |
| y[12] | s[2] [2] | s[0] [4] |
| y[13] | s[2] [3] | s[1] [4] |
| y[14] | s[2] [4] | s[2] [4] |
- 占用空間：3×5×4
- 定位x[i] [j]的過(guò)程（以行主列為例）：
- 利用二維數(shù)組的映射函數(shù)（map（ i 1 i_1 i1?, i 2 i_2 i2?) = u 2 u_2 u2? * i 1 i_1 i1? + i 2 i_2 i2?）計(jì)算x[i] [j]在一維數(shù)組y中的位置u
- 利用一維數(shù)組的映射函數(shù)（map（ i 1 i_1 i1?）= i 1 i_1 i1?）訪問(wèn)元素y[u]
7.2 矩陣
7.2.1 定義和操作
m×n矩陣：m行和n列的表
M(i,j)：矩陣M中第i行、第j列的元素
矩陣相乘直觀表示(* ^ ▽ ^ *）
7.2.2 類matrix
數(shù)據(jù)描述：用于一個(gè)一維數(shù)組element，按行主次序存儲(chǔ)
M：m×n matrix
- 矩陣元素M(i,j)在數(shù)組element中的位置
- map(i,j) = (i-1)*n+j-1
matrix類聲明
我們要重載函數(shù)操作符（），使得在程序中對(duì)矩陣索引的用法和在數(shù)學(xué)中的一樣。我們還要重載算術(shù)操作符，使它們能夠用于矩陣對(duì)象。
template<class T>
class matrix
{
friend ostream& operator<<(ostream&,const matrix<T>&);
public:
matrix(int theRows=0,int theColumns=0);
matrix（const matrix<T>&）；//復(fù)制構(gòu)造函數(shù)
~matrix(){delete[]element;}
int rows()const {return theRows;}
int columns()const {return theColumns;}
T& operator()(int i, int j) const;
matrix<T>& operator=(const matrix<T>&);
matrix<T> operator+()const；//一元加法
matrix<T> operator+(const matrix<T>&)const;
matrix<T> operator-()const；//一元減法
matrix<T> operator-(const matrix<T>&)const;
matrix<T> operator*(constmatrix<T>&)const;
matrix<T>&operator+=(const T&x);
private:
int theRows，theColumns；//矩陣行數(shù)和列數(shù)
T*element；//元素?cái)?shù)組
};
matrix類的構(gòu)造函數(shù)
template<class T>
matrix<T>::matrix(int theRows,int theColumns)
{
//檢驗(yàn)行數(shù)和列數(shù)的有效性
if(theRows <0 || theColumns <0)
throw illegalParameterValue("行列數(shù)必須大于等于0");
if(theRows ==0 || theColumns == 0 && (theRows !=0|| theColumns !=0))
throw illegalParameterValue("要么都大于0，要么都等于0");
//創(chuàng)建矩陣
this-> theRows = theRows;
this-> theColumns = theColumns;
element=new T [theRows* theColumns];
}
matrix類的復(fù)制構(gòu)造函數(shù)
template<class T>
matrix<T>::matrix(const matrix<T>& m)
{
//創(chuàng)建矩陣
theRows = m.rows;
theColumns = m.theColumns;
element= new T [theRows* theColumns];
//復(fù)制m的每一個(gè)元素
copy (m.element,m.element ＋ theRows* theColumns, element);
}
matrix類對(duì)()的重載
矩陣元素M(i,j)在數(shù)組element中的位置
map(i,j) = (i-1)*n+j-1
template<class T>
T& matrix<T>::operator()(int i,int j)const
{
//返回一個(gè)指向元素（i，j）的引用
if(i<1||i>theRows||j<1|j>theColumns)
throw matrixIndexOutOfBounds();
return element[(i-1)*theColumns +j-1];
}
matrix類對(duì)=的重載
template<class T>
matrix<T>& matrix<T>::operator=(const matrix<T>& m)
{
//賦值，*this=m
if(this != &m)
{//不能自己賦值自己
//釋放原空間
delete [] element；
theRows = m.theRows;
theColumns = m.theColumns;
element = new T [theRows* theColumns];
//復(fù)制m的每一個(gè)元素
copy (m.element,m.element + theRows* theColumns, element);
}
return *this;
}
matrix類對(duì)+的重載
template<class T>
matrix<T>matrix<T>::operator + (const matrix<T>& m)const
{
//返回矩陣w=（*this）＋m
if(theRows != m.theRows || theColumns != m.theColumns)
throw matrixSizeMismatch();
//生成結(jié)果矩陣w
matrix<T> w(theRows, theColumns);
for(int i = 0;i < theRows * theColumns;i++)
w.element[i] = element[i] + m.element[i];
return w;
}
matrix類對(duì)*的重載
template<class T>
matrix<T>matrix<T>::operator * (const matrix<T>& m)const
{
//返回矩陣w=（*this）*m
if(theColumns != m.theRows)
throw matrixSizeMismatch();
//生成結(jié)果矩陣w
matrix<T> w(theRows, m.theColumns);
//為*this，m和w定義游標(biāo)，并設(shè)定初始位置為（1,1）
int ct = 0,cm = 0,cw = 0;
/*最外層的循環(huán)對(duì)應(yīng)不同行和不同列的計(jì)算，一行的所有列都好了就換一行*/
for (int i = 1;i <= theRows;i++)
{
/*第二層的循環(huán)對(duì)應(yīng)一行和不同列的計(jì)算，一列完了換一列*/
for (int j = 1;j <= m.theColumns; j++)
{
T sum = element[ct] * m.element[cm];
/*最內(nèi)層的循環(huán)實(shí)現(xiàn)一行對(duì)應(yīng)一列的計(jì)算*/
for(int k=2；k<=theColumns；k++)
{
//累加其余項(xiàng)
ct++；//指向*this第i行的下一項(xiàng)
/*在行主次序中同一列的兩個(gè)相同元素在位置上相差m.theColumns*/
cm += m.theColumns；//指向m的第j列的下一項(xiàng)
sum += element[ct] * m.element[cm];
}
w.element[cw++] = sum;//保存w（i，j）
ct -= theColumns-1;//第i行行首
cm = j;//第j+1列起始
}
ct += theColumns;//重新調(diào)整至下一行的行首
cm = 0;//重新調(diào)整至第一列起始
}
return w;
}
7.3 特殊矩陣
7.3.1 定義和應(yīng)用
方陣是指具有相同行數(shù)和列數(shù)的矩陣
特殊矩陣
7.3.2 對(duì)角矩陣
對(duì)角矩陣：D
矩陣描述：T element[n]
類diagonalmatrix聲明
template<class T>
class diagonalMatrix
{
public:
diagonalMatrix(int theN=10);//構(gòu)造函數(shù)
~diagonalMatrix(){delete []element;} //析構(gòu)函數(shù)
T get(int,int)const;
void set(int,int,const T&);
private:
int n;//矩陣維數(shù)
T*element; //存儲(chǔ)對(duì)角元素的一維數(shù)組
};
diagonalMatrix::get
template <class T>
T diagonalMatrix<T>::get(int i,int j)const
{
//返回矩陣中（i，j）位置上的元素.
//檢驗(yàn)i和j是否有效
if (i<1 || j<1 || i>n || j>n) throw matrixIndexOutOfBounds();
if(i==j)
return element[i-1];//對(duì)角線上的元素
else return 0;//非對(duì)角線上的元素
}
diagonalMatrix:: set
template<class T>
void diagonalMatrix<T>:: set(int i, int j, const T& newValue)
{
//存儲(chǔ)矩陣中位置（i，j）上元素的新值.
//檢驗(yàn)i和j是否有效
if(i<1 || j<1 || i>n || j>n) throw matrixIndexOutOfBounds();
if(i==j)
element[i-1] = newValue；//存儲(chǔ)對(duì)角元素的值
else
if(newValue!= 0)
throw illegalParameterValue("非對(duì)角線上的元素必須是0");
}
7.3.3 三對(duì)角矩陣
三對(duì)角矩陣：T
三條對(duì)角線：
主對(duì)角線：i = j
低對(duì)角線（主對(duì)角線之下的對(duì)角線）：i = j + 1
高對(duì)角線（主對(duì)角線之上的對(duì)角線）：i = j - 1
補(bǔ)充：按對(duì)角線映射
tridiagonalMatrix::get
template <class T>
T tridiagonalMatrix<T>::get(int i,int j)const
{
//返回矩陣中（i，j）位置上的元素.
//檢驗(yàn)i和j是否有效
if(i <1 || j<1 || i>n || j>n) throw matrixIndexOutOfBounds();
//確定要返回的元素
switch (i-j)
{
case 1://低對(duì)角線
return elelment[i-2];
case 0://主對(duì)角線
return elelment[n+i-2];
case -1://高對(duì)角線
return elelment[2*n+i-2];
default: return 0;
}
}
7.3.4 三角矩陣
非0區(qū)域的元素總數(shù)：n(n+1)/2
7.3.5 對(duì)稱矩陣
一個(gè)n×n對(duì)稱矩陣，可以視為下三角或上三角矩陣，用三角矩陣的表示方法，用一個(gè)大小為n(n+1)/2的一維數(shù)組來(lái)表示。未存儲(chǔ)的元素可以由存儲(chǔ)的元素來(lái)計(jì)算。
7.4 稀疏矩陣
7.4.1 基本概念
-
如果一個(gè)m×n矩陣中有“許多”元素為0，則稱該矩陣為稀疏矩陣（sparse）。
-
不是稀疏的矩陣被稱為稠密矩陣（dense）。
-
稀疏矩陣和稠密矩陣之間沒(méi)有一個(gè)精確的界限：
- 我們規(guī)定若一個(gè)矩陣是稀疏矩陣，則其非0元素的數(shù)目應(yīng)小于 n 2 / 3 n^2/3 n2/3，在有些情況下應(yīng)小于 n 2 / 5 n^2/5 n2/5
- 對(duì)角矩陣，三對(duì)角矩陣（n×n）：稀疏矩陣
- 三角矩陣：稠密矩陣
7.4.2 用單個(gè)線性表描述
線性表terms采用數(shù)組描述（terms是arrayList的實(shí)例）
類sparseMatrix聲明
template <class T>
struct matrixTerm
{
int row;
int col;
T value;
operator T() const { return value;}
};
template<class T>
class sparseMatrix
{
public:
void transpose(SparseMatrix<T> &b);//矩陣轉(zhuǎn)置
void add(sparseMatrix<T> &b, sparseMatrix<T> &c);//兩個(gè)稀疏矩陣相加
private:
int rows;//矩陣行數(shù)
int cols;//矩陣列數(shù)
arrayList<matrixTerm<T>>terms;//矩陣非0元素表
};
類sparseMatrix中的矩陣轉(zhuǎn)置
關(guān)鍵點(diǎn)
矩陣*this的轉(zhuǎn)置矩陣→b
矩陣*this中的元素在b中的位置？
- colSize[i]：*this第i列的非0元素?cái)?shù)
- rowNext[i]：*this第i列（b中第i行）下一個(gè)元素在b中的位置
- 初始：b中第i行的起始位置
rowNext[1] = 0;rowNext[i] = rowNext[i - 1]+colSize[i - 1];算法思路
計(jì)算*this每列中的非0元素?cái)?shù)
求出b中每一行的起始點(diǎn)
實(shí)施從*this到b的轉(zhuǎn)置復(fù)制
定義i為* this迭代器
依次掃描* this各元素（ *i）
template<class T>
void sparseMatrix<T>::transpose(sparseMatrix<T>&b)
{//把*this轉(zhuǎn)置結(jié)果送入b
//設(shè)置轉(zhuǎn)置矩陣特征
b.cols = rows;
b.rows = cols;
b.terms.reSet(terms.size());
//初始化以實(shí)現(xiàn)轉(zhuǎn)置
int* colSize = new int[cols + 1];
int* rowNext = new int[cols + 1];
//計(jì)算*this每一列的非0元素?cái)?shù)
for (int i = 1; i <= cols; i++)
colSize[i] = 0;
for (arrayList<matrixTerm<T>>::iterator i = terms.begin();
i!=terms.end();i++)
colSize[(*i).col]++;
//求出b中每一行的起始點(diǎn)
rowNext[1] = 0;
for (int i = 2; i <= Cols; i++)
rowNext[i] = rowNext[i - 1] + colSize[i - 1];
//實(shí)施從*this到b的轉(zhuǎn)置復(fù)制
matrixTerm<T> mTerm;
for(arrayList<matrixTerm<T>>::iterator i = terms.begin();
i!= terms.end();i++)
{
int j = rowNext[(*i).col]++;//在b中的位置
mTerm.row = (*i).col;
mTerm.col = (*i).row;
mTerm.value = (*i).value;
b.terms.set(j,mTerm);
}
}
類sparseMatrix中的兩個(gè)稀疏矩陣相加
兩個(gè)稀疏矩陣（*this和b）相加，所得結(jié)果放入c中。
實(shí)現(xiàn)思想：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-793898.html
- 定義矩陣*this的迭代器：it，和矩陣b的的迭代器ib
- 使用it和ib，從左至右依次掃描兩個(gè)矩陣中的元素。
- 當(dāng)it和ib都未掃描完成時(shí)，循環(huán)：
- 計(jì)算it所指的元素和ib所指的元素按行主次序的索引。
- tIndex=*this中的it所指的元素索引
- 元素索引——（元素的行下標(biāo)-1）* 列數(shù)+元素的列下標(biāo)
- bIndex =b中ib所指的元素索引
- 判斷tIndex>bIndex 還是tIndex=bIndex，確定it所指的元素是在ib所指的元素之前，之后還是進(jìn)行相加運(yùn)算,并只在和不為0時(shí)才加入c。
- 復(fù)制剩余元素
template<class T>
void sparseMatrix<T>::Add(sparseMatrix<T>&b,sparseMatrix<T>&c)
{//計(jì)算c=（*this）+b.
//檢驗(yàn)相容性
if (rows != b.rows || cols != b.cols)
throw matrixSizeMismatch();//不能相加
//設(shè)置結(jié)果矩陣c的特征
c.rows = rows;
c.cols = cols;
c.terms.clear() = 0;//初值
int cSize = 0;
//定義*this和b的迭代器
arrayList<matrixTerm<T>>::iterator it = terms.begin();
arrayList<matrixTerm<T>>::iterator ib = b.terms.begin();
arrayList<matrixTerm<T>>::iterator itEnd = terms.end();
arrayList<matrixTerm<T>>::iterator ibEnd = b.terms.end();
//遍歷*this和b，把相關(guān)的元素值相加
while(it!=itEnd && ib!= ibEnd)
{
//每一個(gè)元素的行主索引+列數(shù)
int tIndex = (*it).row * cols + (*it).col;
int bIndex = (*ib).row * cols + (*ib).col;
if(tIndex < bIndex)//b的元素在后
{
//*this的下一個(gè)元素
c.terms.insert(cSize++,*it);
it++;
}
else
{
if (tIndex == bIndex)//位置相同
{
//僅當(dāng)和不為0時(shí)才添加到c中
if((*it).value + (*ib).value != 0)
{
matrixTerm<T>mTerm;
mTerm.row = (*it).row;
mTerm.col = (*it).col;
mTerm.value =(*it).value +(*ib).value;
c.terms.insert(cSize++,mTerm);
}
//*this和b的下一個(gè)元素
it++;
ib++;
}
else
{//b的下一個(gè)元素
c.terms.insert(cSize++,*ib);
ib++;
}
}
}
//復(fù)制剩余元素
for(;it != itEnd; it++)
c.terms.insert(cSize++,*it);
for(;ib != ibEnd; ib++)
c.terms.insert(cSize++,*ib);
}
7.4.3 用多個(gè)線性表描述
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-793898.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) | 第七章：數(shù)組和矩陣 | 行主映射和列主映射 | 稀疏矩陣的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
