數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料,java數(shù)據(jù)結(jié)構(gòu)期末考試

1、第2章 算法分析1. 算法分析是計(jì)算機(jī)科學(xué)的基礎(chǔ)2. 增長函數(shù)表示問題（n）大小與我們希望最優(yōu)化的值之間的關(guān)系。該函數(shù)表示了該算法的時間復(fù)雜度或空間復(fù)雜度。增長函數(shù)表示與該問題大小相對應(yīng)的時間或空間的使用3. 漸進(jìn)復(fù)雜度：隨著n的增加時增長函數(shù)的一般性質(zhì)，這一特性基于該表達(dá)式的主項(xiàng)，即n增加時表達(dá)式中增長最快的那一項(xiàng)。4. 漸進(jìn)復(fù)雜度稱為算法的階次，算法的階次是忽略該算法的增長函數(shù)中的常量和其他次要項(xiàng)，只保留主項(xiàng)而得出來的。算法的階次為增長函數(shù)提供了一個上界。5. 漸進(jìn)復(fù)雜度：增長函數(shù)的界限，由增長函數(shù)的主項(xiàng)確定的。漸進(jìn)復(fù)雜度類似的函數(shù)，歸為相同類型的函數(shù)。6. 只有可運(yùn)行的語句才會增加時間復(fù)

2、雜度。7. O() 或者 大O記法：與問題大小無關(guān)、執(zhí)行時間恒定的增長函數(shù)稱為具有O（1）的復(fù)雜度。增長函數(shù)階次t(n)=17O(1)t(n)=3log nO(log n)t(n)=20n-4O(n)t(n)=12n log n + 100nO(n log n)t(n)=3 + 5n - 2O()t(n)=8 + 3O()t(n)=+ 18 +3nO()8. 所有具有相同階次的算法，從運(yùn)行效率的角度來說都是等價(jià)的。9. 如果算法的運(yùn)行效率低，從長遠(yuǎn)來說，使用更快的處理器也無濟(jì)于事。10. 要分析循環(huán)運(yùn)行，首先要確定該循環(huán)體的階次n，然后用該循環(huán)要運(yùn)行的次數(shù)乘以它。（n表示的是問題的大小）11.

3、 分析嵌套循環(huán)的復(fù)雜度時，必須將內(nèi)層和外層循環(huán)都考慮進(jìn)來。12. 方法調(diào)用的復(fù)雜度分析：如：public void printsum(int count)int sum = 0 ;for (int I = 1 ; I < count ; I+)sum += I ;System.out.println(sun); printsum方法的復(fù)雜度為O（n）,計(jì)算調(diào)用該方法的初始循環(huán)的時間復(fù)雜度，只需把printsum方法的復(fù)雜度乘以該循環(huán)運(yùn)行的次數(shù)即可。所以調(diào)用上面實(shí)現(xiàn)的printsum方法的復(fù)雜度為O（）。13指數(shù)函數(shù)增長 > 冪函數(shù)增長 > 對數(shù)函數(shù)增長第三章 集合概述棧1.

4、集合是一種聚集、組織了其他對象的對象。它定義了一種特定的方式，可以訪問、管理所包含的對象（稱為該集合的元素）。集合的使用者通常是軟件系統(tǒng)中的另一個類或?qū)ο笾荒芡ㄟ^這些預(yù)定的方式與該集合進(jìn)行交互。2. 集合可分為線性集合和非線性集合。線性集合是一種元素按直線方式組織的集合。非線性集合是一種元素按某種非直線方式組織的集合，例如按層次組織或按網(wǎng)狀組織。從這種意義上來說，非線性集合也許根本就沒有任何組織形式。3. 集合中的元素通常是按照它們添加到集合的順序，或者是按元素之間的某種內(nèi)在關(guān)系來組織的。4. 抽象能隱藏某些細(xì)節(jié)。5. 集合是一種隱藏了實(shí)現(xiàn)細(xì)節(jié)的抽象。6. 對象是用于創(chuàng)建集合一種完美機(jī)制，因?yàn)?/p>

