指针

数据在内存中的存储

这是一段内存，他被分成了许多段，每段一个byte

当我们声明一个变量int a，计算机会给该变量分配一块空间，分配取决于数据类型与编译器

如：int 与float占4bytes，char占1bytes

当我们给变量a赋值a=5，计算机会去寻找该变量，去到他的地址，以二进制写入数据

指针的基础使用

指针是一种变量，它可以存储变量的地址

使用数据类型* 变量名创建一个指针：int *p char *c

使用取地址符&获取一个变量的地址，并可以将指针指向该变量地址：p=&a

print p，print &a，print &p分别对应打印p指向(a)的地址，a的地址，p的地址

将一个*放在指针变量前，可以对指针进行解引用，即获取p指向地址的值

则print *p会返回a的值，*p = 8会更改a的值到8

实例代码：

#include<stdio.h>
int main(){
    int a=5;
    int* p;  // 若该指针p没有被初始化，p会变成一个野指针，会因为指向任意位置而报错
    p = &a;  // 储存a的地址
    // 上两行等同于int* p = &a;
    printf("A:%d\n",p); // a的地址
    printf("V:%d\n",*p); // a的值
    printf("A:%d\n",&a); // a的地址

    *p = 12; // 更改p指向地址(a)的元素值
    printf("A:%d\n",a); // 更改后的a值

    int b = 20;
    *p = b; // p不会指向b，只会将b的值赋给a
    printf("A:%d\n",p); // 还是a的地址
    printf("V:%d\n",*p); // b的值

    return 0;
}

指针类型

不同的数据类型占据不同的内存：

int：4bytes

char：1byte

float：4bytes

void指针：

可以存放任意类型的指针，且无需强制类型转换
需要进行显式转换后才能赋值给其他类型
可以与其他类型指针直接比较地址值
只有强制类型转换后才能操作（解引用、算术运算等）
可以和普通指针一样传入NULL或nullptr表示空指针
作为函数输入输出时，表示可以接受任意类型和输出任意类型的指针

指针类型间的转换

定义一个变量int a=1025：

他在内存中的布局为（从右到左分别为第0 1 2 3个字节，他们的地址也是连续的）：

其中，最左边的一位为符号位，0为整数1为负数

若我们定义一个字符指针c指向a，由于字符只占一个字节，故c只会指向a的第一个字节：

对c进行算术运算(+1)会让他指向下一个字节以至于得到4

#include <stdio.h>
int main(){
  // 一个整形指针
  int a = 1025; // 在二进制中为四字节:00000000 00000000 00000100 00000001
  int* p;
  p = &a;
  printf("size of integer is %d\n", sizeof(int));
  printf("Address = %d, value = %d\n",p,*p);

  // 一个字符指针
  char *c;
  c = (char*)p; // 进行强制类型转换
  printf("size of integer is %d\n", sizeof(char));
  // 由于char指针只有一个字节,则机器只看从右边开始的一个字节 即00000001
  printf("Address = %d, value = %d\n",c,*c);
  // 增加一个字节,则指针指向从右边开始的第一个字节 即00000100
  printf("Address = %d, value = %d\n",c+1,*(c+1));

  // 一个void指针
  void *p0;
  p0 = p;  // 不需要显式的类型转换
  // 当p0没指向任何特定类型时,不能解引用
  printf("Address = %d, value = %d\n",p0,*p0);
  // 也不要进行算术运算
  printf("Address = %d %d\n",p0,p0+1);
}

指针算术运算

对一个指针进行加1操作，相当于将该指针增加一个该指针数据类型所占字节数的字节数

例如对int *p=&a; p++;得到p的值为a的地址加4

#include <stdio.h>
int main(){
  int a = 10;
  int *p;
  p = &a;
  // 指针加法 : +1代表增加一个数据类型的字节数
  printf("Address p is %d\n",p); // p的地址
  printf("Value at address p is %d\n",*p); // p指向的值
  printf("size of integer is %d bytes\n", sizeof(int)); // int类型所占的字节数
  printf("Address p+1 is %d\n",p+1); // p+1指向的地址
  printf("Value at address p+1 is %d\n",*(p+1)); // p+1指向的值(垃圾值)
}

