20182306 2019-2020-1 《數據結構與面向對象程序設計》第八周學習總結

教材學習內容總結

• 查找
  • 線性查找即按順序從前向后一個一個進行查找，但是為了提高代碼運行效率，可以在第一個位置設置哨兵，從后向前查找。如果查找到的位置是在哨兵位置，則說明未找到這一目標。
  • 折半查找：時間復雜度為O（log2n），效率高，但只能用于有序線性存儲結構。二分查找可以極大的減小算法的時間復雜度，但是缺點是其查找的內容必須是已經排序好的，對于那種不排序的雜亂的線性集合，二分查找法不適用，必須要先排序再查找。
  • 哈希表查找：使用mod算法來實現數據的快速存取
    • 開放地址法：線性探測再散列，若關鍵字對應地址非空，向后移位直到找到空地址存入，查找步驟與之相同。
    • 鏈地址法：將存儲空間定義為鏈表數組，每一個存儲空間都代表一個鏈表的表頭，若出現沖突，直接延長鏈表的長度，查找順序與存入順序相同。
• 排序
  • 插入排序：利用雙重循環和插入，逐漸將整個表從前向后實現有序排列。
  • 快速排序：根任意元素劃分表，再遞歸的對兩個子表進行排序，從而完成一整組的排序。
  • 歸并排序：先遞歸的把表對分成每個子表只含一個元素，再將子表按序合并。
  • 選擇排序：反復將具體的值放到它最終應該去的有序位置。

教材學習中的問題和解決過程

• 問題1：設置哨兵在數組第一位有什么意義。
• 問題1解決方案：可以使查找過程獲得一個一定可以找到的結果，此時只需要判斷找到元素的位置是不是在哨兵位置，就可以判斷原來序列中究竟是否含有這個元素。而這一過程可以使循環減少一個判斷語句，循環次數多了以后就可以顯著提高效率
• 問題2：快速排序法和歸并排序法是更加具有效率的排序方法，時間復雜度是多少？
• 問題2解決方案：
  歸并排序：時間復雜度是O(nlogn).
  快速排序：時間復雜度為O(n^2)。

代碼調試中的問題和解決過程

• 問題1：寫書上代碼時用了swap的方法，但是就出現了這樣的錯誤
  

• 問題1解決方案：對<? super T>這個部分進行了修改，
  

代碼托管

上周考試錯題總結

無考試

結對及互評

評分標準

1. 正確使用Markdown語法（加1分）

2. 模板中的要素齊全（加1分）

3. 教材學習中的問題和解決過程, 3個問題加3分

4. 代碼調試中的問題和解決過程, 2個問題加2分

5. 本周有效代碼超過300分行的（加2分）

6. 感想，體會不假大空的加1分

7. 排版精美的加一分

8. 進度條中記錄學習時間與改進情況的加1分

9. 有動手寫新代碼的加1分

10. 課后選擇題有驗證的加1分

11. 錯題學習深入的加1分

12. 點評認真，能指出博客和代碼中的問題的加1分

13. 結對學習情況真實可信的加1分

點評模板：

• 博客中值得學習的或問題：

  • 排版很好

• 代碼中值得學習的或問題：

  • 代碼增長量多，說明結對的同學這周很努力的在學習Java，我也要努力學習Java了
  • 倉庫有點混亂

• 參考示例

點評過的同學博客和代碼

• 本周結對學習情況

  • 20182313

• 上周博客互評情況

  • 20182313

其他（感悟、思考等，可選）

學習內容越來越多，任務量也是越來越大,然后好多知識都要自學，有點跟不上節奏了

學習進度條

• 計劃學習時間:20小時

• 實際學習時間:20小時

參考資料

• 《Java程序設計與數據結構教程（第二版）》

• 《Java程序設計與數據結構教程（第二版）》學習指導

• ...