在線性表中，數(shù)據(jù)元素之間是被串起來的，僅有線性關(guān)系，每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素相關(guān)，但只能和上一層中一個元素相關(guān)；在圖形結(jié)構(gòu)中，是由頂點的有窮非空集合和頂點之間邊的集合組成，如果兩個頂點之間存在一條邊，那么就表示這兩個頂點具有相鄰關(guān)系。通常表示為：G(V,E)。其中G表示一個圖，V是圖G中的頂點集合，E是圖G中邊的集合。那么如何存儲圖呢？下面我們一起從源碼出發(fā)，解析數(shù)據(jù)結(jié)構(gòu)中圖的存儲方式。其實數(shù)據(jù)結(jié)構(gòu)中圖的存儲方式分為兩種：利用鄰接矩陣，利用鄰接表。下面我們詳細(xì)看一下關(guān)于這兩種圖的存儲方式

一、利用鄰接矩陣

由定義我們可以知道，圖是由兩部分組成，頂點和邊，頂點和邊的連接，確定了圖的邏輯關(guān)系，所以圖的存儲，其中它的頂點需要存儲，邊與邊的連接信息也要存儲。頂點的信息，可以使用一維數(shù)組進(jìn)行存儲。邊的信息，存在這多對多的邏輯關(guān)系，那么可以使用二維數(shù)據(jù)進(jìn)行存儲。鄰接矩陣的存儲，其實就是順序存儲的方式。

鄰接矩陣存儲實現(xiàn)思路：

1.確定頂點數(shù)

2.讀取頂點信息

3.初始化鄰接矩陣

4.讀入邊的信息

5.循環(huán)打印

鄰接矩陣存儲圖的數(shù)據(jù)結(jié)構(gòu)：

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define MAXVEX 100 /* 最大頂點數(shù)，應(yīng)由用戶定義 */

#define INFINITYC 0

typedef int Status;    /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */

typedef char VertexType; /* 頂點類型應(yīng)由用戶定義  */

typedef int EdgeType; /* 邊上的權(quán)值類型應(yīng)由用戶定義 */

typedef struct

{

    VertexType vexs[MAXVEX]; /* 頂點表 */

    EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣，可看作邊表 */

    int numNodes, numEdges; /* 圖中當(dāng)前的頂點數(shù)和邊數(shù)  */

}MGraph;

存儲部分

void CreateMGraph(MGraph *G){

    int i,j,k,w;

    printf("輸入頂點數(shù)和邊數(shù)\n");

    scanf("%d,%d",&G->numNodes,&G->numEdges);

    printf("頂點數(shù)：%d,邊數(shù)：%d\n",G->numNodes,G->numEdges);

    // 輸入頂點信息，組成頂點表

    for (i = 0; i<=G->numNodes; i++) {

        scanf("%c",&G->vexs[i]);

    }

    // 初始化鄰接矩陣

    for (i = 0; i<=G->numNodes; i++) {

        for (j = 0; j<=G->numNodes; j++) {

            G->arc[i][j] = INFINITYC; // 初始化0

        }

    }

    // 輸入邊表數(shù)據(jù)

    for (k = 0; k<G->numEdges; k++) {

        printf("輸入邊（vi,vj）上的下標(biāo)i，下標(biāo)j，權(quán)w\n");

        scanf("%d,%d,%d",&i,&j,&w);

        G->arc[i][j] = w;

        //如果是無向圖的話 矩陣對陣

        G->arc[j][i] = w;

    }

    // 打印鄰接矩陣

    printf("矩陣結(jié)果\n");

       for (int i = 0; i < G->numNodes; i++) {

           printf("\n");

           for (int j = 0; j < G->numNodes; j++) {

               printf("%d ",G->arc[i][j]);

           }

       }

       printf("\n");

}

/**

        輸入頂點數(shù)和邊數(shù)

         4,5

         頂點數(shù)：4,邊數(shù)：5

         abcd

         輸入邊（vi,vj）上的下標(biāo)i，下標(biāo)j，權(quán)w

         0,1,1

         輸入邊（vi,vj）上的下標(biāo)i，下標(biāo)j，權(quán)w

         0,2,1

         輸入邊（vi,vj）上的下標(biāo)i，下標(biāo)j，權(quán)w

         0,3,1

         輸入邊（vi,vj）上的下標(biāo)i，下標(biāo)j，權(quán)w

         1,2,1

         輸入邊（vi,vj）上的下標(biāo)i，下標(biāo)j，權(quán)w

         2,3,1

         矩陣結(jié)果

         0 1 1 1

         1 0 1 0

         1 1 0 1

         1 0 1 0

*/

