數(shù)據(jù)結(jié)構(gòu) 數(shù)組矩陣

1、數(shù)據(jù)結(jié)構(gòu)與算法課程實驗報告 實驗三：稀疏矩陣的壓縮存儲及運算 姓名：沈靖雯 班級：14信息與計算科學(xué)（2）班 學(xué)號：2014326601094實驗三 稀疏矩陣的壓縮存儲及運算【實驗內(nèi)容】 實現(xiàn)稀疏矩陣的壓縮存儲方法以及在特定存儲方法下的基本運算。【實驗?zāi)康摹?掌握數(shù)組的應(yīng)用，包括稀疏矩陣、特殊矩陣的壓縮存儲方法。矩陣的基本運算的實現(xiàn)，包括矩陣相加、轉(zhuǎn)置、乘法等。【問題描述】 （1） 用行邏輯鏈接順序表或十字鏈表分別實現(xiàn)稀疏矩陣的壓縮存儲。（2） 編程實現(xiàn)矩陣的轉(zhuǎn)置運算和乘法運算（運用行邏輯鏈接順序表或十字鏈表作為存儲結(jié)構(gòu)）。【問題實現(xiàn)】（1）抽象數(shù)據(jù)類型ADT RLSMatrix 數(shù)據(jù)對象:

2、數(shù)據(jù)關(guān)系： =Î= - 基本操作： CreateMatrix(*M) 操作結(jié)果：創(chuàng)建稀疏矩陣M。 Trans(M,*T) 初始條件：稀疏矩陣M已存在。 操作結(jié)果：求稀疏矩陣M的轉(zhuǎn)置矩陣T。 Mult(M,N,*T） 初始條件：稀疏矩陣M的列數(shù)等于稀疏矩陣N的行數(shù)。 操作結(jié)果：求稀疏矩陣乘積T=M*N。 Show(M) 初始條件：稀疏矩陣M已存在且非空。 操作結(jié)果：輸出稀疏矩陣M。 ADT RLSMatrix （2）主要實現(xiàn)思路和程序代碼： 1).首先定義抽象數(shù)據(jù)類型，構(gòu)建程序框架； 2).定義稀疏矩陣創(chuàng)建函數(shù)； void CreateMatrix(RLSMatrix *M) 用戶首先

3、輸入矩陣行數(shù)、列數(shù)、非零元個數(shù)后再依次輸入非零元行數(shù)、列數(shù)、值，完成稀疏矩陣創(chuàng)建；scanf("%d %d %d",&M->mu,&M->nu,&M->tu); /判斷行值、列值、元素個數(shù)是否合法 if(M->mu<=0)|(M->nu<=0)|(M->tu<=0)|(M->tu>M->mu*M->nu) printf("輸入有誤！"); int k; printf("請輸入非零元的行坐標(biāo) 列坐標(biāo) 值:n"); for(k=1;k&l

4、t;=M->tu;k+) /輸入稀疏矩陣元素 scanf("%d %d %d",&M->datak.i,&M->datak.j,&M->datak.e); /for 在稀疏矩陣創(chuàng)建函數(shù)中加入num和rpos兩個向量的定義，前者記錄稀疏矩陣每行非零元個數(shù)，后者記錄每行第一個非零元所在矩陣的位置，為后續(xù)矩陣運算函數(shù)所用。if(M->tu) int num1000,t; for(col=1;col<=M->mu;+col) numcol=0; for(t=1;t<=M->tu;+t) +numM->

5、;datat.i; /求出M中每行非零元個數(shù)M->rpos1=1; /求矩陣M第col行第一個非零元在M.data中的位置 for(col=2;col<=M->mu;+col) M->rposcol=M->rposcol-1+numcol-1; 3).定義矩陣轉(zhuǎn)置函數(shù)；int Trans(RLSMatrix M,RLSMatrix *T)快速轉(zhuǎn)置法完成矩陣轉(zhuǎn)置操作：if(T->tu)int q=1,t,p;int num1000; for(col=1;col<=M.nu;+col) numcol=0; for(t=1;t<=M.tu;+t) +n

6、umM.datat.j; /求出M中每列非零元個數(shù)T->rpos1=1; /求矩陣M第col列(=矩陣T第col行)第一個非零元在T.data中的位置 for(col=2;col<=M.nu;+col) T->rposcol=T->rposcol-1+numcol-1; for(p=1;p<=M.tu;+p) col=M.datap.j; q=T->rposcol; T->dataq.i=M.datap.j; T->dataq.j=M.datap.i; T->dataq.e=M.datap.e; +T->rposcol; 4).使用行

7、邏輯鏈接順序表存儲定義矩陣乘積函數(shù)； int Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *T) 規(guī)定矩陣M的列數(shù)等于矩陣N的行數(shù)，方可進行矩陣乘法操作。具體代碼如下：if(M.tu*N.tu!=0)for(arow=1;arow<=M.mu;+arow)int ctemp1000;for(i=1;i<=T->nu;+i)ctempi=0;T->rposarow=T->tu+1;if(arow<M.mu) tp=M.rposarow+1; else tp=M.tu+1; for(p=M.rposarow;p<tp;+p

8、) brow=M.datap.j; if(brow<N.mu) t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow;q<t;+q) ccol=N.dataq.j; ctempccol+=M.datap.e*N.dataq.e; for(ccol=1;ccol<=T->nu;+ccol) if(ctempccol) if(+T->tu>SIZE) return ERROR; T->dataT->tu.i=arow; T->dataT->tu.j=ccol;T->dataT->tu.