5、只要設(shè)計(jì)正確，對象的內(nèi)部工作對系統(tǒng)其他部分而言是被封裝的。幾乎在所有情況下，在類中定義的實(shí)例變量的可見性都應(yīng)聲明為私有的（private）。因此，只有該類的方法才可以訪問和修改這些變量。用戶與對象的唯一交互只能通過其公用方法。公用方法表示了對象所能提供的服務(wù)。7. 數(shù)據(jù)類型是一組值及作用于這些數(shù)值上的各種操作。8. 抽象數(shù)據(jù)類型（ADT）是一種在程序設(shè)計(jì)語言中尚未定義其值和操作的數(shù)據(jù)類型。ADT的抽象性體現(xiàn)在，ADT必須對其實(shí)現(xiàn)細(xì)節(jié)進(jìn)行定義，且對這些用戶是不可見的。因此，集合是一種抽象數(shù)據(jù)類型。9. 數(shù)據(jù)結(jié)構(gòu)是一種用于實(shí)現(xiàn)集合的基本編程結(jié)構(gòu)。10. Java集合API（應(yīng)用程序編程接口）是一個

6、類集，表示了一些特定類型的集合，這些類的實(shí)現(xiàn)方式各不相同。11. 棧的元素是按照后進(jìn)先出（LIFO）的方式進(jìn)行處理的，最后進(jìn)入棧中的元素最先被移出。棧是一種線性集合，元素的添加和刪除都在同一端進(jìn)行。在科學(xué)計(jì)算中，棧的基本使用就是用于顛倒順序（如一個取消操作）。12. 通常垂直的繪制棧，棧的末端稱為棧的頂部，元素的添加和刪除在頂部進(jìn)行。13. 如果pop或者peek可作用于空棧，那么棧的任何實(shí)現(xiàn)都要拋出一個異常。集合的作用不是去確定如何處理這個異常，而是把它報(bào)告給使用該棧的應(yīng)用程序。在棧中沒有滿棧的概念，應(yīng)由棧來管理它自己的存儲空間。14. 棧的toString（）操作可以在不修改棧的情況下遍歷

7、和現(xiàn)實(shí)棧的內(nèi)容，對調(diào)試非常有用。15. 類型兼容性是指把一個對象賦給引用的特定賦值是否合法。16. 繼承就是通過某個現(xiàn)有類派生出一個新類的過程。多態(tài)：使得一個引用可以多次指向相關(guān)但不同的對象類型，且其中調(diào)用的方法是在運(yùn)行時與代碼。多態(tài)引用是一個引用變量，它可以在不同地點(diǎn)引用不同類型的對象。繼承可用于創(chuàng)建一個類層次，其中，一個引用變量可用于只想與之相關(guān)的任意對象。類層次：通過繼承創(chuàng)建的類之間的關(guān)系，某個類的子類可以成為其他類的父類17. 一個Object引用可用于引用任意對象，因?yàn)樗蓄愖罱K都是從Object類派生而來的。18. 泛型，用泛型定義類：使這個類能存儲、操作和管理在實(shí)例化之前沒有指定

8、是何種類型的對象。19. 泛型不能被實(shí)例化。它只是一個占位符，允許我們?nèi)ザx管理特定類型的對象的類，且只有當(dāng)該類被實(shí)例化時，才創(chuàng)建該類的對象。20. 計(jì)算后綴表達(dá)式：從左到右掃描，把每個操作符應(yīng)用到其之前的兩個緊鄰操作數(shù)，并用該計(jì)算結(jié)果代替該操作符。21. 棧是用于計(jì)算后綴表達(dá)式的理想數(shù)據(jù)結(jié)構(gòu)。22. 用棧計(jì)算后綴表達(dá)式時，操作數(shù)是作為一個Integer對象而不是作為一個int基本數(shù)值被壓入棧中的，這是因?yàn)闂１辉O(shè)計(jì)為存儲對象的。注意：第一個彈出的操作數(shù)是表達(dá)式的第二個操作數(shù)，第二個彈出的操作數(shù)是表達(dá)式的第一個操作數(shù)。23. Javadoc注釋以 /* 開始，以 */ 結(jié)束。Javadoc標(biāo)簽用

