C語言使用亂數生成矩陣，實作三元組的快速轉置。

稀疏矩陣壓縮及轉置

1、亂數生成矩陣演算法思想：使用time()函式給亂數播種，獲得矩陣的總行數，總列數，非零元個數，總行數與總列數的值可直接存入三元組，每次生成一個非零元的行與列之后，由鍵盤輸入非零元的大小e；并將其先存入二維陣列a[][]，

2、壓縮矩陣至三元組的演算法思想：獲得矩陣之后，將其壓縮進三元組表當中，三元組的非零元個數初始中為0，因在生成隨機矩陣的程序中可能會出現相同的行、列，導致矩陣非零元被覆寫，所以具體的非零元個數以矩陣當中的為準，遍歷矩陣，如果存在非零元，則將該元素的行標i與列標j，存入三元組，同時非零元個數+1，

3、列印矩陣的演算法思想：先列印每一行的元素，如果i,j與三元組表里的i,j相匹配，則列印元素，否則列印0，

4、三元組快速轉置的演算法思想：求得被轉置矩陣M的每一列的非零元個數，進而求得每一列的第一個非零元在T.data中應有的位置，故需要兩個輔助向量：num與copt，先使T.mu=M.nu、T.nu=M.mu、T.tu=M.tu，如果T.tu不等于0，則先求每一列中的非零元個數num[col]，col從1到M.nu；再求位置copt[col]，copt[col]=copt[col-1]+num[col-1] ，col從2到M.nu，copt[1]=1；最后進行轉置操作,令M的i,j互換，每次互換一個元素則++copt[col]，

5、具體實作代碼如下：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 200
#define OK 1
#define FALSE 0
#define OVERFLOW -2
#define ERROR 0
typedef int Status;
typedef int ElemType; 

typedef struct
{
    int i,j;
    ElemType e;
}Triple;

typedef struct
{
    Triple data[MAXSIZE+1];
    int mu,nu,tu;
}TSMatrix;

Status CreateMatrix(TSMatrix *M)
{
    int i,j,n,k;       //行，列，非零元個數
    int a[50][50]={0};   //存放矩陣，初始值為0 
    ElemType e;
    printf("本次稀疏矩陣的行數與列數均由亂數產生！\n");
    srand((unsigned)time(NULL) + (unsigned)rand());  //以time()為種子生成亂數
    (*M).mu=rand()%10+6;   //隨機行大小，取余是確定范圍，mu在（6~15）之間
    (*M).nu=rand()%10+7;   //隨機列大小
    k=rand()%10+6;   //隨機非零元個數
    printf("該稀疏矩陣的行數為%d,列數為%d,非零元個數為%d，",(*M).mu,(*M).nu,k);
    (*M).data[0].i=0;
	for(n = 1; n <= k; n++)   //生成亂數矩陣
	{
        i=rand()%(*M).mu+1;
        j=rand()%(*M).nu+1;
		printf("請按行序輸入第 %d 個非零元素,行%d,列%d,元素值:\n",n,i,j);
		scanf("%d",&e);
        a[i][j]=e;
    }
    (*M).tu=1;
    for(i=1;i<=(*M).mu;i++)  //以行為主序存入三元組
    {
        for(j=1;j<=(*M).nu;j++)
        {
            if(a[i][j]!=0)
            {
                (*M).data[M->tu].i = i;	//行下標
		        (*M).data[M->tu].j = j;	//列下標
		        (*M).data[M->tu].e = a[i][j];	//該下標所對應的值
                M->tu++;
            }
        }
    }
    M->tu--;
	return OK;
}

Status PrintMatrix(TSMatrix M)
{
    int i,j,n=1;
    printf("\n\n");
    for(i=1;i<=M.mu;i++)
    {
        for(j=1;j<=M.nu;j++)
        {
            if(M.data[n].i==i&&M.data[n].j==j)
            {
                printf("%4d",M.data[n].e);
                n++;
            }
            else
                printf("%4d",0);
        }
        printf("\n");
    }
}

Status FastTransposeSMatrix(TSMatrix M,TSMatrix *T)
{
    int col,t,p,q;
    int *num,*copt;
    num=(int*)malloc((M.nu+1)*sizeof(int));  //給num分配記憶體空間；大小為M的列數+1,num[1]開始
    copt=(int*)malloc((M.nu+1)*sizeof(int));  //copt表示該列的第一個非零元在T.data中的位置，copt大小與num相等
    T->mu=M.nu; T->nu=M.mu; T->tu=M.tu;  //T的行數等于M的列數，列數等于行數，非零元個數相等
    if(T->tu)  //非空
    {
        for(col=1;col<=M.nu;++col)
            num[col]=0;  //清零操作
        for(t=1;t<=M.tu;++t)
            ++num[M.data[t].j];    //求M中每一列含非零元個數
        copt[1]=1;  //M的第一列的第一個非零元在T的第一個位置
        for(col=2;col<=M.nu;++col)
            copt[col]=copt[col-1]+num[col-1];  //累加操作，比較復雜，求每一列的第一個非零元在T.data中的位置
        for(p=1;p<=M.tu;++p)
        {  
            col=M.data[p].j; q=copt[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;
            ++copt[col];  //位置已用，計數加一
        }
    }
    return OK;
}

void main()
{
    TSMatrix M,T;  
    CreateMatrix(&M);
    printf("原始矩陣如下:\n");
    PrintMatrix(M);  //列印M
    FastTransposeSMatrix(M,&T);
    printf("轉置矩陣如下:\n");
    PrintMatrix(T);  //列印T
}

6、粉絲數上50，下次加上流程圖，創作不易，謝謝支持，