資料有有線性結構、樹形結構、圖狀結構和集合四種邏輯結構,那麼它們是如何存儲的呢?
資料結構的存儲結構有兩種,分别是順序存儲和鍊式存儲。順序存儲的特點是借助元素在存儲器中的相對位置來表示資料元素之間的邏輯關系;鍊式存儲的特點是借助指針表示資料元素質檢單邏輯關系。
1.線性結構:結構中的元素之間存在着一對一的線性關系。
如圖為一個線性結構,那麼它的順序存儲和鍊式存儲如何呢?如下圖:
順序結構 鍊式結構
線性結構如數組的存法,按一定順序存放;而鍊式結構如連結清單的存法,結點可以任意存放,如上圖,是以要用next相連,以保證每一個結點都有唯一确定的前驅和後繼。
2.樹形結構:結構中的資料元素之間存在着一對一的線性關系。(這裡我們以二叉樹為例)
如圖是一個簡單的二叉樹,其中6号結點不存在,其順序存儲如下圖:
因為是二叉樹,是以我們可以認為每個結點都有兩個“孩子”,不存在的可以用“空”來表示(上圖中的6号就是空),這樣就可以用一行表示一個完整的二叉樹,并且知道每一個結點所對應的前驅和後繼。
至此我們就可以發現:
2,3對應的前驅是1;
4,5對應的前驅是2;
6,7對應的前驅是3。
這樣我們就可以推導出幾個關系:
若結點為i,則i的前驅是i/2;i的左後繼是2i;i的右後繼是2i+1。
下面再給大家一個例子供參考(其中符号∧代表空,也可用null表示):
那麼二叉樹的鍊式結構又如何呢?
二叉樹的結點結構如下圖:
LChild域指向該結點的左孩子,Data域記錄該結點的資料,RChild域指向該結點的右孩子。二叉樹的鍊式結構存儲如下圖所示:
我們可以讓頭指針指向A,則二叉連結清單結點結構的描述如下:
typedef struct Node { DataType date; Struct Node *Lchild; Struct Node *Rchild; }BiTNode, *BiTree;
為了友善通路某結點的雙親,還可以給連結清單結點增加一個雙親字段parent,用來指向其雙親結點。每個結點由四個域組成,其結點結構為:
在實際應用中,要根據二叉樹的形态和具體要進行的操作來選擇決定采用哪種存儲結構。
3.圖狀結構:結構中的資料元素之間存在着多對多的任意關系。
以無向圖為例,如下圖所示:
則可得出關系為:
A: (A,B) (A,C)
B:(B,A) (B,C) (B,D)
C:(C,A) (C,B) (C,D)
D: (D,B) (D,C)
以數組的存儲方式(鄰接矩陣)進行存儲可得:
其中“1”代表存在關系,“0”代表不存在關系。
将其轉化為鍊式的形式如下圖:
對其鍊式結構我們可采用指針數組(鄰接表)的方式來連接配接單連結清單,其中的字母應換成相應的數組下标,如下圖:
鄰接矩陣是不錯的一種圖存儲結構,但是,對于邊數相對頂點較少的圖,這種結構存在對存儲空間的極大浪費。是以,找到一種數組與連結清單相結合的存儲方法稱為鄰接表。圖中每個頂點的所有鄰接點構成一個線性表,由于鄰接點的個數不定,是以,用單連結清單存儲,無向圖稱為頂點的邊表,有向圖則稱為頂點作為弧尾的出邊表。
有向圖情況類似,大家可以自己試一試。而在有向圖中,對于帶權值的網圖,可以在邊表結點定義中再增加一個資料域,存儲權值資訊即可。如下圖:
轉載于:https://www.cnblogs.com/adamjwh/p/5829604.html