❶ 三元组表与稀疏矩阵，怎么转换要求法。最好文字表述
l->e=(list)malloc((MAXSIZE+1)*sizeof(ElemType));// 这句在VC不能通过编译，因为e是elemtype类型，分配的空间是list类型，不匹配。
三元组，第1列是行号，第2列是列号，第3列是非零元素的值。假设以顺序存储结构来表示三元组表（triple table），则得到稀疏矩阵的一种压缩存储方式，即三元组顺序表，简称三元组表。
(1)三元组按列优先存储吗扩展阅读：
对于在实际问题中出现的大型的稀疏矩阵，若用常规分配方法在计算机中储存，将会产生大量的内存浪费，而且在访问和操作的时候也会造成大量时间上的浪费，为了解决这一问题，从而产生了多种解决方案。
由于其自身的稀疏特性，通过压缩可以大大节省稀疏矩阵的内存代价。具体操作是：将非零元素所在的行、列以及它的值构成一个三元组（i，j，v），然后再按某种规律存储这些三元组，这种方法可以节约存储空间。
❷ 急！三元组顺序表的存储结构形成
/*~~~~稀疏矩阵的三元组顺序表存储结构类型定义及部分常见操作算法（smatrix.c）~~~~*/
#ifndef __SPARSEMATRIX__
#define __SPARSEMATRIX__
#ifndef COMMONELEM
#define COMMONELEM 0 /*公共元的值*/
#endif
#include <stdlib.h>
/*三元组顺序表存储空间长度的最小值*/
#define MATRIXMINSIZE 10
/*三元组顺序表存储结构类型定义*/
typedef struct
{
int row; /*行号*/
int col; /*列号*/
MatrixDT value; /*特殊元的值*/
}ThrElem; /*三元组元素类型*/
typedef struct
{
ThrElem *base; /*三元组表的基地址*/
int listsize; /*三元组表的存储空间尺寸*/
int len; /*三元组表的长度，即矩阵中特殊元的个数*/
int rows,cols; /*矩阵的行数、列数*/
}SMatrix;
/*矩阵初始化*/
void MatrixInitialize(SMatrix *pM, int size, int rows, int cols)
{
if(size<MATRIXMINSIZE)
size=MATRIXMINSIZE;
pM->listsize = size;
pM->base=(ThrElem *)malloc(pM->listsize*sizeof(ThrElem));
if(!pM->base)
exit(EXIT_FAILURE);
pM->rows=rows;
pM->cols=cols;
pM->len=0;
}
/*输出矩阵*/
void MatrixPrint(SMatrix M, void (*cout)(MatrixDT))
{
int i,j,k;
for(k=0,i=0; i<M.rows; i++)
{
for(j=0; j<M.cols; j++)
if(k<M.len && i==M.base[k].row && j==M.base[k].col)
(*cout)(M.base[k++].value);/*输出特殊元*/
else
(*cout)(COMMONELEM); /*输出公共元*/
printf("\n");
}
}
/*取矩阵元素*/
BOOL GetElem(SMatrix M, MatrixDT *pd, int i, int j)
{
int k, addr;
BOOL flg=TRUE;
if(i<0 || i>M.rows-1 || j<0 || j>M.cols-1)
flg=FALSE;/*访问越界*/
else
{
*pd = COMMONELEM;
/*
由于三元组顺序表中特殊元是按"以行优先的顺序并保持同一行中列号从小到大的
规律"保存的，故，可以把矩阵中每个特殊元的二元（行号和列号）逻辑地址转换
成递增有序的一元伪地址addr=行号*列数+列号；
本算法采用的是最简单的顺序查找方法。
由于关键字序列是递增有序的,所以也可以使用折半查找（详见第10章）等算法，
那样效率会更高。
*/
addr=i*M.cols+j;
for(k=0; k<M.len && M.base[k].row*M.cols +M.base[k].col <addr; k++)
;
if(k<M.len && i==M.base[k].row && j==M.base[k].col)
/*M[i][j]是特殊元*/
*pd = M.base[k].value;
}
return flg;
}
/*写矩阵元素*/
BOOL PutElem(SMatrix *pM, MatrixDT d, int i, int j,
BOOL (*equal)(MatrixDT,MatrixDT))
{
int k,m,addr;
BOOL flg=TRUE;
if(i<0 || i>pM->rows-1 || j<0 || j>pM->cols-1 || pM->len >=pM->listsize)
flg=FALSE;/*访问越界*/
else
{
addr=i*pM->cols +j;
/*扫描到i行中j列元素应在的位置*/
for(k=0;k<pM->len &&
pM->base[k].row* pM->cols +pM->base[k].col<addr; k++)
;
if(k<pM->len && i==pM->base[k].row && j==pM->base[k].col)
{
/*原来是特殊元*/
if((*equal)(d,COMMONELEM))
{
/*第1种情况：原来是特殊元，写入的是公共元值。从表中删除元素*/
for(m=k+1; m<pM->len; m++)
pM->base[m-1]=pM->base[m];
pM->len--;
}
else
/*第2种情况：原来是特殊元，写入的是特殊元值，更改元素值*/
pM->base[k].value=d;
}
else /*原来是公共元*/
{
if(!(*equal)(d,COMMONELEM))
{
/*第3种情况：原来是公共元，写入的是特殊元值。在表中k位置插入新元素*/
for(m=pM->len-1; m>=k; m--)
pM->base[m+1]=pM->base[m];
pM->base[k].row=i;
pM->base[k].col=j;
pM->base[k].value =d;
pM->len++;
}
else
/*第4种情况：原来是公共元，写入的是公共元值。空操作*/
;
}
}
return flg;
}
/*拷贝矩阵*/
void MatrixCopy(SMatrix* pM, SMatrix M)
{
int i;
pM->listsize = M.listsize;
pM->rows = M.rows;
pM->cols = M.cols;
pM->len = M.len;
/*申请存储空间*/
pM->base=(ThrElem *)malloc(pM->listsize*sizeof(ThrElem));
if(!pM->base)
exit(EXIT_FAILURE);
for(i=0; i<pM->len; i++)
pM->base[i]=M.base[i];/*复制数组中单元的值*/
}
/*矩阵加法*/
BOOL MatrixAdd(SMatrix* pM, SMatrix M, SMatrix N,
MatrixDT (*add)(MatrixDT,MatrixDT),BOOL (*equal)(MatrixDT,MatrixDT))
{
int i,j,k,addrM,addrN;
/*pM所指矩阵有可能是矩阵M或矩阵N，故先用base缓存结果，最后再给pM->base*/
ThrElem *base;
MatrixDT d;
BOOL flg=TRUE;
if(M.rows !=N.rows || M.cols!=N.cols)
flg=FALSE;
else
{
base=(ThrElem*)malloc((M.len + N.len)*sizeof(ThrElem));
if(!base)
exit(EXIT_FAILURE);
/*i、j和k分别指示M.base、N.base和临时数据区base的首位置*/
i=j=k=0;
while(i<M.len && j<N.len)
{
/*计算矩阵M和矩阵N递增有序的一元伪地址addrM和addrN*/
addrM=M.base[i].row*M.cols + M.base[i].col;
addrN=N.base[j].row*N.cols + N.base[j].col;
if(addrM==addrN)/*两个矩阵中存在位置相同的特殊元*/
{
/*d是两个位置相同的特殊元相加之和*/
d=(*add)(M.base[i].value , N.base[j].value);
if(!(*equal)(d, COMMONELEM))
{
/*d是特殊元,把（i,j,d）追加到base数组*/
base[k].row =M.base[i].row;
base[k].col =M.base[i].col;
base[k++].value =d;
}
i++;
j++;
}
else if(addrM < addrN) /*矩阵M中当前特殊元应先追加到base数组*/
{
base[k]=M.base[i++];
base[k++].value=(*add)(base[k].value, COMMONELEM);
}
else /*矩阵N中当前特殊元应先追加到base数组*/
{
base[k++]=N.base[j++];
base[k++].value=(*add)(base[k].value, COMMONELEM);
}
}
/*将矩阵M或矩阵N中剩余的特殊元追加到base数组*/
for(; i<M.len; i++)
{
base[k]=M.base[i++];
base[k++].value=(*add)(base[k].value, COMMONELEM);
}
for(; j<N.len; j++)
{
base[k]=N.base[j++];
base[k++].value=(*add)(base[k].value, COMMONELEM);
}
if(k>pM->listsize)
exit(EXIT_FAILURE);
/*复制结果数据到pM->base区*/
for(i=0; i<k; i++)
pM->base[i]=base[i];
free(base);
pM->rows=M.rows;
pM->cols=M.cols;
pM->len =k;
}
return flg;
}
/*矩阵转置*/
void MatrixTranspose(SMatrix *pM, SMatrix M)
{
int col,i,j;
ThrElem *base;
/*
本函数允许如下调用方式：
MatrixTranspose(&m, m);
所以要额外申请存储空间base
*/
base=(ThrElem*)malloc(M.listsize*sizeof(ThrElem));
if(!base)
exit(EXIT_FAILURE);
for(i=0,col=0; col<M.cols; col++) /*col是转置后矩阵的行号*/
for(j=0; j<M.len; j++)
if(M.base[j].col == col)
{
/*特殊元行列对换后写入新表空间*/
base[i].row = M.base[j].col;
base[i].col = M.base[j].row;
base[i].value = M.base[j].value;
i++;
}
pM->listsize =M.listsize;
pM->len =M.len;
pM->rows=M.cols;
pM->cols=M.rows;
free(pM->base);
pM->base=base;
}
/*销毁矩阵*/
void MatrixDestroy(SMatrix M)
{
free(M.base);
}
#endif
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/*
建议性测试用程序
*/
typedef enum {TRUE=1,FALSE=0} BOOL;
typedef int MatrixDT;
#include "smatrix.c"
#define inFORMAT "%d"
#define outFORMAT "%3d"
void printdata(MatrixDT x)
{
printf(outFORMAT,x);
}
MatrixDT add(MatrixDT x, MatrixDT y)
{
return x+y;
}
BOOL equal(MatrixDT x, MatrixDT y)
{
return x==y ? TRUE: FALSE;
}
void main()
{
int i,j,x, y, tlimit;
MatrixDT d;
SMatrix M,N;
BOOL valid=TRUE;
printf("请输入矩阵M的行数、列数及特殊元个数的上限值：\n");
scanf("%d%d%d",&x,&y, &tlimit);
MatrixInitialize(&M,tlimit, x, y);
while(valid)
{
printf("请输入特殊元的行号、列号(行号或列号无效时结束)：\n");
scanf("%d%d",&x, &y);
printf("请输入特殊元的值\n");
scanf(inFORMAT, &d);
valid=PutElem(&M,d,x,y,equal);
}
printf("原矩阵=\n");
MatrixPrint(M, printdata);
MatrixTranspose(&M,M);
printf("转置后矩阵=\n");
MatrixPrint(M, printdata);
printf("请输入要读取的单元的行号和列号：\n");
scanf("%d%d",&i,&j);
if(GetElem(M,&d,i,j))
{
printf("M[%d][%d]=",i,j);
printf(outFORMAT, d);
printf("\n");
}
else
printf("Invalid.\n");
MatrixPrint(M, printdata);
printf("Copy M to N.\n");
MatrixCopy(&N,M);
if(MatrixAdd(&M,M,N, add, equal))
{
printf("M+N=\n");
MatrixPrint(M, printdata);
}
MatrixDestroy(M);
}
❸ 如何在工作空间查看稀疏矩阵
稀疏矩阵
设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即s<<m×n)，则称A为稀疏矩阵。
1、稀疏矩阵的压缩存储
为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。
其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。
稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。链式存储方法【参见参考书目】。
2、三元组表
将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。
注意：
以下的讨论中，均假定三元组是按行优先顺序排列的。
【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b)
（1）三元组表的类型说明
为了运算方便，将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。其类型描述为：
#define MaxSize 10000 //由用户定义
typedef int DataType； //由用户定义
typedef struct { //三元组
int i，j；//非零元的行、列号
DataType v； //非零元的值
}TriTupleNode；
typedef struct{ //三元组表
TriTupleNode data[MaxSize]； //三元组表空间
int m,n，t； //矩阵的行数、列数及非零元个数
}TriTupleTable；
(2) 压缩存储结构上矩阵的转置运算
一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：
A[i][j]=B[j][i]，0≤i<m，0≤j<n，
即A的行是B的列，A的列是B的行。
【例】下图中的B和上图中的A互为转置矩阵。
①三元组表表示的矩阵转置的思想方法
第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。
第二步：当三元组表非空（A矩阵的非零元不为0）时，根据A矩阵三元组表的结点空间data（以下简称为三元组表），将A的三元组表a->data置换为B的三元组表b->data。
②三元组表的转置
方法一:简单地交换a->data中i和j中的内容，得到按列优先顺序存储倒b->data;再将b->data重排成按行优先顺序的三元组表。
方法二:由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。
按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示。具体实现参见【动画演示】
③具体算法：
void TransMatrix(TriTupleTable *b，TriTupleTable *a)
{//*a，*b是矩阵A、B的三元组表表示，求A转置为B
int p，q，col；
b->m=a->n； b->n=a->m； //A和B的行列总数互换
b->t=a->t； //非零元总数
if(b->t<=0)
Error("A=0")； //A中无非零元，退出
q=0；
for(col=0；col<a->n；col++) //对A的每一列
for(p=0；p<a->t；p++) //扫描A的三元组表
if(a->data[p]．j==col){ //找列号为col的三元组
b->data[q)．i=a->data[p].j；
b->data[q]．j=a->data[p].i；
b->data[q]．v=a->data[p].v；
q++；
}
} //TransMatrix
④算法分析
该算法的时间主要耗费在col和p的二重循环上：
若A的列数为n，非零元素个数t，则执行时间为O(n×t)，即与A的列数和非零元素个数的乘积成正比。
通常用二维数组表示矩阵时，其转置算法的执行时间是O(m×n)，它正比于行数和列数的乘积。
由于非零元素个数一般远远大于行数，因此上述稀疏矩阵转置算法的时间大于通常的转置算法的时间。
上一页
3、带行表的三元组表
为了方便某些矩阵运算，在按行优先存储的三元组表中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。这就是带行表的三元组表。
（1）类型描述
#define MaxRow l00 //在三元组表定义前加入此最大行定义
typedef struct {
TriTupleNode data[MaxSize]；
int RowTab[MaxRow]；//行表，应保证m≤MaxRow
int m，n，t;
}RTriTupleTable；
(2)带行表的三元组表的操作
① 对于任给行号i(0≤i≤m-1)，能迅速地确定该行的第一个非零元在三元组表中的存储位置为RowTab[i]
② RowTab[i](0≤i≤m-1)表示第i行之前的所有行的非零元数。
③ 第i行上的非零元数目为RowTab[i+1]-RowTab[i](0≤i≤m-2)
④ 最后一行(即第m-l行)的非零元数目为t-RowTab[m-1](t为矩阵的非零元总数)
注意：
若在行表中令RowTab[m]=t（要求MaxRow>m）会更方便 些，且t可省略。
带行表的三元组表可改进矩阵的转置算法，具体【参阅其它参考书】。
4．稀疏矩阵压缩存储方式分析
（1） 三元组表和带行表的三元组表的特点
相应的算法描述较为简单，但这类顺序存储方式对于非零元的位置或个数经常发生变化的矩阵运算就显得不太适合。
【例】执行将矩阵B相加到矩阵A上的运算时，某位置上的结果可能会由非零元变为零元，但也可能由零元变为非零元，这就会引起在A的三元组表中进行删除和插人操作，从而导致大量结点的移动。对此类运算采用链式存储结构为宜。
（2）稀疏矩阵的链式结构
稀疏矩阵的链式结构有十字链表等方法，适用于非零元变化大的场合，比较复杂，可【参阅其它参考书】。
❹ 三元组表示稀疏矩阵是什么
三元组表示稀疏矩阵是行列形式。为了方便某些矩阵运算，在按行优先存储的三元组表中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。
在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。
优点
稀疏矩阵的计算速度更快，因为 MATLAB 只对非零元素进行操作，这是稀疏矩阵的一个突出的优点。
假设矩阵 A,B 中的矩阵一样，计算 2*A 需要一百万次的浮点运算，而计算 2*B 只需要 2000 次浮点运算。
因为 MATLAB 不能自动创建稀疏矩阵，所以要用特殊的命令来得到稀疏矩阵。算术和逻辑运算都适用于稀疏矩阵。
对于一个用二维数组存储的稀疏矩阵 Amn ，如果假设存储每个数组元素需要 L 个字节，那么存储整个矩阵需要 m*n*L 个字节。但是，这些存储空间的大部分存放的是 0 元素，从而造成大量的空间浪费。为了节省存储空间，可以只存储其中的非 0 元素。
❺ 什么时候用三元组比较好
一个例子：
用三元组存储的稀疏矩阵的转置运算
三元组采用行优先表示法,转置后的矩阵的三元组同样要采用行优先表示法
0 1 12
0 2 9
2 0 -3
3 5 14
3 2 24
4 1 18
5 0 15
5 3 -7
struct node
{
int i,j; //定义三元组的行、列号
int v; //三元组的值
};
struct sparmatrix
{
int rows,cols; //稀疏矩阵的行、列数
int terms; //稀疏矩阵的非零元个数
struct node data[maxsize]; //存放稀疏矩阵的三元组表
};
（1）按照A的列序进行转置
由于A的列即为B的行，在a.data（原表）中，按列扫描，则得到的b.data（转置表）必按行优先存放。
但为了找到A的每一列中所有的非零的元素，每次都必须从头到尾扫描A的三元组表（有多少列，则扫描多少遍）
void transpose(struct sparmatrix a)
{
struct sparmatrix b; /*b为a的转置*/
int ano,bno=0,col,i;
b.rows=a.cols; b.cols=a.rows;
b.terms=a.terms;
if (b.terms>0)
{
for ( col=0; col<a.cols; col++) /*按列号扫描*/
for( ano=0;ano<a.terms;ano++) /*对三元组扫描*/
if (a.data[ano].j==col) /*进行转置*/
{ b.data[bno].j=a.data[ano].i;
b.data[bno].i=a.data[ano].j;
b.data[bno].v=a.data[ano].v;
bno++;
}
}
…………….
（2）按照A的行序进行转置
即按a.data中三元组的次序进行转置，并将转置后的三元组放入b中恰当的位置。
若能在转置前求出矩阵A的每一列col（即B中每一行）的第一个非零元转置后在b.data中的正确位置pot[col]（0≤col<a.cols），那么在对a.data的三元组依次作转置时，只要将三元组按列号col放置到b.data[pot[col]]中，之后将pot[col]内容加1，以指示第col列的下一个非零元的正确位置。
void fastrans(struct sparmatrix a)
{
struct sparmatrix b;
int pot[maxsize],col,ano,bno,t,i;
b.rows=a.cols; b.cols=a.rows;
b.terms=a.terms;
if(b.terms>0)
{
for(col=0;col<=a.cols;col++)
pot[col]=0;
for( t=0;t<a.terms;t++) /*求出每一列的非零元个数*/
{
col=a.data[t].j;
pot[col+1]=pot[col+1]+1;
}
pot[0]=0;
for(col=1;col<a.cols;col++) /*求出每一列的第一个非零元在转置后的位置*/
pot[col]=pot[col-1]+pot[col];
for( ano=0;ano<a.terms;ano++) /*转置*/
{ col=a.data[ano].j;
bno=pot[col];
b.data[bno].j=a.data[ano].i;
b.data[bno].i=a.data[ano].j;
b.data[bno].v=a.data[ano].v;
pot[col]=pot[col]+1;
}
}
❻ 急急：数据结构， 有加分！！！！
1、错，是有无限的算法的，例如一个没有终止条件的循环。
2、对，参考树和线性表的定义。
3、对
4、错，考虑极端情况：记录完全顺序或逆序排列就很清楚了。
5、错，反例是只有根节点或空的二叉树。
6、错，空二叉树。
7、错，如果是按照（值，行，列）的顺序存储的话就可能是这样。
8、对，但是能先排序的话就可以。
第七个是没问题的，如果按照一般的（行，列，值）的结构存储那就不可能，因为两个点在同一个位置了。但是可以按照（值，行，列）存的，没有冲突。
第一个我也不确定，这种定义问题太麻烦了，我觉得我说的是对的。
❼ 矩阵0元素不存储改怎么办
对于稀疏矩阵比较常用的存贮方式是这样的：
1.带状矩阵通常有两种存法，一种是按列优先方式，保存成一个kxn的矩阵，其中k是带宽。虽然在两端多占用了一些存贮空间，但是访问效率比较高。
另一种存法是沿对角线存成k个数组，这种方法通常仅用于k很小的时候，比如3对角矩阵。
2.一般稀疏矩阵通常采用列压缩(或行压缩)方式存贮，偶尔也用一楼提到的三元组方式，因为列压缩格式在不牺牲效率的情况下更节省空间。
另外，一般不要去看国内数据结构教材上的稀疏矩阵存贮格式，只是纸上谈兵，实际用的时候很少有这样存的。