数据结构与算法

指针学习笔记

Posted by Leo on 2023-10-09
Estimated Reading Time 11 Minutes
Words 2.7k In Total

笔记来源

【强烈推荐】4小时彻底掌握C指针 - 顶尖程序员图文讲解 - UP主翻译校对 (已完结)_哔哩哔哩_bilibili

Introduction to pointers in C

  • 计算机在定义一个变量时，在Memory (RAM) 中划出一片地址空间来存储，并在一个查找表中添加一条记录，如int a;存储为（a int 0x204），通过地址来访问变量，其中int占4个字节；char占1个字节；float占4个字节；指针的长度取决于操作系统位数，如64位操作系统，指针长度是8

  • 指针是一个变量，存放着另外一个变量的地址，值得注意的是指针是一个变量！！

    p是一个整数型的指针（指向整数），通过改变p的值，我们可以通过p访问到不同的变量

    image-20231008145925162

  • 指针的定义

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int a;	// 定义了一个整数变量，分配了0x204的地址
    int *p;	// 定义了一个整数型的指针，分配了0x64的地址
    p = &a;	// 将p的值赋为0x208，指向了a

    print p	    // 204
    print &a	// 204
    print &p	// 64
    print *p	// 4
    // *p：解引用(dereferencing)，与&操作相反
    *p = 5	// a的值变成了5

    p -> address

    *p -> value at address

Working with pointers

  • Null指针，空指针的出现可能导致程序崩溃

    1
    2
    3
    4
    5
    6
    7
    # include<stdio.h>
    int main()
    {
    	int a; 
    	int *p;
    	printf("%d\n", p);
    }

  • 赋值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # include<stdio.h>
    int main()
    {
    	int a = 10; int b = 5;
    	int *p;
    	p = &a;
    	printf("%d\n", p);
    	*p = b;	// 不会改变p的值，p仍然指向a
    }

  • Pointer arithmetic

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # include<stdio.h>
    int main()
    {
    	int a = 10;
    	int *p;
    	p = &a;
    	printf("%d\n", p);		// 0x204
    	printf("%d\n", p+1);	// 0x208
    	// p是一个指向整型类型的指针，对其+1操作会得到下一个整型数据的地址
    	printf("%d\n", *(p+1));	// 指针越界，得到的是随机值
    }

Pointer types, void pointer, pointer arithmetic

  • 指针是强类型的，需要用特定类型的指针变量来存放特定类型变量的地址，那么既然指针仅仅存放着一个地址，为什么要分不同类型呢？答案是指针需要dereference，不同数据有不同的大小

  • 如果打印p的值，应该是200，即首地址，取a的值时，计算机根据数据类型选择要取的地址范围

    image-20231008161119975

  • 代码实例：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    # include<stdio.h>
    int main()
    {
        int a = 1025;
    	int *p;
    	p = &a;
    	printf("size of integer is %d bytes\n", sizeof(int));
    	printf("Address = %d, value = %d\n", p, *p);
        printf("Address = %d, value = %d\n", p+1, *(p+1));
        char *p0;
        p0 = (char*)p;	// 做一次typecasting
        printf("size of char is %d bytes\n", sizeof(char));
        printf("Address = %d, value = %d\n", p0, *p0);
    	printf("Address = %d, value = %d\n", p0+1, *(p0+1));
    }

    Output:
    size of integer is 4 bytes
    Address = 6422028, value = 1025
    Address = 6422032, value = 7372304
    size of char is 1 bytes
    Address = 6422028, value = 1
    Address = 6422029, value = 4
    // 1025 = 00000000 00000000 00000100 00000001

  • 通用指针

    1
    2
    3
    void* p0;
    p0 = p;
    printf("Address = %d, value = %d\n", p0, *p0);	// 只能打印地址，不能dereference

Pointer to pointer

image-20231008171912319 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# include<stdio.h>
int main()
{
    int x = 5;
    int *p = &x;
    int **q = &p;
    int ***r = &q;
    printf("%d\n", *p);
    printf("%d\n", *q);
    printf("%d\n", *r);
    
    printf("\n----following is dereference of x----\n");
    printf("%d\n", *p);
    printf("%d\n", **q);
    printf("%d\n", ***r);
    ***r = **q + *p + 1;
    printf("x = %d\n", x);
}

