數(shù)據(jù)結(jié)構(gòu)·練習(xí)·稀疏矩陣的快速轉(zhuǎn)置
一、問題描述
一個(gè)mxn的矩陣A，它的轉(zhuǎn)置矩陣B是一個(gè)nxm矩陣，且A[i][j]=B[j][i]，0<=i<=m-1，0<=j<=n-1，即A的行是B的列，A的列是B的行。
用三元組表對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，再進(jìn)行時(shí)間復(fù)雜度O(n)的快速轉(zhuǎn)置，最后輸出稀疏矩陣。
其中m=4,n=5
二、算法概述
1、問題分析
1）壓縮
2）轉(zhuǎn)置
3）解壓
2、算法描述
- 用三元組表壓縮存儲(chǔ)稀疏矩陣；
- 用向量num[]表示矩陣A每列的非零元素個(gè)數(shù)，用向量start[]表示矩陣A每列的第一個(gè)非零元素在矩陣B中的位置;
- 遍歷三元組表Atriple，根據(jù)向量num[]和向量start[]將元素逐個(gè)放入三元組表Btriple的相應(yīng)位置；
- 解壓三元組表Btriple得到稀疏矩陣B。
三、輸入說明
一行輸入m和n,換行輸入一個(gè)mxn稀疏矩陣A
四、輸出說明
輸出一個(gè)nxm稀疏矩陣B
輸入樣例：
4 5
0 5 0 0 8
1 0 3 0 0
0 -2 0 0 0
6 0 0 0 0
輸出樣例：
0 1 0 6
5 0 -2 0
0 3 0 0
0 0 0 0
8 0 0 0文章來源：http://www.zghlxwxcb.cn/news/detail-442507.html
五、程序?qū)崿F(xiàn)文章來源地址http://www.zghlxwxcb.cn/news/detail-442507.html
#include<stdio.h>
/*定義三元組表*/
typedef struct
{
int i;//行標(biāo)
int j;//列標(biāo)
int elem;//內(nèi)容
}triple;
typedef struct
{
triple data[M];
int m;//被存儲(chǔ)矩陣的行
int n;//被存儲(chǔ)矩陣的列
int len;//三元組表長(zhǎng)度
} triplematrix;
/*主函數(shù)*/
int main()
{
int i=0,j=0,i1=0,j1=0,k=0,l=0,sum&#到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)·練習(xí)·三元組表法實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu)(C語言版本)上機(jī)實(shí)驗(yàn)]稀疏矩陣的三元組順序表壓縮存儲(chǔ)以及轉(zhuǎn)置實(shí)現(xiàn)(含快速轉(zhuǎn)置）](https://imgs.yssmx.com/Uploads/2024/02/435123-1.png)
