Rất nhiều bài toán trong kỹ thuật sử dụng các phép toán trên ma trận, đặc biệt là các loại ma trận có cấu trúc và ma trận thưa (sparse matrix). Ma trận thưa là loại ma trận (thông thường) có kích thước lớn nhưng phần lớn các phần tử là 0. Khi đó để tiết kiệm dung lượng và tăng tốc độ tính toán, người ta thường có cách lưu trữ và các thực hiện các phép toán dành riêng cho ma trận thưa.
a. Hãy xây dựng cách lưu trữ dữ liệu cho ma trận thưa. Thể hiện bằng một struct trong C (*) có chứa kích cỡ của ma trận, vị trí các phần tử khác không và giá trị của chúng.
b. Từ kiểu dữ liệu đã xây dựng, thực hiện phép nhân ma trận với một vector cột (vector này không phải là vector thưa).
c. Tối ưu hóa? (Làm thế nào để có cách lưu trữ dữ liệu tốn ít dung lượng nhất và thực hiện phép toán trên với ít phép cộng + phép nhân nhất?)
d. (**) Thực hiện phép nhân ma trận ADA' trong đó D là ma trận đường chéo, A' là chuyển vị của A
(*) Có thể thay bằng Object trong C++
Nhận xét: Để lưu trữ ma trận thưa chúng ta có thể dùng nhiều cấu trúc dữ liệu khác nhau, nhưng để lưu trữ ma trận thưa sao cho tiết kiệm bộ nhớ nhất ta dùng danh sách liên kết để lưu trữ.Chỉ lưu những phần tử có giá trị khác ‘0’, do vậy nên ta không mất bộ nhớ để lưu trữ những phần tử có giá trị bằng ‘0’.Bài làm dưới đây sử dụng danh sách liên kết để lưu trữ ma trận thưa.
Phần Code: Sử dụng Object trong C++
#include<iostream>
using namespace std;
//---------------- Sparse matrix -------------------//
//---- struct Node -----//
struct Node
{
Node*nextrow; // Con trỏ nextrow trỏ tới hàng tiếp theo
Node*nextcol; // Con trỏ nextcol trỏ tới cột tiếp theo
int row;
int col;
double value;
};
//-----class sparse_matrix--------//
class sparse_matrix
{
private:
Node**rowhead;
Node**colhead;
int rows; // Số hàng của ma trận
int cols; // Số cột của ma trận
public:
// ------ Constructor -------//
sparse_matrix(int x,int y);
public:
void insert_remove(int row,int col,double value);// Hàm chèn hoặc xóa một Node //
void multiply(sparse_matrix a); // Nhân hai ma trận
void mul(int**&A,int m,int n);
void display(); // Hàm hiển thị ma trận
};
//------- End of Class----------///
sparse_matrix::sparse_matrix(int x, int y) //---- Constructor-----//
{
rows=x;
cols=y;
rowhead=new Node*[x];// Con trỏ trỏ tới một mảng gồmm x phần tử
colhead=new Node*[y];// Con trỏ trỏ tới một mảng gồm y phần tử
for(int i=0;i<x;i++)
{
rowhead[i]=new Node;
rowhead[i]->nextcol=NULL;
rowhead[i]->row=i;
}
for(int j=0;j<y;j++)
{
colhead[j]=new Node;
colhead[j]->nextrow=NULL;
colhead[j]->col=j;
}
}
// --------- Hàm chèn hoặc xóa 1 phần tử----------//
void sparse_matrix::insert_remove(int row,int col,double value)
{
Node *lead, *point, *pre_point;
if(value==0) // Xóa nếu phần tử có giá trị bằng 0
{
point=rowhead[row-1]->nextcol;
pre_point=rowhead[row-1];
while(point!=NULL)
{
if((point->row==row)&&(point->col==col))
{
pre_point->nextcol=point->nextcol;
}
pre_point=point;
point=point->nextcol;
}
point=colhead[col-1]->nextrow;
pre_point=colhead[col-1];
while(point!=NULL)
{
if((point->row==row)&&(point->col==col))
{
pre_point->nextrow=point->nextrow;
}
pre_point=point;
point=point->nextrow;
}
}
else //// Value != 0 ta chen phần tử vào ma trận
{
lead = new Node;
lead->row=row;
lead->col=col;
lead->value=value;
lead->nextrow=NULL;
lead->nextcol=NULL;
// Hàng có phần tử bị xóa //
point=rowhead[row-1]->nextcol;
if(rowhead[row-1]->nextcol==NULL)
{
rowhead[row-1]->nextcol=lead;
}
else
{
pre_point=rowhead[row-1];
while((point->nextcol!=NULL)&&(point->col < col))
{
pre_point=point;
point=point->nextcol;
}
if(point->col > col)
{
pre_point->nextcol=lead;
lead->nextcol=point;
}
else
if(point->col < col)
{
point->nextcol=lead;
}
else
if(point->col==col)
{
pre_point->nextcol=lead;
lead->nextcol=point->nextcol;
}
}
// Cột có phần tử bị xóa //
point=colhead[col-1]->nextrow;
if(colhead[col-1]->nextrow==NULL)
colhead[col-1]->nextrow=lead;
else
{
pre_point=colhead[col-1];
while((point->nextrow!=NULL)&&(point->row < row))
{
pre_point=point;
point = point->nextrow;
}
if(point->row > row)
{
pre_point->nextrow=lead;
lead->nextrow=point;
}
else
if(point->row < row)
{
point->nextrow = lead;
}
else
if(point->row==row)
{
pre_point->nextrow=lead;
lead->nextrow=point->nextrow;
}
}
}
}// Kết thúc hàm
//---------------Hàm nhân 2 ma trận thưa------------------- //
void sparse_matrix::multiply(sparse_matrix a)
{
Node *lead1, *lead2;
int m,n,k;
double sum;
m=rows;
n=a.cols;
if(cols!=a.rows)
{
cout<<"Khong thoa man dieu kien nhan hai ma tran."<<endl;
exit(0);
}
sparse_matrix c(m,n); // Tạo ma trận tích //
for(int i=0;i<m;i++)
{
if(rowhead[i]->nextcol!=NULL)
for(k=0;k<n;k++)
{
sum=0;
lead1=rowhead[i]->nextcol;
while(lead1!=NULL)
{
lead2=colhead[k]->nextrow;
while(lead2!=NULL)
{
if(lead1->col==lead2->row)
sum+=lead1->value*lead2->value;
lead2=lead2->nextrow;
}
lead1=lead1->nextcol;
}
if(sum!=0)
c.insert_remove(i+1,k+1,sum);
}
}
}// Kết thúc hàm
//------ Nhân ma trận thưa với ma trận A(không là ma trận thưa) có m hàng, n cột---------//
void sparse_matrix::mul(int **&A, int m, int n)
{
Node*lead;
double sum;
int k,j;
cout<<"Nhap vao ma tran A:"<<endl;
A=new int*[m];
for(int i=0;i<m;i++)
{
A[i]=new int [n];
for(int j=0;j<n;j++)
{
cout<<"A["<<i<<" , "<<j<<"]=";cin>>A[i][j];
}
}
if(cols!=m)
{
cout<<"Khong thoa man dieu kien nhan 2 ma tran.";
exit(0);
}
sparse_matrix c(rows,n);// Ma tran tich
for(int i=0;i<rows;i++)
{
if(rowhead[i]->nextcol!=NULL)
{
for(j=0;j<n;j++)
{
sum=0;
lead=rowhead[i]->nextcol;
for(k=0;k<m,lead!=NULL;k++)
{
if(lead->col==k)
{
sum+=lead->value*A[k][j];
}
lead=lead->nextcol;
}
if(sum!=0) c.insert_remove(i+1,j+1,sum);
}
}
}
}// Kết thúc hàm.
class Element
Trả lờiXóa{
public:
//Friend function
Element (); // default constructor
Element (int,int,int); //Constructor
~Element(); //Destructor
Element (const Element&); //Copy constructor
//Some assessor functions
int getRow() const;
int getCol() const;
int getValue() const;
//Mutuator
void set(int,int,int);
//Print out the object
void printElement() const;
private:
int row, col, value;
};
struct Node;
typedef Node* NodePtr;
struct Node
{
Element e;
NodePtr next;
};
//**************************************************************************
class SparseMatrix
{
public:
//Default constructor
SparseMatrix ();
//Destructor
~SparseMatrix ();
//Copy constructor
SparseMatrix (const SparseMatrix&);
void Construct_Matrix();
void Insert(int);
bool Delete(int,int);
void printList() const;
int Search(int,int,int,NodePtr&,NodePtr&);
int compare(int,int,int,int);
NodePtr getNode(Element&,int, int,int);
private:
NodePtr head,tail;
Element e;
};
Anh oi em co 2 class nay` , de bai` yeu cau su dung 2 class de tao sparse matrix , nhap vao n , se insert n phan tu , so row and col la unique *ko dc giong nhau, anh giup em voi.