實驗一 線性結構

實驗内容

實驗一 線性結構-1

ArrayList和LinkedList測試：檢視ArrayList和LinkedList的Java API幫助文檔，參考http://www.cnblogs.com/rocedu/p/4837092.html 用Junit對ArrayList和LinkedList的方法進行測試，要盡量覆寫正常情況，異常情況，邊界情況。

使用JUnit測試了ArrayList和LinkedList類的add,get,remove,isEmpty,remove等方法。

實驗一 線性結構-2

分别用Java的ArrayList和LinkedList實作有序線性表的合并：aList，bList都是非遞減線性表，合并後也是非遞減 public static List<？ extends Comparable> mergeSortedList(List<？ extends Comparable> aList, List<？ extends Comparable> bList) 測試mergeSortedList的正确性,要盡量覆寫正常情況，異常情況，邊界情況，送出測試代碼運作截圖，包含學号資訊。課下把代碼推送到代碼托管平台

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class exp2 {
    public static List<? extends Comparable> mergeSortedList(List<? extends Comparable> aList,
                                                             List<? extends Comparable> bList){
        if(aList instanceof ArrayList && bList instanceof ArrayList){
            for(Object o:bList)((ArrayList) aList).add(o);
            Collections.sort(aList);
            return aList;
        }
        if(aList instanceof LinkedList && bList instanceof LinkedList){
            for(Object o:bList)((LinkedList) aList).add(o);
            Collections.sort(aList);
            return aList;
        }
        return new ArrayList<>();
    }

}
           

通過在aList後追加元素，然後對aList進行排序，實作序列的有序合并

實驗一 線性結構-3

參考Java Foundation 3rd 第15.6節，用數組實作線性表List。用JUnit或自己編寫驅動類對自己實作的ArrayList進行測試，送出測試代碼運作截圖，要全屏，包含自己的學号資訊

public class MyArrayList<T> {
    private T[] list = null;
    private int cursor = -1;
    public boolean add(T t){
        if(this.list==null){
            this.list = (T[]) new Object[10];
            this.list[0] = t;
            cursor=0;
        }
        else {
            for(int i=0;i<this.list.length;i++){
                if(this.list[i]==null){
                    this.list[i]=t;
                    return true;
                }
            }
            T[] temp = (T[]) new Object[this.list.length+10];
            for(int i=0;i<this.list.length;i++){
                temp[i] = this.list[i];
            }
            temp[this.list.length] = t;
            this.list = temp;
            cursor += 1;
            return true;
        }
        return true;
    }
    public boolean isEmpty(){
        return this.list==null ? false:true;
    }
    public T get(int index){
        if(index<0 || index>cursor)return null;
        return this.list[index];
    }
}
           

通過申請Object數組，然後強制類型轉換來實作泛型數組，每次預留10個容量，超出時，申請一個大小為array.lenght+10的數組。

實驗一 線性結構-4

參考Java Foundation 3rd 第15.7節，用連結清單實作線性表List。用JUnit或自己編寫驅動類對自己實作的LinkedList進行測試，送出測試代碼運作截圖，要全屏，包含自己的學号資訊

public class MyLinkedList<T> {
    private Node<T> firstNode;
    public MyLinkedList(){
        firstNode = null;
    }
    public void addFirst(T t){
        Node<T> node = new Node(t);
        node.next = firstNode;
        firstNode = node;
    }
    public Node rmFirst(){
        Node<T> node = firstNode;
        firstNode = node.next;
        return firstNode;
    }
    public void add(int index,T t){
        Node newNode = new Node(t);
        Node currentNode = firstNode;
        Node previousNode = firstNode;
        if(index==0)addFirst(t);
        for(int i = 1;i<=index;i++){
            previousNode = currentNode;
            currentNode = currentNode.next;
        }
        previousNode.next = newNode;
        newNode.next = currentNode;
    }
    public T get(int index){
        Node currentNode = firstNode;
        Node previousNode = firstNode;
        if(index==0)return firstNode.data;
        for(int i = 1;i<=index;i++){
            previousNode = currentNode;
            currentNode = currentNode.next;
        }
        return (T) currentNode.data;
    }
    public void remove(int index){
        Node previousNode = firstNode;
        Node currentNode = firstNode;
        if(index==0)rmFirst();
        for(int i = 1;i<=index;i++){
            previousNode = currentNode;
            currentNode = currentNode.next;
        }
        previousNode.next = currentNode.next;

    }
}
class Node<T>{
    protected Node next;
    protected T data;
    public Node( T data){
        this. data = data;
    }
}
           

