歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

Java實現線性表-順序表示和鏈式表示

順序表示和鏈式表示的比較:

1.讀寫方式:順序表可以順序存取,也可以隨機存取;鏈表只能從表頭順序存取元素;

2.邏輯結構與物理結構:順序存儲時,邏輯上相鄰的元素其對應的物理存儲位置也相鄰;鏈式存儲時,邏輯上相鄰的元素,其物理存儲位置則不一定相鄰;

3.查找、插入和刪除操作:

  按值查找,當線性表在無序的情況下,兩者的時間復雜度均為o(n);而當順序表有序時,可采用折半查找,此時時間復雜度為o(log n);

  按位查找,順序表支持隨機訪問,時間復雜度為o(1);而鏈表的平均時間復雜度為o(n)。

  順序表的插入和刪除操作平均需要移動半個表長的元素;鏈表的插入、刪除操作時,只需修改相關節點的指針即可。

4.空間分配:順序存儲一般是基於靜態存儲分配,一單存儲空間裝滿就不能擴充;鏈式存儲的節點空間只有在需要的時候申請分配,只要內存有足夠的空間即可分配。

順序表示的實現:

public class ArrayList<E> {
    final int defaultSize=0; 
    int maxSize;  //線性表的最大長度
    int length;  //線性表當前長度
    Object[] arrayList;  //存儲線性表的數組
   
    /*
    * 構造函數
    */
    public ArrayList(int size){
        initList(size);
    }
   
        //按給定size初始化順序表
    public void initList(int size) {
        if(size < 0){
            throw new RuntimeException("數組大小錯誤:" + size);
        }else{
            this.maxSize= size;
            this.length=0;
            this.arrayList = new Object[size];
        }           
    }

        //表長
    public int length() {
        return length;
    }

        //按值查找
    public int locateElem(Object e) {
        for(int i=0 ;i<length;i++){
            if(arrayList[i] == e){
                return i;
            }
        }
        return -1;
    }

        //按位查找
    public Object getElem(int i) {
        if(i<0 || i>=length ){
            throw new RuntimeException("參數出錯:"+i);
        }
        if(length ==0){
            throw new RuntimeException("順序表為空");
        }
        return arrayList[i];
    }

        //插入
    public void insert(int i, Object e) {
        if(i<0 || i>length+1 ){
            throw new RuntimeException("新元素插入位置有誤:"+i);
        }
        if(i >= maxSize){
            throw new RuntimeException("順序表已滿,不能再插入新的元素");
        }
        for(int j=length;j<i; j--){
            arrayList[j]=arrayList[j-1];
        }
        arrayList[i]=e;
        length++;
    }

        //刪除
    public void delete(int i, Object e) {
        if(i<0 || i > length-1){
            throw new RuntimeException("需刪除元素位置有誤:"+i);
        }
        if(length == 0){
            throw new RuntimeException("順序表為空,不能刪除元素");
        }
        for(int j=i;j<length-1;j++){
            arrayList[j] = arrayList[j+1];
        }
        arrayList[length-1]="";
        length--;
    }

      //判空
    public boolean isEmpty() {
        return length==0 ? true : false;
    }

        //刪除順序表
    public void destroyList() {
        this.arrayList=null;
        this.length=0;
        this.maxSize=0;
    }
}

單鏈表表示的實現:

class Node<E>{
    E e;  //數據
    Node<E> next; //下一個節點
   
    Node(){}
   
    Node(E e){
        this.e = e;
        this.next = null;
    }
}

public class LinkedList<E> {
    private Node<E> header = null;  //頭結點
    int size=0;    //鏈表大小
   
    public LinkedList() {
        this.header = new Node<E>();
    }

    //得到鏈表的長度
    public int length() {
        return size;
    }

    //按值查找節點,返回該節點的位置
    public int locateElem(E e) {
        Node<E> temp = header;
        int count = 1;
        while(temp.next != null && temp.e != e){
            temp = temp.next;
            count ++;
        }
        return count;
    }

