数据结构算法与应用-C++语言描述 矩阵

数据结构算法与应用-C++语言描述 chain 矩阵
定义和 *** 作
一个m x n的矩阵 (matrix ) 是一个m行、n列的表 ，m和n是矩阵的维数 ( dimension )。

	 列1 列2  列3 列4
  行1 7   2   0   9
  行2 0   1   0   5
  行3 6   4   2   0
  行4 8   2   7   3 
  行5 1   4   9   6

//类 matrix
//一个rows x cols 的整型矩阵 M 可用如下的二维整数数组来描述
//int x[rows()][cols];
//其中 M(i,j) 对应于 x[i-1][i-1]。这种描述形式使应用时的数组索引和和矩阵索引不同: 数组的索
//引从 0 开始，和矩阵的索引从 1 开始。另一种描述形式是把数组x 定义为
//int x[rows()+1][cols+1];
//并且对形式为 [0][*] 和 [*][0] 的数组元素奔之不用。本节我们所开发的一个矩阵描述方法，
//是用行主次序把矩阵映射到一个一维数组中。
//类 matrix 用一个一维数组 element 存储，在行主次序中，储存 rows() x cols 矩阵的 rows()#xcols
//个元素。程序 7-2 是类头，即类声明。我们要重载琐数 *** 作符 ( )，使得在程序中对和抢阵索引的
//用法和在数学中的一样。我们还要重载算术 *** 作符，使它们能够用于矩阵对象。

#include 
#include 
#include 
#include 
using namespace std;

//矩阵类 matrix
template
class matrix
{	
	template
    friend ostream& operator<<(ostream& ,const matrix&);
    template
	friend istream& operator>>(istream& ,matrix&);
public:
	matrix(int theRows = 0,int theCols = 0);
	matrix(const matrix&);
	~matrix(){ delete[] element;}
	int rows() const{ return theRows; }
	int columns() const{ return theCols; }
	T& operator()(int i,int j) const;
	matrix& operator=(const matrix&);
	matrix operator+() const;
	matrix operator+(const matrix&) const;
	matrix operator-() const;
	matrix operator-(const matrix&) const;
	matrix operator*(const matrix&) const;
	matrix& operator+=(const T&);

	//ex15. 扩充 matrix 类:增加方法-=(每个矩阵元素减去一个指定的值),<<(输入一个矩阵),*=(每个矩阵元素乘以一个指定的值 )，/=。测试编写的代码。
	matrix operator++() const;
	matrix operator--() const;
	matrix& operator-=(const T&);
	matrix& operator*=(const T&);
	matrix& operator/=(const T&);
    matrix  transpose();

private:
	int theRows = 0;//矩阵的行数
	int	theCols = 0;//矩阵的列数
	T* element = nullptr;//数组element
};

//和矩阵类 matrix 的构造函数和复制构造函数
template
matrix::matrix(int theRows, int theCols)
{
	//矩阵构造函数
	//检验行数和列数的有效性
	if(theRows < 0 || theCols < 0)
		throw logic_error("theRows < 0 || theCols < 0");
	if((theRows == 0 || theCols == 0)
	 &&(theRows!=0 || theCols!=0))
		throw logic_error("(theRows == 0 || theCols == 0) && (theRows!=0||theCols!=0)");

	//创建矩阵
	this->theRows = theRows;
	this->theCols = theCols;
	element = new T(theRows * theCols);
}

//矩阵类 matrix 对赋值 *** 作符=的重载
template
matrix& matrix::operator=(const matrix& m)
{
	//赋值 .(*this) = m
	if(this != &m)
	{
		//不能自己复制自己
		delete [] element;
		theRows = m.theRows;
		theCols = m.theCols;
		element = new T[theRows * theCols];
		//复制每一个元素
		copy(m.element,m.element + theRows * theCols,element);
	}
	return *this;
}

