實驗一：實驗報告
課程：程序設計與數據結構
班級： 1623
姓名： 張旭升
學號：20162329
指導教師：婁嘉鵬 王志強
實驗日期：9月25日
實驗密級： 非密級
預習程度： 已預習
必修/選修： 必修
實驗序號： cs_29
實驗名稱： Java線性表的應用，實現和分析
實驗內容
1. Java中的線性表的測試：過程，問題
2. Java中的線性表的應用：過程，問題
3. 順序表的實現（偽代碼，產品代碼，測試代碼）：過程（分析，設計，實現，測試），問題
4. 鏈表的實現（偽代碼，產品代碼，測試代碼）：過程（分析，設計，實現，測試），問題
5. Java ArrayList，LinkedList源碼分析：過程，學到的技巧
實驗要求
1.沒有Linux基礎的同學建議先學習《Linux基礎入門（新版）》《Vim編輯器》 課程
完成實驗、撰寫實驗報告，實驗報告以博客方式發表在博客園，注意實驗報告重點是 運行結果，遇到的問題(工具查找，安裝，使用，程序的編輯，調試，運行等)、解決 辦法（空洞的方法如“查網絡”、“問同學”、“看書”等一律得0分）以及分析（從中可 以得到什么啟示，有什么收獲，教訓等）。報告可以參考范飛龍老師的指導
嚴禁抄襲，有該行為者實驗成績歸零，并附加其他懲罰措施。
實驗過程
一.Java中線性表的測試
1.MyList類：
Java中提供了兩種線性表，分別是ArrayList和LinkedList，我分別對它們每種類的其中三個主要方法進行了Junit單元測試：
| ArrayList | LinkedList |
|---|---|
| boolean : isEmpty() | boolean : contains(Object o) |
| boolean : add(Object o) | boolean : add(Object o) |
| Object : remove(int index) | boolean : remove(Object o) |
注意：
在測試中我發現，兩種線性表在Java源代碼中是受保護無法直接進行單元測試的，我只能自己寫一個
MyList來繼承上面兩個類，然后通過將需要測試的方法復寫一下只需要調用父類的該方法就可以直接進行單元測試了。
2.測試結果及代碼
測試代碼
ArrayList測試代碼
LinkedList測試代碼
測試截圖
二.用Java線性表實現有序線性表的合并
實現代碼
- 實現代碼
測試代碼
測試截圖
三.用數組實現線性表
1.實現代碼分析：
創建數組線性表的思路和課上的Bag類是很類似的，具體做法也是在Bag類的基礎上進行了一些功能的改進，比如實現了存儲空間的自增長等
思路：
在每次往數組中線性的添加元素時都會進行一個判斷，如果數組已經沒有空位時，就會進行一個變換的操作，新建一個多10位的數組（數組初始大小為10）然后將原數組中的元素遍歷出來放入新建數組，然后將新建數組賦給原數組的引用，即使數組長度增加了10
2.實現代碼及測試
- 實現代碼
- 測試代碼
3.測試截圖
四.用鏈表實現線性表
1.實現代碼分析：
定義一個鏈表的類，然后在類中創建兩個變量，一個為泛型變量，一個是該類的對象，這個類的對象將會作為一個指針，在鏈表中每創建一個新的元素時，就會> > 實將指針實例化。
2.實現代碼及測試代碼
- 實現代碼
- 測試代碼
3.測試截圖
五.ArrayList與LinkedList源碼分析
1.源碼調取
我所分析的源碼是從IDEA中直接調取的，具體操作是在IDEA中連按兩次Shift鍵就會彈出一個搜索框，然后在搜索框中分別搜索ArrayList和LinkedList就可以調出 這兩個類的源代碼
2.源碼分析
1.ArrayList是實現了基于動態數組的數據結構，LinkedList基于鏈表的數據結構。
2.對于隨機訪問get和set，ArrayList覺得優于LinkedList，因為LinkedList要移動指針。
3.對于新增和刪除操作add和remove，LinedList比較占優勢，因為ArrayList要移動數據。
參考資料：
java集合框架05——ArrayList和LinkedList的區別
Java中ArrayList和LinkedList區別
.pdf)
