?? 稀疏矩陣運算.cpp
字號:
// 稀疏矩陣.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include<malloc.h>
#include<iostream.h>
#define OVERFLOW -1
#define ERROR 0
#define OK 1
#define MAXSIZE 10000
#define MAXRC 100
typedef int ElemType;
typedef struct
{
int i;
int j;
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int rpos[MAXRC+1];
int mu;
int nu;
int tu;
}RLSMatrix;
//三元組的存儲結構
void CreateSMatrix(RLSMatrix &M,int m,int n)
{
//按輸入的矩陣非零元建立以三元組存儲的稀疏矩陣
cout<<"輸入矩陣的值"<<endl;
M.tu=0;
int k=1;
int p=1;
int num[100];
int i,j;
ElemType e;
M.mu=m; //傳遞矩陣的行列數
M.nu=n;
for(int z=1;z<=100;z++)num[z]=0;
for(cin>>i>>j>>e;i!=0;cin>>i>>j>>e)
{//按任意次序輸入非零元
M.data[k].j=j;
M.data[k].i=i;
M.data[k].e=e;
k++;
}//for
M.tu=k-1;
M.rpos[1]=1;
for(int a=1;a<=M.tu;++a)++num[M.data[a].i];
for(int b=2;b<=M.mu;++b)M.rpos[b]=M.rpos[b-1]+num[b-1];
//初始化矩陣的行鏈接信息
}//CreateSMatrix
bool MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)
{
//進行兩個矩陣相乘操作，并把結果壓縮存入新矩陣Q
int ctemp[100];
int tp,t,ccol,brow,p,q,arow,lie;
if(M.nu!=N.mu)return ERROR;
Q.mu=M.mu;
Q.nu=N.nu;
Q.tu=0;
//Q初始化
if(M.tu*N.tu!=0)
{
for(arow=1;arow<=M.mu;++arow)
{//處理M的每一行
int w=arow;
for(lie=1;lie<=N.nu;++lie)
ctemp[lie]=0; //當前行個元素累加器清零
Q.rpos[arow]=Q.tu+1;
if(arow<M.mu)tp=M.rpos[arow+1];
else {tp=M.tu+1;}
for(p=M.rpos[arow];p<tp;++p)
{
//對當前行中的每一個非零元找到對應元在N中的行號
brow=M.data[p].j;
if(brow<N.mu)t=N.rpos[brow+1];
else {
t=N.tu+1;
}//else
for(q=N.rpos[brow];q<t;++q)
{
ccol=N.data[q].j; //乘積元素在Q中列號
ctemp[ccol]+=M.data[p].e*N.data[q].e;
}//for q;
}//for p;求得Q中第crow（＝arow）行的非零元
//壓縮存儲存儲該行的非零元
for(ccol=1;ccol<=Q.nu;++ccol)
if(ctemp[ccol])
{
Q.tu++;
if(Q.tu>MAXSIZE)return ERROR;
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
Q.data[Q.tu].e=ctemp[ccol];
}//if
}//for arow
}//if
return OK;
}//MultSMatrix
void Rmove(RLSMatrix &M,int p)
{//矩陣中非零元后移
for(int a=M.tu+1;a>=p;a--)
{
M.data[a].e=M.data[a-1].e;
M.data[a].i=M.data[a-1].i;
M.data[a].j=M.data[a-1].j;
}
}
void Lmove(RLSMatrix &M,int p)
{//矩陣中非零元左移
for(int a=p;a<M.tu;a++)
{
M.data[a].e=M.data[a+1].e;
M.data[a].i=M.data[a+1].i;
M.data[a].j=M.data[a+1].j;
}
}
bool PlusSMatrix(RLSMatrix &M,RLSMatrix N)
{
//進行兩個矩陣的相加，即把第二個矩陣加到第一個矩陣上，如果在對應項上沒有元素則插入，
//如果相加為零
//則在第一個矩陣中刪除原來的元素
int tp,t,p,q,arow,e;
if(M.mu!=N.mu&&M.nu!=N.nu)return ERROR;
if(M.tu*N.tu!=0) //兩個矩陣都為非零矩陣
{
for(arow=1;arow<=M.mu;++arow)
{//逐行計算
if(arow<M.mu)
{
tp=M.rpos[arow+1];
t=N.rpos[arow+1];
}
else
{tp=M.tu+1;
t=N.tu+1;
}
for(p=M.rpos[arow],q=M.rpos[arow];p<tp||q<t;)
{
if(p==tp) //第一個矩陣當前行是否還存在非零元
{Rmove(M,p);
M.data[p].e=N.data[q].e;
M.data[p].i=N.data[q].i;
M.data[p].j=N.data[q].j;
M.tu++;q++;
}
if(q==t)p++; //第二個矩陣當前行是否還存在非零元
int a=M.data[p].j;
int b=N.data[q].j;
if(a<b)p++;
else if(a>b)
{Rmove(M,p); //插入第二個矩陣對應位置上第一個矩陣沒有的元素
M.data[p].e=N.data[q].e;
M.data[p].i=N.data[q].i;
M.data[p].j=N.data[q].j;
M.tu++;
}
else
{e=M.data[p].e+N.data[q].e; //相加
M.data[p].e=e;
p++;
q++;}//else
}//for q,p
}//for arow
}//if
return OK;
}
void PrintSMatrix(RLSMatrix M)
{
//以陣列形式打印矩陣
ElemType Search(RLSMatrix ,int ,int);
for(int i=1;i<=M.mu;i++)
{for(int j=1;j<=M.nu;j++)
{ElemType e=Search(M,i,j);
printf("%d ",e);}
cout<<endl;}
}
void SubN(RLSMatrix &N)
{
for(int i=1;i<=N.tu;i++)
N.data[i].e=-N.data[i].e;
}
bool SubSMatrix(RLSMatrix &M,RLSMatrix N)
{//進行兩個矩陣的相減，這個算法是把第二個矩陣的非零元都乘上-1后加到第一個矩陣上
SubN(N);
if(PlusSMatrix(M,N))return 1;
else return 0;
}
ElemType Search(RLSMatrix M,int i,int j)
{
//查找矩陣中的非零元
for(int k=1;k<=M.tu;k++)
if(M.data[k].i==i&&M.data[k].j==j)
return M.data[k].e;
return 0;
}
void main(int argc, char* argv[])
{
RLSMatrix M,N,Q;
int m,n;
char d='y';
cout<<"歡迎用本程序進行矩陣運算!"<<endl;
loop:
{
cout<<"請輸入第一個矩陣，先輸入行數m再輸入列數n"<<endl;
cout<<"m=";
cin>>m;
cout<<"n=";
cin>>n;
CreateSMatrix(M,m,n);
//建立第一個矩陣
cout<<"第一個矩陣如下，請校對："<<endl;
PrintSMatrix(M);
cout<<"請輸入第二個矩陣，先輸入行數m再輸入列數n"<<endl;
cout<<"m=";
cin>>m;
cout<<"n=";
cin>>n;
CreateSMatrix(N,m,n);
//建立第二個矩陣
cout<<"第二個矩陣如下，請校對："<<endl;
PrintSMatrix(N);
cout<<"請選擇矩陣運算的類型："<<endl;
cout<<"(A)加法"<<endl<<"(B)減法"<<endl<<"(C)乘法"<<endl;
char c;
cin>>c;
switch (c)
{case 'a'://調用矩陣相加函數，并輸出計算結果
if(PlusSMatrix(M,N))
{cout<<"M+N的結果為："<<endl;PrintSMatrix(M);}
else {cout<<"輸入矩陣行列數不相等,請重新輸入"<<endl;
goto loop;}break;
case 'b'://調用矩陣相減函數，并輸出計算結果
if( SubSMatrix(M,N)){
cout<<"M-N的結果為："<<endl;
PrintSMatrix(M);}
else {cout<<"輸入矩陣行列數不相等,請重新輸入"<<endl;
goto loop;}break;
case 'c'://調用矩陣相乘函數，并輸出計算結果
if( MultSMatrix(M,N,Q)){
cout<<"運算結果為："<<endl;
PrintSMatrix(Q);
}
else {cout<<"第一個矩陣的列數不等于第二個矩陣的行數,請重新輸入"<<endl;
goto loop;}break;}
cout<<"Do you want to continue(Y/N)?"<<endl;
if(cin.get()=='Y'||cin.get()=='y') goto loop;
}
cout<<"press any key to contine:"<<endl;
cin.get();
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -