三元十字鏈存儲方法

⑴ 三元組法和十字鏈表法可以存儲普通的數組嗎

沒聽過，新的數據結構嗎？數據結構都可以存數組的。

⑵ 稀疏矩陣一般的壓縮存儲方法有兩種

分別是三元組和十字鏈表。

三元組是指形如（（x，y），z）的集合（這就是說，三元組是這樣的偶，其第一個射影亦是一個偶），常簡記為（x，y，z）。

三元組是計算機專業的一門公共基礎課程——數據結構里的概念。主要是用來存儲稀疏矩陣的一種壓縮方式，也叫三元組表。假設以順序存儲結構來表示三元組表（triple table），則得到稀疏矩陣的一種壓縮存儲方式，即三元組順序表，簡稱三元組表。

十字鏈表（Orthogonal List)是有向圖的另一種鏈式存儲結構。該結構可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的。用十字鏈表來存儲有向圖，可以達到高效的存取效果。同時，代碼的可讀性也會得到提升。

拓展資料：

十字鏈表（Orthogonal List)是有向圖的另一種鏈式存儲結構。可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的一種鏈表。在十字鏈表中，對應於有向圖中每一條弧都有一個結點，對應於每個定頂點也有一個結點。

十字鏈表之於有向圖，類似於鄰接表之於無向圖。

也可以理解為 將行的單鏈表和列的單鏈表結合起來存儲稀疏矩陣稱為十字鏈表， 每個節點表示一個非零元素。

三元組解釋：

1、所謂「三元組」是指圖形的幾何元素構成、圖線間的拓撲關系和尺寸約束。如果一組圖形的前二元相同而只是尺寸大小不同，則這組圖形構成一族形狀相同的系列化圖形。

2、把組成一個元素的三個數稱為三元組。一個三元組包含以下三部分的內容SDO_STARTING_OFFSET表明每個幾何元素的第一個坐標在SDO_ORDINATES數組中的存儲位置。

3、…Mt：N2）的表示稱為三元組...…Mt稱為標號，N1、N2為結點R為關系。當n≠0時，稱Li為對結點N1的修飾。t≠0時，稱Mj為對結點N2的修飾。

參考資料：網路：十字鏈表

網路：三元組

⑶ 用十字鏈表存儲結稀疏矩陣，並進行矩陣的轉置。 要C的，c++的我看不懂。。。。~

這個吧 功能比你要的還多：http://wenku..com/view/3d744dd950e2524de5187e68.html
建立稀疏矩陣A 的十字鏈表首先輸入的信息是：m（A 的行數），n（A 的列數），r（非零項的數目），緊跟著輸入的是r 個形如（i,j,aij）的三元組。

演算法的設計思想是：首先建立每行（每列）只有頭結點的空鏈表，並建立起這些頭結點拉成的循環鏈表；然後每輸入一個三元組（i，j，aij），則將其結點按其列號的大小插入到第i 個行鏈表中去，同時也按其行號的大小將該結點插入到第j 個列鏈表中去。在演算法中將利用一個輔助數組MNode *hd[s+1]; 其中s=max(m , n) , hd [i]指向第i 行(第i 列)鏈表的頭結點。這樣做可以在建立鏈表時隨機的訪問任何一行（列），為建表帶來方便。

演算法如下：
MLink CreatMLink( ) /* 返回十字鏈表的頭指針*/
｛
MLink H;
Mnode *p,*q,*hd[s+1];
int i,j,m,n,t;
datatype v;
scanf(「%d,%,%d」,&m,&n,&t);
H=malloc(sizeof(MNode)); /*申請總頭結點*/
H->row=m; H->col=n;
hd[0]=H;
for(i=1; i<S; i++)
{ p=malloc(sizeof(MNode)); /*申請第i 個頭結點*/
p->row=0; p->col=0;
p->right=p; p->down=p;
hd[i]=p;
hd[i-1]->v_next.next=p;
}
hd[S]->v_next.next=H; /*將頭結點們形成循環鏈表*/
for (k=1;k<=t;k++)
{ scanf (「%d,%d,%d」,&i,&j,&v); /*輸入一個三元組，設值為int*/
p=malloc(sizeof(MNode));
p->row=i ; p->col=j; p->v_next.v=v
/*以下是將*p 插入到第i 行鏈表中去，且按列號有序*/
q=hd[i];
while ( q->right!=hd[i] && (q->right->col)<j ) /*按列號找位置*/
q=q->right;
p->right=q->right; /*插入*/
q->right=p;
/*以下是將*p 插入到第j 行鏈表中去，且按行號有序*/
q=hd[i];
while ( q->down!=hd[j] && (q->down->row)<i ) /*按行號找位置*/
q=q->down;
p-> down =q-> down; /*插入*/
q-> down =p;
} /*for k*/
return H;
} /* CreatMLink */

