數(shù)據(jù)結(jié)構(gòu)-稀疏矩陣運算器課程設(shè)計

數(shù)據(jù)結(jié)構(gòu)----稀疏矩陣運算器課程設(shè)計數(shù)據(jù)結(jié)構(gòu)----稀疏矩陣運算器課程設(shè)計數(shù)據(jù)結(jié)構(gòu)----稀疏矩陣運算器課程設(shè)計資料僅供參考文件編號：2022年4月數(shù)據(jù)結(jié)構(gòu)----稀疏矩陣運算器課程設(shè)計版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：內(nèi)蒙古科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書題目：稀疏矩陣運算器設(shè)計學(xué)生姓名：學(xué)號：專業(yè)：計算機科學(xué)與技術(shù)班級：計09-1班指導(dǎo)教師：劉月峰2011年6月24日稀疏矩陣運算器設(shè)計摘要摘要：設(shè)計一稀疏矩陣運算器。實現(xiàn)轉(zhuǎn)置，相加，相乘的功能。用“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實現(xiàn)兩個矩陣相轉(zhuǎn)置、相加和相乘的運算，采用分級的設(shè)計方法，分別設(shè)計出轉(zhuǎn)置、加、乘運算器的子程序，相加運算時只要依次掃描兩矩陣的行號和列號，若相等則相加后存入結(jié)果矩陣，不等時則存入較小的。相減運算與相加運算相同，同樣比較兩矩陣的行號和列號，只是不等時，若第一個小，則存入第一個的元素，若第二個小，則存入其相反數(shù)。相乘運算要先判斷兩矩陣能否相乘。通過給頂?shù)男刑柡土刑栒页鲈仃噷?yīng)的元素值。當(dāng)在三元組表示中找到時返回其元素值，找不到時，說明該位置為0，因此返回0。然后利用該函數(shù)計算出C的行號i和列號j處的元素值，若該值不為0，則存入矩陣，否則不存入。通過實驗表明本程序能夠進行稀疏矩陣的相加，相減，相乘運算。具備矩陣的加、減、乘功能。關(guān)鍵詞：轉(zhuǎn)置運算器；相加運算器；相乘運算器目錄16973稀疏矩陣運算器設(shè)計 I31887摘要 II11961第一章需求分析 18345第二章概要設(shè)計 228752第三章設(shè)計步驟 6函數(shù)說明 6設(shè)計步驟 711961第四章設(shè)計理論分析方法 20算法一：矩陣轉(zhuǎn)置 20算法二：矩陣加法 20算法三：矩陣乘法 2111961第五章程序調(diào)試 2311961第六章心得體會 2511961參考文獻 26第一章需求分析稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點進行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。實現(xiàn)一個能進行稀疏矩陣基本運算的運算器。以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實現(xiàn)矩陣轉(zhuǎn)置，求逆，實現(xiàn)兩個矩陣相加、相減和相乘的運算。稀疏矩陣的輸入形式采用三元組表示，而運算結(jié)果的矩陣則以通常的陣列形式列出。演示程序以用戶和計算機的對話方式執(zhí)行，數(shù)組的建立方式為邊輸入邊建立。由題目要求可知：首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個矩陣的行、列數(shù)對于所要求作的運算是否相匹配。程序可以對三元組的輸入順序不加以限制；根據(jù)對矩陣的行列，三元組作直接插入排序，從而進行運算時,不會產(chǎn)生錯誤。在用三元組表示稀疏矩陣時，相加、乘積和相減所得結(jié)果矩陣應(yīng)該另生成；矩陣求逆時，為了算法方便，使用二維數(shù)組存放。程序在環(huán)境下設(shè)計。程序執(zhí)行的命令為：1.稀疏矩陣轉(zhuǎn)置;2.稀疏矩陣加法;;3.稀疏矩陣乘法;4.退出的工作。第二章概要設(shè)計抽象數(shù)據(jù)類型稀疏矩陣的定義如下：ADTSparseMatrix{數(shù)據(jù)對象：D={aij|i=1,2,…,m;j=1,2,…,n;aij∈ElemSet,m和n分別為矩陣的行數(shù)和列數(shù)}數(shù)據(jù)關(guān)系：R={Row,Col}Row={﹤ai,j,ai,j+1﹥|1≤i≤m,1≤j≤n-1}Col={﹤ai,j,ai+1,j﹥|1≤i≤m-1,1≤j≤n}基本操作：create(TSMatrix&TM)操作結(jié)果：創(chuàng)建稀疏矩陣矩陣TMLocateELem(TSMatrixM,inti,intj,inte)初始條件：稀疏矩陣M存在操作結(jié)果：稀疏矩陣中是否存在非零元素A[i][j]，若存在返回edisp(TSMatrixTM)初始條件：稀疏矩陣TM存在操作結(jié)果：通常形式輸出稀疏矩陣InsertSortMatrix(TSMatrix&TM)初始條件：稀疏矩陣TM存在操作結(jié)果：根據(jù)對矩陣的行列，三元組TM作直接插入排序TransposeSMatrix(TSMatrixM,TSMatrix&T)初始條件：稀疏矩陣M和T存在操作結(jié)果：求稀疏矩陣M轉(zhuǎn)置的稀疏矩陣TAddTSM(TSMatrixA,TSMatrixB,TSMatrix&C)初始條件：稀疏矩陣A，B和C存在操作結(jié)果：稀疏矩陣的加法運算:C=A+BSubTSM(TSMatrixA,TSMatrixB,TSMatrix&C)初始條件：稀疏矩陣A，B和C存在操作結(jié)果：稀疏矩陣的減法運算:C=A-BMultSMatrix(TSMatrixA,TSMatrixB,TSMatrix&C)初始條件：稀疏矩陣A，B和C存在操作結(jié)果：稀疏矩陣的乘法運算:C=A×BNiMatrix(TSMatrix&TM)初始條件：稀疏矩陣TM存在操作結(jié)果：稀疏矩陣求逆}ADTSparseMatrix;2.主程序：voidmain(){初始化；do{接受命令；選擇處理命令；}while(命令！=“退出”)}3.本程序有四個模塊，調(diào)用關(guān)系如下：主程序模塊主程序模塊 矩陣輸入模塊矩陣輸入模塊矩陣運算模塊矩陣運算模塊 矩陣輸出模塊矩陣輸出模塊 圖4本程序的流程圖開始開始選擇要執(zhí)行的操作作選擇要執(zhí)行的操作作選擇4，退出程序選擇2，進行矩陣加法運算選擇1，進行矩陣轉(zhuǎn)置運算選擇3，進行矩陣乘法運算 選擇4，退出程序選擇2，進行矩陣加法運算選擇1，進行矩陣轉(zhuǎn)置運算選擇3，進行矩陣乘法運算輸入n個矩陣A的行數(shù)、列數(shù)、非零元個數(shù)輸入n個矩陣A的行數(shù)、列數(shù)、非零元個數(shù)輸出結(jié)果輸出結(jié)果結(jié)束結(jié)束圖設(shè)計步驟函數(shù)說明稀疏矩陣的三元組順序表存儲表示：typedefstruct>>[k].j>>[k].v;}輸出矩陣：intc[100][100]={0};for(k=1;k<=;k++){c[[k].i][[k].j]=[k].v;}cout<<"轉(zhuǎn)置（加法，乘法）結(jié)果為："<<endl;for(k=1;k<=;k++){for(intl=1;l<=;l++)cout<<c[k][l]<<"";cout<<endl;}} 轉(zhuǎn)置矩陣：voidtripletable::convert()>>[k].j>>[k].v;}=;=;=;if{intq=1,col;for(col=1;col<=;++col)for(intp=1;p<=;++p)if[p].j==col){[q].i=[p].j;[q].j=[p].i;[q].v=[p].v;++q;}}intshuru[100][100]={0};for(k=1;k<=;k++){shuru[[k].j][[k].i]=[k].v;}cout<<"輸入為："<<endl;for(k=1;k<=;k++){for(intl=1;l<=;l++) cout<<shuru[k][l]<<"";cout<<endl;}intresult[100][100]={0};for(k=1;k<=;k++){result[[k].i][[k].j]=[k].v;}cout<<"結(jié)果為："<<endl;for(k=1;k<=;k++){for(intl=1;l<=;l++)cout<<result[k][l]<<"";cout<<endl;}}以上主要設(shè)計思想：通過三元組輸入一個矩陣A，為了找到A的每一列中所有非零元素，需要對其三元組表從第一行起整個掃描一遍，由于是以A的行序為主序來存放每個非零元的，由此得到的恰是的應(yīng)有的順序。加法矩陣：voidtripletable::add()>>[k].j>>[k].v;}cout<<"輸入稀疏矩陣B的行數(shù)，列數(shù)和非零元個數(shù)：";cin>>>>>>;for(k=1;k<=;k++){printf("輸入第%d個非0元素的行數(shù)，列數(shù)和值:",k);cin>>[k].i>>[k].j>>[k].v;}if!=||!={cout<<"輸入錯誤：A與B的行數(shù)或列數(shù)不相同，請重新輸入"<<endl;return;}inta[100][100]={0};for(k=1;k<=;k++){a[[k].i][[k].j]=[k].v;}cout<<"A輸入為："<<endl;for(k=1;k<=;k++){for(intl=1;l<=;l++)cout<<a[k][l]<<"";cout<<endl;}intb[100][100]={0};for(k=1;k<=;k++){b[[k].i][[k].j]=[k].v;}cout<<"B輸入為："<<endl;for(k=1;k<=;k++){for(intl=1;l<=;l++)cout<<b[k][l]<<"";cout<<endl;}intc[100][100]={0};for(k=1;k<=;k++){for(intl=1;l<=;l++){c[k][l]=a[k][l]+b[k][l];}}cout<<"加法結(jié)果C為："<<endl;for(k=1;k<=;k++){for(intl=1;l<=;l++)cout<<c[k][l]<<"";cout<<endl;}}以上主要設(shè)計思想：此功能由函數(shù)add()實現(xiàn)，當(dāng)用戶選擇該功能時系統(tǒng)即提示用戶初始化要進行加法的兩個矩陣的信息。然后檢測這兩個矩陣是否符合矩陣相加的規(guī)則，如果符合，進行加法。否則重新輸入第二個矩陣來保證兩個矩陣可以相加。最后輸出結(jié)果。乘法矩陣：voidtripletable::multi()>>[k].j>>[k].v;}introw=1;for(k=1;k<=;k++){while(row<=[k].i){[row++]=k;}}while(row<=[row++]=+1;cout<<"輸入稀疏矩陣B的行數(shù)，列數(shù)和非零元個數(shù)：";cin>>>>>>;for(k=1;k<=;k++){printf("輸入第%d個非0元素的行數(shù)，列數(shù)和值:",k);cin>>[k].i>>[k].j>>[k].v;}row=1;for(k=1;k<=;k++){while(row<=[k].i){[row++]=k;}}while(row<=[row++]=+1;if!={cout<<"輸入錯誤：A的列數(shù)不等于B的行數(shù)，請重新輸入"<<endl;return;}=;=;=0;intarow,p,q,ccol,t,tp;if*!=0){for(arow=1;arow<=;++arow){intctemp[maxsize]={0};[arow]=+1;if(arow<{tp=[arow+1];}else{tp=+1;}for(p=[arow];p<tp;++p){intbrow=[p].j;if(brow<{t=[brow+1];}else{t=+1;}for(q=[brow];q<t;++q){ccol=[q].j;ctemp[ccol]+=[p].v*[q].v;}}for(ccol=1;ccol<=;++ccol){if(ctemp[ccol]){if(++>maxsize)return;[].i=arow;[].j=ccol;[].v=ctemp[ccol];}}}}inta[100][100]={0};for(k=1;k<=;k++){a[[k].i][[k].j]=[k].v;}cout<<"A輸入為：";cout<<endl;for(k=1;k<=;k++){for(intl=1;l<=;l++)cout<<a[k][l]<<"";cout<<endl;}intb[100][100]={0};for(k=1;k<=;k++){b[[k].i][[k].j]=[k].v;}cout<<"B輸入為："<<endl;for(k=1;k<=;k++){for(intl=1;l<=;l++)cout<<b[k][l]<<"";cout<<endl;}intc[100][100]={0};for(k=1;k<=;k++){c[[k].i][[k].j]=[k].v;}cout<<"乘法結(jié)果C為："<<endl;for(k=1;k<=;k++){for(intl=1;l<=;l++)cout<<c[k][l]<<"";cout<<endl;}}以上主要設(shè)計思想為：此功能由函數(shù)multi()實現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)提示輸入要進行相乘的兩個矩陣的詳細信息。然后檢測兩者是否可以相乘，如果不能，則重新初始化第二個矩陣。先對矩陣B進行逐行處理，先求得累計求和的中間結(jié)果（C的每一行），然后再壓縮存儲到中去，最后得到結(jié)果。第四章 設(shè)計理論分析方法算法一：矩陣轉(zhuǎn)置轉(zhuǎn)置運算時一種最簡單的矩陣運算，對于一個m*n的矩陣M，他的轉(zhuǎn)置矩陣T是一個n*m的矩陣，且T（i，j）=M（j，i），1<=i<=n,1<=j<=m。顯然，一個稀疏矩陣的轉(zhuǎn)置矩陣仍然是稀疏矩陣。(1)將矩陣的行列值相互交換;(2)將每個三元組中的i和j相互調(diào)換；（3）重排三元組之間的次序便可實現(xiàn)矩陣的轉(zhuǎn)置。一般矩陣轉(zhuǎn)置算法為for(col=1;col<=nu;++col)for(row=1;row<=mu;++row)T[col][row]=M[row][col];按照中三元組的次序進行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入b中恰當(dāng)?shù)奈恢?。在此，需要附設(shè)num和cpot兩個向量。Num[col]表示矩陣M中第col列中非零元的個數(shù)，cpot[c