登录以参加训练计划

四，指针与数组

1、指针与数组的关系

指向数组的指针变量称为数组指针变量。一个数组是一块连续的内存单元组成的，数组名就是这块连续内存单元的首地址。一个数组元素的首地址就是指它所占有的几个内存单元的首地址。

一个指针变量既可以指向一个数组，也可以指向一个数组元素，可把数组名或第一个元素的地址赋予它。如要使指针变量指向第i号元素,可以把元素的首地址赋予它,或把数组名加i赋予它。

设有数组a，指向a的指针变量为pa,则有以下关系:

• pa、a、&a[0]均指向同一单元，是数组a的首地址,也是0号元素a[0]的首地址。
• pa+1、a+1、&a[1]均指向1号元素a[1]。
• 类推可知 pa+i、a+i、&a[i]指向i号元素a[i]。

pa是变量,而a、&a[i]是常量，在编程时应予以注意。

2、指向数组的指针

数组指针变量说明的一般形式为:

类型说明符 *指针变量名

其中类型说明符表示所指数组的类型,从一般形式可以看出,指向数组的指针变量和指向普通变量的指针变量的声明是相同的。

引入指针变量后,就可以用两种方法访问数组元素了，

例如定义了 int a[5]; int * pa=a;

第一种方法为下标法,即用pa[i]形式访问a的数组元素。 第二种方法为指针法,即采用*(pa+i)形式,用间接访问的方法来访问数组元素。

#include <cstdio>
using namespace std;

int main() {
    int a[5], i, *pa = a;  // 定义整型数组和指针, *pa=a 可以在下一行 pa=a;
    
    for (i = 0; i < 5; i++)
        scanf("%d", a + i);  // 可写成 pa+i 和 &a[i]
    
    for (i = 0; i < 5; i++)
        printf("a[%d] = %d\n", i, *(a + i));  // 指针访问数组, 可写成 *(pa+i) 或 pa[i] 或 a[i]
    
    return 0;
}

输入:12345 输出:[0]=1 a[1]=2 a[2]=3 a[3]=4 a[4]=5

[说明] 1，直接拿 a 当指针用，a 指向数组的开始元素，a + i 是指向数组的第 i 个元素的指针。

2, 指针变量 pa 是变量，可以变的，但是静态的变量名 a 不可变，只能当作常量。例如: p = p + 2; 是合法的，a = a + 2; 是非法的。

3,最早在使用标准输入 scanf 时就使用了指针技术，读入一个变量时要加取地址运算符 &。

3、指针也可以看成数组名

指针可以动态申请空间，如果一次申请多个变量空间，系统给的地址是连续的，就可以当成数组使用。这就是传说中的动态数组的一种。

例8.6 动态数组，计算前缀和数组。b数组 a 的前缀和的数组定义: b[i] = a[1] + a[2] + … + a[i]，即 b[i] 是 a 的前 i 个元素的和。

#include <cstdio>
using namespace std;

int n;
int *a;  // 定义指针变量a,后面直接当数组名使用

int main() {
    scanf("%d", &n);
    a = new int[n + 1];  // 向操作系统申请了连续的n+1个int型的空间
    
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    
    for (int i = 2; i <= n; i++)
        a[i] += a[i - 1];
    
    for (int i = 1; i <= n; i++)
        printf("%d ", a[i]);
    
    return 0;
}

输入:5 1 2 3 4 5 输出:1 3 6 10 15 [说明] 动态数组的优点: 在OI中，对于大数据可能超空间的情况是比较纠结的事，用小数组只得部分分，大数组可以爆空间（得0分）。使用“动态数组”，可以在确保小数据没问题的前提下，尽量满足大数据的需求。

五，指针与结构体

1、结构体指针的定义与使用

当一个指针变量用来指向一个结构体变量时，称之为结构体指针变量。结构体指针变量的值是所指向的结构体变量的起始地址，通过结构体指针即可访问该结构体变量，这与数组指针和函数指针的情况是相同的。

结构体指针变量定义的一般形式为：

结构体名 *结构体指针变量名;

当然也可以在定义结构体的同时定义这个结构体指针变量，例如，定义一个结构体（类型为自己定义的student）指针变量p：

struct student {
    char name[20];
    char sex;
    float score;
} *p;

或分开定义：

struct student {
    char name[20];
    char sex;
    float score;
};
student *p;

与前面讨论的各类指针变量相同，结构体指针变量也必须先赋值后才能使用。赋值是把结构体变量的首地址赋予该指针变量，不能把结构名赋予该指针变量。例如：如果p是被定义为student类型的结构体指针变量，boy是被定义为student类型的结构体变量，则p = &boy;是正确的，而p = &student;是错误的。 引用结构体指针变量指向的结构体变量的成员的方法如下：

• 指针名->成员名
• (*指针名).成员名 例如：

(*p).score 与 p->score 是等价的。

结构体指针应用举列：

#include <stdio.h>
using namespace std;

struct student {
    char name[20];
    char sex;
    float score;
};

int main() {
    struct student boy = {"ZhangSan", 'M', 90.5};
    student *p = &boy;

    printf("Name: %s\n", p->name);
    printf("Sex: %c\n", p->sex);
    printf("Score: %.2f\n", p->score);

    return 0;
}

2、自引用结构

在一个结构体内部包含一个类型为该结构体本身的成员是否合法呢？

struct stu {
    char name[20];
    int age, score;
    stu p; // 这种类型的自引用是非法的
};

这种类型的自引用是非法的，因为成员p是另一个完整的结构，其内部还将包含它自己的成员p。这第二个成员又是一个完整的结构，它还将包含自己的成员p，如此重复下去就永无止境了。这有点像永远不会终止的递归程序。

但是，下面这个程序是合法的：

struct stu {
    char name[20];
    int age, score;
    stu *p; // 使用指针的方式进行自引用是合法的
};

这个声明和前面那个声明的区别在于p现在是一个指针而不是结构体。编译器在结构体的长度确定之前就已经知道指针的长度，所以这种类型的自引用是合法的。

当一个结构体中有一个或多个成员是指针，它们所指向的类型是本结构体类型时，通常这种结构体称为“引用自身的结构体”，即“自引用结构”。这种自引用结构是实现其他一些结构的基础。

自引用结构在动态数据结构中有重要作用，甚至可以说，自引用结构是C/C++语言实现动态数据结构的基石，包括动态的链表、堆、线段树等，无不是自引用结构的具体实现。

例如，下面的定义就可以在实际操作中建立起一个链表：

struct node {
    int x, y;
    node *next;
};

在下一节将对链表结构进行深入的研究。