最近有数据结构实验课了，还得学一学数据结构喽，以后就把学习经过贴上来了。

稀疏矩阵

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组

稀疏数组的处理方法

1）记录数组一共有几行几列，有多少个不同的值(假设有sum个，则稀疏矩阵有sum+1行，3列)
2）把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

百度盗图（手动滑稽）

稀疏矩阵转置

题目

（不得不说这个题输入数据的确坑。。）
有两种方法转置
话不多说，上代码：

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 1000
typedef struct{
int row;//第几行
int col;//第几列
int e;//存储的值
}Triple;

typedef struct
{
    Triple data[MAXSIZE];
    int m,n,len;//稀疏矩阵的行，列，非零元素的个数
}TSMatrix;


void createTSMatrix(TSMatrix *A)//创建矩阵
{    int i=1;     //data【0】未用
    scanf("%d %d",&A->m,&A->n);
    int flag = 1;
    int a,b,c;
    char c1,c2;
    while(flag)
    {
        scanf("%d",&a);
        c1 = getchar();
         scanf("%d",&b);
         c2 = getchar();
          scanf("%d",&c);
          if(c1=='?'&&c2=='?')
            break;
          A->data[i].row=a;
          A->data[i].col=b;
          A->data[i].e=c;
          i++;

    }
    i--;
    A->len=i;
}

void TransMatrix(TSMatrix A,TSMatrix *B)//序列递增转置法
{
    int i,j,k;
    B->n=A.m;
    B->m=A.n;
    B->len=A.len;
    if(B->len)
    {
        j=1;//辅助计数器，记录转置后的三元组元素下标值
        for(k=1;k<=A.n;k++)//扫描矩阵A的列次或B的行次

            for(i=1;i<=A.len;i++)  //扫描A找列为k的元素
        {
            if(A.data[i].col==k)
            {
                B->data[j].row=A.data[i].col;
                B->data[j].col=A.data[i].row;
                B->data[j].e=A.data[i].e;
                j++;
            }
        }
    }
}

void FastTransMatrix(TSMatrix A,TSMatrix *B)//快速转置法
{
    int col,t,p,q;
    int num[MAXSIZE],position[MAXSIZE];
    B->n=A.m;
    B->m=A.n;
    B->len=A.len;
    if(B->len)
    {
        for(col=1;col<=A.n;col++)
            num[col]=0;
        for(t=1;t<=A.len;t++)
            num[A.data[t].col]++;
        position[1]=1;
        for(col=2;col<=A.n;col++)
        {
            position[col]=position[col-1]+num[col-1];
        }
        for(p=1;p<=A.len;p++)
        {
            col=A.data[p].col;
            q=position[col];
            B->data[q].row=A.data[p].col;
            B->data[q].col=A.data[p].row;
            B->data[q].e=A.data[p].e;
            position[col]++;
        }
    }
}

void printMatrix(TSMatrix *B)//输出矩阵
{
    for(int i=1;i<=B->len;i++)
    {
        printf("%d %d %d\n",B->data[i].row,B->data[i].col,B->data[i].e);
    }
}

int main()
{
    TSMatrix A,B;//A为初始矩阵，B为转置后的矩阵
    createTSMatrix(&A);
    FastTransMatrix(A,&B);
    printMatrix(&B);
    return 0;
}

（参考数据结构教材，严蔚敏，吴伟民版 p99，多谢阅读，望对您有帮助）
无论是几维的数组，在计算机中都是以一维数组的方式进行存储的。
矩阵：相当于二维数组，它的存储，依然是用一维数组的方式进行存储。
nxn的矩阵，在计算机空间上，需要nxn个空间。
稀疏矩阵的压缩：将矩阵中的值为零或者为常数C的某c个数，不做存储（或者共用同样的空间，本题转置对0不做存储），压缩后原本nxn的矩阵，存储只需要nxn-c的空间
下面以这样的M矩阵进行转置
1 2 3
4 0 0
0 5 1
转置后得N矩阵：
1 4 0
2 0 5
3 0 1
M矩阵的计算机三元组存储方式（此图为图1）

转置后T矩阵的计算机三元组存储方式（此图为图2）

转置过程的实现，实际上是从图一转化为图二的过程
因为图1是按照行储存（第一行储存完了，才储存第二行），转置后的T矩阵，同样是按照行进行存储。
故T矩阵再遍历矩阵M时，M的列就是T的行，把M的每列的数据，逐列，一一存到data中，完成转置运算

先给出转置代码实现：

#include "stdio.h"
#include "stdlib.h"

