关于数据结构的一点唠叨
现在大部分高级编程语言的标准库都会提供几种常用的数据结构，诸如线性表、链表、栈、队列、哈希表等等，可以满足日常开发中的大部分需求，开发人员只要调用接口就行了。这导致有一些半路出家的程序员觉得学习数据结构没有必要，更有甚者，不仅自身满足于成为一个API Caller，还对外大肆宣扬底层无用论，误导了一些心存迷茫的初学者。
其实哪怕从实用的角度讲，学习数据结构也是非常必要的。至少了解每种数据结构的特性，对于其优缺点和适用场景做到心中有数，在使用的时候才能得心应手。举个最简单的例子，我们知道线性表中的元素在空间上是连续的，对其进行查找操作十分方便，但若是要进行插入和删除操作，则需要移动其中的元素，在数据量非常大的时候效率并不高；相反，链表中的元素是通过指针相连，在空间上并不连续，查找的时候需要从首元素开始通过指针进行，效率并不高，但在插入和删除时，只需要改变目标位置的指针即可，并不需要移动元素。所以对于只需要查询或修改操作的数据当然是使用线性表为好，而对于需要进行大量增删操作的数据，则使用链表为宜，在实际开发中应根据具体情况进行选择权衡。若是对数据结构一无所知，那写出的代码质量着实令人堪忧。出来混，迟早是要还的。
在我的理解中，编程，其实就是个建模+实现的过程。现在最主流的编程范式是FP（函数式编程）和OOP（面向对象编程），当然最流行的还是OOP，鼓吹的人非常多，说得神乎其神，搞得很多初学者云里雾里，油然而生一股不明觉厉之情，忍不住就要顶礼膜拜，我当初也是如此，想来真是不胜唏嘘。其实FP和OOP最根本的区别在于建模的角度不同，FP是要把现实问题抽象成数学模型，只有代入，没有赋值，具有引用透明性（简单来说就是同样的输入会产生同样的结果），不产生副作用（副作用主要指改变系统状态）。与之相对的是命令式编程范式，广泛采用赋值，用数据的变化来模拟真实世界的状态变化。OOP是命令式编程的一种，它直观地将现实中的事物抽象成对象模型，对象具有内部状态和特定行为。
市面上的面向对象语言中都有类(class)的概念，类内部封装了一些属性（有些语言没有属性，只有字段）和方法。但是类究竟是什么呢？它其实就是一种数据类型，而一般我们所说的接口(interface)，便相当于抽象数据类型（Abstract Data Type， ADT）。数据类型、抽象数据类型和数据结构听着有点像，但它们还是不一样的：
- 数据结构：用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。逻辑上的数据结构反映成分数据之间的逻辑关系，物理上的数据结构反映成分数据在计算机内的存储安排。数据结构是数据存在的形式。
- 数据类型：数据按照进行数据结构分类，具有相同数据结构的数据属同一类。同一类数据的全体称为数据类型。
- 抽象数据类型：一个数学模型以及定义在此数学模型上的一组操作。可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算封装在一起。
我们口中常说的数据结构，其实大部分时候都是指抽象数据类型，比如我们说到栈(Stack)的时候，是指一种具有push和pop操作，数据遵循先进后出顺序的ADT。所以我们当然可以定义一个叫Stack的类，去实现push和pop操作，无论具体实现细节是怎样的，它都可以称为栈。而我们实例化一个对象的时候，便是申请了一块内存空间，里面保存了：
- 类中定义的一些基本数据类型(或者其他值类型)的拷贝
- 指向函数（或称方法）和其他对象的指针
上面两点说的都是类中定义的成员变量和成员方法，具体的实现不同的语言会有些差别。至于静态变量和静态方法跟对象并没有关系，它们其实相当于是全局的，类名只是起到了命名空间的作用。
说了这么多，顺便也说说Swift中的类型吧，Swift中的class、struct、enum、closure都是数据类型，至于协议protocol就是抽象数据类型了。一个protocol定义一组数据和操作，可以被class、struct、enum实现。至于集合类型，Swift中原生的有三种——Array、Set和Dictionary，平常开发基本已经够用了，但是如果我们想要实现诸如Stack、Queue这样的数据结构，也是非常方便的：
//栈
struct Stack<T> {
var items = [T]()
//栈顶指针
var top: Int {
return items.count - 1
}
var isEmpty: Bool {
return items.isEmpty
}
//加上mutating才能改变struct中的属性
//因为struct是值类型，默认是不可变的
mutating func push(item: T) {
items.append(item)
}
mutating func pop() -> T {
return items.removeLast()
}
}
//队列
struct Queue<T> {
var items = [T]()
//入队
mutating func enqueue(item: T) {
items.append(item)
}
mutating func dequeue(item: T) -> T {
return items.removeFirst()
}
}这里我使用了范型，这样Stack和Queue中的元素就可以为任意类型，而且保证了类型安全,譬如
var intStack = Stack<Int>()
intStack.push(1)
intStack.push(2)
let topElement = intStack.pop() //topElement = 2
var stringQueue = Queue<String>()
stringQueue.enqueue("Swift")
stringQueue.enqueue("C#")
let str= stringQueue.dequeue() //str = "Swift"Swift不直接支持指针，但是class是引用类型，对于实现链表、二叉树这样的基于指针的数据结构来说，也够用了。下面是链表的Swift实现：
//节点(只能用class，struct不支持类型嵌套，也就是Node<T>内部不能声明类型为Node<T>的属性)
class Node<T: Equatable> {
var value: T?
var next: Node<T>!
var prev: Node<T>!
init(value: T?) {
self.value = value
}
}
//带哨兵(nilNode)的链表，没有head和tail
class LinkedList<T: Equatable> {
var nilNode: Node<T>
init() {
nilNode = Node<T>(value: nil)
nilNode.next = nilNode
nilNode.prev = nilNode
}
//线性搜索
func search(value: T) -> Node<T> {
var node = nilNode.next
//node.value为空则说明node是nilNode，因为其他节点的value都由值
while let v = node.value {
if v != value {
node = node.next
} else {
break
}
}
return node
}
//插入到nilNode之后
func insert(value: T) {
let node = Node<T>(value: value)
node.next = nilNode.next
nilNode.next.prev = node
nilNode.next = node
node.prev = nilNode
}
func delete(value: T) {
let node = search(value)
assert(node.value != nil, "Value not found in LinkedList.")
node.prev.next = node.next
node.next.prev = node.prev
}
}二叉树的三种遍历方式：
class Tree<T: Equatable> {
var value: T
var leftChild: Tree<T>!
var rightChild: Tree<T>!
init(value: T) {
self.value = value
}
}
//树中序遍历
func inorderTreeWalk<T>(tree: Tree<T>?) {
guard let node = tree else {
return
}
inorderTreeWalk(node.leftChild)
print(node.value)
inorderTreeWalk(node.rightChild)
}
//前序
func preorderTreeWalk<T>(tree: Tree<T>?) {
guard let node = tree else {
return
}
print(node.value)
preorderTreeWalk(node.leftChild)
preorderTreeWalk(node.rightChild)
}
//后序
func postorderTreeWalk<T>(tree: Tree<T>?) {
guard let node = tree else {
return
}
postorderTreeWalk(node.leftChild)
postorderTreeWalk(node.rightChild)
print(node.value)
}以Int类型为键的哈希表：
struct Element<T: Equatable>: Equatable {
var key: Int?
var value: T?
init(key: Int?, value: T?) {
self.key = key
self.value = value
}
}
func ==<T>(lhs: Element<T>, rhs: Element<T>) -> Bool {
return lhs.key == rhs.key && lhs.value == rhs.value
}
//哈希表
struct HashTable<T: Equatable> {
typealias E = Element<T>
var size: Int
var memory : [LinkedList<E>?]
init(size: Int) {
self.size = size
memory = [LinkedList<E>?](count: size, repeatedValue: nil)
}
//假定关键字都是Int
func hash(key: Int) -> Int {
return key % size
}
subscript(key: Int) -> T? {
get {
guard let linkedList = memory[hash(key)] else {
return nil
}
let element = Element<T>(key: key, value: nil)
return linkedList.search(element).value?.value
}
set {
let element = Element<T>(key: key, value: newValue)
let linkedList = memory[hash(key)] ?? LinkedList<E>()
linkedList.insert(element)
memory[hash(key)] = linkedList
}
}
// mutating func insert(key: Int, value: T) {
// memory[hash(key)] = value
// }
}这段哈希表代码有一些需要说明的地方：
- 对于存入哈希表中的元素，我定义了一个
Element类型，它实现了Equatable协议，表明是可判等的，然后再重载==操作符，就可以用==符号来对两个Element类型的实例进行比较了。同时也使用了范型，范型类型也必须是实现了Equatable协议的类型，譬如Element<Int>、Element<String>都可以。 - 在哈希表中我使用了一个最简单的哈希函数，就是一个取模操作。对于碰撞冲突(不同的key值经过
hash函数处理后返回了相同的地址)的处理我使用了链接法，也就是说哈希表的每个槽都保存了一个链表，多个值被哈希到同一个地址的话就都保存在链表中。碰撞处理还可以使用开放寻址法，就是一旦哈希到相同的地址就用不同的哈希函数再进行哈希，直到找到一个空的地址，不过在实践中使用得较少，一般还是使用链接法。 - 自定义下标，可以通过下标直接操作哈希表：
var hashTable = HashTable<Int>(size: 10)
hashTable[1] = 20
let value1 = hashTable[1] //value1 = 20
let value2 = hashTable[33] //value2 = nil上次我写快排的时候提到过，除了快排之外，还有两种算法的时间复杂度也是O(nlgn)，就是归并排序和堆排序。虽然在实践中，快排和归并排序的效果更好些，大部分语言的标准库中提供的sort函数也是使用这两种算法或其中一种。但是堆排序中构建的堆却是一种非常实用的数据结构，这个堆不是垃圾回收机制(GC)中的堆，而是一种完全二叉树。它不仅可以用在堆排中，还可以用来构造一种有效的优先队列。先看看堆排吧，我同样用Swift实现了一下：
//二叉堆基本操作
func parent(index: Int) -> Int {
return (index - 1) / 2
}
func leftChild(index: Int) -> Int {
return 2 * index + 1
}
func rightChild(index: Int) -> Int {
return 2 * index + 2
}
var heapSize = 0
//维护最大堆性质
func maxHeapity(inout maxHeap: [Int], index: Int) {
let left = leftChild(index)
let right = rightChild(index)
//在index，left，right三者中取最大值
var largest = (left < heapSize && maxHeap[left] > maxHeap[index]) ? left : index
largest = (right < heapSize && maxHeap[right] > maxHeap[largest]) ? right : largest
if largest != index {
(maxHeap[index], maxHeap[largest]) = (maxHeap[largest], maxHeap[index])
maxHeapity(&maxHeap, index: largest)
}
}
//建堆
func buildMaxHeap(inout list: [Int]) {
heapSize = list.count
var index = list.count/2 - 1
//index+1...endIndex都是叶子节点
while index >= 0 {
maxHeapity(&list, index: index--)
}
}
//堆排序
func heapSort(inout list: [Int]) {
buildMaxHeap(&list)
var endIndex = heapSize - 1
while endIndex > 0 {
//将最大元素换到底部
(list[0], list[endIndex--]) = (list[endIndex], list[0])
//将底部元素从堆中移除
heapSize--
//重新维持最大堆性质
maxHeapity(&list, index: 0)
}
}
//test
var testList = [27, 999, 77, 5, 90, 63, 11, 8]
heapSort(&testList)这里我构建了一个最大堆，最大堆的性质就一条：maxHeap[parent(i)] >= maxHeap[i]，也就是说父节点不小于孩子节点；同理，最小堆的性质是minHeap[parent(i)] <= minHeap[i]。
优先队列是一种用来维护一组含关键字(用key表示)的元素的数据结构。一个最大优先队列支持以下操作：
- insert(element)：插入一个元素element
- maximum：返回具有最大关键字的元素
- extract-max：去掉并返回最大关键的元素
- increase-key(element, k)：将元素element的关键字增加到k，k >= element.key
最大优先队列的应用很多，譬如系统的作业调度，最大优先队列记录并维护将要执行的各个任务以及它们之间的相对优先级，当一个任务完成或中断后，调度器调用extract-max从所有的等待任务中选出具有最高优先级的任务执行。在任何时候，调度器都可以调用insert把一个新任务加入队列。
最小优先队列支持的操作包括insert、minimum、extract-min和decrease-key。最小优先队列可以被用于基于事件驱动的模拟器。队列中保存事件，每个事件都有一个发生时间作为其关键字key。事件按照时间顺序进行，每次调用extract-min返回队列中具有最小时间的事件。新事件产生时，模拟器调用insert进行插入。
显然优先队列可以用堆轻易实现，而且十分高效。我就不给出代码了，好困好想睡觉。。。
IT界每天都有新技术出现，但其实很多东西都换汤不换药，都是在炒冷饭，我们不应该被种种表象迷惑而疲于奔命。打好基础，慢慢地就会摸到整个体系的脉络，去芜存菁，才能在这不进则退的信息化浪潮中安然立世。