⑷ 數據結構分別在什麼時候應該採用三元組、十字鏈表來存儲矩陣

據我所知有下面幾種情況
1.數據結構教材上
2.作業或考試題
3.對於三元組，在不同人交換數據的時候經常採用，因為這個格式最簡單

實際存貯稀疏矩陣不用這兩種方式，一般用列壓縮格式或者行壓縮格式，這和三元組一樣是標准格式，但是節省存貯量。

⑸ 稀疏矩陣的應用（三元組和十字鏈法）

十字鏈表是這樣構成的：用鏈表模擬矩陣的行（或者列，這可以根據個人喜好來定），然後，再構造代表列的鏈表，將每一行中的元素節點插入到對應的列中去。十字鏈表的邏輯結構就像是一個圍棋盤（沒見過，你就想一下蒼蠅拍，這個總見過吧），而非零元就好像是在棋盤上放的棋子，總共占的空間就是，確定那些線的表頭節點和那些棋子代表的非零元節點。最後，我們用一個指針指向這個棋盤，這個指針就代表了這個稀疏矩陣。
=================
說了一堆還是舉個例子吧：
#include <malloc.h>
#include <stdio.h>

/*十字鏈表的結構類型定義如下：*/
typedef struct OLNode
{
int row,col; /*非零元素的行和列下標*/
ElementType value;
struct OLNode *right; /*非零元素所在行表、列表的後繼鏈域*/
struct OLNode *down;
}OLNode; *OLink;

typedef struct
{
OLink *row_head; /*行、列鏈表的頭指針向量*/
OLink *col_head;
int m,n,len; /*稀疏矩陣的行數、列數、非零元素的個數*/
}CrossList;

/*建立稀疏矩陣的十字鏈表的演算法*/

void CreateCrossList(CrossList *M)
{
/*採用十字鏈表存儲結構，創建稀疏矩陣M*/
scanf(&m,&n,&t); /*輸入M的行數,列數和非零元素的個數*/
M->m=m;
M->n=n;
M->len=t;
if(!(M->row_head=(OLink *)malloc((m+1)sizeof(OLink))))
exit(OVERFLOW);
if(!(M->col_head=(OLink * )malloc((n+1)sizeof(OLink))))
exit(OVERFLOW);
M->row_head[ ]=M->col_head[ ]=NULL; /*初始化行、列頭指針向量，各行、列鏈表為空的鏈表*/
for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e))
{
if(!(p=(OLNode *)malloc(sizeof(OLNode))))
exit(OVERFLOW);
p->row=i;
p->col=j;
p->value=e; /*生成結點*/
if(M->row_head[i]==NULL)
M->row_head[i]=p;
else
{
/*尋找行表中的插入位置*/
for(q=M->row_head[i];q->right&&q->right->col<j;q=q->right); /*空循環體*/
p->right=q->right;
q->right=p; /*完成插入*/
}
if(M->col_head[j]==NULL)
M->col_head[j]=p;
else
{
/*尋找列表中的插入位置*/
for(q=M->col_head[j];q->down&&q->down->row<i;q=q->down); /*空循環體*/
p->down=q->down;
q->down=p; /*完成插入*/
}
}
}

更多相關知識自己去找數據結構的書來看。
編程愛好者群：24410693 只要對c有興趣就可以申請加入本群.

⑹ 線性表最主要的兩個應用是他們之間最重要的區別是

隊列和堆棧
隊列是先進先出FIFO
堆棧是先進後出FILO

⑺ 十字鏈表的介紹

十字鏈表（Orthogonal List)是有向圖的另一種鏈式存儲結構。該結構可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的。用十字鏈表來存儲有向圖，可以達到高效的存取效果。同時，代碼的可讀性也會得到提升。

⑻ 畫圖表示下列稀疏矩陣的三元組和十字鏈表存儲方式。

如圖

⑼ 如何用行邏輯鏈接順序表及十字鏈表存儲稀疏矩陣

來自 嚴蔚敏《數據結構》 稀疏矩陣的壓縮方法主要有： 1：三元組順序表 （行下標，列下標，值） 2：行邏輯鏈接的順序表。 3：十字鏈表。

⑽ 稀疏矩陣的加法和乘法c語言（十字鏈演算法）

你沒有寫具體要求，是用採用三元組作存儲結構還是數組，下面是我們以前做過的數據結構習題你參考一下：
能區分加法、減法、乘法和轉置；能處理任意輸入的典型數據和進行出錯數據處理（例如乘法，當第一個矩陣的列數不等於第二個矩陣的行數時）；必須採用三元組作存儲結構，不能採用數組等形式；輸出要求用矩陣的形式輸出（即習題集136頁的形式），當第一個矩陣的行數不等於第二個矩陣的行數時，注意如第三個乘法的形式輸出

