数据结构--数组（详细分析）

目录

🍉引言

🍉数组

🍈数组的特性

🍈数组的优缺点

🍍优点：

🍍缺点：

🍈数组的声明与初始化

🍈数组的常见操作

🍍 插入操作

🍍删除操作

🍍查找操作

🍅线性查找：

🍅二分查找：

🍈数组的常见问题实现

🍍反转数组

🍍数组中的最大和最小元素

🍈演示

🍍插入操作

🍍删除操作

🍍反转数组

🍉总结

🍉引言

  • 数据结构是计算机科学的基石，它们为数据的组织、管理和存储提供了不同的方法和策略。在众多数据结构中，数组和字符串是最基本且常用的两种。本教学文章将详细分析数组与字符串的特性，展示两者的示例操作与问题实现，并通过图示演示实现问题的过程。

🍉数组

🍈数组的特性

数组是一种线性数据结构，它使用连续的内存空间存储相同类型的元素。数组的主要特点如下：

  1. 固定大小：数组在声明时必须指定大小，并且在大多数编程语言中，数组的大小在其生命周期内不可改变。
  2. 随机访问：数组支持通过索引进行快速随机访问，这使得数组在查找操作中的效率很高。
  3. 相同数据类型：数组中所有元素必须是相同的数据类型，这保证了数组的内存布局的紧凑性和一致性。
  4. 低级别存储：由于数组使用连续的内存空间存储数据，它们在内存管理和访问速度方面具有优势。

🍈数组的分类

🍍基本定义

  • 数组的空间复杂度通常为 O(n)，其中 n 是数组的元素个数。具体来说，如果每个元素占用的空间是固定的（比如在C语言中的 int 类型占用4个字节），那么整个数组的空间复杂度就是元素个数乘以每个元素占用的空间。

🍍静态数组 vs 动态数组

🍅静态数组
  • 静态数组在编译时确定大小，一旦分配就不能改变大小。其空间复杂度为：O(n)其中 n 是数组的长度。
🍅动态数组
  • 动态数组（如C++中的 std::vector，Java中的 ArrayList）在运行时可以调整大小。当需要扩展时，通常会以一定比例（如2倍）增加大小。因此，动态数组的空间复杂度稍微复杂一些，考虑到了扩展时的额外开销。
  • 动态数组的平均空间复杂度仍然是 O(n)，但在最坏情况下，当数组需要扩展时，空间复杂度会瞬间增加到 O(2n)，即需要额外的空间来存储新的元素数组。

🍍内存分配的细节

🍅连续内存分配
  • 数组元素在内存中是连续存储的，这种方式的优点是访问速度快，但缺点是需要一次性分配大块连续的内存。在内存紧张或碎片化严重的情况下，可能会导致分配失败。
🍅空间浪费
  • 由于数组在创建时必须确定大小，如果预估不准确，可能会出现空间浪费或空间不足的情况。预分配过多会导致内存浪费，预分配过少则需要重新分配更大的数组，这样不仅增加了额外的内存开销，还可能影响性能。

🍍实际示例分析

假设我们有一个包含 1000 个整数的数组 int arr[1000];：

  • 每个整数占用 4 个字节。
  • 数组总共占用的空间为 1000×4=40001000×4=4000 字节，即 4 KB。

🍍 动态数组的扩展分析

假设一个动态数组在初始分配时大小为 4，存储了4个元素后需要扩展到 8：

  1. 初始状态：大小为 4，占用 4×4=164×4=16 字节。
  2. 扩展到 8：需要分配新的内存块，占用 8×4=328×4=32 字节。

在扩展过程中，原有的4个元素需要复制到新的内存块，导致在扩展的瞬间，数组占用的空间为 16+32=4816+32=48 字节。

🍍总结

  • 静态数组：空间复杂度为 O(n)，其中 n 是数组长度。
  • 动态数组：平均空间复杂度为 O(n)，但由于扩展过程可能导致瞬时空间复杂度达到 O(2n)。

🍈数组的优缺点

🍍优点：

  • 快速访问：

    • 数组提供了快速访问元素的能力。由于数组元素在内存中是连续存储的，可以通过索引直接访问任意元素，时间复杂度为 �(1)O(1)。

  • 易于遍历：

    • 数组的线性结构使得遍历非常方便，可以使用简单的循环结构（如for循环）访问所有元素。

  • 内存管理：

    • 数组在内存中是连续分配的，这可以提高缓存命中率，从而加快访问速度。

  • 简单性：

    • 数组的数据结构和操作（如插入、删除、访问）相对简单，容易理解和实现。

