linkedmatrix.h

一种基于二维链表的稀疏矩阵模半板类设计 A template Class of sparse matrix. Key technology: bin,2-m linked matrix. con

#include <iostream.h>
#include "dzqList.h"







#ifndef _DZQLINKED_MAXTRIX
#define _DZQLINKED_MAXTRIX


//CNode.....................................
template<class T>
class CNode 
{
	public:
		int operator !=(const CNode<T>& y)
		{
			return (value != y.value );
		}
		void Output(ostream& out) const
		{
			out << "column " << col << " value " << value;
		}
		ostream& operator<<(ostream& out, const CNode<T>& x);

	private:
		int col;
		T value;
};



template<class T>
ostream& CNode<T>::operator<<(ostream& out, const CNode<T>& x)
{
	x.Output(out);
	out << endl; return out;
}
//CNode over............................................................



//HeadNode ...................................................................
template<class T>
class HeadNode
{
public:
	int operator !=(const HeadNode<T>& y)
	{
		return (row != y.row );
	}

	void Output(ostream& out) const
	{
		out << "row " << row;
	}
	ostream& operator<<(ostream& out, const HeadNode<T>& x);

private:
	int row;
	Chain<CNode<T> > a; //行链表
};



template<class T>
ostream& HeadNode<T>:: operator<<(ostream& out, const HeadNode<T>& x)
{
	x.Output(out);
	out << endl; 
	return out;
}
//HeadNode over...................................................................







//Interface of LinkedMatrix.........................................
template<class T>
class LinkedMatrix
{
	friend ostream& operator<<(ostream&, const LinkedMatrix<T>&);
	friend istream& operator>>(istream&, LinkedMatrix<T>&);

public:
	LinkedMatrix( ) { }
	~ LinkedMatrix( ) { }
	void Transpose(LinkedMatrix<T> &b) const;
	void Add(Const LinkedMatrix<T> &b, LinkedMatrix<T> &c) const;
	
private:
	int rows, cols; // 矩阵维数
	Chain<HeadNode<T> > a; // 头节点链表
};
#endif;
//Interface of LinkedMatrix over.








//*******************************************************************
//***********************Implementations******************************
//********************************************************************


//______________________________________________________________________________
//*********************input matrix by istream,in fact this fun is not a member.
template<class T>
istream& operator>>(istream& in, LinkedMatrix<T>& x)
{
	// 从输入流中输入矩阵x
	x.a.Erase(); // 删除x中的所有节点
	// 获取矩阵特征
	int terms; // 输入的元素数
	cout << "Enter number of rows, columns, and terms" << endl;
	in >> x.rows >> x.cols >> terms;
	// 虚设第0行
	HeadNode<T> H; // 当前行的头节点
	H.row = 0; // 当前行号
	// 输入x的非0元素
	for (int i = 1; i <= terms; i++) 
	{
		// 输入下一个元素
		cout << "Enter row, column, and value of term " << i << endl;
		int row, col;
		T value;
		in >> row >> col >> value;
		// 检查新元素是否属于当前行
		if (row > H.row) 
		{
			// 开始一个新行
			// 如果不是第0行，则把当前行的头节点H添加到头节点链表x . a之中
			if (H.row) x.a.Append(H);
			//为新的一行准备H
			H.row = row;
			H.a.Zero();
		}   // 置链表头指针f i r s t = 0
		    // 添加新元素
		CNode<T> *c = new CNode<T>;
		c->col = col;
		c->value = value;
		H.a.Append(*c);
	}
	// 注意矩阵的最后一行
	if (H.row)
		x.a.Append(H);
	H.a.Zero(); // 置链表头指针为0
	return in;
}

//______________________________________________________________________________
//*********************fun over****************************************








//______________________________________________________________________________
//*********************output matrix by ostream,in fact this fun is not a member.
template<class T>
ostream& operator<<(ostream& out, const LinkedMatrix<T>& x)
{
	// 把矩阵x 送至输出流
	ChainIterator<HeadNode<T> > p;// 头节点遍历器
	// 输出矩阵的维数
	out << "rows = " << x.rows << " columns = " << x.cols << endl;
	// 将h 指向第一个头节点
	HeadNode<T> *h = p.Initialize(x.a);
	if (!h) 
	{
		out << "No non-zero terms" << endl;
		return out;
	}
	// 每次输出一行
	while (h)
	{
		out << "row " << h->row << endl;
		out << h->a << endl; //输出行链表
		h = p.Next(); // 下一个头节点
	}
	return out;
}

//______________________________________________________________________________
//*********************output matrix by ostream,in fact this fun is not a member.








//______________________________________________________________________________
void LinkedMatrix<T>::Transpose(LinkedMatrix<T> &b) const
{
	// 转置* t h i s，并把结果放入b
	b.a.Erase(); // 删除b中所有节点
				// 创建用来收集b中各行元素的箱子
	Chain<CNode<T> > *bin;
	bin = new Chain<CNode<T> > [cols + 1];	
	ChainIterator<HeadNode<T> > p;  // 头节点遍历器
	HeadNode<T> *h = p.Initialize(a);  // h 指向* t h i s的第一个头节点
	// 把* t h i s的元素复制到箱子中
	while (h)
	{ 
		// 检查所有的行
		int r = h->row; // 行链表中的行数
		ChainIterator<CNode<T> > q;  // 行链表遍历器
		CNode<T> *z = q.Initialize(h->a);  // z指向行链表的第一个节点
		CNode<T> x; // 临时节点
		// *this第r行中的元素变成b中第r列的元素
		x.col = r;	//检查* this中第r行的所有非0元素
		while (z)
		{
			// 遍历第r行
			x.value = z->value;
			bin[z-> col].Append (x);
			z = q.Next(); // 该行的下一个元素
		}
		h = p.Next(); // 继续下一行
	}
	// 设置b的维数
	b.rows = cols;
	b.cols = rows;
	// 装配b的头节点链表
	HeadNode<T> H;
	// 搜索箱子
	for (int i = 1; i <= cols; i++)
		if (!bin[i].IsEmpty())
		{
			// 转置矩阵的第i 行
			H.row = i;
			H.a = bin[i];
			b.a.Append(H);
			bin[i].Zero();
		} // 置链表头指针为0
		H.a.Zero(); // 置链表头指针为0
		delete [] bin;
}
//______________________________________________________________________________