9、于標(biāo)識特定類型的信息。auther標(biāo)簽用于標(biāo)識編寫代碼的程序員。version標(biāo)簽用于制定代碼的版本號。return標(biāo)簽用于表明該方法的返回值。param標(biāo)簽用于標(biāo)識傳遞給該方法的每個參數(shù)。24. 異常就是一個對象，它被定義了一種非正常或錯誤的情況。異常由程序或運(yùn)行時環(huán)境拋出，可以按預(yù)期的被捕獲或被正確處理。錯誤與一場異常類似，只不過錯誤往往表示一種無法恢復(fù)的情況，且不必去捕獲它。25. 接口的命名：用集合名+ADT來為集合接口命名。26. 取消操作通常是使用一種名為drop-out的棧來實(shí)現(xiàn)。它與棧唯一的不同是，它對存儲元素的數(shù)量有限制，一旦達(dá)到限制，如果有新元素要壓入，那么棧底的元素將從棧

10、中被丟棄。27. 數(shù)組一旦創(chuàng)建好，其容量是不能改變的。28. 處于運(yùn)行效率的考慮，給予數(shù)組的棧實(shí)現(xiàn)總是使棧底位于數(shù)組的索引0處。29. ArrayStack類有兩個構(gòu)造函數(shù)，一個使用的是默認(rèn)容量，一個使用的是制定容量。30. 構(gòu)造函數(shù)與成員方法的區(qū)別：a) 構(gòu)造函數(shù)是初始化一個類的對象時調(diào)用，無返回值。名字與類名相同b) 成員函數(shù)由類對象主動調(diào)用，使用點(diǎn)操作符（“.”），又返回值。31. private T stack;Stack = (T) ( new ObjectDEFAULT_CAPACITY);由于不能實(shí)例化一個泛型對象，這里實(shí)例化了一個Object數(shù)組，然后將它轉(zhuǎn)換為一個泛型數(shù)組。3

11、2. push（）public void push(T element) if(size()=stack.length)expandCapacity();stacktop= element;top+;33. pop（）public T pop() throws EmptyCollectionExceptionif (isEmpty()throw new EmptyCollectionException("Stack");top-;T result=stacktop;stacktop=null;return result;34. peek（）public T peek()th

12、rows EmptyCollectionException if(isEmpty()throw new EmptyCollectionException("Stack");return stacktop-1;35.private void expandCapacity()Tlarger = (T)(new Objectstack.length*2); for (int index=0; index<stack.length;index+) largerindex=stackindex; stack = larger;第4章 鏈?zhǔn)浇Y(jié)構(gòu)棧1. 對象引用變量可以用來創(chuàng)建鏈?zhǔn)?/p>

13、結(jié)構(gòu)。鏈?zhǔn)浇Y(jié)構(gòu)是一種數(shù)據(jù)結(jié)構(gòu)，它使用對象引用變量來創(chuàng)建對象之間鏈接。鏈?zhǔn)浇Y(jié)構(gòu)是基于數(shù)組的集合實(shí)現(xiàn)的主要替代方案。2. 對象引用變量存放的是對象的地址，表示該對象在內(nèi)存中的存儲位置。我們通常并不是顯示地址，而是把引用變量描繪成一種“指向”對象的名字，這種引用變量又稱為指針。3. 鏈表由一些對象構(gòu)成，是一種鏈?zhǔn)浇Y(jié)構(gòu)，其中的一個對象可以指向另一個對象，從而在鏈表中創(chuàng)建一個對象的線性次序。鏈表中存儲的對象通常泛稱為該鏈表的結(jié)點(diǎn)。4. 需要一個單獨(dú)的引用變量來表示鏈表的首結(jié)點(diǎn)。鏈表終止于其next引用為空的結(jié)點(diǎn)。5. 鏈表只是鏈?zhǔn)浇Y(jié)構(gòu)的一種。如果建立的類含有多個指向?qū)ο蟮囊茫涂梢詣?chuàng)建更復(fù)雜的鏈?zhǔn)浇Y(jié)構(gòu)

