uu们，这是C++最后一篇啦，属于拓展噢，接下来会写C++语言的数据结构哦

 一.内存和地址

在讲内存和地址之前，我们想有个生活中的案例： 假设有一栋宿舍楼，把你放在楼里，楼上有100个房间，但是房间没有编号，你的一个朋友来找你玩， 如果想找到你，就得挨个房子去找，这样效率很低，但是我们如果根据楼层和楼层的房间的情况，给每个房间编上号，如：

一楼：101，102，103...
二楼：201，202，203..

有了房间号，如果你的朋友得到房间号，就可以快速的找房间，找到你

如果把上面的例子对照到计算机中，又是怎么样呢？ 我们知道计算机上CPU（中央处理器）在处理数据的时候，需要的数据是在内存中读取的，处理后的数据也会放回内存中，那我们买电脑的时候，电脑上内存是8GB/16GB/32GB 等， 那这些内存空间如何高效的管理呢？

其实也是把内存划分为一个个的内存单元，每个内存单元的大小为1个字节。

每个内存单元也都有一个编号（这个编号就相当于宿舍房间的门牌号），有了这个内存单元的编 号，CPU就可以快速找到编号对应的内存单元。

生活中我们的门牌号也叫地址，在计算机中我们 把内存单元的编号也称为地址。C语言中给地址起了新的名字叫：指针。 所以我们可以理解为：

内存单元的编号==地址==指针

计算机中常见的单位（补充）：

一个比特位可以存储一个2进制的位1或者0

 bit - 比特位
 Byte - 字节
 KB
 MB
 GB
 TB
 PB

 1Byte = 8bit
 1KB = 1024Byte
 1MB = 1024KB
 1GB = 1024MB
 1TB = 1024GB
 1PB = 1024TB

1.指针变量

1.1.取地址操作符（&）

理解了内存和地址的关系，我们再回到C++，在C++中创建变量的本质是向内存申请空间，比如：

#include <iostream>

using namespace std; 

int main()
{
    int a = 10;
    
    return 0;
}

比如，上述的代码就是创建了整型变量a，在内存中申请4个字节，用于存放整数10，申请到的每个字节都有地址，上图中4个字节的地址分别是：

 0x0117FAD8
 0x0117FAD9
 0x0117FADA
 0x0117FADB

那我们如何能得到a的地址呢？

这里就得学习一个操作符(&)-取地址操作符

#include <iostream>

using namespace std;

int main()
{
    int a = 10;
    &a;//取出a的地址
 
    cout  << &a << endl;
    //0x6ffe4c
    
    return 0;
}

&a取出的是a所占4个字节中地址较小的字节的地址。

虽然整型变量占用4个字节，我们只要知道了第一个字节地址，顺藤摸瓜访问到4个字节的数据也是可行的。

那我们通过取地址操作符(&)拿到的地址是一个数值，比如： 0x0117FAD8 ，这个数值有时候也是需要存储起来，方便后期再使用的，那我们把这样的地址值存放在哪里呢？

答案是：指针变量中。

比如：

#include <iostream>

using namespace std;

int main()
{
    int a = 10;
    int * pa = &a;//取出a的地址并存储到指针变量pa中
 
    return 0;
 }
 

指针变量也是一种变量，这种变量就是用来存放地址的，存放在指针变量中的值都会理解为地址。 pa 就是存放 a 的地址，指针变量中存放谁的地址，我们就说这个指针变量指向了谁；上面代码中 们就是 pa 指向了 a 变量。 但是有时候一个指针变量创建的时候，还不知道存储谁的地址，那怎么办呢？在C++中这时候，我们会给指针变量赋值为 NULL ， NULL 的值其实是 0 ，表示空指针，意思是没有指向任何有效的变量。 当然 0 也是作为地址编号的，这个地址是无法使用的，读写该地址会报错。

int *p = NULL; 

当然在C++11后，使用 nullptr 来代替了NULL，我们在代码中也可以直接使用 nullptr 。

1.2.如何拆解指针类型

我们看到 pa 的类型是 int* ，我们该如何理解指针的类型呢？

int a = 10;
int * pa = &a;

这里pa左边写的是 int* ， * 是在说明pa是指针变量，而前面的 int 是在说明pa指向的是整型(int) 类型的对象。

