1.常用數(shù)據(jù)結(jié)構(gòu)簡介
答:
1.幾個基本概念
數(shù)據(jù)：數(shù)據(jù)是指計算機接受的輸入數(shù)據(jù)，比如：整型、浮點型等數(shù)值類型以及聲音、圖像、視頻等非數(shù)值類型的數(shù)據(jù)
數(shù)據(jù)元素：是組成數(shù)據(jù)有一定意義的基本單位，比如一個人的基本信息包括姓名、性別、年齡等
數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，比如正整數(shù)數(shù)據(jù)對象N={1，2，3……}
數(shù)據(jù)結(jié)構(gòu)：是數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間存在的一種或幾種特定關(guān)系
數(shù)據(jù)類型：是用來刻畫一組性質(zhì)相同的數(shù)據(jù)及其上的操作?？梢苑譃樵宇愋秃徒Y(jié)構(gòu)類型。
抽象數(shù)據(jù)類型：對具有某種邏輯關(guān)系的數(shù)據(jù)類型進行描述，并在該類型上進行的一組操作。比如C++中的結(jié)構(gòu)體。
2、數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)的主要任務(wù)就是通過描述對象的結(jié)構(gòu)特征，包括邏輯結(jié)構(gòu)在內(nèi)的聯(lián)系，然后把邏輯結(jié)構(gòu)表示成計算機可實現(xiàn)的物理結(jié)構(gòu)，從而方便計算機處理。
邏輯結(jié)構(gòu)：數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)對象中的數(shù)據(jù)元素的所有分布情況滿足的規(guī)律。
集合結(jié)構(gòu)：這種結(jié)構(gòu)中的數(shù)據(jù)元素除了屬于同一數(shù)據(jù)對象之外沒有其他的任何關(guān)系。
線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對一的關(guān)系，并且有一種先后次序關(guān)系。包括數(shù)組、線性表、棧、隊列和串等等。
樹形結(jié)構(gòu)：樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對多的層次關(guān)系。
圖形結(jié)構(gòu)：圖形結(jié)構(gòu)中的數(shù)據(jù)元素之間是多對多的關(guān)系。
2.物理結(jié)構(gòu)：又稱存儲結(jié)構(gòu)，指的是邏輯結(jié)構(gòu)在計算機中的存儲形式。
順序存儲結(jié)構(gòu)：把數(shù)據(jù)元素存放到地址連續(xù)的存儲單元里，數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系一致
鏈?zhǔn)酱鎯Y(jié)構(gòu)：把數(shù)據(jù)元素存放到任意的存儲單元里，地址可以不連續(xù)，通過指針實現(xiàn)數(shù)據(jù)元素之間的邏輯關(guān)系。
3、算法
算法的定義：描述解決問題的方法。使用不同的數(shù)據(jù)結(jié)構(gòu)解決某一類或者具體的問題的策略。
算法的特性：
有窮性：算法執(zhí)行有限的步驟之后會結(jié)束而不會出現(xiàn)無限循環(huán)。
確定性：對于相同的輸入只有唯一的輸出結(jié)果。
可行性：算法的每一步都必須在有限執(zhí)行次數(shù)完成。
輸入：算法有零個輸入或多個輸入。
輸出：至少有一個或多個輸出。
2.列舉java的集合以及集合之間的繼承關(guān)系
用于存儲數(shù)據(jù)的容器。
特點：
1：對象封裝數(shù)據(jù)，對象多了也需要存儲。集合用于存儲對象。
2：對象的個數(shù)確定可以使用數(shù)組，但是不確定怎么辦？可以用集合。因為集合是可變長度的。
集合和數(shù)組的區(qū)別：
1：數(shù)組是固定長度的；集合可變長度的。
2：數(shù)組可以存儲基本數(shù)據(jù)類型，也可以存儲引用數(shù)據(jù)類型；集合只能存儲引用數(shù)據(jù)類型。
3：數(shù)組存儲的元素必須是同一個數(shù)據(jù)類型；集合存儲的對象可以是不同數(shù)據(jù)類型。
?
數(shù)據(jù)結(jié)構(gòu)：就是容器中存儲數(shù)據(jù)的方式。
對于集合容器，有很多種。因為每一個容器的自身特點不同，其實原理在于每個容器的內(nèi)部數(shù)據(jù)結(jié)構(gòu)不同。
集合容器在不斷向上抽取過程中。出現(xiàn)了集合體系。
在使用一個體系時，原則：參閱頂層內(nèi)容。建立底層對象。
?
------------------------------------------------------------
--< java.util >--?Collection接口：
Collection：
??? |--List：有序(元素存入集合的順序和取出的順序一致)，元素都有索引。元素可以重復(fù)。
??? |--Set：無序(存入和取出順序有可能不一致)，不可以存儲重復(fù)元素。必須保證元素唯一性。
1，添加：
??? add(object)：添加一個元素
addAll(Collection)?：添加一個集合中的所有元素。
2，刪除：
??? clear()：將集合中的元素全刪除，清空集合。
remove(obj)?：刪除集合中指定的對象。注意：刪除成功，集合的長度會改變。
removeAll(collection)?：刪除部分元素。部分元素和傳入Collection一致。
3，判斷：
boolean contains(obj)?：集合中是否包含指定元素 。
boolean containsAll(Collection)?：集合中是否包含指定的多個元素。
??? boolean isEmpty()：集合中是否有元素。
4，獲?。?/b>
??? int size()：集合中有幾個元素。
5，取交集：
boolean? retainAll(Collection)?：對當(dāng)前集合中保留和指定集合中的相同的元素。如果兩個集合元素相同，返回flase；如果retainAll修改了當(dāng)前集合，返回true。
6，獲取集合中所有元素：
?Iteratoriterator()：迭代器
7，將集合變成數(shù)組：
toArray();
------------------------------------------------------------
--< java.util >--?Iterator接口：
迭代器：是一個接口。作用：用于取集合中的元素。
booleanhasNext()如果仍有元素可以迭代，則返回?true。
voidremove()從迭代器指向的?collection?中移除迭代器返回的最后一個元素（可選操作）。
每一個集合都有自己的數(shù)據(jù)結(jié)構(gòu)，都有特定的取出自己內(nèi)部元素的方式。為了便于操作所有的容器，取出元素。將容器內(nèi)部的取出方式按照一個統(tǒng)一的規(guī)則向外提供，這個規(guī)則就是Iterator接口。
也就說，只要通過該接口就可以取出Collection集合中的元素，至于每一個具體的容器依據(jù)自己的數(shù)據(jù)結(jié)構(gòu)，如何實現(xiàn)的具體取出細節(jié)，這個不用關(guān)心，這樣就降低了取出元素和具體集合的耦合性。
Iterator it = coll.iterator();//獲取容器中的迭代器對象，至于這個對象是是什么不重要。這對象肯定符合一個規(guī)則Iterator接口。
-----------------------------------------------------------------------------
public static void main(String[] args) {
Collection coll = new ArrayList();
coll.add("abc0");
coll.add("abc1");
coll.add("abc2");
??????? //--------------方式1----------------------
Iterator it = coll.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
??????? //---------------方式2用此種----------------------
?for(Iterator it = coll.iterator();it.hasNext(); ){
System.out.println(it.next());
}
}
-----------------------------------------------------------------------------
--< java.util >--?List接口：
List本身是Collection接口的子接口，具備了Collection的所有方法。現(xiàn)在學(xué)習(xí)List體系特有的共性方法，查閱方法發(fā)現(xiàn)List的特有方法都有索引，這是該集合最大的特點。
List：有序(元素存入集合的順序和取出的順序一致)，元素都有索引。元素可以重復(fù)。
?|--ArrayList：底層的數(shù)據(jù)結(jié)構(gòu)是數(shù)組,線程不同步，ArrayList替代了Vector，查詢元素的速度非?？?。
?|--LinkedList：底層的數(shù)據(jù)結(jié)構(gòu)是鏈表，線程不同步，增刪元素的速度非?？?。
?|--Vector：底層的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，線程同步的，Vector無論查詢和增刪都巨慢。
1，添加：
add(index,element)?：在指定的索引位插入元素。
addAll(index,collection)?：在指定的索引位插入一堆元素。
2，刪除：
remove(index)?：刪除指定索引位的元素。 返回被刪的元素。
3，獲?。?/b>
Object get(index)?：通過索引獲取指定元素。
int?indexOf(obj)?：獲取指定元素第一次出現(xiàn)的索引位，如果該元素不存在返回-1；
?所以，通過-1，可以判斷一個元素是否存在。
int lastIndexOf(Object o)?：反向索引指定元素的位置。
List?subList(start,end)?：獲取子列表。
4，修改：
Object set(index,element)?：對指定索引位進行元素的修改。
5，獲取所有元素：
ListIterator?listIterator()：list集合特有的迭代器。
List集合支持對元素的增、刪、改、查。
List集合因為角標(biāo)有了自己的獲取元素的方式： 遍歷。
for(int x=0; x
sop("get:"+list.get(x));
}
在進行l(wèi)ist列表元素迭代的時候，如果想要在迭代過程中，想要對元素進行操作的時候，比如滿足條件添加新元素。會發(fā)生.ConcurrentModificationException并發(fā)修改異常。
導(dǎo)致的原因是：
集合引用和迭代器引用在同時操作元素，通過集合獲取到對應(yīng)的迭代器后，在迭代中，進行集合引用的元素添加，迭代器并不知道，所以會出現(xiàn)異常情況。
如何解決呢？
既然是在迭代中對元素進行操作,找迭代器的方法最為合適.可是Iterator中只有hasNext,next,remove方法.通過查閱的它的子接口,ListIterator,發(fā)現(xiàn)該列表迭代器接口具備了對元素的增、刪、改、查的動作。
ListIterator是List集合特有的迭代器。
ListIterator it = list.listIterator;//取代Iterator it = list.iterator;
方法摘要
booleanhasNext()?以正向遍歷列表時，如果列表迭代器有多個元素，則返回?true（換句話說，如果?next返回一個元素而不是拋出異常，則返回?true）。
booleanhasPrevious()?如果以逆向遍歷列表，列表迭代器有多個元素，則返回?true。
intnextIndex()?返回對next?的后續(xù)調(diào)用所返回元素的索引。
intpreviousIndex()?返回對previous?的后續(xù)調(diào)用所返回元素的索引。
voidremove()?從列表中移除由?next?或previous?返回的最后一個元素（可選操作）。
voidset(Ee)?用指定元素替換?next?或previous?返回的最后一個元素（可選操作）。
可變長度數(shù)組的原理：
當(dāng)元素超出數(shù)組長度，會產(chǎn)生一個新數(shù)組，將原數(shù)組的數(shù)據(jù)復(fù)制到新數(shù)組中，再將新的元素添加到新數(shù)組中。
ArrayList：是按照原數(shù)組的50%延長。構(gòu)造一個初始容量為?10?的空列表。
Vector：是按照原數(shù)組的100%延長。
注意：對于list集合，底層判斷元素是否相同，其實用的是元素自身的equals方法完成的。所以建議元素都要復(fù)寫equals方法，建立元素對象自己的比較相同的條件依據(jù)。
LinkedList：的特有方法。
addFirst();
addLast();
在jdk1.6以后。
offerFirst();
offerLast();
getFirst():獲取鏈表中的第一個元素。如果鏈表為空，拋出NoSuchElementException;
getLast();
在jdk1.6以后。
peekFirst();獲取鏈表中的第一個元素。如果鏈表為空，返回null。
peekLast();
removeFirst()：獲取鏈表中的第一個元素，但是會刪除鏈表中的第一個元素。如果鏈表為空，拋出NoSuchElementException
removeLast();
在jdk1.6以后。
pollFirst();獲取鏈表中的第一個元素，但是會刪除鏈表中的第一個元素。如果鏈表為空，返回null。
pollLast();
------------------------------------------------------------
--< java.util >--?Set接口：
Set接口中的方法和Collection中方法一致的。Set接口取出方式只有一種，迭代器。
?|--HashSet：底層數(shù)據(jù)結(jié)構(gòu)是哈希表，線程是不同步的。無序，高效；
?HashSet集合保證元素唯一性：通過元素的hashCode方法，和equals方法完成的。
?當(dāng)元素的hashCode值相同時，才繼續(xù)判斷元素的equals是否為true。
?如果為true，那么視為相同元素，不存。如果為false，那么存儲。
?如果hashCode值不同，那么不判斷equals，從而提高對象比較的速度。
?|--LinkedHashSet：有序，hashset的子類。
?|--TreeSet：對Set集合中的元素的進行指定順序的排序。不同步。TreeSet底層的數(shù)據(jù)結(jié)構(gòu)就是二叉樹。
哈希表的原理：
1，對對象元素中的關(guān)鍵字(對象中的特有數(shù)據(jù))，進行哈希算法的運算，并得出一個具體的算法值，這個值 稱為哈希值。
2，哈希值就是這個元素的位置。
3，如果哈希值出現(xiàn)沖突，再次判斷這個關(guān)鍵字對應(yīng)的對象是否相同。如果對象相同，就不存儲，因為元素重復(fù)。如果對象不同，就存儲，在原來對象的哈希值基礎(chǔ)?+1順延。
4，存儲哈希值的結(jié)構(gòu)，我們稱為哈希表。
5，既然哈希表是根據(jù)哈希值存儲的，為了提高效率，最好保證對象的關(guān)鍵字是唯一的。
?這樣可以盡量少的判斷關(guān)鍵字對應(yīng)的對象是否相同，提高了哈希表的操作效率。
對于ArrayList集合，判斷元素是否存在，或者刪元素底層依據(jù)都是equals方法。
對于HashSet集合，判斷元素是否存在，或者刪除元素，底層依據(jù)的是hashCode方法和equals方法。
TreeSet:
?用于對Set集合進行元素的指定順序排序，排序需要依據(jù)元素自身具備的比較性。
?如果元素不具備比較性，在運行時會發(fā)生ClassCastException異常。
?所以需要元素實現(xiàn)Comparable接口，強制讓元素具備比較性，復(fù)寫compareTo方法。
?依據(jù)compareTo方法的返回值，確定元素在TreeSet數(shù)據(jù)結(jié)構(gòu)中的位置。
?TreeSet方法保證元素唯一性的方式：就是參考比較方法的結(jié)果是否為0，如果return 0，視為兩個對象重復(fù)，不存。
注意：在進行比較時，如果判斷元素不唯一，比如，同姓名，同年齡，才視為同一個人。
?在判斷時，需要分主要條件和次要條件，當(dāng)主要條件相同時，再判斷次要條件，按照次要條件排序。
TreeSet集合排序有兩種方式，Comparable和Comparator區(qū)別：
1：讓元素自身具備比較性，需要元素對象實現(xiàn)Comparable接口，覆蓋compareTo方法。
2：讓集合自身具備比較性，需要定義一個實現(xiàn)了Comparator接口的比較器，并覆蓋compare方法，并將該類對象作為實際參數(shù)傳遞給TreeSet集合的構(gòu)造函數(shù)。
第二種方式較為靈活。
------------------------------------------------------------
Map集合：
|--Hashtable：底層是哈希表數(shù)據(jù)結(jié)構(gòu)，是線程同步的。不可以存儲null鍵，null值。
|--HashMap：底層是哈希表數(shù)據(jù)結(jié)構(gòu)，是線程不同步的?？梢源鎯ull鍵，null值。替代了Hashtable.
|--TreeMap：底層是二叉樹結(jié)構(gòu)，可以對map集合中的鍵進行指定順序的排序。
?
Map集合存儲和Collection有著很大不同：
Collection一次存一個元素；Map一次存一對元素。
Collection是單列集合；Map是雙列集合。
Map中的存儲的一對元素：一個是鍵，一個是值，鍵與值之間有對應(yīng)(映射)關(guān)系。
特點：要保證map集合中鍵的唯一性。
1，添加。
put(key,value)：當(dāng)存儲的鍵相同時，新的值會替換老的值，并將老值返回。如果鍵沒有重復(fù)，返回null。
void?putAll(Map);
2，刪除。
void?clear()：清空
value?remove(key)?：刪除指定鍵。
3，判斷。
boolean?isEmpty()：
boolean?containsKey(key)：是否包含key
boolean?containsValue(value)?：是否包含value
4，取出。
int?size()：返回長度
value?get(key)?：通過指定鍵獲取對應(yīng)的值。如果返回null，可以判斷該鍵不存在。當(dāng)然有特殊情況，就是在hashmap集合中，是可以存儲null鍵null值的。
Collection?values()：獲取map集合中的所有的值。
5，想要獲取map中的所有元素：
?原理：map中是沒有迭代器的，collection具備迭代器，只要將map集合轉(zhuǎn)成Set集合，可以使用迭代器了。之所以轉(zhuǎn)成set，是因為map集合具備著鍵的唯一性，其實set集合就來自于map，set集合底層其實用的就是map的方法。
★?把map集合轉(zhuǎn)成set的方法：
Set keySet();
Set entrySet();//取的是鍵和值的映射關(guān)系。
Entry就是Map接口中的內(nèi)部接口；
為什么要定義在map內(nèi)部呢？entry是訪問鍵值關(guān)系的入口，是map的入口，訪問的是map中的鍵值對。
3.數(shù)組和鏈表的區(qū)別
答:
數(shù)組是將元素在內(nèi)存中連續(xù)存放，由于每個元素占用內(nèi)存相同，可以通過下標(biāo)迅速訪問數(shù)組中任何元素。但是如果要在數(shù)組中增加一個元素，需要移動大量元素，在內(nèi)存中空出一個元素的空間，然后將要增加的元素放在其中。同樣的道理，如果想刪除一個元素，同樣需要移動大量元素去填掉被移動的元素。如果應(yīng)用需要快速訪問數(shù)據(jù)，很少或不插入和刪除元素，就應(yīng)該用數(shù)組。
鏈表恰好相反，鏈表中的元素在內(nèi)存中不是順序存儲的，而是通過存在元素中的指針聯(lián)系到一起。比如：上一個元素有個指針指到下一個元素，以此類推，直到最后一個元素。如果要訪問鏈表中一個元素，需要從第一個元素開始，一直找到需要的元素位置。但是增加和刪除一個元素對于鏈表數(shù)據(jù)結(jié)構(gòu)就非常簡單了，只要修改元素中的指針就可以了。如果應(yīng)用需要經(jīng)常插入和刪除元素你就需要用鏈表數(shù)據(jù)結(jié)構(gòu)了
? ?綜合以上，對于快速訪問數(shù)據(jù)，不經(jīng)常有添加刪除操作的時候選擇數(shù)組實現(xiàn)，而對于經(jīng)常添加刪除數(shù)據(jù)，對于訪問沒有很高要求的時候選擇鏈表。
