目的:
1、创建三对角矩阵类,采用按列映射方式,提供 store 和 retrieve 方法。
2、创建下三角矩阵类,采用按列映射方式,提供 store 和 retrieve 方法。
3、创建稀疏矩阵类,采用行主顺序把稀疏矩阵映射到一维数组中,实现稀疏矩阵的转置和两个稀疏矩阵的加法操作。
4、使用散列表设计实现一个字典,假设关键字为整数且 D 为 961,在字典 中插入随机产生的 500 个不同的整数,实现字典的建立和搜索操作。分别使 用线性开型寻址和链表散列解决溢出。
创建特殊矩阵类的重点就是分析矩阵中位置在一维数组中的映射方式,根据公式就可以计算出元素存放的位置。可以先假设n为一个比较小的定值,并画出数组中的位置在矩阵内元素上的编号,通过带入求解公式。
在这次的目的中,我们都采用按列映射方式,输入位置不对就抛出MustBeZero异常。
三对角矩阵:使用列主映射保存元素在大小为3*n-2的数组中,如果行列之差的绝对值大于1就抛出异常,如果能存储就存在数组中2*column+row-3的位置上。
下三角矩阵:使用列主映射保存元素在大小为n*(n-1)/2的数组中,如果列数比行数小就抛出异常,如果能存储就存储在数组中column*(2*n-column + 1)/2-(n-row)-1的位置上。
稀疏矩阵是矩阵中多数元素为0的矩阵,在这里我们采用自定义类型存储它的一个元素。
template<class T>
class Term
{
friend SparseMatrix<T>;
private:
int row, column;
T value;
};
存储时使用行主映射,保存元素的行、列、值,行数小的在前面,行数相同列数小的在前面。
转置时,设置两个数组,一个(ColSize)用来记录每一列的元素数量,另一个(RowNext)记录通过元素数量计算出的每一行的开始位置,再把矩阵中的所有元素按照相应的列顺序放到新矩阵的行位置上,并把元素的行和列交换保存,每放一个元素相应行开始位置(RowNext)就加一,直到把所有元素全部放入新矩阵。
template<class T>
最后
以上就是风趣小懒虫最近收集整理的关于矩阵和散列表的全部内容,更多相关矩阵和散列表内容请搜索靠谱客的其他文章。
发表评论 取消回复