558-数据结构(数组)

亦凉 2022-09-11 09:20 74阅读 0赞

## 数据结构和算法介绍 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 线性表-数组理论讲解 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

int arr[10];//中括号里的一定要用常量或者常量表达式，写开辟数组的长度

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**长度是10个，下标是0-9**  
![在这里插入图片描述][edddd339adf44c748f42ff91f5554c16.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
现在，数组的0号位-6号位有放置元素，也就是说，数组的长度是10个，里面有效元素的个数是7个。  
**数组的特点是 内存是连续的。**

**数组的查找或者搜索：时间复杂度是O(n)**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]

**数组的下标访问（随机访问）：**  
![在这里插入图片描述][78b2d0d9b0aa473385242ef1e1ecfdd5.png]  
**因为数组的每个元素的内存是连续的，所以我们地址可以在内存连续的方向上进行偏移，所以可以支持下标访问，不管访问哪个下标，时间复杂度都是O(1)**  
![在这里插入图片描述][874ca93b79f7446ea83ab00c582a5332.png]  
**数组的末尾位置进行插入和删除花费的时间少（时间复杂度是O(1))，因为不涉及元素的移动**  
比如说有一个cur=7，记录数组中有效元素的个数，如果把它看作下标，刚好是数组末尾元素的后继位置的下标，我们要去删除一个末尾元素的话，把cur–一下，从7变成6就可以了，前面的元素也不用移动。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
**我们可以通过指针p的++访问当前元素的下一个元素，我们可以通过指针–访问当前元素的上一个元素，因为内存地址是连续的。**

**什么是线性表？**  
就是每一个元素都有一个前驱元素和一个后继元素  
数组就满足这样1个特征

**数组的优点：** 如果下标访问多，就使用数组。

**数组的缺点是：**  
![在这里插入图片描述][d76c2c657f4b4a248a89f7f509788277.png]  
![在这里插入图片描述][3135690563e54667b6b73a83af4f2ba1.png]  
比如说，我要在31元素这个位置插入元素80![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
31这个元素及它后面的所有元素都要依次向后挪动1个位置，才能把80插到31这个元素的位置。  
从后往前，依次向后挪动1个位置。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]

**在数组的非末尾位置插入1个元素，时间复杂度是O(n）**  
因为在非末尾位置插入元素，当前插入位置的元素的后边的元素越多，要进行数据移动所花费的时间就越多，就是线性时间，成正比。  
**在数组的非末尾位置删除元素，和上面同理。**  
比如说，现在要删除80这个元素，相当于要把80后面的所有元素依次前移1个位置。删除元素的位置的后面的元素的数据量越多，向前移动一个一个数据的总耗费时间就越多，和数据规模成正比的关系，**所以时间复杂度是O(n）**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]  
![在这里插入图片描述][a360d7a117d640389a47e21352b89cdf.png]  
**如果是在无序的数组中搜索，要找某一个元素，只能for循环从0号位置开始，一个一个比对下去，数据量越大，算法所耗费的时间就越多，时间复杂度是O(n）**  
**如果是在有序的数组（从小到大排序），要找某一个元素，我们就不用线性搜索，我们做二分搜索。时间复杂度是O(logn）**

**C++的vector容器底层的数据结构就是数组。**

**数组是可以扩容的。要使数组可以扩容，我们就得把数组定义在堆内存上。**  
![在这里插入图片描述][b3e9ab20bf4b4d72a7e2a7bb512b289a.png]

## 数组的代码实现 ##

**对于C/C++的程序，程序运行后叫进程，进程在内存上的布局：**  
可用内存主要分为3个部分：  
![在这里插入图片描述][c5d20711543449e8ad826d09a9de2e88.png]  
**.data数据段**存储的是全局变量的地方，是系统分配，系统释放的，其生命周期是整个程序的生命周期。  
**heap堆**上的内存是我们自己可用通过C的malloc，free或者C++的new和delete来去自己开辟，自己手动释放。  
**stack栈**上的内存，随着函数进来，分配内存，函数出右括号，释放内存，是系统来控制的。  
**所以，我们要想数组可以扩容，只能把数组定义在heap堆上了。**

**定义一个指针，指向堆上开辟的数组内存**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]  
**在析构的时候没有必要去判断指针是否为空，即使指针不为空，也有可能是野指针，delete有效指针，是我们开发者自己去保证的，delete或者free空指针是可以的，相当于是一个空操作而已，不做任何操作。**

**扩容是在原有的基础上再定义一个新的内存，新的内存大小是原来的2倍。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]  
1、开辟新的内存  
2、把原来的数组上的数据一个一个拷贝到新的内存数组上  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 14]  
3、把原来的堆内存释放掉  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 15]  
**vector在gcc下是2倍扩容，在VS2017以是1.5倍扩容**

