数据结构、算法与应用-C++描述4.ppt

* * //执行转置操作 for (int i = 0; i terms; i++) { int j = RowNext[a[i].col]++; //在b中的位置 b.a[j].row = a[i].col; b.a[j].col = a[i].row; b.a[j].value = a[i].value; } } 复杂性？ 转置一个稀疏矩阵 * * templateclass T void SparseMatrixT::Append(const TermT t) {//把一个非0元素t添加到*this之中 if (terms = MaxTerms) throw NoMem(); a[terms] = t; terms++ ; } 添加一个非0元素 * * templateclass T void SparseMatrixT::Add(const SparseMatrixT b, SparseMatrixT c) const {//计算c = (*this)+b. //验证可行性 if (rows != b.rows || cols != b.cols) throw SizeMismatch(); //不能相加 //设置结果矩阵c的特征 c.rows = rows; c.cols = cols; c.terms = 0; //初值 //定义*this 和b的游标 int ct = 0, cb = 0; 两个稀疏矩阵相加 * * //在*this 和b 中遍历 while (ct terms cb b.terms) { //每一个元素的行主索引 int indt = a[ct].row*cols+a[ct].col; int indb = b.a[cb].row*cols+b.a[cb].col; if (indt indb) {//b 的元素在后 c.Append(a[ct]) ; ct++;} //*this的下一个元素 两个稀疏矩阵相加 * * else {if (indt == indb) {//位置相同 //仅当和不为0时才添加到c中 if (a[ct].value+b.a[cb].value) { TermT t; t.row = a[ct].row; t.col = a[ct].col; t.value = a[ct].value+b.a[cb].value; c.Append(t) ; } ct++; cb++;} //*this 和b的下一个元素 else {c.Append(b.a[cb]); cb++;} //b的下一个元素 } } 两个稀疏矩阵相加 * * //复制剩余元素 for (; ct terms; ct++) c.Append(a[ct]) ; for (; cb b.terms; cb++) c Append(b.a[cb]) ; } 复杂性？ 两个稀疏矩阵相加 * * 链表描述的一种可行方案是把每行的非0元素串接在一起，构成一个链表。 稀疏矩阵链接描述 * * 稀疏矩阵链接描述 * * templateclass T class CNode { public: int operator !=(const CNodeT y) {return (value != y.value) ; } void Output(ostream out) const {out column col value value;} private: int col; T value; } ; 链表节点 * * templateclass T class HeadNode { public: int operator !=(const HeadNodeT y) {return (row != y. r o w ) ; } void Output(ostream out) const {out row row;} private: int row; ChainCNodeT a; //行链表 } ; 行链表 * * templateclass T class LinkedMatrix { friend ostream operator(ostream, const LinkedMatrixT); friend istream operator(istream, LinkedMatrixT); public: LinkedMatrix( ) { } ~ LinkedMatrix( ) { } void Transpose(Linke