Outputs:
5
6422036
6422024

----following is dereference of x----
5
5
5
x = 11

Pointers as function arguments / Call by reference

  • 指针的一个用处是用于函数传值，下面的传值只传了值，没有传参数（形参&实参）

    1
    2
    3
    4
    void increase(int a)
    {
    	a = a + 1;
    }
    image-20231008173512179

    一个程序的内存空间分为以上四个部分，Code是程序的指令语句，Static/Global是分配给程序的静态/全局变量，Stack是分配给函数调用的局部变量和参数等，Heap是动态分配内存的区域；在函数调用栈中，函数只能访问自己栈帧中的局部变量

    1
    2
    3
    4
    5
    6
    // 正确的如下
    void increase(int* p)
    {
    	*p = *p + 1;
    }
    increase(&a);

Pointers and Arrays

  • 数字首元素的地址称为数组的基地址

    1
    2
    3
    4
    5
    6
    int A[5];
    int* p;
    p = A;

    Address -> &A[i] or A+i
    Value -> A[i] or *(A+i)

  • A 和 &A[0]的值相同，都是数组基地址，可以理解成数组就是指针

Arrays as function arguments

  • 编译器在编译时，只复制了数组的基地址到一个定义的同名指针中，而不是传递整个数组的空间，隐式地将sum()函数的参数int A[]变成了int* A，这节省了调用的函数栈帧的空间大小，是编译器做的优化（传引用，而不是传值）

    image-20231008203117862 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 传了同一数组，为什么长度算出来不一样？
    // 因为一个是数组，一个是指针
    # include<stdio.h>

    int sum(int A[])	// or int* A
    {
        printf("sum :%d %d\n", sizeof(A), sizeof(A[0]));
    }
    int main()
    {
        int A[] = {1,2,3,4,5};
        int size = sizeof(A)/sizeof(A[0]);
        sum(A);
        printf("main :%d %d\n", sizeof(A), sizeof(A[0]));
    }

    Outputs:
    sum :8 4
    main :20 4

Character arrays and pointers

  • 字符串就是字符数组，以'\0'作为结尾

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # include<stdio.h>
    int main()
    {
        char A[3];
        A[0] = 'L';
        A[1] = 'e';
        A[2] = 'o';
        // A[3] = '\0';

        printf("%s", A);
    }

    Leo饈r，取消注释的结果是Leo，没有多余的乱码

    字符数组实际上也是一个指针，不能直接对指针赋值

    1
    2
    3
    4
    5
    // 定义字符数组时，可以
    char A[20] = "Leo";
    // 但是不可以
    char A[20];
    A = "Leo";

  • 一个示例理解数组和指针的区别，这里print()函数的参数C可以自增，因为在编译器看来，它就是一个指针

    image-20231008210459135 
  • char C[20] = "Hello";	// string gets stored in the space for array
char* C = "Hello";		// string gets stored as compile time constant，即应用程序代码区

