數據結構--數組（詳細分析）

目錄

🍉引言

🍉數組

🍈數組的特性

🍈數組的優缺點

🍍優點：

🍍缺點：

🍈數組的聲明與初始化

🍈數組的常見操作

🍍?插入操作

🍍刪除操作

🍍查找操作

🍅線性查找：

🍅二分查找：

🍈數組的常見問題實現

🍍反轉數組

🍍數組中的最大和最小元素

🍈演示

🍍插入操作

🍍刪除操作

🍍反轉數組

🍉總結

🍉引言

  • 數據結構是計算機科學的基石，它們為數據的組織、管理和存儲提供了不同的方法和策略。在眾多數據結構中，數組和字符串是最基本且常用的兩種。本教學文章將詳細分析數組與字符串的特性，展示兩者的示例操作與問題實現，并通過圖示演示實現問題的過程。

🍉數組

🍈數組的特性

數組是一種線性數據結構，它使用連續的內存空間存儲相同類型的元素。數組的主要特點如下：

  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.pswp.cn/bicheng/21346.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/21346.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/21346.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Touch Camera PRO 2024 Easy Mobile Desktop Camera Controller（觸控相機專業版）

Touch Camera PRO 2024 Easy Mobile Desktop Camera Controller（觸控相機專業版）

一個真正易于使用的移動+臺式攝像機控制器，具有視角切換功能！ Touch Camera PRO 是一款非常易于使用的移動+桌面相機控制器，具有透視切換功能！它在 Home Designer、Runtime Level Editor 和 Floor Map Designer 等其他插件中使用！ 在桌面和移動設備上工作！ 一個干…
閱讀更多...
WIireShark使用教程

WIireShark使用教程

文章目錄 目錄 文章目錄 一.入門抓包示例 一.入門抓包示例 先介紹一下如何使用wireshark抓取相應網卡的流量&#xff0c;讓讀者可以先上手操作感受一下抓包的具體過程。 1.打開wireshark的主界面如下 2.選擇需要抓包的網卡&#xff0c;鼠標左鍵雙擊&#xff0c;即可抓取該網…
閱讀更多...
Mysql常見問題總結

Mysql常見問題總結

1、MySQL初始化報錯 mysqld --initialize --usermysql --console 2024-06-02T15:52:22.645557Z 0 [System] [MY-013169] [Server] D:\installSoft\mysql-8.0.21-winx64\bin\mysqld.exe (mysqld 8.0.21) initializing of server in progress as process 8980 2024-06-02T15:52:2…
閱讀更多...
02-2.3.2_1 單鏈表的插入和刪除

02-2.3.2_1 單鏈表的插入和刪除

喜歡《數據結構》部分筆記的小伙伴可以訂閱專欄&#xff0c;今后還會不斷更新。 此外&#xff0c;《程序員必備技能》專欄和《程序員必備工具》專欄&#xff08;該專欄暫未開設&#xff09;日后會逐步更新&#xff0c; 插入 按位序插入 &#xff08;1&#xff09;帶頭結點 L…
閱讀更多...
量子加速超級計算簡介

量子加速超級計算簡介

本文轉載自&#xff1a;量子加速超級計算簡介(2024年 3月 13日) By Mark Wolf https://developer.nvidia.cn/zh-cn/blog/an-introduction-to-quantum-accelerated-supercomputing/ 文章目錄 一、概述二、量子計算機的構建塊&#xff1a;QPU 和量子位三、量子計算硬件和算法四、…
閱讀更多...
代碼隨想錄算法訓練營第三十七 | ● 738.單調遞增的數字 ● 968.監控二叉樹

代碼隨想錄算法訓練營第三十七 | ● 738.單調遞增的數字 ● 968.監控二叉樹

738.單調遞增的數字 講解鏈接&#xff1a;https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html class Solution { public:int monotoneIncreasingDigits(int n) {//整數轉字符串&#xff0c;變為字符串訪問比諸位取出數字要…
閱讀更多...
項目集成過程中的makefile記錄

項目集成過程中的makefile記錄

項目集成過程中的makefile記錄 文章目錄 項目集成過程中的makefile記錄1.基礎概念注釋打印賦值方式常用變量$ 偽目標函數wildcard 多目錄、文件操作 2.思路梳理**需求分析**目錄結構 3.可行示例 持續更新中1.基礎概念 注釋 # 示例&#xff1a; # 項目名稱打印 echo "H…
閱讀更多...
控制臺相關

控制臺相關

輸入輸出 輸出 Console.WriteLine("123123");//光標空行 Console.Write("123123123123");//不空行輸入 string str Console.ReadLine(); //如果在ReadKey(true)不會把輸入的內容顯示在控制臺上 char c Console.ReadKey(true).KeyChar; Console.WriteL…
閱讀更多...
ACM實訓第25天

ACM實訓第25天

第四套 第一道&#xff08;修改&#xff09; #include<stdio.h> #include<string.h> int cnt[10]; void count_digits(int n,int* cnt){for(int i1;i<n;i){int numi;while(num){cnt[num%10];num/10;}} } int main(){int t;scanf("%d\n",&t);whi…
閱讀更多...
力扣刷題--2553. 分割數組中數字的數位【簡單】

力扣刷題--2553. 分割數組中數字的數位【簡單】

