大部分内容来自于《大话数据结构》，代码全部使用Swift实现。至于为什么抽风写这个？😊你懂的。

1.线性表

线性表：零个或者多个数据元素的有限序列。

性质：

  • 数据元素可以为空
  • 数据元素有限
  • 数据元素之间的逻辑结构为线性结构，也就是一对一的关系
  • 数据元素类型相同
  1. 举个例子：
  2. 白羊 -> 金牛 -> 双子 -> 巨蟹 -> 狮子 -> 处女 -> 天秤 -> 射手 -> 摩羯 -> 水平 -> 双鱼
  4. 线性表的抽象数据类型：
  5. ADT 线性表（List）
  6. Data
  7.       线性表的数据对象集合为{a1, a2, ......, an}，每一个元素的类型都是DataType。其中，除第一个元素a1外，每一个元素有且仅有一个直接前驱元素，除了最后一个元素an外，每一个元素有且仅有一个直接后续元素。数据元素之间的关系是一对一的关系。
  8. Operation
  9.        count：线性表元素个数。
  10.        first：头指针。
  11.        last：尾指针。
  12.        isEmpty()：若线性表为空，返回true，否则返回false。
  13.        remove()：将线性表清空
  14.        node(i)：将线性表中的第i个位置的元素返回。
  15.        insert(data,i)：在线性表中的第i个位置插入新数据data。
  16. EndADT

线性表根据在计算机的储存方式可以分为两种：

  • 顺序线性表
  • 链式线性表

顺序线性表

顺序线性表：使用一段连续的地址存储单元放置线性表的数据元素。

举个例子：数组。

  1. 顺序线性表的优缺点：
  2. 优点：
  3. - 可以快速获取下标的数据元素，时间复杂度为O(1)
  4. - 逻辑关系是一对一的关系，连续存储单元足以储存，不需要增加额外的存储空间
  6. 缺点：
  7. - 插入和删除操作需要移动大量的元素，时间复杂度为O(n)
  8. - 线性表的存储空间大小难以确定，并且不好扩展
  9. - 造成存储空间碎片

链式线性表

链式线性表：线性表的数据元素可以存储在随意的存储单元，每一个节点不仅仅包括数据元素还有一个指向下一个节点的指针（基本的单链表）。

链式（单链表）和顺序线性表优缺点对比：

  1. 存储分配方式：
  2. - 顺序 -> 一段地址连续的存储空间
  3. - 链式 -> 任意地址存储空间
  5. 时间性能：
  6. - 查找
  7.   顺序 -> O(1)
  8.   链式 -> O(n)
  9. - 插入和删除
  10.   顺序 -> O(n)
  11.   链式 -> 寻找相应的节点，时间复杂度为O(n)，然后，插入和删除为O(1)
  13. 空间性能：
  14. - 顺序 -> 需要提前分配存储空间，分配大了，浪费空间，分配小了，容易发生上溢
  15. - 链式 -> 不需要提前分配空间，只要有存储空间分配就行，数据元素个数只受可分配存储空间大小的限制

总结：
（1）若线性表需要频繁查找，很少进行插入和删除操作时，使用顺序存储结构；反之，使用链式存储结构。
（2）如果提前知道线性表需要的存储空间，可以使用顺序结构；如果不知道线性表中的数据元素变化有多大，即不确定需要多大的存储空间，则使用链式存储结构。

链式线性表的基本分类：

  • 单向链表
  • 静态链表 -> 使用顺序结构实现链式线性表
  • 双向链表 -> 每个节点除了数据元素，还包含一个指向上一个节点的指针和一个指向下一个节点的指针
  • 循环链表 -> 线性表的尾部指向头节点，形成一个闭环

下面具体讲解双链表的Swift实现，其他的链表实现可以参考《大话数据结构》或者自行Googel/Baidu。

双向链表：在单链表的基础上，每个节点加一个指向上一个节点的指针。

节点定义：

  1. public class LinkedListNode<T> {
  2.     var data: T  //Data could not be nil.
  3.     var previous: LinkedListNode?  //The pointer to previous node.
  4.     var next: LinkedListNode?  //The pointer to next node.
  5.     init(_ data: T) {
  6.         self.data = data
  7.     }
  8. }

