数据结构与算法 - 双链表 - 大整数相加

工作中虽然主打 Objc，但是接触 Swift 后就很难回去，在用 Swift 写过一些 Demo 程序时，她的优雅和简练以及它所反映的编程思想深深地让人迷恋。本系列文章会用 Swift 实现一些常见算法，以期待能够在实战中持续学习 Swift 并对基础数据结构算法做整理和回顾。

样式

双链表是在单链表的基础上，扩展了一个前向指针，使得双链表可以在两个方向自由地移动。下面将定义一个存放单个数字的链表，用来展示大整数加法和 LRU 算法。

  1. 每一个节点除了包含数据空间，还必须包含前向和后向的指针。定义节点：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class DigitNode {
        var val: Int!
        var next: DigitNode?
        var previous: DigitNode?
        init(_ val: Int) {
            self.val = val
            self.next = nil
            self.previous = nil
        }
    }

  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
    31
    32
    class DigitList {
        var digitList: DigitNode?
        
        var headerDigit: DigitNode?
        var tailDigit: DigitNode?
        
        var nodesCnt: Int = 0
        
        init(_ numStr:String) throws {
            for s in numStr {
                guard let digit = Int(String(s)) else {
                    throw BigNumberError.InvalidDigit
                }
                
                let digitNode = DigitNode(digit)
                
                if self.headerDigit == nil {
                    self.headerDigit = digitNode
                }
                
                self.tailDigit?.next = digitNode
                digitNode.previous = self.tailDigit
                
                self.tailDigit = digitNode
                self.nodesCnt += 1
            }
        }
    }

    enum BigNumberError: Error {
        case InvalidDigit
    }

组建链表时，时刻注意前向和后向指针的指向，不至于出现野指针、循环指向问题

非负大整数相加

“大整数”使用链表存放，整数相加时，使用竖式计算，从右往左逐位相加，封 10 进一。代码如下：

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
42
extension DigitList {
    // 插入时注意，先准备外围环境(node)，然后再去动 list，最后打扫环境
    static func insertHead(list:DigitList, node:DigitNode){
        node.next = list.headerDigit
        list.headerDigit?.previous = node
        list.headerDigit = node
        node.previous = nil
    }
    
    class func addNode(for list:DigitList, at location:DigitNode, 
                        with val: Int) {
        location.val = location.val + val
        var work = location
        while work.val / 10 != 0 {
            // 位“溢出”了，将当前位置赋值为个位数值，向高位进 1
            work.val = work.val % 10
            if (work.previous != nil) {
                work.previous!.val += 1
                work = work.previous!
            } else {
                // 高位“溢出”：新创建一个 node，插到头部
                let newNode = DigitNode(1)
                DigitList.insertHead(list: list, node: newNode)
                work = newNode
            }
        }
    }
    // 重载 + 。修改了输入的链表，以得到返回值
    static func + (left:DigitList, right:DigitList) throws -> DigitList {
        let longgerList = left.nodesCnt > right.nodesCnt ? left : right
        let shorterList = (longgerList === right ? left : right)
        var workS = shorterList.tailDigit
        var workL = longgerList.tailDigit
        
        while workS != nil {
            DigitList.addNode(for: longgerList, at: workL!, with: workS!.val)
            workS = workS?.previous
            workL = workL?.previous
        }
        return longgerList
    }
}

为了方便打印，添加如下扩展：

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
extension DigitNode {
    func debugDesc() -> String {
        return "\(self.val!)(\(self.address()))"
    }
    func address() -> String {
        return String(format: "%p", unsafeBitCast(self, to: Int.self))
    }
}

extension DigitList {
    func print(verbose:Bool = false) {
        let desc = self.desc(verbose: verbose)
        Swift.print(desc)
        Swift.print("\n")
    }
    
    func desc(verbose:Bool = false) -> String {
        var worker = self.headerDigit
        var result = ""
        while worker != nil {
            if verbose {
                result = result + (worker!.debugDesc() + " ↔ ")
            } else {
                result += "\(worker!.val!)"
            }
            worker = worker?.next
        }
        return result
    }
}

验证代码：

1
2
3
4
5
6
7
8
9
10
11
var bigNumber1 = try DigitList("859743092540326504983725381796084325974835743")
var bigNumber2 = try DigitList("999999999999999999999999999999999999999999999")
var val1Desc = "\(bigNumber1.desc())"
var val2Desc = "\(bigNumber2.desc())"
var result = try bigNumber2 + bigNumber1
var resultDesc = "\(result.desc())"

print("\(val1Desc) + \(val2Desc) = \(resultDesc)")
/* 输出结果：（可使用 python 交互环境验证结果）
859743092540326504983725381796084325974835743 + 999999999999999999999999999999999999999999999 = 1859743092540326504983725381796084325974835742
*/

双链表常用操作

  • 头部插入（如上）

  • 尾部追加

    1
    2
    3
    4
    5
    6
    func appendTail(with node:DigitNode) {
        node.previous = self.tailDigit
        self.tailDigit?.next = node
        self.tailDigit = node
        node.next = nil
    }

  • 中间插入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    // 在 node 节点后面插入新节点 newNode
    func insert(after node:DigitNode?, with newNode:DigitNode)throws -> Bool {
        guard node != nil else {
            throw BigNumberError.NullParamOccur
        }
        var work = self.headerDigit
        while work != nil {
            if work === node {
                // 找到了锚节点，准备插入
                newNode.next = work?.next
                work?.next?.previous = newNode
                work?.next = newNode
                newNode.previous = work
                return true
            }
            work = work?.next
        }
        return false
    }

  • 倒置
    1. 常规方法是使用一个工作指针，指向头部，然后顺次滑向尾部，逐个 node 操作：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      func reverse1() {
          var workNode = self.headerDigit?.next
          if workNode?.next == nil {
              return
          }
          // 尾部指针直接指向新的头部
          self.tailDigit = self.headerDigit
          while workNode != nil {
              let formerNext = workNode?.next
              
              workNode?.next = self.headerDigit
              self.headerDigit?.previous = workNode
              
              self.headerDigit = workNode
              workNode = formerNext
          }
          
          self.headerDigit?.previous = nil
          self.tailDigit?.next = nil
      }
    2. 示例中的链表记录了元素个数，可以使用折半交换的方式倒置，效率比常规方法高
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      func reverse2(){
          var tempHeade = self.headerDigit
          var tempTail = self.tailDigit
          var tempCnt = 0
          while tempCnt < self.nodesCnt / 2 {
              let val = tempHeade?.val
              tempHeade?.val = tempTail?.val
              tempTail?.val = val
              tempCnt += 1
              
              tempHeade = tempHeade?.next
              tempTail = tempTail?.previous
          }
      }

LRU

数据结构与算法 - 双链表（LRU）