題目描述 給你一個正整數數組 nums &#xff0c;請你返回一個數組 answer &#xff0c;你需要將 nums 中每個整數進行數位分割后&#xff0c;按照 nums 中出現的 相同順序 放入答案數組中。 對一個整數進行數位分割&#xff0c;指的是將整數各個數位按原本出現的順序排列成數…
閱讀更多...
名為投資實為借貸，如何處理

名為投資實為借貸，如何處理

投資近百萬參與號稱“高回報、零風險”的內部商鋪投資項目&#xff0c;與公司簽訂商鋪投資合同及租賃合同。本想投資商鋪收取租金&#xff0c;沒想到不僅租金沒拿到手&#xff0c;連本金都要不回來。 2019年底&#xff0c;原告何某&#xff08;乙方&#xff09;與被告祁東縣某…
閱讀更多...
QSettings注冊表 json雙模式配置文件

QSettings注冊表 json雙模式配置文件

qt　QSettings　類可用來保存軟件設置&#xff0c;json文件也是保存軟件設置的很好的方式&#xff0e; 這里結合json文件和QSettings注冊表來保存軟件設置&#xff0e;區別在于json文件在軟件目錄&#xff0c;每次更新時會被覆蓋&#xff0c;注冊表中設置持久有效&#xff0c;…
閱讀更多...
14.FreeRTOS 消息緩存 Message Buffer

14.FreeRTOS 消息緩存 Message Buffer

FreeRTOS 消息緩存&#xff08;Message Buffer&#xff09;的使用 介紹 在實時操作系統&#xff08;RTOS&#xff09;中&#xff0c;任務之間的通信是一個非常重要的方面。FreeRTOS 提供了多種機制來實現任務間通信&#xff0c;其中之一就是消息緩存&#xff08;Message Buffe…
閱讀更多...
【IC驗證】一文速通多通道數據整型器(MCDF)

【IC驗證】一文速通多通道數據整型器(MCDF)

目錄 01 README 02 MCDF設計結構 2.1 功能描述 2.2 設計結構 2.3 接口與時序 2.3.1 系統信號接口 2.3.2 通道從端接口 2.3.3 整形器接口 2.3.4 控制寄存器接口 2.3.4.1 接口時序圖 2.3.4.2 各數據位信息 03 驗證框圖 3.1 reg_pkg 3.1.1 reg_trans 3.1.2 reg_driv…
閱讀更多...
【一刷《劍指Offer》】面試題 27：二叉搜索樹與雙向鏈表

【一刷《劍指Offer》】面試題 27：二叉搜索樹與雙向鏈表

牛客對應題目鏈接&#xff1a;二叉搜索樹與雙向鏈表_牛客題霸_牛客網 (nowcoder.com) 力扣對應題目鏈接&#xff1a;LCR 155. 將二叉搜索樹轉化為排序的雙向鏈表 - 力扣&#xff08;LeetCode&#xff09; 一、《劍指 Offer》對應內容 二、分析題目 上面力扣上的這道題目和牛客…
閱讀更多...
AGM DAP-LINK 離線燒錄報錯信息分析

AGM DAP-LINK 離線燒錄報錯信息分析

DAP-LINK 支持離線燒錄。 即&#xff1a;先把要燒錄的bin 燒錄到DAP-LINK 中&#xff1b;然后DAP-LINK 可以脫離PC&#xff0c;上電后通過按鍵對目標板進行燒錄。 CMSIS-DAP模式 跳線JGND斷開&#xff0c;狀態LED D4快閃&#xff0c;D3常亮&#xff08;串口狀態&#xff09;。…
閱讀更多...
deepin開發web前端：探索、挑戰與無限可能

deepin開發web前端：探索、挑戰與無限可能

deepin開發web前端&#xff1a;探索、挑戰與無限可能 在數字化浪潮洶涌的時代&#xff0c;Web前端作為連接用戶與數字世界的橋梁&#xff0c;其重要性日益凸顯。而deepin作為一款優秀的開源操作系統&#xff0c;為Web前端開發者提供了廣闊的舞臺。本文將圍繞deepin開發Web前端…
閱讀更多...
接口設計的最佳實踐-下篇

接口設計的最佳實踐-下篇

大多數程序員&#xff0c;做得最多的事&#xff0c;也不過是寫接口這件事而已。 今天繼續總結下接口設計需要注意的點。盡量每種都給出具體的場景、案例等&#xff0c;希望大家能有所收獲。 1、接口冪等 冪等性&#xff1a;是指一個操作或者一個服務&#xff0c;無論執行多少…
閱讀更多...
小程序怎樣進行本地存儲的讀、寫、刪、清？

小程序怎樣進行本地存儲的讀、寫、刪、清？

小程序進行本地存儲的讀、寫、刪、清操作&#xff0c;可以通過微信小程序提供的API來實現。這些API分為同步和異步兩種類型&#xff0c;以滿足不同的使用場景和需求。 同步操作 同步操作會阻塞后續的代碼執行&#xff0c;直到操作完成。 寫入本地緩存&#xff08;寫&#xf…
閱讀更多...
Vue3 - Mac系統用文本編輯寫html不顯示效果的坑

Vue3 - Mac系統用文本編輯寫html不顯示效果的坑

平時在win系統下&#xff0c;可以直接對文本進行編輯&#xff0c;非常的舒服。 在mac系統中&#xff0c;也有類似的功能&#xff0c;就是文本編輯&#xff0c;沒想到居然還有坑。 這是我mac系統中創建的html文件&#xff0c;想著沒有幾行代碼&#xff0c;就沒有開編輯器了&am…
閱讀更多...
最新文章

Copyright @ 2022~2023