#define Max_size 1000

typedef struct 
{
	int i;//矩阵中数据的行号
	int j;//矩阵中数据的列号
	int e;//i行j列，数据的值
}Triple;//三元组为一个节点

typedef struct
{
	Triple data[Max_size + 1];//data[0]未用
	int mu, nu, tu;//矩阵的行数，列数，非零元个数
}Matrix;

void TransposeSMatrix(Matrix M,Matrix &T)//将矩阵M转置为T
{
	T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
	if (T.tu)//非零元不为0
	{
		int q = 1;//用于逐项记录转置后矩阵T的值
		int col, p;//矩阵M的col列号，p:指向当前值在M矩阵硬件的储存位置
		for (col = 1; col < M.nu; col++)
		{
			for (p = 1; p < M.tu; p++)
			{
				if (M.data[p].j == col)//逐列进行遍历，并插入到T.data中
				{
					T.data[q].i = M.data[p].j;
					T.data[q].j = M.data[p].i;//转置后i，j互换
					T.data[q].e = M.data[p].e;//T的值获取到
					q++;//T指针的数据后移
				}
			}
		}
	}
}

int main()
{
	Matrix M,T;
	M.mu = 3;
	M.nu = 3;
	M.tu = 6;
	M.data[1].i = 1;
	M.data[1].j = 1;
	M.data[1].e = 1;

	M.data[2].i = 1;
	M.data[2].j = 2;
	M.data[2].e = 2;

	M.data[3].i = 1;
	M.data[3].j = 3;
	M.data[3].e = 3;

	M.data[4].i = 2;
	M.data[4].j = 1;
	M.data[4].e = 4;

	M.data[5].i = 3;
	M.data[5].j = 2;
	M.data[5].e = 5;

	M.data[6].i = 3;
	M.data[6].j = 3;
	M.data[6].e = 1;

	TransposeSMatrix(M, T);
	printf("(%d,%d):%d", T.data[4].i, T.data[4].j, T.data[4].e);//求转置后T矩阵2行3列的值
	return 0;
}

运行结果
转置后T矩阵2行3列的值为5，如运行结果所示

问题描述

  输入矩阵的行数、列数和非零元素个数，以及所有非零元素，非零元素包括每个元素的行号、列号、元素值。

  要求：1. 输入的非零元素个数必须满足稀疏矩阵要求，输入过程检测是否满足此要求，若不满足，则重新输入非零元素个数；
        2. 非零元素按行号从小到大顺序输入，相同行号的元素，列号从小到大输入，输入过程检测是否满足此要求，若不满足，则重新输入当前非零元素的行号、列号和元素值
        

了解什么是稀疏矩阵

/**
 * 稀疏矩阵: 是指矩阵中大多数元素为 0 的矩阵。从直观上讲,当非零元素个数低于总元素的 30%
 * 时,这样的矩阵为稀疏矩阵
 *  1. 稀疏矩阵的三元组存储表示
 *      对于稀疏矩阵的存储压缩,采取只存储非零元素的方法。由于稀疏矩阵中非零元素 a_i_j 的分布没有
 *      规律，因此再存储非零元素值的同时,还必须存储该非零元素在矩阵中所处的行号和列号的位置,这就是
 *      稀疏矩阵的三元组表 表示法。
 *
 *  三元组结构:
 *      该非零元素所在的行值       该非零元素所在的列值       该非零元素的值
 *              row                     col                 e
 *
 *   说明: 为处理方便,将稀疏矩阵中非零元素的三元组按照 "行序为主序" 的一维结构体数组进行存放,
 *        将矩阵的每一行(行由小到大)的全部非零元素的三元组按列号递增存放.
 *
 *   矩阵转置:
 *      指变换元素的位置,把位于(row,col) 位置上的元素转换到(col,row)位置上,即把元素的行列互换
 *
 */

输入数据样例

第一组数据:
行 	列 	数据元素值
3 	5 		4
--------------------
1 	1 		1
1 	4 		32
2 	3 		4
3 	2 		15

第二组数据:
行 	列 	数据元素值
3 	5 		4
--------------------
1 	1 		1
1 	4 		32
2 	3 		4
2  	1 		15
3   2       15


第三组数据:
行 	列 	数据元素值
3 	5 		6

非零元素不满足条件重新输入: 4
--------------------
1 	1 		1
1 	4 		32
2 	3 		4
3   2       15

解决方案

#include <stdio.h>

/* 非零元素的个数最多为 255 */
#define MAX_SIZE 255

typedef int ElementType;

