《C语言》—— 数组详解

Myth丶恋晨 2023-02-23 14:29 9阅读 0赞

### 数组的基本概念 ###

我们把一组数据的集合称为 **数组（Array）** ，它所包含的每一个数据叫做 **数组元素** （Element），所包含的数据的个数称为 **数组长度** （Length），数组中的每个元素都有一个序号，这个序号从0开始，而不是从我们熟悉的1开始，称为 **下标** （Index），所包含数组的里面元素的类型叫做 **数组类型** （Type）。

一句话就说清楚了数组的基本概念，就是这么简单，\_。

### 数组底层结构探析 ###

1int array[5];

#### 内存布局图 ####

![image][]

不要看这个图简单，底层就是这样的。数组是一个整体，它的内存是 **连续** 的；也就是说，数组元素之间是相互挨着的，彼此之间没有一点点缝隙。

#### 这一点很重要,连续的内存为 [指针][Link 1] 操作（通过指针来访问数组元素）和内存处理（整块内存的复制、写入等）提供了便利，这使得数组可以作为缓存使用。 ####

有同学估计要说什么叫做指针操作，听龙叔絮叨下。

1int arr[5] = {1,2,3,4,5};
    2printf("%d\n",arr[3]);

看上面的代码，学过数组都知道arr\[3\]是取第三个元素的值， **那我就要问你了，怎么取到值的呢？？？**

不要慌，龙叔告诉你其实就是指针操作。当我们声明并定义数组 `int arr[5] = {1,2,3,4,5}` ，此时数组被分配了5个int大小的空间在 **栈上** ，并初始化了数组元素。我们都知道数组名代表数组的首元素的首地址，那么很明显就可以得到 `arr[3] = arr + 3` 。指针的加减操作详情请看龙叔公号，微信搜索 **龙跃十二** 即可订阅喔。

![image][image 1]

### 数组的运算 ###

1int a[] = {1,2,3,4};
     2printf("%d\n",sizeof(a));
     3printf("%d\n",sizeof(a+0));
     4printf("%d\n",sizeof(*a));
     5printf("%d\n",sizeof(a+1));
     6printf("%d\n",sizeof(a[1]));
     7printf("%d\n",sizeof(&a));
     8printf("%d\n",sizeof(&a+1));
     9printf("%d\n",sizeof(&a[0]));
    10printf("%d\n",sizeof(&a[0]+1));
    11//字符数组
    12char arr[] = {'a','b','c','d','e','f'};
    13printf("%d\n", sizeof(arr));
    14printf("%d\n", sizeof(arr+0));
    15printf("%d\n", sizeof(*arr));
    16printf("%d\n", sizeof(arr[1]));
    17printf("%d\n", sizeof(&arr));
    18printf("%d\n", sizeof(&arr+1));
    19printf("%d\n", sizeof(&arr[0]+1));
    20printf("%d\n", strlen(arr));
    21printf("%d\n", strlen(arr+0));
    22printf("%d\n", strlen(*arr));
    23printf("%d\n", strlen(arr[1]));
    24printf("%d\n", strlen(&arr));
    25printf("%d\n", strlen(&arr+1));
    26printf("%d\n", strlen(&arr[0]+1));
    27char *p = "abcdef";printf("%d\n", sizeof(p));
    28printf("%d\n", sizeof(p+1));
    29printf("%d\n", sizeof(*p));
    30printf("%d\n", sizeof(p[0]));
    31printf("%d\n", sizeof(&p));
    32printf("%d\n", sizeof(&p+1));
    33printf("%d\n", sizeof(&p[0]+1));
    34printf("%d\n", strlen(p));
    35printf("%d\n", strlen(p+1));
    36printf("%d\n", strlen(*p));
    37printf("%d\n", strlen(p[0]));
    38printf("%d\n", strlen(&p));
    39printf("%d\n", strlen(&p+1));
    40printf("%d\n", strlen(&p[0]+1));
    41//二维数组
    42int a[3][4] = {0};
    43printf("%d\n",sizeof(a));
    44printf("%d\n",sizeof(a[0][0]));
    45printf("%d\n",sizeof(a[0]));
    46printf("%d\n",sizeof(a[0]+1));
    47printf("%d\n",sizeof(a+1));
    48printf("%d\n",sizeof(&a[0]+1));
    49printf("%d\n",sizeof(*a));
    50printf("%d\n",sizeof(a[3]));

