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

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