1.1 引言
1.1.1 什么是數據結構
數據結構包含兩方面的內容，其一是構成集合的數據元素，其二是數據元素之間存在的關系。數據結構也就是帶有結構的數據元素的集合，結構指的是數據元素之間的相互關系，即數據的組織形式。由此可見，計算機所處理的數據并不是數據的雜亂堆積，而是具有內在聯系的數據集合。如表1-1所示的成績表就是一個數據結構（線性表），其中每一行表示一個數據元素，表中的所有行構成了一個數據元素集合，數據元素之間具有線性結構關系（詳見第2章）。如圖1-1所示是一軟件公司員工職務組織結構圖，其中每一個方框表示一位員工的信息（如職工號、姓名、性別、年齡和電話等），即一個數據元素，全部員工的信息構成了一個數據元素集合，數據元素之間具有樹形結構關系（詳見第5章）。如圖1-2所示是城市交通示意圖，其中每一個頂點表示一座城市，即一個數據元素，全部頂點構成了一個數據元素集合，每一條邊表示兩座城市間的交通線路，之間的距離用邊上的值表示，數據元素之間具有圖結構關系（詳見第6章）。
表1-1 成績表
圖1-1 公司員工職務組織結構圖
圖1-2 城市交通示意圖
1.1.2 數據結構研究什么
數據結構可定義為一個二元組：Data_Structure=（D,R）
其中D是數據元素的有限集合，R是D上關系的有限集合。
數據結構具體應包括3個方面：數據的邏輯結構、數據的物理結構和數據的運算集合。
1.邏輯結構
數據的邏輯結構是指數據元素之間邏輯關系的描述。
根據數據元素之間關系的不同特性，有下列4種基本的邏輯結構，如圖1-3所示。
（1）集合結構。結構中的數據元素之間除了同屬于一個集合的關系外，無任何其他關系。
（2）線性結構。結構中的數據元素之間存在著一對一的線性關系。
（3）樹形結構。結構中的數據元素之間存在著一對多的層次關系。
（4）圖狀結構或網狀結構。結構中的數據元素之間存在著多對多的任意關系。
由于集合的關系非常松散，因此可以用其他的結構代替。本書所討論數據的邏輯結構如圖1-4所示。
圖1-3 4種基本邏輯結構
圖1-4 本書所討論數據的邏輯結構
2.存儲結構
存儲結構（又稱物理結構）是邏輯結構在計算機中的存儲映像，是邏輯結構在計算機中的實現（或存儲表示），它包括數據元素的表示和關系的表示。有數據結構Data_Structure=(D,R)，對于D中的每一個數據元素都對應有存儲空間中的一個單元，D中全部元素對應的存儲空間必須明顯或隱含地體現關系R。邏輯結構與存儲結構的關系為，存儲結構是邏輯結構的映像與元素本身的映像。邏輯結構是抽象，存儲結構是實現，兩者綜合起來建立了數據元素之間的結構關系。
數據元素之間的關系在計算機中有兩種不同的表示方法，即順序映像（順序存儲結構）與非順序映像（非順序存儲結構）。數據結構在計算機中的映像，包括數據元素映像和關系映像。關系映像在計算機中可用順序存儲結構或非順序存儲結構兩種不同方式來表示。
3.運算集合
討論數據結構的目的是為了在計算機中實現所需的操作，施加于數據元素之上的一組操作構成了數據的運算集合，因此在結構上的運算集合是數據結構很重要的組成部分。
以表1-1所示的成績表為例，該表的數據元素與數據元素之間是一種簡單的線性關系，所以邏輯結構采用線性表。存儲結構既可采用順序存儲結構，也可采用非順序存儲結構。對于成績表，當學生退學或轉出時要刪除相應的數據元素，轉入學生時要增加數據元素，發現成績輸入錯誤時要修改。這里的增加、刪除和修改就構成了數據的操作集合。
綜上所述，數據結構的內容可歸納為3個部分：邏輯結構、存儲結構和運算集合。按某種邏輯關系組織起來的一批數據，依一定的映像方式把它存放在計算機存儲器中，并在這些數據上定義一個運算的集合，就構成了一個數據結構。
《數據結構》是一門主要研究怎樣合理地組織數據，建立合適的數據結構，提高計算機執行程序所用的時、空效率的學科。數據結構課程不僅講授數據信息在計算機中的組織和表示方法，同時也訓練用高效的設計算法解決復雜問題的能力。《數據結構》屬于計算機專業的核心專業基礎課，對于程序設計者來說掌握該課程的知識是非常必要的，數據結構貫穿程序設計的始末，缺乏數據結構功底的人，很難設計出高水平的應用程序。