双向链表：

  1. public enum ErrorStatus {
  2.     case Error(message: String)
  3.     case OK
  4. }
  6. public class DoubleLinkedList<T> {
  7.     public typealias Node = LinkedListNode<T>
  9.     private var head: Node?  //Head node of link list.
  11.     public var isEmpty: Bool {  //If link list has no data, return true.
  12.         return head == nil
  13.     }
  15.     public var first: Node? {  //Get first node is the head of link list.
  16.         return head
  17.     }
  19.     public var last: Node? {  //Last node of link list.
  20.         ...
  21.         return node
  22.     }
  24.     public var count: Int {  //Retrun link list's nodes count.
  25.         ...
  26.         return count
  27.     }
  29.     public func node(atIndex index: Int) -> Node? {  //Get node with index
  30.         ...
  31.         return node
  32.     }
  34.     public func appendData(data: T) {  //Append data to link list tail
  35.         ...
  36.     }
  38.     public func insert(data: T, atIndex index: Int) -> ErrorStatus {  //Insert data at index
  39.         guard index >= 0, index <= count else {
  40.             return ErrorStatus.Error(message: "Index is out of range!")
  41.         }
  42.         let newNode = Node(data)
  43.         if index == 0 {
  44.             if let node = first {
  45.                 head = newNode
  46.                 newNode.next = node
  47.                 node.previous = newNode
  48.             } else {
  49.                 head = newNode
  50.             }
  51.         } else {
  52.             let node = self.node(atIndex: index-1)
  53.             let nextNode = self.node(atIndex: index)
  54.             node?.next = newNode
  55.             newNode.previous = node
  56.             newNode.next = nextNode
  57.             nextNode?.previous = newNode
  58.         }
  59.         return ErrorStatus.OK
  60.     }
  62.     public func remove(atIndex index: Int) -> (T?, ErrorStatus) {  //Remove node at index
  63.         guard !isEmpty else {
  64.             return (nil, ErrorStatus.Error(message: "Link list is Empty!"))
  65.         }
  67.         guard index >= 0, index < count else {
  68.             return (nil, ErrorStatus.Error(message: "Index is out of range!"))
  69.         }
  71.         let node = self.node(atIndex: index)
  72.         let nextNode = self.node(atIndex: index+1)
  73.         if index == 0 {
  74.             head = nextNode
  75.         } else {
  76.             let beforeNode = self.node(atIndex: index-1)
  77.             beforeNode?.next = nextNode
  78.             nextNode?.previous = beforeNode
  79.         }
  80.         return (node?.data, ErrorStatus.OK)
  81.     }    
  82. }

⚠️注意：
这里的head指向第一个有数据的节点，有的线性表会生成一个头节点，该节点不存储任何数据或者只存储该链表的长度，该节点指向第一个有数据的节点。这样做的好处就是，第一个节点的删除和插入操作和其他节点保持一致。

下面主要解释一下，插入和删除操作：

  • insert
  1. public func insert(data: T, atIndex index: Int) -> ErrorStatus {  //Insert data at index
  2.     guard index >= 0, index <= count else {
  3.         return ErrorStatus.Error(message: "Index is out of range!")
  4.     }
  5.     let newNode = Node(data)
  6.     if index == 0 {
  7.         if let node = first {
  8.             head = newNode
  9.             newNode.next = node
  10.             node.previous = newNode
  11.         } else {
  12.             head = newNode
  13.         }
  14.     } else {
  15.         let node = self.node(atIndex: index-1)
  16.         let nextNode = self.node(atIndex: index)
  17.         node?.next = newNode
  18.         newNode.next = nextNode
  19.         newNode.previous = node
  20.         nextNode?.previous = newNode
  21.     }
  22.     return ErrorStatus.OK
  23. }