那如果有一个 char 类型的变量 ch ， ch 的地址，要放在什么类型的指针变量中呢？

char ch = 'w';
pc = &ch;//pc 的类型怎么写呢？

1.3.解引用操作符

我们将地址保存起来，未来是要使用的，那怎么使哦那个呢？ 在现实生0活中，我们用地址要找到一个房间，在房间里可以拿去或者存放物品。 C++语言中其实也是一样的，我们只要拿到了地址（指针），就可以通过地址（指针）找到地址（指针）指向的对象，这里必须学习一个操作符叫解引用操作符( * )。

#include <iostream>

using namespace std;
 
int main()
{
    int a = 100;
    int* pa = &a;
    *pa = 0;
    
    cout << a << endl;
    //0
    return 0;
}

上面代码中第7行就使用了解引用操作符， *pa 其实就是 a 变量了；所以 *pa 的意思就是通过pa中存放的地址，找到指向的空间， *pa = 0 ，这个操作符是把 a 改成了 0 .

有同学肯定在想，这里如果目的就是把 呢？ 其实这里是把a的修改交给了pa来操作，这样对a的修改，就多了一种的途径，写代码就会更加灵活， 后期慢慢就能理解了。 注意：如果一个指针变量的值是 NULL 时，表示这个指针变量没有指向有效的空间，所以一个指针变量的值是 NULL 的候，是不能解引用操作的。

2.指针类型

2.1.指针类型的意义

就两个方面

2.11指针的解引用 

对比，下面2段代码，主要在调试时观察内存的变化。

//代码1
#include <iostream>

using namespace std;

int main()
{
    int n = 0x11223344;
    int *pi = &n; 
    *pi = 0;   
    
    return 0;
}

//代码2
#include <iostream>

using namespace std;

int main()
{
    int n = 0x11223344;
    char *pc = (char *)&n;
    *pc = 0;
    
    return 0;
}

调试我们可以看到，代码1会将 n 的 4 个字节全部改为 0 ，但是代码2只是将 n 的第1个字节改为 0 。

结论：指针的类型决定了，对指针解引⽤的时候有多大的权限（一次能操作几个字节）。

比如： char* 的指针解引用就只能访问一个字节，而 int* 的指针的解引用就能访问四个字节。

2.12指针+-整数

先看一段代码，调试观察地址的变化。这里为了方便观察，将环境改成x86（32位环境），在X86的环 境下地址是32个比特位的长度，在X64环境下地址是64个比特位的长度。我们这里仅仅是为了说明问题。

#include <cstdio>
#include <iostream> 

using namespace std;

int main()
{
    int n = 10;
    char* pc = (char*)&n;
    int * pi = &n;   
    printf("&n   = %p\n", &n);
    printf("pc   = %p\n", pc); 
	//字符的地址使用cout打印会以为是字符串，
	//所以这里使用printf来打印
    printf("pc+1 = %p\n", pc + 1);
    printf("pi   = %p\n", pi);
    printf("pi+1 = %p\n", pi + 1);
    //在vs2022中
	//&n   = 012FF904
	//pc   = 012FF904
	//pc+1 = 012FF905
	//pi   = 012FF904
	//pi+1 = 012FF908
    
    return 0;
}

我们可以看出， char* 类型的指针变量 +1 跳过 1 个字节， int* 类型的指针变量+1 跳过了 4 个字节。这就是指针变量的类型差异带来的变化。指针+1 ，其实跳过 1 个指针指向的元素。指针可以 +1 ，那也可以-1 。

结论：指针的类型决定了指针向前或者向后走一步有多大（距离）。

2.2.void* 指针

在指针类型中有一种特殊的类型是 void * 类型的，可以理解为无具体类型的指针（或者叫泛型指 针），这种类型的指针可以用来接受任意类型地址。但是也有局限性，void* 类型的指针不能直接进行指针的+-整数和解引用的运算。

#include <cstdio>
#include <iostream> 

using namespace std;

int main()
{
    int a = 10;
    int* pa = &a;
    char* pc = &a;
    
    return 0;
}

在上面的代码中，将一个int类型的变量的地址赋值给一个 char* 类型的指针变量。 编译器给出一个报错（无法转换类型），是因为类型不兼容。而使用 void* 类型就不会有这样的问题。

