Java LL队列链表实现为每个LL节点复制队列
我试图用Java编写一个RadixSort的示例,虽然我理解了算法的工作原理,但在实现队列链表时遇到了一些问题
我相信我的问题是当我用一个新的队列作为它的值来更新第n个位置的链表时。我相信我对每个节点更新都使用相同的队列,这导致我在链表中为每个节点获得相同的值
所以当从int[] theArray = {4,3,5,9,7,2,4,1,6,5};
数组开始时
最后,我得到了一个由10个节点组成的链表,每个节点组成一个队列:{4,3,5,9,7,2,4,1,6,5}
我认为通过使用new
关键字可以创建一个新的实例,但它似乎在每次迭代中都会保留旧的值
有人能解释一下或者给我指出正确的方向来理解为什么会发生这种情况吗
编辑:(忘记附加代码)
package radixsort;
import java.util.*;
/**
* @author dlanz
*/
public class RadixSort {
public static void main(String[] args) {
int[] theArray = {4,3,5,9,7,2,4,1,6,5};
RadixSort theSort = new RadixSort();
System.out.println(Arrays.toString(theArray)); //Outputs the original array
theSort.sort(theArray);
System.out.println(Arrays.toString(theArray)); //Outputs the original array (no modifictions)
}
public void sort(int[] theArray) {
int significant;
int curVal;
int modulo = 10;
int ofInterest = 1;
LinkedList<Queue> lists = new LinkedList<>();
Queue<Integer> queue = new LinkedList<>();
int max = theArray[0];
for(int i = 0; i < theArray.length; i++) {
if ( theArray[i] > max) {
max = theArray[i];
}
}
significant = String.valueOf(max).length();
Queue<Integer> thisQueue;
for(int j = 1; j <= significant; j++){
lists.clear();
for(int i = 0; i < 10; i++){
lists.add(i, queue);
}
System.out.println(lists); //Outputs a list of 10 elements each with a value of null
for(int value : theArray){
curVal = value % modulo;
curVal = curVal / ofInterest;
System.out.println(curVal); //Correctly outputs the expected result
System.out.println(lists.get(curVal)); //With each iteration this outputs 10 elements each with a queue of all values.
thisQueue = new LinkedList<>();
thisQueue = lists.get(curVal);
thisQueue.add(value);
lists.set(curVal, thisQueue);// This seems to insert the generated queue into every linked lists node.
}
int k = 0;
for(int i = 0; i < 10; i++){
Queue<Integer> curQueue = lists.get(i);
if(!curQueue.isEmpty()){
theArray[k] = curQueue.remove();
k++;
}
}
ofInterest = ofInterest * 10;
modulo = modulo * 10;
}
}
}
编辑2:
我一直在玩弄它,似乎thisQueue
、lists
和queue
是共享的。当我在thisQueue
上执行某些操作时,例如thisQueue.add(1)
,会全面添加“1”的值。如果我对lists
和lists.add(1)
做同样的操作,lists
中的每个节点都填充了值1
我记得读过一些关于对象值通过引用传递的内容(虽然不是对象本身),这与我的经历有什么关系吗
编辑3:
我还注意到,如果我在.add()
行中使用文本而不是变量,比如
thisQueue.add(value);
这些值不重复,如编辑2中所述。我试图将变量转换为int
,尽管它们被声明为Int,但仍然得到了相同的结果
# 1 楼答案
奇怪的是,我很感激没有人回答这个问题。我在创建一组示例代码和制定一个不太具体的问题时自己解决了这个问题。但在很长一段时间内,我不会忘记这一点
发生的事情发生在代码中,我在链接列表中循环并创建节点0-9
我在添加对同一队列的引用。所以不管其他队列的使用情况如何。clear()我实际上是在这一行中提取对原始队列的引用
虽然我在这个过程中做了一些更改,但真正需要做的就是将循环更改为
改变
只是
我曾想过显式地创建10个单独的队列,然后在代码中使用一个开关来决定应该使用哪个队列。这似乎不是很灵活,而且会非常乏味。同时,我意识到为每次迭代创建一个新的队列是非常昂贵的。我将创建与数组中相同数量的对象,在本例中是10个,但可能是100、1000、1000000个。通过使用匿名对象(如果我错了,请纠正我),我只能创建所需数量的对象(链表中的每个元素对应一个)