Java数据结构与算法笔记

2024-06-19 18:12| 来源: 网络整理| 查看: 265

文章目录无序数组和有序数组比较无序数组特点有序数组特点代码实现自己的数组无序数组有序数组

无序数组和有序数组比较无序数组

增：在数组最后插入删：找到元素；改为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 break;//找到了就直接终止循环，此时i不再++，就等于对应元素的索引值 } } if(i == nElems){ return false; } else{ return true; } } //删除指定的数据项 public void delete(long targetDate){ //首先找到要删除的数据 int i; for (i=0;i break;//找到了就直接终止循环，此时i不再++，就等于对应元素的索引值 } } if(i == nElems){ System.out.println("没有找到要删除的数据"); } else{ for(int j =i;j for(int i=0;i for(int i=0;i arr[i] = targetData; } } } //修改数组内容(全部相同内容都改) public void modifyFirst(long originalData, long targetData){ for(int i=0;i 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 break; } } //判断找没找到 if(i if(j//没找到,，要插入的元素比数组中其他元素都大 if(nElems for(int i=0;i 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 arr[j] = arr[j+1]; } nElems --; } } }

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章