内部类实现双向循环链表

内部类DL Node 实现双链表


题:双向循环链表_实践应用
定义双向循环链表,解决如下的问题:

有 n 个孩子顺时针站成一圈,其编号为:1,2,3,... n

从1号孩子开始顺时针数数,每个孩子数一个数,遇到7的倍数或数字中含有7,则该孩子不出声,只拍一下手,数数的方向逆转,下一个孩子数下一个数字。

例如:1,2,3...6,拍手,则接下来,6号孩子数8,5号孩子数9 ....

请模拟该过程,如果有20个孩子,求哪个孩子要数100。

源码DLList.java


package DLList;

public class DLList {
    
    private int s = 0;
    private DLNode head;
    private int len = 0;

    public DLList() {
    }
    public DLList(int x) {
        len = x;
    }
    public void init() {
        if (len!=0) {
            for (int i=0; i<len; i++) {
                addA(0);
            }
        }
    }
    public void addA(int x) {
        DLNode p = new DLNode(x);
        if (s<len) {
            if (head==null) {
                head = p;
                head.setInit();
            }
            else {
                p.setNext(head.getNext());
                p.setPrev(head);
                head.getNext().setPrev(p);
                head.setNext(p);
                head = p;
            }
            s++;
        }
        else {
            if (head==null) {
                head = p;
            }
            else {
                if (head.getNext().getInit()) {
                    p.setInit();
                }
                p.setNext(head.getNext().getNext());
                p.setPrev(head);
                head.getNext().getNext().setPrev(p);
                head.setNext(p);
                head = p;
            }
        }
    }
    public void addB(int x) {
        DLNode p = new DLNode(x);
        if (s<len) {
            if (head==null) {
                head = p;
                head.setInit();
            }
            else {
                p.setNext(head);
                p.setPrev(head.getPrev());
                head.getPrev().setNext(p);
                head.setPrev(p);
                head = p;
            }
            s++;
        }
        else {
            if (head==null) {
                head = p;
            }
            else {
                if (head.getPrev().getInit()) {
                    p.setInit();
                }
                p.setNext(head);
                p.setPrev(head.getPrev().getPrev());
                head.getPrev().getPrev().setNext(p);
                head.setPrev(p);
                head = p;
            }
        }
    }
    public int size() {
        return s;
    }
    public int srch(int x) {
        return head.search(x, s);
    }
    public void show() {
        if (head!=null) {
            head.showNode(s);
        }
    }

    //Inner class
    class DLNode {
        private int data;
        private DLNode prev;
        private DLNode next;
        private boolean init;
        public DLNode(int x) {
            data = x;
            prev = this;
            next = this;
            init = false;
        }
        public boolean getInit() {
            return init;
        }
        public void setInit() {
            init = true;
        }
        public int getData() {
            return data;
        }
        public void setData(int x) {
            data = x;
        }
        public DLNode getPrev() {
            return prev;
        }
        public DLNode getNext() {
            return next;
        }
        public void setPrev(DLNode x) {
            prev = x;
        }
        public void setNext(DLNode x) {
            next = x;
        }
        public void showNode(int x) {
            DLNode p = this;
            while (p.init==false) {
                p = p.next;
            }
            for (int i=0; i<x; i++) {
                System.out.println(p.data);
                p = p.next;
            }
        }
        public int search(int x, int s) {
            DLNode p = this;
            while (p.init==false) {
                p = p.next;
            }
            int i = 0;
            while (p.data!=x && i<s) {
                p = p.next;
                i++;
            }
            if (i==s) {
                return -1;
            }
            else {
                return i+1;
            }
        }
    }
}

源码2PlayGame.java


import DLList.DLList;

class Rule {
    public static boolean Set(int x, int t) {
        String s1 = ""+x;
        String s2 = ""+t;
        if (t%x==0) {
            return true;
        }
        else if (s2.indexOf(s1)!=-1) {
            return true;
        }
        else {
            return false;
        }
    }
    public static boolean Sign(boolean x) {
        if (x) {
            return false;
        }
        else {
            return true;
        }
    }
}

public class PlayGame {
    public static void game(int p, int c, int n) {
        DLList t = new DLList(p);
        t.init();
        boolean sig = true;
        for (int i=1; i<c+1; i++) {
            if (sig) {
                t.addA(i);
            }
            else {
                t.addB(i);
            }
            if (Rule.Set(7,i)) {
                sig = Rule.Sign(sig);
            }
        }
        t.show();
        System.out.println("\nNo. "+t.srch(n));
    }
    public static void main(String[] args) {
        game(20,100,100);
    }
}

参考——

  1. Wenku
  2. 2cto

发表评论

电子邮件地址不会被公开。 必填项已用*标注