就这几个运算，估计会难倒很多同学的，不信你可以把答案写出来之后在去跑一遍， **全对找我拿红包** 。

![image][image 2]

#### sizeof(数组名)，代表整个数组的字节数；&数组名，代表取得整个数组的地址。 ####

### 数组的一些特性 ###

1.  严格上说数组只有一维数组。n维数组是在一维数组里面存放一个(n-1)维数组，掌握以为数组即可。
2.  数组的长度指的是数组的元素个数不是数组空间长度。sizeof()关键字即可获取数组总的字节数，在除以元素类型的字节数即可得到数组长度。
3.  C语言并不会判断数组访问越界，需要程序员判断越界访问。eg: `int arr[5] = {1,2,3,4,5}; int b = arr[10];` ，这样访问也是可以拿到元素的，天知道你访问的是谁的数据。
4.  数组底层内存结构是连续的。正是由于数组结构的连续性便诞生了内存的友好性，数组分配内存是整块分配的，堆内存很友好；连续的内存是的访问内存效率高。
5.  数组大小是固定不变的。需要改变大小就需要新开一块大内存的数组，把之前的元素拷贝过来，释放之前的内存。
6.  数据根据下标随机访问的时间复杂度为 O(1)
7.  数据的插入和删除很低效：

*  如果删除数组末尾的数据，最好情况时间复杂度为 O(1)
 *  如果删除开头的数据，则最坏情况时间复杂度为 O(n)
 *  平均情况时间复杂度也为 O(n)。

### 数组常见问题 ###

#### 数组长度是一个非常量。 ####

1int b;
    2scanf("%d",&b);
    3int arr[3*b];

不知道你曾经有没有写过这样的代码，反正我写过。数组的长度和内存是在程序 **编译时** 就已经确定了的。b的值是在 **运行时** 才确定的。有两个新名词， **程序编译时&程序运行时** 。

#### 数组越界访问 ####

1int arr[5] = {1,2,3,4,5};
    2printf("%d\n",arr[-1]);
    3printf("%d\n",arr[1]);
    4printf("%d\n",arr[4]);
    5printf("%d\n",arr[5]);
    6printf("%d\n",arr[6]);

肉眼可见的错误，编译器竟然没报错。

![image][image 3]

### 数组相关笔试题目 ###

1.  给你一个数组，求一个k值，使得前k个数的方差 + 后面n-k个数的方差最小 ，时间复杂度可以到O(n)。
2.  给定一个n个整型元素的数组a，其中有一个元素出现次数超过n / 2，求这个元素。
3.  给定一个含有n个元素的数组，找出数组中的两个元素X和Y使得abs（x-y）最小。
4.  在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
5.  在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。
6.  给定一个数组A\[0,1,…,n-1\],请构建一个数组B\[0,1,…,n-1\],其中B中的元素B\[i\]=A\[0\] *A\[1\]* … *A\[i-1\]* A\[i+1\] *…* A\[n-1\]。不能使用除法。（注意：规定B\[0\] = A\[1\] \* A\[2\] \* … \* A\[n-1\]，B\[n-1\] = A\[0\] \* A\[1\] \* … \* A\[n-2\];）

利用数组可以出很多笔试题目，当然这些题目很多并不是考验数组本身特性大多是考算法基础的。

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。  
![format_png][]  
![format_png 1][]

[image]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMTg4MTc0Mi01ODlkYmJjMTMxZjAwZjE0LmpwZyF3ZWI?x-oss-process=image/format,png
[Link 1]: https://mp.weixin.qq.com/s/tdyCTqH9WYMrS0HmRtVPng
[image 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMTg4MTc0Mi02ODVjOGEzYWY5NDM1NDYwLmpwZyF3ZWI?x-oss-process=image/format,png
[image 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMTg4MTc0Mi00ZDE2OWRkZjQ1YWRkN2Y0LmpwZyF3ZWI?x-oss-process=image/format,png
[image 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMTg4MTc0Mi0yN2U1NzIzMjg4ODAxZDYxLmpwZyF3ZWI?x-oss-process=image/format,png
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMTg4MTc0Mi03N2U2N2Q1MmVmMTI4MDQ4LnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xMTg4MTc0Mi0zOThmNmE5MGUxZjFiZTAwLnBuZw?x-oss-process=image/format,png