1.先判断需要插入数据的index是否在[0, count]的范围之内，注意这里是方括号，也就是包含边界，因为线性表最前面和最后面都可以插入新的数据。
2.生成新节点。
3.因为这里的双向链表没有采取头节点的方式实现，所以，插入第一个节点和其他节点有点不一样，需要做一些判断。
4.如果是插入第一个节点，则判断如果该链表为空，则直接设置head=newNode；如果该链表不为空，则将一个节点赋值给node，然后将newNode赋值给head，接着将node赋值给newNode.next，最后设置node.previous=newNode。
5.如果不是插入一个节点，则先获取下标为index-1的节点node，然后获取下标为index的节点nextNode。设置node.next=newNode，然后newNode.next=nextNode，连成一条指向下一个数据元素的链，最后设置newNode.previous=node和nextNode.previous=newNode连上指向上一个数据元素的链，自此，先的数据插入成功。

  • remove
    无论insert还是remove都是先拆链，然后再组合成新的数据链。
  1. public func remove(atIndex index: Int) -> (T?, ErrorStatus) {  //Remove node at index
  2.     guard !isEmpty else {
  3.         return (nil, ErrorStatus.Error(message: "Link list is Empty!"))
  4.     }
  6.     guard index >= 0, index < count else {
  7.         return (nil, ErrorStatus.Error(message: "Index is out of range!"))
  8.     }
  10.     let node = self.node(atIndex: index)
  11.     let nextNode = self.node(atIndex: index+1)
  12.     if index == 0 {
  13.         head = nextNode
  14.     } else {
  15.         let beforeNode = self.node(atIndex: index-1)
  16.         beforeNode?.next = nextNode
  17.         nextNode?.previous = beforeNode
  18.     }
  19.     return (node?.data, ErrorStatus.OK)
  20. }

1.先判断是否是空链，如果是则返回，否则再判断需要删除数据的小表是否在合理范围内，如果不是则返回。
2.判断index是否等于0，如果是，则直接将head=secondNode。
3.获取beforeNode和nextNode，然后将beforeNode.next=nextNode，nextNode,previous=beforeNode，自此，下标为index的节点，没有任何对象指向它，在当前函数域外就外被系统回收掉。

2.栈与队列

栈：限定在表尾进行插入和删除的线性表。

栈是一种LIFO(Last In First Out)的线性表，也就是数据元素遵循后进先出的原则。

栈的抽象数据类型：

  1. ADT 栈(Stack)
  2. Data
  3.       具有线性表一样的性质。
  4. Operation
  5.       top：获取栈顶元素
  6.       count：栈的长度
  7.       isEmpty：栈内元素是否为空
  8.       push(data)：元素进栈
  9.       pop()：元素出栈
  10.       removeAll()：清空栈内元素
  11. EndADT

按栈的存储结构分类：

  • 栈的顺序存储结构
    单栈
    共享栈
  • 栈的链式存储结构

共享栈：
两个顺序栈共享存储空间，栈1的栈顶在下标0处，栈2的栈顶在下标n-1处。

  1. 栈的顺序结构和链式结构区别：
  2. 1.顺序结构需要预先估算存储空间大小，适合数据元素变化不大的情况
  3. 2.链式结构不需要预先估算存储空间，适合数据元素变化较大的情况

栈的链式结构实现：

  1. public struct Stack<T> {
  2.     private var stackData: [T] = []
  4.     public var count: Int {
  5.         return stackData.count
  6.     }
  8.     public var top: T? {
  9.         if isEmpty {
  10.             return nil
  11.         } else {
  12.             return stackData.last
  13.         }
  14.     }
  16.     public var isEmpty: Bool {
  17.         return stackData.isEmpty
  18.     }
  20.     public mutating func push(data: T) {
  21.         stackData.append(data)
  22.     }
  24.     public mutating func pop() -> T? {
  25.         if isEmpty {
  26.             return nil
  27.         } else {
  28.             return stackData.removeLast()
  29.         }
  30.     }
  32.     public mutating func removeAll() {
  33.         stackData.removeAll()
  34.     }
  36.     public func printAllData() {
  37.         for item in stackData {
  38.             print(item)
  39.         }
  40.     }
  41. }

