數據結構大學教程
The Complete Data Structure Training Course
第一章 數據結構及其基本概念
Chapter Data Structure and Its Basic Concepts
什麼是數據結構(What is Data Structure)
如果你問一個木匠學徒你工作的工具要用什麼他可能會回答你我只要一把錘子和一個鋸但是如果你去問一個老木工或者是大師級的建築師他會告訴你我需要一些精確的工具由於計算機所解決的問題都是從生活中抽象出來的問題其復雜性不言而喻所以我們需要這樣精確有效的工具去解決現實生活中的復雜問題算法數據結構程序設計語言都是這樣的工具數據結構是信息的組織方式對於相同的算法用不同的數據結構表示其中的抽象數據類型會造成不同的執行效率這就有必要研究各種抽象數據類型用不同的數據結構表示的效率差異以及其適用場合
[一]何謂數據結構(What is Data Structure)
數據結構是在整個計算機科學與技術領域上廣泛被使用的術語它用來反映一個數據的內部構成即一個數據由哪些成分數據構成以什麼方式構成呈什麼結構數據結構有邏輯上的數據結構和物理上的數據結構之分邏輯上的數據結構反映成分數據之間的邏輯關系而物理上的數據結構反映成分數據在計算機內部的存儲安排數據結構是信息的一種組織方式好的數據結構可以提高算法的效率它通常與一組算法的集合相對應通過這組算法集合可以對數據結構中的數據進行某種操作從學科角度來講數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科
[二]數據結構學科的研究對象 (The Object of Data Structure Research)
數據結構作為一門學科主要研究數據的各種邏輯結構和存儲結構以及對數據的各種操作因此主要有三個方面的內容數據的邏輯結構;數據的物理存儲結構;對數據的操作(即算法)通常算法的設計取決於數據的邏輯結構算法的實現取決於數據的物理存儲結構數據結構的研究不僅涉及到計算機硬件的研究比如存儲裝置和存取方法而且解決編譯原理操作系統數據庫系統的數據元素在存儲器中的分配問題的重要基礎
基本概念與學科術語(Basic Concepts and Terminologies)
數據(Data):是一個集合的概念是對客觀事物的符號表示在計算機科學中是指所有能被輸入到計算機中並被計算機處理的符號的總稱是計算機處理的信息的某種特定的符號表示形式
數據元素(Data Element):是數據的基本單位數據中的一個個體又稱為記錄或者表目
數據項(Data Item)數據的不可分割的最小單位數據元素是數據項的集合
數據對象(Data Object)是性質相同的數據元素的集合是數據的一個子集
[總結]
數據項組成數據元素數據元素組成數據對象數據對象組成數據
數據結構(Data Structure)是相互之間存在一種或多種特定關系的數據元素的集合它包括三個方面數據元素的邏輯結構存儲結構和相適應的運算(操作)
數據元素之間的邏輯關系被稱為數據元素的邏輯結構可以用一個二元組表示
Data_Structure = (D S) // Data_Structure= (Datapart LogicStructurePart)
這裡D是數據元素的集合S是定義在D(或其他集合)上的關系的集合
S = { R │ R : D×D×}
數據的邏輯結構可歸結為以下四類:
()集合結構
結構中的數據元素之間除了同屬於一個集合的關系外別無其他關系
()線性結構
結構中的數據元素之間存在一個對一個的前趨後繼關系
在此種結構下
有且僅有一個元素無前趨元素
有且僅有一個元素無後繼元素
其余任何一個元素均有且僅有一個前趨有且僅有一個後繼元素
()樹形結構
結構中的數據元素之間存在一個對多個的關系
任何一個節點最多有一個前趨可以有多個後繼是一種典型的非線性結構
()圖狀結構(網狀結構)
結構中的數據元素之間存在多個對多個的關系
這種結構的特征是任何一個元素可以有多個前趨也可以有多個後繼是一種多對多的前趨後繼關系
表和樹是最常用的兩種高效數據結構許多高效的算法可以用這兩種數據結構來設計實現表是線性結構的(全序關系)樹(偏序或層次關系)和圖(局部有序(weak/local orders))是非線性結構
數據結構在計算機中的表示(又稱為映像)稱為數據的存儲結構(物理結構)
數據結構的物理結構是指邏輯結構的存儲映像(image)數據結構 DS 的物理結構 P 對應於從 DS 的數據元素到存儲區M(維護著邏輯結構S)的一個映射
PDS) > M
存儲器模型一個存儲器 M 是一系列固定大小的存儲單元每個單元 U 有一個唯一的地址 A(U)該地址被連續地編碼每個單元 U 有一個唯一的後繼單元 U=succ(U)
P 的四種基本映射模型順序(sequential)鏈接(linked)索引(indexed)和散列(hashing)映射因此我們至少可以得到×種可能的物理數據結構
sequential (sets)
linked lists
indexed trees
hashing
graphs
需要指出的是並不是所有的可能組合都合理
數據結構DS上的操作所有的定義在DS上的操作在改變數據元素(節點)或節點的域時必須保持DS的邏輯和物理結構
DS上的基本操作任何其他對DS的高級操作都可以用這些基本操作來實現最好將DS和他的所有基本操作看作一個整體——稱之為模塊(model)我們可以進一步將該模塊抽象為數據類型(其中DS的存儲結構被表示為私有成員基本操作被表示為公共方法)稱之為ADT(即是抽象數據類型Abstract Data Type指一個數學模型以及定義在該模型上的一組操作)
ADT按照其值的不同特性分為下列三種類型
原子類型(Atomic Data Type)變量是不帶結構的不可分解的
固定聚合類型(Fixedaggregate Data Type)其值由確定數目的成分按照某種結構組成
可變聚合類型(VariableAggregate Data Type)值的成分的數目不確定
抽象數據類型的描述方法
抽象數據類型可用(DSP)三元組表示
其中D是數據對象S是D上的關系集P是對D的基本操作集
ADT 抽象數據類型名 {
數據對象〈數據對象的定義〉
數據關系〈數據關系的定義〉
基本操作〈基本操作的定義〉
} ADT 抽象數據類型名
其中數據對象和數據關系的定義用偽碼描述基本操作的定義格式為
基本操作名(參數表)
初始條件〈初始條件描述〉
操作結果〈操作結果描述〉
基本操作有兩種參數賦值參數只為操作提供輸入值;引用參數以&打頭 除可提供輸入值外還將返回操作結果初始條件描述了操作執行之前數據結構和參數應滿足的條件若不滿足則操作失敗並返回相應出錯信息操作結果說明了操作正常完成之後數據結構的變化狀況和應返回的結果若初始條件為空則將其省略需要注意的是抽象數據類型需要通過固有數據類型(高級編程語言中已實現的數據類型)來實現
順便提一句多形數據類型(Polymorphic Data Type)是指值的成分不確定的數據類型不過這個不太多見或者是可以用ADT表示所以我們在今後的章節再論述
好的和壞的DS如果一個DS可以通過某種線性規則被轉化為線性的DS(例如線性表)則稱它為好的DS好的DS通常對應於好的(高效的)算法這是由計算機的計算能力決定的因為計算機本質上只能存取邏輯連續的內存單元因此如何沒有線性化的結構邏輯上是不可計算的比如對一個圖進行操作要訪問圖的所有結點則必須按照某種順序來依次訪問所有節點(要形成一個偏序)必須通過某種方式將圖固有的非線性結構轉化為線性結構才能對圖進行操作
樹是好的DS——它有非常簡單而高效的線性化規則因此可以利用樹設計出許多非常高效的算法樹的實現和使用都很簡單但可以解決大量特殊的復雜問題因此樹是實際編程中最重要和最有用的一種數據結構樹的結構本質上有遞歸的性質——每一個葉節點可以被一棵子樹所替代反之亦然實際上每一種遞歸的結構都可以被轉化為(或等價於)樹形結構說到遞歸在北京大學的數據結構課程裡面有個老師經常說不懂遞歸就不算北大計算機系的學生這樣看來足以從側面說明書的結構的重要性
[] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23999.html