指向指针的指针

假设定义了一个数据int x = 5;

我们定义一个指针指向x int *p = &x

此时我们可以再定义一个指针指向指针p int **q = &p

甚至还可以定义一个指针指向指针q int ***r = &q

(r是205)

示例代码

#include <stdio.h>
int main(){
  int x =5;
  int* p = &x;
  *p = 6;
  int** q = &p;
  int*** r = &q;
  printf("%d\n",*p); // p指向x的值
  printf("%d\n",*q); // q指向p的值(x的地址)
  printf("%d\n",*(*q)); // q指向p的值指向x的值
  printf("%d\n",*(*r)); // r指向q的值,q指向p的值
  printf("%d\n",*(*(*r))); // r指向q的值,q指向p的值,p指向x的值
  
  // 更改x的值
  ***r = 10;
  print("x = %d\n", x);

  // **q与*p都指向x的值,则相当于x自加2
  **q = *p +2;
  print("x = %d\n", x);
}

指针用例—函数传引用 or 传值？

e.g. 局部变量与全局变量：

有以下代码

#include <stdio.h>
void f(int x){
    x=x+1;
}
int main(){
    int x=10;
	f(x);
    printf("%d\n",x);
    return 0;
}

该代码中的函数想让变量+1，但输出的结果显然还是10，这是为什么呢？

看以下代码：

#include <stdio.h>
void f(int x){
    printf("Address of x in f is:%d\n",&x);
    x=x+1;
}
int main(){
    int x=10;
	  f(x);
    printf("Address of x in main is:%d\n",&x);
    return 0;
}

你会惊奇的发现，f函数中的x与main函数中的x的地址不一样，这也就说明了为什么+1不成立

当程序运行时，计算机会预留一部分内存给程序，他们被分为四个部分：栈、堆、数据区、代码区

栈：非静态局部变量（函数参数等）。栈是向下生长的
堆：用于动态内存分配。堆是向上生长的
数据区：存储全局变量和静态变量
代码区：可执行的代码与常量

当一个程序进行时，main函数被调用，关于这个函数的信息（如参数，局部变量，返回地址）会存在栈上，栈便为该函数开辟一块空间，称为栈帧(stack frame)，每个函数都会有一个栈帧

让一个函数调用另一个函数时，两个函数分别称为主调函数与被调函数，在主调函数中调用其他函数用到的参数称为实际参数，被调函数中的函数称为形式参数，实参会被映射到形参。这个操作即传值

当main函数调用f函数时，一块它的栈帧会被创建，其中的参数会被分配到对应空间，执行+1操作后，这个函数的栈帧中的变量执行了+1，但不影响其他地方的变量。

当f函数执行完毕，程序回到main函数，此时f的栈帧会被清除，main函数会被继续执行，故局部变量的生命周期只是函数执行期间。

接下来进行的函数是printf函数，这是一个库函数，在栈中创建它的栈帧并指型。这一个结构被称为(函数)调用栈，即：是将一个个函数的栈帧，按照调用的顺序依次压入栈中，等最上层的函数执行完了，就弹出相应的栈帧的过程

注意：栈是有大小的，如果因为无限递归等原因导致栈帧一直被创建而不清除，程序会因为栈溢出而终止

那传引用能否实现？

#include <stdio.h>
void f(int *p){
    *p = (*p)+1;
}
int main(){
    int a;
    a = 10;
    f(&a);
    printf("a = %d", a);
    return 0;
}

该函数传的是地址

当调用main函数，它的栈帧被创建，a=10进入栈。

调用f函数，它的栈帧被创建，则p接收到a的地址，入栈，此时p指向a。

在函数中解引用p，并执行操作，p指向的内存(a)的值就会增加，即a的值增加1

回到main函数，a的值就是11

这就是传引用，它可以节省很多内存空间，也可以处理一些复杂数据类型以节省内存

指针与数组

让我们声明一个数组 int a[5]

