数组的重要性不言而喻，数组连同链表构成其它数据结构的基础。

数组集中存储数据，元素通过索引来访问。链表可以分散存储数据节点，通过指针来建立节点之间的联系。

数组根据其长度，类型是否可变，以及数据存储的内存空间的不同，有静态数组、动态数组、变长数组、柔性数组、vector数组等类型。

1 静态数组

静态数组是指其长度是一个编译器确定的常量，数组长度固定不变，存储在栈空间或全局空间。

    const int size = 11;
    int arr[size] = {0};

静态数组虽然在空间使用上不灵活，或可能存在浪费，但却有较高的时间使用效率。

2 动态数组

动态数组是指其长度在运行期确定，也就是长度可变，存储在堆空间。

int *arr = (int*)malloc(sizeof(int)*11);
// arr使用，其使用空间不能超过分配的空间，否则free时会出错
free(arr);

3 变长数组

变长数组是指数组声明时其长度可以用一个非常量的整型变量来表示：

    int n = 11;
    int arr2[n] = {0} // C99

变长数组用整型变量或表达式来声明或定义，并不是说数组的长度会随时变化，变长数组在其生存期内的长度同样是固定的。

4 柔性数组

柔性数组是指通过结构体来实现一个长度可变长的动态数组。

#include <stdio.h>
#include <stdlib.h>

void foo()
{
    struct ST{
        int n;
        int arr[0];
    };
    //ST s;
    //s.n = 10;
    //s.arr = (int[])malloc(sizeof(int)*s.n);
    
    struct ST* st = (struct ST*)malloc(sizeof(struct ST)+24*sizeof(int));
    st->n = 10;
    for(int i=0;i<st->n;i++)
    {
        st->arr[i] = i+1;
    }
    for(i=0;i<st->n;i++)
    {
        printf("%d ",st->arr[i]);
    }
    struct ST* newst = (struct ST*)realloc(st,sizeof(int)*21);
    if(newst!=NULL)
        st = newst;
    st->n = 20;
    for(i=10;i<st->n;i++)
        st->arr[i] = i+1;
    printf("\n");
    for(i=0;i<st->n;i++)
    {
        printf("%d ",st->arr[i]);
    }
    free(st); // 当过量使用时，free会出错，如只分配了44Byte,却使用到了20个int
}
void foo2()
{
    struct ST{
        int n;
        int *arr;
    };
    struct ST* st = (struct ST*)malloc(sizeof(struct ST));
    st->n = 10;
    st->arr = (int*)malloc(sizeof(int)*10);
    for(int i=0;i<st->n;i++)
    {
        st->arr[i] = i+1;
    }
    for(i=0;i<st->n;i++)
    {
        printf("%d ",st->arr[i]);
    }
    int* newarr = (int*)realloc(st->arr,94);
    if(newarr!=NULL)
        st->arr = newarr;
   st->n = 20;
    for(i=10;i<st->n;i++)
        st->arr[i] = i+1;
    printf("\n");
    for(i=0;i<st->n;i++)
    {
        printf("%d ",st->arr[i]);
    }
    free(st->arr);
    free(st);
    st->arr=NULL;
    st=NULL;
}
int main()
{
    foo();
    printf("\n");
    foo2();
    getchar();
    return 0;
}

通常通过封装一个结构体（结构体中包含一个指针，由指针指向一块动态内存）来构建一个动态数组，并做适当的边界检查。但相对而言，柔性数组也有其优势所在。柔性数组只需使用1次malloc，另外，也少了一个指针空间。且内存空间是连续的，可以避免内存碎片，也可以提高缓存命中率。

5 vector数组

vector是一个STL容器（数据结构），属类型泛化、动态长度的数组。

    const int size = 11;
    int arr[size] = {0};
    std::vector<int> vc(arr,arr+size); // <vector>
    for(int i=0;i<50;i++)
        vc.push_back(i+1);
    printf("%d\n",vc[60]); // 50

对于C++来说，正如推荐使用智能指针代替祼指针，使用string类代替C风格字符串，vector也是其推荐使用的数组类型，可以避免数组溢出的风险。

－End－