馨荣家园

数组和指针概念很容易让初学者混淆，这里把我所知道的概括一下，希望对大家有所帮助。

一维数组和一级指针的相同和差异

一维数组的名字大部分情况下可以当成一个常指针来看，也就是说：

 int a[3]
 int * const p;

则数组名a可以在大部分p能用的地方使用，有两种情况比较特殊：

1. p可以在定义是初始化一个地址如：int *p const = new int[100];，而且这也是唯一的初始化他的机会。而数组则是有操作系统载入可执行文件时初始化内存空间的。
2. sizeof运算符对p计算将获得指针的长度（现在一般为4），而对数组名则得到数组占有的所有字节数。

在内存排布上，一维数组和一阶指针指向的内存是完全一样的。

高维数组和高阶指针

对于高维数组（以二维为例，其他完全一样），情况和一维数组完全不一样。例如对于数组和指针：

 int a[3][4]
 int**p;

他们就没有任何可比性。初学者从一维数组中的知识简单的推断出a是一个等价于int**的东西，*a就可以得到一个 int*的值，这其实是完全错误的。

从内存排布上，数组按照先低维后高维的顺序一次排列数组的每个元素。其中低维到高维是指定义数组时，离数组名越近的维为低维，反之为高维，例如上面这个数组，3就是低维的维数，4为高维的维数，因此，在内存中，上面这个数组占有12个int单元，所有单元靠在一起，其顺序则为

a[0][0]，a[0][1]，a[0][2]，a[0][3]
a[1][0]，a[1][1]，a[1][2]，a[1][3]
a[2][0]，a[2][1]，a[2][2]，a[2][3]

如果a是一个和二阶指针等价的常量，那么他的值应该指向一个指针数组才对，而实际上这样的指针数组是不存在。

从前面这个排布还可以看出一个问题，在排列过程中，数组的最低维不确定是没有关系的，但是为了安排好数组元素的先后顺序，高维的维数必须确定，也就是说在使用数组类型来定义指针时，必须首先确定高维，例如：

  int (*p)[3] = new int[4][3]
 

是可以的，但是

  int (*p)[] = new int[4][3]
 

就不行。

回到一维数组

仔细考虑一维数组和多维数组，是不是编译器对一维数组特殊处理了？其实也不是，数组名其实代表的是数组对象也就是其第一个元素的地址，从这个角度讲，一维数组名a代表了a[0]的地址，二维数组名a代表了a[0][0]的地址，高维数组的名字从这个意义讲更接近1阶指针。

整除

如果非0整数a和整数b满足

其中k也是整数，则说a整除b，记做 a|b，也称a是b的一个因子或约数，b是a的倍数。

关于因子的简单结论有：

• 1是所有整数的因子
• 所有整数(0除外)都是0的因子
• 如果a | b,b|c ，则a |c ，也就是整除性是传递的。
• 如果a | b且 b|a ，则a = ±b
• 如果a | b,a |c,m,n是整数，则a | mb+nc

公约数和最大公约数

如果整数d满足d|a且d|b，则说d是整数a、b的公约数。在整数a、b的所有正公约数中，值最大的被称为最大（正）公约数，记 做gcd(a,b)，其中gcd是Greatest Common Divisor的缩写。最大公约数有时又被称为最大公因子。

定理：如果d是整 数a,b的公约数，则d是ma + nb的约数(其中m,n是整数)，且满足ma+nb形式的最小的正整数是a,b的最大公约数。

证明：

     
1)
假设d是a,b的一个约数，d|a,d|b，集合S = { ma + nb | m,n ∈ Z}，则对于S中任意一个元素x，有
           x = k1a + k2b
因此根据前面结论，d | x，也就是说d整除S中的每个元素。由此可以得出，S中的最小整数是a,b所有
公约数的倍数。
2)
假设d是集合S中最小的正整数，则d能整除S中任何一个元素。反证：假设存在x∈S，d不能整除x，则x可以表示为
                x = kd + r 
其中r为小于d的正整数，由于x,d都是S的元素，因此都可以表示为ma+nb的形式，由上式可以得出
               r = x - kd
也可以表示为ma + nb的形式，因此r∈S，这于d是S中最小正整数矛盾。因此，d能整除S中任何一个元素。
3) a和b都是S的元素，因为
               a = 1 a + 0 b
               b = 0 a + 1 b
因此2中所述的d必然能整除a,b，因此d是a,b的公约数。而根据1，a,b的所有约数都能整除d，因此d是最大公约数。

质数和互质

正整数p是一个质数的条件是：

• p > 1
• p的正因子有且只有两个，就是p和1

因此，最小的质数是2，而除了2之外，所有的偶数都不是质数。

互质的概念其实和质数没有什么关系，互质的定义为：如果非0整数a,b的最大公约数为1，则说这两个数互质。

除法和余数

对于整数a和b，则b一定可以表示成

 b = ka +r

其中k、r是整数，且0 ≤ r < a，称呼r为b除以a的余数，当r为0时，a | b 。计算b除以a的余数的过程称为模运算。

如果整数a,b除以p的余数相等，称为a,b模p相等，记做

  a ≡ b mod p