C语言 链表 栈与队列 二叉树遍历

![在这里插入图片描述](/static/img/images/01392.png)





`1 栈的注意点`

先进后出。

递归的时候就会用到栈，把这次结果压入栈，去计算下一次的。

题外话：算法中避免用递归。不断压入栈有时会导致过多占用内存，

`2 栈的典型应用`

可线性描述、逆序输出、大小规模不确定。

递归嵌套：具有自相似性的问题多可嵌套地递归描述。

栈混洗（stack permutation）、括号匹配、

![在这里插入图片描述](/static/img/images/01393.png)

逆波兰表达式



`3  试探回溯法  高效地实现试探回溯策略`

n皇后问题

迷宫路径问题




`4 栈与队列`

都是一种数据结构，应用场合不定，作用广泛。

数据结构 笔记 --栈与队列 C++ 语言版 邓俊辉老师

![在这里插入图片描述](/static/img/images/01401.png)





![在这里插入图片描述](/static/img/images/01402.png)


`1 链表 列表`

链表不是列表。我们所谈的列表更倾向于是针对对象而言的。

或许应该说列表是链表的扩展。他们的物理存储结构都不是连续的，而是依赖于节点指针指向的。所以链表里面的很多算法拿到列表对象上来说，都差不多。

`2 向量 列表`

向量在物理存储上地址是连续的。所以get()、size()这类静态方法效率高。但是insert()和remove()等动态操作需要线性时间。

列表则相反。

数据结构 笔记--列表 循位置访问 C++ 语言版 邓俊辉老师

邓俊辉老师的书。





![在这里插入图片描述](/static/img/images/01403.png)

`1 有数组为什么还需要向量？`

几乎所有程序设计语言中都会有数组，程序设计语言的开发者将数组作为一种内置的数据类型。

数组在刚开始初始化的时候就已经固定了长度，也可以依照下标查找，但还有很多种特性数组是不含有的。

向量这种抽象数据类型，它是一种利用程序设计语言抽象出来的一种数据类型。我们可以在运行时开辟一块空间来放一段数据，它就是一个对象。我们可以轻易的利用操作接口方法来对这些数据进行获取、插入、删除、查找、排序、集合化。可以看到如果拥有这些方法可以对数据进行更好的处理，是数组不能替代的。

还有一点是非常重要的，无论我们基于什么语言设计了一个抽象数据类型，在内部的实现方法可能就是使用的数组，我们只是做了将数组抽象化为更普遍的数据类型，并把这种数据类型取名为向量，因为这种数据类型和向量的很多特性都很相似。

`2 什么是抽象数据类型？什么是数据结构？`

抽象数据类型=数据模型+定义在该模型上的一组操作

数据结构=基于某种特定语言，实现抽象数据类型adt的一整套算法。

数据类型就是指 Int x，我们抽象数据类型的目的就是 vector x。

抽象数据类型是一种抽象定义、要考虑操作语义、不涉及数据的存储方式。

数据结构是一种具体的实践方法，要注重内部的实现算法，要考虑数据的具体存储机制。


`3 在这一章中主要讲的内容是什么？`

假如我们用c语言写了一个队列数据结构。我们应该讲一下队列这种数据结构的特性，所需要的方法（从对象的角度来看，就是我们应该讲一下队列这种对象应该有哪些行为和属性），同时我们也应该考虑去实现这些方法的时候我们的程序应该怎么写才能使得对象用起来更加顺手，去实现这些方法我们有不同的程序写法（每一种写法都是一种算法），如何使这些算法更加低成本和高效率也是我们应该考虑的。

这一章的内容就是在讲向量这个数据结构应该具有的行为方法，以及我们应该怎么用程序去实现这些行为方法，并且使得程序是高效率和低成本兼顾着的。

`4 有序向量和无序向量有什么区别？`

由于这两者表达数据的方法不一样，所以这两者的数据结构实现算法也不一样。有序向量可以很方便的进行查找操作，如果我们在给一堆数据建模，然后查找操作非常频繁的话就可以优先使用有序向量。

`5 总结`

如果我们是在用c语言学习数据结构这门课，那么内容将会有线性表（数组、链表）、队列与栈（特殊线性表）、串、树、图，在这些内容中又会详细的了解到查找与排序。

现在我们用c++语言学习数据结构这门课，要将关注点放在对象上来。

向量是`寻秩访问`，内部是由数组实现的，在物理空间上一个向量对象里的数据是连续存储的。

数据结构 笔记--向量 C++ 语言版 邓俊辉老师

学习 清华大学 尊敬的邓俊辉老师的C++数据结构与算法课程 第10章 优先级队列，本文旨在摘要和心得体会。






# 1 优先级队列需求

计算机系统里CPU的任务调度，$\color{red}{循优先级访问}$。

不同于队列结构的先进先出，找队列里最大值先出。

约定：优先级队列里的每个数据项目都有一个关键码key，可以进行比较大小（可依靠重载比较操作符实现），关键码越大，优先级越高。

操作接口描述：

| 操 作 接 口 |   功 能 描 述 |

-------- | -----