14、。鏈接的管理方式表明了這種鏈?zhǔn)浇Y(jié)構(gòu)的特定組織形式。6. 鏈表會按需動態(tài)增長，因此在本質(zhì)上，它沒有容量限制（在不考慮計(jì)算機(jī)本身的內(nèi)存限制下）。7. 鏈表的大小可以按需伸縮以容納要存儲的元素?cái)?shù)量，因此鏈表被認(rèn)定為是一種動態(tài)結(jié)構(gòu)。在java語言中，所有動態(tài)創(chuàng)建的對象都來自于一個名為系統(tǒng)堆或自由存儲的內(nèi)存區(qū)。8. 對于鏈表來說，訪問鏈表的元素的唯一方式是，從第一個元素開始，順著該鏈表往下進(jìn)行。9. 結(jié)點(diǎn)可以被插入到鏈表的任意位置。在鏈表前端架結(jié)點(diǎn)時，需重新設(shè)置指向整個鏈表的引用：a) 新添加結(jié)點(diǎn)的next引用被設(shè)置為指向鏈表的當(dāng)前首結(jié)點(diǎn)；b) 指向鏈表前端的引用重新設(shè)置為指向這個新結(jié)點(diǎn)。如果顛倒順序，

15、即先重新設(shè)置front引用，那么就失去了那個唯一指向現(xiàn)有鏈表的引用，于是再也檢索不到該鏈表了。10. 改變引用順序是維護(hù)鏈表的關(guān)鍵。11. 鏈表的任一結(jié)點(diǎn)都可被刪除。要刪除鏈表的首結(jié)點(diǎn)，需要重置指向鏈表前端的引用，使其指向鏈表當(dāng)前的次。如果其他地方需要這個被刪除的結(jié)點(diǎn)，那么在重制front引用之前，必須創(chuàng)建一個指向被刪除結(jié)點(diǎn)的單獨(dú)引用。12. 鏈表的一個關(guān)鍵特征：必須把鏈表結(jié)構(gòu)的細(xì)節(jié)內(nèi)容與鏈表所儲存的元素區(qū)分開來13. 存儲在集合中的對象不應(yīng)該含有基本數(shù)據(jù)結(jié)構(gòu)的任何實(shí)現(xiàn)細(xì)節(jié)。14. 節(jié)點(diǎn)類含有兩個引用：一個引用指向鏈表的下一結(jié)點(diǎn)，另一個引用指向?qū)⒋鎯Φ芥湵碇械哪莻€元素。這時，鏈表中所存儲的實(shí)際

16、元素是使用結(jié)點(diǎn)對象中單獨(dú)引用來訪問的。15. 雙向鏈表中，需維護(hù)兩個引用：一個指向鏈表的首結(jié)點(diǎn)，一個指向鏈表的末結(jié)點(diǎn)。鏈表中的每個結(jié)點(diǎn)都存有兩個引用：一個指向下一元素，一個指向上一元素。16. 哨兵結(jié)點(diǎn)或啞結(jié)點(diǎn)：位于鏈表前端或末端的結(jié)點(diǎn)，起標(biāo)記符作用，不表示鏈表中的某個元素。如果要在雙向鏈表中使用啞結(jié)點(diǎn)，那么就得在鏈表的兩端都放置啞結(jié)點(diǎn)。17. 遞歸使用了程序棧的概念，程序棧又稱運(yùn)行時棧，用于跟蹤被調(diào)用的方法。每調(diào)用一個方法時，就會創(chuàng)建一個表示該調(diào)用的調(diào)用記錄，并壓入到程序棧中。因此，棧中的元素表示的是在一個正在運(yùn)行程序中，到達(dá)某個位置時所調(diào)用的方法系列。18. 程序運(yùn)行出現(xiàn)異常時，可檢查調(diào)用