******************************************************************************************

#include<stdio.h>
#define maxsize 100
typedef struct
{
int i,j; //該非零元的行和列
int v; //該非零元的值
}triple;
typedef struct
{
triple data[maxsize]; //非零元三元組表，data[0]未用
int rpos[maxsize];
int m,n,t; //矩陣的行數，列數和非零元個數
}tripletable;

void convert() //矩陣的轉置

{
int k;
tripletable A,B;
printf("輸入稀疏矩陣A的行數，列數和非零元個數：");
scanf("%d %d %d",&A.m,&A.n,&A.t);
for(k=1;k<=A.t;k++)
{
printf("輸入第%d個非0元素的行數，列數和值:",k);
scanf("%d %d %d",&A.data[k].i,&A.data[k].j,&A.data[k].v);
}
B.m=A.m;B.n=A.n;B.t=A.t;
if(B.t)
{
int q=1,col;
for(col=1;col<=A.n;++col)
for(int p=1;p<=A.t;++p)
if(A.data[p].j==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;
}
}
int shuru[100][100]={0};
for(k=1;k<=B.t;k++)
{
shuru[B.data[k].j][B.data[k].i]=B.data[k].v;
}
printf("輸入為：\n");
for(k=1;k<=B.m;k++)
{
for(int l=1;l<=B.n;l++)
printf("%d ",shuru[k][l]);
printf("\n");
}
int result[100][100]={0};

for(k=1;k<=B.t;k++)
{
result[B.data[k].i][B.data[k].j]=B.data[k].v;
}
printf("結果為：\n");
for(k=1;k<=B.n;k++)
{
for(int l=1;l<=B.m;l++)
printf("%d ",result[k][l]);
printf("\n");
}
}

void add() //矩陣的加法
{
int k;
tripletable A,B;
printf("輸入稀疏矩陣A的行數，列數和非零元個數：");
scanf("%d %d %d",&A.m,&A.n,&A.t);
for(k=1;k<=A.t;k++)
{
printf("輸入第%d個非0元素的行數，列數和值:",k);
scanf("%d %d %d",&A.data[k].i,&A.data[k].j,&A.data[k].v);
}
printf("輸入稀疏矩陣B的行數，列數和非零元個數：");
scanf("%d %d %d",&B.m,&B.n,&B.t);
for(k=1;k<=B.t;k++)
{
printf("輸入第%d個非0元素的行數，列數和值:",k);
scanf("%d %d %d",&B.data[k].i,&B.data[k].j,&B.data[k].v);
}
if(A.m!=B.m||A.n!=B.n)
{
printf("輸入錯誤：A與B的行數或列數不相同，請重新輸入\n");
return;
}
int a[100][100]={0};
for(k=1;k<=A.t;k++)
{
a[A.data[k].i][A.data[k].j]=A.data[k].v;
}
printf("A輸入為：\n");
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
printf("%d ",a[k][l]);
printf("\n");
}

int b[100][100]={0};
for(k=1;k<=B.t;k++)
{
b[B.data[k].i][B.data[k].j]=B.data[k].v;
}
printf("B輸入為：\n");
for(k=1;k<=B.m;k++)
{
for(int l=1;l<=B.n;l++)
printf("%d ",b[k][l]);
printf("\n");
}
int c[100][100]={0};
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
{
c[k][l]=a[k][l]+b[k][l];
}
}
printf("加法結果C為：\n");
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
printf("%d ",c[k][l]);
printf("\n");
}
}

void jian() //矩陣的減法
{
int k;
tripletable A,B;
printf("輸入稀疏矩陣A的行數，列數和非零元個數：");
scanf("%d %d %d",&A.m,&A.n,&A.t);
for(k=1;k<=A.t;k++)
{
printf("輸入第%d個非0元素的行數，列數和值:",k);
scanf("%d %d %d",&A.data[k].i,&A.data[k].j,&A.data[k].v);
}
printf("輸入稀疏矩陣B的行數，列數和非零元個數：");
scanf("%d %d %d",&B.m,&B.n,&B.t);
for(k=1;k<=B.t;k++)
{
printf("輸入第%d個非0元素的行數，列數和值:",k);
scanf("%d %d %d",&B.data[k].i,&B.data[k].j,&B.data[k].v);
}
if(A.m!=B.m||A.n!=B.n)
{
printf("輸入錯誤：A與B的行數或列數不相同，請重新輸入\n");
return;
}
int a[100][100]={0};
for(k=1;k<=A.t;k++)
{
a[A.data[k].i][A.data[k].j]=A.data[k].v;
}
printf("A輸入為：\n");
for(k=1;k<=B.m;k++)
{
for(int l=1;l<=A.n;l++)
printf("%d ",a[k][l]);
printf("\n");
}

int b[100][100]={0};
for(k=1;k<=B.t;k++)
{
b[B.data[k].i][B.data[k].j]=B.data[k].v;
}
printf("B輸入為：\n");
for(k=1;k<=B.m;k++)
{
for(int l=1;l<=B.n;l++)
printf("%d ",b[k][l]);
printf("\n");
}
int c[100][100]={0};
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
{
c[k][l]=a[k][l]-b[k][l];
}
}
printf("減法結果C為：\n");
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
printf("%d ",c[k][l]);
printf("\n");
}
}