size() | 报告优先级队列的规模，即其中词条的总数

insert()  | 将指定词条插入优先级队列

getMax()  | 返回优先级最大的词条（若优先级队列非空）

delMax()   |删除优先级最大的词条（若优先级队列非空）


借助无序列表、有序列表、无序向量或有序向量，都难以同时兼顾insert()和

delMax()操作的高效率。而采用一些树结构如平衡二叉搜索树BBST又有点牛刀杀鸡，需要一种轻量级的数据结构，只需要考虑最大值，无需全部排序（无需维护全序，只需要关心“偏序”），使得我们能在效率和消耗上有一个平均，能完成我们需要的ADT接口。

# 2 完全二叉堆

## 2.1 定义

何为堆？

- 堆中某个节点的值总是不大于或不小于其父节点的值；$\color{red}堆序性，最顶上是最大值的也叫大项堆，反之叫最小堆。$

- 堆总是一棵完全二叉树。$\color{red}结构性$

常见的堆有完全二叉堆。$\color{red}完全二叉堆性质：结构性与堆序性$

由于完全二叉树性质，n个词条组成的堆的高度h =$\mathbf{1} \mathbf{o} \mathbf{g}_{2} \mathbf{n}$ = O(logn)。

基于向量的紧凑表示：

![在这里插入图片描述](/static/img/images/02324.png)

## 2.2 getMax()

取出最顶端元素的操作即是返回向量的首单元_elem[0]。

## 2.3 insert() 插入与上滤

插入算法分为两个步骤：

首先将新词条接至向量末尾；

再对该词条实现上滤调整。

```cpp
template <typename T> void PQ_ComplHeap<T>::insert ( T e ) { 
Vector<T>::insert ( e );  //首先将新词条接至向量末尾
percolateUp ( _size - 1 ); //再对该词条实现上滤调整
```

![在这里插入图片描述](/static/img/images/02325.png)

$\color{red}上滤$：将插入的新节点与其父节点比较，若大于父节点值，则进行节点交换，交换后再次将这个新插入节点与新的父节点比较；若小于父节点值，则算是完成上滤过程。若来插入的新节点来到堆顶，也算是完成了上滤过程。

整体时间复杂度：O(logn)。

$\color{red}效率改进$

代码里每次需要交换swap需要三次赋值操作，时间复杂度就是3*logn。

改进后步骤：

（1）插入新节点后，新节点数值赋值给一个副本；

（2）进行不断比较，新节点值大于父节点则需要一次赋值操作（只将父节点值往下移）；

（3）直到找到一个父节点比自身大，停止比较，将新节点数值赋值给上次的父节点。

如下图的表示，时间复杂度就是2+logn。

![在这里插入图片描述](/static/img/images/02326.png)

## 2.4 delMax() 删除与下滤

删除算法分为两个步骤：

对新堆顶实施下滤；

返回此前备份的最大词条。

```cpp
 template <typename T> T PQ_ComplHeap<T>::delMax() { //删除非空完全二叉堆中优先级最高的词条
 T maxElem = _elem[0]; _elem[0] = _elem[ --_size ]; //删除堆顶（首词条），代之以末词条
 percolateDown ( _size, 0 ); //对新堆顶实施下滤
 return maxElem; //返回此前备份的最大词条
 }
```

$\color{red}下滤$：

父节点与子节点的不断的比较与交换，直到下滤完成。

![在这里插入图片描述](/static/img/images/02327.png)

## 2.5 heapification 建堆

给定一组无序词条，如何快速组建成堆结构？

蛮力算法（自上而下的上滤）：

从空堆开始，不断调用insert()，将词条插入。时间复杂度大。

$o(\log 1+\log 2+\ldots+\log n)=O(\log n !)=o(n \log n)$


Floyd 建堆算法（自下而上的下滤）：

依照层次遍历顺序找到最后一个子节点，不断通过下滤来合并堆（和父节点比较和交换过程）。

时间复杂度

$\sum_{i=0}^{n}\left((d-i) \cdot 2^{i}\right)=2^{d+1}-(d+2)=n-\log _{2}(n+1)=o(n)$
```cpp
template <typename T> void PQ_ComplHeap<T>::heapify ( Rank n ) { //Floyd建堆算法，O(n)时间
for ( int i = LastInternal ( n ); InHeap ( n, i ); i-- ) //自底而上，依次
percolateDown ( n, i ); //下滤各内部节点
}
```

![在这里插入图片描述](/static/img/images/02328.png)

## 2.6 就地堆排序

M是堆顶元素，和堆尾元素交换，然后对x进行下滤再次将剩余部分组建成堆；重复取出堆顶元素的操作和下滤操作，直至空堆后结束。

```cpp
 template <typename T> void Vector<T>::heapSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= size
 PQ_ComplHeap<T> H ( _elem + lo, hi - lo ); //将待排序匙间建成一个完全二叉堆，O(n)
 while ( !H.empty() ) //反复地摘除最大元并归入已排序癿后缀，直至堆空
 _elem[--hi] = H.delMax(); //等效于堆顶不末元素对换后下滤
 }
```

