數據結構與算法——數組

DangoSky 發布于2019-08-16 15:45 / 3018人閱讀

摘要：概述數組是一種很基礎的數據結構，幾乎絕大多數編程語言都會支持數組這種數據結構。數組是一種線性結構，使用一組連續的內存空間，來存儲相同類型的數據。

1. 概述

數組（Array）是一種很基礎的數據結構，幾乎絕大多數編程語言都會支持數組這種數據結構。數組是一種線性結構，使用一組連續的內存空間，來存儲相同類型的數據。

所謂線性結構，就是指數據是前后排列的，只有前后兩個方向，除了數組，其他的比如鏈表、棧、隊列都是線性結構。

因為數組是使用連續的內存空間來存儲數據的，所以數組的最大的特點就是支持根據下標隨機訪問數據，這是數組最大的優勢。但是，有利就有弊，雖然數組高效的支持下標訪問，只不過在插入和刪除數據的時候就比較低效了，為了保證內存的連續性，必須要進行數據搬移。

2. 插入數據

先來看看插入操作，假如有一個數組 [3, 4, 6, 8, 7, 2, 5]，第一種情況是插入的元素位于數組的最后一個位置，那么不用進行數據搬移，時間復雜度為 O(1) ，如果插入的位置是第一個，那么必須移動整個數組，時間復雜度為 O(n) 。

這里有另外一個處理思路：如果數組中存儲的數據不在乎彼此順序的話，那么插入數據的時候，我們可以直接將插入位置的元素放到數組最后一位，騰出位置給新的元素。就像下圖這樣：

3. 刪除數據

再來看看刪除操作，還是上面的數組 [3, 4, 6, 8, 7, 2, 5]，如果刪除的是最后一個元素，那么不需要進行數據搬移，如果刪除的是第一個元素，那么數組每一個元素都會向前移動一位。

只不過，在某些場景下，如果不是特別追求數據的連續性，那么我們可以采用另一種思路來處理刪除操作。例如數組的大小為 10 ，現在存儲了 7 個元素，分別是 [3, 4, 6, 8, 7, 2, 5]，如果我們要刪除 3 4 6 這三個元素，我們先將其標記為刪除，等到數組空間不夠的時候，在集中性的進行數據搬移，這樣就大大減少了數據搬移的次數！

是不是非常高效呢？

4. Java 容器

在 Java 語言中，提供了一個可以支持動態擴容的數組容器：ArrayList，如果你熟悉 Java 語言的話，幾乎每天都會和這個容器打交道，它封裝了一些數組的操作，并且在數組空間不夠的時候，自動擴容為原來的 1.5 倍。

只不過，在使用 ArrayList 的時候，要是能夠指定大小，最好指定，這樣會減少申請內存空間和數據搬移的操作。

5. 代碼示例

下面是簡單的支持動態擴容的數組實現：

/*
 * 泛型動態數組
 */
public class GenericArray {

    private T[] data;
    private int count;//數組中存儲的個數
    
    public GenericArray(int capacity) {
        this.data = (T[]) new Object[capacity];
        this.count = 0;
    }

    public GenericArray() {
        this(16);
    }
    
    //返回數組中元素的個數
    public int getSize() {
        return this.count;
    }
    
    //返回數組容量
    public int getCapacity() {
        return this.data.length;
    }

    //設置某個位置的數據
    public void set(int index, T value) {
        if (count == data.length) {
            //擴容
            resize(data.length * 2);
        }
        checkIndex(index);
        
        if (index == count) {
            data[count ++] = value;
            return;
        }
        //常規刪除
        for (int i = count; i < index; i --) 
            data[i] = data[i - 1];
        data[index] = value;
        count ++;
    }
    
    //在數組末尾插入數據
    public void insert(T value) {
        set(count, value);
    }
    
    //刪除數據 
    public T remove(int index) {
        if(index == count) throw new IllegalArgumentException("Index Illegal!");
        checkIndex(index);
        
        T result = data[index];
        
        for (int i = index; i < count - 1; i ++) 
            data[i] = data[i + 1];
        count --;
        
        //縮容
        if (count == data.length / 2) {
            resize(data.length / 2);
        }
        return result;
    }
    
    //檢查下標的方法
    public void checkIndex(int index) {
        if(index < 0 || index > count) throw new IllegalArgumentException("Index Illegal!");
    }
    
    //重新設置數組的容量, 對應的操作是擴容和縮容
    private void resize(int capacity) {
        T[] temp = (T[]) new Object[capacity];
        for (int i = 0; i < count; i++) {
            temp[i] = data[i];
        }
        data = temp;
    }
}

是不是很簡單呢？后面接著講數據結構與算法的知識！

GPU云服務器云服務器算法與數據結構數據結構與算法數據結構與算法教程數據結構與算法答案

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/73676.html

數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

zsirfs 2019-08-23 15:33 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

you_De 2019-08-16 15:26 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

gotham 2019-07-31 10:07 評論0 收藏0
你知道和你不知道的冒泡排序

摘要：用來標示該輪冒泡排序中，數組是否是有序的。適用情況當冒泡算法運行到后半段的時候，如果此時數組已經有序了，需要提前結束冒泡排序。當第一輪冒泡排序結束后，元素會被移動到下標的位置。這篇文章包含了你一定知道的，和你不一定知道的冒泡排序。 gif看不了可以點擊【原文】查看gif。源碼: 【地址】 1. 什么是冒泡排序可能對于大多數的人來說比如我，接觸的第一個算法就是冒泡排序。我看過的很...

Worktile 2019-08-16 18:23 評論0 收藏0
JS數據結構與算法_排序和搜索算法

摘要：上一篇數據結構與算法樹寫在前面這是學習數據結構與算法的最后一篇博客，也是在面試中常常會被問到的一部分內容排序和搜索。上一篇：JS數據結構與算法_樹寫在前面這是《學習JavaScript數據結構與算法》的最后一篇博客，也是在面試中常常會被問到的一部分內容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無心去深入研究排序相...

姘擱『 2019-08-23 16:26 評論0 收藏0
數據結構與算法:常見排序算法

摘要：這是一個簡單的遞歸函數，你可以使用它來生成數列中指定序號的數值這個函數的問題在于它的執行效率非常低有太多值在遞歸調用中被重新計算。本章內容銜接上一章　數據結構與算法：二分查找內容提要兩種基本數據結構：數組常見操作: 數組降維、數組去重鏈表遞歸：遞歸是很多算法都使用的一種編程方法　　- 如何將問題分成基線條件和遞歸條件　　- 分而治之策略解決棘手問題 ...

wuyumin 2019-07-30 15:33 評論0 收藏0