上面的代码写的非常清楚，一目了然，这里就不费口舌了。

栈较之线性表有什么特别作用？😊

栈和线性表的不同之处在于，栈只有进栈和出栈操作，并且遵循后进先出的规则，也就是说数据元素顺序进栈，逆序出栈。嘿嘿，栈可以实现回退操作，递归和四则运算等等。

  • 递归
    听说过斐波那契数列吗？😏没错就是兔子繁殖🐰： | 所经过的月数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | :—- | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | | 兔子对数 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 |

以月数为自变量，兔子的对数为因变量，则它们之间的关系为：

  1. F(0) = 0, n=0
  2. F(1) = 1, n=1
  3. F(n) = F(n-1) + F(n-2), n>1

下面使用常规的方法解决这个问题：

  1. func rabbitNumbers() {
  2.     //After 40 months
  3.     var r0 = 0
  4.     print("rabbit: \(r0)")
  5.     var r1 = 1
  6.     print("rabbit: \(r1)")
  7.     var r: Int = 0
  8.     for _ in 2..<40 {
  9.         r = r0 + r1
  10.         print("rabbit: \(r)")
  11.         r0 = r1
  12.         r1 = r
  13.     }
  14. }

再者使用递归解决这个问题：

  1. func rabbitNumbers(months n: Int) -> Int {
  2.     if n < 2 {
  3.         return n
  4.     }
  5.     return rabbitNumbers(months: n-1)+rabbitNumbers(months: n-2)
  6. }
  8. for i in 0..<40 {
  9.     let rabbits = rabbitNumbers(months: i)
  10.     print("rabbit: \(rabbits)")
  11. }

比较一下前面两个的差异：

  1. 常规方法：
  2.     使用一个迭代的方式，计算出结果。不需要反复调用函数，浪费内存。但是，相对于递归来说，没有那么简洁。
  3. 递归：
  4.     递归就需要不断调用函数，建立函数副本，消耗大量的内存。但是，相对于常规方法，代码简洁易懂。

为什么说递归是栈的应用呢？
递归在执行的时候，需要不断的调用自身，直到可以返回确定的值，然后，又从最后面的一层，一层层往回调，直到最上一层，这个两个操作正好对应着栈的压栈和出栈的操作。其实，编译器也是这样干的，在前行阶段，对于每一层递归，函数的局部变量，参数值和返回地址都压进栈；在退回阶段，位于栈顶的局部变量，参数值以及返回地址都被弹出，用于返回调用层次中执行代码的剩余部分，恢复调用状态。

  • 四则运算
    四则运算就有意思了。自己用笔和纸算数学题知道怎么做，但是计算机呢？怎么算加减乘除的？毕竟计算机只能识别0和1。😊

一般手动计算数学题我们用的是中缀表达法（符号在需要运算的数字中间）：

  1. 9 + (3 - 1) * 3 + 10 / 2

计算机运算需要用到的后缀表达法（去调括号，符号在需要运算的数字后面）：

  1. 9 3 1 - 3 * + 10 2 / +

