十字鏈存儲

A. 圖的五種存儲結構

圖的鄰接矩陣（Adjacency Matrix）： 圖的鄰接矩陣用兩個數組來表示圖。一個一維數組存儲圖中頂點信息，另一個二維數組（一般稱之為鄰接矩陣）來存儲圖中的邊或者弧的信息。從鄰接矩陣中我們自然知道一個頂點的度（對於無向圖）或者有向圖中一個頂點的入度出度信息。

假設圖G有n個頂點，則鄰接矩陣是一個n*n的方陣。
1.對於如果圖上的每條邊不帶權值來說，那麼我們就用真（一般為1）和假（一般為0）來表示一個頂點到另一個頂點存不存在邊。下面是一個圖的鄰接矩陣的定義：

鄰接矩陣法實現帶權值的無向圖的創建如下：

按照如圖輸入各邊（不重復）

測試程序如下：

結果可得該矩陣，證明創建樹成功。 假設n個頂點e條邊的創建，createGraph演算法的時間復雜度為O（n+n*n+e）。如果需要創建一個有向圖，那麼和上面一樣一個一個錄入邊下標和權值。

鄰接矩陣這種存儲結構的優缺點： 缺點是對於邊數相對頂點較少的稀疏圖來說會存在極大的空間浪費。假設有n個頂點,優點是對於有向完全圖和無向完全圖來說鄰接矩陣是一種不錯的存儲結構，浪費的話也只浪費了n個頂點的容量。

在樹的存儲結構一節中我們提到對於孩子表示法的第三種：用一段連續的存儲單元（數組）存儲樹中的所有結點，利用一個單鏈表來存儲數組中每個結點的孩子的信息。對於圖的存儲結構來說，我們也可以利用這種方法實現圖的存儲

鄰接表(Adjacency List): 這種數組與鏈表相結合的存儲方法叫做鄰接表。1.為什麼不也用單鏈表存儲圖的結點信息呢？原因就是數組這種順序存儲結構讀取結點信息速率快。對於頂點數組中，每個數據元素還需要存儲一個指向第一個鄰接頂點的指針，這樣才可以查找邊的信息2.圖中每個頂點Vi(i > 0)的所有鄰接點構成一個線性表 （在無向圖中這個線性表稱為Vi的邊表，有向圖中稱為頂點作為弧尾的出邊表） ，由於鄰接點的不確定性，所以用鏈表存儲，有多少個鄰接點就malloc一個空間存儲鄰接點，這樣更不會造成空間的浪費（與鄰接矩陣相比來說）。3.對於鄰接表中的某個頂點來說，用戶關心的是這個頂點的鄰接點，完全可以遍歷用單鏈表設計成的邊表或者出邊表得到，所以沒必要設計成雙鏈表。

鄰接表的存儲結構：
假設現在有一無向圖G，如下圖：

從鄰接表結構中，知道一個頂點的度或者判斷兩個頂點之間是否存在邊或者求一個頂點的所有鄰接頂點是很容易的。

假設現在有一有向圖G，如下圖：

無向圖的鄰接表創建示例如下：

假設在上圖（無向圖）中的V0V1V2V3頂點值為ABCD，則依據下面測試程序可得結果：

鄰接表的優缺點： 優點是：鄰接表存儲圖，既能夠知道一個頂點的度和頂點的鄰接結點的信息，並且更不會造成空間的浪費。缺點是鄰接表存儲有向圖時，如果關心的是頂點的出度問題自然用鄰接表結構，但是想了解入度需要遍歷圖才知道（需要考慮逆鄰接表）。

十字鏈表(Orthogonal List) ：有向圖的一種存儲方法，它把鄰接表和逆鄰接表結合起來，因此在十字鏈表結構中可以知道一個頂點的入度和出度情況。
重新定義頂點表的結點如下圖：

現在有一有向圖如下圖：

則它的存儲結構示意圖為：

其定義如下：

十字鏈表是用來存儲有向圖的，這樣可以看出一個頂點的出入度信息。對於無向圖來說完全沒必要用十字鏈表來存儲。

在無向圖中，因為我們關注的是頂點的信息，在考慮節約空間的情況下我們利用鄰接表來存儲無向圖。但是如果我們關注的是邊的信息，例如需要刪除某條邊對於鄰接表來說是挺繁瑣的。它需要操作兩個單鏈表刪除兩個結點。因此我們仿照十字鏈表的方式對邊表結點結構重新定義如下圖：

它的鄰接多重表結構為：

多重鄰接表的優點：對於邊的操作相比於鄰接表來說更加方便。比如說我們現在需要刪除(V0,V2)這條邊，只需將69步驟中的指針改為nullptr即可。

邊集數組(edgeset array)： 邊集數組是由兩個數組組成，一個存儲頂點信息，另一個存儲邊的信息，這個邊數組中的每個數據元素由起點下標，終點下標，和權組成（如果邊上含有權值的話）。
邊數組結構如下圖：

邊集數組實現圖的存儲的優缺點：優點是對於邊的操作方便快捷，操作的只是數組元素。比如說刪除某條邊，只需要刪除一個數組元素。缺點是：對於圖的頂點信息，我們只有遍歷整個邊數組才知道，這個費時。因此對於關注邊的操作來說，邊集數組更加方便。

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

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

三元組是指形如（（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. 圖的存儲結構有多少種

1、鄰接矩陣：邏輯結構分為兩部分：V和E集合。因此，用一個一維數組存放圖中所有頂點數據；用一個二維數組存放頂點間關系的數據，這個二維數組稱為鄰接矩陣。鄰接孝答矩陣又分為有向圖鄰接矩陣和無向圖鄰接巧畢慧矩陣。

2、鄰接表：是由單鏈表的表頭形成的頂點表和單鏈表其餘結點形成的邊表兩部分組成。

3、十字鏈表：是有向圖數基的另一種鏈式存儲結構。該結構可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的。

4、鄰接多重表：主要用於存儲無向圖。

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

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

E. 用十字鏈表存儲結稀疏矩陣，並進行矩陣的轉置。 要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 */