Java: как выполнить итерацию по массиву типов связанных списков и добавить их в массив

Question

Для домашней работы в классе алгоритмов нам пришлось написать программу, которая реализовала алгоритм сортировки Radix. Я закончил тем, что реализовал его в раунде, и он функционирует правильно. Однако есть часть моего кода, который является ужасным, если else блокируется в цикле for. Я должен получить элементы из массива связанных списков в правильном порядке и добавить элементы обратно в массив Integer. Один из моих одноклассников, и я потратил немало времени, пытаясь понять, как включить этот блок в циклы, но просто не мог придумать это. Итак, это мои вопросы, как бы поместить объекты связанных списков в массив в другой массив. Код, который я придумал для метода сортировки ниже:

private static Integer[] sort(Integer[] input, int place){ 
    //create an array of linked lists 
    LinkedList<Integer>[] bucketsOut = new LinkedList[10]; 

    //initialize the linked lists 
    for(int i=0; i < 10; i++){ 
     bucketsOut[i] = new LinkedList<Integer>(); 
    } 

    int bucketPlacement = 0; 
    //place every input into the correct bucket 
    for(int i = 0; i < input.length; i++){ 
     bucketPlacement = getDigit(input[i].intValue(), place); 
     bucketsOut[bucketPlacement].add(input[i]); 
    } 

    //Place the elements out of the linked lists into the correct place in input[] 
    for(int i = 0; i < input.length; i++){ //for each input number 
     if(bucketsOut[0].peekFirst() != null){ 
      input[i] = bucketsOut[0].pollFirst().intValue(); 
     }else if(bucketsOut[1].peekFirst() != null){  
      input[i] = bucketsOut[1].pollFirst().intValue(); 
     }else if(bucketsOut[2].peekFirst() != null){  
      input[i] = bucketsOut[2].pollFirst().intValue(); 
     }else if(bucketsOut[3].peekFirst() != null){  
      input[i] = bucketsOut[3].pollFirst().intValue(); 
     }else if(bucketsOut[4].peekFirst() != null){  
      input[i] = bucketsOut[4].pollFirst().intValue(); 
     }else if(bucketsOut[5].peekFirst() != null){  
      input[i] = bucketsOut[5].pollFirst().intValue(); 
     }else if(bucketsOut[6].peekFirst() != null){  
      input[i] = bucketsOut[6].pollFirst().intValue(); 
     }else if(bucketsOut[7].peekFirst() != null){  
      input[i] = bucketsOut[7].pollFirst().intValue(); 
     }else if(bucketsOut[8].peekFirst() != null){  
      input[i] = bucketsOut[8].pollFirst().intValue(); 
     }else if(bucketsOut[9].peekFirst() != null){  
      input[i] = bucketsOut[9].pollFirst().intValue(); 
     } 
    } 
    //return sorted list for digit 
    return input; 
} 

Answer 1

Благодаря greybeard за указание, что else s выше фактически заставляет первое ведро полностью опорожняться.

Учитывая это, его не слишком сложно превратить в цикл. Помните, что основная идея состоит в том, что вы сначала хотите скопировать все элементы в первом ковше. Это легко сделать с помощью петли while.

 while(bucketsOut[bucketIndex].peekFirst() != null && 
      inputIndex < input.length) 
    { 
     input[inputIndex++] = bucketsOut[bucketIndex].pollFirst(); 
    } 

Так вот, для каждого сегмента, мы копируем, пока значение peek не равно нуль. Обратите внимание: я использую post-increment внутри индекса массива. Это действительно распространено, когда вам нужно скопировать некоторое количество элементов в массив. Это позволяет мне копировать увеличивающиеся элементы, не имея необходимости заранее фиксировать точное число с помощью цикла for.

При этом остальное довольно легко. Я просто добавил цикл for вокруг цикла while, чтобы увеличить его до следующего ведра. Цикл while проверяет inputIndex, поэтому мы не случайно пытаемся скопировать за пределы input.

for(int inputIndex = 0, bucketIndex = 0; bucketIndex < bucketsOut.length; 
      bucketIndex++) 
    { 
    while(bucketsOut[bucketIndex].peekFirst() != null && 
      inputIndex < input.length) 
    { 
     input[inputIndex++] = bucketsOut[bucketIndex].pollFirst(); 
    } 
    } 

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

 if(inputIndex >= input.length) break; 

Answer 2

Если у вас есть ряд операций, которые точно так же для изменения индекса, за исключением, это означает, что вы можете сделать это в for цикле :

Первая попытка

for (int j = 0; j < bucketsOut.length; j++) { 
    // The part that is repeated again and again 
    if (bucketsOut[j].peekFirst() != null) { 
     input[i] = bucketsOut[j].pollFirst().intValue(); 
    } 
} 

Но подождите! Это будет продолжаться через все ведра. Ваша оригинальная структура if фактически означала, что как только вы нажмете направо if, вы не будете смотреть ни на один из других else.

Это может быть сделано путем вспыхивают петли когда условие становится истинным:

Улучшенная версия

for (int j = 0; j < bucketsOut.length; j++) { 
    if (bucketsOut[j].peekFirst() != null) { 
     input[i] = bucketsOut[j].pollFirst().intValue(); 
     break; // Now the j loop will stop when we hit the first non-null. 
    } 
} 

Или вы могли бы использовать расширения для - логика та же:

for (LinkedList<Integer> bucket : bucketsOut) { 
    if (bucket.peekFirst() != null) { 
     input[i] = bucket.pollFirst().intValue(); 
     break; 
    } 
}