    //找到第index個位置的節點
    public Node<E> getNode(int index) {
        if(index > size || index < 0){
            throw new RuntimeException("索引值有錯:" + index);
        }
        Node<E> temp = new Node<E>();
        temp = header;
        int count=1;
        while(count != index){
            temp = temp.next;
            count ++;
        }
        return temp;
    }

    //尾添加
    public boolean addToLast(E e) {
        if(size == 0){
            header.e = e;
        }else{
            Node<E> newnode = new Node<E>(e);  //根據需要添加的內容封裝為節點
            Node<E> last = getNode(size); //得到最後一個節點
            last.next = newnode;       
        }
        size ++;
        return true;
    }
   
    //頭添加
    public boolean addTofirst(E e) {
        if(size == 0){
            header.e = e;
        }else{
            Node<E> newnode = new Node<E>(e);  //根據需要添加的內容封裝為節點
            newnode.next = header.next;
            header.next = newnode;
        }
        size ++;
        return true;
    }

    //插入到第index個的位置
    public boolean insert(int index, E e) {
        Node<E> newnode = new Node<E>(e);  //根據需要添加的內容封裝為節點
        Node<E> cnode = getNode(index-1);  //得到第index-1個節點
        newnode.next = cnode.next;
        cnode.next = newnode;
        size++;
        return true;
    }

    //刪除第index個節點
    public boolean delete(int index) {
        Node<E> prinode = getNode(index-1);  //得到被刪除的節點的前一個節點
        Node<E> delnode = prinode.next;    //得到被刪除的節點
        prinode.next = delnode.next;
        size --;
        return true;
    }

    //判空
    public boolean isEmpty() {
        return size==0 ? true : false;
    }

    public void destroyList() {
        header = null;
        size = 0;
    }
   
    //輸出
    public String toString(){
        StringBuilder s = new StringBuilder("[");
        Node<E> temp = header;
        for(int i=0; i < size;i++){
            s.append(temp.e.toString()+" ");
            temp = temp.next;           
        }
        s.append("]");
        return s.toString();
    }
}

雙鏈表表示的實現

class TNode<E>{
    E e;
    TNode<E> prior, next;
   
    TNode(){}
    TNode(E e){
        this.e = e;
        prior = null;
        next = null;
    }
}

public class DoubleLinkedList<E> {
    private TNode<E> header = null;  //頭結點
    int size=0;    //鏈表大小
   
    public DoubleLinkedList(){
        this.header = new TNode<E>();
    }
   
    //尾添加
    public boolean addToLast(E e) {
        if(size == 0){
            header.e = e;
        }else{
            TNode<E> TNode = new TNode<E>(e);  //根據需要添加的內容封裝為節點
            TNode<E> last = getNode(size); //得到最後一個節點
            last.next = TNode;
            TNode.prior=last;
        }
        size ++;
        return true;
    }   
   
   
    //找到第index個位置的節點
    public TNode<E> getNode(int index){
        if(index > size || index < 0){
            throw new RuntimeException("索引值有錯:" + index);
        }
        TNode<E> temp = new TNode<E>();
        temp = header;
        int count =1;
        while(count != index){
            temp = temp.next;
            count ++;
        }
        return temp;
    }
   
    //插入到第index個的位置
    public boolean insert(int index,E e){
        TNode<E> TNode = new TNode<E>(e);
        TNode<E> cnode = getNode(index-1); //找到第index-1個位置的節點
        TNode.next=cnode.next;
        TNode.prior = cnode;
        cnode.next.prior = TNode;
        cnode.next = TNode;
        size++;
        return true;
    }
   
    //刪除第index個節點
    public boolean delete(int index){
        TNode<E> delnode = getNode(index);
        delnode.prior.next=delnode.next;
        delnode.next.prior= delnode.prior;
        size--;
        return true;
    }
}

Copyright © Linux教程網 All Rights Reserved