17、跟蹤棧，來發(fā)現(xiàn)問題出自于哪個方法。19. 可以使用棧來模擬遞歸處理，以便跟蹤恰當(dāng)?shù)臄?shù)據(jù)。20. 用鏈表實(shí)現(xiàn)棧：a) Push：public void push(T element)LinearNode<T> temp = new LinearNode<T>(element);temp.setNext(top);top = temp;count+;b) Pop：public T pop() throws EmptyCollectionException if(isEmpty()throw new EmptyCollectionException("stack&q

18、uot;);T result = top.getElement();top = top.getNext();count-;return result;第5章 隊(duì)列1. 隊(duì)列是一種線性集合，其元素從一端加入，另一端刪除。因此，隊(duì)列元素是按先進(jìn)先出（FIFO）方式處理的。從隊(duì)列中刪除元素的次序，與往隊(duì)列中放置元素的次序是一樣的。元素都是從隊(duì)列末端（rear）進(jìn)入，從隊(duì)列前端（front）退出。2. 用鏈表實(shí)現(xiàn)棧：a) 隊(duì)列和棧的主要區(qū)別在于，隊(duì)列中我們必須要操作鏈表的兩端。因此需要兩個引用分別指向鏈表的首、末元素。b) 對于單向鏈表，可選擇從末端入列，從前端出列。c) 雙向鏈表可以解決需要遍歷鏈表

19、的問題，因此在雙向鏈表實(shí)現(xiàn)中，無所謂在哪端入列和出列。d) 對于一個空隊(duì)列，head和tail引用都為null，count為0。隊(duì)列中只有一個元素時，head和tail引用都會指向這個對象。e) Enqueue：將新元素放到鏈表末端public void enqueue(T element) LinearNode<T> node = new LinearNode<T>(element);if(isEmpty()head = node;elsetail.setNext(node);tail = node;count+;f)Dequeuepublic T dequeue()

20、 throws EmptyCollectionException if(isEmpty()throw new EmptyCollectionException("queue");T result = head.getElement();head = head.getNext();count-;if(isEmpty()tail = null;return result;3. 用數(shù)組實(shí)現(xiàn)隊(duì)列：a) 由于隊(duì)列操作會修改集合的兩端，因此將一端固定于索引0出要求移動元素。b) 非環(huán)形數(shù)組實(shí)現(xiàn)的元素位移，將產(chǎn)生O（n）的復(fù)雜度。c) 把數(shù)組看作是環(huán)形的，可以除去在隊(duì)列的數(shù)組實(shí)現(xiàn)中元素的

21、移位需要。d) 環(huán)形數(shù)組：如果數(shù)組的最后一個索引后面跟的是第一個索引，那么該數(shù)組就可用作環(huán)形數(shù)組。e) 用兩個整數(shù)值表示隊(duì)列的前端和末端。front的值表示的是隊(duì)列的首元素存儲的位置，rear的值表示的是數(shù)組下一個可用單元（不是最后一個元素儲存的位置），此時rear的值不在表示隊(duì)列元素的數(shù)目了。f) Enqueue：public void enqueue(T element) if(size() = queue.length)expendCapacity();queuerear = element;rear = (rear + 1) % queue.length;count+;適當(dāng)?shù)臅r候，繞回

22、到0正常增加注意：環(huán)形增加rear = (rear + 1) % queue.length;e) Dequeue:public T dequeue() throws EmptyCollectionException if(isEmpty()throw new EmptyCollectionException("queue");T result = queuefront;queuerear = null;front = (front + 1)%queue.length;count-;return result;4. 隊(duì)列是一種可存儲重復(fù)編碼密鑰的便利集合。5. 隊(duì)列的鏈表實(shí)現(xiàn)

23、中，head和tail引用相等的情況：a) 隊(duì)列為空：head和tail都為nullb) 隊(duì)列中只有一個元素6. 隊(duì)列的環(huán)形數(shù)組實(shí)現(xiàn)中，front和rear引用相等的情況：a) 隊(duì)列為空b) 隊(duì)列為滿7. dequeue操作復(fù)雜度為O(n)的非環(huán)形數(shù)組實(shí)現(xiàn)的時間復(fù)雜度最差8. 環(huán)形數(shù)組和非環(huán)形數(shù)組都會因未填充元素而浪費(fèi)空間。鏈表實(shí)現(xiàn)中的每個存儲元素都會占用更多的空間。第6章 列表1. 鏈表和列表集合之間的差別：a) 鏈表是一種實(shí)現(xiàn)策略，使用引用來在對象之間創(chuàng)建鏈接，如前面用鏈表來實(shí)現(xiàn)了棧和隊(duì)列集合。b) 列表集合是一種概念性表示法，其思想是使事物以線性列表的方式進(jìn)行組織。就像棧和隊(duì)列一樣，列表