C[0] = 'A';		// 常量不能被修改，程序会崩溃

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18



    ## Pointers and multi-dimensional arrays

    ## Pointers and dynamic memory

    - 分配给栈的内存空间在程序运行期间不会增加，当产生过多的函数调用，如：无穷的递归等，可能会发生栈溢出的情况（stack overflow），而程序的堆的大小不是固定的，堆就是空闲的内存池，C语言中使用malloc、calloc、realloc和free四个函数使用堆，C++添加了new和delete两个函数

    - malloc()：malloc的参数是要在堆中申请的内存空间的大小，返回一个void pointer，通过cast可以变成指定数据类型的指针；使用堆上内存的唯一方式就是**reference**

      ```c
      int* p;
      p = (int*)malloc(sizeof(int));	// 这样就在堆中有了一块内存，可以存放一个整型
      *p = 10;
      free(p);
      p = (int*)malloc(sizeof(int));
      *p = 20;	// 原来的内存在函数调用结束后不会被释放（像栈那样），造成了“内存泄漏”！要使用free()释放内存

malloc、calloc、realloc、free

  • malloc：对malloc返回指针先进行类型转换，之后可以使用*(p+1)或者p[1]来写入堆

    使用malloc之后最好用memset( p , 0x00 , sizeof(p) )初始化一下，养成良好的习惯

  • calloc：malloc(3*sizeof(int))写成calloc(3, sizeof(int))，calloc函数会进行初始化，而malloc不会

  • realloc：已经申请了一块动态内存，希望改变大小，使用realloc函数，函数原型为void* realloc(void* Ptr, size_t size)

Memory leak

  • 以赌博游戏为例，如果在play函数中char c[3] = {'J', 'Q', 'K'};这样定义数组，数组存储在函数栈帧中，每一次调用play函数后，都会清空栈帧，所以在程序运行过程中，占用的内存不会明显增长
  • 如果char *c = (char*)malloc(3*sizeof(char));这样定义数组，每一次调用play函数，都在堆中申请了一块内存，函数栈帧中只有一个指向这块内存的指针，如果不调用free函数释放，在程序运行过程中，占用的内存会不断增长，Java等语言已经有内存回收机制，而C/C++程序员要格外小心

Pointers as function returns

  • 从栈顶向下传递局部变量或局部变量的地址（指针）是不被允许的，因为栈顶的空间先被释放，可能会被其他函数覆盖，而从栈底向上传递局部变量或局部变量的地址（指针）是可以的

    image-20231008221924880

    sum函数结果会出错，被PrintHelloWorld函数覆盖

  • 函数调用可以返回指针的情况：在堆上有内存地址（释放内存）或全局变量区上有变量时，如：

    image-20231008222222631

Function Pointers

  • 一个函数就是一组存储在连续内存块中的指令，函数的地址称为函数的入口点，是函数第一条指令的地址，函数调用是一条跳转指令跳转到函数的入口点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # include<stdio.h>

    int Add(int a, int b)
    {
        return a+b;
    }

    int main()
    {
        int c;
        int (*p)(int, int);	// (*p)不加括号就变成了返回指针的函数的声明
        p = &Add;	// 也可以写成 p = Add; 就像数组一样
        c = (*p)(2, 3);	// 解引用得到函数，并传参执行,也可以直接写成 c = p(2, 3);
        printf("%d", c);
    }

Function pointers and Callbacks

  • 函数指针可以作为函数的参数，接受这个函数指针参数的函数可以回调指针指向的函数

  • 代码示例：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # include<stdio.h>

    void A()
    {
        printf("hello!");
    }

    void B(void (*ptr)())
    {
        ptr();  // call-back function that "ptr" points to
    }

    void main()
    {
        void (*p)();
        p = A;
        B(p);
        
        B(A); // 也是可以的，因为函数名就是指针
    }

  • 在数组排序中，升序和降序的代码十分相近，为了减少冗余代码，提出了传入比较函数的做法，qsort 是C语言中的一个标准库函数，用于对数组进行快速排序。它位于 <stdlib.h> 头文件中，其函数原型如下

    1
    2
    3
    void qsort(void* base, size_t num, size_t size,
               int (*compar)(const void*, const void*));
    // base 是待排序数组的起始地址，num 是数组中元素的个数，size 是每个元素的大小（以字节为单位），compar 是比较函数指针

    比较函数（compar）是用户自定义的函数，必须满足以下规则：

    • 如果第一个参数小于第二个参数，则返回负值
    • 如果第一个参数等于第二个参数，则返回0
    • 如果第一个参数大于第二个参数，则返回正值

    比较函数的使用就是一个回调函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # include<stdio.h>
    # include<stdlib.h>

    int compare(const void* a, const void* b)
    {
        int A = *((int*)a);
        int B = *((int*)b);
        return A-B;		// 改成 B-A 就成了降序
    }

    void main()
    {
        int i;
        int A[] = {-31, 22, -1, 50, -6, 4};
        qsort(A, 6, sizeof(int), compare);
        for(int i=0; i<6; i++) printf("%d ", A[i]);
    }

    Outputs:
    -31 -6 -1 4 22 50

本着互联网开源的性质，欢迎分享这篇文章，以帮助到更多的人，谢谢！

FRIENDS
ESC