Classes, Arrays

引言

到目前为止，在本课程中，我们使用了许多集合类：

向量、网格、栈、队列、映射、集合、哈希映射、哈希集合、词汇表等。

从现在开始让我们探索它们是如何实现的。

我们将从实现自己的栈类版本开始。

为此，我们必须学习有关类、数组和内存分配的知识。

Classes

在面向对象编程中，类是创建对象的蓝图。类定义了对象的属性和方法。

而那些 c++中的数据结构，比如栈、队列、映射、集合等，都是使用类来编写的.

关于类的详解,可以去到前面的笔记c++.oop 类与对象编程

Interface vs.code(C++实现)

C++将类分为两种代码文件：

.h: 一个包含接口（声明）的“头文件”。
.cpp: 一个包含定义（方法体）的“源文件”。
class Foo => 必须同时编写 Foo.h 和 Foo.cpp。

.h 文件的内容会被 #include 进 .cpp 文件中：

使其能够识别在其他地方实现的代码声明。
在编译时，所有定义会被链接在一起形成可执行文件。

Arrays(数组)

数组是一种存储相同类型元素的固定大小的内存块。

数组的两种实现:

静态数组(Static Array): 静态数组在编译时就已经分配好了内存空间，数组的大小在编译时就已经确定了。

c++

int arr[10]; // 10个整数数组

动态数组(Dynamic Array): 动态数组在运行时才分配内存空间，数组的大小可以根据需要增加或减少。

c++

int* arr = new int[10]; // 10个整数数组
int* arr = new int[10](); // 10个默认初始化的整数数组

Memory Allocation(内存分配)

在 C++中，内存分配是通过 new 和 delete 关键字来完成的。

当我们使用 new 关键字申请内存时，系统会从堆中分配一块内存，并返回一个指向这块内存的指针。

当我们使用 delete 关键字释放内存时，系统会回收这块内存。

注意：当我们使用 new 关键字申请内存时，系统会自动调用构造函数来初始化这块内存。

注意：当我们使用 delete 关键字释放内存时，系统会自动调用析构函数来销毁这块内存。

How Vector/Stack works(向量/栈的实现原理)

向量内部是一个存储你添加的元素的数组。

通常，数组的大小大于目前添加的数据，以便有一些额外的槽位来放置后面的新元素。

我们称之为未填充数组。

如果数组随着你的增加从而增加他的存储这会使得效率非常的低下

因为在 C++中,数组实际上并不容易进行大小的调整

若想扩展数组,实际上就需要创建一个新的数组并将所有元素一一复制过去,这是一个很慢的过程

所以,有了"未填充数组"的概念,使其拥有额外的槽位.

ArrayStack(用数组实现栈)

在头文件里面我们需要命名变量和函数,然后在源文件里面实现函数的具体实现.

c++

#ifndef _ARRAYSTACK_H
#define _ARRAYSTACK_H

#include<iostream>
using namespace std;


class ArrayStack{
public:

    //构造函数
    ArrayStack();

    //函数
    void push(int n);

    int pop();

    int peek();

    //成员

    int* element;
    int size;
    int capacity;
};

#endif // ARRAYSTACK_H

c++

#include"ArrayStack.h"

ArrayStack::ArrayStack()
{
    element = new int[10]();
    size = 0;
    capacity = 10;
}

void ArrayStack::push(int n)
{
    element[size] = n;
    size++;
}

int ArrayStack::pop()
{
    int s = element[size-1];
    element[size-1] = 0;
    return s;
}

int ArrayStack::peek()
{
    return element[size-1];
}

Classes, Arrays ​

引言 ​

Classes ​

Interface vs.code(C++实现) ​

Arrays(数组) ​

Memory Allocation(内存分配) ​

How Vector/Stack works(向量/栈的实现原理) ​

ArrayStack(用数组实现栈) ​