山大数据结构_4.pptx

Arrays

Matrices

SpecialMatrices

SparseMatrices;矩阵ADT

特殊矩阵

稀疏矩阵;数组的抽象数据类型描述抽象数据类型Array{

实例

形如(index,value)的数据对集合，其中任意两对数据的index值都各不相同

操作

Create()：创建一个空的数组Store(index,value)：添加数据(index,value)，同时删除具有相同index值的数据对（如果存在）

Retrieve(index)：返回索引值为index的数据对; 在C++中，值为整数类型的k维数组score可用如下语句来创建：

intscore[u1][u2][u3]...[uk]

为实现与数组相关的函数Store和Retrieve必须把数组索引[i1][i2][i3]...[ik]映射到

[0,n-1]中的某个数map(i1,i2,i3,...,ik)，使得该索引所对应的元素值存储在以下位置：start+map(i1,i2,i3,...,ik)*sizeof(int);·当数组维数为1时（即k=1），使用以下函数：map(i1)=i1;行主映射和列主映射

Row-andColumn-MajorMappings;行主次序所对应的映射函数为：map(i1,i2)=i1u2+i2

其中u2是数组的列数。

在行主映射模式中，在对索引[i1][i2]进行编号时,第0，...i1-1行中的i1u2个元素以及第i1行中的前i2个元素都已经被编号。;·三维数组的行主映射函数为：map(i1,i2,i3)=i1u2u3+i2u3+i3;templateclassTclassArray1D{public:

Array1D(intsize=0);

Array1D(constArray1DTv);//复制构造函数

~Array1D(){delete[]element;}Toperator[](inti)const;intSize(){returnsize;}

Array1DToperator=(constArray1DTv);Array1DToperator+()const;//一元加法操作符Array1DToperator+(constArray1DTv)const;Array1DToperator-()const;//一元减法操作符Array1DToperator-(constArray1DTv)const;Array1DToperator*(constArray1DTv)const;Array1DToperator+=(constTx);;private:intsize;

T*element;//一维数组

};;templateclassTclassArray2D{public:

Array2D(intr=0,intc=0);

Array2D(constArray2DTm);//复制构造函数

~Array2D(){delete[]row;}

intRows()const{returnrows;}intColumns()const{returncols;}

Array1DToperator[](inti)const;Array2DToperator=(constArray2DTm);Array2DToperator+()const;//一元加法操作符

Array2DToperator+(constArray2DTm)const;Array2DToperator-()const;//一元减法操作符Array2DToperator-(constArray2DTm)const;Array2DToperator*(constArray2DTm)const;Array2DToperator+=(constTx);;private:

introws,cols;//数组维数Array1DT*row;//一维数组的数组

};;一个m×n的矩阵是一个m行、n列的表，其中m和n是矩阵的维数。

矩阵通常被用来组织数据。;矩阵; 对于矩阵来说，最常见的操作就是矩阵转置、矩阵加、矩阵乘。

一个m×n矩阵的转置矩阵是一个n×m的矩阵MT，它与M之间存在以下关系：

MT(i,j)=M(j,i),1≤i≤n，1≤j≤m

仅当两个矩阵的维数相同时（即具有相同的行数和列数），才可以对两个矩阵求和。两个m×n矩阵A和B相加所得