24、也可以使用鏈表或數(shù)組來實(shí)現(xiàn)。2. 列表集合沒有內(nèi)在的容量大小，它可以隨著需要增大。3. 棧和隊(duì)列都是線性結(jié)構(gòu)，可以像列表那樣進(jìn)行思考，但元素只能在末端添加和刪除。列表集合更一般化，可以在列表的中間和末端添加和刪除元素。In other words,棧和隊(duì)列都屬于列表，列表可任意操作。4. 列表可分為：a) 有序列表：其元素按照元素的某種內(nèi)在特性進(jìn)行排序；b) 無序列表：其元素間不具有內(nèi)在順序，元素按照它們在列表中的位置進(jìn)行排序。c) 索引列表：其元素可以用數(shù)字索引來引用。5. 有序列表是基于列表中元素的某種內(nèi)在特征的。列表基于某個關(guān)鍵值排序。對于任何已添加到有序列表中的元素，只要給定了元素的關(guān)

25、鍵值，同時已經(jīng)定義了元素的所有關(guān)鍵值，那么它在列表中就會有一個固定的位置。6. 無序列表中各元素的位置并不基于元素的任何內(nèi)在特性。但列表中的元素是按照特殊順序放置著，只不過這種順序與元素本身無關(guān)。列表的使用者會決定元素的順序。無序列表的新元素可以加到列表的前端、后端，或者插到某個特定元素之后。7. 索引列表與無序列表類似，各元素間也不存在能夠決定它們在列表中的順序的內(nèi)在關(guān)系。列表的使用者決定了元素的順序。除此之外，索引列表的每個元素都能夠從一個數(shù)字索引值得到引用，該索引值從列表頭開始從0連續(xù)增加直到列表末端。索引列表的新元素可以加到列表的任一位置，包括列表的前端和后端。每當(dāng)列表發(fā)生改變，索引值

26、就相應(yīng)調(diào)整以保持順序和連續(xù)性。索引列表為它的元素維護(hù)一段連續(xù)的數(shù)字索引值。8. 索引列表和數(shù)組的根本區(qū)別在于：索引列表的索引值總是連續(xù)的。如果刪除了一個元素，其他元素的位置會像“坍塌”了一樣消除產(chǎn)生的空隙。當(dāng)插入一個元素時，其他元素的索引將進(jìn)行位移以騰出位置。9. 列表有可能既是有序列表，又是索引列表，但這種設(shè)計(jì)沒有什么意義。10. Java集合API中的列表：a) Java集合API提供的列表類只要是支持索引列表。在一定程度上，這些類與無序列表是重疊的。i. 注意：java API并沒有任何類能直接實(shí)現(xiàn)以上描述的有序列表。b) List接口：add(E element)往列表的 末端 添加一

27、個元素add（int index,E element）在指定索引處插入一個元素get（int index）返回指定索引處的元素remove(int index)刪除指定索引處的元素remove（E Object）刪除制定對象的第一個出現(xiàn)set（int index，E element）替代指定索引處的元素size（）返回列表中的元素?cái)?shù)目11. 數(shù)組實(shí)現(xiàn)列表：使用環(huán)形數(shù)組方法，但當(dāng)從列表中間插入或者刪除元素時，仍需移動元素。a) Remove操作：public T remove(T element) throws ElementNotFoundExceptionT result;int index

28、 = find(element);if(index = NOT_FOUND)throw new ElementNotFoundException("ArrayList");result = listindex;rear-;for(int scan=index;scan<rear; scan+)listscan=listscan+1;listrear=null;return result;注意：程序中的for循環(huán)，當(dāng)循環(huán)結(jié)束后，scan等于rear。因?yàn)楫?dāng)scan=rear-1時，最后運(yùn)行一次listscan=listscan+1,然后scan+，不滿足scan<

