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

數(shù)據(jù)結(jié)構(gòu)與算法課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三：稀疏矩陣的壓縮存儲(chǔ)及運(yùn)算姓名：班級(jí)：14信息與計(jì)算科學(xué)（2）班學(xué)號(hào)：實(shí)驗(yàn)三稀疏矩陣的壓縮存儲(chǔ)及運(yùn)算【實(shí)驗(yàn)內(nèi)容】實(shí)現(xiàn)稀疏矩陣的壓縮存儲(chǔ)方法以及在特定存儲(chǔ)方法下的基本運(yùn)算?！緦?shí)驗(yàn)?zāi)康摹空莆諗?shù)組的應(yīng)用，包括稀疏矩陣、特殊矩陣的壓縮存儲(chǔ)方法。矩陣的基本運(yùn)算的實(shí)現(xiàn)，包括矩陣相加、轉(zhuǎn)置、乘法等?！締?wèn)題描述】(1)用行邏輯鏈接順序表或十字鏈表分別實(shí)現(xiàn)稀疏矩陣的壓縮存儲(chǔ)。(2)編程實(shí)現(xiàn)矩陣的轉(zhuǎn)置運(yùn)算和乘法運(yùn)算(運(yùn)用行邏輯鏈接順序表或十字鏈表作為存儲(chǔ)結(jié)構(gòu))?！締?wèn)題實(shí)現(xiàn)】(1)抽象數(shù)據(jù)類型ADTRLSMatrix{D={ali=1,2,3，…，m；j=1,2,3，…，n;數(shù)據(jù)對(duì)象：a上eElemSet,m和n分別稱為矩陣行數(shù)和列數(shù)}R={Row，Col}Row={a,a\I1<i<m,1<j<n—1}數(shù)據(jù)關(guān)系： i,ji,j+1/Col={(a,a.)11<i<m-1,1<j<n}基本操作：CreateMatrix(*M)操作結(jié)果：創(chuàng)建稀疏矩陣M。Trans(M,*T)初始條件：稀疏矩陣乂已存在。操作結(jié)果：求稀疏矩陣M的轉(zhuǎn)置矩陣T。Mult(M,N,*T)初始條件：稀疏矩陣M的列數(shù)等于稀疏矩陣N的行數(shù)。操作結(jié)果：求稀疏矩陣乘積T=M*N。Show(M)初始條件：稀疏矩陣乂已存在且非空。操作結(jié)果：輸出稀疏矩陣M。}ADTRLSMatrix(2)主要實(shí)現(xiàn)思路和程序代碼：.首先定義抽象數(shù)據(jù)類型，構(gòu)建程序框架；.定義稀疏矩陣創(chuàng)建函數(shù)；voidCreateMatrix(RLSMatrix*M)用戶首先輸入矩陣行數(shù)、列數(shù)、非零元個(gè)數(shù)后再依次輸入非零元行數(shù)、列數(shù)、值，完成稀疏矩陣創(chuàng)建；scanf("%d%d%d",&M->mu,&M->nu,&M->tu);〃判斷行值、列值、元素個(gè)數(shù)是否合法if((M->mu<=0)||(M->nu<=0)||(M->tu<=0)||(M->tu>M->mu*M->nu))printf("輸入有誤！")；intk;printf("請(qǐng)輸入非零元的行坐標(biāo)列坐標(biāo)值:\n");for(k=1;k<=M->tu;k++){ 〃輸入稀疏矩陣元素scanf("%d%d%d",&M->data[k].i,&M->data[k].j,&M->data[k].e);}//for在稀疏矩陣創(chuàng)建函數(shù)中加入num口和rpos口兩個(gè)向量的定義，前者記錄稀疏矩陣每行非零元個(gè)數(shù)，后者記錄每行第一個(gè)非零元所在矩陣的位置，為后續(xù)矩陣運(yùn)算函數(shù)所用。if(M->tu){intnum[1000],t;for(col=1;col<=M->mu;++col)num[col]=0;for(t=1;t<=M->tu;++t)++num[M->data[t].i];//求出M中每行非零元個(gè)數(shù)M->rpos[1]=1;//求矩陣M第col行第一個(gè)非零元在M.data中的位置for(col=2;col<=M->mu;++col)M->rpos[col]=M->rpos[col-1]+num[col-1];}.定義矩陣轉(zhuǎn)置函數(shù)；intTrans(RLSMatrixM,RLSMatrix*T)快速轉(zhuǎn)置法完成矩陣轉(zhuǎn)置操作：if(T->tu){intq=1,t,p;intnum[1000];for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];//求出M中每列非零元個(gè)數(shù)T->rpos[1]=1;//求矩陣M第col列(=矩陣T第col行)第一個(gè)非零元在T.data中的位置for(col=2;col<=M.nu;++col)T->rpos[col]=T->rpos[col-1]+num[col-1];for(p=1;p<=M.tu;++p){col=M.data[p].j;q=T->rpos[col];T->data[q].i=M.data[p].j;T->data[q].j=M.data[p].i;T->data[q].e=M.data[p].e;++T->rpos[col];).使用行邏輯鏈接順序表存儲(chǔ)定義矩陣乘積函數(shù)；intMult(RLSMatrixM,RLSMatrixN,RLSMatrix*T)規(guī)定矩陣M的列數(shù)等于矩陣N的行數(shù)，方可進(jìn)行矩陣乘法操作。具體代碼如下：if(M.tu*N.tu!=0){for(arow=1;arow<=M.mu;++arow){intctemp[1000];for(i=1;i<=T->nu;++i)ctemp[i]=0;T->rpos[arow]=T->tu+1;if(arow<M.mu)tp=M.rpos[arow+1];elsetp=M.tu+1;for(p=M.rpos[arow];p<tp;++p){brow=M.data[p].j;if(brow<N.mu)t=N.rpos[brow+1];elset=N.tu+1;for(q=N.rpos[brow];q<t;++q){ccol=N.data[q].j;ctemp[ccol]+=M.data[p].e*N.data[q].e;))for(ccol=1;ccol<=T->nu;++ccol)if(ctemp[ccol]){if(++T->tu>SIZE)returnERROR;T->data[T->tu].i=arow;T->data[T->tu].j=ccol;T->data[T->tu].e=ctemp[ccol];)).定義矩陣輸出函數(shù)輸出矩陣；voidShow(RLSMatrixM)通過(guò)雙重循環(huán)，把稀疏矩陣中不為零的元素的行數(shù)、列數(shù)和值顯示出來(lái)：for(col=1;col<=M.mu;col++)for(p=1;p<=M.tu;p++)if(M.data[p].i==col)printf("%3d%3d%3d\n",M.data[p].i,M.data[p].j,M.data[p].e);.定義主函數(shù)，總體完成以上所有函數(shù)功能的實(shí)現(xiàn)。程序運(yùn)行如圖1:"C:\Users\Ashmore\Desktc WSScfree\sh1yansar.exe請(qǐng)輸入矩陣M的工行數(shù)列數(shù)非零元個(gè)數(shù)九344請(qǐng)輸入非零元的行坐標(biāo)列坐標(biāo)值,11314522-1312請(qǐng)輸入矩陣忖的〈行數(shù)列數(shù)非零元個(gè)數(shù)M424請(qǐng)輸入非零元的行坐標(biāo)列坐標(biāo)值二12221131-2324矩陣M113TOC\o"1-5"\h\z14 52 2-13 12矩陣比12 22 113 1-23 2 4矩陣M的轉(zhuǎn)置;11313 22 2-14 15矩陣N小得矩陣必12 62 1-1請(qǐng)fed：鍵全練..【總結(jié)】實(shí)驗(yàn)結(jié)果基本實(shí)現(xiàn)問(wèn)題要求。在實(shí)驗(yàn)調(diào)試過(guò)程中主要出現(xiàn)了兩個(gè)問(wèn)題：.在定義函數(shù)時(shí)一開始照著書上定義矩陣變量，但程序總是報(bào)錯(cuò)；后來(lái)直接換成指針才得以解決；.在處理矩陣乘積函數(shù)時(shí)，函數(shù)測(cè)試結(jié)果總是出現(xiàn)問(wèn)題，經(jīng)過(guò)幾次思考發(fā)現(xiàn)是num口和rpos口在該函數(shù)中不曾定義而直接使用導(dǎo)致問(wèn)題，為避免重復(fù)定義，故將這兩個(gè)向量定義到矩陣創(chuàng)建函數(shù)中(voidCreateMatrix(RLSMatrix*M))才得以解決問(wèn)題。附件：源代碼：#include<stdio.h>#include<stdlib.h>#defineERROR-1#defineSIZE12500intcol;intccol,arow,brow;typedefstruct(inti,j;//非零元行下標(biāo)和列下標(biāo)inte;}Triple;typedefstruct(Tripledata[SIZE+1];//data[0]未用intrpos[SIZE+1];intmu,nu,tu; 〃矩陣行數(shù)、列數(shù)、非零元個(gè)數(shù)}RLSMatrix;〃采用三元組順序表存儲(chǔ)表示，創(chuàng)建稀疏矩陣MvoidCreateMatrix(RLSMatrix*M){scanf("%d%d%d",&M->mu,&M->nu,&M->tu);〃判斷行值、列值、元素個(gè)數(shù)是否合法if((M->mu<=0)||(M->nu<=0)||(M->tu<=0)||(M->tu>M->mu*M->nu))printf("輸入有誤！")；intk;printf("請(qǐng)輸入非零元的行坐標(biāo)列坐標(biāo)值:\n");for(k=1;k<=M->tu;k++){ 〃輸入稀疏矩陣元素scanf("%d%d%d",&M->data[k].i,&M->data[k].j,&M->data[k].e);}//forif(M->tu){intnum[1000],t;for(col=1;col<=M->mu;++col)num[col]=0;for(t=1;t<=M->tu;++t)++num[M->data[t].i];//求出M中每行非零元個(gè)數(shù)M->rpos[1]=1;〃求矩陣M第col行第一個(gè)非零元在M.data中的位置for(col=2;col<=M->mu;++col)M->rpos[col]=M->rpos[col-1]+num[col-1];))〃行邏輯順序存儲(chǔ)快速轉(zhuǎn)置intTrans(RLSMatrixM,RLSMatrix*T){T->mu=M.nu;T->nu=M.mu;T->tu=M.tu;if(T->tu){intq=1,t,p;intnum[1000];for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];//求出M中每列非零元個(gè)數(shù)T->rpos[1]=1;//求矩陣M第col列(=矩陣T第col行)第一個(gè)非零元在T.data中的位置for(col=2;col<=M.nu;++col)T->rpos[col]=T->rpos[col-1]+num[col-1];for(p=1;p<=M.tu;++p){col=M.data[p].j;q=T->rpos[col];T->data[q].i=M.data[p].j;T->data[q].j=M.data[p].i;T->data[q].e=M.data[p].e;++T->rpos[col];))return0;)〃求矩陣乘積T=M*N,行邏輯鏈接順序表存儲(chǔ)intMult(RLSMatrixM,RLSMatrixN,RLSMatrix*T){if(N.mu!=M.nu)returnERROR;T->mu=M.mu;T->nu=N.nu;T->tu=0;inttp,t,p,q,i;if(M.tu*N.tu!=0){for(arow=1;arow<=M.mu;++arow){intctemp[1000];for(i=1;i<=T->nu;++i)ctemp[i]=0;T->rpos[arow]=T->tu+1;if(arow<M.mu)tp=M.rpos[arow+1];elsetp=M.tu+1;for(p=M.rpos[arow];p<tp;++p){brow=M.data[p].j;if(brow<N.mu)t=N.rpos[brow+1];elset=N.tu+1;for(q=N.rpos[brow];q<t;++q){ccol=N.data[q].j;ctemp[ccol]+=M.data[p].e*N.data[q].e;))for(ccol=1;ccol<=T->nu;++ccol)if(ctemp[ccol]){if(++T->tu>SIZE)returnERROR;T->data[T->tu].i=arow;T->data[T->tu].j=ccol;T->data[T->tu].e=ctemp[ccol];)))return0;)〃輸出矩陣voidShow(RLSMatrixM){〃通過(guò)雙重循環(huán)，把稀疏矩陣中不為零的元素的行數(shù)、列數(shù)和值顯示出來(lái)intp;for(col=1;col<=M.mu;col++)for(p=1;p<=M.tu;p++)if(M.data[p].i==col)printf("%3d%3d%3d\n",M.data[p].i,M.data[p].j,M.data[p].e);)intm