❶ 三元組表與稀疏矩陣，怎麼轉換要求法。最好文字表述
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.一般稀疏矩陣通常採用列壓縮(或行壓縮)方式存貯，偶爾也用一樓提到的三元組方式，因為列壓縮格式在不犧牲效率的情況下更節省空間。
另外，一般不要去看國內數據結構教材上的稀疏矩陣存貯格式，只是紙上談兵，實際用的時候很少有這樣存的。