#include <iostream>
    #include <stdlib.h>
    #include <time.h>
    #include <string.h>
    using namespace std;
    
    //数组实现
    class Array
    {
        
    public:
        Array(int size = 10) : mCur(0), mCap(size)//构造函数，用户没有传参数，就用初始化值10 
        {
        
            mpArr = new int[mCap]();//把每一个位置初始化为int的0值 
        }
        ~Array()//析构函数 
        {
        
            delete[]mpArr;
            mpArr = nullptr;//放在野指针的出现 
        }
    
    public:
        //末尾增加元素
        void push_back(int val)
        {
        
            if (mCur == mCap)//mcur指向最后一个有效元素的后继位置 
            {
        
                expand(2 * mCap);//O(n)
            }
            mpArr[mCur++] = val;//O(1) 
        }
        //末尾删除元素
        void pop_back()
        {
        
            if (mCur == 0)
            {
        
                return;
            }
            mCur--;//O(1)
        }
        //按位置增加元素
        void insert(int pos, int val)
        {
        
            if (pos < 0 || pos > mCur)
            {
        
                return;//throw "pos invalid!";
            }
    
            if (mCur == mCap)
            {
        
                expand(2 * mCap);
            }
    
            //移动元素  O(n)
            for (int i = mCur - 1; i >= pos; i--)//从后向前，进行依次向后移1个位置 
            {
        
                mpArr[i + 1] = mpArr[i];
            }
    
            mpArr[pos] = val;
            mCur++;
        }
        //按位置删除元素 
        void erase(int pos)
        {
        
            if (pos < 0 || pos >= mCur)
            {
        
                return;
            }
    
            //O(n)
            for (int i = pos + 1; i < mCur; i++)//从前向后，依次向前移动1个位置 
            {
        
                mpArr[i - 1] = mpArr[i];
            }
    
            mCur--;
        }
        //元素查询
        int find(int val)
        {
        
            for (int i = 0; i < mCur; i++)//O(n)
            {
        
                if (mpArr[i] == val)
                {
        
                    return i;
                }
            }
            return -1;
        }
        //打印数据
        void show()const
        {
        
            for (int i = 0; i < mCur; i++)
            {
        
                cout << mpArr[i] << " ";
            }
            cout << endl;
        }
    private:
        //内部数组扩容接口
        void expand(int size)
        {
        
            int* p = new int[size];
            memcpy(p, mpArr, sizeof(int) * mCap);//旧内存数据拷贝到新内存上 
            delete[]mpArr;
            mpArr = p;
            mCap = size;
        }
    private:
        int* mpArr;//指向可扩容的数组内存，指针指向堆上开辟的数组内存 
        int mCap;//数组的容量
        int mCur;//数组有效元素个数
    };
    
    int main()
    {
        
        Array arr;
    
        srand(time(0));//系统时间种一个随机数种子 
        for (int i = 0; i < 10; i++)
        {
        
            arr.push_back(rand() % 100);
        }
    
        arr.show();
        arr.pop_back();
        arr.show();
    
        arr.insert(0, 100);
        arr.show();
    
        arr.insert(10, 200);
        arr.show();
    
        int pos = arr.find(100);
        if (pos != -1)
        {
        
            arr.erase(pos);
            arr.show();
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/330090e244f84cb1bfe7769b41fdab1d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/08439749c5534fe18dad91851268e7af.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/756af02b8ba540f9b529907faa0981f2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/03d25577cefe41f586f38adb1c49a252.png
[edddd339adf44c748f42ff91f5554c16.png]: /images/20220828/1e3a0db99ce347988d9141c0f45fec6b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/06cdd60996014d06b787409a766ba205.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/b1a500e493a94659b3f52b0918a61e8e.png
[78b2d0d9b0aa473385242ef1e1ecfdd5.png]: /images/20220828/984238e115d247359f0694243974681a.png
[874ca93b79f7446ea83ab00c582a5332.png]: /images/20220828/338ccf991c154b978006175fca692667.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/fa4c9414c30b4bcaa8dba8e0e884a943.png
[d76c2c657f4b4a248a89f7f509788277.png]: /images/20220828/4ad822b7942b416da81016f4091e1ea9.png
[3135690563e54667b6b73a83af4f2ba1.png]: /images/20220828/71b87aafcdde4c12aff7dec09d2ab65c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/60183193c7284b87b286d156325ed395.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/1b1ac9dab6bb4afb80a388edcfa769de.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/4897bd75770342e382908b66c9156f2d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/f716580d42ec431b99176ec37d7f27c7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/4d6e4fe5b66243108aeff3366681f43c.png
[a360d7a117d640389a47e21352b89cdf.png]: /images/20220828/2cfdbf376e3342f5943bb4197cc38451.png
[b3e9ab20bf4b4d72a7e2a7bb512b289a.png]: /images/20220828/869d4b6d210842cf902aca3b3684aadf.png
[c5d20711543449e8ad826d09a9de2e88.png]: /images/20220828/3e5e728c3efe43488324328301a79cc3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/25ff1c9faf2c4614a29a7a60a3544a6c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/b5e510cc4912424f832d796e7602cd34.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 14]: /images/20220828/0016cf5ae7eb4acc94cde48ce745bf6b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 15]: /images/20220828/e88602f0889e45cb9be79ae2f2b39d78.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 16]: /images/20220828/ff917f4a496b4aebbeabeb8ea094c56d.png