数据结构之——数组
2024-02-04 23:37 由
abababiubiu 发表于
#其他
数组
数据结构的基本类型之一,它可以构成其他数据结构,如栈、队列、哈希表、树、图、堆、矩阵、张量。
数组在内存中的存储方式为一片连续的内存空间,其基本操作与其他数据结构一致,即所谓的增删改查。废话不多说,上代码加以理解。
Java类型实现
class array {
public static void main(String[] args) {
// 初始化数组
Scanner in = new Scanner(System.in);
int[] arr = new int [5];
int[] nums = {1,3,2,5,4};
System.out.println("访问的随机元素是:"+randomAccess(nums));
System.out.print("输入要插入的索引和元素:");
int index = in.nextInt();
int n = in.nextInt();
insert(nums,n,index);
System.out.println("现在的nums数组为:");
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]);
}
System.out.println();
System.out.print("输入要删除的索引和元素:");
index = in.nextInt();
n = in.nextInt();
delete(nums,n,index);
System.out.println("现在的nums数组为:");
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]);
}
// foreach遍历方式
// for (int num: nums) {
// System.out.println(num);
// }
System.out.println();
//查找元素
System.out.println("请输入要查找的元素:");
n = in.nextInt();
System.out.println("查找的元素的下标为:"+find(nums,n));
//扩展数组
System.out.println("请输入扩展的大小:");
n = in.nextInt();
int[] a = extend(nums,n);
System.out.println("新数组为:");
for (int b:a) {
System.out.print(b);
}
}
//访问元素,在数组中随机抽取一个数
public static int randomAccess(int[] nums){
int randomIndex = ThreadLocalRandom.current().nextInt(0, nums.length);
int randomNum = nums[randomIndex];
return randomNum;
}
//插入元素
public static void insert(int[] nums,int num,int index){
for (int i = nums.length-1; i > index ; i--) {
nums[i] = nums[i-1];
}
nums[index] = num;
}
//删除元素
public static void delete(int[] nums,int num,int index){
if (index == nums.length-1){
nums[index] = 0;
return ;
}
for (int i = index; i < nums.length - 1; i++) {
nums[i] = nums[i+1];
}
}
//查找元素,返回索引
public static int find(int[] nums,int num){
for (int i = 0 ; i < nums.length ; i++ ) {
if (nums[i] == num) {
return i;
}
}
return -1;
}
//扩展数组:思路——新建一个更大的数组,将原数组复制到新数组中
public static int[] extend(int[] nums,int enlarge){
int[] newArr = new int[nums.length+enlarge];
for (int i = 0; i < nums.length; i++) {
newArr[i] = nums[i];
}
return newArr;
}
}
数组的优点与局限性:
·空间效率高:数组为数据分配了连续的内存块,无需额外的结构开销
·支持随机访问:允许在O(1)时间内访问任何元素
·缓存局部性:当访问数组元素时,计算机不仅会加载它,还会缓存其周围的其他数据,从而借助高速缓存来提升后续操作的执行速度
连续空间存储的局限性:
·插入与删除效率低:但数据量大时,该操作会移动大量数据
·长度不可变:数组在初始化后长度就固定了,扩容数组需要将所有数据复制到新数组,开销很大
·空间浪费:如果数组分配的空间大小超过实际所需,那么多余的空间就被浪费了
数组典型应用:
·随机访问
·排序和搜索
·查找表
·机器学习
·数据结构实现
本篇内容参考自Github krahets的hello算法,将其内容进行归纳整理
热门相关:唐朝贵公子 黑暗血时代 抗战老兵之不死传奇 惊艳人生 万古第一帝