数据结构课程设计：稀疏矩阵 *** 作

一、需求分析

二、概要设计

三、详细设计：Cpp1.cpp

四、调试分析

五、用户手册及测试数据：执行Cpp1.exe

六、附录

[数据结构] 数据结构稀疏矩阵加法实验报告

一、需求分析

假设稀疏矩阵M和N均以三元组表作为存储结构，试写出矩阵相加的算法 ；

另设三元组表存放结果矩阵。

处理要求：

1．输入稀疏矩阵M和N。

2．检测M和N能否相加

3．矩阵相加运算

4．打印输出结果

矩阵相加测试实例：输入

M= ，N=

二、概要设计

1．稀疏矩阵三元数组定义如下：

ADT SparseMatrix {

数据对象：

m和n分别称为矩阵的行数和列数 }

数据关系：R={ Row, Col }

基本 *** 作：

CreateSMatrix (&M)

*** 作结果：创建稀疏矩阵M。

AddSMatrix (M, N, &Q)

初始条件：稀疏矩阵M与N的行数列数相等。

*** 作结果：求得Q=M+N。

PrintSMatrix (M)

初始条件：稀疏矩阵M存在。

*** 作结果：输出稀疏矩阵M。

} ADT SparseMatrix

①．输入稀疏矩阵M和N。

CreateSMatrix_M (TSMatrix &M) //新建稀疏矩阵M

{ 输入矩阵M的行数,列数和非零元素个数

输入非零元素的行下标,列下标和值 }

// 稀疏矩阵相加，稀疏矩阵用数组来表示

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <memory.h>

typedef struct

{

int row

int col

int val

}Element // 稀疏矩阵元素

#define DIM 10 // 稀疏矩阵维数

#define ARY1_LEN 10 // 稀疏矩阵1数组维数

#define ARY2_LEN 10 // 稀疏矩阵2数组维数

Element ary1[ARY1_LEN+1]// 稀疏矩阵1数组

Element ary2[ARY2_LEN+1]// 稀疏矩阵2数组

Element ary3[ARY1_LEN+ARY2_LEN+1]// 稀疏矩阵之和数组

int cmp(const void *p1, const void *p2)

void matrix_add(Element ary1[], Element ary2[], Element ary3[])

void print_matrix(Element ary1[], Element ary2[], Element ary3[])

void main()

{

int i

int j

// 初始化稀疏矩阵1和2数组

srand(time(NULL))

for(i = 0i <ARY1_LENi++)

{

ary1[i].row = i % DIM

ary1[i].col = i % DIM

ary1[i].val = rand() % 4 + 1

}

ary1[i].row = -1

ary1[i].col = -1

ary1[i].val = 0

for(i = 0i <ARY2_LENi++)

{

ary2[i].row = i % DIM

ary2[i].col = (ARY2_LEN - i - 1) % DIM

ary2[i].val = rand() % 4 + 1

}

ary2[i].row = -1

ary2[i].col = -1

ary2[i].val = 0

// 将稀疏矩阵1和2相加，结果放到稀疏矩阵之和数组中

matrix_add(ary1, ary2, ary3)

// 打印稀疏矩阵相加的结果

print_matrix(ary1, ary2, ary3)

}

int cmp(const void *p1, const void *p2)

{

Element *pe1 = (Element *)p1

Element *pe2 = (Element *)p2

if (pe1->row == pe2->row)

{

return (pe1->col - pe2->col)

}

else

{

return (pe1->row - pe2->row)

}

}

void matrix_add(Element ary1[], Element ary2[], Element ary3[])

{

int i

int j

Element *pe

// 将稀疏矩阵1和2按找行、列顺序由小到大来排序，排序算法在cmp()中定义。

qsort(ary1, ARY1_LEN, sizeof(Element), cmp)

qsort(ary2, ARY2_LEN, sizeof(Element), cmp)

// 先将稀疏矩阵1复制给稀疏矩阵之和数组

memcpy(ary3, ary1, sizeof(Element)*ARY1_LEN)

j = ARY1_LEN

// 再将稀疏矩阵2的每个元素添加或累加到稀疏矩阵之和数组

for(i = 0i <ARY2_LENi++)

{

pe = (Element *)bsearch(&ary2[i], ary1, ARY1_LEN, sizeof(Element), cmp)

if (pe != (Element *)NULL)

{

ary3[pe-ary1].val += ary2[i].val

}

else

{

ary3[j++] = ary2[i]

}

}

ary3[j].row = -1

ary3[j].col = -1

ary3[j].val = 0

// 最后将稀疏矩阵之和按找行、列顺序由小到大来排序，排序算法在cmp()中定义。

qsort(ary3, j, sizeof(Element), cmp)

}

void print_matrix(Element ary1[], Element ary2[], Element ary3[])

