20162330 2017-2018-1《程式設計與資料結構》第六周學習總結

2017-2018-1 學習總結目錄：　1　2　3　5　6　7　9　10　11　12

目錄

• 0. 教材學習内容總結

  * 0.1 隊列ADT

  * 0.2 使用隊列：編碼k值

  * 0.3 使用隊列：模拟票務櫃台

  * 0.4 實作隊列：使用連結清單

  * 0.5 隊列的實作：使用數組

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

  * 1.1 棧與隊列相比的相同點

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

• 3. 代碼托管

• 4. 上周考試錯題總結

• 5. 結對及互評

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

• 7. 學習進度條

• 8. 參考資料

教材學習内容總結

第15章 隊列

隊列ADT

• 隊列在一端添加元素，在另一端删除元素。（最先進入的元素最先離開）

  【推論】隊列是一個線性集合。

• 隊列的元素處理方式：FIFO（先進先出）
• 在棧中，隻在集合一端處理元素；在隊列中，集合兩端都有操作。
• 重要術語：enqueue是指在隊尾添加新元素；dequeue是指從對頭删除元素；first操作檢測對頭的元素。
• 其他方法在接口Queue的注釋中已經寫得很清楚了：

public interface Queue<T> {
    // Adds the specified element to the rear of the queue.
    public void enqueue(T element);

    // Removes and returns the element at the front of the queue.
    public T dequeue();

    // Returns a reference to the element at the front of the queue without removing it.
    public T first();

    // Returns true if the the queue contains no elements and false otherwise.
    public boolean isEmpty();

    // Returns the number of elements in the queue.
    public int size();

    // Returns a string representation of the queue.
    public String toString();
}
           

• 在非空隊列中，front始終指向隊頭元素，rear始終指向隊尾元素的下一個位置。

  

使用隊列：編碼k值

• Caesar 密碼是一個簡單的加密算法，但是它的加密方法非常容易被破解，移動位數固定造成加密的局限性。
• 如果使用重複變化的k值，就可以改進Caesar 編碼技術。自定義一個k值表，讓每個字元移動的位數不同。這樣一旦資訊比k值長，就可以重新回到表頭使用，既不容易被破解，又能适用于長資訊的處理。
• 新的加密方法對于相同的字元加密後得到不同的字元。

使用隊列：模拟票務櫃台

• 常用隊清單示等待的一列。

實作隊列：使用連結清單

• 便于找到指向連結清單中的第一個和最後一個元素的引用。
• 入隊操作：将目前最後一個元素的next引用指向新元素，并且rear引用重置為新的最後元素。
• 出隊操作：必須確定至少傳回一個元素。

隊列的實作：使用數組

• 政策：将隊列的一端固定在數組下标為0的地方。
• 非循環數組實作隊列時元素的移動得到O（n）階複雜度。
• 将數組看成一個環，可以避免移動元素。
• 入隊操作：

  (rear = rear + 1) % queue.length;

• 出隊操作：删除最大下标處的元素之後，front值必須置為0，其餘情況出隊front加1。
• 循環隊列：利用前端空閑空間存放新的隊列元素。

  

【傳回目錄】

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

• 【問題】：棧與隊列相比相同點有哪些？

• 解決方案 ：（查找相關資料）

  （1）之前分析過，棧在一端操作，而隊列在兩端操作，但是它們都是線性結構，資料元素具有“一對一”的邏輯關系；

  （2）插入操作都是限制在表尾進行；

  （3）都可以通過順序存儲結構（數組）和鍊式存儲結構實作；

  （4）在時間複雜度上，插入與删除操作都需要常數時間；在空間複雜度上，情況也相同；

  （5）（擴充）多棧鍊和多棧隊列的管理模式可以相同。在計算機系統軟體中，經常會出現同時管理和使用兩個以上棧或隊列的情況，若采用順序存儲結構實作棧和隊列，将會給處理帶來極大的不便，因而一般采用多個單連結清單來實作多個棧或隊列。

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

• 暫無

代碼托管

• 本周代碼上傳 ch15 檔案夾中，統計結果是第四五六周一共的代碼，其中第六周寫了260行代碼：

  （statistics.sh腳本的運作結果截圖）

  

上周考試錯題總結

• 還未給出解析。

結對及互評

本周結對學習情況

• 莫禮鐘本周比第三周的狀态好一點，雖然實驗隻完成了第一個和第五個，設計的方法比較簡單，但是都是自己做的。在學習十四章的過程中，他已經基本掌握了如何使用數組實作棧，其中一些比較重要的方法（push、pop）我已經看着他寫了一遍，希望多熟練已掌握的内容，并且再恢複一些學習狀态，繼續增加每周學習時間。
• 20162319
  • 結對學習内容
    • 線性表
    • 用數組實作棧（push、pop方法的實作）

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

　　本周算是比較忙的一周了，國慶之後的第一周并不輕松，除了運動會的一些雜事之外，本周的學習任務真心有點多。本周在課堂上我們又複習了查找與排序的内容，我的掌握情況還算過關，對于棧、隊列這部分内容我選擇“先聽課再看書”的方式。到現在為止，棧的基本内容掌握了，隊列的掌握情況還差很多，測試的成績也不算高。本周我的狀态有些下降，主要因為睡眠時間不足導緻，下周我會将精力集中回來，并且平衡好完成團隊任務和個人任務的時間。

• 【附1】教材及考試題中涉及到的英語：

  Chinese | English | Chinese | English

  :---😐:---😐:---😐:---:

  隊尾 | rear | 特征 | characteristic

  出隊 | dequeue | 可序列化的 | serializable

  入隊 | enqueue | 外部的 | external

  增量 | increment | 制止 | suppress

• 【附2】本周小組部落格

學習進度條

• | | 代碼行數（新增/累積）| 部落格量（新增/累積）|學習時間（新增/累積）| 重要成長 |

  |:--------😐 :----------------😐:----------------😐:---------------: |:-----😐

  | 目标 | 5000行 | 30篇 | 400小時 | |

  | 第一周 | 234/234 | 1/28 | 14/14 | 了解算法效率、大O符号等理論内容 |

  | 第二周 | 255/489 | 1/29 | 12/26 | 了解靈活的團隊、泛型的使用 |

  | 第三周 | 436/925 | 2/31 | 10/36 | 了解一些查找和排序的算法 |

  | 第四周 | 977/1902 | 3/34 | 10/46 | 掌握實作線性結構 |

  | 第五周 | 800/2702 | 2/36 | 12/58 | 掌握實作棧集合 |

  | 第六周 | 260/2962 | 1/37 | 8/64 | 掌握實作隊列集合 |

• 計劃學習時間：12小時
• 實際學習時間：8小時
• 有效學習時間：3小時
• 改進情況：學習内容有所增加，本周我的效率極低，下周必須恢複到之前的狀态，學習時務必心無旁骛。

參考資料

• 《Java程式設計與資料結構教程（第二版）》
• 《Java程式設計與資料結構教程（第二版）》學習指導