2011計算機等考二級公共基礎知識講義：第1章(2)

　　點擊進入：2011計算機等考二級公共基礎知識講義匯總>>

　　1.2 數(shù)據(jù)結構的基本概念

　　1、數(shù)據(jù)結構是指相互有關聯(lián)的數(shù)據(jù)元素的集合。

　　2、數(shù)據(jù)結構主要研究和討論以下三個方面的問題：

　　(1)數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關系，即數(shù)據(jù)的邏輯結構。

　　數(shù)據(jù)的邏輯結構包含：1)表示數(shù)據(jù)元素的信息;2)表示各數(shù)據(jù)元素之間的前后件關系[wx1] 。

　　(2)在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關系，即數(shù)據(jù)的存儲結構。

　　數(shù)據(jù)的存儲結構有順序、鏈接、索引等。

　　1)順序存儲。它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結構。

　　2)鏈接存儲。它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結構。

　　3)索引存儲：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。

　　*：數(shù)據(jù)的邏輯結構反映數(shù)據(jù)元素之間的邏輯關系，數(shù)據(jù)的存儲結構(也稱數(shù)據(jù)的物理結構)是數(shù)據(jù)的邏輯結構在計算機存儲空間中的存放形式。同一種邏輯結構的數(shù)據(jù)可以采用不同的存儲結構，但影響數(shù)據(jù)處理效率。

　　(3)對各種數(shù)據(jù)結構進行的運算。

　　3、數(shù)據(jù)結構的圖形表示

　　一個數(shù)據(jù)結構除了用二元關系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結構的圖形表示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標有元素值的方框表示，一般稱之為數(shù)據(jù)結點，并簡稱為結點;為了進一步表示各數(shù)據(jù)元素之間的前后件關系，對于關系R中的每一個二元組，用一條有向線段從前件結點指向后件結點。

　　4、數(shù)據(jù)結構分為兩大類型：線性結構和非線性結構。

　　(1)線性結構(非空的數(shù)據(jù)結構)條件：1)有且只有一個根結點[wx2] ;2)每一個結點最多有一個前件，也最多有一個后件。

　　*：常見的線性結構有線性表、棧、隊列和線性鏈表等。

　　(2)非線性結構：不滿足線性結構條件的數(shù)據(jù)結構。

　　*：常見的非線性結構有樹、二叉樹和圖等。

　　注釋1：前后件關系：一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在某種關系(即聯(lián)系)，這種關系反映了該集合中的數(shù)據(jù)元素所固有的一種結構。在數(shù)據(jù)處理領域中，通常把數(shù)據(jù)元素之間這種固有的關系簡單地用前后件關系(即直接前驅與直接后繼關系)來描述。

　　注釋2：在數(shù)據(jù)結構中，沒有前件的結點稱為根結點。

　　相關推薦：

　　2011計算機等考二級公共基礎知識要點匯總

　　2010年9月計算機等級考試成績查詢時間匯總

　　2011年上半年計算機等級考試報名時間匯總