注册 登录
  • 欢迎访问"运维那点事",推荐使用Google浏览器访问,可以扫码关注本站的"微信公众号"。
  • 如果您觉得本站对你有帮助,那么可以扫码捐助以帮助本站更好地发展。

C语言拾遗:数组指针

Python闲聊 彭东稳 2882次浏览 已收录 0个评论

一、数组介绍

在程序设计中,为了处理方便,把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。

在C语言中,数组属于构造数据类型。一个数组可以分解为多个数组元素,这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同,数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

对于数组(Array)数据结构,它可以存储一个固定大小的相同类型元素的顺序集合。它所包含的每一个数据叫做数组元素(Element),所包含的数据的个数称为数组长度(Length),例如int a[4];就定义了一个长度为4的整型数组,数组名字是a

总结一下数组的定义方式:

dataType 为数据类型,arrayName 为数组名称,length 为数组长度。例如:

从数组的定义可以看出,要想把数据放入内存,必须先要分配内存空间。放入4个整数,就得分配4个int类型的内存空间:

这样,就在内存中分配了4个int类型的内存空间,共4×4=16个字节,并为它们起了一个名字,叫a。如果把数据类型变为叫short,那么就是2×4 = 8个字节。

数组中的每个元素都有一个序号,这个序号从0开始,而不是从我们熟悉的1开始,称为下标(Index)。使用数组元素时,指明下标即可,形式为:

arrayName 为数组名称,index 为下标。例如,a[0] 表示第0个元素,a[3] 表示第3个元素。

接下来我们就把第一行的4个整数放入数组:

这里的0、1、2、3就是数组下标,a[0]、a[1]、a[2]、a[3] 就是数组元素。

需要注意的是:

1) 数组中每个元素的数据类型必须相同,对于int a[4];,每个元素都必须为 int。

2) 数组长度 length 最好是整数或者常量表达式,例如 10、20*4 等,这样在所有编译器下都能运行通过;如果 length 中包含了变量,例如 n、4*m 等,在某些编译器下就会报错。

3) 访问数组元素时,下标的取值范围为 0 ≤ index < length,过大或过小都会越界,导致数组溢出,发生不可预测的情况,务必要引起注意。

4) 数组是一个整体,它的内存是连续的;最低的地址对应第一个元素,最高的地址对应最后一个元素。

二、 数组初始化

上面的代码是先定义数组再给数组赋值,我们也可以在定义数组的同时赋值:

{ }中的值即为各元素的初值,各值之间用,间隔。

对数组赋初值需要注意以下几点:

1) 可以只给部分元素赋初值。当{}中值的个数少于元素个数时,只给前面部分元素赋值。

例如:

表示只给 a[0]~a[4] 5个元素赋值,而后面5个元素自动赋0值。

当赋值的元素少于数组总体元素的时候,剩余的元素自动初始化为 0:对于short、int、long,就是整数0;对于char,就是字符 ‘\0’;对于float、double,就是小数0.0。

我们可以通过下面的形式将数组的所有元素初始化为 0:

由于剩余的元素会自动初始化为0,所以只需要给第0个元素赋0值即可;其实为空也可以,所有元素默认都为0。

示例:输出数组元素。

经过 gcc test.c -o test.out编译后(不指定编译后文件名,默认为a.out),运行test.out结果如下:

2) 只能给元素逐个赋值,不能给数组整体赋值

例如:给十个元素全部赋1值,只能写为

而不能写为:

3) 如给全部元素赋值,那么在数组定义时可以不给出数组的长度。

例如:

等价于

三、指针介绍

指针是C语言中广泛使用的一种数据类型。运用指针编程是C语言最主要的风格之一。

利用指针变量可以表示各种数据结构;能很方便地使用数组和字符串;并能象汇编语言一样处理内存地址,从而编出精练而高效的程序。指针极大地丰富了C语言的功能。

我们计算机中所有的数据都必须放在内存中,不同类型的数据占用的字节数不一样,例如 int 占用4个字节,char 占用1个字节。为了正确地访问这些数据,必须为每个字节都编上号码,就像门牌号、身份证号一样,每个字节的编号是唯一的,根据编号可以准确地找到某个字节。

