第5讲数组和广义表.ppt

第5章数组和
广义表数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。例如：推广到一般情况，可得到n维数组数据元素存储位置的映象关系特殊矩阵
非零元在矩阵中的分布有一定规则
例如:对称矩阵
三角矩阵
三对角矩阵矩阵的压缩存储
对称矩阵三角矩阵对角矩阵稀疏矩阵(SparseMatrix)稀疏矩阵是非零元素个数远远少于矩阵元素个数的矩阵以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)尽可能少存或不存零值元素；稀疏矩阵基本操作1．intGetRows()const初始条件：稀疏矩阵已存在。操作结果：返回稀疏矩阵行数。2．intGetCols()const初始条件：稀疏矩阵已存在。操作结果：返回稀疏矩阵列数。3．intGetNum()const初始条件：稀疏矩阵已存在。操作结果：返回稀疏矩阵非零元素个数。4．boolEmpty()const初始条件：稀疏矩阵已存在。操作结果：如稀疏矩阵为空，则返回true，否则返回false5．StatusCodeSetElem(intr,intc,constElemType&v)初始条件：稀疏矩阵已存在。操作结果：设置指定位置的元素值。6．StatusCodeGetElem(intr,intc,ElemType&v)初始条件：稀疏矩阵已存在。操作结果：求指定位置的元素值。随机稀疏矩阵的顺序压缩存储三元组表//三元组类模板
template<classElemType>
structTriple
{
//数据成员:
introw,col; //非零元素的行下标与列下标
ElemTypevalue; //非零元素的值

//构造函数模板:
Triple(); //无参数的构造函数模板
Triple(intr,intc,ElemTypev);
//已知数数据域建立三元组
};以顺序表存储三元组表，可得到稀疏矩阵的顺序存储结构——三元组顺序表
在三元组顺序表中，用三元组表表示稀疏矩阵时，为避免丢失信息，增设了一个信息元组，形式为：
（行数，列数，非零元素个数）已知稀疏矩阵//稀疏矩阵三元组顺序表类模板
template<classElemType>
classTriSparseMatrix
{
protected:
//稀疏矩阵三元组顺序表的数据成员:
Triple<ElemType>*triElems;
//存储稀疏矩阵的三元组表
intmaxSize; //非零元素最大个数
introws,cols,num;
//稀疏矩阵的行数,列数及非零元个数
public:
//抽象数据类型方法声明及重载编译系统默认方法声明:
TriSparseMatrix(intrs=DEFAULT_SIZE,intcs
=DEFAULT_SIZE,
intsize=DEFAULT_SIZE);
//构造一个rs行cs列非零元素最大个数为size
//的空稀疏矩阵
~TriSparseMatrix(); //析构函数
intGetRows()const; //返回稀疏矩阵行数
intGetCols()const; //返回稀疏矩阵列数
intGetNum()const; //返回稀疏矩阵非零元个数
StatusCodeSetElem(intr,intc,constElemType&v); //设置指定位置的元素值
StatusCodeGetElem(intr,intc,ElemType&v);
//求指定位置的元素值
TriSparseMatrix<ElemType>&operator=(const
TriSparseMatrix<ElemType>&copy);//赋值 ……
};稀疏矩阵的转置算法的基本思想：第一次从source中取出应该放置到dest中第一个位置的元素，行列号互换后，放于dest中第一个位置；第二次从source中选取应该放到dest中的第二个位置的元素，……，如此进行，依次生成dest中的各元素。

由于转置后列号变行号，所以转置后元素的行序排列实质上是原矩阵元素的列序排列。实现算法可形式化描述为：
destPos=0;//稀疏矩阵dest的下一个三元组的存放位置
for(col=最小列号;col<=最大列号;col++)
{
在source中从头查找有无列号为col的三元组；
若有，则将其行、列号交换后，依次存入dest
中destPos所指位置，同时destPos加1；
}template<classElemType>
voidTriSparseMatrix<ElemType>::SimpleTranspose(
constTriSparseMatrix<ElemType>&s