Download presentation
Presentation is loading. Please wait.
1
資料結構使用Java 第5章 串列程式實作
2
課程內容 抽象資料型態ADT 串列(List)的介紹 實作串列 List的資料結構 List的ADT 串列主程式 新增元素到List尾端
3
抽象資料型態 － ADT的涵義 抽象資料型態 (ADT，abstract data types)
隱藏內部細節 展現平易外觀的目的 利如飲料販賣機的面板 理論上，我們常把ADT定義為將資料規格 (specification) 與實作 (implementation) 分開 的資料型態。
4
ADT的實例
5
陣列的基本操作 陣列的作用是提供循序的空間供我們使用 只需用一個唯一的索引值，便能任意指定要放入 或取出哪一個位置內的資料
因此陣列的基本操作也就非常簡單，只有『產 生』、『寫入』、與『讀取』三個動作。 有很多實際應用的概念或事物都適合用陣列來表 示，最常見的是串列、矩陣 (matrix) 與多項式 (polynomial)。
6
認識串列 將字典裡頭的字彙當成元素，則整本字典就是字 彙所形成的串列。 由身分證字號所形成的戶籍資料庫也可以看成是 一種串列。
7
串列的資料結構設計 串列的大小會隨著串列的使用而不斷地改變，但 陣列的大小在宣告以後就固定了。
8
串列的操作與處理方法 串列的操作包括 : 新增元素到串列尾端 (append) 讀取元素 (read) 寫入 (write)
將元素插入到串列中 (insert) 刪除元素 (delete) 傳回串列的元素數目 (listSize) 以及傳回儲存串列的陣列大小 (arraySize)。
9
串列的程式實作 [串列的ADT] list.java
![串列的程式實作 [串列的ADT] list.java](http://slidesplayer.com/slide/17181636/99/images/9/%E4%B8%B2%E5%88%97%E7%9A%84%E7%A8%8B%E5%BC%8F%E5%AF%A6%E4%BD%9C+%5B%E4%B8%B2%E5%88%97%E7%9A%84ADT%5D+list.java.jpg "串列的程式實作 [串列的ADT] list.java")
10
串列的程式實作 [串列的主程式] testList.java
![串列的程式實作 [串列的主程式] testList.java](http://slidesplayer.com/slide/17181636/99/images/10/%E4%B8%B2%E5%88%97%E7%9A%84%E7%A8%8B%E5%BC%8F%E5%AF%A6%E4%BD%9C+%5B%E4%B8%B2%E5%88%97%E7%9A%84%E4%B8%BB%E7%A8%8B%E5%BC%8F%5D+testList.java.jpg "串列的程式實作 [串列的主程式] testList.java")
11
[串列的產生] [串列的實作程式] myList.java 下面用一維陣列來儲存串列
另外使用一個程式變數listSize來記載串列的長度， 也就是串列元素的數目。 int myArray[ ]; int listSize=0; 透過建構元進行初始化動作
![[串列的產生] [串列的實作程式] myList.java 下面用一維陣列來儲存串列](http://slidesplayer.com/slide/17181636/99/images/11/%5B%E4%B8%B2%E5%88%97%E7%9A%84%E7%94%A2%E7%94%9F%5D+%5B%E4%B8%B2%E5%88%97%E7%9A%84%E5%AF%A6%E4%BD%9C%E7%A8%8B%E5%BC%8F%5D+myList.java+%E4%B8%8B%E9%9D%A2%E7%94%A8%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97%E4%BE%86%E5%84%B2%E5%AD%98%E4%B8%B2%E5%88%97.jpg "另外使用一個程式變數listSize來記載串列的長度， 也就是串列元素的數目。 int myArray[ ]; int listSize=0; 透過建構元進行初始化動作.")
12
[新增元素到串列尾端 (append)] 把元素新增到串列尾端並不影響其他的串列元素 可以用listSize來決定新增的元素的位置
myArray[listSize] = element
![[新增元素到串列尾端 (append)] 把元素新增到串列尾端並不影響其他的串列元素 可以用listSize來決定新增的元素的位置](http://slidesplayer.com/slide/17181636/99/images/12/%5B%E6%96%B0%E5%A2%9E%E5%85%83%E7%B4%A0%E5%88%B0%E4%B8%B2%E5%88%97%E5%B0%BE%E7%AB%AF+%28append%29%5D+%E6%8A%8A%E5%85%83%E7%B4%A0%E6%96%B0%E5%A2%9E%E5%88%B0%E4%B8%B2%E5%88%97%E5%B0%BE%E7%AB%AF%E4%B8%A6%E4%B8%8D%E5%BD%B1%E9%9F%BF%E5%85%B6%E4%BB%96%E7%9A%84%E4%B8%B2%E5%88%97%E5%85%83%E7%B4%A0+%E5%8F%AF%E4%BB%A5%E7%94%A8listSize%E4%BE%86%E6%B1%BA%E5%AE%9A%E6%96%B0%E5%A2%9E%E7%9A%84%E5%85%83%E7%B4%A0%E7%9A%84%E4%BD%8D%E7%BD%AE.jpg "myArray[listSize] = element.")
13
[插入一個串列元素 (insert)] 有時候可能需要將新元素插入到串列的特定位置， 這時就要有個更複雜的插入動作。
![[插入一個串列元素 (insert)] 有時候可能需要將新元素插入到串列的特定位置， 這時就要有個更複雜的插入動作。](http://slidesplayer.com/slide/17181636/99/images/13/%5B%E6%8F%92%E5%85%A5%E4%B8%80%E5%80%8B%E4%B8%B2%E5%88%97%E5%85%83%E7%B4%A0+%28insert%29%5D+%E6%9C%89%E6%99%82%E5%80%99%E5%8F%AF%E8%83%BD%E9%9C%80%E8%A6%81%E5%B0%87%E6%96%B0%E5%85%83%E7%B4%A0%E6%8F%92%E5%85%A5%E5%88%B0%E4%B8%B2%E5%88%97%E7%9A%84%E7%89%B9%E5%AE%9A%E4%BD%8D%E7%BD%AE%EF%BC%8C+%E9%80%99%E6%99%82%E5%B0%B1%E8%A6%81%E6%9C%89%E5%80%8B%E6%9B%B4%E8%A4%87%E9%9B%9C%E7%9A%84%E6%8F%92%E5%85%A5%E5%8B%95%E4%BD%9C%E3%80%82.jpg "[插入一個串列元素 (insert)] 有時候可能需要將新元素插入到串列的特定位置， 這時就要有個更複雜的插入動作。")
14
[插入一個串列元素 (insert)]
![[插入一個串列元素 (insert)]](http://slidesplayer.com/slide/17181636/99/images/14/%5B%E6%8F%92%E5%85%A5%E4%B8%80%E5%80%8B%E4%B8%B2%E5%88%97%E5%85%83%E7%B4%A0+%28insert%29%5D.jpg "[插入一個串列元素 (insert)]")
15
[刪除一個串列元素 (delete)] 刪除一個串列元素，後面的串列元素要往前補
以下的例子把myArray[1]裡頭儲存的數字從串列 中移除，所以後面的數字必須往前補到空出來的 陣列位置上。
![[刪除一個串列元素 (delete)] 刪除一個串列元素，後面的串列元素要往前補](http://slidesplayer.com/slide/17181636/99/images/15/%5B%E5%88%AA%E9%99%A4%E4%B8%80%E5%80%8B%E4%B8%B2%E5%88%97%E5%85%83%E7%B4%A0+%28delete%29%5D+%E5%88%AA%E9%99%A4%E4%B8%80%E5%80%8B%E4%B8%B2%E5%88%97%E5%85%83%E7%B4%A0%EF%BC%8C%E5%BE%8C%E9%9D%A2%E7%9A%84%E4%B8%B2%E5%88%97%E5%85%83%E7%B4%A0%E8%A6%81%E5%BE%80%E5%89%8D%E8%A3%9C.jpg "以下的例子把myArray[1]裡頭儲存的數字從串列 中移除，所以後面的數字必須往前補到空出來的 陣列位置上。")
16
[刪除一個串列元素 (delete)]
![[刪除一個串列元素 (delete)]](http://slidesplayer.com/slide/17181636/99/images/16/%5B%E5%88%AA%E9%99%A4%E4%B8%80%E5%80%8B%E4%B8%B2%E5%88%97%E5%85%83%E7%B4%A0+%28delete%29%5D.jpg "[刪除一個串列元素 (delete)]")
17
[讀取(read)] 要從串列讀取資料，必須指定元素的位置。
由於串列元素是按先後順序不間斷地儲存在陣列 中，所以串列元素在串列中的次序剛好就是該元 素儲存在陣列上對應的索引。
![[讀取(read)] 要從串列讀取資料，必須指定元素的位置。](http://slidesplayer.com/slide/17181636/99/images/17/%5B%E8%AE%80%E5%8F%96%28read%29%5D+%E8%A6%81%E5%BE%9E%E4%B8%B2%E5%88%97%E8%AE%80%E5%8F%96%E8%B3%87%E6%96%99%EF%BC%8C%E5%BF%85%E9%A0%88%E6%8C%87%E5%AE%9A%E5%85%83%E7%B4%A0%E7%9A%84%E4%BD%8D%E7%BD%AE%E3%80%82.jpg "由於串列元素是按先後順序不間斷地儲存在陣列 中，所以串列元素在串列中的次序剛好就是該元 素儲存在陣列上對應的索引。")
18
[寫入(write)] 提供一個值，並指定接收這個值的串列位置
寫入同樣可以透過函式的呼叫來執行，或者直接 在程式中將一個變數或常數的值直接透過索引存 入到串列的正確位置。
![[寫入(write)] 提供一個值，並指定接收這個值的串列位置](http://slidesplayer.com/slide/17181636/99/images/18/%5B%E5%AF%AB%E5%85%A5%28write%29%5D+%E6%8F%90%E4%BE%9B%E4%B8%80%E5%80%8B%E5%80%BC%EF%BC%8C%E4%B8%A6%E6%8C%87%E5%AE%9A%E6%8E%A5%E6%94%B6%E9%80%99%E5%80%8B%E5%80%BC%E7%9A%84%E4%B8%B2%E5%88%97%E4%BD%8D%E7%BD%AE.jpg "寫入同樣可以透過函式的呼叫來執行，或者直接 在程式中將一個變數或常數的值直接透過索引存 入到串列的正確位置。")
19
[列出所有串列元素(printList)]
將串列中的元素一一地列印出來，用來列印出目 前串列中的元素。串列元素的數目由listSize來決 定。 for (int i=0; i<listSize; i++) System.out.print(this.myArray[i]+" ");
![[列出所有串列元素(printList)]](http://slidesplayer.com/slide/17181636/99/images/19/%5B%E5%88%97%E5%87%BA%E6%89%80%E6%9C%89%E4%B8%B2%E5%88%97%E5%85%83%E7%B4%A0%28printList%29%5D.jpg "將串列中的元素一一地列印出來，用來列印出目 前串列中的元素。串列元素的數目由listSize來決 定。 for (int i=0; i<listSize; i++) System.out.print(this.myArray[i]+ );")
20
串列與鏈結串列 串列的缺點： 改良─鏈結串列(Linked List) 串列的大小受到陣列的限制。
插入或刪除一個元素，其後面所有元素都要修正。 改良─鏈結串列(Linked List) 鏈結串列的大小可以無限制擴增 插入與刪除元素動作小，不會影響其他元素。
Similar presentations