typedef struct {
    /* 非零元素的行下标 */
    int row;
    /* 非零元素的列下标 */
    int col;
    /* 该非零元素的值 */
    ElementType e;
} Triple;


typedef struct {
    /* 该非零元素的三元组表 MAX_SIZE+1: 表示 data[0] 为使用 */
    Triple data[MAX_SIZE + 1];
    /* 矩阵的行数 */
    int rows;
    /* 矩阵的列数 */
    int cols;
    /* 矩阵的非零元素个数 */
    int length;
} TSMatrix;




/**
 * 稀疏矩阵列序递增转置算法
 * @param A 原矩阵
 * @param B 转置后
 */
void TransposeTSMatrix(TSMatrix A, TSMatrix *B);

void printT(TSMatrix B);

void InputT(TSMatrix *A);
int main() {
    TSMatrix A, B;
    InputT(&A);

    /* 转置前输出 */
    printf("Before:\n");
    printT(A);

    TransposeTSMatrix(A, &B);

    /* 转置后输出 */
    printf("After:\n");
    printT(B);

    return 0;
}

void TransposeTSMatrix(TSMatrix A, TSMatrix *B) {
    /* 把矩阵 A 转置到 B 所指向的矩阵中去。矩阵用三元组表示 */
    int i, j, k;
    /* B的行 = A 的列 */
    B->rows = A.cols;
    /* B的列 = A的行 */
    B->cols = A.rows;
    /* 矩阵元素个数相同 */
    B->length = A.length;

    /* 如果 B元素个数大于 0 */
    if (B->length > 0) {
        /* j为辅助计数器,记录转置后的三元组在三元组表B中的下标值 */
        j = 1;
        /* 扫描三元组表 A共 A.cols,每次寻找到列值为 k 的三元组进行转置 */
        for (k = 1; k <= A.cols; k++) {
            for (i = 1; i <= A.length; i++) {
                /* 从头到尾扫描三元组表A,寻找 col 值为 k 的三元组进行转置 */
                if (A.data[i].col == k) {
                    B->data[j].row = A.data[i].col;
                    B->data[j].col = A.data[i].row;
                    B->data[j].e = A.data[i].e;
                    /* 计数器 j 加 1,指向本行下一个转置后元素的位置下标 */
                    j++;
                }
            } /* inner for end */
        } /* out for end */
    } /* if end */
} /* TransposeTSMatrix end */


void printT(TSMatrix B) {
    int i, j;
    int t = 1;
    int zero = 0;
    for (i = 1; i <= B.rows; i++) {
        for (j = 1; j <= B.cols; j++) {
            if (B.data[t].row == i && B.data[t].col == j) {
                printf("%-4d", B.data[t].e);
                t++;
            } else printf("%-4d", zero);
        }
        printf("\n");
    }
}

void InputT(TSMatrix *A) {
    int i;
    /*
     * 目标:
     *    存储一个三元组
     *      1. 先满足输入的行列条件
     *      2. 再满足非零元素个数
     *      3. 实现三元组创建
     * */

    /* 第一次输入行列: 获取对应矩阵的行数和列数 */
    scanf("%d%d", &A->rows, &A->cols);

    /* 输入的非零元素个数必须满足稀疏矩阵要求，输入过程检测是否满足此要求，若不满足，则重新输入非零元素个数 */
    do {
        /* 输入非零元素个数 */
        scanf("%d", &A->length);
        /* 如果非零元素个数大于 4,重新输入 => 矩阵大小为 3 行 5 列，6 个非零元素；(6 个非零元素，不是稀疏矩阵，输入错误） */
    } while ((A->length > (A->rows * A->cols * 0.3))); /* 限制非零元素个数的 do...while end  */

    /* 非零元素个数满足后: 输入第一组矩阵表元素 */
    scanf("%d%d%d", &A->data[1].row, &A->data[1].col, &A->data[1].e);

    /**
    *  非零元素按行号从小到大顺序输入，相同行号的元素，列号从小到大输入，输入过程检测是否满足此要求，
    *  若不满足，则重新输入当前非零元素的行号、列号和元素值
    */
    for (i = 2; i <= A->length; i++) {
        do {
            /* 输入三元组表: 获取对应位置下标的值 */
            scanf("%d%d%d", &A->data[i].row, &A->data[i].col, &A->data[i].e);
        } while (A->data[i].row < A->data[i - 1].row ||
                 A->data[i].row == A->data[i - 1].row && A->data[i].col <= A->data[i - 1].col);
    }
}

结果输出