Links List Stack Classes

还记得几节课之前的的 ArrayStack 吗？

这节课我们继续学习.

但是在这之前我们还需要了解 c++中的一些东西

`Const`

const关键字是用来修饰变量的，用来表示这个变量是常量，不能被修改。

const 的意思就是恒定不变,即无法更改的事物.

一个 const 引用参数不能被函数修改：

c++

void f(const int& x) {
    // x is a const reference to a const object
    // x cannot be modified
}

一个 const 成员函数不能改变对象的状态：

c++

class BankAccount {
    ...
    double getBalance() const;
};

ArrayStack

那么 ArrayStack 里面那些函数使用const关键字呢?

大概有这几个:

int peek() const
int isEmpty() const
int toString() const

Operator Overloading(重载运算符)

运算符重载是指在已有的运算符的基础上,定义新的运算符,使得其作用在特定的数据类型上.

是的但是这就是 C++,自由而又危险.

operator<<

详情可见:c++.opp/运算符重载

Destructor(析构函数)

析构函数是用来释放内存的,当对象被销毁时,析构函数就会被调用.

详情请见:c++.oop/构造函数和析构函数

A LinkedIntlist class

内存的释放

我们不够使用front = nullptr;来释放内存,因为这样做会导致内存泄漏.

正确的做法是使用delete来释放内存.

c++

LinkIntList::~LinkIntList() {
    while (front!= nullptr) {
        LinkInt* temp = front;
        front = front->next;
        delete temp;
    }
}

Priority Queue and Heaps(优先队列和堆)

优先级问题

打印任务：实验室打印机接受来自整个大楼的任务。教师的打印任务优先于工作人员，然后是研究生和本科生的任务。
急救调度：枪伤受害者应优先于感冒患者进行处理，无论到达时间如何。

我们想要一个“队列”，功能包括：

添加一个元素（打印任务、患者等）
获取/移除最“重要”或“紧急”的元素

优先队列

提供对其最高优先级元素的快速访问。

enqueu：以给定优先级添加一个元素
peek：返回最高优先级值
dequeue：移除/返回最高优先级值

Heaps(堆)

堆必须是完全二叉树.

那么什么是完全二叉树呢:

除了最底层,其他层的节点都有两个子节点
从左到右,节点的索引是其在数组中的位置
最后一行元素之间不能有间隔

堆的性质:

堆序性:

我们可以把堆分为两类:

- 大根堆:每个节点的值都大于或等于其子节点的值
- 小根堆:每个节点的值都小于或等于其子节点的值

把堆看作一棵树,根节点的值是最小的或最大的,并且树的结构保持堆序性.

对可以用数组来实现的堆来说,父节点的索引是i/2,左子节点的索引是2i+1,右子节点的索引是2i+2.

堆的基本操作

上滤: 将一个元素添加到堆中,我们需要将其与父节点比较,如果父节点的值比新元素小,我们就交换它们的位置,直到新元素的位置被找到.
下滤: 当我们从堆中移除一个元素时,我们需要将其与最后一个元素交换,然后将它与新的最后一个元素比较,直到它被放到正确的位置.

建堆

自下而上建堆法:

从最后一个非叶子节点开始,对每个节点执行下滤操作
最后一个非叶子节点的索引是n/2-1,其中n是堆的大小
时间复杂度:O(n)

堆排序

如果你想排出来是正序,那么请使用大根堆,反之,请使用小根堆.

建堆
交换堆顶元素和最后一个元素
下滤最后一个元素
重复步骤 2 和 3,直到堆为空
时间复杂度:O(nlogn)

Links List Stack Classes ​

Const ​

ArrayStack ​

Operator Overloading(重载运算符) ​

Destructor(析构函数) ​

A LinkedIntlist class ​

Priority Queue and Heaps(优先队列和堆) ​

优先级问题 ​

优先队列 ​

Heaps(堆) ​