Объектно-ориентированное программирование, сравнивающее связанные списки

Question

У меня есть объекты класса Bit, который в основном является классом, в котором есть одно поле с именем value и оно имеет логическое значение.

public class Bit {

    private boolean value;

    public Bit() {
        this.value = false;
    }

    public Bit(boolean value) {
        this.value = value;
    }

    public boolean getValue() {
        return value;
    }
}

, и у него есть еще несколько методов.

, а затем у меня естькласс с именем number, который должен представлять большое число в их двоичном представлении, используя связанный список, где firstlink - это LSB, а lastlink - это MSB.например, если я вызываю конструктор Number num1 = new Number (6);тогда у меня будет связанный список, подобный следующему: 0 1 1 (null)

Теперь я хочу знать, как можно сравнить два объекта Number.так, например: если у меня есть num1, а номер num2 = новый номер (7);[1 1 1] тогда я хочу метод, который скажет мне, что num2 больше, чем num1

, чтобы сравнить два двоичных числа просто, я бы начал с MSB и сравнил каждый бит, и как только один будет больше другого,означает, что число больше.Я мог легко получить целочисленное значение каждой ссылки (бит), используя Bit.toInt ();

Так что я думал об итерации по списку и сравнении битов один за другим, проблема в том, что мой итератор помечается раньшеfirstlink (LSB), я знаю, что могу переместить его до конца и начать итерацию с помощью hasPrevious (), но у меня нет этого метода.Я хочу быть в состоянии сделать это, просматривая каждый список только один раз.Есть идеи?

public static boolean lessEq(Number num1, Number num2){ 
    Iterator<Bit> it1 = num1.bitIterator().;
    Iterator<Bit> it2 = num2.bitIterator();
}

Числовые конструкторы:

public Number(){
    list = new LinkedList<Bit>();
    list.add(new Bit(false));
}

/**
 * Constructs a new Number from an int.
 * @param number an int representing a decimal number
 */
public Number(int number) {  // assignment #1
    list = new LinkedList<Bit>();
    if(number == 0) list.add(new Bit(false));
    if (number < 0) throw new IllegalArgumentException("number cannot be negative");

    else {
        while (number > 0) {
            if (number % 2 == 0) {
                list.add(new Bit(false));
            }else list.add(new Bit(true));

            number = number / 2;
        }
    }
}

Редактировать: это работает Большое спасибо за комментарии!

Answer 1

Нет реальной проблемы в сравнении с младшим битом.Вам просто нужно отследить найденную разницу и отбросить ее, если вы найдете разницу в старшем (более значимом) бите.Проще всего сделать это рекурсивно:

public class Number implements Comparable<Number> {

    /** Linked list of bits, least significant bit first */
    Node lsb;

    public Number(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Negative numbers not supported, got " + n);
        }
        if (n == 0) {
            lsb = null;
        } else {
            lsb = new Node(new Bit(n % 2 != 0));
            n /= 2;
            Node tail = lsb;
            while (n > 0) {
                Node newNode = new Node(new Bit(n % 2 != 0));
                n /= 2;
                tail.setNext(newNode);
                tail = newNode;
            }
        }
    }

    @Override
    public int compareTo(Number other) {
        return compare(lsb, other.lsb, 0);
    }

    private int compare(Node left, Node right, int diffSoFar) {
        if (left == null) {
            if (nonZero(right)) {
                return -1;
            } else {
                return diffSoFar;
            }
        }
        if (right == null) {
            if (nonZero(left)) {
                return 1;
            } else {
                return diffSoFar;
            }
        }
        int localDiff = Boolean.compare(left.getData().getValue(), right.getData().getValue());
        if (localDiff != 0) {
            diffSoFar = localDiff;
        }
        return compare(left.getNext(), right.getNext(), diffSoFar);
    }

    private boolean nonZero(Node list) {
        if (list == null) {
            return false;
        }
        if (list.getData().getValue()) {
            return true;
        }
        return nonZero(list.getNext());
    }
}

Пример использования:

    Number six = new Number(6);
    Number seven = new Number(7);

    System.out.println("Comparing 6 and 7: " + six.compareTo(seven));
    System.out.println("Comparing 15 and 6: " + new Number(15).compareTo(six));

Вывод:

Comparing 6 and 7: -1
Comparing 15 and 6: 1

Я предполагаю следующееNode класс:

