主要问题出现在insertElement()方法,其中记录插入数据的midPos始终有问题。始终是会移动有问题。请帮忙看一下。
/**
* Description:
* <br>本程序主要实现一个包含有序数组类。
* <br>主要目的:将数组封装起来,然后,外界只能利用提供出去的接口方法,访问数组。
* <br>Program Name:OrderArray
* <br>Date:2015-09-20
* @author WayneZhao
* @version 1.0
*/
import java.util.Scanner;
class OrderArray
{
private int[] array;
private int nIndex;//数组元素的下标
/**
* 无参数构造器
*/
public OrderArray()
{
System.out.println("数组必须要有长度!");
}
/**
* 带一个int类型参数的构造器
* <br>用于告诉类,数组有多长
* @param maxSize 该参数用于指定数组的长度
*/
public OrderArray(int maxSize)
{
this.array = new int[maxSize];
this.nIndex = 0;
}
/**
* 展示数组中的每一个元素
*/
public void display()
{
for(int i = 0; i < nIndex;i++)
{
System.out.print("" + array[i] + '\t');
}
System.out.println("");
}
/**
* 在数组中寻找一个元素
* <br>此为二分法寻找数组中的元素
* @param value 该参数用于表示需要找寻值
* @return 返回数组的索引值
*/
public int findElementBinary(int value)
{
int headerPos = 0;
int railPos = nIndex-1;
while(headerPos < railPos)
{
int midPos = (headerPos + railPos)/2;
if(value == array[midPos])
return midPos;
else if(value < array[midPos])
railPos = midPos-1;
else
headerPos = midPos+1;
}
return -1;
}
/**
* 向数组中插入一个元素
* @param value 该参数用于向数组中插入一个元素
*/
public void insertElement(int value)
{
/*
int pos;//设置一个变量,记录插入的位置
//1st,遍历里数组,确定元素所需要插入的位置
for(pos = 0;pos<nIndex;pos++)
if(value<array[pos])
break;
*/
if(nIndex == 0)
{
System.out.println("[fillData]nIndex="+nIndex);
array[0] = value;
}
else if(nIndex == 1)
{
System.out.println("[fillData]nIndex="+nIndex);
if(value < array[0])
{
array[1]=array[0];
array[0]=value;
}
else
{
array[1]=value;
}
}
else
{
System.out.println("[fillData]nIndex="+nIndex);
if(value < array[0])
{
System.out.println("[fillData]"+value+"比"+array[0]+"小");
for(int j = nIndex;j>0;j--)
array[j] = array[j-1];
array[0] = value;
}
else if(value > array[nIndex-1])
{
System.out.println("[fillData]"+value+"比"+array[nIndex-1]+"大");
array[nIndex]=value;
}
else
{
int midPos = 0;//定义中间位置
int headPos = 0,tailPos = nIndex-1;//定义起始位置
System.out.println("[fillData]插入的元素为"+value);
System.out.println("[fillData]headPos初始"+headPos);
System.out.println("[fillData]tailPos初始"+tailPos);
System.out.println("[fillData]midPos初始"+midPos);
while(headPos<tailPos)
{
System.out.println("[fillData]现在开始进行二分法");
midPos = (headPos+tailPos)/2;
System.out.println("[fillData]结果如下:");
System.out.println("[fillData]二分中headPos="+headPos);
System.out.println("[fillData]二分中tailPos="+tailPos);
System.out.println("[fillData]二分中midPos="+midPos);
System.out.println("------------------------------");
if(value<array[midPos])
{
System.out.println("[fillData]二分中");
System.out.println("[fillData]"+value+"比"+array[midPos]+"小");
System.out.println("[fillData]移动tailPos");
System.out.println("[fillData]tailPos=midPos-1");
tailPos=midPos-1;
}
else
{
System.out.println("[fillData]二分中");
System.out.println("[fillData]"+value+"比"+array[midPos]+"大");
System.out.println("[fillData]移动headPos");
System.out.println("[fillData]headPos=midPos+1");
headPos=midPos+1;
}
System.out.println("[fillData]移动之后的结果:");
System.out.println("[fillData]二分中headPos="+headPos);
System.out.println("[fillData]二分中tailPos="+tailPos);
System.out.println("[fillData]二分中midPos="+midPos);
System.out.println("------------------------------");
}
//进行插入动作
for(int j = nIndex;j>midPos;j--)
array[j] = array[j-1];
array[midPos] = value;
}
}
nIndex++;
}
/**
* 在数组中删除一个元素
* @param value 该参数用于表示需要删除的元素
* @return 返回是否删除成功
*/
public boolean deleteElement(int value)
{
int indexTemp = findElementBinary(value);
if(indexTemp == -1)
return false;
else
{
for(int j = indexTemp;j<nIndex-1;j++)
{
array[j] = array[j+1];
}
nIndex--;
return true;
}
}
}
public class OrderArrayAdvance
{
public static void main(String[] args)
{
Scanner sc_maxSize = new Scanner(System.in);
System.out.println("你希望数组的长度有多长?");
int maxSize = sc_maxSize.nextInt();
OrderArray oaOne = new OrderArray(maxSize);
System.out.println("我们已经得到一个长度为"+maxSize+"的数组");
System.out.println("现在我们需要填充它。");
System.out.println("这里使用1到100的随机数来填充它");
for(int i = 0;i<maxSize;i++)
{
int tempInt = (int)(Math.random()*100+1);
oaOne.insertElement(tempInt);
System.out.println("[fillData]填充好的数组如下");
oaOne.display();
}
/*
oaOne.insertElement(1);
System.out.println("[fillData]填充好的数组如下");
oaOne.display();
oaOne.insertElement(3);
System.out.println("[fillData]填充好的数组如下");
oaOne.display();
oaOne.insertElement(7);
System.out.println("[fillData]填充好的数组如下");
oaOne.display();
oaOne.insertElement(9);
System.out.println("[fillData]填充好的数组如下");
oaOne.display();
oaOne.insertElement(5);
System.out.println("[fillData]填充好的数组如下");
oaOne.display();
*/
System.out.println("填充好的数组如下");
oaOne.display();
}
}