設計了Node類，包括資料域和指針，然後在MyLinkedList中通過改變不同Node的指針來實作連結清單的增加、删除和檢視操作。

實驗一 線性結構-5

源碼分析：參考http://www.cnblogs.com/rocedu/p/7483915.html對Java的ArrayList，LinkedList按要求進行源碼分析，并在實驗報告中展現分析結果

ArrayList繼承了抽象類AbstractList，實作了List、RandomAccess、Cloneable、java.io.Serializable接口，可以看到，類内部實作了很多函數，實作了低耦合和高内聚。

public  boolean add(E e) {

ensureCapacityInternal(size +  1); // Increments modCount!!

elementData[size++] = e;

return  true;

}
           

public boolean add(T t){
    if(this.list==null){
        this.list = (T[]) new Object[10];
        this.list[0] = t;
        cursor=0;
    }
    else {
        for(int i=0;i<this.list.length;i++){
            if(this.list[i]==null){
                this.list[i]=t;
                return true;
            }
        }
        T[] temp = (T[]) new Object[this.list.length+10];
        for(int i=0;i<this.list.length;i++){
            temp[i] = this.list[i];
        }
        temp[this.list.length] = t;
        this.list = temp;
        cursor += 1;
        return true;
    }
    return true;
}
           

以add方法為例，比較我和Java的實作，可以看到的就是，Java把容量的擴增寫進了ensureCapacityInternal方法，然後ensureCapacityInternal又有其他的幾個方法來支撐，到最後整個add方法看起來就很簡潔。

事實上，在ArrayList類和LinkedList中，很少會看到一個超過20行的方法，是以說程式的邏輯更多地通過方法名來展現（而非代碼），這種設計實作了代碼的子產品化，提高了可讀性。

總結

這周進行了數組的相關實驗，通過自己寫方法，更深入地了解了數組的實作，比較Java的代碼，進一步發現了自己在編碼過程中所存在的問題（代碼耦合度太高）。

王垠在程式設計的智慧中說：“程式設計是一種創造性的工作，是一門藝術。精通任何一門藝術，都需要很多的練習和領悟。”

真正的子產品化，并不是文本意義上的，而是邏輯意義上的。一個子產品應該像一個電路晶片，它有定義良好的輸入和輸出。實際上一種很好的子產品化方法早已經存在，它的名字叫做“函數”。每一個函數都有明确的輸入（參數）和輸出（傳回值），同一個檔案裡可以包含多個函數，是以你其實根本不需要把代碼分開在多個檔案或者目錄裡面，同樣可以完成代碼的子產品化。我可以把代碼全都寫在同一個檔案裡，卻仍然是非常子產品化的代碼。

尤其是這一段，其實真正意義上的子產品化是各個元件和部分各司其職，然後盡可能地将操作“原子化”，盡可能實作代碼的複用（而非通用）。另外一方面，是盡可能地寫出可讀的代碼，我讀過一些同學的代碼，包括變量的命名、函數的命名、注釋等等因素，都很難為提升代碼可讀性做出貢獻。讀Java的源碼，一個非常明顯的特征就是，注釋和命名都是高度标準化的，通過有意義的命名方式、聲明代碼位置和變量名縮寫，可以實作代碼高度可讀和工程化。

雖然自己這回在實驗中寫的代碼可能永遠也用不到，但是隻有自己親自去嘗試一回，才能高山仰止，發現自己和優秀程式員之間的差距，看到自己代碼内部存在的一些問題。