數據存儲表示法

數據是信息的載體。它能夠被計算機識別、存儲和加工處理，是電腦程式加工的"原料"。在數據結構中，數據的存儲結構一般分為線性結構和非線性結構。數據存儲表示法一般是指數據的存儲結構表示方法。一般為了表示數據之間的關係，會採用不同的表示法。

基本介紹

• 中文名：數據存儲表示法
• 外文名：Data Storage Representation
• 學科：計算機科學
• 定義：數據的存儲結構表示方法
• 目的：數據之間的關係
• 領域：數據結構

簡介

數據存儲對象包括數據流在加工過程中產生的臨時檔案或加工過程中需要查找的信息。數據以某種格式記錄在計算機內部或外部存儲介質上。數據存儲要命名，這種命名要反映信息特徵的組成含義。數據流反映了系統中流動的數據，表現出動態數據的特徵；數據存儲反映系統中靜止的數據，表現出靜態數據的特徵。

在計算機科學中，數據存儲表示法一般是指數據的存儲結構表示方法，來表示數據之間的聯繫。例如稀疏矩陣，有鄰接矩陣與鄰接表兩種存儲表示法來表示數據之間的關係。

數據存儲結構

數據結構

數據結構指的是數據之間的相互關係，即數據的組織形式。

1．數據結構一般包括以下三方面內容：

① 數據元素之間的邏輯關係，也稱數據的邏輯結構（Logical Structure）；數據的邏輯結構是從邏輯關係上描述數據，與數據的存儲無關，是獨立於計算機的。數據的邏輯結構可以看作是從具體問題抽象出來的數學模型。

② 數據元素及其關係在計算機存儲器內的表示，稱為數據的存儲結構（Storage Structure）；數據的存儲結構是邏輯結構用計算機語言的實現（亦稱為映象），它依賴於計算機語言。對機器語言而言，存儲結構是具體的。一般，只在高級語言的層次上討論存儲結構。

③ 數據的運算，即對數據施加的操作。數據的運算定義在數據的邏輯結構上，每種邏輯結構都有一個運算的集合。最常用的檢索、插入、刪除、更新、排序等運算實際上只是在抽象的數據上所施加的一系列抽象的操作。所謂抽象的操作，是指我們只知道這些操作是"做什麼"，而無須考慮"如何做"。只有確定了存儲結構之後，才考慮如何具體實現這些運算。

分類

在不產生混淆的前提下，常將數據的邏輯結構簡稱為數據結構。數據的邏輯結構有兩大類：

（1）線性結構
線性結構的邏輯特徵是：若結構是非空集，則有且僅有一個開始結點和一個終端結點，並且所有結點都最多只有一個直接前趨和一個直接後繼。
線性表是一個典型的線性結構。棧、佇列、串等都是線性結構。

（2）非線性結構
非線性結構的邏輯特徵是：一個結點可能有多個直接前趨和直接後繼。數組、廣義表、樹和圖等數據結構都是非線性結構。

樹的表示法

1、雙親表示法

在樹中除了根結點以外，其他結點都會僅有一個雙親結點。

將數組中的下標用於表示雙親結點的位置或者是左孩子或者右孩子或是由兄弟。當然，這樣的結構依賴於存儲的順序是採用的是層序遍歷。

2、孩子的多重鍊表表示法

這種表示方法分2種，一種是多重鍊表表示法，即用樹的度就表示一個節點指針域的個數，這樣很大程度上浪費了記憶體資源。第二種是孩子鍊表表示法，即一個節點的指針域的個數和其孩子的個數（該節點的度）相等。

3、孩子鍊表表示法

用多個單鍊表表示孩子，在同一個單鍊表中的孩子有著共同的雙親。

有孩子鍊表表示法衍生出來的雙親孩子表示法，既是將雙親表示法和孩子鍊表表示法相結合起來了，將孩子與雙親，雙親與孩子之間的關係展示出來，可以不用遍歷便可尋找孩子的雙親或者雙親的孩子。

4、孩子兄弟表示法

存儲區域分三塊，中間那塊存儲結點的數據，左邊指向該節點的第一個孩子，右邊指向該節點的右兄弟。

圖的表示法

鄰接矩陣:

有向圖的鄰接矩陣

具有n個頂點的有向圖可以用一個n′n的方形矩陣表示。假設該矩陣的名稱為M，則當<vi,vj>是該有向圖中的一條弧時，M[i,j]=1；否則M[i,j]=0。第i個頂點的出度為矩陣中第i行中"1"的個數；入度為第i列中"1"的個數，並且有向圖弧的條數等於矩陣中"1"的個數。

無向圖的鄰接矩陣

具有n個頂點的無向圖也可以用一個n′n的方形矩陣表示。假設該矩陣的名稱為M，則當（vi,vj）是該無向圖中的一條邊時，M[i,j]=M[j,i]=1；否則，M[i,j]=M[j,j]=0。第i個頂點的度為矩陣中第i 行中"1"的個數或第i列中"1"的個數。圖中邊的數目等於矩陣中"1"的個數的一半，這是因為每條邊在矩陣中描述了兩次。

在C 語言中，實現鄰接矩陣表示法的類型定義如下所示：

#define MAX_VERTEX_NUM 20typedef struct graph{Elemtypeelem [MAX_VERTEX_NUM][MAX_VERTEX_NUM];int n;}Graph;

鄰接表

邊結點的結構為：

adjvex是該邊或弧依附的頂點在數組中的下標，next是指向下一條邊或弧結點的指針

elem是頂點內容，firstedge是指向第一條邊或弧結點的指針。

在C語言中，實現鄰接表表示法的類型定義如下所示：

#defineMAX_VERTEX_NUM30//最大頂點個數typestructEdgeLinklist{//邊結點intadjvex;structEdgeLinklist*next;}EdgeLinklist;typedefstructVexLinklist{//頂點結點Elemtypeelem;EdgeLinklist*firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];

創建有向圖鄰接表

voidCreate_adj(AdjListadj,intn){for(i=0;i<n;i++){//初始化頂點數組 scanf(&adj.elem);adj.firstedge=NULL;}scanf(&i,&j);//輸入弧 while(i){s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));//創建新的弧結點s->adgvex=j-1;s->next=adj[i-1].firstedge;//將新的弧結點插入到相應的位置adj[i-1].firstegde=s; scanf(&i,&j);//輸入下一條弧}}

創建無向圖的鄰接表

voidCreate_adj(AdjListadj,intn){for(i=0;i<n;i++){//初始化鄰接表scanf(&adj.elem);adj.firstedge=NULL;}scanf(&i,&j);//輸入邊 while(i){s1=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s1->adgvex=j-1;s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s2->adgvex=i-1;s1->next=adj[i-1].firstedge;adj[i-1].firstegde=s1;s2->next=adj[j-1].firstedge;adj[j-1].firstegde=s2; scanf(&i,&j);}}