3. 指针运算

使用 void* 类型的指针接收地址：

#include <cstdio>
#include <iostream> 

using namespace std;

int main()
{
    int a = 10;
    void* pa = &a;
    void* pc = &a;
    *pa = 10;
    *pc = 0;
    
    return 0;
}
//运行报错

这里我们可以看到， void* 类型的指针可以接收不同类型的地址，但是无法直接进行指针运算。

那么 void* 类型的指针到底有什么用呢？

一般 void* 类型的指针是使用在函数参数的部分，用来接收不同类型数据的地址，这样的设计可以 实现泛型编程的效果。指针在竞赛中使用的不是很多，但是在工程中非常多，所以大家下来需要深入学习指针哦。

4.指针访问数组

有了前面的知识铺垫，我们就可以使用指针来访问内存了，这就会涉及到指针运算。 常见的指针运算就是：

练习：有一个整型数组，10个元素，默认初始化为0，现在要将数组的内容设置为1~10，然后打印数组的内容。 我们可以使用数组的形式，来完成任务，也可以使用指针的形式来完成。 我们知道数组在内存中是连续存放的，那是只要给定一个起始位置，顺藤摸瓜就能到后边的其他元素 了。下面我们来使用指针，给一个整型数组做一个初始化，再将数组的内容打印出来。

#include <iostream>

using namespace std;

int main()
{
    int arr[10] = {0};
    int *p = &arr[0];
    int i = 0;
    for(i = 0; i < 10; i++)
    {
        *(p + i) = i + 1;
    }
    
    for(i = 0; i < 10; i++)
    {
        cout << *p << " ";
        p++;
    }
    
    //1 2 3 4 5 6 7 8 9 10
    return 0;
}

上述代码中要注意几个点：

1. 这里操作的是整型数组，我们写代码时期望以一 个整型为单位的访问，解引用时访问一个整型， +1 跳过一个整型，所以我们使用了 int* 类型的指针，如果是其他类型的数据要选择最恰当的指针类型。

2. 代码中第一个 for 循环，我们选择使用个元素，第而个 p+i 的方式， p 不变， i 在不断地变化，找到数组的每 for 循环，我们选择 p++ 的效果，让 p 不断地往后寻找元素，要体会这两种的差异。

3. 我们在代码中使用 for 循环，通过元素个数控制循环的次数。其实指针就是地址，是一串编号， 这个编号是有大小的，那就可以比较大小，这就是指针的关系运算。使用指针关系运算，也能完成 上面代码。

请看下方代码：

#include <iostream>

using namespace std;

int main()
{
    int arr[10] = {0};
    int *p = &arr[0];
    int i = 0;
    for(i = 0; i < 10; i++)
    {
        *(p + i) = i + 1;
    }
    while(p < &arr[10])
    {
        cout << *p << " ";
        p++; 
    }
    //1 2 3 4 5 6 7 8 9 10
    
    return 0;
}

二. 动态内存管理

其实我们之前已经学习了变量、数组等知识，我们知道变量的创建会为变量申请一块内存空间，数组的创建其实也向内存申请一块连续的内存空间。

int n = 10; 
//向内存申请4个字节的空间
char arr1[5];
//向内存申请5个字节的空间
int arr2[5]; 
//向内存申请20个字节的空间

这两种方式，如果创建是全局的变量和数组，是在内存的静态区（数据段）申请的，如果是局部的变量和数组，是在内存的栈区申请的。不管是全局变量还是局部变量，申请和回收都是系统自动完成的，不需要程序员自己处理。

栈区：局部的变量，函数的形参

堆区：动态内存管理new和delete

静态区（数据段）：全局变量，静态变量

其实C++还提供了另外一种方式，就是：动态内存管理，允许程序员在适当的时候，自己申请空间，自己释放空间，⾃主维护这块空间的生命周期。动态内存管理所开辟到的空间是在内存的堆区。

1.new和delete

C++中通过 new 和 delete 操作符进行动态内存管理。

new 负责申请内存， new 操作符返回的是申请到的内存空间的起始地址，需要指针存放。

new申请一个变量的空间， new[] 申请一个数组的空间

de lete 负责释放（回收）内存

de lete 负责释放⼀个变量的空间，delete[] 释放一个数组的空间

