1.2　數據結構的基本概念

考點1　概　述

（1）數據處理概述

①定義

數據處理是指對數據集合中的各元素以各種方式進行運算，包括插入、刪除、查找、更改等運算，也包括對數據元素進行分析。

②關鍵問題

大量數據元素在計算機中如何組織，以便提高數據處理的效率，從而節省計算機的存儲空間，這是進行數據結構處理的關鍵問題。

（2）數據結構研究概述

①研究問題

a．數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構；

b．在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構；

c．對各種數據結構進行的運算。

②研究目的

數據結構研究和討論上述3個問題的主要目的在于提高數據處理效率，包括：

a．提高數據處理的速度；

b．盡量節省在數據處理過程中所占用的計算機存儲空間。

考點2　數據結構的概念

（1）數據結構的定義

數據結構是指相互有關聯的數據元素的集合，即它是反映數據元素之間關系的數據元素集合的表示。簡言之，數據結構是指帶有結構的數據元素的集合，這里的“結構”指數據元素之間的前后件關系。一個數據結構應包含以下兩方面內容：

①表述數據元素的信息；

②表示各數據元素之間的前后件關系。

（2）數據的邏輯結構

①定義

數據的邏輯結構是指反映數據元素之間邏輯關系的數據結構。

②要素：

a．數據元素的集合，通常記為D；

b．D上的關系，通常記為R，它反映了D中各數據元素之間的前后件關系。

③表示

一個數據結構B可表示為：B＝（D，R）。

為反映D中各數據元素之間的前后件關系，一般用二元組來表示。

（3）數據的存儲結構

①定義

數據的存儲結構，也稱數據的物理結構，是指數據邏輯結構在計算機存儲空間中的存放形式。在數據的存儲結構中，不僅要存放各數據元素的信息，而且要存放各數據元素之間的前后件信息。

②常用的存儲結構：

a．順序；

b．鏈接；

c．索引。

采用不同的存儲結構，數據處理的效率是不同的。

【真題演練】

下列敘述中正確的是（　　）。[2014年3月真題]

A．有且只有一個根結點的數據結構一定是線性結構

B．每一個結點最多有一個前件也最多有一個后件的數據結構一定是線性結構

C．有且只有一個根結點的數據結構一定是非線性結構

D．有且只有一個根結點的數據結構可能是線性結構，也可能是非線性結構

【答案】D

【解析】邏輯結構分為線性結構和非線性結構，線性結構的特征有：①集合中必存在唯一的一個“第一個元素”；②集合中必存在唯一的一個“最后的元素”；③除第一元素之外，其他數據元素均有唯一的“前驅”；④除最后元素之外，其他數據元素均有唯一的“后繼”。D項正確，如樹形結構只有一個根結點，為非線性結構。答案選擇D選項。

考點3　數據結構的圖形表示

（1）在數據結構的圖形表示中，數據集合D中每個元素用中間標有元素值的方框表示，稱為數據結點（簡稱結點）；對關系R中的每一個二元組，用一條有向線段從前件結點指向后件結點。

（2）在數據結構中，沒有前件的結點稱為根結點，沒有后件的結點稱為終端結點（也稱葉子結點），其余結點都稱為內部結點。

（3）數據結構中的元素結點可能是在動態變化的，這種變化體現在結點數量的增減以及各結點之間的前后件關系的動態變化上。

考點4　線性結構與非線性結構

根據數據結構中各數據元素之間的前后件關系的復雜程度，可將數據結構分為：

（1）線性結構（線性表）

一個非空的數據結構滿足下列兩個條件時，稱其為線性結構：

①有且只有一個根結點；

②每個結點最多只有一個前件，也最多只有一個后件。

線性結構中插入或刪除任何一個結點還應是線性結構，如果不滿足這個條件就不能稱之為線性結構。

（2）非線性結構

如果一個數據結構不是線性結構，則稱之為非線性結構。

注：線性結構與非線性結構都可以是空的數據結構。一個空的數據結構屬于線性結構還是非線性結構，需要根據對該數據結構的運算是否按照線性結構的規則來處理進行判斷。