數(shù)據(jù)結(jié)構(gòu)與算法 特殊矩陣和稀疏矩陣

1、數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo)V2017常熟理工學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)指導(dǎo)與報(bào)告書(shū)_2017-2018_學(xué)年 第_1_ 學(xué)期專(zhuān) 業(yè)： 物聯(lián)網(wǎng)工程 實(shí)驗(yàn)名稱(chēng)： 特殊矩陣和稀疏矩陣 實(shí)驗(yàn)地點(diǎn)： N6-210 指導(dǎo)教師： 聶盼紅 計(jì)算機(jī)科學(xué)與工程學(xué)院2017實(shí)驗(yàn)五 特殊矩陣和稀疏矩陣【實(shí)驗(yàn)?zāi)康摹?、掌握數(shù)組的結(jié)構(gòu)類(lèi)型（靜態(tài)的內(nèi)存空間配置）；通過(guò)數(shù)組的引用下標(biāo)轉(zhuǎn)換成該數(shù)據(jù)在內(nèi)存中的地址；2、掌握對(duì)稱(chēng)矩陣的壓縮存儲(chǔ)表示；3、掌握稀疏矩陣的壓縮存儲(chǔ)-三元組表表示，以及稀疏矩陣的轉(zhuǎn)置算法?！緦?shí)驗(yàn)學(xué)時(shí)】2學(xué)時(shí)【實(shí)驗(yàn)預(yù)習(xí)】回答以下問(wèn)題：1、什么是對(duì)稱(chēng)矩陣？寫(xiě)出對(duì)稱(chēng)矩陣壓縮存儲(chǔ)sak與aij之間的對(duì)應(yīng)關(guān)系。若n階矩陣A中

2、的元素滿(mǎn)足下述性質(zhì)：aij=aji，則稱(chēng)為n階對(duì)稱(chēng)矩陣。sak與矩陣元素aij之間存在著一一對(duì)應(yīng)的關(guān)系： 若i>=j，k=i*(i+1)/2+j; 若i<j，k=j*(j+1)/2+i。 0<=i, j<=n-1 0<=k<=n*(n+1)/2-12、什么是稀疏矩陣？稀疏矩陣的三元組表表示。假設(shè)在m×n的矩陣中，有t個(gè)元素不為零，且tm×n，則稱(chēng)此矩陣為稀疏矩陣。稀疏矩陣的三元組成表示: 矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)【實(shí)驗(yàn)內(nèi)容和要求】1、編寫(xiě)程序exp5_1.c，將對(duì)稱(chēng)矩陣進(jìn)行壓縮存儲(chǔ)。（1）對(duì)稱(chēng)矩陣數(shù)組元素Aij轉(zhuǎn)換成為以行為主的一維數(shù)

3、組sak，請(qǐng)描述k與ij的關(guān)系。（注意C程序中，i，j，k均從0開(kāi)始）（2）調(diào)試程序與運(yùn)行。對(duì)稱(chēng)矩陣存儲(chǔ)下三角部分即i>=j。對(duì)稱(chēng)矩陣為 3,9,1,4,7 9,5,2,5,8 1,2,5,2,4 4,5,2,1,7 7,8,4,7,9參考程序如下：#include<stdio.h>#define N 5int main() int upperNN= 3,9,1,4,7, 9,5,2,5,8, 1,2,5,2,4, 4,5,2,1,7, 7,8,4,7,9 ; /*對(duì)稱(chēng)矩陣*/ int rowMajor15; /*存儲(chǔ)轉(zhuǎn)換數(shù)據(jù)后以行為主的數(shù)組*/ int Index; /*數(shù)

4、組的索引值*/ int i,j; printf("Two dimensional upper triangular array:n"); for (i=0; i<N; i+) /*輸出對(duì)稱(chēng)矩陣*/ for(j=0; j<N; j+) printf("%3d",upperij); printf("n"); for(i=0; i<N; i+) /*進(jìn)行壓縮存儲(chǔ)*/ for(j=0; j<N; j+) if(i>=j) /*下三角元素進(jìn)行存儲(chǔ)*/ Index=i*(i+1)/2+j; /*ij與index的轉(zhuǎn)換

5、*/ rowMajorIndex=upperij; printf("nRow Major one dimensional array:n"); for(i=0; i<15; i+) /*輸出轉(zhuǎn)換后的一維數(shù)組*/ printf("%3d", rowMajori); printf("n"); return 1;2、完成程序exp5_2.c，實(shí)現(xiàn)稀疏矩陣的三元組表存儲(chǔ)及稀疏矩陣的轉(zhuǎn)置。調(diào)試并給出結(jié)果： 補(bǔ)充完整程序，運(yùn)行稀疏矩陣的一般轉(zhuǎn)置算法； 完成稀疏矩陣的快速轉(zhuǎn)置算法，并修改主函數(shù)的轉(zhuǎn)置調(diào)用算法，驗(yàn)證快速轉(zhuǎn)置算法的正確性。exp5

