Pointers and Linked Lists

Linked data structures(链表数据结构)

一些集合使用节点的链接序列来存储数据。

每个节点存储一个元素及一个指向其他节点的链接。

例子：集合（Set）、映射（Map）、链表（LinkedList）

优点:在任何位置添加/删除速度快；不需要移动、不需要调整大小。

缺点:需要额外的内存空间来存储链接。访问列表的某些部分较慢。

Structs(结构体)

结构体是一种数据类型，它可以包含多个成员变量。

结构体就是一个小型的类，它可以包含数据成员和函数成员。

但是一般用来存放数据，而不是用来定义行为。

例如我们定义一个名为 date 的结构体:

c++

struct Date{
    int month;
    int day;
};

Memory addresses(内存地址)

内存地址是一个数字，它唯一地标识一个内存位置。

在 C++中，可以使用&运算符来获取变量的内存地址。

十六进制表示法:内存地址以十六进制表示，以0x开头。

例如，0x7fff0000是一个常用的地址，表示系统的堆栈区。

有趣的是:结构体的内存地址和结构体变量的第一个成员的内存地址是一样的。而,第二个变量比前地址向前偏移了若干字节.

Pointers(指针)

type* name = address

指针是一个变量，它存储着另一个变量的内存地址。

引用是指针的简化版本，它只存储一个变量的内存地址。

指针可以指向任意类型的变量，包括结构体。

指针可以用来访问变量的值，也可以用来修改变量的值。

几种指针的变体:

空指针(null pointer): 指针变量没有指向任何内存地址。

如果你想输出一个*空指针,那么你的程序会崩溃.

未初始化指针(uninitialized pointer): 指针变量没有被初始化。

如果你试图使用一个未初始化的指针,那么你的程序也会崩溃.

c++

int* p1 = nullptr; // 空指针

if(p1 == nullptr)// true
if(p1) // false
if(!p1) // true

野指针(dangling pointer): 指针变量指向一个已经被释放的内存地址。

Point to a struct(指向结构体):

type* name = new type(parameters);

符号->用来访问结构体的成员变量。

c++

struct Person{
    string name;
    int age;
};

int main(){
    Person* p = new Person;
    p->name = "John";
    p->age = 25;
    cout << p->name << " " << p->age << endl;
    delete p;
    return 0;
}

我们来进行一个比较:

c++

// 1) non-pointer
Date d1;
d1.month = 7;
d1.day = 13;

// 2) pointer
Date* d2 = new Date();
d2->month = 7;
d2->day = 13;

很线性第一种语法更为简洁,有时我们会采用这种语法.

该问题和作用域有关,第一种在函数中定义的变量,其生命周期只在函数内,而在函数外,其生命周期则是整个程序的生命周期.

但是第二种就不会被销毁,直到程序结束.或是我们主动 delete

A list node structure(链表节点结构)

c++

struct ListNode{
    int date;
    ListNode* next;
};

每一个链表节点都包含:

一个整数值(date)
一个指向下一个节点的指针(next)

你会发现,如果你将链表连起来,指针就可以连起来.就是可以如图所示

Pointers and Linked Lists ​

Linked data structures(链表数据结构) ​

Structs(结构体) ​

Memory addresses(内存地址) ​

Pointers(指针) ​