数据结构课件1-11全书讲第5讲数组和广义表幻灯片.ppt

* （1，3，3） （1，8，1） （3，1，9） （4，5，7） （5，7，6） （6，4，2） （6，6，3） （7，3，5） // 三元组类 templateclass ElemType struct Triple { // 数据成员: int row, col; // 非零元素的行下标与列下标 ElemType value; // 非零元素的值 // 构造函数: Triple(); // 无参数的构造函数 Triple(int r, int c, ElemType v); // 已知数数据域建立三元组 }; 以顺序表存储三元组表，可得到稀疏矩阵的顺序存储结构——三元组顺序表 在三元组顺序表中，用三元组表表示稀疏矩阵时，为避免丢失信息，增设了一个信息元组，形式为： （行数，列数，非零元素个数） （7，8，8） （1，3，3） （1，8，1） （3，1，9） （4，5，7） （5，7，6） （6，4，2） （6，6，3） （7，3，5） // 稀疏矩阵三元组顺序表类 templateclass ElemType class TriSparseMatrix { protected: // 稀疏矩阵三元组顺序表的数据成员: TripleElemType *triElems; // 存储稀疏矩阵的三元组表 int maxSize; // 非零元素最大个数 int rows, cols, num; // 稀疏矩阵的行数,列数及非零元个数 public: // 抽象数据类型方法声明及重载编译系统默认方法声明: TriSparseMatrix(int rs = DEFAULT_SIZE, int cs = DEFAULT_SIZE, int size = DEFAULT_SIZE); // 构造一个rs行cs列非零元素最大个数为size // 的空稀疏矩阵 ~TriSparseMatrix(); // 析构函数 int GetRows() const; // 返回稀疏矩阵行数 int GetCols() const; // 返回稀疏矩阵列数 int GetNum() const; // 返回稀疏矩阵非零元个数 StatusCode SetElem(int r, int c, const ElemType v); // 设置指定位置的元素值 StatusCode GetElem(int r, int c, ElemType v); // 求指定位置的元素值 TriSparseMatrixElemType operator =(const TriSparseMatrixElemType copy);// 赋值 …… }; 稀疏矩阵的转置 算法的基本思想：第一次从source中取出应该放置到dest中第一个位置的元素，行列号互换后，放于dest中第一个位置；第二次从source中选取应该放到dest中的第二个位置的元素，……，如此进行，依次生成dest中的各元素。 由于转置后列号变行号，所以转置后元素的行序排列实质上是原矩阵元素的列序排列。实现算法可形式化描述为： destPos = 0; // 稀疏矩阵dest的下一个三元组的存放位置 for(col = 最小列号; col =最大列号; col++) { 在source中从头查找有无列号为col的三元组； 若有，则将其行、列号交换后，依次存入dest 中destPos所指位置，同时destPos加1； } templateclass ElemType void TriSparseMatrixElemType::SimpleTranspose( const TriSparseMatrixElemType source, TriSparseMatrixElemType dest) // 操作结果：将稀疏矩阵source转置成稀疏矩阵dest的简 // 单算法 { dest.rows = source.cols; // 行数 dest.cols = source.rows; // 列数 dest.num = source.num; // 非零元素个数 dest.maxSize = source.maxSize; // 最大非零元素个数 delete []dest.triElems; // 释放存储空间 dest.triElems = new TripleElemType [dest.maxSize]; // 分配存储空间 if (dest.