二、利用鄰接表

同樣的，鄰接矩陣（順序存儲）的方式，可能會產(chǎn)生一些空白的空間，會造成空間的浪費，那么，我們嘗試使用鏈?zhǔn)降拇鎯Α?/p>

鄰接表中首先有一個一維數(shù)組，在這個一維數(shù)組中的某一個頂點數(shù)據(jù)，指向了一個鏈表。一維數(shù)組中的數(shù)據(jù)，類似鏈表中的表頭。鏈表中的數(shù)據(jù)都是與其有著頂點的連接邏輯關(guān)系的。

假如邊有權(quán)重，那么鄰接表的節(jié)點可以添加一個權(quán)重。

鄰接表存儲的數(shù)據(jù)結(jié)構(gòu)設(shè)計：

#define M 100

#define true 1

#define false 0

typedef char Element;

typedef int BOOL;

//鄰接表的節(jié)點

typedef struct Node{

    int adj_vex_index;  //弧頭的下標(biāo)，也就是被指向的下標(biāo)

    Element data;       //權(quán)重值

    struct Node * next; //邊指針

}EdgeNode;

//頂點節(jié)點表

typedef struct vNode{

    Element data;          //頂點的權(quán)值

    EdgeNode * firstedge;  //頂點下一個是誰？

}VertexNode, Adjlist[M];

//總圖的一些信息

typedef struct Graph{

    Adjlist adjlist;       //頂點表

    int arc_num;           //邊的個數(shù)

    int node_num;          //節(jié)點個數(shù)

    BOOL is_directed;      //是不是有向圖

}Graph, *GraphLink;

存儲部分

void creatGraph(GraphLink *g){

    int i,j,k;

    EdgeNode *p;

    //1. 頂點,邊,是否有向

    printf("輸入頂點數(shù)目,邊數(shù)和有向？：\n");

    scanf("%d %d %d", &(*g)->node_num, &(*g)->arc_num, &(*g)->is_directed);

    //2.頂點表

     printf("輸入頂點信息：\n");

    for (i = 0; i < (*g)->node_num; i++) {

        getchar();

        scanf("%c", &(*g)->adjlist[i].data);

        (*g)->adjlist[i].firstedge = NULL;

    }

    //3.錄入數(shù)據(jù)

    printf("輸入邊信息：\n");

    for (k = 0; k < (*g)->arc_num; k++){

        getchar();

        scanf("%d %d", &i, &j);

        //①新建一個節(jié)點

        p = (EdgeNode *)malloc(sizeof(EdgeNode));

        //②弧頭的下標(biāo)

        p->adj_vex_index = j;

        //③頭插法插進(jìn)去，插的時候要找到弧尾，那就是頂點數(shù)組的下標(biāo)i

        p->next = (*g)->adjlist[i].firstedge;

        //④將頂點數(shù)組[i].firstedge 設(shè)置為p

        (*g)->adjlist[i].firstedge = p;

        //j->i

        if(!(*g)->is_directed)

        {

            // j -----> i

            //①新建一個節(jié)點

            p = (EdgeNode *)malloc(sizeof(EdgeNode));

            //②弧頭的下標(biāo)i

            p->adj_vex_index = i;

            //③頭插法插進(jìn)去，插的時候要找到弧尾，那就是頂點數(shù)組的下標(biāo)i

            p->next = (*g)->adjlist[j].firstedge;

            //④將頂點數(shù)組[i].firstedge 設(shè)置為p

            (*g)->adjlist[j].firstedge = p;

        }

    }

}

圖作為一種非線性數(shù)據(jù)結(jié)構(gòu)，圖的存儲方式相對于線性數(shù)據(jù)結(jié)構(gòu)的存儲是比較復(fù)雜的，弄懂圖的存儲對我們掌握圖的數(shù)據(jù)結(jié)構(gòu)有著重要意義，沒有看明白的小伙伴可以到本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中觀看更加詳細(xì)的講解。