在不少編程人員的潛意識裏老是以爲數據結構知識彷佛沒什麼用，由於工做中彷佛曆來都沒有涉及到數據結構的什麼內容。我對這樣的認識只能報以呵呵~ 也難怪，其實有這些想法的同行在工做中的大部分都是如此走過來的：掌握幾種經常使用Web框架，好比SSH，而後不停的堆砌已有的API作一些對數據庫的增刪改查之類的簡單代碼設計，最後反正功能是實現了，是否設計無誤，效率又優，就幾乎沒有人去管了。也是，這樣的工做也基本涉及不到有用到數據結構知識去解決問題的地方。其實，有這樣想法人算不上真正的軟件開發者，或者層次還不深，由於數據結構是軟件開發中最基礎最重要的理論基礎。1. 爲何數據結構很重要 首先爲何要開發各類各樣的軟件，目的只有一個：就是利用計算機來爲人們處理各類數據並以必定的形式展示出來供用戶使用。隨着計算機的應用範圍的不斷擴大，計算機所須要處理的數據愈來愈複雜，而且規模愈來愈大，計算機所處理的數據已再也不是單純的數值數據，而更多的是非數值數據。 另外一方面，現實中須要處理的數據並非雜亂無章的，它們必定有內在的各類聯繫，但這須要算法設計人員去總結、概括、建模、而後抽象出一個具體的模型來表示—，咱們將這個模型成爲數據的邏輯結構。而後聰明的設計師再圍繞這個建立的邏輯結構總結設計出一套處理方法，這樣，數據有了，模型有了，算法有了，在理論上問題就能夠解決了。剩下的就應該交給計算機去作了，但以上都是基於邏輯上的設計，計算機纔不懂這些。因此接下來還須要對應的存儲結構來將要處理的數據先存儲到計算機中，再將那些處理邏輯（算法）用相應的代碼實現，計算機才能對數據進行有效的處理。 2. 什麼是數據結構數據結構：即人們抽象出來的描述現實世界實體的數學模型（非數值計算）及其上的操做（運算），在計算機上的表示和實現。數據結構就是指按必定的邏輯結構組成的一批數據，使用某種存儲結構將這批數據存儲於計算機中，並在這些數據上定義了一個運算集合。3. 數據類型數據類型：定義該類型涵蓋的數據的性質、取值範圍以及對數據所能進行的各類操做。程序中的每個數據都屬於一種數據類型，決定了數據的類型也就決定了數據的性質以及對數據進行的各類運算和操做，同時數據也受到類型的保護，確保對數據不能進行非法操做。高級程序設計語言一般預約義一些基本數據類型和構造數據類型。基本數據類型的值是單個的、不可分解的，它能夠直接參與該類型所容許的運算。構造數據類型是使用已有的基本數據類型和已定義的構造數據類型按照必定的語法規則組織起來的較複雜的數據類型。構造數據類型的值由若干元素組合而成，這些元素按某種結構組織在一塊兒。Java語言的基本數據類型有整數類型、浮點數類型、字符類型、布爾類型，構造數據類型（稱爲引用類型）有數組、類和接口。抽象數據類型（Abstract Data Type ,ADT）：是指一個數學模型以及定義在該模型上的一組操做。抽象數據類型和數據類型本質上是一個概念，它們都表現數據的抽象特徵。數據抽象是指「定義和實現相分離」，即將一個類型上的數據及操做的邏輯含義與具體的實現分離。程序設計語言提供的數據類型是抽象的，僅描述數據的特徵和對數據操做的語法規則，並無說明這些數據類型是如何實現的。程序設計語言實現了它預約義數據類型的各類操做，編程人員按照語言提供的規則使用數據類型，只考慮對數據執行什麼操做（作什麼），而沒必要考慮怎樣實現這些操做（怎樣作）。對於使用數據類型的用戶來講，數據類型實現了信息的隱蔽，即將一切用戶沒必要了解的細節都封裝在類型中。例如Java語言的類型-整數類型便是一個抽象數據類型，編程人員在使用整型時，並不須要知道其是如何實現的。另外一方面，抽象數據類型的範疇更廣，它再也不侷限於程序語言已定義並實現的數據類型（也可稱這類數據類型爲固有數據類型），還包括編程人員在設計軟件系統時本身定義的數據類型。如前所述，抽象數據類型的定義是由一個值域和定義在該值域上的一組操做組成，算法設計時，編程人員一般須要爲一些抽象出來的邏輯結構來自定義一個抽象數據類型，好比：爲線性表，棧，隊列，串，廣義表，二叉樹，樹，圖等自定義抽象類型。一種抽象數據類型描述一種數據結構的邏輯特性和操做，與該數據結構在計算機內存儲及實現無關。抽象數據類型的三要素：數據對象，數據關係，基本操做。在實際應用中，編程人員在使用自定義的抽象數據類型以前，必須實現這些抽象數據類型（在實現以前，還應該爲屬於數據類型的數據元素定義結點），才能使用它們。而實現抽象數據類型依賴於數據存儲結構。例如，線性表可分別採用順序存儲結構或鏈式存儲結構來實現。 在Java語言設計中，一般使用接口描述抽象數據類型，使用類實現借接口，即實現抽象數據類型中描述的操做。4. 數據的邏輯結構數據的邏輯結構是指數據元素之間的邏輯關係，用一個數據元素的集合（包括n>=0個數據元素）和定義在此集合上的若干關係來表示，常被簡稱爲數據結構。數據的邏輯結構是獨立於計算機的，它與數據在計算機中的存儲無關。數據的邏輯結構指數據元素之間的邏輯關係，分四種：集合，線性結構、樹形結構、圖狀結構。再具體一些：線性表，棧，隊列，串，廣義表，樹，圖等都是對現實實體的抽象出來的邏輯結構。 數據元素：是數據的基本單位，在計算機程序中一般作爲一個總體進行考慮和處理。數據元素能夠是一個不可分割的原子項，也能夠由多個數據項組成。數據項是數據元素中有獨立含義的、不可分割的最小標示單位。例如，一個整數、一個字符都是原子項；一個學生的數據元素由學號、姓名、性別和出生日期等多個數據項組成。在計算機存儲時，咱們能夠用一個由若干位組合起來造成的一個位串標示一個數據元素（如用一個字長的位串表示一個整數，用8位二進制數表示一個字符等），一般呈這個位串爲元素（element）或結點（node）。當數據元素由若干數據項組成時，位串中對應與各個數據項的子位串稱爲數據域。在編程語言中，好比Java，一個數據元素一般由一個類來描述。咱們知道在C語言和C＋＋語言中是用指針來實現鏈表結構的，因爲Java語言不提供指針，因此有人認爲在Java語言中不能實現鏈表，其實否則，Java語言比C和C＋＋更容易實現鏈表結構。Java語言中的對象引用其實是一個指針（本文中的指針均爲概念上的意義，而非語言提供的數據類型），因此咱們能夠編寫這樣的類來實現鏈表中的結點。 class Node
{
Object data;
Node next;//指向下一個結點
} 將數據域定義成Object類是由於Object類是廣義超類，任何類對象均可以給其賦值，增長了代碼的通用性。爲了使鏈表能夠被訪問還須要定義一個表頭，表頭必須包含指向第一個結點的指針和指向當前結點的指針。爲了便於在鏈表尾部增長結點，還能夠增長一指向鏈表尾部的指針，另外還能夠用一個域來表示鏈表的大小，當調用者想獲得鏈表的大小時，沒必要遍歷整個鏈表。 5. 數據的存儲結構但要對數據進行處理，就必須將數據存儲在計算機中。若是將數據在計算機中無規律地存儲，那麼在處理時是很是糟的，是沒有用的。試想一下，若是一本英漢字典中的單詞是隨意編排的，這本字典誰會用！ 數據結構在計算機中的表示（又稱映像）成爲數據的物理結構，又稱存儲結構。它包括數據元素在計算機中的表示和關係的表示。5.1 數據的基本存儲結構主要有4種：(1) 順序存儲：將邏輯上相鄰的結點存儲在一組連續的內存單元中，使得邏輯相鄰的結點必定是物理位置相鄰，元素在內存中的存儲次序與它們的邏輯次序相同。順序存儲一般用於存儲具備線性結構的數據，在高級程序設計語言中一般使用數組來實現。(2) 鏈式存儲：即便用若干地址分散的存儲單元存儲數據元素，邏輯上相鄰的數據元素在物理位置上不必定相鄰，數據元素之間的關係須要採用附加信息特別指定。一般，採用指針變量記載前驅或後繼元素的存儲地址，由數據域和地址域組成的一個結點表示一個數據元素，經過地址域把相互直接關聯的結點連接起來，結點間的連接關係提仔數據元素間的邏輯關係。(3) 索引存儲：在線性結構中，設開始結點的索引號爲1，其它結點的索引號等於其前繼結點的索引號加1，則每個結點都有惟一的索引號，索引號就是根據結點的索引號肯定該結點的存儲地址。(4) 散列（哈希）存儲：散列存儲的思想是構造一個從集合K到存儲區域M的一個函數h，該函數的定義域爲K，值域爲M，K中的每一個結點ki在計算機中的存儲地址由h(ki)肯定。其中，順序存儲結構和鏈式存儲結構是兩種最基本、最經常使用的存儲結構。除此以外，將順序存儲結構和鏈式存儲結構進行組合，還能夠構造出一些更加複雜的存儲結構。5.2 一些常見的數據結構（即邏輯結構）對應的存儲結構線性表的存儲：線性表能夠採用順序存儲結構和鏈式存儲結構。採用順序存儲結構的鏈表稱爲順序表，順序表一般使用採用數組存儲其數據元素，將線性表的數據元素順序存放在數組中，數據元素在數組中的物理順序與線性表中的元素的順序關係徹底相同。採用鏈式存儲的線性表成爲鏈表。棧的存儲：順序存儲和鏈式存儲兩種，分別成爲順序棧和鏈棧；隊列的存儲：隊列通常採用鏈式存儲，其中循環隊列可採用順序存儲；數組的存儲結構：順序存儲，其中二維數組包括以行序爲主序存儲和以以列序爲主序存儲； 數組是順序存儲的隨機存儲結構，佔用一組連續的存儲單元，經過下標識別元素，元素地址是下標的線性函數。在程序設計語言中，數組已被實現爲一種構造數據類型，程序語言中的整數類型，字符類型等都是基本數據類型，經過一個變量表示一個數據，這種變量稱爲簡單變量。在實際應用中，常常須要處理具備相同性質的一批數據。例如要處理100個學生的考試成績，若是要使用簡單變量，將須要100個不一樣的變量，極爲不便，爲此，好比在java中，可使用數組來存儲着一批具備相同性質的數據。數組一旦佔用一片存儲空間，這片存儲空間的地址和長度就是肯定的，不能更改。所以，數組只能進行賦值、取值兩種隨機存取操做，不能進行插入、刪除操做。字符串的存儲結構： 1. 定長順序存儲：相似於線性表的順序存儲結構，用一組地址連續的存儲單元存儲串值的字符序列（好比使用一維數組存儲）。 2. 堆分配存儲：仍以一組地址連續的存儲單元存儲串值的字符序列，但它們的存儲空間是在程序執行過程當中動態分配而得。 3. 串的塊鏈存儲：可用鏈表的方式存儲串值。掌握：數組，字符數組，字符串數組，ArrayList(動態數組)、LinkedList類、String類 、StringBuffer類 、StringBuilder類的區別和使用方法。矩陣的存儲結構：高級語言編程時，一般都是用二位數組來存儲矩陣元。矩陣存儲時，咱們感興趣的不是矩陣自己，而是如何存儲矩陣的元，從而使矩陣的各類運算可以有效的進行。矩陣式不少科學與工程計算問題中常常研究的數學對象。廣義表的存儲結構：一般採用鏈式存儲結構。樹的經常使用存儲結構有：雙親表示法存儲、孩子鏈表存儲、孩子兄弟表示法（又稱二叉鏈表表示法）存儲等，這幾種存儲方法都屬於鏈式存儲的不一樣方式。二叉樹的經常使用存儲結構：適用於徹底二叉樹的順序存儲結構、二叉鏈表存儲、三叉鏈表存儲法兩種鏈式存儲結構。圖的經常使用存儲結構有：鄰接矩陣表示法存儲（數組表示法）、鄰接表法、十字鏈表法、鄰接多重表；其中鄰接表法和十字鏈表法、鄰接多重表都是圖的不一樣鏈式存儲方法。5.3數據的操做（運算集合）數據操做指對一種數據結構中的數據元素進行各類運算或處理。每種數據結構都有一組數據操做。對於一批數據，數據的運算是定義在數據的邏輯結構之上的，而運算的具體實現就依賴於數據的存儲結構。數據的運算集合要視狀況而定，通常而言，數據的運算包括插入、刪除、更新、檢索、遍歷、排序等。初始化、判斷是否爲空狀態、統計數據元素個數插入：在一個結構中增長一個新的結點。刪除：在一個結構刪除一個結點。更新：更新一個結構中制定位置的結點。檢索：在一個結構中查找知足條件的結點。輸出：將一個結構中全部結點的值打印、輸出。排序：將一個結構中全部結點按某種順序從新排列。java