一般地，计算机内存的每个位置都由一个地址标识，在C语言中我们用指针表示内存地址。指针变量的值实际上就是内存地址，而指针变量所指向的内容则是该内存地址存储的内容，这是通过解引用指针获得。声明一个指针变量并不会自动分配任何内存。在对指针进行间接访问前，指针必须初始化: 要么指向它现有的内存，要么给它分配动态内存。
对未初始化的指针变量执行解引用操作是非法的，而且这种错误常常难以检测，其结果往往是一个不相关的值被修改，并且这种错误很难调试，因而我们需要明确强调: 未初始化的指针是无效的，直到该指针赋值后，才可使用它。　
*a=12; //只是声明了变量a,但从未对它初始化，因而我们没办法预测值12将存储在什么地方
int *d=0; //这是可以的，0可以视作为零值
int *c=&b;
另外C标准定义了NULL指针，它作为一个特殊的指针常量，表示不指向任何位置，因而对一个NULL指针进行解引用操作同样也是非法的。因而在对指针进行解引用操作的所有情形前，如常规赋值、指针作为函数的参数，首先必须检查指针的合法性- 非NULL指针。
解引用NULL指针操作的后果因编译器而异，两个常见的后果分别是返回置0的值及终止程序。总结下来，不论你的机器对解引用NULL指针这种行为作何反应，对所有的指针变量进行显式的初始化是种好做法。
如果知道指针被初始化为什么地址，就该把它初始化为该地址，否则初始化为NULL
在所有指针解引用操作前都要对其进行合法性检查，判断是否为NULL指针，这是一种良好安全的编程风格
1.1 指针运算基础
在指针值上可以进行有限的算术运算和关系运算。合法的运算具体包括以下几种: 指针与整数的加减(包括指针的自增和自减)、同类型指针间的比较、同类型的指针相减。例如一个指针加上或减去一个整型值，比较两指针是否相等或不相等，但是这两种运算只有作用于同一个数组中才可以预测。如float指针加3的表达式实际上使指针的值增加3个float类型的大小，即这种相加运算增加的是指针所指向类型字节大小的倍数。参考
对于任何并非指向数组元素的指针执行算术运算是非法的，但常常很难被检测到。
如果对一个指针进行减法运算，产生的指针指向了数组中第1个元素前面的内存位置，那么它是非法的。
加法运算稍微不同，如果产生的指针指向了数组中最后一个元素后面的那个内存地址，它是合法的,但不能对该指针执行解引用操作，不过之后就不合法了(这和STL中迭代器尾部元素可指向尾部元素的下一个位置是一样的道理)
关于指针的运算操作将会在数组中的应用中更深入地介绍。
1.2 typedef和C++中的引用
C语言中用typedef说明一种新类型名，来代替已有类型名。它的作用是给已存在的类型起一个别名，原有类型名仍然有效。如下:
typedef float REAL;
typedef char*
那么和#define有什么区别呢？
typdef int* int_t;
#define int_d int*;
它们的区别主要在于:
前者在于声明一个类型的别名，在编译时处理有类型检查；而后者只是简单的宏文本替换，无类型检查
从使用上来说,int_t a,b这两个变量都是int *类型的，而int_d a,b中b是int类型的
为了更好的理解指针，所以也有必要把C++中的一些概念引入进来作对比。C++中所谓的引用实际上是一个特殊的变量，这个变量的内容是绑定在这个引用上面的对象的地址，而使用这个变量时，系统自动根据这个地址去找到它绑定的变量，再对变量操作。即引用的本身只是一个对象的别名，在引用的操作实际是对变量本身的操作。
本质上说，引用还是指针，只不过该指针不能修改，一旦定义了引用，就必须跟一个变量绑定起来，且无法修改此绑定。尽管使用引用和指针都可间接访问某个值，但它们还是有区别的。
引用被创建时，它必须初始化(引用不能为空)；指针可以为空值，可在任何时候被初始化
一旦引用被初始化为指向某个对象，它就不能改变为另一个对象的引用；指针可以在任何时候指向另一个对象
不能有NULL引用，必须确保引用是和一块合法的存储单元关联
sizeof(引用)得到的是所指向变量的大小；sizeof(指针)得到的是指针本身的大小
在函数中传递实参时，对于非引用类型的形参的任何修改仅作用于局部副本，并不影响实参本身(指针作为参数传递时仍然是传值调用，传递的副本是指针变量的值)。在C++中，为了避免传递副本带来的开销，将形参指定为引用类型，可见这样效率更高。但是也带来了对引用形参的任何修改会直接影响实参本身的副作用。
所以既要利用引用提高效率，又要保护传递的函数参数在函数中不被改变，就应使用常引用，定义一个普通变量的只读属性的别名，避免实参在函数中意外被改变。
const int ival=10;
const int &ref= //必须使用const引用
1.3 各种指针
该小节主要讲述二级指针、通用指针和函数指针，与数组相关的指针在后面第2章中会具体解释。
1.3.1 指向指针的指针
指针本身也是可用指针指向的内存对象。指针占用内存空间存放其值(值作为地址)，因而指针的存储地址可存放在指针中，通过间接访问的方式。只要当确实需要时，才应该是多级指针。
我们在实现二叉树时经常会遇到如何插入节点，在C中由于涉及到了指针，经常使我们对节点间究竟有没有链接成功产生混淆，特别是不清楚什么时候使用二级指针，什么时候又是一级指针。它的结构描述如下：
typedef int T;
typedef struct tree_node {
struct tree_node *
struct tree_node *
下面分析调用该插入节点的方法，能否成功构建二叉树。
void insert_node(node *root,T element);
Step 1: 函数调用参数前，root=NULL
当传递的参数是指针时，我们仍然可以把指针看做变量，即传递的是指针值的副本，即产生了一个和实参地址不同的形参地址，但它们的内容是相同的(这里为NULL),并不指向任何位置
Step 2: 调用函数并修改形参的内容，为root分配了新地址
if(root==NULL)
root=new_node(data);
可看出函数结束后，形参root的内容(指针本身的值)发生了变化，由NULL变成了0x4567的地址(只是为了说明情形，该地址表示并不准确)。可知root已指向一块含有数据的堆内存，而实参root仍为NULL,不指向任何内存位置。
因而一级指针作为参数传递时，在这种方法下形参的变化并未使实参发生任何变化，因而下一次调用插入节点函数时，实参root值始终为NULL，这种方法不能建立起二叉树。那么要成功地构建二叉树，使实参指向的内容发生真正改变呢，有3个方法：
A. 初始化的root结点不为空，即根结点始终不为空
Step 1: 函数调用前实参和形参指向
Step 2: 函数调用后实参和形参指向
回想一下，这种情形是不是很像单链表中的头结点，它极大地简化了插入和删除操作，实现上更为简洁。
B. 插入函数定义为：bstree_node *insert_node(bstree_node *root,element)
返回函数操作中变化的形参地址，再把返回值赋值给实参地址（root初始化可以允许为NULL）,这样函数结束后实参和形参均指向了相同内容
root=insert_node(root,element);
这种方法确实有效，但也可看出有一缺点： 需要重新调整指针的指向，无法在程序执行中自动修改root的地址，而且还占用内存空间。所以要想在插入和删除节点的操作过程中，二叉树能动态地变化而无需指定返回root地址，该用什么样的方法呢。于是二级指针就上场了
C. 插入函数定义为：void insert_node(bstree_node **root,T element)
利用二级指针无需返回值便可动态修改二叉树,这种实现是最有效的。下面请看函数执行前后实参和形参的变化图（始终要记住: 函数的参数传递始终是传值调用(不包括C++中的引用)，即传递的始终是参数的拷贝，一个副本而已）
Step 1: 函数调用前实参和形参指向
Step 2: 函数调用后实参和形参指向
当根结点为空时， *root=new_node(element) 表明执行函数后形参指向的二级指针root的内容发生了变化，重新分配了地址，从而导致指向的结点内容发生了变化，这样实参指向的指针所指向的结点内容同样也发生了变化。
当根结点不为空时，根结点的地址不会发生变化，只会通过链接的形式链上了左右子树。
对比，我们在实现单链表时使用虚拟头结点。优点之一是方便我们简化插入和删除操作，它会动态链接上节点或删除节点。其实它还有一个优点：
不管链表是否为空，头结点始终存在。如果不使用头结点，插入和删除操作就必须要保证一个结点存在使结点链接上，否则就必须使用返回结点地址（这会占用空间）或者使用二级指针（抽象，使用起来容易出问题）。因而使用虚拟头结点就可避免这些问题了
void insert(linknode *list,int data); //list是虚拟头结点，推荐使用
void insert(linknode **list,int data);//使用二级指针，难懂
linknode *insert(linknode *list,int data);//需要重新调整指针指向，占用内存空间
1.3.2 void *指针
C中提供一个特殊的指针类型: void *,它可以保存任何类型对象的地址：
double obj=3.14;
double *pd=&
void *pv=&
void *表明该指针与一地址值相关，但不清楚存储在此地址上的对象的类型。void *指针只支持以下几种操作:
与另一个指针比较
给另外一个void *指针赋值
void *指针当函数参数或返回值
不允许使用void *指针操作它指向的对象，值得注意的是函数返回void *类型时返回一个特殊的指针类型，而不是向返回void 类型那样无返回值。
1.3.3 函数指针
函数指针是指指向函数的指针，函数类型由其返回类型及形参表确定，与函数名无关，有时候还用typedef简化函数指针的定义。
bool (*pf)(int *,int *);
typedef bool (*cmpfcn)(int *,int *); //cmpfcn是一种指向函数的指针类型的名字，该类型为指向返回bool类型并带有两个整型指针参数的函数的指针。
在引用函数名但又没有调用该函数，函数名自动解释为指向函数的指针，并且直接引用函数名就等价于在函数名应用取地址操作符。
bool lencmp(int *,int *);
bool (*)(int *,int *);
cmpfcn pf1=0;
cmpfcn pf2=&
函数指针只能通过同类型的函数名或者函数指针或者0值常量进行初始化和赋值。初始化为0表示该指针不指向任何函数，只有当初始化后才能调用函数。调用它可以直接使用函数名或者直接利用函数指针，不用解引用符号或者使用解引用符号，如下：
cmpfcn pf=
lencmp(a,b); //调用1
pf(a,b); //调用2
(*pf)(a,b); //调用3
另外函数的形参也可以是指向函数的指针，这个通常被称为回调函数。允许形参是一个函数类型，它对应的实参被自动转换为指向相应函数类型的指针，注意函数的返回类型不能是函数。
int (*ff(int))(int ,int); //返回指向函数的指针
typedef int (*PF)(int ,int );
PF ff(int); //函数ff返回一个函数指针
typdef int func(int ,int); //func是一个函数，而不是一个函数指针
void f1(func); //正确，f1的形参是一个函数指针，func自动转换为函数指针
func f2(int); //错误，无法被自动转换
func *f3(int); //正确，f3返回一个函数指针
int (*a[10])(int); //一个有10个指针的数组，每个指针指向一个函数，接收一个整型参数返回一个整型
int (*(*p)[10])(int); //声明一个指向10个元素的数组指针，每个元素是一个函数指针，接收一个整型参数返回一个整型。
2 数组与指针
人们在使用数组时经常会把等同于指针，并自然而然地假定在所有的情况下数组和指针都是等同的。为什么出现这样的混淆？ 因为我们在使用时经常可以看到大量的作为函数参数的数组和指针，在这种情况下它是可以互换的，但是人们容易忽视它只是发生在一个特定的上下文环境中。如在main函数的参数中有这样的char **argv 或char *argv[]的形式，因为argv是一个函数的参数，它诱使我们错误地总结出指针和数组是等价的。如下面一个程序：
#include& stdio.h &
int len(int arr[]){
return sizeof(arr);
int main(){
int arr[]={1,2,3,4,5};
printf(&%d\n&,sizeof(arr)); //sizeof计算类型或变量或类的存储字节大小
printf(&%d\n\n&,len(arr)); //同样使用sizeof,为什么结果不同
printf(&arr=%p\n&,(void *)arr); //指针表示法取地址：arr+0..len-1
printf(&&arr[0]=%p\n\n&,(void *)&arr[0]); //数组表示法取地址: &arr[0..len-1]
int *p=(int *)(&arr+1);//&arr+1与arr+1为什么有区别
int *p1=(int *)(arr+1);
printf(&arr+1=%p\n&,(void *)p1);
printf(&&arr+1=%p\n\n&,(void *)p);
结果如图所示：
可以看出：
使用sizeof计算数组的时候数组名有时候当指针来看，有时候又当整个数组来看待
数组表示法有时候和指针表示法等价，但数组名前加一个&运算符，它却不等同于指针的使用。
可知数组和指针并不全都相同。那么数组什么时候等同于指针，什么时候不等同于指针呢？
2.1 区分定义和声明
extern声明说明编译器对象的类型和名字，描述了其他地方的创建对象
定义要求为对象分配内存：定义指针时编译器并不为指针所指向的对象分配空间，它只是分配指针本身的空间
int a[100];
extern int a[]; //正确并且无需提供关于数组长度的信息
extern int *a;//错误,人们总是错误地认为数组和指针非常类似
2.2 数组和指针是如何访问的
X=Y：左值在编译时可知，表示存储结果的地址;右值表示Y的内容
也就是说编译器为每个变量分配一个左值，该地址在编译时可知，而变量在运行时一直保存于这个地址，而右值只有在运行时才可知。如需用到变量中存储的值，编译器就发出指令从指定地址读入变量值并将它存入寄存器中。如果编译器需要一个地址，可能要加上偏移量来执行某种操作，它就可以直接进行操作，并不需要增加指令取得具体的地址。相反对于指针，必须先在运行时取得它的值然后才能对它解引用。
下面分别是对数组下标的引用和对指针的引用的描述：
char a[9]=”abcdefgh”; c=a[i];
编译器符号表具有一个地址9980,运行时
步骤1：取i的值，将它与9980相加
步骤2：取地址（9980+i）的内容
char *p; c=*p;
编译器符号表有一个符号p,它的地址为4624,运行时
步骤1：先得到地址p 的内容，即5081
步骤2：将5081作为字符的地址并取得它的内容
可以看出指针的访问明显灵活很多，但需要增加一次额外的提取
2.3 数组和指针的引用
2.3.1 定义为指针，但以数组方式引用
指针定义编译器会告诉你这是一个指向字符的指针，相反数组定义则告诉你是一个字符序列。
char *p=”hello”;c=p[i];
2.3.2 定义为数组名,但以指针方式引用
数组名变量代表了数组中第一个元素的地址，它并不是一个指针但却表现得像一个不能被修改的常指针 。因而它不能被赋值
对数组下标的引用总是可以写成一个指向数组起始地址的指针加上偏移量
int a[100];
int *p=a; p[i]或*(p+i);
通常情况下，数组下标是在指针的基础上，所以优化器可以把它转化为更有效率的指针表达形式，并生成相同的机器指令，所以C语言采用指针形式就是因为指针和偏移量是底层硬件所使用的基本模型，但在处理一维数组时指针见不得比数组更快
2.3.3 为什么要把数组作为函数的参数传递当作指针
把作为形参的数组和指针等同起来是出于效率的考虑，数组名自动改写成指向数组第一个元素的指针形式，而不是整个数组的拷贝，并且如果要操作数组的元素千万不要在数组名上进行操作，形式应如下:
char *test(char a[]) {
char *p=a;
在C语言规定中，所有非数组形式的数据均以传值形式（即对实参做一份拷贝并传递给调用的函数，函数不能修改作为实参的实际变量的值而只能修改它的那份拷贝）。
因而有些人喜欢把它理解成数组和函数是传址调用，缺省情况下都是传值调用，数据也可以传址调用，即加&地址运算符，这样传递给函数的是实参的地址而不是实参的拷贝。 但严格意义上传址调用也不十分准确，因为编译器的机制是在被调用的函数中，你拥有的是一个指向变量的指针，而不是变量本身，传递的参数只是指针变量值本身的拷贝。
传值调用的拷贝是指分配了栈上的空间地址，内容和实参值一样而形参的地址肯定与实参地址不一样，因而当指针作为函数参数，你只需要测试指针变量值的实参和形参地址是否不一样就可以知道传递的究竟是指针变量值本身的副本还是该指针指向的变量的副本。
例如下面的程序：
#include &stdio.h&
#include &stdlib.h&
void f2(int *a){
printf(&执行函数f2(a)：\n&);
printf(&形参变量a的地址=%p\n&,&a);
printf(&形参变量a的值=%p\n\n&,a);
int main(){
int *a=(int *)malloc(sizeof(int));
printf(&previous *a=%d\n&,*a);
printf(&实参变量a的地址%p\n&,&a);
printf(&实参变量a的值%p\n\n&,a);
printf(&after *a=%d\n&,*a);
printf(&存储*a变量的地址%p\n&,a);
printf(&存储指针变量a的地址%p\n&,&a);
结果如下：
2.3.4 指针数组与数组指针
指针数组： 一个数组里装着指针，即指针数组是一个数组，如int *a[10]
数组指针： 一个指向数组的的指针，即它还是个指针，但指向的是整个数组，如int (*p)[10] 。
二维数组的数组名是一个数组指针，若有：
int a[4][10];
int (*p)[10];
p=a //a的类型就是int (*)[10]
可知p指向含4个数组元素的数组首地址(p=a),但要注意的是a是常量，不可以进行赋值操作。再如：
int a[10];
int (*p)[10]=&a;//注意此处是&a,不是a
int *q=a; //a的类型是int *,&a的类型是int (*)[10]
可以看出p和q虽然都指向数组的第一个元素，但两者类型是不同，p是指向有10个整型元素的指针，p+1要跳过40个字节；而q是指向一个整型元素，p+1跳过4个字节。
注意到数组作为函数实参传递时，传递给函数的是数组首元素的地址；而将数组某个元素的地址当做实参时，传递的是此元素的地址，可理解传递的是子数组(以此元素作为首元素的子数组)首元素的地址。如下题，sum(&aa[i])传递的是以第 i个元素为首元素的子数组，结果输出为4
#include &stdio.h&
void sum(int *a){
a[0]=a[1];
int main(){
int aa[10]={1,2,3,4,5,6,7,8,9},i;
for(i=2;i&=0;i--)
sum(&aa[i]);
printf(&%d\n&,aa[0]); //输出为4
2.4 二维数组
当提到C语言中的数组时，就把它看做一个向量，数组的元素也可以是另一个数组。因而多维数组可以看成数组的数组。 数组下标的规则告诉我们元素的存储和引用都是线性排列在内存中的。 在C和C++中二维数组按照行优先顺序连续存储，一般二维数组a[x][y]在一维数组b中，它们的转换关系如下:
a[x][y]=b[x*列数+y]
如果想动态创建一个二维数组a[m][n],使用后再释放，操作如下:
int **a=new int*[m];
for(int i=0;i&i++)
a[i]=new int[n];
/*释放内存*/
for(int i=0;i&i++)
delete []a[i];
delete []a;
如果你想初始化二维字符串数组，一般利用指针数组初始化字符串常量:
char *p[]={“1heh”,”ghh”,...};
而其他非字符串类型的指针数组不能直接初始化，它的定义如下
int r1[]={3,4,5};
int r2[]={0,9,8,4,3};
int r3[]={0};
int *weight[]={r1,r2,r3};
上面这种长度不一的数组，我们称之为锯齿状数组。在这里有很多处理技巧，例如：
char *ip[len];
char hello[]=”world”;
ip[i]=&hello[0];
//共享字符串，直接使用现有的
ip[j]=malloc(strlen(hello)+1);
strcpy(ip[j],hello); //拷贝字符串，通过分配内存创建一份现有字符串的新鲜拷贝，仅传递指针
还有如，在指针数组的末尾增加一个NULL指针，该NULL指针使函数在搜索这个表格时能够检测到表的结束，而无需预先知道表的长度,如查询C源文件中关键字的个数：
const char *keyword[]={&do&,&for&,...,NULL};
2.4.1 数组的内存布局与定位
若要计算pea[i][j], 则是要先找到pea[i]的位置，再根据偏移量取得字符，因而pea[i][j]解析为：
*(*(pea+i)+j)。 如下图：
2.4.2 多维数组作为参数是如何传递的
当多维数组作为参数时，数组作为实参总是被改写对应指针的形式的，实参和形参关系如下：
数组的数组char c[8][10]
数组指针char (*)[10]
指针数组char *c[15]
指针的指针char **c
数组指针(行指针)char (*c)[64]
数组指针char (*)[64],不改变
指针的指针char **c
指针的指针char **c，不改变
所以在main函数中看到char **argv这样的参数，是因为argv是个指针数组char *argv[]，这个表达式被编译器改写为指向数组第一个元素的指针，即指向指针的指针。事实上如果argv参数被声明为数组的数组，将会改写为char (*)[len]而不是char **argv
2.5 指针的运算
例如二维数组int a[4][5]，它的指针运算说明如下(一定要明确对应形式的类型，它指向的是什么，才能知道它自增运算跳过的字节大小)
int (*)[4][5]数组的首地址，&a+1将跳过整个数组
int (*)[5]数组指针类型，指向第i个数组的指针
int *类型 ,它表示a[i]
*(*(a+i)+j)
int类型 ，它表示a[i][j]
在这里需要注意，数组下标可以使用负号，如：
cp[-1]=*(cp-1);
cpp[-1][-1]=*(*(cp-1)-1);
2.6 数组和指针的异同点
指针的特点：
保存数据的地址，间接访问数据，首先取得指针的内容，把它当做地址，加上偏移量作为新地址提取数据
通常用于动态数据结构，如malloc、free，用于指向匿名数据（指针操作匿名内存）
可用下标形式访问指针，一般都是指针作为函数参数，但你要明确实际传递给函数的是一个数组
数组的特点：
直接保存数据，以数组名+偏移量访问数据
通常用于固定数目的元素
数组作为函数参数会当做指针看待
另外从变量在内存的位置来说:
数组要么在静态存储区被创建，如全局数组，要么在用户栈中被创建。
数组名对应着一块内存(而非指向)，其地址与容量在生命期内保持不变，只有其内容可以改变。
指针可以随时指向任意类型的内存块，所以我们常用指针来操作动态分配的内存，但使用起来也容易出错
下面以字符串为例比较指针与数组的特性，程序为test.c:
#include &stdio.h&
#include &stdlib.h&
void ex1(){
char a[]=&hello&;// 字符数组,a的内容可变,如a[0]='X'
a[0]='X';
printf(&%c\n&,*a);
char *p=&world&; //指针p指向常量字符串&world\0&(存储于静态存储区),内容不可以被修改
p[0]='X'; //编译时尚不能发现错误,在运行时发现该语句企图修改常量字符串内容而导致运行错误
printf(&%s\n&,p);
void ex2(){
/* 数组与数组内容复制与比较 */
char a[]=&hello&;
char b[10];
strcpy(b,a); //数组与数组的复制不能用b=a,否则产生编译错误
if(strcmp(b,a)==0) //数组与数组内容的比较同样不能用b=a
printf(&内容相同\n&);
/* 数组与指针内容复制与比较 */
int len=strlen(a);
char *p=(char *)malloc(sizeof(char)*(len+1));
strcpy(p,a); //复制不能用p=a,否则产生编译错误
if(strcmp(p,a)==0) //数组与数组内容的比较同样不能用p=a,用p=a比较的是地址
printf(&内容相同\n&);
int main()
可以了解到常量字符串的内容是不可以被修改的，而字符数组的内容是可以被修改的；并且如果想要复制或比较数组内容，不能简单用b=a或b==a等来判断，需要使用如程序里所描述的strcpy和strcmp函数
注意也有例外, 就是把数组当做一个整体来考虑，而对数组的引用不能作为指向该数组第一个元素的指针来代替，看参见介绍中程序arr.c的执行结果：
数组作为sizeof的操作数，显示要求的是整个数组的大小，但注意当数组作为函数形参时，自动退化为指针，在函数内部计算sizeof,结果只是计算指针类型的大小，这一般与机器字长有关，两者并不矛盾。通常可以在头文件定义一个宏语句：#define TABLESIZE(arr) (sizeof(arr)/sizeof(arr[0]))
使用&获取字符数组的地址
3 实现动态数组
当我们想周期性地聚合一堆数据时，我们需要一个数组，并且这个长度是不确定的，可以动态增长。C++的vector便满足这个需求，那么对于C来说呢？一般来说C语言中的数组是静态数组，它的长度在编译期就确定了。如果你预先不知道数组的长度，想在程序运行的时候根据需要动态扩充数组的大小，这里可以设计一个动态数组的ADT。
它的基本思路是使用如malloc/free等内存分配函数得到一个指向一大块内存的指针，以数组的方式引用这块内存或者直接调用动态数组的接口，根据其内部的实现机制自行扩充空间，动态增长并能快速地清空数组，对数据进行排序和遍历。
3.1 动态数组的结构和接口定义
动态数组的数据结构定义如下：
* 动态数组的结构定义
指向一块连续内存的指针；type_size: 元素类型的大小(动态执行时才能确定类型)
* capacity: 动态数组的容量大小，最大可用空间
* index: 动态数组的实际大小
* int (*comp)(const void *,const void *): 元素的大小比较函数
typedef struct {
int (*comp)(const void *,const void *);
} array_t;
动态数组常见的接口函数设计：
/*为动态数组分配内存*/
array_t *array_alloc(int capacity,int type_size,int (*comp)(const void *,const void *));
/*为动态数组分配默认容量大小的内存*/
array_t *array_alloc_default(int type_size,int (*comp)(const void *,const void *));
/*释放动态数组的内存*/
void array_free(array_t *arr);
/*判断数组是否为空*/
bool array_empty(array_t *arr);
/*返回数组存储的元素个数*/
int array_size(array_t *arr);
/*借助函数指针遍历数组中每个元素*/
void array_foreach(array_t *arr, void (*visit)(void *elt));
* 插入一个元素，根据实际空间决定是否扩充或缩减容量
* 默认范围内，保持不变；超过默认容量，则扩充
void array_push(array_t *arr,void *elt);
/*把尾部元素拿掉*/
void *array_pop(array_t *arr);
/*成功找到pos位置上的元素，否则返回NULL*/
void *array_get(array_t *arr, int pos);
/*把位置pos上的内容设置成item对应的内容*/
void array_set(array_t *arr,void *item,int pos);
/*动态数组排序*/
void array_sort(array_t *arr);
3.2 动态数组的实现
具体代码如下：
dynarr.h :
#ifndef _DYNARR_H_
#define _DYNARR_H_
#include &stdbool.h&
#define DEFAULT_CAPACITY 16
* 动态数组的结构定义
指向一块连续内存的指针；type_size: 元素类型的大小(动态执行时才能确定类型)
* capacity: 动态数组的容量大小，最大可用空间
* index: 动态数组的实际大小
* int (*comp)(const void *,const void *): 元素的大小比较函数
typedef struct {
int (*comp)(const void *,const void *);
} array_t;
/*为动态数组分配内存*/
array_t *array_alloc(int capacity,int type_size,int (*comp)(const void *,const void *));
/*为动态数组分配默认容量大小的内存*/
array_t *array_alloc_default(int type_size,int (*comp)(const void *,const void *));
/*释放动态数组的内存*/
void array_free(array_t *arr);
bool array_empty(array_t *arr);
bool array_full(array_t *arr);
int array_size(array_t *arr);
void array_foreach(array_t *arr, void (*visit)(void *elt));
* 插入一个元素，根据实际空间决定是否扩充或缩减容量
* 默认范围内，保持不变；超过默认容量，则扩充
void array_push(array_t *arr,void *elt);
/*把尾部元素拿掉*/
void *array_pop(array_t *arr);
/*成功找到pos位置上的元素，否则返回NULL*/
void *array_get(array_t *arr, int pos);
/*把位置pos上的内容设置成item对应的内容*/
void array_set(array_t *arr,void *item,int pos);
/*动态数组排序*/
void array_sort(array_t *arr);
dynarr.c :
#include &dynarr.h&
#include &stdio.h&
#include &stdlib.h&
#include &string.h&
/*为动态数组分配内存*/
array_t *array_alloc(int capacity,int type_size,int (*comp)(const void *,const void *)){
array_t *arr=malloc(sizeof(array_t));
arr-&data=malloc(capacity*type_size);
arr-&capacity=
arr-&index=0;
arr-&type_size=type_
arr-&comp=
/*为动态数组分配默认容量大小的内存*/
array_t *array_alloc_default(int type_size,int (*comp)(const void *,const void *)){
return array_alloc(DEFAULT_CAPACITY,type_size,comp);
/*释放动态数组的内存*/
void array_free(array_t *arr){
free(arr-&data);
free(arr);
bool array_empty(array_t *arr){
return (arr-&index==0)?true:
bool array_full(array_t *arr){
return (arr-&index==arr-&capacity)?true:
int array_size(array_t *arr){
return arr-&
void array_foreach(array_t *arr, void (*visit)(void *elt)){
for(int i=0;i&arr-&i++){
void *elt=(char *)arr-&data+i*arr-&type_
visit(elt);
printf(&\n&);
/****************辅助函数**********************/
/*使用字节流从src复制size个字节到dst位置上*/
void copy(void *dst,void *src,int size){
char *buf=malloc(size);
memcpy(buf,src,size);
memcpy(dst,buf,size);
free(buf);
/*使用字节流交换v1和v2的size个字节大小*/
void swap(void *v1,void *v2,int size){
char *buf=malloc(size);
memcpy(buf,v1,size);
memcpy(v1,v2,size);
memcpy(v2,buf,size);
free(buf);
void exchange(array_t *arr,int i,int j){
void *v1=(char *)arr-&data+i*arr-&type_
void *v2=(char *)arr-&data+j*arr-&type_
swap(v1,v2,arr-&type_size);
int compare(array_t *arr,int i,int j){
void *v1=(char *)arr-&data+i*arr-&type_
void *v2=(char *)arr-&data+j*arr-&type_
return (arr-&comp)(v1,v2);
void array_qsort(array_t *arr,int left,int right){
if(left&right) {
int last=left,i;
exchange(arr,left,(left+right)/2);
for(i=left+1;i&=i++){
if(compare(arr,i,left)&0){
exchange(arr,++last,i);
exchange(arr,left,last);
array_qsort(arr,left,last-1);
array_qsort(arr,last+1,right);
/*******************************************/
* 插入一个元素，根据实际空间决定是否扩充或缩减容量
* 默认范围内，保持不变；超过容量，则扩充
void array_push(array_t *arr,void *elt){
if(array_full(arr)){
/*实现复制函数*/
void *new_data=malloc(arr-&type_size*arr-&capacity*2);
for(int i=0;i& arr-&i++){
src=(char *)arr-&data + i*arr-&type_
dst=(char *)new_data + i*arr-&type_
copy(dst,src,arr-&type_size);
free(arr-&data);
arr-&data=new_
arr-&capacity *=2;
/*使用realloc函数*/
// arr-&capacity *=2;
// arr-&data=realloc(arr-&data,arr-&type_size*arr-&capacity);
void *new_elt=(char *)arr-&data + arr-&index * arr-&type_
copy(new_elt,elt,arr-&type_size);
arr-&index++;
/*把尾部元素拿掉*/
void *array_pop(array_t *arr){
void *elt=(char *)arr-&data+arr-&index*arr-&type_
* 成功找到pos位置上的元素，否则返回NULL
* 注意: 如果查找函数，需要定义元素大小的比较函数int (*comp)(const void *,const void *)
void *array_get(array_t *arr, int pos){
if(pos&0||pos&=arr-&index){
printf(&Invalid position\n&);
return NULL;
void *elt=(char *)arr-&data+pos*arr-&type_
/*把位置pos上的内容设置成item对应的内容*/
void array_set(array_t *arr,void *elt,int pos){
if(pos&0||pos&=arr-&index){
printf(&Invalid position\n&);
void *new_elt=(char *)arr-&data+pos*arr-&type_
copy(new_elt,elt,arr-&type_size);
/*动态数组排序*/
void array_sort(array_t *arr){
array_qsort(arr,0,arr-&index-1);
阅读(...) 评论()