前面的幾篇博客，我們對(duì)圖進(jìn)行基本定義，同時(shí)介紹了圖的創(chuàng)建、圖的添加和刪除等。今天，我們聊一聊圖是怎么在存儲(chǔ)在外設(shè)中的。這些外接設(shè)備可以是各種類(lèi)型的，比如說(shuō)，可以是硬盤(pán)、sd卡、網(wǎng)絡(luò)硬盤(pán)等等。本質(zhì)上說(shuō)，我們今天討論的主題就是怎么把圖的數(shù)據(jù)永久地保留在本地。并且，如果需要加載這些數(shù)據(jù)，也可以快速恢復(fù)圖原來(lái)的面貌。對(duì)圖數(shù)據(jù)結(jié)構(gòu)已經(jīng)記得不太清楚的朋友可以復(fù)習(xí)一下面的代碼，回想一下我們之前的定義方法。

typedef struct _LINE
{
    int end;
    int weight;
    struct _LINE* next;
}LINE;

typedef struct _VECTEX
{
    int start;
    int number;
    LINE* neighbor;
    struct _VECTEX* next;
}VECTEX;

typedef struct _GRAPH
{
    int count;
    VECTEX* head;
}GRAPH;

數(shù)據(jù)結(jié)構(gòu)中有好多的指針。那么在外存中應(yīng)該怎么保存呢？因?yàn)閷?duì)于外存來(lái)說(shuō)，指針是沒(méi)有什么意義的。大家稍微思考其實(shí)就明白了。其實(shí)我們可以把這些指針全部看成是偏移值。GRAPH是有許多的點(diǎn)構(gòu)成的，點(diǎn)的結(jié)構(gòu)中有很多的邊連接，那么我們就可以按照下面的順序保存數(shù)據(jù)。

    /*
    *    ---------------------------------------------------------------------------
    *    | GRAPH | vectex1 | vectex2 | ...... | vectex n   | LINE1 |......| LINE n |
    *    ---------------------------------------------------------------------------
    */

那么偏移值怎么安排呢？

a）GRAPH結(jié)構(gòu)

head為第一個(gè)vectex的偏移地址。

b）VECTEX結(jié)構(gòu)

neighbour記錄了第一條邊的偏移位置，next記錄了下一個(gè)節(jié)點(diǎn)的偏移值。

c）LINE結(jié)構(gòu)

next為下一條邊的偏移值。

但是，如果我們做一些優(yōu)化的話(huà)，那么保存的數(shù)據(jù)還要少一些。比如說(shuō)，第一個(gè)vectex的節(jié)點(diǎn)就在GRAPH的后面，那么head實(shí)際上不需要保存；同時(shí)在vectex結(jié)構(gòu)中，因?yàn)槲覀冃枰繪INE的偏移值，所以neighbour的偏移是需要知道的，但是next就不再需要了，因?yàn)関ectex數(shù)據(jù)本身就是并列在一起的；最后同樣因?yàn)槲覀冃枰阉袑儆谕粋€(gè)vectex的邊放在一起，那么LINE結(jié)構(gòu)中的next數(shù)據(jù)其實(shí)也可以省略了。所以修改后保存的數(shù)據(jù)結(jié)構(gòu)大體應(yīng)該是這樣的：

typedef struct _LINE
{
    int end;
    int weight;
}LINE;

typedef struct _VECTEX
{
    int start;
    int number;
    LINE* neighbor;
}VECTEX;

typedef struct _GRAPH
{
    int count;
}GRAPH;

有了上面的數(shù)據(jù)結(jié)構(gòu)，那么從外層加載數(shù)據(jù)就是一個(gè)逆向操作而已，不再?gòu)?fù)雜了。