實(shí)現(xiàn)效果：
1、編寫程序任意輸入一個(gè)稀疏矩陣，用三元組順序表壓縮存儲(chǔ)稀疏矩陣。
2、對(duì)稀疏矩陣進(jìn)行轉(zhuǎn)置，輸出轉(zhuǎn)置后的矩陣。

實(shí)驗(yàn)?zāi)康?/h2>

對(duì)應(yīng)《數(shù)據(jù)結(jié)構(gòu)(C語言版）》 第5章 數(shù)組與廣義表 實(shí)驗(yàn)：

1、 掌握下三角矩陣的輸入、輸出、壓縮存儲(chǔ)算法；
2、 理解稀疏矩陣的三元組表類型定義
3、 掌握稀疏矩陣的輸入、輸出、轉(zhuǎn)置算法。

---

一、基本概念

o(*￣︶￣*)o請(qǐng)先確保理清一下概念

1.稀疏矩陣

假設(shè)m*n的矩陣中，有t的非零元，令s=t/m * n,當(dāng)，s<=0.05時(shí)，稱此矩陣為稀疏矩陣，簡(jiǎn)單理解就是非零元特別少的矩陣

//一般矩陣a
    1 2 3
 a= 4 5 6
    7 8 9
    
//稀疏矩陣s
    0 0 0 0 0 
    0 2 0 0 5
 s= 0 0 3 0 0
    0 0 0 0 4

2.矩陣轉(zhuǎn)置

矩陣的轉(zhuǎn)置實(shí)際上就是將數(shù)據(jù)元素的行標(biāo)和列標(biāo)互換，即 T(i,j) = M(j,i)

對(duì)應(yīng)三元組的轉(zhuǎn)置

3.快速轉(zhuǎn)置算法

矩陣的轉(zhuǎn)置過程經(jīng)歷了三個(gè)步驟：

• 矩陣的行數(shù) n 和列數(shù) m 的值交換；
• 將三元組中的 i 和 j 調(diào)換；
• 轉(zhuǎn)換之后的表同樣按照行序（置換前的列序）為主序，進(jìn)行排序；【兩者不同之處】

快速轉(zhuǎn)置算法，預(yù)先確定矩陣M中每一列的第一個(gè)非零元在轉(zhuǎn)置的三元組中的位置。

時(shí)間復(fù)雜度由O(nu * tu)提升到O(nu + tu)，尤其是在矩陣的非零元個(gè)數(shù)tu與mu * nu數(shù)量級(jí)越接近時(shí)差別越明顯!

二、完整代碼（附詳細(xì)注釋）

提示：本實(shí)驗(yàn)環(huán)境為VS2019(￣??)

代碼如下（示例）：

//Matrix.cpp
//任意輸入一個(gè)稀疏矩陣，并輸出其轉(zhuǎn)置矩陣
#include <stdio.h>
#include <stdlib.h>
#include "SparseMatrix.h"

void TransposeSMatrix(TSMatrix M, TSMatrix& T);
void FastTransposeSMatrix(TSMatrix M, TSMatrix& T);

int main()
{
    TSMatrix M,T;
    //創(chuàng)建稀疏矩陣
    CreateSMartrix(M);
    PrintSMatrix(M);

    printf("1.普通轉(zhuǎn)置\t2.快速轉(zhuǎn)置\t3.退出\n");
    printf("請(qǐng)選擇對(duì)矩陣的操作：\n");
    int choice = 1;
    while (scanf_s("%d", &choice)) {
        switch (choice) {
        case 1:
            //轉(zhuǎn)置
            TransposeSMatrix(M, T);
            PrintSMatrix(T);
            printf("是否繼續(xù)操作：");
            break;
        case 2:
            //快速轉(zhuǎn)置
            FastTransposeSMatrix(M, T);
            PrintSMatrix(T);
            printf("是否繼續(xù)操作：");
            break;
        default:
            printf("程序結(jié)束");
            exit(0);          
        }
    }
    return 0;
}

//普通轉(zhuǎn)置，按照三元組在轉(zhuǎn)置矩陣中的存儲(chǔ)位置轉(zhuǎn)換
void TransposeSMatrix(TSMatrix M, TSMatrix& T) {
    T.mu = M.mu;//行數(shù)
    T.nu = M.nu;//列數(shù)
    T.tu = M.tu;//非零元的個(gè)數(shù)
    if (T.tu) {
        int q = 1;
        for (int col = 1; col <= M.mu; ++col) {
            for (int p = 1; p <= M.nu; ++p) {
                if (M.data[p].j == 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;
                    ++q;
                }
            }
        }
    }
}

//快速轉(zhuǎn)置，按照三元組在原矩陣中的位置轉(zhuǎn)換
//即預(yù)先確定M中每一列的第一個(gè)元素所在的位置
void FastTransposeSMatrix(TSMatrix M, TSMatrix& T) {
    T.mu = M.mu;//行數(shù)
    T.nu = M.nu;//列數(shù)
    T.tu = M.tu;//非零元的個(gè)數(shù)
    int* num = (int*)malloc(M.nu * sizeof(int));//num[col]表示矩陣M中第col列中的非零元素的個(gè)數(shù)
    int* cpot = (int*)malloc(M.nu * sizeof(int));//cpot[col]指示M中第col列的第一個(gè)非零元素在T的位置
    int q, col;
    if (T.tu) {//當(dāng)矩陣不是零矩陣的時(shí)候執(zhí)行操作
        for (col = 1; col <= M.nu; ++col)
            num[col] = 0;//初始化全部設(shè)置為0
        for (int t = 1; t <= M.tu; ++t)
            ++num[M.data[t].j];//按創(chuàng)建三元組的順序，每列有非零元素時(shí)num加一
        cpot[1] = 1;
        for (col = 2; col <= M.nu; ++col)
            cpot[col] = cpot[col - 1] + num[col - 1];
        for (int p = 1; p <= M.tu; ++p) {
            col = M.data[p].j;
            q = cpot[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;
            ++cpot[col];
        }
    }
}

//SparseMatrix.h
#pragma once
#define MAXSIZE 12500 //非零元最大個(gè)數(shù)

//三元組
typedef struct {
	int i, j;//該元素的行、列
	int e;//該元素的值，此例為整型
}Triple;

//稀疏矩陣
typedef struct {
	Triple data[MAXSIZE + 1];//非零元素三元組，data[0]未用，即矩陣的第一個(gè)元素坐標(biāo)表示為(1,1)
	int mu, nu, tu;//稀疏矩陣的行、列、非零元的個(gè)數(shù)
}TSMatrix;


//創(chuàng)建稀疏矩陣，采用三元組順序壓縮存儲(chǔ)的方式
void CreateSMartrix(TSMatrix& M) {
	printf("請(qǐng)依次輸入矩陣的大小:\n行數(shù)m\t列數(shù)n\t非零元個(gè)數(shù)t\n");
	int m, n, t;
	scanf_s("%d\t%d\t%d", & m, &n, &t);
	M.mu = m;
	M.nu = n;
	M.tu = t;

	printf("請(qǐng)依次輸入矩陣非零元的三元組:\n行坐標(biāo)i\t列坐標(biāo)j\t元素值e\n");
	int i, j, e;
	for (int i = 1; i <= t; i++)
	{
		scanf_s("%d\t%d\t%d", &i, &j, &e);
		M.data[i].i = i;
		M.data[i].j = j;
		M.data[i].e = e;
	}
}

//輸出稀疏矩陣
void PrintSMatrix(TSMatrix M)
{
	printf("------------------------------\n");
	printf("矩陣的三元組表示：\n");
	printf("i\tj\te\n");
	for (int i = 1; i <= M.tu; i++)
	{
		printf("%d\t%d\t%d\n", M.data[i].i, M.data[i].j, M.data[i].e);
	}
	printf("------------------------------\n");
}

題外話

☆*: .?. o(≧▽≦)o .?.:*☆
最近在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)??
也想通過寫文章鍛煉鍛煉自己??
之后會(huì)持續(xù)更新后續(xù)上機(jī)實(shí)驗(yàn)的（暗示??????）
不足的地方希望友友們指正，歡迎和我討論呀??文章來源地址http://www.zghlxwxcb.cn/news/detail-435123.html

到了這里，關(guān)于[數(shù)據(jù)結(jié)構(gòu)(C語言版本)上機(jī)實(shí)驗(yàn)]稀疏矩陣的三元組順序表壓縮存儲(chǔ)以及轉(zhuǎn)置實(shí)現(xiàn)(含快速轉(zhuǎn)置）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！