public class Node {
    private Node next;
    private Bit data;
    // Constructor, getters, setters
}

Answer 2

Вы можете сделать очевидную вещь: собрать биты в массив, а затем пройтись по двум массивам назад.Или вы можете использовать рекурсию и использовать стек для хранения:

public int compareTo(Number other) {
    Iterator<Bit> it1 = this.bitIterator();
    Iterator<Bit> it2 = other.bitIterator();
    return bitCompareTo(it1, it2);
}

private static int bitCompareTo(Iterator<Bit> it1, Iterator<Bit> it2) {
    if (!it1.hasNext() && !it2.hasNext()) return 0;

    boolean b1 = it1.hasNext() ? it1.next().getValue() : false;
    boolean b2 = it2.hasNext() ? it2.next().getValue() : false;

    int cmp = bitCompareTo(it1, it2);

    if (cmp != 0) return cmp;
    else return Boolean.compare(b1, b2);
}

Это обходит каждый итератор только один раз, но поскольку логика сравнения равна после рекурсивного вызова, вы получаетесравнения выполняются, когда они выталкиваются из стека вызовов - в обратном порядке, точно так, как мы этого хотим.

В основном: если мы достигаем конца обоих итераторов одновременно, мы не решаемся только по длине,и сигнализируем это 0, и мы начинаем наше рекурсивное принятие решений.(Если мы достигаем конца одного итератора раньше, мы предполагаем false для заполнения левой части этого числа нулями.) На каждом рекурсивном шаге, если мы решили (будь то по длине или по старшей паре битов), мы простопринять это решениеЕсли старшие биты не определены, мы пытаемся сравнить текущую битовую пару (и, если она равна, Boolean.compareTo вернет 0, сообщая на следующем уровне, что мы все еще не определились).Если мы проверили все биты и все еще не определились, мы просто скажем, что 0 теперь означает «равно» - именно то, что compareTo должно вернуть в этом случае.

Как только вы получите compareTo, это тривиально, чтобы определить другие операторы отношений.

Answer 3

1. Первоначально вы предполагаете, что оба числа равны.
2. Вы получаете биты от обоих чисел.Используйте ноль, если любой из них был исчерпан.
3. Если оба бита равны, вы не измените результат.
4. Если бит из числа A равен 1, то установите число A как большее.
5. Если бит из числа B равен 1, то установить число B на большее.
6. Если оба списка исчерпаны, вернуть результат.
7. В противном случае повторить с шага 2.

Это учитывает случай, когда вы разрешаете списки с ненужными нулевыми битами в качестве MSB.

Если вы хотите представить необычную домашнюю работу, вы можете начать с конца, следите за индексом, который вынаходимся и останавливаемся при первом сравнении, где биты не равны.

Answer 4

Я думаю, вы должны попробовать это:

public static boolean lessEq(Number num1, Number num2) {
    LinkedList<Bit> bits1 = num1.list;
    LinkedList<Bit> bits2 = num2.list;
    if(bits1.size() == bits2.size()) {
        for(int i = bits1.size() - 1; i >= 0; i++) { // reversed loop since the MSB is at the end of the list
            Bit bit1 = bits1.get(i);
            Bit bit2 = bits2.get(i);
            if(bit1.getValue() != bit2.getValue()) {
                if(bit1.getValue()){ // can be replaced with return !bit1.getValue() if you want
                    return false; // bit1's actual bit is true, bit2 is false, so bit1 is greater
                } else {
                    return true;
                }
            }
        }
        return true; // all bits are the same
    } else {
        if(bits1.size() > bits2.size()) { // can be replaced with return bits1.size() <= bits2.size() if you want
            return false; // first number has more elements, so it's greater
        } else {
            return true;
        }
    }
}

РЕДАКТИРОВАТЬ

В соответствии с комментариями вы можете сделать следующее (используя итераторы)

public static boolean lessEq(Number num1, Number num2) {
    Iterator<Bit> bits1 = num1.list.descendingIterator();
    Iterator<Bit> bits2 = num2.list.descendingIterator();
    while(bits1.hasNext() && bits2.hasNext()){
        Bit bit1 = bits1.next();
        Bit bit2 = bits2.next();
        if(bit1.getValue() != bit2.getValue()) {
            return !bit1.getValue();
        }
    }
    return bits2.hasNext();
}