即我们创建了五个整型变量，在内存中连续存在(int 占四个字节)，则整个数组占的大小为20bytes，作为一个连续的块

我们定义一个指针int* p，将p指向a的第一个元素，则p解引用后打印的是a[0]的值

回忆之前说的指针算术，若我们将p+1，则p会往前移动四个字节，**此时*(p+1)即a[0]后四个字节的值，即a[1]**

与之前不同，一个值它的地址+1后会移动到一个未知内容的地址，而数组a中+1后p指向的值是已知的

若直接将数组名赋值给p，则p默认接收到的是数组a首元素的地址，称为数组的基地址

若想获得数组某个值的地址，可以使用&a[i]或者a+i

若想获得数组某个值，可以使用a[i]或者*(a+i)

注意：对数组名（常量）自加是非法的，可以定义一个指针指向数组名让该指针自加

实例代码：

#include <stdio.h>

int main(){
  int a[]={2,4,5,8,1};
  for (int i = 0;i<5;i++){
    printf("Address = %d\n",&a[i]);
    printf("Address = %d\n",a+i);
    printf("Value = %d\n",a[i]);
    printf("Value = %d\n", *(a+i));
  }
}

指针用例—数组传参

#include<stdio.h>
int suma(int a[],int size){
  int sum = 0;
  for (int i = 0;i<size;i++){
    sum+=a[i];
  }
  return sum;
}
int sumb(int a[]){
  int sum = 0;
  int size = sizeof(a)/sizeof(a[0]);
  printf("In sumb - size of a = %d, size of a[0] = %d\n",sizeof(a),sizeof(a[0]));
  for (int i = 0;i<size;i++){
    sum+=a[i];
  }
  return sum;
}
int main(){
  int a[]={1,2,3,4,5};
  // 计算数组大小
  printf("In main - size of a = %d, size of a[0] = %d\n",sizeof(a),sizeof(a[0]));
  int size = sizeof(a)/sizeof(a[0]);
  // 传入数组大小后进行加和
  int tot = suma(a,size);
  // 在函数中计算数组大小并加和
  int tot2 = sumb(a);
  printf("tot = %d\n", tot);
  printf("tot2 = %d\n", tot2);
}

以上代码会出现一些问题：

在调用main与sumb函数时，它们的栈帧会被创建

调用sumb函数时，编译器只会创建一个同名的指针在sumb的栈帧中，即它只指向main函数中数组a的首元素地址（即int a[]等同于int *a）

因此函数中的sizeof a是一个8字节的指针。

指针与字符数组

字符数组

C中的字符串存储在数组中，必须以’\0’结束

字符数组赋值：

可以指定每一位进行赋值，

或者使用字符串字面值（用双引号括起来的字符串）赋值，该方法会隐式地添加一个’\0’

或者使用大括号初始化每一位，以逗号间隔并在结尾加上’\0’

注意：只能在声明同时用字符串字面值赋值

使用指针

字符数组中数组名代表的是数组首元素的地址，可以用一个指针变量指向它，该变量也可以对字符数组进行操作

#include <stdio.h>
int main(){
    char c1[6]="Hello";
    char *c2;
    c2 = c1;
    c2[0]='A'; // equal to c1[0]='A';
    
    c2++; // 指向下一个元素
    c1++; // 非法
}

有等价关系：

c2[i]等同于*(c2+i) c1[i]等同于*(c1+i)

函数传参

#include<stdio.h>
void print(char *c){
  int i = 0;
  // while (c[i]!='\0'){ // *(c+i)也可以
  //   printf("%c",c[i]);
  //   i++;
  // }
  // 由于c是指针，故可以通过自增与解引用来进行访问
  while(*c!='\0'){
    printf("%c",*c);
    c++;
  }
  printf("\n");
}
int main(){
  char c[20] = "Hello";
  print(c);
  return 0;
}

指针与二维数组

如果我们要创建一个二维数组b[2][3]

此时，b[0]与b[1]表示三个整数的一维数组，在内存中占用3*4=12个字节，是按行存储的

故int *p=b;指代的是返回一个指向一维数组的指针，此时不能指针运算或解引用，故不能这么用