🍍缺点：

  • 固定大小：

    • 在大多数编程语言中，数组的大小在创建时必须确定，不能动态调整。如果预估不准确，要么浪费内存，要么导致空间不足。

  • 插入和删除效率低：

    • 由于数组的元素是连续存储的，在中间位置插入或删除元素需要移动大量元素，时间复杂度为 �(�)O(n)，这对性能有负面影响。

  • 内存浪费：

    • 如果数组大小预估过大，会浪费内存；如果预估过小，又可能导致数组溢出，需重新分配更大的数组，增加了复杂性和时间开销。

  • 类型限制：

    • 数组通常只能存储相同类型的数据，这限制了数组的灵活性。如果需要存储不同类型的数据，需要使用其他数据结构（如对象或元组）。

🍈数组的声明与初始化

在C语言中，可以通过以下方式声明和初始化数组：

#include <stdio.h>

int main() {
    // 声明一个大小为5的整数数组
    int arr[5];
    
    // 初始化数组
    int arr2[5] = {1, 2, 3, 4, 5};
    
    // 打印数组元素
    for(int i = 0; i < 5; i++) {
        printf("%d ", arr2[i]);
    }
    
    return 0;
}

🍈数组的常见操作

🍍 插入操作

在数组中插入元素需要将插入位置之后的所有元素向后移动一位，以腾出位置：

#include <stdio.h>

void insert(int arr[], int n, int pos, int value) {
    for(int i = n; i > pos; i--) {
        arr[i] = arr[i - 1];
    }
    arr[pos] = value;
}

