文章目录
无序数组和有序数组比较无序数组特点
有序数组特点
代码实现自己的数组无序数组有序数组
无序数组和有序数组比较
无序数组
增：在数组最后插入 删：找到元素；改为null；后面的元素逐一前移 查：从第一项元素开始遍历，直至找到该元素或者遍历结束
特点
效率：插入数据快，查找数据慢，删除数据慢 扩展性差：一旦创建后，大小就固定了，不能动态扩展数组元素的个数，有可能造成空间浪费或者空间不足。
有序数组
插入：找到插入元素应该插入的位置（根据元素值的大小）；将该位置以及以后的全部数据项向后移动一位；在该位置插入元素 删除：找到要删除的元素；后面的所有元素向前移位 查找：遍历查找or二分查找
特点
效率：插入数据慢，查找数据快（二分查找），删除数据慢。 扩展性差：一旦创建后，大小就固定了，不能动态扩展数组元素的个数，有可能造成空间浪费或者空间不足。
代码实现自己的数组
无序数组
package demo;
public class unorderedArray {
//程序的执行入口
public static void main(String[] args){
ArrayClass arrayClass = new ArrayClass(100);
//新增元素
arrayClass.insert(11);
arrayClass.insert(23);
arrayClass.insert(45);
arrayClass.insert(21);
arrayClass.insert(66);
arrayClass.insert(77);
arrayClass.insert(66);
//显示新增的数据
arrayClass.display();
//删除数据77
arrayClass.delete(23);
//显示新增的数据
arrayClass.display();
//查找
System.out.println(arrayClass.find(11));
System.out.println(arrayClass.find(1));
//修改
arrayClass.modifyFirst(66,77);
//显示新增的数据
arrayClass.display();
//修改
arrayClass.modifyAll(77,100);
//显示新增的数据
arrayClass.display();
}
}
/**
* 创建一个封装数组的类
*/
class ArrayClass{
private long[] arr; //被封装的数组
private int nElems; //数组中存在的元素的个数，当前的数组长度
//通过类的构造方法初始化
public ArrayClass(int maxSize){ //数组的最大长度
arr = new long[maxSize]; //初始化被封装的数组
nElems = 0;
}
//新增数据项，数组元素
public void insert(long data){
arr[nElems] = data;
nElems ++;
}
//查找某一特定的数据项
//找到返回true，否则返回false
public boolean find(long searchData){
int i;
for (i=0;i if(searchData == arr[i]){ break;//找到了就直接终止循环，此时i不再++，就等于对应元素的索引值 } } if(i == nElems){ return false; } else{ return true; } } //删除指定的数据项 public void delete(long targetDate){ //首先找到要删除的数据 int i; for (i=0;i if(targetDate == arr[i]){ break;//找到了就直接终止循环，此时i不再++，就等于对应元素的索引值 } } if(i == nElems){ System.out.println("没有找到要删除的数据"); } else{ for(int j =i;j arr[j] = arr[j+1]; //删除数组中要删除的元素 } nElems --; //数组长度-1 } } //遍历数据结构中的各个数据项 public void display(){ for(int i=0;i System.out.print(arr[i] + " "); } System.out.println();//加一个换行符 } /** * 以下内容是自己加的 */ //修改数组内容(全部相同内容都改) public void modifyAll(long originalData, long targetData){ for(int i=0;i if(arr[i]==originalData){ arr[i] = targetData; } } } //修改数组内容(全部相同内容都改) public void modifyFirst(long originalData, long targetData){ for(int i=0;i if(arr[i]==originalData){ arr[i] = targetData; break; } } } } 有序数组 package demo; public class OrderedArray { //程序的执行入口 public static void main(String[] args){ OrderArray orderArray = new OrderArray(100); orderArray.insert(15); orderArray.insert(44); orderArray.insert(55); orderArray.insert(22); orderArray.insert(1); orderArray.insert(99); orderArray.display(); System.out.println(orderArray.find(55)); orderArray.delete(22); orderArray.display(); } } /** *封装有序数组 */ class OrderArray{ private long[] arr; private int nElems; //构造方法 public OrderArray(int maxSize){ arr = new long[maxSize]; nElems =0; } //插入新的数据项 public void insert(long data){ //找到插入数据的位置 int i; for(i=0;i if(arr[i]> data){ break; } } //判断找没找到 if(i for(int j=nElems;j>i;j--){ if(j arr[j]=arr[j-1]; } } arr[i] = data; nElems ++; } else{//没找到,，要插入的元素比数组中其他元素都大 if(nElems arr[nElems] = data; nElems ++; } } } //遍历数组 public void display(){ for(int i=0;i System.out.print(arr[i]+" "); } System.out.println(); } //查找（二分查找） //找到了就返回数组在数组中的索引值，没找到就返回数组的当前长度 public int find(long searchData){ int lowerBound = 0; int upperBound = nElems-1; int curint; // 对数组进行二分的时候，中间元素对应的索引值 while(true){ curint = (lowerBound + upperBound) / 2; //自动取整 if(arr[curint] == searchData){ return curint; //return不仅会结束while循环，还会结束find方法 }else if(lowerBound>upperBound) { //数组中没有要查找的元素 return nElems; }else{ if(arr[curint] > searchData){ upperBound = curint-1; }else{ lowerBound = curint+1; } } } } //删除指定元素 public void delete(long data){ int i = find(data); if(i for(int j = i;j arr[j] = arr[j+1]; } nElems --; } } }