故应使用int (*p)[3]来创建一个二维指针数组，其中3表示三个指向一维数组的指针

这时print b or &b[0]都指代第一个元素的地址

print *b or b[0] or &b[0][0]都指代第一个元素地址的值

print b+1 or &b[1]会跳到下一个数组的首地址（+12）

使用print *(b+ 1)or b[i]or&b[1][0]指代下一个指向一维数组的并返回值

解引用时，需要一步步解

例 *(*b+1)

*b 为b[0]，一个一维数组的首元素地址，*b+1会让指针移动四个字节带到下一个整型变量，

相当于&b[0][1]

我们解引用后，*(*b+1)就相当于b[0][1]

指针运算：b[i][j]=*(b[i]+j)=*(*(b+i)+j)

指针与多维数组

原理

与二维数组类似

假如我们有一个int数组c[3][2][2]，在内存中的存储如下

简化为三个二维数组线性存储，每个二维数组内两个一维数组线性存储

故我们可以声明一个指针int (*p)[2][2] = c;，指向2*2的二维数组

这时print c，print *c，print c[0]，print &c[0][0]均输出第一个一维数组的地址

指针运算：c[i][j][k]=*(c[i][j]+k)=*(*(c[i]+j)+k)=*(*(*(c+i)+j)+k)

可以理解为解引用一次就脱一层[]

e.g.

print *(c[0][1]+1)指向的是c[0][1][1]

print *(c[1]+1)指向的是c[1][1]，即c[1][1][0]

用于函数传参

如一维数组传参，我们可以通过传值或传引用两种方法传参

注意：传值时除了最高维度，其他维度必须要指定偏移量（即形参定义时必须和传入数组长度一样）

int two_dim(int a[][3]){

}
int three_dim(int a[][2][2]){

}

而根据数组名就是指向第一个元素的指针，我们可以直接传引用来实现降维度

注意：只能降到次一级维度，且其余的必须指定偏移量

int two_dim(int (*a)[3]){

}
int three_dim(int (*a)[2][2]){

}

指针与动态内存

内存的分配

在一个典型架构中，分配给应用程序的内存分为四个区段：栈、堆、数据区、代码区

栈：非静态局部变量（函数参数等），函数调用信息。栈是向下生长的
堆：用于动态内存分配。堆是向上生长的
数据区：存储全局变量和静态变量
代码区：可执行的代码与常量

栈

当一个程序进行时，main函数被调用，关于这个函数的信息（如参数，局部变量，返回地址）会存在栈上，栈便为该函数开辟一块空间，称为栈帧(stack frame)，每个函数都会有一个栈帧，大小在编译期间决定

所有函数从下往上开辟栈帧后，在执行时总是栈顶的函数在执行，其余函数暂停，等待上方函数返回值等。当上方函数返回后，它占用栈的内存也会被清除，下一个函数运行。任何时候正在执行的函数都是栈顶的那个函数

预留给栈的空间在运行期间并不会增长，也不能请求更多内存。如果运行时的栈增长超过了程序预留的栈内存大小，那么会造成栈溢出(stack overflow)

因此栈有两个限制：

在栈上的变量无法操作骑作用域
当声明一个很大的数据类型，可能会造成溢出；且只能在编译时分配他的大小，无法在程序运行时分配它的大小

堆(动态内存)

这时我们需要用到堆来分配或销毁或内存。我们可以任意使用堆上的内存，只要不超过系统内存限制。

堆又称为动态内存，使用堆内存称为动态内存分配 (注意这里的堆并不是数据结构)

C风格：

#include <stdio.h>
#include <stdlib.h>
int main(){
  int a; // 分配到栈上
  int *p; // 指向堆内存的指针
  p = (int*)malloc(sizeof(int)); // 在堆上开辟一块四字节的内存，让指针p指向其地址
  *p=10; // 解引用将值存入堆
  free(p); // 释放内存
  p = (int*)malloc(20*sizeof(int)); // 在堆上再开辟一块20个四字节的内存作为数组，让指针p指向其首元素地址
  // 可以用以下两种方式访问
  p[0] = 1; 
  *(p+1) = 2;
}

