data structure

常用数据结构总结

sort

Posted by Jow on June 20, 2019

目录

  1. 栈和队列
  2. 链表
  3. 指针的对象的实现
  4. 堆
  5. 树

At this time, i have realised what i know is so less that i can’t do what i want to do. So what you should do is to study more what is deep in your field.

栈和队列

栈后进先出（LIFO），与之对应的是队列先进先出（FIFO）。

进栈：push

出栈：pop

链表

链表当第一个节点存在数据的时候，这个链表是没有哨兵的，当第一个节点不存在数据的时候这个链表是存在哨兵的。

链表分为单项链表和双向链表。

指针的对象的实现

例如像双向链表，用多个数组来表示的时候，一个数组放可以值，一个数组放next的index，一个数组放pre的index。

一个数组来表示的时候，加上偏移就可以实现。

堆

堆不仅用在堆排序中，而且它也可以构造一种有效的优先队列。虽然”堆”这一词源自于堆排序，但是目前他已经被引申为”垃圾收集存储机制”。

堆是一个数组，它可以被看成一个近似的完全二叉树，树上的每个节点对应数组中的一个元素，除了底层外，该树是完全充满的，而且是从左向右充满。

表示堆的数组A包括连个属性：A.length给出元素的个数，A.heap-size表示有多少个元素储存在该数组中，意味着从1到A.length都存有数据，但是1到heapsize是堆的有效数据。

树的根节点是A[1],所以我们可以很方便的算出父节点和左孩子以及右孩子。

parent： math.floor(i / 2)

left 2i

right: 2i+1

堆又分为最大堆和最小堆：

最大堆，除了根节点意外其他所有的节点的值都要小于等于其父节点。

最小堆，除了根节点意外其他所有的节点的值都要大于于等于其父节点。最小堆的最小元素放在根节点中。

在堆排序算法中，我们使用最大堆，最小堆通常用于构造优先队列。

我们定义一个堆的高度就是为为该节点到叶节点最简单路径上的数目。

包含n个元素的堆可以看做一颗完全二叉树，那么该堆的高度是lgn。

我们发现堆结构的一些基本操作的运行时间至多与树的高度成正比，即时间复杂度为O(lgn)。

维护堆的性质

MAX-HEAPIFY是用于维护最大堆性质的重要过程。它的输入为一个数组A和一个下标i。在调用MAX-HEAPIFY的时候我们假设根节点的左孩子和右孩子的二叉树都是最大堆，但这个时候A[i]可能小于其孩子，这就违背了最大堆的性质。MAX-HEAPIFY通过让A[i]的值在最大堆中“逐级下降”，从而使得下标i为根节点的子树重新遵循最大堆的性质。MAX_HEAPIFY的作用是当堆中的元素值发生变化的时候，进行重新构造堆的结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

local arr = { 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 }

local function getChildTreeMax(arr, i, max)
    if arr[i] then
        if arr[i] > arr[max] then
            max = i
        end
    end
    return max
end
local heapify
heapify = function(arr, i)
    local max = i
    local l = getChildTreeMax(arr, 2 * i, i)
    local r = getChildTreeMax(arr, 2 * i + 1, i)
    if arr[l] > arr[max] then
        max = l
    end
    if arr[r] > arr[max] then
        max = r
    end
    if max ~= i then
        arr[i], arr[max] = arr[max], arr[i]
        heapify(arr, max)
    end
end
heapify(arr,2)

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

含n个元素的堆的高度为math.floor(lgn) 因为 2^n - 1 = 2 ^ (n - 1) + … + 2^0

当使用数组表示存储n个元素的堆时，叶节点的下标分别是math.floor(n/2) + 1 … n,因为堆是完全二叉树，所以叶子节点在最后一层的左边。

n = n0 + n1 + n2

n = 1 + n1 + 2 * n2

n0 = 2*n0 + n1 - 1 ，因为完全二叉树的n1为0或者1，所以n0等于n/2或者(n+1)/2

所以最后一个父节点为math.floor(n/2)，所以堆的建立，通过从底向上调整堆就可以得到一个正确的最大堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

local arr = { 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 }

local function getChildTreeMax(arr, i, max)
    if arr[i] then
        if arr[i] > arr[max] then
            max = i
        end
    end
    return max
end
local heapify
heapify = function(arr, i)
    local max = i
    local l = getChildTreeMax(arr, 2 * i, i)
    local r = getChildTreeMax(arr, 2 * i + 1, i)
    if arr[l] > arr[max] then
        max = l
    end
    if arr[r] > arr[max] then
        max = r
    end
    if max ~= i then
        arr[i], arr[max] = arr[max], arr[i]
        heapify(arr, max)
    end
end
local lastParent = math.floor(#arr / 2)
for i = lastParent, 1, -1 do
    heapify(arr, i)
end

堆排序

每次取出堆顶的那个元素，再进行重新校正，再取出堆顶的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

local arr = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 }

local function getChildTreeMax(arr, i, max)
    if arr[i] then
        if arr[i] > arr[max] then
            max = i
        end
    end
    return max
