JAVA链接存储

首先定义一个接口，无论线性存储的表还是链接存储的表都实现这个接口。

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);
}

链接表需要定义节点
（有个疑问？head = new Node(head);这样做不是循环链表。）
实现线性表的链接存储

package list;

public class LinkList implements List {
    private Node head;//头结点
    private int lenth;//长度
    public LinkList() {
        // TODO Auto-generated constructor stub
                //有个疑问？head = new Node(head);这样做不是循环链表。
        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() {
                   //新建一个数组，将链表中的拷贝进去，倒叙输出
        // 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
        //首先建立空表
        //此次取出当前列表的值，
        //寻找插入节点，
        //插入
        //时间复杂度为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 指向当前节点
在 第几个位置插入、删除时，需要两个指针，需要和前后联系起来。 p指向前一个节点，q指向当前节点。注意 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，实现接口 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;
    }

}

结果自己跑就可以了。
下部分，记录多项式求值。