new 和 delete 配对， new[] 和 delete[] 释放一个数组的空间 delete[] 配对使用

 //动态申请一个int类型的空间 
int* ptr1 = new int; 

// 动态申请一个int类型的空间并初始化为10  
int* ptr2 = new int(10);

 // 动态申请10个int类型的空间 
int* ptr3 = new int[10];

 //释放内存空间
delete ptr1;
delete ptr2;
delete[] ptr3;

new 不是只能给内置类型开辟空间，也可以给自定义类型开辟空间。

举个例子~

#include <iostream>

using namespace std;

int main()
{
    int*p = new int;
    *p = 20;
    
    cout << *p << endl;
    delete p;
    int *ptr = new int[10];
    for(int i = 0; i < 10; i++)
    {
        *(ptr + i) = i;
    }
    for(int i = 0; i < 10; i++)
    {
        cout << *(ptr + i) << " ";
    }
    delete[]  ptr;
    
    return 0;
}

其实数组是连续的空间，new[] 申请到的空间也是连续的，那上述代码中ptr 指向的空间能不能使用数组的形式访问呢？答案是可以的，上面代码中第18行代码可以换成：

 cout << ptr[i] << " ";

三.使用指针实现链表

什么是数据结构

数据结构是计算机的内存中存储和组织数据的方式。

为什么需要数据结构？

通过数据结构，能够有效将数据组织和管理在一起。 按照我们的方式任意对数据进行增、删、改、查等操作。

常见的数据结构分类

数据结构一般根据组织形式，分为：

线性数据结构和非线性数据结构。

线性的数据结构有：数组(顺序表)、链表、栈和队列等。

非线性的数据结构有：树、散列表、堆、图等。

链表的概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。 链表中的元素在内存中不必顺序排列，而是通过指针相互连接。

链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只 需要将火车里的某节车厢 去掉 / 加上，不会影响其他车厢，每节车厢都是独立存在的。

车厢是独立存在的，且每节车厢都有车门，想象一下这样的场景，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车走到车尾？ 最简单的做法：每节车厢里都放一把下一节车厢的钥匙。 火车的每节车厢就相当于链表的一个节点。 在链表里，每个节点（车厢）是什么样的呢？

链表的结构

链表的基本结构由节点组成，每个节点包含数据和指向下一个节点的指针。

 //链表节点类型的声明
 
struct Node 
{
    int data;
    Node* next;
};

数据域：存放每个节点携带的数据

指针域：存放下一个节点的地址

链表的分类

链表可以分为单向链表、双向链表和循环链表

单向链表：每个节点只有一个指针指向下一个节点。

双向链表：每个节点有两个指针，分别指向前一个节点和后一个节点

循环链表：尾节点指向头节点。

链表的结构非常多样，以下情况组合起来就有8种（2x2x2）链表结构：

动态申请链表节点和链表构建

动态申请节点并初始化

Node* createNode(int data) 
{
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = nullptr;
    return newNode;
 }

单链表元素的打印

打印链表的所有节点数据。

void printList(Node* cur) 
{
    while (cur != nullptr) 
    {
        cout << cur->data << "-->";
        cur = cur->next;
    }
    cout << "nullptr" << endl;
    cout << endl;
 }

单链表的尾部插入元素

在链表的尾部插入节点。

void PushBack(Node*& phead, int x)
{
    Node* newnode = createNode(x);
 // 1、空链表
 
// 2、非空链表
 
    if (phead == nullptr)
    {
        phead = newnode;
    }
    else
    {
        Node* tail = phead;
        while (tail->next != nullptr)
        {
            tail = tail->next;
        }

        tail->next = newnode;
    }
}

单链表头部删除元素

void PopFront(Node*& phead)
{
    //空
    if (phead == nullptr)
    {
        cout << "链表为空，没有元素可以删除了" << endl;
         return;
    }
 //非空
 
    Node* tmp = phead;
    phead = phead->next;
    delete tmp;
    tmp = nullptr;
}

单链表尾部删除元素

void PopBack(Node*& phead)
{
    //空链表
 
    if (phead == nullptr) 
    {
        cout << "链表为空，没有元素可以删除了" << endl;
        return;
    }
    // 1、一个节点
 
    // 2、一个以上节点
 
    if (phead->next == nullptr)
    {
        free(phead);
        phead = nullptr;
    }
    else
    {
        // 找尾
 
        Node* tail = phead;
        while (tail->next->next != nullptr)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = nullptr;
    }
}

