算法与数据结构前置知识(1)—c语言指针

前段时间自己开始写一个事件驱动web服务器，由于使用的是c语言，发现所有数据结构都需要自己从0开始实现，在写的过程中并不是很顺利，由此萌生了写这一系列文章的想法，也是对数据结构和算法回顾。

后续代码主要使用c语言实现，也正是因为这样，前面花了3篇文章来回顾c语言的必要知识。至于为什么使用c语言我有一些自己的看法，这里我讲两个主要的原因。第一，c语言更接近底层，操作系统的底层实际上也是一个个数据结构和算法堆砌而成的，使用c语言实现可以更好的窥视系统底层运行原理。第二，c语言原生支持指针，对于链表、树、图这类数据结构使用指针更能事倍功半。当然，除了c语言我还会根据数据结构的实际特点使用其它语言实现比如python、java、go，并且对比它们之前的差异。

1. 指针的声明

int *p = NULL;

上面声明了一个指针p，p表示指针变量，值是所在内存的地址。

要注意指针一定要进行初始化，一般我们使用NULL来初始化指针变量，NULL表示不指向任何地址的指针，上面的声明如下图：

图：1-1

下面我们对p进行赋值：

int a = 100; p = &a;

这时候就变成下面这样，如图：

图：1-2

来看一下下面的声明

int* a,b;

a是一个int类型指针变量，b是一个int类型的变量。通常情况下，在声明指针的时候一般会把'*'放到变量名的一侧，例如：
int *a,b;
这样在我们阅读的时候能够减少一些歧义。

考虑下面的声明：

int *func();

上面的声明会先执行()，所以上面的声明表示函数返回一个int型指针。

接着看下面的声明：

int (*func)();

上面的声明会先执行(*func)表示某个类型的指针，接着执行()，表示一个返回值为int的函数指针，这也是函数指针最简单的声明。关于函数指针，我们后面再详细说明。

2. 指针的使用

我们使用'*'操作符来对指针解引用，例如：

int *a = NULL; 
int b = 100; 
a = &b;

上面a=100表示将a所在地址的值修改为100。''表示对指针变量解引用，很多书上都是这么说的，对于没怎么使用过指针的人来讲还是太抽象了。我们通过下面的图来理解，见图2-1

图：2-1

我们还可以对指针进行加减运算，例如：

a++; 
a--; 
a += 1; 
a -= 1;

这在c语言中都是合法的，要注意的是对于上面的指针变量a来说，a++和a--都会导致不可预料的结果，我们在对内存进行加减操作的时候一定要有明确的边界条件。对内存地址变量+1表示往后移动对应类型的长度，比如说我们在32位机器上声明一个int类型的指针，那么对指针变量进行+1操作实际上对于地址变量来讲是加了8个字节的长度，这点要注意。

3. 数组与指针

数组与指针的关系一直是学习指针的一个难点，来看下面两个声明：

int a[10]; 
int *p = NULL;

a是一个长度为10元素类型为整型的数组，p是一个不指向任何地址的整型指针。如果听到有人说数组等同于指针这种说法要小心了，这种说法是不完全对的。例如我们考虑下面的情况：

文件1：

int a[10];

文件2：

extern int *a;

上面我们在文件1中定义了一个长度为10元素类型为整型的数组a，在文件2中给出一个a的声明int *a。直觉上，我们会把文件1中的a和文件2中的a都当成一个指针，因为它们都保存了一个内存地址。但实际上，上面这种做法是错误的。

为了说明上述问题，我们需要弄明白c语言中的两个术语定义和声明。在上述例子中，文件1中的 int a[10]表示定义，定义是需要占用内存空间的。文件2中的extern int *a表示是声明，不分配内存空间，编译器编译的时候会找到定义的实体也就是文件1中的a，我们可以把定义想象成古时候的皇帝，把声明想象成钦差大臣，并且他们的意志完全一样，但钦差大臣本身不可能像皇帝一样掌控皇权，他只是代表了皇帝的意志。这里的皇权就相当于定义中分配的地址空间。

搞明白了定义和声明的意思，下面我们来分析一下上面的例子为什么是错误的。为了搞明白，我们要先搞清楚数组和指针使用的时候中间发生了什么。

考虑下面的情况:

char a[10] = "hello world!"; 
a[1]; 
char *b = "hello world!"; 
b[1];

对于a[1]来讲，直接访问初始地址的内容e，如下图：

图：3-1

对于b[1]来讲，是先将提取b所保存的地址然后把地址加1个字符的长度，拿到存储字符e所在的地址，然后取地址里的内容e，如下图：

图：3-2

那么问题就来了，我们看第一个例子，定义为int a[10]，声明为int *a会发生什么，当我们对声明的a(int *a)进行a[1]访问的时候，会先提取a的地址，然后加一个字符长度，再取计算后地址里的内容。但是定义里面a是一个数组，我们使用a[1]去访问的时候拿到的是字符e，并不是一个地址，这个时候编译器就会报错。

上面说明了数组和指针在使用时候的的区别，这也说明了为什么数组等同于指针这种说法是不正确的。下面对数组和指针的区别总结如下：

1. 数组是编译器随机分配的内存地址，不能修改，而指针的地址是可以修改的。

2. 数组保存的是数据，指针保存的是数据的指针。

3. 数组a[1]表示直接访问数据，指针a[1]表示先提取a的地址，然后将地址加一个单位长度，最后取计算后地址里的内容。

当然，数组和指针还有一其它一些细微的差别，但是只要掌握了以上的内容，应该能将数组和指针的关系搞明白了。

4. 结构指针

结构指针和普通指针并没有什么区别，只是在使用上有一些扩展。

例如：

typedef struct _TEST{ 
  int age; 
  char *name; 
} test; 
test t = {20, "张三"}; 
test *t2 = &t; 
int age = (*t2).age; 
char *name = (*t2).name; 
(*t2).age = 30;

要注意的是，使用指针的访问结构成员的时候要将操作符放在括号内，操作符的优先级低于.操作符。

结构还提供了一种方便操作符->来操作结构指针，例如：

t2->age = 30; 
int age = t2->age;

由于结构占用的内存空间是结构内部所有元素之和，所以在将结构当作函数参数的时候我们一般都使用结构指针，可以回顾结构那一节。

5. 函数指针

在第一节我们说到声明函数指针的简单声明：

int (*fn)();

表示返回值为int的函数指针，但这个函数是没有参数的，下面我们来看一下函数指针的使用方法及注意事项。

5.1. 声明函数指针

int (*func01)(int); 
int (*func02)(int, char*); 
char* (*func03)(int, char*);

图：5-1

5.2. 函数指针的使用

调用：

func_name(name, 23) // 或者 (*func_name)(name, 23)

传参：

find(func_name); // 或者 find(&func_name);

5.3. 函数指针数组

创建：

void (*func_arr[])(char*, int);