我们将内存中字节的编号称为地址(Address)或指针(Pointer)。地址从 0 开始依次增加,对于 32 位环境,程序能够使用的内存为 4GB,最小的地址为 0,最大的地址为 0XFFFFFFFF。

下面的代码演示了如何输出一个地址:

输出结果如下:

%#X表示以十六进制形式输出,并附带前缀0X。a 是一个变量,用来存放整数,需要在前面加&来获得它的地址;array 本身就表示字符串的首地址,不需要加&

一切都是地址

C语言用变量来存储数据,用函数来定义一段可以重复使用的代码,它们最终都要放到内存中才能供 CPU 使用。

数据和代码都以二进制的形式存储在内存中,计算机无法从格式上区分某块内存到底存储的是数据还是代码。当程序被加载到内存后,操作系统会给不同的内存块指定不同的权限,拥有读取和执行权限的内存块就是代码,而拥有读取和写入权限(也可能只有读取权限)的内存块就是数据。

CPU 只能通过地址来取得内存中的代码和数据,程序在执行过程中会告知 CPU 要执行的代码以及要读写的数据的地址。如果程序不小心出错,或者开发者有意为之,在 CPU 要写入数据时给它一个代码区域的地址,就会发生内存访问错误。这种内存访问错误会被硬件和操作系统拦截,强制程序崩溃,程序员没有挽救的机会。

CPU 访问内存时需要的是地址,而不是变量名和函数名!变量名和函数名只是地址的一种助记符,当源文件被编译和链接成可执行程序后,它们都会被替换成地址。编译和链接过程的一项重要任务就是找到这些名称所对应的地址。

假设变量 a、b、c 在内存中的地址分别是 0X1000、0X2000、0X3000,那么加法运算c = a + b;将会被转换成类似下面的形式:

( )表示取值操作,整个表达式的意思是,取出地址 0X1000 和 0X2000 上的值,将它们相加,把相加的结果赋值给地址为 0X3000 的内存

变量名和函数名为我们提供了方便,让我们在编写代码的过程中可以使用易于阅读和理解的英文字符串,不用直接面对二进制地址,那场景简直让人崩溃。

需要注意的是,虽然变量名、函数名、字符串名和数组名在本质上是一样的,它们都是地址的助记符,但在编写代码的过程中,我们认为变量名表示的是数据本身,而函数名、字符串名和数组名表示的是代码块或数据块的首地址。

四、数组指针

数组(Array)是一系列具有相同类型的数据的集合,每一份数据叫做一个数组元素(Element)。数组中的所有元素在内存中是连续排列的,整个数组占用的是一块内存。

定义数组时,要给出数组名和数组长度,数组名可以认为是一个指针,它指向数组的第 0 个元素。在C语言中,我们将第 0 个元素的地址称为数组的首地址。以数组 a[6] = {100, 200, 300, 400} 为例,下图是 a 的指向:

C语言拾遗:数组指针

数组名的本意是表示整个数组,也就是表示多份数据的集合,但在使用过程中经常会转换为指向数组第 0 个元素的指针,所以上面使用了“认为”一词,表示数组名和数组首地址并不总是等价。可以暂时忽略这个细节,把数组名当做指向第 0 个元素的指针使用即可。

下面的例子演示了如何以数组指针的方式遍历数组元素:

运行结果如下:

代码中sizeof(arr) 会获得整个数组所占用的字节数,sizeof(int) 会获得一个数组元素所占用的字节数,它们相除的结果就是数组包含的元素个数,也即数组长度。

我们使用了*(a+i) = i + 100这个表达式,a 是数组名,指向数组的第 0 个元素,表示数组首地址,并且赋值;a+i 指向数组的第 i 个元素,*(a+i) 表示取第 i 个元素的数据,它等价于 a[i]。

我们也可以定义一个指向数组的指针,例如:

a 本身就是一个指针,可以直接赋值给指针变量 p。a 是数组第 0 个元素的地址,所以int *p = a;也可以写作int *p = &a[0];。也就是说,a、p、&a[0] 这三种写法都是等价的,它们都指向数组第 0 个元素,或者说指向数组的开头。

如果一个指针指向了数组,我们就称它为数组指针(Array Pointer)。