29、rear,退出循環(huán)。復(fù)雜度為O（n）。b) find方法： private int find(T target) int scan = 0; int result = NOT_FOUND; if(!isEmpty() while (result = NOT_FOUND && scan < rear) if(target.equals(listscan) result = scan; else scan+; return result; 注意：find方法依靠equals方法來判斷目標(biāo)元素是否已找到。c) contains操作public boolean contains(

30、T target)return (find(target)!=NOT_FOUND); 如果沒有找到目標(biāo)元素，contains方法將返回false。如果找到了，返回true。由于該方法執(zhí)行的是列表的線性查找，因此最壞的情況是所查找的元素不在列表中。在這種情況下需要n個比較操作。因此該方法平均需要n/2次比較操作，因而其復(fù)雜度為O(n)。d)有序列表的add操作：public void add(T element) if(size()=list.length)expandCapacity();Comparable<T> temp =(Comparable<T>)elemen

31、t;int scan =0;while(scan<rear && pareTo(listscan)>0)scan+;for(int scan2=rear; scan2>scan;scan2-)listscan2=listscan2-1;listscan=element;rear+;注意：復(fù)雜度為O（n）。只有Comparable對象才能存儲在有序列表中。e） Comparable接口定義了compareTo方法，當(dāng)執(zhí)行對象為小于、等于或者大于傳入?yún)?shù)時，該方法將分別返回一個負(fù)整數(shù)、0或者一個正整數(shù)。無序列表和索引列表不要求它們所存儲的元素是Comparable

32、的。f）無序列表的操作public void addAfter(T element,T target) if(size()=list.length)expandCapacity();int scan=0;while(scan<rear&&!(target.equals(listscan)scan+;if(scan=rear)throw new NoSuchElementException();for(int i=rear;i>scan+1;i-)listi=listi-1;listscan+1=element;rear+;public void addToFront

33、(T element) if(size()=list.length)expandCapacity();for(int i=rear;i<0;i-)listi=listi-1; list0=element; rear+;public void addToRear(T element) if(size()=list.length)expandCapacity();listrear=element;rear+;注意：addToFront操作的復(fù)雜度為O（n），addToRear的為O（1）addAfter的為O（n）。12. 用鏈表實(shí)現(xiàn)列表a) Remove操作：4種情況：要刪除的元素是唯一元

34、素；是首元素；是末元素；處于列表中間的元素。最壞的情況下，仍需進(jìn)行n次比較，以確定目標(biāo)元素不在列表中。因此remove操作的復(fù)雜度是O（n）。public T remove(T targetElement) throws ElementNotFoundException, EmptyCollectionException if (isEmpty()throw new EmptyCollectionException("List");boolean found = false;LinearNode<T> previous = null;LinearNode<

35、T> current = head;while(current !=null &&!found)if(targetElement.equals(current.getElement()found = true;else previous = current; current = current.getNext();if(!found)throw new ElementNotFoundException("List");if(size()=1)head=tail=null;else if(current.equals(head)head=current.

36、getNext();else if(current.equals(tail) tail = previous; tail.setNext(null);else previous.setNext(current.getNext();count-;return current.getElement();b)有序列表的add操作（僅供參考）public class LinkedOrderedList42<T extends Comparable<? super T>> extends LinkedList42<T> implements OrderedListAD

37、T<T>Overridepublic void add(T element) LinearNode<T> node = new LinearNode<T>(element);LinearNode<T> temp = head;LinearNode<T> temp0 = temp;if(isEmpty()head = tail = node;count+;elseif(size()=1)if(head.getElement().compareTo(element)>0)node.setNext(head);head = node;

38、count+;elsehead.setNext(node);tail = node;count +;else if(head.getElement().compareTo(element)>=0)node.setNext(head);head = node;count+;elsewhile(temp !=tail && temp.getElement().compareTo(element)<0)temp0 = temp;temp = temp.getNext();if(temp = tail)if(temp.getElement().compareTo(eleme

39、nt)<0)temp.setNext(node);tail = node;count+;elsenode.setNext(temp);temp0.setNext(node);count+;elsenode.setNext(temp);temp0.setNext(node);count+;c)無序列表的操作public class LinkedUnorderedList42<T> extends LinkedList42<T> implements UnorderedListADT<T>Overridepublic void addToFront(T element) LinearNode<T> New = new LinearNode<T