定义一个指针变量p，它被存储在栈中，指向堆中分配的内存地址

通过malloc在堆上分配一块四字节的内存，malloc会返回一个指向这块内存起始地址的指针，void类型。故我们需要进行一个强制类型转换，并赋给指针变量p

使用堆上内存的唯一方式是通过引用，自己维护一个指针指向这块内存。我们通过对指针变量p解引用并赋值来使用。

若我们再以同样方式分配一块四字节内存，让p指向它，并赋值为20，p此时指向的便是堆中的另一块内存。而之前那块内存仍在堆上，并不会被自动回收，此时称为内存泄漏，因此我们需要在用完一块内存后，及时调用free()释放内存。

如果要分配一个数组内存，我们只需要传入数组大小字节数即可，返回的是内存的初始地址

若malloc无法在堆上成功分配内存，会返回NULL

C++风格：

#include <stdio.h>
#include <stdlib.h>

int main(){
  int a;
  int *p; // 指向堆内存的指针
  p = new int; // 在堆上开辟一块int大小的内存(四字节)
  *p = 10; // 解引用并赋值
  delete p; // 释放内存
  p = new int[20]; // 在堆上开辟一个20大小的int数组
  delete[] p; // 释放数组内存
}

c++中使用关键字new与delete开辟与释放内存，不需要类型转换

内存泄漏

当我们动态申请了内存后，忘记去释放，此时程序占用了一些未使用的内存，称为内存泄露

对于栈：由于栈帧在使用完后会被自动销毁，故不会发生内存泄漏

对于堆：在开辟空间后，堆上的内存必须要被显式地释放掉，否则会一直存在

注意：任何未使用和未引用的堆上内存都是垃圾，程序员要确保不要浪费内存

函数返回指针

我们可以在函数类型处加上*来声明函数返回值是一个指针。

注意以下情况：

#include <stdio.h>
#include <stdlib.h>
// 现在该函数返回的是一个int类型的指针，即c的地址
void print(){
  printf("hello world");
}
int* add(int* a,int* b){
  int c = (*a)+(*b);
  return &c;
}
int main(){
  int x = 2,y=4;
  int* p =add(&x,&y);
  print();
  printf("sum=%d",*p);

}

该程序对print的输出正常，而输出sum时出现了异常，从底层原理分析：

执行main函数，开辟栈帧，执行add函数，在main函数上再开辟栈帧，main函数会等待add返回

此时add中a与b存储了main函数中x与y的地址，c存储了*a与*b的和，返回的是c的地址，故main函数中的p指针存储的是c的地址

add执行完毕，占用空间被清除。但注意，此时p指向的内存仍未变化，即此时它指向了被释放掉的内存空间，值是随机的

现在执行print函数，开辟栈帧，原空间被覆盖，因此p存储的地址对应的值已经不是c的值了，因此输出异常。

还有一种情况：若不执行print函数，输出的值可能会正确。因为此时程序还没重写或清除那个空间上的数据（虽然已经释放空间）

而对于main与add函数，由于被调函数的栈空间总是在主调函数之上，因此被调函数执行时主调函数仍在栈内存中，因此add可以访问main函数中的变量。但若我们想要返回被调函数的一个局部变量给主调函数，当被调函数结束后，内存已被释放，因此会出问题。

因此可以从栈底向上传局部变量或局部变量的地址，但不能从栈顶向下传局部变量或局部变量的地址

因此我们可以修改：

#include <stdio.h>
#include <stdlib.h>
// 现在该函数返回的是一个int类型的指针，即c的地址
void print(){
  printf("hello world");
}
int* add(int* a,int* b){
  int *c = (int*)malloc(sizeof(int)); // 在堆上开辟内存
  *c = (*a)+(*b);
  return c; // 返回的是堆上的指针
}
int main(){
  int x = 2,y=4;
  int* p =add(&x,&y);
  print();
  printf("sum=%d",*p);
}

我们将c开辟在堆上，此时就不会被清除了，返回c是安全的

