20162329 張旭升 2017 - 2018 《程序設計與數據結構》第五周總結

20162329 2017-2018-1 《程序設計與數據結構》第五周學習總結

教材學習內容總結

1.學習目標

• 了解集合的概念

• 了解并使用抽象數據類型

• 初步了解使用Java泛型

• 學習棧這種數據結構

• 用數組、鏈表實現棧

2.學習內容

集合的概念：

集合是手機并組織其他對象的對象，他定義了訪問和管理那些稱為集合元素的其他對象的一種具體方式。在我們所學習的Java編程語言的龐大類庫中，Java Collections API 就表示了一些使用不同方式實現的幾類集合的類。

抽象數據類型：

事物的抽象往往可以隱藏其中大部分細節，只需要通過一些小的接口就可以控制一個龐大的體系，所以在編程時抽象的思維是非常重要的，當你需要將一件事情用編程的方法實現的時候，首先要做的是將這件事情抽象出一些接口，就拿車來舉個例子：

首先車是一個龐大的體系，但是我們在控制車的時候卻并沒有去考慮車的內部零件是如何運作的，我們只是同過方向盤，踏板等來實現對它的控制，而這些我們實在知道的就是智造車的人給我們提供的接口。這樣以來用戶在使用它的時候就不需要考慮應該用哪個零件帶動哪個零件它才能轉彎這種實際問題。
這樣看我們的類也是一樣的，我們只是提供給用戶一些看的到的方法（函數），用戶通過這些方法的使用就能調用一個龐大的類，而并不需要去考慮類中的邏輯。

泛型

泛型是在Java 5.0后才開始支持基于泛型來定義類的，泛型的作用是在我們實例化類的對象時可以同時制定一種儲存數據的類型，這樣就避免了我們要為不同的被儲存類創建多個相應類型的類，大大減少了代碼復用，增加了代碼的可用能力，而這種方法在我們的Java Collections API 中尤其有用，因為既然是集合就必定需要儲存元素，但是每次用戶用來存儲的元素不可能都是一種類型，這時泛型的作用就大大體現。

棧

棧也是集合中的一種，他的模型就類似于現實中的羽毛球桶一樣，每次放置的羽毛球都只能放在前一個羽毛球的后面， 每次取羽毛球的時候只能從后面取最后一個放進去的，也就是一種LIFO結構

3.用數組、鏈表實現棧

• 數組實現棧 ArrayStack

         public class ArrayStack<T> implements Stack<T>{private final int DEFAULT_CAPACITY = 100;private int num;private T[] stack;public ArrayStack(){num = 0;stack = (T[])(new Object[DEFAULT_CAPACITY]);}public ArrayStack (int lenth){num = 0;stack = (T[])(new Object[lenth]);}public void push (T element){if (size() == stack.length)expandCapacity();stack[num] = element;num++;}public T pop() throws Exception{if (isEmpty())throw new Exception("Stack is empty");num--;T result = stack[num];stack[num] = null;return result;}public T peek() throws Exception{if (isEmpty())throw new Exception("Stack is empty");return stack[num -1];}public boolean isEmpty(){return (num == 0);}public int size(){return num;}public String toString(){String result = "";for (int scan = 0; scan < num; scan++)result = result + stack[scan].toString() + "\n";return result;}private void expandCapacity(){T[] larger = (T[])(new Object[stack.length*2]);for (int index=0; index < stack.length; index++)larger[index] = stack[index];stack = larger;}}

• 鏈表實現棧 LinkedStack

    public class LinkedStack<T> implements Stack<T>{private int num;private LinearNode<T> Next;public LinkedStack(){num = 0;Next = null;}public void push (T element){LinearNode<T> temp = new LinearNode<T> (element);temp.setNext(Next);Next = temp;num++;}public T pop() throws Exception{if (isEmpty())throw new Exception("Stack");T result = Next.getElement();Next = Next.getNext();num--;return result;}public T peek() throws Exception{if (isEmpty())throw new Exception("Stack");return Next.getElement();}public boolean isEmpty(){return (num == 0);}public int size(){return num;}public String toString(){String result = "";LinearNode current = Next;while (current != null){result = result + (current.getElement()).toString() + "\n";current = current.getNext();}return result;}}

Android 開發一個關于棧的小APP

界面布局：

EditText控件：輸入需要加入棧中的元素
Button控件：設置push壓棧操作和pop出棧操作
TextView控件：模擬棧的結構

活動代碼

public class MainActivity extends AppCompatActivity{EditText editText;Button pop,push;TextView Stack;String result;@Overrideprotected void onCreate(Bundle savedInstanceState) {super.onCreate(savedInstanceState);setContentView(R.layout.activity_main);editText = (EditText)findViewById(R.id.in);pop = (Button)findViewById(R.id.pop);push = (Button)findViewById(R.id.push);Stack = (TextView)findViewById(R.id.Stack);final ArrayStack<String> stack = new ArrayStack<>();push.setOnClickListener(new View.OnClickListener() {@Overridepublic void onClick(View v) {result = editText.getText().toString();stack.push(result);Stack.setText(stack.toString());}});pop.setOnClickListener(new View.OnClickListener() {@Overridepublic void onClick(View v) {try {stack.pop();Stack.setText(stack.toString());} catch (Exception e) {e.printStackTrace();}}});}
}

效果截圖

代碼托管

結對及互評

#### 本周并沒有在結對方面有什么合作項目

點評模板：

• 博客中值得學習的或問題：
  • 界面很好看
  • 問題分析可以更詳細

• 其他
  希望我們結對在這學期能相互促進，技術更上一層樓。

  本周結對學習情況

  • 20162302
  • 結對學習內容
    • 一起討論學習。

其他

這學期的課程難度增加了很多，有些時候感覺自己學到的東西還不扎實，導致有時候做一些懂非常困難，就算最終解決了也會花費很長時間，效率很低，希望能盡快適應新方式新進度。

學習進度條

	代碼行數（新增/累積）	博客量（新增/累積）	學習時間（新增/累積）	重要成長
目標	5000行	30篇	400小時
第一周	0/200	1/2	10/20	了解數據結構及算法
第二周	664/500	2/3	10/20	系統的學習了查找和排序
第五周	1333/1000	2/2	15/20	棧數據結構的學習

參考資料

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

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

• ...