所以？怎么得到后缀表达式呢？利用栈：

  1. 规则：
  2. 1.遇到数字，直接输出
  3. 2.遇到左括号进栈
  4. 3.遇到右括号执行出栈操作，直到弹出左括号，左括号和右括号不输出
  5. 4.遇到其他操作符，则判断其与栈顶操作符的优先级，如果其优先级（<=）栈顶操作符，则栈顶元素依次出栈，该操作符进栈
  6. 5.直到最后，将栈中的元素依次输出
  8. enum OperationPriority: String {
  9.     case multi = "*"
  10.     case divide = "/"
  11.     case add = "+"
  12.     case sub = "-"
  14.     var intValue: Int {
  15.         switch self {
  16.         case .multi,.divide:
  17.             return 1
  18.         case .add, .sub:
  19.             return 0
  20.         }
  21.     }
  22. }
  24. func suffixExpFromMiddleExp(exps: Array<String>) -> Array<String>{
  25.     var suffixExp: [String] = Array()
  26.     var stack = Stack<String>()
  27.     let predicate = NSPredicate.init(format: "SELF MATCHES %@", "^[0-9]*$")
  28.     for value in exps {
  29.         if predicate.evaluate(with: value) {
  30.             suffixExp.append(value)
  31.         } else if value == "(" {
  32.             stack.push(data: value)
  33.         } else if value == ")" {
  34.             while stack.top != "(" {
  35.                 suffixExp.append(stack.pop() ?? "")
  36.             }
  37.             if stack.top == "(" {
  38.                 stack.pop()
  39.             }
  40.         } else {
  41.             //value <= top, stack.pop;value > top, stack.push
  42.             let advantage = OperationPriority.init(rawValue: value)?.intValue ?? 0
  43.             var topAdvantage: Int = 0
  44.             while let top = stack.top, top != "(" {
  45.                 topAdvantage = OperationPriority.init(rawValue: top)?.intValue ?? 0
  46.                 if advantage > topAdvantage {
  47.                     break
  48.                 } else {
  49.                     suffixExp.append(top)
  50.                     stack.pop()
  51.                 }
  52.             }
  53.             stack.push(data: value)
  54.         }
  55.     }
  56.     while let top = stack.top {
  57.         suffixExp.append(top)
  58.         stack.pop()
  59.     }
  60.     return suffixExp
  61. }
  63. let exp = ["9", "+", "(", "3", "-", "1", ")", "*", "3", "+", "10", "/", "2"]  
  64. //中缀表达式：9+(3-1)*3+10/2
  65. //后缀表达式：9 3 1 - 3 * + 10 2 / +

注：后缀表达式更多获取方法。

得到了后缀表达式，那么开始我们的四则运算了。😊

  1. 规则：
  2. 1.数字直接进栈
  3. 2.遇到符号，将栈顶两个数字出栈，进行运算，运算结果进栈
  5. //在上面的枚举加一个计算加减乘除的函数
  6. enum OperationPriority: String {
  7.     ...
  8.     func result(operator1: String, operator2: String) -> Int {
  9.         switch self {
  10.         case .multi:
  11.             return Int(operator1)!*Int(operator2)!
  12.         case .divide:
  13.             return Int(operator1)!/Int(operator2)!
  14.         case .add:
  15.             return Int(operator1)!+Int(operator2)!
  16.         case .sub:
  17.             return Int(operator1)!-Int(operator2)!
  18.         }
  19.     }
  20. }
  22. func mathOperation(exps: Array<String>) -> Int {
  23.     var result = 0
  24.     var stack = Stack<String>()
  25.     let predicate = NSPredicate.init(format: "SELF MATCHES %@", "^[0-9]*$")
  26.     for value in exps {
  27.         if predicate.evaluate(with: value) {
  28.             stack.push(data: value)
  29.         } else {
  30.             let operator2 = stack.pop()
  31.             let operator1 = stack.pop()
  32.             let temp = (OperationPriority.init(rawValue: value)?.result(operator1: operator1!, operator2: operator2!))!
  33.             stack.push(data: "\(temp)")
  34.         }
  35.     }
  36.     if let resultStr = stack.pop() {
  37.         result = Int(resultStr)!
  38.     }
  39.     return result
  40. }
  41. let exp = ["9", "+", "(", "3", "-", "1", ")", "*", "3", "+", "10", "/", "2"]  
  42. //result=20

是不是很有意思，一个简单的四则运算就这样实现出来了。栈在计算机里面用的挺多的，比如，系统管理的对象就是放进一个全局栈里面的，等不需要的时候，一个一个出栈，释放所占的内存。

队列：只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列其实和显示社会排队买东西的队列一个道理，都是一边进，一边出，插队是会被所有人鄙视的😒，慎重。

队列的抽象数据类型：

  1. ADT 队列(Queue)
  2. Data
  3.     具有线性表一样的性质。
  4. Operation
  5.     front：队列第一个数据
  6.     count：队列的长度
  7.     isEmpty()：队列是否为空
  8.     enQueue(data)：数据进队列
  9.     deQueue()：数据出队列
  10.     removeAll()：清空队列内的所有数据
  11. EndADT