函数指针

我们可以用指针指向函数地址，即指向函数的指针。我们可以用这种指针解引用和调用函数。

函数的地址

在内存中，一个函数就是一块连续的内存。

一般程序执行指令会按照地址依次执行，而函数调用可以让程序跳到某一个地址开始执行其中的指令。

此时对应的函数地址可以称为函数的入口点，即函数第一条指令的地址

函数指针的使用

#include <stdio.h>
#include <stdlib.h>
void print(char *name){
  printf("hello");
}
int add(int a, int b){
  return a+b;
}
int main(){
  int c;
  int (*p)(int,int); // 函数指针
  p = &add; // 指针指向add函数的地址(不用&也可)
  c = (*p)(2,3); // 解引用，并传入参数执行函数(不用解引用也行)
  printf("%d\n",c);
  void (*ptr)(char*);
  ptr = print; // 不用&的情况
  ptr("mixbp"); // 不用解引用的情况
}

由于单纯的函数名代表函数入口点，故不用&与解引用也可以

注意：为了指向一个函数，函数指针的类型必须是正确的

回调函数

将函数指针作为函数参数传入，并在函数内部通过该函数指针调用函数，被调用的函数即为回调函数

#include <stdio.h>
#include <stdlib.h>

void print(){
  printf("hello");
}
void b(void (*ptr)()){
  ptr(); // 用ptr回调传进来的函数
}

int main(){
  void (*p)() = print; // 定义一个指针指向print
  b(p); // 传入该函数指针
  b(print); // 这样也可以传
}

代码中，函数b可以通过函数指针来回调函数print

可以定义一个指向print函数的指针传入，也可以直接传入print，此时指代的是print函数的首地址

应用：排序

设计一个排序函数，并可以按照不同逻辑进行排序

我们可以在普通排序函数中添加一个函数指针参数(比较函数)，通过设计蚂蚁比较逻辑并传入排序函数，可以灵活实现不同情景的比较，而不用每次都根据不同逻辑重新写一遍排序函数

如实现正序、逆序、按绝对值排序

#include <stdio.h>
#include <math.h>
int compare(int a,int b){
  if (a>b) return 1;
  else return -1;
}
int r_compare(int a, int b){
  if (a>b) return -1;
  else return 1;
}
int abs_compare(int a, int b){
  if (abs(a)>abs(b)) return 1;
  else return -1;

}
void sort(int *a, int n, int (*cmp)(int,int)){
  int tep;
  for (int i = 0;i<n;i++){
    for (int j = 0;j<n-1;j++){
      if (cmp(a[j],a[j+1])>0){
        tep = a[j];
        a[j] = a[j+1];
        a[j+1]=tep;
      }
    }
  }
}
int main(){
  int a[]={3,2,1,5,6,4};
  int b[]={-2,-3,5,4,1,-6};
  sort(a,6,compare); // 正序排序
  for (int i = 0;i<6;i++) printf("%d ",a[i]);
  printf("\n");
  sort(a,6,r_compare); // 逆序排序
  for (int i = 0;i<6;i++) printf("%d ",a[i]);
  printf("\n");
  sort(b,6,abs_compare); // 绝对值排序
  for (int i = 0;i<6;i++) printf("%d ",b[i]);
  printf("\n");

}

同样的逻辑，在c的stdlib.h库中有一个qsort函数，只要给予它排序逻辑并传入就可以对任意数组排序

指针

数据在内存中的存储

指针的基础使用

实例代码：

指针类型

指针类型间的转换

指针算术运算

指向指针的指针

示例代码

指针用例—函数传引用 or 传值？

e.g. 局部变量与全局变量：

那传引用能否实现？

指针与数组

实例代码：

指针用例—数组传参

指针与字符数组

字符数组

使用指针

函数传参

指针与二维数组

指针与多维数组

原理

用于函数传参

指针与动态内存

内存的分配

栈

堆(动态内存)

C风格：

C++风格：

相关函数

malloc

calloc

realloc

内存泄漏

函数返回指针

函数指针

函数的地址

函数指针的使用

回调函数

应用：排序