数据结构和算法

数据结构

1. 哈希表 Hash Table

应用:计数排序 桶排序 基数排序

2. 队列 queue

先进先出,可以用数组实现,push shift

3. 栈 stack

先进后出,可以用数组实现 push pop

4. 链表 Linked Table

用 hash 实现链表,链表头为 head,节点为 node
通过改变指向可实现数据的删除

5. 树 tree

概念: 层数、深度、节点个数2^n-1、二叉树、满二叉树、完全二叉树、
完全二叉树和满二叉树可以用数据实现,其他树可以用 hash 实现
堆排序用到了树

6. 堆 heap

算法

1. 什么是算法?

算法的五大特征: 输入 输出 明确性 有限性 有效性(可行性)
有限性 一个算法必须保证执行有限的步之后结束
确切性 一个算法的每一步都必须有确切的意义
输入 一个算法有零个或者一个初始值,以刻画运算对象的初始情况,所谓零个输入是指算法本身给与了初始值
输出 一个算法有一个或者多个输出 没有输出的算法毫无意义
可行性 一个算法的任何步骤都可以被分解为基本可执行的操作,每个操作都能在有限的时间内完成

2. 算法的分类

分治法 
动态规划法 
贪婪算法 
线性规划法 
简并法

3. 关于排序

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 快速排序
  • 桶排序
    • 计数排序 复杂度为 n+max 无法统计负数和小数
    • 基数排序
  • 归并排序
  • 希尔排序
  • 堆排序

4. 一些伪代码

现在感觉写伪代码特别好,以前都懒得写,可能就是想不清楚吧 XD

计数排序

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
a = {
'0': 2,
'1': 34,
'2': 5,
'3': 43,
'4': 98,
'5': 21,
'length': 6
}
hash = {

}
index = 0
while index < a.length
n = a[index]
if hash[n] == undefined
hash[n] = 1
else
hash[n] = hash[n] + 1
end
index = index + 1
end

index2 = 0
new arr = []
while index2 < a的最大值 + 1
count = hash[index2]
if count != undefined
countindex = 0
while countindex < count
arr.push(index2)
countindex + 1
end
end
index2 = index2 + 1
end