//为了用左右括号来表示矩阵索引，我们重载 C++ 的函数 *** 作符()，它可以具有任意个数
//的参数，不过在矩阵应用中，我们需要两个整型参数。程序 7-5 是重载函数 *** 作符 () 的代码。
//它的返回值是对索引为 (i,j) 的矩阵元素的引用，这个引用既可以用来取值，也可以用来赋值。
//例如，语句 a(i,j) = 2 和语句 x = a(i,j) 都可以，其中 a 是矩阵。
// 和矩阵类 matrix 对 ()  *** 作符的重载
template
T& matrix::operator()(int i,int j) const
{
	//返回对元素element (i,j) 的引用
	if(i < 1 || i > rows() || j < 1 || j > columns())
		throw logic_error("i < 1 || i > theRows || j < 1 || j > theCols ");
	return element[(i - 1) * columns() + (j - 1)];	
}

//程序是重载 *** 作符 +，以实现矩阵加法。因为矩阵被映射到一维数组，所以两个矩
//阵相加只需要一层 for 循环。诸如矩阵的一元增值 *** 作 ( 每个元素增加相同的值 ) 和和矩阵减法
//的代码都与矩阵加法的代码相似。
template
matrix matrix::operator+(const matrix& m) const
{
	//返回矩阵 w = (*this) + m
	if(theRows != m.theRows || theCols != m.theCols)
		throw logic_error("theRows != m.theRows || theCols != m.theCols");

	//生成结果矩阵
	matrix w(theRows, theCols);
	for(int i = 0; i
matrix matrix::operator*(const matrix& m) const
{
	//矩阵乘法 . 返回结果矩阵 w = (*this) * m
	if(theCols != m.theCols)
		throw logic_error("theCols != m.theCols");

	matrix w(theRows,m.theCols); //结果和矩阵

	// 定义矩阵 *this，m和w的游标且初始化以为 (1,1) 元素定位
	int ct = 0,cm = 0,cw = 0;
	//在程序的矩阵乘法代码中有三层for循环，循环结构与程序加的相似。
	//对所有i 和j 计算 w(i,j)
	//最内层的循环利用公式C(i,j) = A(i,j) + B(i,j)来计算矩阵乘积后索引为 (i,j) 的元素
	for(int i = 1; i <= theRows; i++)
	{
		// 计算结果矩阵的第i行
		for(int j = 1;j <= m.theCols;j++)
		{
			//计算w(i,j) 第一项
			T sum = element[ct] * m.element[cm];

			//累加其余所有项
			for(int k = 2; k<=theCols;k++)
			{
				//进入最内层循环时
				//element[ct] 是第i行的第一个元素
				//m.element[cm] 是第j列的第一个元素
				//为了得到第i行的下一个元素将ct增加 1，
				//因为在行主次序中同一行的元素是连续存放的
				//为了得到第j列的下一个元素，将 cm 增加 m.theCols,
				//因为在行主次序中同一列的两个相邻元素在位置上相差 m.theCols。
				ct++; //*this 中第i行的下一项
				cm += m.theCols;//m中第j列的下一项
				sum += element[ct] * m.element[cm];
			}
			//当最内层循环完成时，ct指向第i行的最后一个元素
			//cm指向第j列的最后一个元素
			//对于j循环的下一次循环，起始时必须将ct指向第i行的第一个元素
			w.element[cw++] = sum; //存储在w(i,j)

			//从行的起点和下一列从新开始
			ct -= theCols - 1;
			cm = j;
		}
		//cm指向m的下一列的第一个元素。对ct的调整是在最内层循环完成后进行的。
		//当j循环完成时，需要将 ct 指向下一行的第一个元素，
		//而将 cm 指向第一列的第一个元素。

		// 从下一行和第一列重新开始
		ct += theCols;
		cm = 0;
	}
	return w;
}

//ex15. 扩充 matrix 类:增加方法-=(每个矩阵元素减去一个指定的值),
//<<(输入一个矩阵),*=(每个矩阵元素乘以一个指定的值 )，/=。测试编写的代码。
template
ostream& operator<<(ostream& out,const matrix& m)
{
	for(int i = 0;i < m.rows(); i++)
	{
		for(int j = 0; j < m.columns(); j++)
		{
			out<
istream& operator>>(istream& in, matrix& m)
{
	//矩阵构造函数
	//检验行数和列数的有效性
	if(m.theRows < 0 || m.theCols < 0)
		throw logic_error("theRows < 0 || theCols < 0");
	if((m.theRows == 0 || m.theCols == 0)
	 &&(m.theRows != 0 || m.theCols != 0))
		throw logic_error("(theRows == 0 || theCols == 0) && (theRows!=0||theCols!=0)");
	delete[] m.element;
	m.element = new U[m.rows() * m.columns()];

	for(int i = 0; i < m.rows();i++)
	{
		for(int j = 0;j < m.columns();j++)
		{
			if(in)
			{
				in>>m.element[i * m.columns() + j];
			}
			else
			{
				m.element[i * m.columns() + j] = 0;
			}
		}
	}
	return in;
}

template
matrix matrix::operator++() const
{
	matrix result(rows(),columns());
	for(int i = 0; i < rows() * columns();i++)
	{
		result.element[i] = ++element[i];
	}
	return result;
}


template
matrix matrix::operator--() const
{
	matrix result(rows(),columns());
	for(int i = 0; i < rows() * columns(); i++)
	{
		result.element[i] = --element[i];
	}
	return result;
}


template
matrix matrix::operator-(const matrix& right) const
{
	if(rows() != right.rows() || columns() != right.columns())
		throw logic_error("rows() != right.rows() || columns() != right.columns()");

	matrix result(rows(),columns());
	for(int i = 0; i < rows() * columns();i++)
	{
		result.element[i] = element[i] - right.element[i];
	}
	return result;
}


template
matrix& matrix::operator+=(const T& value)
{
	for(int i = 0; i < rows() * columns(); i++)
	{
		element[i] += value;
	}
	return *this;
}

template
matrix& matrix::operator-=(const T& value)
{
	for(int i = 0; i < rows() * columns(); i++)
	{
		element[i] -= value;
	}
	return *this;
}

template
matrix& matrix::operator*=(const T& value)
{
	for(int i = 0; i < rows() * columns();i++)
	{
		element[i] *= value;
	}
	return *this;
}

template
matrix& matrix::operator/=(const T& value)
{
	if(value == 0)
		throw logic_error("divide 0");
	for(int i = 0; i
matrix matrix::transpose()
{
	matrix result(columns(),rows());
	for(int i = 0; i < rows() * columns(); i++)
	{
		result.element[(i%columns())*rows() + i / columns()] = 
		element[i];
	}
	return result;
}



int main()
{
	matrix m(2,4);
	string s1("2 3 0 1 2 3 4 5");
	istringstream iss1(s1);
	iss1>>m;
	cout< m5 = m.transpose();
	cout << m5 << endl;
	//cout< 
//ex17. 1 ) 开发一个类 matrixAs2DArray，用二维数组表示矩阵。这个类应该包含所有和矩阵方法和
//和矩阵转置。
//2 ) 测试你的方法。
//3 ) 针对矩阵加法和乘法的性能，对类 matrix 和类 matrixAs2DArray 进行比较。比较的方
//法是测量实际的运行时间。你认为行主映射的一维数组表示方法比二维数组表示方法
//好在哪里


#include 
#include 

using namespace std;
template
class matrix2DArray
{
	template
    friend ostream& operator<<(ostream& ,const matrix2DArray&);
    template
	friend istream& operator>>(istream& ,matrix2DArray&);
public:
	matrix2DArray():
		rows(0),
		columns(0),
		element(nullptr)
	{

	}
	matrix2DArray(int theRows,int theColumns);
	matrix2DArray(const matrix2DArray& right);
	~matrix2DArray();
	T& operator()(int i,int j) const;
	matrix2DArray& operator=(const matrix2DArray&);
	matrix2DArray  operator+(const matrix2DArray&) const;
	matrix2DArray  operator-(const matrix2DArray&) const;
	matrix2DArray  operator*(const matrix2DArray&) const;
	matrix2DArray  transpose();
private:
	void clear();
	void initialize();
	int rows;
	int columns;
	T** element;
};


template
ostream& operator<<(ostream& out,const matrix2DArray& m)
{
	for(int i = 1;i <= m.rows;i++)
	{
		for(int j = 1;j <= m.columns;j++)
		{
			out<
istream& operator>>(istream& in,matrix2DArray& m)
{
	m.clear();
	in>>m.rows>>m.columns;
	if(m.rows < 0 || m.columns < 0) 
		throw logic_error("Rows and columns must be >=0");
	if(m.rows == 0 && m.columns > 0 || m.columns == 0 && m.rows > 0)
		throw logic_error("Both or neither rows and columns should be zero.");
	m.initialize();
	for(int i = 1;i <= m.rows;i++)
	{
		for(int j = 1;j <= m.columns;j++)
		{
			if(in)
			{
				in >> m.element[i][j];
			}
			else
			{
				m.element[i][j] = 0;
			}
		}
	}
	return in;
}

template
matrix2DArray::matrix2DArray(int theRows,int theColumns)
	:rows(theRows),
	 columns(theColumns)
{
	if(rows < 0 || columns < 0)
		throw logic_error("Rows and columns must be >=0");
	if(rows == 0 && columns < 0)
		throw logic_error("Both or neither rows and columns should be zero.");	
	if(rows == 0)
	{
		element = nullptr;
		return;
	}
	initialize();
}

template
matrix2DArray::matrix2DArray(const matrix2DArray& right):
	matrix2DArray()
{
	if(&right == this)
		return ;
	clear();
	rows = right.rows;
	columns = right.columns;
	initialize();
	for(int i = 1; i <= rows; i++)
	{
		for(int j = 1;j <= columns; j++)
		{
			element[i][j] = right.element[i][j];
		}
	}
}

template
matrix2DArray::~matrix2DArray()
{
	clear();
}

template
void matrix2DArray::clear()
{
	for(int i = 1;i <= rows;i++)
	{
		delete[] element[i];
	}
	delete[] element;
	element = nullptr;
}

template
void matrix2DArray::initialize()
{
	element = new T* [rows + 1];
	for(int i = 1; i <= rows; i++)
	{
		element[i] = new T[columns + 1];
	}
}

template
T& matrix2DArray::operator()(int i,int j) const
{
	if(i < 1 || i > rows || j < 1 || j > columns)
		throw logic_error("i < 1 || i > rows || j < 1 || j > columns");
	return element[i][j];
}

template
matrix2DArray& matrix2DArray::operator=(const matrix2DArray& right)
{
	if(&right == this)
		return *this;
	clear();
	rows = right.rows;
	columns=  right.columns;
	initialize();
	for(int i = 1;i <= rows; i++)
	{
		for(int j = 1;j <= columns;j++)
		{
			element[i][j] = right.element[i][j];
		}
	}
	return *this;
}

template
matrix2DArray matrix2DArray::operator+(const matrix2DArray& right) const
{
	if(rows != right.rows || columns != right.columns)
		throw logic_error("matrixAs2DArray addition should got same rows and columns.");

	matrix2DArray result(rows,columns);
	for(int i = 1;i <= rows; i++)
	{
		for(int j = 1;j <= columns;j++)
		{
			result.element[i][j] = element[i][j] + right.element[i][j];
		}
	}
	return result;
}

template
matrix2DArray matrix2DArray::operator-(const matrix2DArray& right) const
{
	if(rows != right.rows || columns != right.columns)
		throw logic_error("rows != right.rows || columns != right.columns");

	matrix2DArray result(rows,columns);
	for(int i = 1; i <= rows; i++)
	{
		for(int j = 1;j <= columns;j++)
		{
			result.element[i][j] = element[i][j] - right.element[i][j];
		}
	}
	return result;
}

template
matrix2DArray matrix2DArray::operator*(const matrix2DArray& right) const
{
	if(columns != right.rows)
		throw logic_error("matrixAs2DArray multply must have m * n and n *s .");

	matrix2DArray result(rows,right.columns);
	for(int i = 1;i<=rows;i++)
	{
		for(int j = 1;j <= right,columns;j++)
		{
			result.element[i][j] = 0;
			for(int k = 1;k<=columns;k++)
			{
				result.element[i][j] += element[i][k] * right.element[k][j];
			}
		}
	}	
	return result;
}

template
matrix2DArray matrix2DArray::transpose()
{
	matrix2DArray result(columns,rows);
	for(int i = 1;i <= rows;i++)
	{
		for(int j = 1;j <= columns;j++)
		{
			result.element[j][i] = element[i][j];
		}
	}
	return result;
}


int main()
{
	string s1("2 3 0 1 2 3 4 5");
	istringstream iss1(s1);
	matrix2DArray m1;
	iss1>>m1;
	cout< m2 = m1.transpose();
	cout< 
例7-4 考察佛罗里达州( Florida ) 的6个城市 Gainesville 、Jacksonville 、Miami 、Orlando ，Tallaha–ssee 和 Tampa。按照上面列出的顺序，从1 ~ 6编号。任意两个城市之间的距离可以用一个6x6的矩阵distance来表示。和矩阵的第i行和第i列代表第i个城市。distance(i) 代表城市i和城市j之间的距离。 给出了相应的矩阵，因为对于所有的i和j有 distance(i,j)=distance(j,i)，所以这是一个对称和矩阵
 

	GN   JX   MI    OD    TL    TM

GN  0    73   333   114   148   129

JX  73   0    348   140   163   194

MI  333  348   0    229   468   250

OD  114  140   229   0    251   84

TL  148  163   468   251   0    173

TM  129  194   250   84    273   0

 
例7-5 假定一个栈有n个纸盒，纸盒1位于栈底，纸盒n位于栈项。每个纸盒的宽度
 为w，深度为d第i个纸盒的高度为hi 栈的体积为wd(h的和)。 在栈折叠(stack folding)问题中，我们要选择一个折叠点i，把栈分成两个相邻的子栈，其中一个子栈包含纸盒1至i另一个子栈包含纸盒i+1至n。重复这种折叠过程，可以得到若干个子栈。如果生成了s个子栈，则这些子栈所需要的空间宽度为sw，深度为d，高度h为最高子栈的高度。s个子栈所需要的空间容量为 swdh。由于h是第i个至第j个纸盒所构成栈的高度(其中i<=j),因此h的可能取值可由nxn矩阵H给出，其中对于i>j有H(i,j) = 0，由于每个纸盒的高度可以认为大于0，所以 成H(i,j)=0代表一个不可能的高度。图 7-10a 给出了一个五个纸盒的栈。每个矩形中的数字代表纸盒的高度。图 7-10b 给出了五个纸盒栈折压成三个栈后的情形，其中最大栈的高度为7。矩阵H是一个上三角和矩阵，如图7-10c所示。栈折叠问题的一个应用是栈所包含的内容为电子部件，目的是折叠后的栈所需空间最小
 
-----
|   |      
|   |
| 5 |
|   |
|   |
-----
| 2 |
|   |
-----
|   |
| 4 |
|   |
|   |
-----
|   |
| 3 |				-----	-----			
|   |				|   |	|	|			
-----		-----	|	|	|	|			  1  2  3  4   5
|   |		|	|	| 4	|	| 5 |			  —			   —
|   |		|	|	|	|	|	|			1|6  9  13 15 20|  
| 6 |		| 6 |	-----	|	|			2|0  0  7  9  14|
|   |		|	|	|	|	-----			3|0  0  4  6  11|
|   |		|	|	| 3 |	|	|			4|0  0  0  2  7 |
|   |		|	|	|	|	| 2 |			5|0  0  0  0  5 |
-----		-----	-----	-----			  —			   —
 a 栈  			b 三个栈折叠                     c H矩阵

 
//对角矩阵
 //一个rows x rows的对角矩阵可以表示为一个二维数组element[rows][rows]，其中
 //element[i-1][j-1] 表示 D(i,j)。这种表示法需要rows个类型为T的数据空间。然而，对角
 //矩阵最多只有 rows 个非0元素，因此可以用一维数组 element[rows]来表示对角和矩阵，其
 //中 element[i-1] 表示 D(i,j)。所有未在一维数组中出现的矩阵元素均为0。这种表示法仅需要
 //rows 个类型为T的数据空间，而且产生了 C++ 类 diagonalMatrix。
 //构造函数的时间复杂度，当T是内部类型时为 O(1)，当T是用户定义类型时为 O(rows)。
 
//类 diagonalMatrix 的声明
template 
class diagonalMatrix
{
public:
	diagonalMatrix(int theN = 10);
	~diagonalMatrix(){delete []element;}
	T get(int,int) const;
	void set(int,int,const T&);
private:
	int n;	//矩阵维数
	T* element;	//存储对角和矩阵的一维数组
};

//diagonalMatrix构造函数
template
diagonalMatrix::diagonalMatrix(int theN)
{
	//构造函数
	//检验 the 的值是否有效
	if(theN < 1)
		throw logic_error("矩阵大小必须 > 0");
	n = theN;
	element = new T[n];
}

//类 diagonalMatrix 的方法 get
template
T diagonalMatrix::get(int i,int j) const
{
	//返回矩阵中 (i,j) 位置上的元素
	//检验i和j的值是否有效
	if(i < 1 || j < 1 || i > n || j > n)
		throw logic_error("矩阵索引超出范围");

	if(i == j)
		return element[i-1]; //对角线上的元素
	else
		return 0; //非对角线上的元素
}	

//类 diagonalMatrix 的方法 set
template
void diagonalMatrix::set(int i,int j,const T& newValue)
{
	//存储 (i,j) 项的新值
	//检查i和j的值是否有效
	if(i < 1 || j < 1 || i > n || j > n)
		throw logic_error("矩阵索引超出范围");

	if(i == 1)
	{
		element[i-1] = newValue; //存储对角元素的值
	}
	else
	{
		if(newValue != 0) //非对角元素的值必须是 0
		{
			throw logic_error("nondiagonal element must be zero");
		}
	}
}

 
//三对角矩阵
 在一个 rows x rows 的三对角矩阵中, 非 0 元素排列在如下三条对角线上:
 1.主对角线一i = j。
 2.主对角线之下的对角线 ( 称低对角线 ) 一 i=j+1。
 3.主对角线之上的对角线 (称高对角线 ) 一 i=j-1。
 这三条对角线上的元素总数为3rows-2。可以用一个容量为3rows-2的一维数组element来描述三对角和矩阵，因为只有三条对角线上的元素需要真正地存储。4x4三对角和矩阵。三条对角线上共有 10 个元素。
 如果逐行映射，则 element[0:9]={2,1,3,1,3,5,2,7,9,0};
 如果逐列映射，则 element = {2,3,1,1,5,3,2,9,7,0};
 如果从最下面的对角线开始逐条对角线映射，则有element={3,5,9,2,1,2,0,1,3,7}如上所述，把三对角和矩阵映射到数组element 有三种不同方式。每一种方式都有不同的 get 和 set 函数代码。假定类tridiagonalMatrix 采用的是逐条对角线映射。数据成员和构造本数与类 diagonal 的相似。
 
	2 1 0 0
	3 1 3 0
	0 5 2 7
	0 0 9 0 

 
//三对角和矩阵的方法 get
template
T tridiagonalMatrix::get(int i, int j) const
{
	//返回矩阵中 (i,j) 位置上的元素
	//检验 i和j 的值是否有效
	if(i < 1 || j < 1 || i > n||j > n)
		throw logic_error("矩阵索引超出范围")；
	//确定要返回的元素
	switch(i - j)
	{
		case 1: //下对角线
			return element[i-2];
		case 0: //主对角线
			return element[n+i-2];
		case -1: //上对角线
			return element[2*n+i-2];
		default: 
			return 0;
	}
}

 
//三角矩阵
 
/*
 —			  —
|x             |
|  x           |
|    x         |
|      x       |
|        x     |
|          x   |
|            x |
 —			  — 
  对角矩阵

 —			  —
|x x           |
|x x x         |
|  x x x       |
|    x x x     |
|      x x x   |
|        x x x |
|          x x |
 —			  — 
 三对角矩阵

 —			  —
|x             |
|x x           |
|x x x         |
|x x x x       |
|x x x x x     |
|x x x x x x   |
|x x x x x x x |
 —			  — 
 下三角

 —			  —
|x x x x x x x |
|  x x x x x x |
|    x x x x x |
|      x x x x |
|        x x x |
|          x x |
|            x |
 —			  — 
上三角

 
template
void lowerTriangleMatrix::set(int i,int j,const T& newValue)
{
	//给 (i,j) 元素赋新值
	//检验i和j的值是否合法
	if(i < 1 || j < 1 || i > n || j > n)
		throw logic_error("矩阵索引超出范围");
	//(i,j) 在下三角，当且仅当i >= j
	if(i >= j)
	{
		element[i * (i - 1) / 2 + j - 1] = newValue;
	}
	else
	{
		if(newValue != 0)
			throw logic_error("下三角元素必须是零");
	}
}

 
//对角矩阵
//一个rows x rows的对角矩阵可以表示为一个二维数组element[rows][rows]，其中
//element[i-1][j-1] 表示 D(i,j)。这种表示法需要rows个类型为T的数据空间。然而，对角
//矩阵最多只有 rows 个非0元素，因此可以用一维数组 element[rows]来表示对角和矩阵，其
//中 element[i-1] 表示 D(i,j)。所有未在一维数组中出现的矩阵元素均为0。这种表示法仅需要
//rows 个类型为T的数据空间，而且产生了 C++ 类 diagonalMatrix。
//构造函数的时间复杂度，当T是内部类型时为 O(1)，当T是用户定义类型时为 O(rows)。

//ex20. 
//1 ) 扩充 diagonalMatrix 类，增加以下成员方法 : 输入、输出、加、减、乘
//和和矩阵转置。每个成员方法的结果都是一个用一维数组表示的对角矩阵。
//2 ) 测试代码。
//3 ) 每个成员方法的时间复杂度是多少?

//类 diagonalMatrix 的声明

#include 
#include 
#include 

using namespace std;

template 
class diagonalMatrix
{
	template
	friend ostream& operator<<(ostream&, const diagonalMatrix&);
	template
	friend istream& operator>>(istream&, diagonalMatrix&);
public:
	diagonalMatrix(int theN = 10);
	~diagonalMatrix(){delete []element;}
	diagonalMatrix(const diagonalMatrix&);
	T get(int,int) const;
	void set(int,int,const T&);
	diagonalMatrix& operator=(const diagonalMatrix&);
	diagonalMatrix operator+(const diagonalMatrix&) const;
	diagonalMatrix operator-(const diagonalMatrix&) const;
	diagonalMatrix operator*(const diagonalMatrix&) const;
	diagonalMatrix operator/(const diagonalMatrix&) const;
	diagonalMatrix transpose() 
	{
		return *this;
	}
private:
	void checkIndex(int i, int j) const;
	int n;	//矩阵维数
	T* element;	//存储对角和矩阵的一维数组
};

//diagonalMatrix构造函数
template
diagonalMatrix::diagonalMatrix(int theN)
{
	//构造函数
	//检验 the 的值是否有效
	if(theN < 1)
		throw logic_error("矩阵大小必须 > 0");
	n = theN;
	element = new T[n];
}

//类 diagonalMatrix 的方法 get
template
T diagonalMatrix::get(int i,int j) const
{
	//返回矩阵中 (i,j) 位置上的元素
	//检验i和j的值是否有效
	if(i < 1 || j < 1 || i > n || j > n)
		throw logic_error("矩阵索引超出范围");

	if(i == j)
		return element[i-1]; //对角线上的元素
	else
		return 0; //非对角线上的元素
}	

//类 diagonalMatrix 的方法 set
template
void diagonalMatrix::set(int i,int j,const T& newValue)
{
	//存储 (i,j) 项的新值
	//检查i和j的值是否有效
	if(i < 1 || j < 1 || i > n || j > n)
		throw logic_error("矩阵索引超出范围");

	if(i == 1)
	{
		element[i-1] = newValue; //存储对角元素的值
	}
	else
	{
		if(newValue != 0) //非对角元素的值必须是 0
		{
			throw logic_error("nondiagonal element must be zero");
		}
	}
}

template
void diagonalMatrix::checkIndex(int i,int j) const
{
	if(i < 1 || i > n || j < 1 || j > n)
		throw logic_error("i < 1 || i > n || j < 1 || j > n");
}

template
ostream& operator<<(ostream& out,const diagonalMatrix& m)
{
	for(int i = 0;i < m.n; i++)
	{
		for(int j = 0; j < m.n; j++)
		{
			if(i == j) 
				out<
istream& operator>>(istream& in,diagonalMatrix& m)
{
	for(int i = 0; i < m.n; i++)
	{
		if(in) 
			in>>m.element[i];
		else
			m.element[i] = 0;
	}
	return in;
}

template
diagonalMatrix::diagonalMatrix(const diagonalMatrix& m)
{
	n = m.n;
	element = new T[n];
	copy(m.element,m.element + n,element);
}

template
diagonalMatrix diagonalMatrix::operator-(const diagonalMatrix& m) const
{
	if(n != m.n)
		throw logic_error("must have same size");
	diagonalMatrix result(n);
	for(int i = 0; i < n; i++)
	{
		result.element[i] = element[i] - m.element[i];
	}
	return result;
}

template
diagonalMatrix diagonalMatrix::operator+(const diagonalMatrix& m) const
{
	if(n != m.n)
		throw logic_error("must have same size");
	diagonalMatrix result(n);
	for(int i = 0; i < n; i++)
	{
		result.element[i] = element[i] + m.element[i];
	}
	return result;
}


template
diagonalMatrix diagonalMatrix::operator*(const diagonalMatrix& m) const
{
	if(n != m.n) 
		throw logic_error("must have same size");
	diagonalMatrix result(n);
	for(int i = 0; i < n; i++)
	{
		result.element[i] = element[i] * m.element[i];
	}
	return result;
}

template
diagonalMatrix diagonalMatrix::operator/(const diagonalMatrix& m) const
{
	if(n != m.n) 
		throw logic_error("must have same size");
	diagonalMatrix result(n);
	for(int i = 0; i < n; i++)
	{
		if(m.element[i] == 0)
			result.element[i] = 0;	
		result.element[i] = element[i] / m.element[i];
	}
	return result;
}

template
diagonalMatrix& diagonalMatrix::operator=(const diagonalMatrix& m)
{
	n = m.n;
	delete[] element;
	element = new T[n];
	copy(m.element, m.element + n, element);
	return *this;
}


int main()
{
	diagonalMatrix m;
	string s1("2 3 0 1 2 3 4 5");
	istringstream iss1(s1);
	iss1>>m;
	cout< m1;
	s1 = {"1 2 3 4 5 6 7 8"};
	istringstream iss2(s1);
	iss2>>m1;
	cout< m2;
	m2 = m1 + m;
	cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5658627.html