JAVA鏈接存儲

首先定義一個接口，無論線性存儲的表還是鏈接存儲的表都實現(xiàn)這個接口。


package list;

public interface List {

Object value(int pos);//返回第幾個位置值

boolean add(Object obj,int pos);//在第幾個位置添加

Object remove(int pos);//刪除第幾個位置的值

int find(Object obj);//查詢第一個和obj相等的元素

boolean modify(Object obj,int pos);//修改某個值

boolean isEmpty();

int size();//長度

void forward();//前向輸出

void backward();//后向輸出

void clear();

List sort();//生成新的有序表，返回新的表

}


//有序表的接口（順序存儲和鏈接存儲）
package list;

public interface SortedList extends List {
        void insert(Object obj);
        Object delete(Object obj);
        int check(Object obj);
}

鏈接表需要定義節(jié)點
（有個疑問？head = new Node(head);這樣做不是循環(huán)鏈表。）
實現(xiàn)線性表的鏈接存儲

package list;

public class LinkList implements List {
    private Node head;//頭結點
    private int lenth;//長度
    public LinkList() {
        // TODO Auto-generated constructor stub
                //有個疑問？head = new Node(head);這樣做不是循環(huán)鏈表。
        lenth = 0;
        head = new Node(null);
        head.next =head;
        
    }
//Node作為一個內置類
    public class Node {
        Node next;
        Object ele;
        public Node(Node n){
            next = n;
        }
        public Node(Object e,Node n) {
            // TODO Auto-generated constructor stub
            next = n;
            ele = e;
            
        }
    }
    public Object value(int pos) {
        // TODO Auto-generated method stub 判斷給的位置是否超過范圍
        if(pos<1||pos>lenth){
            return null;
        }
        int num = 1;
        Node p = head.next;
        while(num<pos){
            num++;
            p = p.next;
        }
        return p.ele;
    }

    public boolean add(Object obj, int pos) {
        // TODO Auto-generated method stub
        if(pos<1||pos>lenth+1){
            return false;
        }
        
        int num = 1;
        Node p = head,q = head.next;
        while(num<pos){
            p=q;q=q.next;
            num++;
        }//找到插入位置
        p.next = new Node(obj,q);
        lenth++;
        return true;
    }

    public Object remove(int pos) {
        // TODO Auto-generated method stub
        if(pos<1||pos>lenth){
            return false;
        }
        int num = 1;
        Node p = head,q = head.next;
        while(num<pos){
            p=q;q=q.next;
            num++;
        }
        p.next = q.next;
        lenth--;
        return q.ele;
    }

    public int find(Object obj) {
        // TODO Auto-generated method stub
        int num =1;
        Node p = head.next;
        while(p!=head&&p.ele.equals(obj)==false){
            num++;
            p = p.next;
        }
        if(p==head)return -1;
        else
        return num;
    }

    public boolean modify(Object obj, int pos) {
        // TODO Auto-generated method stub
        if(pos<1||pos>lenth){
            return false;
        }
        int num = 1;
        Node p = head.next;
        while(num<pos){
            p=p.next;
            num++;
        }
        p.ele = obj;
        return true;
    }

    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return lenth==0;
    }

    public int size() {
        // TODO Auto-generated method stub
        return lenth;
    }

    public void forward() {
        // TODO Auto-generated method stub
        Node p = head.next;
        while(p!=head){
            System.out.println(p.ele.toString());
            p = p.next;
            
        }
    }

    public void backward() {
                   //新建一個數(shù)組，將鏈表中的拷貝進去，倒敘輸出
        // TODO Auto-generated method stub
        Object []a = new Object[lenth];
        int i =0;
        Node p = head.next;
        while(p!=head){
            a[i++]=p.ele;
            p = p.next;
        }
        for(i=lenth-1;i>=0;i--){
            System.out.println(a[i].toString());
        }
    }

    public void clear() {
        // TODO Auto-generated method stub
        lenth = 0;
        head.next = head;
    }

    public List sort() {
        // TODO Auto-generated method stub
        //首先建立空表
        //此次取出當前列表的值，
        //尋找插入節(jié)點，
        //插入
        //時間復雜度為n*n
        LinkList linklist = new LinkList();
        Node r = head.next;
        while(r!=head){
            Object a = r.ele;
            Node p = linklist.head,q = p.next;
            while(q!=linklist.head){
                Object y = q.ele;
                if(((Comparable)a).compareTo(y)<0)break;
                p=q;
                q=q.next;
            }
            p.next = new Node(a,q);
            lenth++;
            r = r.next
        }
        return linklist;
    }
}

總結：
在 獲取第幾個位置、刪除某個位置的值得時候，使用一個 指針 就可以了，p 指向當前節(jié)點
在 第幾個位置插入、刪除時，需要兩個指針，需要和前后聯(lián)系起來。 p指向前一個節(jié)點，q指向當前節(jié)點。注意 if 的條件，在第一個位置插入元素時，我參考的這本書(pos>len)，根本無法插入，有錯。修改了一下，可以在len+1的位置插入元素。

然后新建一個測試類，看看我們的鏈接存儲的表。

package list;

public class LinkListTest {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        LinkList list = new LinkList();
        int []a = {20,16,38,42,29};
        for(int i =0;i<a.length;i++){
            list.add(a[i], i+1);
        }
        list.forward();
        int n = (Integer)list.remove(2);
        System.out.println("刪除的元素"+n);
        System.out.println("刪除后的鏈表");
        list.forward();
        System.out.println("修改第二個元素");
        list.modify(100, 2);
        list.forward();
        System.out.print(list.size());
        LinkList a1 = new LinkList();
        a1 = (LinkList)list.sort();
        a1.forward();
        
    }

}

20
16
38
42
29
刪除的元素16
刪除后的鏈表
20
38
42
29
修改第二個元素
20
100
42
29
4
20
29
42
100

有序線性列表表的鏈接存儲
LinkSortedList 繼承 LinkList，實現(xiàn)接口 SortedList
在構造方法中，可以傳一個list進來，調用insert方法自動排序添加。

package list;

public class LinkSortedList extends LinkList implements SortedList {
    public LinkSortedList(){
        super();
    }
    public LinkSortedList(LinkList list){
        super();
        for(int i=1;i<=list.size();i++){
            this.insert(list.value(i));
        }
    }
    public void insert(Object obj) {
        //找到插入位置，下標從1開始，
        // TODO Auto-generated method stub
        int i ;
        for(i=1;i<=size();i++){
            if(((Comparable)obj).compareTo(this.value(i))<0)break;
            
        }
        add(obj, i);
    }

    public Object delete(Object obj) {
        // TODO Auto-generated method stub
        for(int i =1;i<=this.size();i++){
            if(((Comparable)obj).compareTo(this.value(i))<0)return null;
            if(((Comparable)obj).compareTo(this.value(i))==0)return remove(i);
        }
        return null;
    }

    public int check(Object obj) {
        // TODO Auto-generated method stub
        for(int i =1;i<=this.size();i++){
            if(((Comparable)obj).compareTo(this.value(i))<0)return -1;
            if(((Comparable)obj).compareTo(this.value(i))==0)return i;
        }
        return -1;
    }

}

結果自己跑就可以了。
下部分，記錄多項式求值。

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容