Nicklaus Wirth, 因?yàn)橐粋€(gè)著名的公式而獲得了圖靈獎(jiǎng)， 那就是"算法+數(shù)據(jù)結(jié)構(gòu)=程序"。由此可見(jiàn)數(shù)據(jù)結(jié)構(gòu)的重要性。本系列旨在探索數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)與原理，使得人人都懂?dāng)?shù)據(jù)結(jié)構(gòu)，都會(huì)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)。
本篇文章為數(shù)據(jù)結(jié)構(gòu)系列的開(kāi)篇， 目的很明確，讓大家了解數(shù)據(jù)結(jié)構(gòu)的概念與組成， 幫大家創(chuàng)建一個(gè)系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)知識(shí)體系。讓我們從0開(kāi)始，窺見(jiàn)數(shù)據(jù)結(jié)構(gòu)。
1.什么是數(shù)據(jù)結(jié)構(gòu)？
先引入百度百科的定義
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)[效率]。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索[算法]和[索引]技術(shù)有關(guān)。
從以上定義來(lái)看，數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的一種組織形式。我從這個(gè)定義提取了兩個(gè)重要的因素：
數(shù)據(jù)元素
特定關(guān)系
通俗定義，根據(jù)個(gè)人理解就是，數(shù)據(jù)結(jié)構(gòu)是若干數(shù)據(jù)，根據(jù)一定的關(guān)系組合在一起形成的組織形式。很抽象？我也這么覺(jué)得。下面從兩個(gè)重要的因素談起：
生活中任何一個(gè)事物都可以看作一個(gè)數(shù)據(jù)元素， 而且每個(gè)事物都可以隨意賦予一個(gè)代表數(shù)值；當(dāng)然平時(shí)我們以它實(shí)際代表的意義作為它的值。如一雙鞋， 一個(gè)風(fēng)扇， 一堆沙子，一個(gè)世界；我們分別可以把把它的值看作一雙（1），也可以看作兩只（2）；一臺(tái)（1），四個(gè)扇葉（4）；一堆（1）， 30萬(wàn)顆（300000）；一個(gè)（1）， 無(wú)窮大（正無(wú)窮）。從這個(gè)例子來(lái)看， 萬(wàn)物皆數(shù)字（數(shù)據(jù)元素），它的值你可以隨意想象（角度不同，值自然不同）。
生活中所有的事物都是有關(guān)系的，這個(gè)關(guān)系也可以稱之為數(shù)據(jù)元素的特定關(guān)系。還是上面的例子， 一雙鞋與單獨(dú)的兩只，一臺(tái)風(fēng)扇與四個(gè)扇葉， 一堆沙子與沙子顆粒， 一個(gè)世界與世界內(nèi)的一切。 兩只鞋得左腳與右腳， 風(fēng)扇與沙子， 鞋，風(fēng)扇，沙子與世界。萬(wàn)物皆存在關(guān)聯(lián)（沒(méi)有任何關(guān)系的兩個(gè)事物之間，也稱為一種關(guān)系）。
從以上說(shuō)法來(lái)看， 我們的世界可以看成一個(gè)巨大的數(shù)據(jù)結(jié)構(gòu)；世界內(nèi)的任何元素也可以看成一個(gè)數(shù)據(jù)結(jié)構(gòu)。還是那句話，角度不同。
可能很多人納悶了，說(shuō)這些干嘛呢，驢唇不對(duì)馬嘴的？ 答案是，我在培養(yǎng)你一種數(shù)據(jù)結(jié)構(gòu)的眼光。就像是Java中的所有實(shí)現(xiàn)你都要看成對(duì)象（面向?qū)ο螅?C中的所有實(shí)現(xiàn)你都要看成過(guò)程（面向過(guò)程），不同模塊下的同一抽象看成切面（面向切面），數(shù)據(jù)結(jié)構(gòu)同樣如此。只有具備了這種思維，理解起來(lái)容易的多，而且你可以根據(jù)現(xiàn)實(shí)去總結(jié)出自己的數(shù)據(jù)結(jié)構(gòu)；這也是為什么Nicklaus Wirth把所有程序看成是算法+數(shù)據(jù)結(jié)構(gòu)的組合了。
2.數(shù)據(jù)結(jié)構(gòu)的關(guān)系有什么？
不同的角度下， 數(shù)據(jù)元素的關(guān)系是千千萬(wàn)的；但是總結(jié)起來(lái)，大抵分為4類：
上圖是數(shù)據(jù)結(jié)構(gòu)的四種關(guān)系：集合， 線性關(guān)系， 樹(shù)， 圖。 其實(shí)是正好囊括生活中的所有關(guān)系的，不是么？ 解釋起來(lái)，分別是
集合： 任意兩個(gè)元素之間都是獨(dú)立的，也即沒(méi)有關(guān)系
線性： 元素之間存在1對(duì)1的關(guān)系（兩個(gè)元素之間只有唯一的對(duì)應(yīng)關(guān)系，如1和2， 2和3等）
樹(shù)： 元素之間存在1對(duì)多的關(guān)系（每個(gè)父節(jié)點(diǎn)對(duì)應(yīng)N個(gè)子節(jié)點(diǎn)， 如A節(jié)點(diǎn)對(duì)應(yīng)B和C兩個(gè)子節(jié)點(diǎn)）
圖： 元素之間存在多對(duì)多的關(guān)系（任何一個(gè)頂點(diǎn)都可能對(duì)應(yīng)多個(gè)關(guān)系，如A對(duì)應(yīng)和另外的節(jié)點(diǎn)都存在關(guān)系）
其實(shí)現(xiàn)實(shí)生活中的對(duì)應(yīng)關(guān)系也是這樣， 從無(wú)關(guān)系（集合），到有關(guān)系（線性），再?gòu)?fù)雜一點(diǎn)（樹(shù)）從1-1到了1-N，然后再?gòu)?fù)雜一點(diǎn)（圖）從1-N到了N-N， 這就是最復(fù)雜的關(guān)系了。當(dāng)然， 說(shuō)這些只是為了相對(duì)好理解。
3.程序（Java）中的數(shù)據(jù)結(jié)構(gòu)的關(guān)系是什么？
Java是一種面向?qū)ο缶幊蹋?因此在設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)時(shí)，會(huì)采用各種接口， 抽象類， 繼承等；所以Java中的數(shù)據(jù)結(jié)構(gòu)是一個(gè)復(fù)雜的關(guān)系網(wǎng)絡(luò)，借用網(wǎng)上一張關(guān)系圖來(lái)看一下
從上圖來(lái)看， 數(shù)據(jù)結(jié)構(gòu)的關(guān)系還是很復(fù)雜的。大抵分為三層： 1） 公共接口層 2） 數(shù)據(jù)抽象層 3） 數(shù)據(jù)結(jié)構(gòu)層
公共接口層
主要包括Iterator, Collection, Map; 分別對(duì)應(yīng)迭代器， 集合， 圖。 公共接口層主要作用是定義一系列的公共操作，提供一個(gè)執(zhí)行規(guī)范。
Iterator
迭代器，我們可以簡(jiǎn)單的理解為遍歷。 它是一個(gè)標(biāo)準(zhǔn)的遍歷所有對(duì)象的接口。
——————————————————————————————
boolean hasNext();
E next();
——————————————————————————————
Collection
集合，我們并不陌生。看上圖就知道，它衍生了主要的幾種線性結(jié)構(gòu)。 我們使用的List,Set等系列結(jié)構(gòu)都是它的衍生類。
——————————————————————————————
int size();
boolean isEmpty();
boolean contains(Object o);
Object[] toArray();
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
void clear();
——————————————————————————————
Map
圖， 或者稱之為表最合適，但是此圖非彼圖。圖是一種基于鍵值對(duì)即Key-Value形式存儲(chǔ)的結(jié)構(gòu)，我們經(jīng)常使用的HashMap即衍生于此。
———————————————————————
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
void clear();
...
———————————————————————
Map是一種基于鍵值對(duì)（Key-Value）存儲(chǔ)的結(jié)構(gòu)，因此所有操作都是基于鍵值對(duì)操作。我們使用的HashMap, TreeMap， HashSet等都是基于此而來(lái)。
List
提供了列表的系列功能， 至于詳細(xì)的我真不想說(shuō)了，沒(méi)有人沒(méi)用過(guò)List是真的，大家都比我熟。它提供的方法與Collection類似，甚至近乎相同。
Set
Set結(jié)構(gòu)有兩個(gè)重要的特點(diǎn)： 無(wú)序性和唯一性。 Set的元素期存入順序和取出順序是不一致的，如先后存儲(chǔ)ABC，在Set中的元素位置并不一定是ABC,可能是BCA或者其他。 Set的值是唯一的，即Set不允許添加相同值。Set直接繼承自Collection, 沒(méi)有新增方法。
Queue
提供了隊(duì)列的系列功能，隊(duì)列是一種先進(jìn)先出的結(jié)構(gòu)。它提供了以下方法
——————————————————————
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
——————————————————————
隊(duì)列可能在平時(shí)用的很少， 像隊(duì)列， 棧等結(jié)構(gòu)很多時(shí)候可以更方便的解決問(wèn)題。
結(jié)構(gòu)封裝層
實(shí)現(xiàn)了公共接口， 對(duì)某一類型或某具有相似特征的類型提供基類支持。該層主要包含AbstractMap, AbstractList, AbstractSet等針對(duì)底層接口的一些公共的處理，不詳細(xì)說(shuō)明。
結(jié)構(gòu)層
這層涉及到具體的數(shù)據(jù)結(jié)構(gòu)，如List下的ArrayList, LinkedList，Vector; Set下的HashSet, LinkedHashSet,
TreeSet； Map下的HashMap, LinkedHashMap, HashTable, TreeSet等。
《數(shù)據(jù)結(jié)構(gòu)》系列的目的是理清數(shù)據(jù)結(jié)構(gòu)的框架 ， 了解不同結(jié)構(gòu)的特征，詳細(xì)講解不同的具體數(shù)據(jù)結(jié)構(gòu)以及核心部分的原理。下面將按線性表， 樹(shù)， 圖的大順序來(lái)講解數(shù)據(jù)結(jié)構(gòu)；其中順序表又包含上圖中的部分常用的結(jié)構(gòu)。
目錄
線性表
順序表
List系列
Set系列
Queue系列
Vector系列
Stack
Map系列
鏈表
單鏈表
雙鏈表
樹(shù)
樹(shù)
二叉樹(shù)
二叉排序樹(shù)
完全二叉樹(shù)
紅黑樹(shù)
..
圖
