学生成绩管理系统 - 数据结构上机实验报告Yangtze(5)

实验总结:

通过实验明白了栈的“后进先出”的特点，栈强调在栈顶的操作，而不是元素的

位序。栈的优点就是读取速度快，而且数据可以共享；缺点就是存在于栈中的数据大小及周期必须是确定的，缺乏灵活性。

而通过对递归算法的应用，体会到了递归的便利，递归使算法的描述简洁而且易于理解，十分有效的解决了一大类问题，但是在使用递归算法的同时还要注意必须有一个明确的递归出口。

软件学院上机实验报告

备注：学生应根据实验的要求，设计一个实验过程（包括程序代码、各种定义说明），并根据实验的结论及实验过程中出现的情况（错误、异常等）得出的体会。要求学生每人一台计算机，独立完成实验的全过程。

实验题目：矩阵的存储压缩 实验要求：1.特殊矩阵的压缩存储

2.稀疏矩阵的压缩存储 3.稀疏矩阵的快速转质

实验内容：1.数组的抽象数据类型

ADT Array{

数据对象：D={aj1j2…jn|n(>0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i 维下标，aj1j2…jn∈ElemSet, ji=0, …,bi-1, i=1,2, …,n} 数据关系：R={R1,R2, …,Rn} Ri={|0≦jk≦bk-1,1≦k≦n且k≠i, 0≦ji≦bi-2, aj1...ji...jn,aj1…ji+1…jn∈D, i=2, …,n } 基本操作： InitArray( &A, n, bound1, …, boundn ) 操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。 DestroyArray( &A ) 操作结果：销毁数组A。 Value( A, &e, index1, …, indexn ) 初始条件：A是n维数组，e为元素变量，随后是n个下标值。 操作结果：若各下标不越界，则e赋值为所指定的A的元素值，并返回OK。 Assign( &A, e, index1, …, indexn ) 初始条件：A是n维数组，e为元素变量，随后是n个下标值。 操作结果：若下标不越界，则将e的值赋给所指定的A的元素，并返回OK。 }ADT Array 2.稀疏矩阵的抽象数据类型:

ADT SparseMatrix{ 数据对象：D={aij | i=1,2,…,m; j=1,2,..,n;aij∈Elemset, m和n分别称为矩阵的行数和列数。} 数据关系：R={Row,Col} Row={ | 1<=i<=m, 1<=j<=n-1} Col= { | 1<=i<=m-1, 1<=j<=n} 基本操作： CreateSMatrix(&M)； 操作结果：创建稀疏矩阵M。 DestroySMatrix(&M)； 初始条件：稀疏矩阵M存在。 操作结果：销毁稀疏矩阵M。 PrintSMatrix(M)； 初始条件：稀疏矩阵M存在。 操作结果：输出稀疏矩阵M。 CopySMatrix(M，＆T)； 初始条件：稀疏矩阵M存在。 操作结果：由稀疏矩阵M复制得到T。 AddSMatrix(M，N，&Q)； 初始条件：稀疏矩阵M与N的行数和列数对应相等 操作结果：求稀疏矩阵的和Q=M+N。 SubtMatrix(M，N，&Q)； 初始条件：稀疏矩阵M与N的行数和列数对应相等 操作结果：求稀疏矩阵的差Q=M-N。 MultSMatrix(M，N，＆Q)； 初始条件：稀疏矩阵M的列数等于N的行数。 操作结果：求稀疏矩阵乘积Q=M*N。 TransposeSMatrix(M，＆T)； 初始条件：稀疏矩阵M存在。 操作结果：求稀疏矩阵M的转置矩阵T。 }ADT SparseMatrix

稀疏矩阵的应用:

编写程序实现矩阵的基本的加法、减法、成法运算，代码如下： #include using namespace std; class Matrix {private:

int row,col; double **mx; public: Matrix(){} ~Matrix();

Matrix(Matrix &m);

Matrix(int n,int m);

friend Matrix operator*(Matrix &,Matrix &); friend istream & operator >>(istream &,Matrix &); friend ostream & operator <<(ostream &,Matrix &); friend Matrix operator+(Matrix &,Matrix &); friend Matrix operator-(Matrix &,Matrix &); friend Matrix operator!(Matrix &); };

Matrix::Matrix(Matrix &m) {

int i,j;

row=m.row; col=m.col;

mx=new double *[row]; for(i=0;i

mx[i]=new double[col]; for(i=0;i

Matrix::~Matrix() { int i;

for(i=0;i

Matrix::Matrix(int n,int m) {

int i,j; row=n; col=m;

mx=new double *[row]; for(i=0;i

mx[i]=new double[col]; for(i=0;i

istream& operator>>(istream &input,Matrix &m) {

int i,j;

for(i=0;i>m.mx[i][j];

return input; }

Matrix operator+(Matrix &m1,Matrix &m2) {

Matrix m(m1.row,m1.col); int i,j;

for(i=0;i

m.mx[i][j]=m1.mx[i][j]+m2.mx[i][j]; return m; }

Matrix operator*(Matrix &m1,Matrix &m2) {

if(m1.col!=m2.row)throw 1; Matrix m(m1.row,m2.col); int i,j,t=0,s,l=0;

for(i=0;i

for(j=0,s=0;j

m.mx[t][l]+=m1.mx[t][j]*m2.mx[s][l]; }

if((i+1)%m.col==0) {t++;l=0;} else l++; }

return m; }

ostream& operator<<(ostream &output,Matrix &m) {

int i,j;

for(i=0;i

for(j=0;j

output<