按线性表的存储结构分类：

  • 线性存储结构
    顺序队列
    循环顺序队列
  • 链式存储结构
    链式队列
  1. 顺序队列：就是使用数组来模拟队列，但是数组的插入和删除需要移动数据，比较繁琐。
  2. 循环顺序队列：在顺序队列的基础上改造，使队列的队头和队尾可以在数组中循环变化，在数据插入和删除就不需要频繁移动数据了。但是顺序队列，都需要提前申请存储空间，还有溢出的可能。
  3. 链式队列：为了解决顺序队列的不足，引用链式队列。不需要提前申请空间，只不过会引入频繁申请和释放的操作。

队列的链式结构实现：

  1. public struct Queue<T> {
  2.     private var queueData: [T] = []
  4.     public var front: T? {
  5.         return queueData.first
  6.     }
  8.     public var isEmpty: Bool {
  9.         return queueData.isEmpty
  10.     }
  12.     public var count: Int {
  13.         return queueData.count
  14.     }
  16.     public mutating func enQueue(_ data: T) {
  17.         queueData.append(data)
  18.     }
  20.     public mutating func deQueue() -> T? {
  21.         if isEmpty {
  22.             return nil
  23.         } else {
  24.             return queueData.removeFirst()
  25.         }
  26.     }
  28.     public mutating func removeAll() {
  29.         queueData.removeAll()
  30.     }
  32.     public func printAllData() {
  33.         for value in queueData {
  34.             print(value)
  35.         }
  36.     }
  37. }

队列有什么作用？
在开发过程中，接触最多的应该是全局并发队列。为什么要用队列实现呢？在我看来，在线程的优先级一样的情况下，不应该先申请系统资源的先被满足吗？这和在银行排队取钱是一个道理。当然，VIP就可以无视我们这些在前台排队取钱的渣渣，他们有专门的通道，多么痛的领悟😓。

3.串

串：是由零个或多个字符组成的有限序列，又叫字符串。

字符串在开发的时候很常用，以Objective-C为例，有可变字符串和不可变字符串，两者的实现数据结构应该有点区别；一个是链式存储结构，一个是顺序存储结构。

字符串的抽象数据类型：

  1. ADT 串（String）
  2. Data
  3.     串中元素仅由一个字符组成，相邻元素具有前驱和后续关系。
  4. Operation
  5.     StringEmpty(S)：若串S为空，返回true，否则返回false。
  6.     ...
  7. EndADT

按存储结构分类：

  • 顺序存储结构的字符串
  • 链式存储结构的字符串

字符串的模式匹配
朴素的模式匹配算法：核心思想，需要匹配的字符串和主串从下标0开始匹配，一旦子串不匹配，则子串又从下标0开始匹配，主串则挪到下标1，不断的循环这个过程，直到主串或者字串当前的下标超过字符串的长度或者匹配成功返回。

  1. let s = "goodgoogle"
  2. let t = "google"
  4. func matchString(s: String, t: String) -> Int {
  5.     var post: Int = -1
  6.     guard !s.isEmpty || !t.isEmpty else {
  7.         return post
  8.     }
  10.     var i = 0  //s current index
  11.     var j = 0  //t current index
  13.     while i < s.count, j < t.count {
  14.         let sIndex = s.index(s.startIndex, offsetBy: i)
  15.         let tIndex = t.index(t.startIndex, offsetBy: j)
  16.         let sStr = s[sIndex]
  17.         let tStr = t[tIndex]
  18.         if sStr == tStr {
  19.             i = i+1
  20.             j = j+1
  21.         } else {
  22.             i = i-j+1
  23.             j = 0
  24.         }
  25.     }
  26.     if j > t.count-1 {
  27.         post = i-t.count
  28.     }
  29.     return post
  30. }

朴素的模式匹配，虽然，简单明了，但是效率低。所以，强大的KMP模式匹配算法就应运而生了。
强大的KMP算法，这个可以看我之前写的KMP字符串匹配算法，这里就不做详细的介绍了。