9、e=ctempccol; 5).定義矩陣輸出函數(shù)輸出矩陣；void Show(RLSMatrix M)通過雙重循環(huán)，把稀疏矩陣中不為零的元素的行數(shù)、列數(shù)和值顯示出來： for(col=1;col<=M.mu;col+) for(p=1;p<=M.tu;p+) if(M.datap.i=col) printf("%3d %3d %3dn",M.datap.i,M.datap.j,M.datap.e); 6).定義主函數(shù)，總體完成以上所有函數(shù)功能的實現(xiàn)。 程序運行如圖1：圖 1【總結(jié)】 實驗結(jié)果基本實現(xiàn)問題要求。 在實驗調(diào)試過程中主要出現(xiàn)了兩個問題： 1.在定義函數(shù)

10、時一開始照著書上定義矩陣變量，但程序總是報錯；后來直接換成指針才得以解決； 2.在處理矩陣乘積函數(shù)時，函數(shù)測試結(jié)果總是出現(xiàn)問題，經(jīng)過幾次思考發(fā)現(xiàn)是num和rpos在該函數(shù)中不曾定義而直接使用導(dǎo)致問題，為避免重復(fù)定義，故將這兩個向量定義到矩陣創(chuàng)建函數(shù)中（void CreateMatrix(RLSMatrix *M)）才得以解決問題。附件：源代碼：#include <stdio.h> #include <stdlib.h> #define ERROR -1 #define SIZE 12500int col;int ccol,arow,brow;typedef struct

11、 int i,j; / 非零元行下標(biāo)和列下標(biāo) int e; Triple; typedef struct Triple dataSIZE+1; / data0未用 int rposSIZE+1;int mu,nu,tu; /矩陣行數(shù)、列數(shù)、非零元個數(shù) RLSMatrix; /采用三元組順序表存儲表示，創(chuàng)建稀疏矩陣Mvoid CreateMatrix(RLSMatrix *M) scanf("%d %d %d",&M->mu,&M->nu,&M->tu); /判斷行值、列值、元素個數(shù)是否合法 if(M->mu<=0)|(M

12、->nu<=0)|(M->tu<=0)|(M->tu>M->mu*M->nu) printf("輸入有誤！"); int k; printf("請輸入非零元的行坐標(biāo) 列坐標(biāo) 值:n"); for(k=1;k<=M->tu;k+) /輸入稀疏矩陣元素 scanf("%d %d %d",&M->datak.i,&M->datak.j,&M->datak.e); /for if(M->tu) int num1000,t; for(co

13、l=1;col<=M->mu;+col) numcol=0; for(t=1;t<=M->tu;+t) +numM->datat.i; /求出M中每行非零元個數(shù)M->rpos1=1; /求矩陣M第col行第一個非零元在M.data中的位置 for(col=2;col<=M->mu;+col) M->rposcol=M->rposcol-1+numcol-1; /行邏輯順序存儲快速轉(zhuǎn)置 int Trans(RLSMatrix M,RLSMatrix *T)T->mu=M.nu;T->nu=M.mu;T->tu=M.tu

14、;if(T->tu)int q=1,t,p;int num1000; for(col=1;col<=M.nu;+col) numcol=0; for(t=1;t<=M.tu;+t) +numM.datat.j; /求出M中每列非零元個數(shù)T->rpos1=1; /求矩陣M第col列(=矩陣T第col行)第一個非零元在T.data中的位置 for(col=2;col<=M.nu;+col) T->rposcol=T->rposcol-1+numcol-1; for(p=1;p<=M.tu;+p) col=M.datap.j; q=T->rpos

15、col; T->dataq.i=M.datap.j; T->dataq.j=M.datap.i; T->dataq.e=M.datap.e; +T->rposcol; return 0;/求矩陣乘積T=M*N,行邏輯鏈接順序表存儲int Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *T)if(N.mu!=M.nu) return ERROR;T->mu=M.mu;T->nu=N.nu;T->tu=0;int tp,t,p,q,i;if(M.tu*N.tu!=0)for(arow=1;arow<=M.mu;+aro

16、w)int ctemp1000;for(i=1;i<=T->nu;+i)ctempi=0;T->rposarow=T->tu+1;if(arow<M.mu) tp=M.rposarow+1; else tp=M.tu+1; for(p=M.rposarow;p<tp;+p) brow=M.datap.j; if(brow<N.mu) t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow;q<t;+q) ccol=N.dataq.j; ctempccol+=M.datap.e*N.dataq.e; for(

17、ccol=1;ccol<=T->nu;+ccol) if(ctempccol) if(+T->tu>SIZE) return ERROR; T->dataT->tu.i=arow; T->dataT->tu.j=ccol;T->dataT->tu.e=ctempccol; return 0;/輸出矩陣 void Show(RLSMatrix M)/通過雙重循環(huán)，把稀疏矩陣中不為零的元素的行數(shù)、列數(shù)和值顯示出來 int p; for(col=1;col<=M.mu;col+) for(p=1;p<=M.tu;p+) if(M.datap.i=col) printf("%3d %3d %3dn",M.datap.i,M.datap.j,M.datap.e);int main()RLSMatrix M,N,T,Q; printf("請輸入矩陣M的(行數(shù) 列數(shù) 非零元個數(shù))：n");