1.2　數據結構的基本概念

視頻二維碼（掃碼觀看）

數據結構作為計算機的一門學科，主要研究和討論以下三個方面的問題：

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

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

（3）對各種數據結構進行的運算。

討論以上問題的目的：

（1）提高數據處理的速度；

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

一、什么是數據結構

【定義】數據結構是指相互有關聯的數據元素的集合。

數據元素具有廣泛的含義：

描述一年四季的季節名：春、夏、秋、冬

表示數值的各個數：18、11、35、23、16…

表示家庭成員的各成員名：父親、兒子、女兒

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

【注意】作為某種處理，其中的數據元素一般具有某種共同特征，一般情況下，在具有相同特征的數據元素集合中，各個數據元素之間存在有某種關系，這種關系反映了該集合中的數據元素所固有的一種結構。

1數據的邏輯結構

（1）定義

反映數據元素之間邏輯關系的數據結構。一個數據結構應包含以下兩方面的信息：

①表示數據元素的信息；

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

（2）數據的邏輯結構有兩個要素：

一是數據元素的集合，通常記為D；

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

即一個數據結構可以表示成B＝（D，R）。

【例4】一年四季的數據結構可以表示成

B＝（D，R）

D＝{春，夏，秋，冬}

R＝{（春，夏），（夏，秋），（秋，冬）}

2數據的存儲結構

定義：數據的邏輯結構在計算機存儲空間中的存放形式。

【注意】

①各數據元素在計算機存儲空間中的位置關系與它們的邏輯關系不一定是相同的，而且一般也不可能相同。

②在數據的存儲結構中，不僅要存放各數據元素的信息，還需要存放各數據元素之間的前后件關系的信息。

③常用的存儲結構有順序、鏈接、索引等存儲結構。

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

二、數據結構的圖形表示

一個數據結構除了用二元關系表示外，還可以直觀地用圖形表示。

（1）對于數據集合D中的每一個數據元素用中間標有元素值的方框表示，一般稱之為數據結點，并簡稱為結點；

（2）對于關系R中的每一個二元組，用一條有向線段從前件結點指向后件結點，有時箭頭可省去。

圖1-1　一年四季數據結構的圖形表示圖（線性）

圖1-2　家庭成員間關系數據結構的圖形表示（樹型結構）

【考題】下列敘述中正確的是（　　）。

A．線性表是線性結構

B．棧與隊列是非線性結構

C．循環鏈表是非線性結構

D．二叉樹是線性結構

【答案】A

【解析】選項A正確；選項B，棧和隊列都是線性結構，二者區別是，棧只允許在一端插入和刪除，隊列只允許在一端插入，在另一端刪除；選項C，循環鏈表是線性表的鏈式存儲結構；選項D，二叉樹是一種典型的非線性結構。

三、線性結構與非線性結構

根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。

如果一個非空的數據結構滿足下列兩個條件：

（1）有且只有一個根結點；

（2）每一個結點最多有一個前件，也最多有一個后件。

則稱該數據結構為線性結構，線性結構又稱線性表。

【注意】在一個線性結構中插入或刪除任何一個結點后還應是線性結構。如果一個數據結構不是線性結構，則稱之為非線性結構。

【考題】設數據集合為D＝{1，3，5，7，9}，D上的關系為R。下列數據結構B＝（D，R）中為非線性結構的是（　　）。

A．R＝{（5，1），（7，9），（1，7），（9，3）}

B．R＝{（9，7），（1，3），（7，1），（3，5）}

C．R＝{（1，9），（9，7），（7，5），（5，3）}

D．R＝{（1，3），（3，5），（5，9）}

【答案】D

【解析】如果一個非空的數據結構滿足下列兩個條件：①有且只有一個根結點；②每一個結點最多有一個前件，也最多有一個后件。則該數據結構為線性結構。

選項A：5是根結點，5的后件是1，1的后件是7，7的后件是9，9的后件是3，故選項A是線性結構；

選項B：9是根結點，9的后件是7，7的后件是1，1的后件是3，3的后件是5，故選項B是線性結構；

選項C：1是根結點，1的后件是9，9的后件是7，7的后件是5，5的后件是3，故選項C是線性結構；

選項D：1是根結點，1的后件是3，3的后件是5，5的后件是9，7也是根結點，沒有前件也沒有后件，線性數據結構第一個條件不滿足，故選項D是非線性結構，即選項D正確。