释放链表的所有节点

当链表不再需要的时候，申请的节点资源最好能释放掉，否则可能带来内存泄漏的风险。所有我们再提供一个函数，释放链表的所有节点。其实这个就很简单了，我们调用一个删除元素的函数，直到把链表删除为空链表就释放了所有的节点

void PopFront(Node* & ph)
{
 //  空
 
    if (ph == nullptr)
    {
        cout << "链表为空，没有元素可以删除了" << endl;
        return;
    }
 //非空 
 
    Node* tmp = ph;
    ph = ph->next;
    delete tmp;
    tmp = nullptr;
 }

void DestropList(Node* & ph)
{
    while(ph)
    {
        PopFront(ph);
    }
}

面向对象的方式实现链表

#include <iostream>

using namespace std;

//节点类型声明
struct Node 
{
    int data;
    Node* next;
 }; 

struct List
 {
    //指向头节点的指针
 
    Node* phead;
    //成员函数
 
    //构造函数
 
    List()
    {
        cout << "构造函数调用" << endl;
        phead = nullptr;
    }
    
    //析构函数 - 在结束时释放所有剩余节点
 
    ~List()
    {
        cout << "析构函数" << endl;
        while (phead)
        {
            PopFront();
        }
    }
    
    //创建节点
 
    Node* createNode(int data) 
    {
        Node* newNode = new Node;
        newNode->data = data;
        newNode->next = nullptr;
        return newNode;
    }
    //打印链表
 
    void printList() 
    {
        Node* cur = phead;
        while (cur != nullptr) 
        {
            cout << cur->data << "-->";
            cur = cur->next;
        }
        cout << "nullptr" << endl;
        cout << endl;
    }
    
    //头部添加元素
 
    void PushFront(int data)
    {
        Node* newNode = createNode(data);
        newNode->next = phead;
        phead = newNode;
    }
    //头部删除元素
 
    void PopFront()
    {
        // 空
 
        if (phead == nullptr)
        {
            cout << "链表为空，没有元素可以删除了" << endl;
            return;
        }
        //非空
 
        Node* tmp = phead;
        phead = phead->next;
        delete tmp;
        tmp = nullptr;
    }
    
    //尾部添加元素
 
    void PushBack(int x)
    {
        Node* newnode = createNode(x);
        // 1、空链表
        // 2、非空链表
 
        if (phead == nullptr)
        {
            phead = newnode;
        }
        else
        {
            Node* tail = phead;
            while (tail->next != nullptr)
            {
                tail = tail->next;
            }
            tail->next = newnode;
        }
    }
    //尾部删除元素
 
    void PopBack()
    {
        //空链表
 
        if (phead == nullptr) 
        {
            cout << "链表为空，没有元素可以删除了" << endl;
            return;
        }
        // 1、一个节点
 
        // 2、一个以上节点
 
        if ((phead)->next == nullptr)
        {
            delete phead;
            phead = nullptr;
        }
        else
        {
            // 找尾
 
            Node* tail = phead;
            while (tail->next->next != nullptr)
            {
                tail = tail->next;
            }
            delete tail->next;
            tail->next = nullptr;
        }
    }
     void DestropList()
    {
        while(phead)
        {
            PopFront();
        }
    }
 };
 
int main()
{
    List list;
    list.PushBack(1);
    list.PushBack(2);
    list.PushBack(3);
    list.PushBack(4);
    list.printList();
    //头部删除并打印
 
    list.PopBack();
    list.printList();
    list.PopBack();
    list.printList();
    list.PopBack();
    list.printList();
    list.PopBack();
    list.printList();
    list.PopBack();
    list.printList();
    //头部添加元素
 
    list.PushFront(1);
    list.PushFront(2);
    list.PushFront(3);
    list.PushFront(4);
    list.printList();
    //头部删除
 
    list.PopFront();
    list.printList();
    list.PopFront();
    list.printList();
    
    return 0;
}

运行结果

OK~uu们，到此C++结束咯，本系列只适用于竞赛，想熟练使用只了解这些是不够的，还需系统学习，我以后也会出深入系统篇哒，再见哦