end
local heapify
heapify = function(arr, i)
    local max = i
    local l = getChildTreeMax(arr, 2 * i, i)
    local r = getChildTreeMax(arr, 2 * i + 1, i)
    if arr[l] > arr[max] then
        max = l
    end
    if arr[r] > arr[max] then
        max = r
    end
    if max ~= i then
        arr[i], arr[max] = arr[max], arr[i]
        heapify(arr, max)
    end
end
local lastParent = math.floor(#arr / 2)
for i = lastParent, 1, -1 do
    heapify(arr, i)
end

local result = {}
local length = #arr
for i = 1, length do
    table.insert(result, arr[1])
    table.remove(arr, 1)
    if arr[1] then
        heapify(arr, 1)
    end
end

优先队列

优先队列是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字。一个最大优先队列支持一下操作：

insert（s,x):把元素x插入集合s中， –在堆的最后添加一个新值，然后调用increase-key函数

maximum(s):返回s中具有最大键字的元素 –>返回第一个值

extract-max(s):去掉并返回s中具有最大键字的元素 –>取出第一个值，然后对第一个值进行校正

increase-key(s,x,k):将元素x的关键字值增加到k，这里假设k不小于x的原关键字值 –>和插入排序很像，不断的和父节点进行比较，直到到顶或者小于父节点。

树

二叉树表示方法，每个节点存的信息应该包含父节点，左孩子和右孩子节点。

分支无限制的有根树：左孩子右兄弟表示法。父节点，左孩子和右兄弟。

当然还有其他表示方法，对于一颗完全二叉树可以使用堆来表示，堆用一个单数组加上堆的最末节点的下表表示。还有就是只需要向父节点遍历，这个时候只需要根节点就行了，所以使用那一种表示方法取决于应用场景。

二叉搜索树

对于二叉搜索树，对于任意的节点x它的左子树上的关键字，不超过x位置上的关键字，其右子树上的关键字不小于x的关键字。

二叉树的遍历方法：

  1. 中序遍历：输出的子树根的关键字位于其左子树和右子树之间。
  2. 先序遍历：…之前
  3. 后序遍历:… 之后

输出一个二叉搜索树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

local midOrderTree
local midResult = {}
midOrderTree = function(node)
    if node then
        midOrderTree(node.left)
        table.insert(midResult, node.key)
        midOrderTree(node.right)
    end
end

local preOrderTree
local preResult = {}
preOrderTree = function(node)
    if node then
        table.insert(preResult, node.key)
        preOrderTree(node.left)
        preOrderTree(node.right)
    end
end

local lastOrderTree
local lastResult = {}
lastOrderTree = function(node)
    if node then
        lastOrderTree(node.left)
        lastOrderTree(node.right)
        table.insert(lastResult, node.key)
    end
end

查询二叉搜索树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

local treeSearch
treeSearch = function(x, k)
    if x == nil or k == x.key then  --返回节点值，或者空值
        return x
    end
    if k < x.key then
        return treeSearch(x.left, k)
    else
        return treeSearch(x.right, k)
    end
end

local treeMin
treeMin = function(x)
    while x.left ~= nil do
        x = x.left
    end
	return x
end

local treeMax
treeMax = function(x)
    while x.right ~= nil do
        x = x.right
    end
	return x
end

后继和前驱

查找后继：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

local treeSearch
treeSearch = function(x, k)
    if x == nil or k == x.key then  --返回节点值，或者空值
        return x
    end
    if k < x.key then
        return treeSearch(x.left, k)
    else
        return treeSearch(x.right, k)
    end
end

local treeMin
treeMin = function(x)
    while x.left ~= nil do
        x = x.left
    end
	return x
end

local treeMax
treeMax = function(x)
    while x.right ~= nil do
        x = x.right
    end
	return x
end

往搜索树上插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

local treeInsesrt = function(t, z)
    local x = t.root
    local y
    while x do
        y = x
        if x.key > z.key then
            x = x.left
        else
            x = x.right
        end
    end
    z.parent = y
    if not y then
        t.root = z
    elseif y.key > z.key then
        y.left = z
    else
        y.right = z
    end
end

往搜索树上删除

删除分为三种情况:

  1. 没有子节点–>直接删除改变父节点
  2. 只有一个孩子，删除之后将孩子的位子变成自己的位子，改变父节点和，孩子节点的父节点
  3. 两孩子的时候，需要找出后继节点，如果后继节点是子孩子，直接把子孩子和自己的位置互换就行了，不是的话，需要把后继的右孩子作为后继节点父节点的左孩子自，后继节点和删除节点互换。
  4. ```lua local function translateNode(T, u, v) if u.parent == nil then T.root = v elseif u == u.parent.left then u.parent.left = v else u.parent.right = v end if v ~= nil then v.parent = u.parent end end

local function treeDelete(T, z) if z.left == nil then translateNode(T, z, z.right) elseif z.right == nil then translateNode(T, z, z.left) else local y = treeNext(z) if z.right ~= y then translateNode(T, y, y.right) y.right = z.right y.right.parent = y end translateNode(T, z, y) y.left = z.left y.left.parent = y end end

```

CATALOG
    FEATURED TAGS
    DDT Lua lua program dedign C++ OpenGL 数据结构 network c++ 感悟 Python arithmetic graph Battle Life ToolStudy Unity ddt
    FRIENDS