我在作业中遇到问题。 我对编码相当陌生,我很难弄清楚如何做到这一点。 我的教授提供了用于在数组中添加和删除项目的代码,但他希望我们添加一个方法,该方法会将项目添加到数组的正确位置。这是提供的代码:
import java.util.*;
public class MyArrayList {
private Object[]buffer;
private int currentSize;
public MyArrayList(){
final int INITIAL_SIZE=10;
buffer = new Object[INITIAL_SIZE];
currentSize=0;
}
public int size() {
return currentSize;
}
private void checkBounds(int n){
if (n<0||n>= currentSize){
throw new IndexOutOfBoundsException();
}
}
public Object get (int pos){
checkBounds(pos);
return buffer[pos];
}
public Object remove(int pos){
checkBounds(pos);
Object removed = buffer[pos];
for (int i = pos+1; i < currentSize; i++){
buffer[i-1] = buffer[i];
}
currentSize--;
return removed;
}
public boolean add(int pos, Object newElement){
growBufferIfNecessary();
currentSize++;
checkBounds(pos);
for(int i = currentSize - 1; i > pos; i--){
buffer[i] = buffer [i-1];
}
buffer[pos] = newElement;
return true;
}
public boolean addLast(Object newElement){
growBufferIfNecessary();
currentSize++;
buffer[currentSize -1] = newElement;
return true;
}
private void growBufferIfNecessary(){
if (currentSize==buffer.length){
Object[] newBuffer = new Object[2*buffer.length];
for(int i=0; i<buffer.length; i++){
newBuffer[i] = buffer[i];
}
buffer = newBuffer;
}
}
}
这是我们的任务:
添加一个名为"public void insert(int n("的方法,该方法将在正确的位置将n添加到MyArrayList对象中,保持排序顺序。使用现有的 MyArrayList 类并进行必要的修改。下面是一个测试用例:
MyArrayList list = new MyArrayLst((;
list.insert(5(; insert(10(; insert(8(; insert(20(; insert(6(;
如果现在打印列表,它应打印为:
5
6
8
10
20
所以这就是我到目前为止在我的主要方法中所拥有的:
import java.util.*;
public class ArrayListHomework {
public static void main (String[]args){
MyArrayList list = new MyArrayList();
list.insert(5);
list.insert(10);
list.insert(8);
list.insert(20);
list.insert(6);
for (int i=0; i<list.size(); i++){
System.out.println(list.get(i));
}
}
}
我对如何启动此插入方法感到非常迷茫。 任何帮助将不胜感激。 谢谢。
可悲的是,不可原谅的是,您的"教授"提供的代码在add()
方法中存在错误,如下所示:
public boolean add(int pos, Object newElement){
growBufferIfNecessary();
currentSize++;
checkBounds(pos);
// rest of method
由于不首先调用checkBounds()
,因此如果pos
超出界限,currentSize
将递增(并且缓冲区不必要地增长(,从而使实例处于不一致/错误状态。
编码101:首先,检查参数。
要修复:
public boolean add(int pos, Object newElement){
checkBounds(pos);
growBufferIfNecessary();
currentSize++;
// rest of method
要回答您的问题,您必须实现所谓的插入排序。简而言之,这意味着使用循环遍历所有元素,并在遇到较大元素或到达元素末尾时插入新元素。
请注意,如果数组元素尚未排序,则调用insert()
是没有意义的。要处理这种情况,您应该考虑在元素顺序不正常时抛出IllegalStateException
(您可以在迭代时检查前一个元素是否不大于当前元素(。
不完全像插入排序,因为存在具有空值的可用空格
public void insert( int n ) {
growBufferIfNecessary();
for( int i = 0; i < buffer.length; i++ ) {
if( buffer[i] == null ) {
buffer[i] = n; currentSize++;
break;
}
else if( buffer[i + 1] != null ) {
int n1 = ((Number)buffer[i]).intValue();
int n2 = ((Number)buffer[i + 1]).intValue();
if( n1 < n && n2 > n ) {
System.arraycopy( buffer, i + 1, buffer, i + 2, currentSize - i - 1 ); // line 1
buffer[i + 1] = n; currentSize++; // line 2
break;
}
}
}
}
add()
函数可以替换 第 1 行和第 2 行
谢谢大家的帮助和建议。 我通过使用 Marco13 建议的代码让它工作: https://codereview.stackexchange.com/questions/36221/binary-search-for-inserting-in-array#answer-36239 希望每个人都有美好的一天和快乐的编程。 -TJ