void multi() //矩陣的乘法
{
int k;
tripletable A,B,C;
printf("輸入稀疏矩陣A的行數，列數和非零元個數：");
scanf("%d %d %d",&A.m,&A.n,&A.t);
for(k=1;k<=A.t;k++)
{
printf("輸入第%d個非0元素的行數，列數和值:",k);
scanf("%d %d %d",&A.data[k].i,&A.data[k].j,&A.data[k].v);
}
int row=1;
for(k=1;k<=A.t;k++)
{
while(row<=A.data[k].i)
{
A.rpos[row++]=k;
}
}
while(row<=A.m)A.rpos[row++]=A.t+1;
printf("輸入稀疏矩陣B的行數，列數和非零元個數：");
scanf("%d %d %d",&B.m,&B.n,&B.t);
for(k=1;k<=B.t;k++)
{

printf("輸入第%d個非0元素的行數，列數和值:",k);
scanf("%d %d %d",&B.data[k].i,&B.data[k].j,&B.data[k].v);
}
row=1;
for(k=1;k<=B.t;k++)
{
while(row<=B.data[k].i)
{
B.rpos[row++]=k;
}
}
while(row<=B.m)B.rpos[row++]=B.t+1;
if(A.n!=B.m)
{
printf("輸入錯誤：A的列數不等於B的行數，請重新輸入\n");
return;
}

C.m=A.m;C.n=B.n;C.t=0;
int arow,p,q,ccol,t,tp;
if(A.t*B.t!=0)
{
for(arow=1;arow<=A.m;++arow)
{
int ctemp[maxsize]={0};
C.rpos[arow]=C.t+1;
if(arow<A.m){tp=A.rpos[arow+1];}
else{tp=A.t+1;}
for(p=A.rpos[arow];p<tp;++p)
{
int brow=A.data[p].j;
if(brow<B.m){t=B.rpos[brow+1];}
else{t=B.t+1;}
for(q=B.rpos[brow];q<t;++q)
{
ccol=B.data[q].j;
ctemp[ccol]+=A.data[p].v*B.data[q].v;

}

}
for(ccol=1;ccol<=C.n;++ccol)
{
if(ctemp[ccol])
{
if(++C.t>maxsize)return;
C.data[C.t].i=arow;
C.data[C.t].j=ccol;
C.data[C.t].v=ctemp[ccol];
}
}

}

}

int a[100][100]={0};
for(k=1;k<=A.t;k++)
{
a[A.data[k].i][A.data[k].j]=A.data[k].v;
}
printf("A輸入為：\n");
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
printf("%d ",a[k][l]);
printf("\n");
}

int b[100][100]={0};
for(k=1;k<=B.t;k++)
{
b[B.data[k].i][B.data[k].j]=B.data[k].v;
}
printf("B輸入為：\n");
for(k=1;k<=B.m;k++)
{
for(int l=1;l<=B.n;l++)
printf("%d ",b[k][l]);
printf("\n");
}
int c[100][100]={0};
for(k=1;k<=C.t;k++)
{
c[C.data[k].i][C.data[k].j]=C.data[k].v;
}
printf("乘法結果C為：\n");
for(k=1;k<=C.m;k++)
{
for(int l=1;l<=C.n;l++)
printf("%d ",c[k][l]);
printf("\n");
}

}

void main()
{
printf("============= 菜 單 ==============\n");
printf(" 1 矩陣轉置\n");
printf(" 2 矩陣加法\n");
printf(" 3 矩陣減法\n");
printf(" 4 矩陣乘法\n");
printf("======================================\n\n");
loop: printf("請選擇相應操作的序號:");
int y;
scanf("%d",&y);
switch(y)
{
case 1: convert();
printf("\n");
goto loop;
case 2: add();
printf("\n");
goto loop;
case 3: jian();
printf("\n");
goto loop;
case 4: multi();
printf("\n");
goto loop;
}
}