![在这里插入图片描述](/static/img/images/02329.png)

时间复杂度O(nlogn)，空间复杂度几乎就地。但算法不稳定。

| 排序方法 |   平均时间 |最好时间 |最坏时间

-------- | -----| -----| -----

桶排序(不稳定) |O(n)  |O(n) | O(n)

基数排序(稳定)  |O(n)  |O(n)  |O(n)

归并排序(稳定)  |O(nlogn) | O(nlogn)  |O(nlogn)

快速排序(不稳定) | O(nlogn)  |O(nlogn) | O(n^2)

堆排序(不稳定) | O(nlogn) | O(nlogn) | O(nlogn)

希尔排序(不稳定) | O(n^1.25)    

冒泡排序(稳定) | O(n^2)  |O(n)  |O(n^2)

选择排序(不稳定) | O(n^2)  |O(n^2)  |O(n^2)

直接插入排序(稳定)  |O(n^2)  |O(n)  |O(n^2)


# 3 左式堆

## 3.1 堆合并

有两个堆A和B，需要合并。

不理想的方法一：

反复取出堆B的最大词条并插入堆A中；当堆B为空时，堆A即为所需的堆H。O(mlogn)

不理想的方法二：

用Floyd 建堆算法直接将所有元素重建。O(n)

## 3.2 左式堆

左式堆（leftist heap）是优先级队列的另一实现方式，可高效地支持堆合并操作。

左式堆的节点的分布均偏向左侧，不再满足堆的结构性，故不再使用向量实现，而是采用二叉树。

![在这里插入图片描述](/static/img/images/02330.png)

节点x的空节点路径长度（null path length），记作npl(x)。若x为外部节点，则约定

npl(x) = npl(null) = 0。反之若x为内部节点，则npl(x)可递归地定义为：

npl(x) = 1 + min( npl(lc(x)), npl(rc(x)) )

也就是说，节点x的npl值取决于其左、右孩子npl值中的小者。

左式堆是处处满足“左倾性”的二叉堆，即任一内部节点x都满足

npl(lc(x)) >= npl(rc(x))

也就是说，就npl指标而言，任一内部节点的左孩子都不小于其右孩子。

![在这里插入图片描述](/static/img/images/02331.png)

## 3.3 左式堆合并算法

一言以蔽之：递归地去维护一个左倾。

![在这里插入图片描述](/static/img/images/02332.png)

![在这里插入图片描述](/static/img/images/02333.png)

![在这里插入图片描述](/static/img/images/02334.png)

![在这里插入图片描述](/static/img/images/02335.png)

## 3.4 左式堆 插入

等效于合并：新元素自成一个堆，原来的堆一个堆，两个堆合并。

## 3.5 左式堆 删除

等效于合并：删除了顶元素，剩下的两个堆合并在一起。


# 4 python里的heapq

[https://docs.python.org/zh-cn/3/library/heapq.html](https://docs.python.org/zh-cn/3/library/heapq.html)

heapq实现的是最小堆。

Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for all k, counting elements from 0. 

```python
Usage:
heap = []            # creates an empty heap
heappush(heap, item) # pushes a new item on the heap
item = heappop(heap) # pops the smallest item from the heap
item = heap[0]       # smallest item on the heap without popping it
heapify(x)           # transforms list into a heap, in-place, in linear time
item = heapreplace(heap, item) # pops and returns smallest item, and adds
                               # new item; the heap size is unchanged
```

接口：

```python
__all__ = ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge',
           'nlargest', 'nsmallest', 'heappushpop']
```

简单使用：

```python
import heapq
import random
h = [random.randint(2,100) for i in range(10)]
print("heap is", h)
heapq.heapify(h)
print("heap is", h)
print([heapq.heappop(h) for i in range(len(h))])
print(list(heapq.merge([1,33,5,7], [0,2,4,8], [5,10,15,20], [], [25])))
```

# 5 python里的heapq  第二话

[https://docs.python.org/zh-cn/3/library/heapq.html](https://docs.python.org/zh-cn/3/library/heapq.html)

堆是一个二叉树。

层次遍历，为每个节点编号如下。

![在这里插入图片描述](/static/img/images/02336.png)

可见，根节点root编号 i(root)=0

如果一个普通节点v的编号记作是 i(v)

那么，节点v的左孩子编号是2*i(v)+1，

节点v的右孩子编号是2*i(v)+2。

python实现的是小顶堆，满足：

 heap[v] <= heap[2*v+1] 和 heap[k] <= heap[2*v+2]。

 这个API与教材的堆算法实现有所不同，具体区别有两方面：（a）我们使用了从零开始的索引。这使得节点和其孩子节点索引之间的关系不太直观但更加适合，因为 Python 使用从零开始的索引。 （b）我们的 pop 方法返回最小的项而不是最大的项（这在教材中称为“最小堆”；而“最大堆”在教材中更为常见，因为它更适用于原地排序）。

[数据结构与算法] 优先级队列/堆队列 完全二叉堆 左式堆 python里的heapq

我是一个专注技术分享的博主,尤其爱搞深度学习和单片机电子。你现在看到的是我的个人博客网站。