int main() {
    int arr[6] = {1, 2, 3, 4, 5};
    int n = 5;  // 当前数组元素数量
    int pos = 2; // 插入位置
    int value = 99; // 插入值
    
    insert(arr, n, pos, value);
    
    for(int i = 0; i <= n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

🍍删除操作

删除数组中的元素需要将删除位置之后的所有元素向前移动一位：

#include <stdio.h>

void delete(int arr[], int n, int pos) {
    for(int i = pos; i < n - 1; i++) {
        arr[i] = arr[i + 1];
    }
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    int n = 5; // 当前数组元素数量
    int pos = 2; // 删除位置
    
    delete(arr, n, pos);
    
    for(int i = 0; i < n - 1; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

🍍查找操作

在数组中查找元素可以通过线性查找或二分查找（如果数组有序）来实现：

🍅线性查找：
#include <stdio.h>

int linearSearch(int arr[], int n, int value) {
    for(int i = 0; i < n; i++) {
        if(arr[i] == value) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    int value = 3; // 查找值
    
    int index = linearSearch(arr, 5, value);
    
    if(index != -1) {
        printf("Element found at index %d\n", index);
    } else {
        printf("Element not found\n");
    }
    
    return 0;
}
🍅二分查找：
#include <stdio.h>

int binarySearch(int arr[], int left, int right, int value) {
    while(left <= right) {
        int mid = left + (right - left) / 2;
        
        if(arr[mid] == value) {
            return mid;
        }
        if(arr[mid] < value) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    int value = 3; // 查找值
    
    int index = binarySearch(arr, 0, 4, value);
    
    if(index != -1) {
        printf("Element found at index %d\n", index);
    } else {
        printf("Element not found\n");
    }
    
    return 0;
}

🍈数组的常见问题实现

🍍反转数组

反转数组意味着将数组中的元素顺序颠倒：

#include <stdio.h>

void reverseArray(int arr[], int n) {
    int start = 0;
    int end = n - 1;
    while(start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    
    reverseArray(arr, 5);
    
    for(int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

运行结果：

🍍数组中的最大和最小元素

查找数组中的最大和最小元素：

#include <stdio.h>

void findMaxMin(int arr[], int n, int *max, int *min) {
    *max = arr[0];
    *min = arr[0];
    for(int i = 1; i < n; i++) {
        if(arr[i] > *max) {
            *max = arr[i];
        }
        if(arr[i] < *min) {
            *min = arr[i];
        }
    }
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    int max, min;
    
    findMaxMin(arr, 5, &max, &min);
    
    printf("Max: %d, Min: %d\n", max, min);
    
    return 0;
}

运行结果：

🍈演示

🍍插入操作

在数组 arr = [1, 2, 3, 4, 5] 中插入值 99 到位置 2：

初始数组: [1, 2, 3, 4, 5]
插入值99到位置2:
向后移动: [1, 2, 3, 3, 4, 5]
向后移动: [1, 2, 2, 3, 4, 5]
插入完成: [1, 99, 2, 3, 4, 5]

🍍删除操作

在数组 arr = [1, 2, 3, 4, 5] 中删除位置 2 的元素：

初始数组: [1, 2, 3, 4, 5]
删除位置2的元素:
向前移动: [1, 2, 4, 4, 5]
向前移动: [1, 2, 4, 5, 5]
删除完成: [1, 2, 4, 5]

🍍反转数组

将数组 arr = [1, 2, 3, 4, 5] 反转：

初始数组: [1, 2, 3, 4, 5]
反转过程:
交换位置0和4: [5, 2, 3, 4, 1]
交换位置1和3: [5, 4, 3, 2, 1]
反转完成: [5, 4, 3, 2, 1]

🍉总结

  • 数组作为一种固定大小且内存连续的线性数据结构，提供了高效的随机访问能力

 

希望这些能对刚学习算法的同学们提供些帮助哦！！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/673957.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

QTP——功能测试

QTP——功能测试

一、前言&#xff08;课设目的及内容&#xff09; QTP是quicktest Professional的简称&#xff0c;是一种自动测试工具。使用QTP的目的是想用它来执行重复的手动测试&#xff0c;主要是用于回归测试和测试同一软件的新版本。因此你在测试前要考虑好如何对应用程序进行测试&…
阅读更多...
46、Flink 的 异步 I/O 算子详解

46、Flink 的 异步 I/O 算子详解

异步 I/O 1.需求 在与外部系统交互&#xff08;用数据库中的数据扩充流数据&#xff09;时&#xff0c;需要考虑与外部系统的通信延迟对整个流处理应用的影响。 同步交互&#xff1a;使用 MapFunction访问外部数据库的数据&#xff0c; MapFunction 向数据库发送一个请求然后…
阅读更多...
企业软件产品和服务 之 设计保证安全 七项承诺

企业软件产品和服务 之 设计保证安全 七项承诺

1. 引言 公司如何保护自己免受数据泄露的影响&#xff1f;标准答案就是&#xff1a; “启用多因素身份验证”——MTA&#xff08;Enable multifactor authentication&#xff09;。 但是&#xff0c;目前很多公司仍然盲目地只使用密码作为唯一的身份来源。 网络安全的核心是…
阅读更多...
IPD推行成功的核心要素（九）需求管理助力产品从一次成功走向一直成功

IPD推行成功的核心要素（九）需求管理助力产品从一次成功走向一直成功

在当今竞争激烈的商业环境中&#xff0c;项目的成功与否往往取决于其能否满足用户和利益相关者的需求。然而&#xff0c;理解、捕捉和有效管理这些需求并非易事。因此&#xff0c;需求管理在项目管理中扮演着至关重要的角色。需求管理是一个系统性的过程&#xff0c;旨在确保项…
阅读更多...
直播分享|深入解析ts-morph：通过注释生成类型文档

直播分享|深入解析ts-morph：通过注释生成类型文档

♪ ♫ 你看小狗在叫 树叶会笑 风声在呢喃♫ ♪ 乘风追梦&#xff0c;童心未泯 OpenTiny 预祝所有大朋友、小朋友儿童节快乐~ 与此同时&#xff0c;OpenTiny 贡献者直播也即将开启啦~ 直播主题&#xff1a;【深入解析ts-morph&#xff1a;通过注释生成类型文档】 6月1日&am…
阅读更多...
前驱图，程序执行和进程状态

前驱图，程序执行和进程状态

目录 前驱图 程序的执行 顺序执行 并发执行 进程的定义 进程的状态 总结 前驱图 现在有两个任务分别为p1,p2; 只有执行了p1,才可以执行p2&#xff0c;此时可以称p1为p2的前驱。通过符号语言表示如下&#xff1a; p1->p2 程序的执行 下面引进一段代码来理解进程的概念…
阅读更多...
IDEA 学习之 疑难杂症系列

IDEA 学习之 疑难杂症系列

IDEA 学习之 疑难杂症系列 1. Mapstruct 编译空指针问题 1.1. 现象 NullPointerException at org.mapstruct.ap.internal.processor.DefaultVersionInformation.createManifest1.2. 原因 MapStruct 在 IDEA 2020.3 版本编译 NPE 问题 1.3. 解决办法 2. IDEA 学习之 编译内…
阅读更多...
什么牌子的开放式耳机质量好？2024超强实力派品牌推荐！

什么牌子的开放式耳机质量好？2024超强实力派品牌推荐！

耳机对于一个音乐人有重要这个不必多说&#xff0c;我朋友是个音乐编辑&#xff0c;他经常需要长时间佩戴耳机进行音频编辑和混音工作。在尝试过多款开放式耳机后&#xff0c;都没找到合适的。今天&#xff0c;我将从专业角度为大家带来几款热门开放式耳机的测评报告&#xff0…
阅读更多...
Python 高级数据类型

Python 高级数据类型

列表List 定义列表 可以将不同的基本数据类型或者列表装到一个列表里 my_list [1,2,3,4,5] print(my_list) # [1, 2, 3, 4, 5] 直接打印出列表的内容 print(type(my_list)) # <class list>my_list ["1","2","3","4","…
阅读更多...
MYSQL之安装

MYSQL之安装

一&#xff0c;下载仓库包 wget -i -c https://dev.mysql.com/get/mysql80-community-release-el7-3.noarch.rpm二&#xff0c;安装仓库 yum -y install mysql80-community-release-el7-3.noarch.rpmsed -i s/gpgcheck1/gpgcheck0/g mysql-community.repo三&#xff0c;安装MY…
阅读更多...
免费SSL证书的安全性与获取指南

免费SSL证书的安全性与获取指南

SSL证书是一种数字凭证&#xff0c;用于加密用户与网站之间的信息交换&#xff0c;以确保传输的数据不被第三方窃取。它像是一个数字版的密封印章&#xff0c;为数据的传输过程提供了一层保护膜。 免费的SSL证书通常由CA机构提供&#xff0c;它们同样可以提供基础数据的加密服…
阅读更多...
瑞吉外卖项目整体介绍

瑞吉外卖项目整体介绍

黑马程序员瑞吉外卖 文章目录 一、项目介绍二、产品原型展示三、技术选型四、功能架构五、角色 一、项目介绍 二、产品原型展示 产品原型&#xff0c;就是一款韩品成型之前的一个简单的框架&#xff0c;就是将页面的排版布局展现出来&#xff0c;使产品的初步构思有一个可视化…
阅读更多...
跟着大佬学RE（一）

跟着大佬学RE（一）

学了一个 map&#xff08;&#xff09;函数的使用 import base64rawData "e3nifIH9b_CndH" target list(map(ord, rawData)) # map 函数将 rawData 中的每个字符传递给 ord 函数。ord 函数返回给定字符的 Unicode 码点 print(target) # 打印 map 对象的内存地址&…
阅读更多...
Prism 入门02，区域介绍

Prism 入门02，区域介绍

一.区域概念和使用方式 什么是区域（Region）？区域，在Prism 框架中，区域是模块化的核心功能之一，其主要作用是降低应用程序和模块之间的耦合度 。使用方式：在应用程序的界面中，划分出某块区域，并为这个区域定义一个唯一的区域名称。那么通过这个区域名称，应用程序就可以…
阅读更多...
Android Display Graphics #1 整体框架介绍一

Android Display Graphics #1 整体框架介绍一

软件基础 Android的framework层提供了一系列的图像渲染API&#xff0c;可绘制2D和3D。简单理解就是上层开发APP的小伙伴提供了接口&#xff0c;开发者可以直接显示对应的自己内容。但如果掌握了Display底层逻辑再写上层app&#xff0c;会有掌控力&#xff0c;出问题可以根据lo…
阅读更多...
【Mybatis】源码分析-自定义框架

【Mybatis】源码分析-自定义框架

1、自定义持久层框架 1.1、分析JDBC操作问题 package blnp.net.cn.jvm.demos;import java.sql.*;/*** <p></p>** author lyb 2045165565qq.com* createDate 2024/5/24 14:24*/ public class JdbcTest {public static void main(String[] args) {Connection conne…
阅读更多...
大模型+RAG，全面介绍！

大模型+RAG，全面介绍！

1 介绍 大型语言模型&#xff08;LLMs&#xff09;在处理特定领域或高度专业化的查询时存在局限性**&#xff0c;如生成不正确信息或“幻觉”。**缓解这些限制的一种有前途的方法是检索增强生成&#xff08;RAG&#xff09;&#xff0c;RAG就像是一个外挂&#xff0c;将外部数…
阅读更多...
环路检测00

环路检测00

题目链接 环路检测 题目描述 注意点 返回环路的开头节点 解答思路 快慢指针确认链表中是否有环&#xff0c;如果无环则快指针最终会到达链表尾部&#xff0c;如果有环则快慢指针会相遇&#xff0c;当快慢指针相遇&#xff0c;此时新的节点node从head开始出发&#xff0c;与…
阅读更多...
探索数据结构：便捷的双向链表

探索数据结构：便捷的双向链表

&#x1f511;&#x1f511;博客主页&#xff1a;阿客不是客 &#x1f353;&#x1f353;系列专栏&#xff1a;渐入佳境之数据结构与算法 欢迎来到泊舟小课堂 &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 ​​ 前言 前面我们学习了单链表&#xff0c;它解…
阅读更多...
微服务中feign远程调用相关的各种超时问题

微服务中feign远程调用相关的各种超时问题

1. 引言 在spring cloud微服中&#xff0c;feign远程调用可能是大家每天都接触到东西&#xff0c;但很多同学却没咋搞清楚这里边的各种超时问题&#xff0c;生产环境可能会蹦出各种奇怪的问题。 首先说下结论&#xff1a; 1)只使用feign组件&#xff0c;不使用ribbion组件&…
阅读更多...
最新文章

Copyright @ 2022~2023