Вставка строки в отсортированный массив

Question

У меня возникли проблемы с выяснением того, как заставить эту программу работать на Java. Я должен иметь класс словник:

public class WordList{ 
    private int size; //number of words in array 
    private String array1[]; //array of words 
    private int capacity; // how big the array is supposed to be 

И мы должны иметь два конструктора: Первый:

public WordList(int capacity){ 
    this.array1 = new String[capacity]; //makes a new array of specified capacity 
    this.capacity = capacity; //sets the capacity 
    this.size = 0; //sets the size of array (i.e. # of words) to 0 
} 

Вторая:

public WordList (String[] arrayOfWords){ 
    this.capacity = 2 * arrayOfWords.length; //makes the capacity of array twice the # of words in input array 
    this.array1 = new String[capacity]; //makes a new array 
    this.size = arrayOfWords.length; //sets the # of words in array 
    for (int i = 0; i < arrayOfWords.length; i++){ //loops through array 
     this.insert(arrayOfWords[i]); //inserts the words (sorted into our array) 
} 
} 

и, наконец, метод вставки. Я думаю, что главная проблема здесь. Я не знаю, если мои два конструктора правильно, но я 110% уверен, что что-то здесь не так:

public void insert(String newword){ 


    for (int i = 0; i < size; i++){ 
     int l = newword.compareTo(array1[i]); 
     if (l > 0) 
      continue; // means that the word we're inserting is after 
     if (l < 0){ 
      for (int j = size; j > i; j--){ 
       array1[j] = array1[j-1]; //shifts all array elements over by one - starting at end of array to avoid over writing anything 
      } 
      array1[i] = newword;//inserts the word 
     } 
     if (l == 0) 
      return;//doesn't do anything if word is already in list 
    } 
    } 

По существу он должен вставить слово при условии в уже отсортированный массив слов и сохранить список отсортирован. Программа просто падает. Любые идеи о том, что может быть неправильным?

Answer 1

Это домашнее задание? Я думаю, что это так, поэтому я просто даю несколько идей, а не полные ответы.

1. Поскольку массив отсортирован, вы можете использовать Arrays.binarySearch() найти свое место для insert()

2. Я знаю, что вы строите в каком-то дополнительном пространстве в конструкторе, но если вставить достаточное количество элементов, ваш массив будет нужно расти. Вставить нужно будет сравнить размер и емкость.

3. Подумайте о своем коде «shift all right». Запишите на бумаге (или используйте индексные карточки) примерный начальный массив, введите gedanken insert и пройдите через свой код один цикл за время обновления массива. Вероятно, у вас есть ошибка. Просто скажу ... :-)

4. Вы можете использовать System.arraycopy()? Если это так, используйте это при вставке или расширении массива.

Answer 2

В цикле for попробуйте инициализировать j до размера-1 вместо размера. Также обратите внимание, что пока программа будет работать, если вы не проверите емкость вставки, вы потеряете последний элемент при вставке в полный массив. Надеюсь это поможет.