6、_2.c部分代碼如下：#include<stdio.h>#define MAXSIZE 20 /*非零元素個(gè)數(shù)最大值*/typedef int ElemType;typedef struct int i,j; ElemType e;Triple;typedef struct Triple dataMAXSIZE+1; /*三元組表，data0不用*/ int mu,nu,tu;/*矩陣的行數(shù)、列數(shù)、非零元個(gè)數(shù)*/TSMatrix;void TransposeSMatrix(TSMatrix *T,TSMatrix *M);/*一般轉(zhuǎn)置算法*/void FastTransposeSM

7、atrix(TSMatrix *M,TSMatrix *T);/*快速轉(zhuǎn)置算法*/int main() int i,j,k,q,col,p; int temp67=0,12,9,0,0,0,0, /*稀疏矩陣*/ 0,0,0,0,0,0,0, -3,0,0,0,0,14,0, 0,0,24,0,0,0,0, 0,18,0,0,0,0,0, 15,0,0,-7,0,0,0, ; TSMatrix T,M; M.mu=6; M.nu=7; M.tu=0; k=1; for (i=0;i< M.mu;i+) /*轉(zhuǎn)換為稀疏矩陣的三元組表示*/ for (j=0;j< M.nu;j+) i

8、f (tempij!=0) M.datak.i=i+1; M.datak.j=j+1; M.datak.e=tempij; k+; M.tu=k-1; FastTransposeSMatrix(&M,&T); /*調(diào)用轉(zhuǎn)置算法進(jìn)行轉(zhuǎn)置*/ /*輸出轉(zhuǎn)置結(jié)果*/ printf("稀疏矩陣：n"); for (i=0;i< M.mu;i+) /*轉(zhuǎn)換為稀疏矩陣的三元組表示*/ for (j=0;j< M.nu;j+) printf("%3d",tempij); printf("n"); printf("

9、;轉(zhuǎn)置前M三元組表：nmutnuttun"); printf("%dt%dt%dn",M.mu,M.nu,M.tu); printf("nitjten"); for (i=1;i<=M.tu;i+) printf("%dt%dt%dn",M.datai.i,M.datai.j,M.datai.e); printf("轉(zhuǎn)置后T三元組表：nmutnuttun"); printf("%dt%dt%dn",T.mu,T.nu,T.tu); printf("nitjten&quo

10、t;); for (i=1;i<=T.tu;i+) printf("%dt%dt%dn",T.datai.i,T.datai.j,T.datai.e);/*稀疏矩陣的轉(zhuǎn)置*/void TransposeSMatrix(TSMatrix *M,TSMatrix *T) int q,col,p; T->mu=M->nu; T->nu=M->mu; T->tu=M->tu; if (T->tu) q=1; for (col=1;col<=M->nu;+col) for (p=1;p<=M->tu;+p) if

11、 (M->datap.j=col) T->dataq.i=M->datap.j; T->dataq.j=M->datap.i; T->dataq.e=M->datap.e; +q; /*稀疏矩陣的快速轉(zhuǎn)置算法*/void FastTransposeSMatrix(TSMatrix *M,TSMatrix *T) int t,q,col,p,numMAXSIZE,cpotMAXSIZE; T->mu=M->nu; T->nu=M->mu; T->tu=M->tu; if (T->tu) /*快速轉(zhuǎn)置過(guò)程的實(shí)現(xiàn)，請(qǐng)

12、補(bǔ)充代碼*/ for(col=1;col<=M->mu;+col) numcol=0; /num數(shù)組的初始化 for(t=1;t<=M->tu;+t) +numM->datat.j; /求M中每一列的非零元素的個(gè)數(shù) cpot1=1; /求col列中第一個(gè)非零元素在T中序號(hào) for( col=2;col<=M->nu;+col) /求cpot數(shù)組的值 cpotcol=cpotcol-1+numcol-1; for( p=1;p<=M->tu;+p) /進(jìn)行轉(zhuǎn)置 col=M->datap.j; q=cpotcol; T->dataq.i=M-&g