{

int i

int j

int k

Element key

Element *pe

for(k = 0k <ARY1_LEN+ARY2_LEN+1k++)

{

if (ary3[k].row == -1)

{

break

}

}

for(i = 0i <DIMi++)

{

for(j = 0j <DIMj++)

{

key.row = i

key.col = j

pe = (Element *)bsearch(&key, ary1, ARY1_LEN, sizeof(Element), cmp)

if (pe != (Element *)NULL)

{

printf(" %d", pe->val)

}

else

{

printf(" 0")

}

}

if (i == DIM / 2)

{

printf(" +")

}

else

{

printf(" ")

}

for(j = 0j <DIMj++)

{

key.row = i

key.col = j

pe = (Element *)bsearch(&key, ary2, ARY2_LEN, sizeof(Element), cmp)

if (pe != (Element *)NULL)

{

printf(" %d", pe->val)

}

else

{

printf(" 0")

}

}

if (i == DIM / 2)

{

printf(" =")

}

else

{

printf(" ")

}

for(j = 0j <DIMj++)

{

key.row = i

key.col = j

pe = (Element *)bsearch(&key, ary3, k, sizeof(Element), cmp)

if (pe != (Element *)NULL)

{

printf(" %d", pe->val)

}

else

{

printf(" 0")

}

}

printf("\n")

}

http://hi.baidu.com/alonso13/blog/item/5a454f29a2b513f899250ac6.html

稀疏矩阵的定义及转置

#include <iostream>

using namespace std

const int maxNum=100

template <class T>

class Trituple

{

public:

int row

int col

T data

}

template <class T>

class SparseMatrix

{

friend istream&operator >>(istream&in,SparseMatrix<T>&m) //重载输入运算符

{

cout<<"请输入行数，列数以及非零元素个数：" //初始化稀疏矩阵的行、列以及非零元素的个数

in>>m.row>>m.col>>m.terms

if(m.terms>m.maxTerms)

{

cout<<"错误！非零元素溢出!"

}

else

{

for(int i=0i<m.termsi++)

{

cout<<"请输入第"<<i+1<<"个非零元素的行数，列数以及非零元素的值：" //通过初始化三元组来初始化矩阵

in>>m.t[i].row>>m.t[i].col>>m.t[i].data

while((m.t[i].row>=m.row)||(m.t[i].col>=m.col)) //矩阵元素下标检查

{

cout<<"错误！输入的矩阵元素下标越界！请从新输入："

in>>m.t[i].row>>m.t[i].col>>m.t[i].data

}

}

}

return in

}

friend ostream&operator <<(ostream&out,SparseMatrix<T>&m) //重载输出运算符

{

int i,j,k=0

out<<"行:"<<m.row<<" 列:"<<m.col<<" 非零元素个数:"<<m.terms<<endl

/*for(int i=0i<m.termsi++)

{

out<<"M["<<m.t[i].row<<"]["<<m.t[i].col<<"]="<<m.t[i].data<<endl//以 M[行][列] 的形式输出稀疏矩阵

}*/

for(i=0i<m.rowi++)

{

for(j=0j<m.colj++)

{

if((m.t[k].row==i)&&(m.t[k].col==j))

{

out<<m.t[k++].data<<" "

}

else

{

cout<<'0'<<" "

}

}

out<<endl

}

return out

}

private:

int row

int col

int terms

Trituple<T>*t //三元组数组

int maxTerms//最大元素数目

public:

SparseMatrix(int maxSize=maxNum) //构造函数

{

maxTerms=maxSize

row=col=terms=0

t=new Trituple<T>[maxSize]

}

~SparseMatrix()//析构函数

{

delete []t

}

/*SparseMatrix<T>transposedMatrix()//课本上的矩阵转置函数，逻辑正确，但是运行时内存报错

{

int *rowSize=new int[col] //存放转置矩阵各行中的非零元素个数

int *rowStart=new int[col] //存放转置矩阵各行中非零元素开始的存放位置

SparseMatrix<T>tp(maxTerms)//存放转置后的矩阵

tp.row=col

tp.col=row

tp.terms=terms

if(terms>0)

{

int i=0

int j=0

for(i=0i<coli++) //初始化rowSize

rowSize=0

for(i=0i<termsi++)

rowSize[t[i].col]++

rowStart[0]=0

for(i=1i<maxTermsi++) //初始化rowStart

rowStart[i]=rowSize[i]+rowStart[i-1]

//*****************************************

for(i=0i<coli++)

cout<<rowSize[i]<<" "

cout<<endl

for(i=0i<coli++)

cout<<rowStart[i]<<" "

cout<<endl

//******************************************

for(i=0i<termsi++)

{

j=rowStart[t[i].col] //j转置矩阵的三元组的行

//rowStart[t[i].col]++

tp.t[j].row=t[i].col

tp.t[j].col=t[i].row

tp.t[j].data=t[i].data

rowStart[t[i].col]++

}

}

delete []rowSize

delete []rowStart

return tp

}*/

void transposedMatrix(SparseMatrix &tp) //自己编写的转置矩阵函数

{

int i,j

if(terms>0)

{

int Row=0

tp.col=row//初始化转置矩阵的行、列以及非零元素个数

tp.row=col

tp.terms=terms

for(j=0j<colj++) //从第0列开始检查

{

for(i=0i<termsi++)

{

if(t[i].col==j) //检查原三元组的列，如果相同，则交换行、列赋值给转置矩阵

{

tp.t[Row].row=t[i].col

tp.t[Row].col=t[i].row

tp.t[Row].data=t[i].data

Row++

}

}

}

}

}

/*void displayTrituple() //输出三元组

{

for(int i=0i<termsi++)

{

cout<<t[i]

}

cout<<endl

}*/

}

//*******************************************SparseMatrixMain.cpp*************************************************

//#include "stdafx.h"

#include <iostream>

//#include "Trituple.h"

#include "SparseMatrix.h"

using namespace std

int _tmain(int argc, _TCHAR* argv[])

{

SparseMatrix<int>obj

SparseMatrix<int>obj1

cin>>obj

//obj.displayTrituple()//测试时使用的输出三元组的函数

cout<<"*********************初始矩阵**********************"<<endl

cout<<obj

obj.transposedMatrix(obj1) //调用自己编写的转置函数

//obj.transposedMatrix() //调用课本的转置函数

cout<<"*********************转置矩阵**********************"<<endl

cout<<obj1

//cout<<obj

return 0

}

---