数组指针指向的是数组中的一个具体元素,而不是整个数组,所以数组指针的类型和数组元素的类型挂钩;并且其数组名本身就是一个指针,指向数组的首地址。上面的例子中,p 指向的数组元素是 int 类型,所以 p 的类型必须也是int *。其每次跳动都会跳跃4个字节,*(a+2)就是跳过8个字节,然后就跳到了第3个元素的开始,然后*就把数据取出来。

反过来想,p 并不知道它指向的是一个数组,p 只知道它指向的是一个整数,究竟如何使用 p 取决于程序员的编码。

我们把使用数组指针来遍历数组元素的代码简单变更为下面这样:

数组在内存中只是数组元素的简单排列,没有开始和结束标志,在求数组的长度时不能使用sizeof(p) / sizeof(int),因为 p 只是一个指向 int 类型的指针,编译器并不知道它指向的到底是一个整数还是一系列整数(数组),所以 sizeof(p) 求得的是 p 这个指针变量本身所占用的字节数,而不是整个数组占用的字节数。

也就是说,根据数组指针不能逆推出整个数组元素的个数,以及数组从哪里开始、到哪里结束等信息。不像字符串,数组本身也没有特定的结束标志,如果不知道数组的长度,那么就无法遍历整个数组。

对指针变量进行加法和减法运算时,是根据数据类型的长度来计算的。如果一个指针变量 p 指向了数组的开头,那么 p+i 就指向数组的第 i 个元素;如果 p 指向了数组的第 n 个元素,那么 p+i 就是指向第 n+i 个元素;而不管 p 指向了数组的第几个元素,p+1 总是指向下一个元素,p-1 也总是指向上一个元素。

更改上面的代码,让 p 指向数组中的第二个元素:

运行结果:

引入数组指针后,我们就有两种方案来访问数组元素了,上面都已经使用过了,一种是使用下标,另外一种是使用指针。

1) 使用下标

也就是采用 a[i] 的形式访问数组元素。如果 p 是指向数组 a 的指针,那么也可以使用 p[i] 来访问数组元素,它等价于 a[i]。

2) 使用指针

也就是使用 *(p+i) 的形式访问数组元素。另外数组名本身也是指针,也可以使用 *(a+i) 来访问数组元素,它等价于 *(p+i)。

不管是数组名还是数组指针,都可以使用上面的两种方式来访问数组元素。不同的是,数组名是常量,它的值不能改变,而数组指针是变量(除非特别指明它是常量),它的值可以任意改变。也就是说,数组名只能指向数组的开头,而数组指针可以先指向数组开头,再指向其他元素。

更改上面的代码,借助自增运算符来遍历数组元素:

代码中 *p++ 应该理解为 *(p++),每次循环都会改变 p 的值(p++ 使得 p 自身的值增加),以使 p 指向下一个数组元素。该语句不能写为 *a++,因为 a 是常量,而 a++ 会改变它的值,这显然是错误的。

四、延伸

Python的LIST数据类型就是使用数组实现的,对于数组来说根据下标取数据的时间复杂度为O(1),元素赋值的时间复杂度也是O(1)。另外hash表的桶一般是数组,hash对一个字符串计算出来的hash值一般是整数,可直接作为数组下标。所以hash查找索引当然会很快,时间复杂度是O(1)。不过只有无冲突的hash table复杂度才是O(1),一般是O(c),c为哈希关键字冲突时查找的平均长度。

但对key进行hash的时候,不同的key可能hash出来的结果是一样的,尤其是数据量增多的时候,这个问题叫做哈希冲突。如果解决这种冲突情况呢?通常的做法有两种,一种是链接法,另一种是开放寻址法。比如说开放寻址法中,所有的元素都存放在散列表里,当产生哈希冲突时,通过一个探测函数计算出下一个候选位置,如果下一个获选位置还是有冲突,那么不断通过探测函数往下找,直到找个一个空槽来存放待插入元素。

由此看来数组的深入理解是多么重要。


如果您觉得本站对你有帮助,那么可以支付宝扫码捐助以帮助本站更好地发展,在此谢过。
喜欢 (0)or分享 (0)
关于作者:

您必须 登录 才能发表评论!