Как программировать собственные массивы и списки

Question

Мне нужно запрограммировать несколько разных типов бинарных деревьев. Однако я не могу использовать утилиты, такие как массивы или коллекции. Предлагается создать свой собственный массив, если в этом будет необходимость. Проблема в том, что я даже не знаю, с чего начать. Как я могу построить, скажем, двумерный массив?

Answer 1

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

public class ListNode<T> {
  private T payload;
  private ListNode<T> nextNode;
}

public class TreeNode<T> {
  private T payload;
  private TreeNode<T> leftChild, rightChild;
}

Answer 2

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

http://en.wikipedia.org/wiki/Binary_tree

или http://en.wikipedia.org/wiki/List_of_data_structures

(ответ на вопрос: Для 2d-массива создайте 1-мерный массив и сохраните 1-мерные массивы в 1-мерном массиве. Можно эмулировать встроенные массивы, создавая собственную реализацию связанного списка. Но это ни эффективно, ни то, что задумал ваш учитель.

(вдохновение для реального вопроса, о котором вы не знаете, что задаете:

Примерно такова основная структура данных для двоичного дерева поиска ...

class Node {
     Object value;
     Node left;
     Node right;
} )

Answer 3

Редактировать : Хорошо, все упоминали списки, но давайте не будем забывать, что вы можете реализовывать двоичные деревья также в массивах, как в кучах.Таким образом, у нас есть что-то вроде:

public class BinaryTree {
    private int[] tree; // assuming each node holds an integer.
    private int nodeCount;

    public BinaryTree (int nodes) {
         tree = new int[nodes * 2];
         nodeCount = nodes;
    }

    public int getRoot() {
         return tree[0];
    }

    private int getPositionOfNode(int value) {
         for(int i = 0; i < nodeCount; i++) {
             if(tree[i] == value) {
                 return i;
             }
         }
         return -1;
    }

    public int getLeftChildOfNode(int node) {
         int pos = getPositionOfNode(node);
         if(pos != -1) {
              return tree[pos * 2];
         }
         return pos;
    }

    public int getRightChildOfNode(int node) {
         int pos = getPositionOfNode(node);
         if(pos != -1) {
              return tree[pos * 2 + 1];
         }
         return pos;
    }

    public int getParentOfNode(int node) {
         int pos = getPositionOfNode(node);
         if(pos != -1) {
              return tree[pos / 2];
         }
         return pos;
    }
}

В этой структуре, если узел находится в позиции i, его дочерние элементы будут в позициях 2 * i и 2 * i + 1.

Answer 4

со связанным списком.здесь код: http://www.roseindia.net/java/jdk6/LinkedListExample.shtml

Answer 5

Я начну с предположения, что вам запрещено использовать даже примитивные типы массивов Java. В этом случае вам придется вернуться к самым основам и начать управлять памятью самостоятельно. Вам нужно начать с выделения байтового массива или байтового буфера соответствующего размера. Затем доступ к этому блоку данных будет обрабатываться с использованием того, что в C было бы простым указателем математики.

Пример 1D массива 16 дюймов:

byte[] mem = new byte[16 * 4] ; // Ints are 4 bytes long

// Write a value to the 8th element of our "array"
index = 8 ;
int value = 31415926 ;
mem[4 * index + 0] = (byte)( value >> 24 ) ;
mem[4 * index + 1] = (byte)( ( value << 8 ) >> 24 ) ;
mem[4 * index + 2] = (byte)( ( value << 16 ) >> 24 ) ;
mem[4 * index + 3] = (byte)( ( value << 24 ) >> 24 ) ;

Чтение значения будет выполнено путем обращения процесса и вычисления сохраненного значения int.

Примечание. Процесс установки и извлечения значений проще с использованием ByteBuffer, поскольку он позволяет получать и помещать примитивные типы Java в байтовый массив.

Answer 6

public class TwoDArray {
   private Object[] values;
   public TwoDArray(int n, int m) {
       values = new Object[n * m];
   }
   public void set(int i, int j, Object x) { ... }
   public Object get(int i, int j) { ... }
}
public class BinTree {
   private BinTree left;
   private BinTree right;
   private Comparable value;
   public void insert(Comparable x) { ... }
}

Как то так?Не должно быть так сложно.