去年对设计模式有了一些浅显的知识, 今年来学习下数据结构与算法, 为了学习以后的先进技术打好基础. 本文包括队列, 栈, 线性表, 树, 图, 五个部分来学习编程的基础, 也复习下Swift的语法.
数据结构和算法和设计模式相同, 属于编程的软实力, 并不局限于语言, 而着重于思想, 本文就是通过学习总结将C++实现的算法迁移到Swift的过程并了解具体的实现.
队列
首先, 我们第一个就要学习的就是队列这个数据结构, 队列, 顾名思义就是排队, 也就是先进先出, 我们这里通过Swift来实现一个队列, 来更好的了解这个数据结构.
private var capacity: Int //队列的容量大小限制.
private lazy var head: Int = 0 //队列头
private lazy var tail: Int = 0 //队列尾
private lazy var length: Int = 0 //队列长度
private lazy var queue: [Element] = [Element]() //队列数组
我们需要定义一些成员变量来控制这个队列, 我们实现的这个队列比较特殊, 并不是一个线性队列, 而是环形队列, 这样的队列更加适合我们的程序.
init(_ queueCapacity: Int = 16) {
capacity = queueCapacity
}
func clear() {
head = 0
tail = 0
length = 0
}
func isEmpty() -> Bool {
return length == 0 ? true : false
}
func isFull() -> Bool {
return length == capacity ? true : false
}
func size() -> Int {
return length
}
实现了初始化和一些必要的函数, 这里很容易理解就不过多赘述.
@discardableResult func entry(_ element: Element) -> Bool {
guard !isFull() else { return false }
queue.append(element)
queue[tail] = element
tail += 1
tail %= capacity
length += 1
return true
}
@discardableResult func depart() -> Element? {
guard !isEmpty() else { return nil }
let element = queue[head]
head += 1
head %= capacity
length -= 1
return element
}
这是对于队列这个数据结构最为重要的两个函数, 进入队列和离开队列, 其实也非常容易理解, 由于是环形队列所以关键点在于tail %= capacity和head %= capacity上, 对于取余数的概念其实和之前的投机流轮播图那篇类似理解即可.
func traverse() {
print("︵")
for i in head..<length + head {
print(queue[i % capacity])
}
print("︶")
}
队列遍历的函数, 也和取余数一样, 环形队列的好处和TCP滑动窗口也类似, 可以作为参考.
let queue_i = Queue<Int>()
queue_i.entry(1)
queue_i.entry(2)
queue_i.entry(3)
queue_i.traverse() // (1, 2, 3)
print(queue_i.depart()!) //1
queue_i.traverse() //(2, 3)
print(queue_i.depart()!) //2
queue_i.traverse() //(3)
queue_i.entry(4)
queue_i.entry(5)
queue_i.traverse() //(3, 4, 5)
print(queue_i.depart()!) //3
queue_i.traverse() //(4, 5)
队列的实现十分简单, 我们来用一下这个数据结构, 可以看到的确遵循了先进先出的原则, 这也就是队列这个数据结构了.
栈
接下来, 我们来说说栈, 有了队列的基础, 我们学习栈也并不是那么的费劲, 队列是先进先出, 而队列是先进后出, 区别也就在于此.
private var capacity: Int //栈容量
private lazy var peek: Int = 0 //栈顶
private lazy var buffer: [Element] = [Element]() //栈缓冲区
和学习队列相同, 我们也将成员变量列出来, 能够更好的了解这个数据结构.
@discardableResult func push(_ element: Element) -> Bool {
guard !isFull() else { return false }
buffer.append(element)
buffer[peek] = element
peek += 1
return true
}
@discardableResult func pop() -> Element? {
guard !isEmpty() else { return nil }
peek -= 1
return buffer[peek]
}
判空, 判满, 清空, 构造之类的基础函数就带过了, 可以去github上看代码, 我们这里聚焦栈的关键函数, 进栈和出栈. 嗯,看代码就能够了解, 也不过多讲解了.
func traverse(reversed: Bool = false) {
print("︵")
if reversed {
for i in (0..<peek).reversed() {
print(buffer[i])
}
} else {
for i in 0..<peek {
print(buffer[i])
}
}
print("︶")
}
遍历函数, 正序遍历和倒序遍历, 嗯. 也很容易理解.
let stack_i = Stack<Int>(3)
stack_i.push(1)
stack_i.push(2)
stack_i.push(3)
stack_i.push(4)
stack_i.traverse() //(1, 2, 3)
print(stack_i.pop()!) //3
stack_i.traverse() //(1, 2)
stack_i.push(5)
stack_i.push(6)
stack_i.traverse() //(1, 2, 5)
print(stack_i.pop()!) //5
stack_i.traverse() //(1, 2)
我们也来实际使用下栈这个数据结构, 可以看到和队列不同, 栈是遵循先进后出的原则就类似于做电梯, 先进去的人最后出来. 这里为什么进栈4个元素, 打印只有3个, 是因为我们的容量限制为3, 到达容量限制就无法入栈, 就和电梯超载发出警报类似.
func converse(_ origin: Int , format: Int) -> String {
let stack = Stack<Int>(30)
var ori = origin
var mod = 0
var char = ["0","1","2","3","4","5","6","7","8","9",
"A","B","C","D","E","F"]
var conversed = ""
while ori != 0 {
mod = ori % format
stack.push(mod)
ori /= format
}
while !stack.isEmpty() {
guard let index = stack.pop() else { continue }
conversed += char[index]
}
stack.clear()
return "(\(conversed))"
}
print(converse(1000, format: 2)) //(1111101000)
print(converse(1000, format: 8)) //(1750)
print(converse(1000, format: 10)) //(1000)
print(converse(123456789, format: 16)) //(75BCD15)
栈这个数据结构可以做到非常多的事情, 比如说转换进制, 上面就是进制转换中栈的应用.
func match(_ brackets: String) -> Bool {
let stack = Stack<Character>(30)
let needStack = Stack<Character>(30)
var currentNeed = Character(" ")
for i in 0..<brackets.count {
let char = brackets[brackets.index(brackets.startIndex, offsetBy: i)]
if char != currentNeed {
stack.push(char)
switch char {
case "[":
if currentNeed != Character(" ") {
needStack.push(currentNeed)
}
currentNeed = "]"
break
case "(":
if currentNeed != Character(" ") {
needStack.push(currentNeed)
}
currentNeed = ")"
break
default:
return false
}
} else {
stack.pop()
guard let need = needStack.pop() else { currentNeed = Character(" "); continue }
currentNeed = need
}
}
return stack.isEmpty()
}
print(match("[]()[]()[]") ? "match" : "not match") //match
不仅可以转换进制, 还可以判断括号的匹配, 这里就需要2个栈的应用, 最后判断栈是否为空来推断是否匹配.
线性表
数据结构从线性表这里开始难易程度上了一个台阶, 对于线性表来说, 栈和队列感觉就是闹着玩的, 好了, 我们来说说线性表.
线性表分为, 数组和链表, 数组就是连续的内存地址, 而链表则是不连续的内存地址通过指针指向来串联, 比如每个保险箱里有一把能够打开下一个保险箱的钥匙, 而下一个保险箱内又有一把指向下下一个保险箱的钥匙, 如此往复, 便是链表.
数组
我们来先说说数组这个数据结构, 对于一般我们开发来说, 数组是我们最为常用的容器类了, 但我们真的了解数组的实现过程么, 来看看吧.
private var capacity: Int = 0 //数组容量
private lazy var length: Int = 0 //数组长度
private lazy var list: [Element] = [Element]() //数组
这里的list成员变量, 我们可以理解成为一段连续的内存地址即可.
func getElement(loc index: Int) -> Element? {
if index < 0 || index >= capacity || length == 0 {
return nil
}
return list[index]
}
func locate(of element: Element) -> Int {
for i in 0..<length {
if list[i] == element {
return i
}
}
return -1
}
数组比之前学的队列和栈复杂点, 我们先来看看取元素和定位元素的函数的实现, 嗯. 还是理解尚可.
func prior(of element: Element) -> Element? {
let temp = locate(of: element)
if temp == -1 {
return nil
} else {
if temp == 0 {
return nil
} else {
return list[temp - 1]
}
}
}
func next(of element: Element) -> Element? {
let temp = locate(of: element)
if temp == -1 {
return nil
} else {
if temp == length - 1 {
return nil
} else {
return list[temp + 1]
}
}
}
接着我们来看看获取元素的前后元素的函数, 通过偏移下标来获取前后元素, 并做了界限控制, 没什么可多说的.
@discardableResult func insert(loc index: Int, element: Element) -> Bool {
if index < 0 || index > length {
return false
}
list.append(element)
for i in (index..<length).reversed() {
list[i + 1] = list[i]
}
list[index] = element
length += 1
return true
}
@discardableResult func delete(loc index: Int) -> Element? {
if index < 0 || index >= length {
return nil
}
for i in (index + 1)..<length {
list[i - 1] = list[i]
}
length -= 1
return list[index]
}
来说说核心函数, 插入与删除的实现, 其实也是通过偏移指针来完成的, 可以说因为数组是一段连续的内存地址, 只需要偏移指针就可以定位并获取到这段内存地址中的任意数据.
let list_i = List1<Int>(10)
list_i.insert(loc: 0, element: 1)
list_i.insert(loc: 1, element: 2)
list_i.insert(loc: 2, element: 3)
list_i.insert(loc: 3, element: 4)
list_i.insert(loc: 4, element: 5)
list_i.insert(loc: 5, element: 6)
list_i.insert(loc: 6, element: 7)
list_i.traverse() //(1, 2, 3, 4, 5, 6, 7)
list_i.delete(loc: 3)
list_i.delete(loc: 2)
list_i.traverse() //(1, 2, 5, 6, 7)
print(list_i.prior(of: 6)!) //5
print(list_i.next(of: 1)!) //2
print(list_i.getElement(loc: 2)!) //5
我们来使用一下数组这个数据结构, 嗯, 和平时用的NSArray没有什么太大区别, 但了解了内部实现逻辑, 可以更好的定义自己的数据结构并进行功能的扩展.
链表
链表这个数据结构我在iOS和Web开发中基本没有用到过, 可能有的数组比如NSMutableArray或List是用链表实现的? 这点没有验证过不能瞎说, 但我们可以知道链表在数据量大的情况下性能优于数组, 接下来我们来看下链表这个数据结构吧.
var data: Element? //节点数据
// for list
var next: Node? //节点指针, 指向下一个节点
说道链表, 我们需要有一个节点Node类来存储数据和指针.
private var head: Node<Element> //头节点
private lazy var length: Int = 0 //链表长度
有了节点, 我们来定义一下链表所需要的成员属性吧.
func getElement(loc index: Int) -> Node<Element>? {
if index < 0 || index >= length {
return nil
}
var currentNode = head
for _ in 0...index {
guard let node = currentNode.next else { continue }
currentNode = node
}
let node = Node<Element>()
node.data = currentNode.data
return node
}
func locate(of node: Node<Element>) -> Int {
var currentNode = head
var count = 0
while currentNode.next != nil {
currentNode = currentNode.next!
if currentNode.data == node.data {
return count
}
count += 1
}
return -1
}
与数组的不同, 链表的获取及定位函数, 是以节点指针指向进行操作的.
func prior(of node: Node<Element>) -> Node<Element>? {
var currentNode = head
var tempNode: Node<Element>? = nil
while currentNode.next != nil {
tempNode = currentNode
currentNode = currentNode.next!
if currentNode.data == node.data {
guard let tempNode = tempNode else { continue }
if tempNode == head {
return nil
}
let node = Node<Element>()
node.data = tempNode.data
return node
}
}
return nil
}
func next(of node: Node<Element>) -> Node<Element>? {
var currentNode = head
while currentNode.next != nil {
currentNode = currentNode.next!
if currentNode.data == node.data {
if currentNode.next == nil {
return nil
}
guard let data = currentNode.next?.data else { continue }
let node = Node<Element>()
node.data = data
return node
}
}
return nil
}
同理, 获取前后元素也是通过节点指针进行操作的, 以头节点为基点, 通过多次指向指向获取响应元素及下标.
@discardableResult func insert(loc index: Int, node: Node<Element>) -> Bool {
if index < 0 || index >= length {
return false
}
var currentNode = head
for _ in 0..<index {
guard let nextNode = currentNode.next else { continue }
currentNode = nextNode
}
let newNode = Node<Element>()
newNode.data = node.data
newNode.next = currentNode.next
currentNode.next = newNode
length += 1
return true
}
@discardableResult func delete(loc index: Int) -> Node<Element>? {
if index < 0 || index >= length {
return nil
}
var currentNode = head
var currentNodeBefore: Node<Element>? = nil
for _ in 0...index {
currentNodeBefore = currentNode
guard let nextNode = currentNode.next else { continue }
currentNode = nextNode
}
currentNodeBefore?.next = currentNode.next
let node = Node<Element>()
node.data = currentNode.data
length -= 1
return node
}
插入和删除的核心操作也是同理, 通过next节点指向变换, 进行插入和删除.
@discardableResult func insertHead(node: Node<Element>) -> Bool {
let temp = head.next
let newNode = Node<Element>()
newNode.data = node.data
head.next = newNode
newNode.next = temp
length += 1
return true
}
@discardableResult func insertTail(node: Node<Element>) -> Bool {
var currentNode = head
while currentNode.next != nil {
currentNode = currentNode.next!
}
let newNode = Node<Element>()
newNode.data = node.data
newNode.next = nil
currentNode.next = newNode
length += 1
return true
}
我们这里多了一步插入头节点和尾节点的操作, 其实原理也是相同的, 就是改变节点指针的指向, 重要的东西多说几遍.
let list_i = List2<Int>()
for i in 1...7 {
list_i.insertTail(node: Node<Int>(data: i))
}
list_i.traverse() //(1, 2, 3, 4, 5, 6, 7)
list_i.getElement(loc: 2)?.printNode() //3
let node_i = Node<Int>(data: 1024)
list_i.insert(loc: 5, node: node_i)
list_i.traverse() //(1, 2, 3, 4, 5, 1024, 6, 7)
print(list_i.locate(of: node_i)) //5
print(list_i.size()) //8
list_i.prior(of: node_i)?.printNode() //5
list_i.next(of: node_i)?.printNode() //6
list_i.delete(loc: 5)?.printNode() //1024
list_i.traverse() //(1, 2, 3, 4, 5, 6, 7)
以上是链表这个数据结构的使用情况, 可以感觉到FMDB就是采用类似链表的形式吧.
树
二叉树, 听的挺多, 做业务几乎也是没有用到过, 所谓二叉树, 就是从头节点向下有不超过两个的自己点, 向下伸展即为二叉树,
数组树
private var tree: [Any] //树数组
private var capacity: Int //树容量
我们先来看一下数组树这个数据结构我们需要哪些数据成员属性,
init(_ treeCapacity: Int, root: Element) {
capacity = treeCapacity
tree = [Any](repeating: 0, count: treeCapacity)
tree[0] = root
}
func searchNode(loc index: Int) -> Element? {
if index < 0 || index >= capacity {
return nil
}
if tree[index] as? Int == 0 {
return nil
}
return tree[index] as? Element
}
初始化构造时, 将数组树中的所有元素以0占位, 并将外部传入的元素赋值到数组树的第0个下标, 作为树根. 搜索节点的算法其实和数组这个数据结构相同, 通过下标来查询.
@discardableResult func addNode(loc index: Int, direction: Direction, node: Element) -> Bool {
if index < 0 || index >= capacity {
return false
}
if tree[index] as? Int == 0 {
return false
}
switch direction {
case .left:
if index * 2 + 1 >= capacity {
return false
}
if tree[index * 2 + 1] as? Int != 0 {
return false
}
tree[index * 2 + 1] = node
case .right:
if index * 2 + 2 >= capacity {
return false
}
if tree[index * 2 + 2] as? Int != 0 {
return false
}
tree[index * 2 + 2] = node
}
return true
}
@discardableResult func deleteNode(loc index: Int) -> Bool {
if index < 0 || index >= capacity {
return false
}
if tree[index] as? Int == 0 {
return false
}
tree[index] = 0
deleteNode(loc: index * 2 + 1)
deleteNode(loc: index * 2 + 2)
return true
}
添加及删除节点, 添加的时候用了一个简单的数学公式, 因为是二叉树所以index * 2, 左边子节点为 +1, 右边子节点为+2. 删除节点的时候使用了递归, 也同样使用了这个公式.
let tree_i = Tree1(15, root: Node<Int>(data: 3))
tree_i.addNode(loc: 0, direction: .right, node: Node<Int>(data: 4))
tree_i.addNode(loc: 2, direction: .left, node: Node<Int>(data: 5))
tree_i.addNode(loc: 5, direction: .right, node: Node<Int>(data: 6))
tree_i.traverse() //(304005000000600)
tree_i.searchNode(loc: 5)?.printNode() //5
tree_i.deleteNode(loc: 2)
tree_i.traverse() //(300000000000000)
可以看到数组树就是以第一个下标作为第一个节点, 后面的以0占位, 如果是子节点, 则显示子节点的数据, 没有子节点就是0.
链表树
学会了数组树, 我们来看看链表树到底是一个怎么会事, 可能想象也就知道, 是通过链表的形式进行树的延伸, 而不是以0占位吧. 看看是什么歌情况吧.
// for tree
var index: Int = 0
var leftChild: Node?
var rightChild: Node?
var parent: Node?
首先, 我们先在树的节点上定义一下所需要的元素, 和之前链表的节点类似, 只是一个指针变成了三个.
func searchNode(nodeIndex: Int) -> Node<Element>? {
if index == nodeIndex {
return self
}
var temp: Node<Element>? = nil
if leftChild != nil {
if leftChild?.index == nodeIndex {
return leftChild
} else {
temp = leftChild?.searchNode(nodeIndex: nodeIndex)
if temp != nil {
return temp
}
}
}
if rightChild != nil {
if rightChild?.index == nodeIndex {
return rightChild
} else {
temp = rightChild?.searchNode(nodeIndex: nodeIndex)
if temp != nil {
return temp
}
}
}
return nil
}
还需要在节点中添加搜索节点的方法, 因为是链表, 所以节点自身也成为了链表的一部分, 所以搜索的逻辑写入在节点中是非常合适的.
func deleteNode() {
if leftChild != nil {
leftChild?.deleteNode()
}
if rightChild != nil {
rightChild?.deleteNode()
}
if parent != nil {
if parent?.leftChild == self {
parent?.leftChild = nil
}
if parent?.rightChild == self {
parent?.rightChild = nil
}
}
parent = nil
}
还需要添加删除节点的函数在节点中进行递归.
enum PrintType {
case dafault
case preorder
case inorder
case postorder
}
func printNode(_ type: PrintType = .dafault) {
guard let data = data else { return }
switch type {
case .dafault:
print(data)
case .preorder:
print("\(index), \(data)")
if leftChild != nil {
leftChild?.printNode(.preorder)
}
if rightChild != nil {
rightChild?.printNode(.preorder)
}
case .inorder:
if leftChild != nil {
leftChild?.printNode(.inorder)
}
print("\(index), \(data)")
if rightChild != nil {
rightChild?.printNode(.inorder)
}
case .postorder:
if leftChild != nil {
leftChild?.printNode(.postorder)
}
if rightChild != nil {
rightChild?.printNode(.postorder)
}
print("\(index), \(data)")
}
}
节点中, 我们最后需要加入打印节点的方法, 这里通过枚举判断是前序遍历, 中序遍历还是后序遍历.
private var root: Node<Element> //头节点
init(root node: Node<Element>) {
root = node
}
func searchNode(loc index: Int) -> Node<Element>? {
return root.searchNode(nodeIndex: index)
}
有了刚才的节点支持, 我们在链表树中的操作就轻松多了, 只需要导入一个头节点, 搜索节点也只需要调用刚才节点中的饿搜索方法.
func preorderTraversal() {
print("︵")
root.printNode(.preorder)
print("︶")
}
func inorderTraversal() {
print("︵")
root.printNode(.inorder)
print("︶")
}
func postorderTraversal() {
print("︵")
root.printNode(.postorder)
print("︶")
}
前序遍历, 后序遍历, 中序遍历只需要传入不同的枚举即可, 逻辑都在刚才的节点函数中实现了.
@discardableResult func addNode(loc index: Int, direction: Direction, node: Node<Element>) -> Bool {
guard let temp = searchNode(loc: index) else { return false }
let newNode = Node<Element>()
newNode.index = node.index
newNode.data = node.data
newNode.parent = temp
if direction == .left {
temp.leftChild = newNode
}
if direction == .right {
temp.rightChild = newNode
}
return true
}
@discardableResult func deleteNode(loc index: Int) -> Node<Element>? {
guard let temp = searchNode(loc: index) else { return nil }
temp.deleteNode()
return temp
}
删除节点也是调用了节点中的递归方法, 值得注意的只有添加节点的方法, 我们可以看到, 添加节点做的就是像子节点指针进行赋值, 并通过搜索方法定位到该赋值的节点.
let tree_i = Tree2(root: Node<Int>(data: 0))
tree_i.addNode(loc: 0, direction: .right, node: Node<Int>(index: 1, data: 4))
tree_i.addNode(loc: 1, direction: .left, node: Node<Int>(index: 2, data: 5))
tree_i.addNode(loc: 2, direction: .right, node: Node<Int>(index: 3, data: 6))
tree_i.preorderTraversal()
tree_i.inorderTraversal()
tree_i.postorderTraversal()
/*
︵
0, 0
1, 4
2, 5
3, 6
︶
︵
0, 0
2, 5
3, 6
1, 4
︶
︵
3, 6
2, 5
1, 4
0, 0
︶
*/
tree_i.searchNode(loc: 3)?.printNode() //6
tree_i.deleteNode(loc: 1)
tree_i.preorderTraversal() //(0,0)
tree_i.inorderTraversal() //(0,0)
tree_i.postorderTraversal() //(0,0)
链表树和数组树的使用也是如出一辙, 就和数组和链表的关系一样, 一个是下标索引, 一个是指针指向.
图
终于要讲到最为关键的一个数据结构了, 图, 刚学习的时候对于图真的有点不好理解, 什么是图, 轨道交通图, 就是一个非常好的一个无向图, 可以说是图这个数据结构的完美写照, 比如说要从静安寺到陆家嘴再到人民广场再到徐家汇再到世纪大道的最近距离, 就是最小生成树算法. 算法我们等会说, 我们先来看看图这个数据结构.
// for map
var visited: Bool = false //是否访问
我们需要在节点中添加是否访问的字段
class Edge {
var nodeIndexA: Int //点A
var nodeIndexB: Int //点B
var weightValue: Int //边的权重
var selected: Bool = false //是否选择此边
init(nodeIndexA A: Int = 0, nodeIndexB B: Int = 0, weightValue Val: Int = 0) {
nodeIndexA = A
nodeIndexB = B
weightValue = Val
}
}
还需要创建一个边的类, 并声明以上成员属性.
private var capacity: Int //图的容量
private var matrix: [Int] //图的矩阵
private var edge: [Edge] //边的集合
private lazy var count: Int = 0 //图的数量
private lazy var map: [Node<Element>] = [Node<Element>]() //图集合
init(_ mapCapacity: Int) {
capacity = mapCapacity
matrix = [Int](repeating: 0, count: capacity * capacity)
edge = [Edge](repeating: Edge(), count: capacity - 1)
}
定义上述成员属性, 并进行初始化.
@discardableResult func addNode(_ node: Node<Element>?) -> Bool {
guard let node = node else { return false }
map.append(node)
map[count].data = node.data
count += 1
return true
}
func resetNode() {
for i in 0..<count {
map[i].visited = false
}
}
添加节点和重置节点的函数, 没什么好说, 请回顾数组篇.
@discardableResult func setValueToMatrixForDirectedGraph(row: Int, col: Int, val: Int = 1) -> Bool {
if row < 0 || row >= capacity {
return false
}
if col < 0 || col >= capacity {
return false
}
matrix[row * capacity + col] = val
return true
}
@discardableResult func setValueToMatrixForUndirectedGraph(row: Int, col: Int, val: Int = 1) -> Bool {
if row < 0 || row >= capacity {
return false
}
if col < 0 || col >= capacity {
return false
}
matrix[row * capacity + col] = val
matrix[col * capacity + row] = val
return true
}
单边图和无向图的区别, 即是矩阵中的展示区别.
func depthFirstTraverse(loc index: Int) {
print("︵")
func depthFirstTraverseImpl(loc index: Int) {
guard let data = map[index].data else { return }
print(data)
map[index].visited = true
for i in 0..<capacity {
let value = getValueFromMatrix(row: index, col: i)
if value == 1 {
if map[i].visited {
continue
} else {
depthFirstTraverseImpl(loc: i)
}
} else {
continue
}
}
}
depthFirstTraverseImpl(loc: index)
print("︶")
}
深度优先遍历, 就是纵向的结构进行遍历.
func breadthFirstTraverse(loc index: Int) {
print("︵")
guard let data = map[index].data else { return }
print(data)
map[index].visited = true
var temp = [Int]()
temp.append(index)
func breadthFirstTraverseImpl(preTemp: [Int]) {
var temp = [Int]()
for i in 0..<preTemp.count {
for j in 0..<capacity {
let value = getValueFromMatrix(row: preTemp[i], col: j)
if value != 0 {
if map[j].visited {
continue
} else {
guard let data = map[j].data else { return }
print(data)
map[j].visited = true
temp.append(j)
}
}
}
}
if temp.count == 0 {
return
} else {
breadthFirstTraverseImpl(preTemp: temp)
}
}
breadthFirstTraverseImpl(preTemp: temp)
print("︶")
}
广度优先遍历, 就是一层层的进行遍历, 先得到第一层的根节点, 再第二层, 第三层, 以此类推.
private func getValueFromMatrix(row: Int, col: Int) -> Int? {
if row < 0 || row >= capacity {
return nil
}
if col < 0 || col >= capacity {
return nil
}
return matrix[row * capacity + col]
}
从矩阵中获取值的函数, 嗯… 做了边界控制.
最小生成树算法
func primTree(loc index: Int) {
var edgeCount = 0
var edgeBuffers = [Edge]()
var nodeIndexes = [Int]()
var primTreePath = [Element]()
nodeIndexes.append(index)
map[index].visited = true
primTreePath.append(map[index].data!)
while edgeCount < capacity - 1 {
guard let index: Int = nodeIndexes.last else { continue }
for i in 0..<capacity {
guard let value = getValueFromMatrix(row: index, col: i) else { continue }
if value != 0 {
if map[i].visited {
continue
} else {
edgeBuffers.append(Edge(nodeIndexA: index, nodeIndexB: i, weightValue: value))
}
}
}
let edgeIndex = getMinEdge(buffers: edgeBuffers)
edgeBuffers[edgeIndex].selected = true
print(edgeBuffers[edgeIndex].nodeIndexA, edgeBuffers[edgeIndex].nodeIndexB, edgeBuffers[edgeIndex].weightValue)
edge[edgeCount] = edgeBuffers[edgeIndex]
edgeCount += 1
let nextNodeIndex = edgeBuffers[edgeIndex].nodeIndexB
nodeIndexes.append(nextNodeIndex)
map[nextNodeIndex].visited = true
primTreePath.append(map[nextNodeIndex].data!)
}
for node in primTreePath {
print("\(node)", terminator: "")
}
print()
}
prim算法, 核心思想是获取所有的边放入待选边集合, 并根据所有的边的权重获取最小权重的边放入边集合, 这步需要判断是都点是否访问过.如此往复就可生成最小生成树.
func kruskalTree() {
var edgeCount = 0
var edgeBuffers = [Edge]()
var nodeIndexes = [[Int]]()
for i in 0..<capacity {
for j in i + 1..<capacity {
guard let value = getValueFromMatrix(row: i, col: j) else { continue }
if value != 0 {
edgeBuffers.append(Edge(nodeIndexA: i, nodeIndexB: j, weightValue: value))
}
}
}
while edgeCount < capacity - 1 {
let minEdgeIndex = getMinEdge(buffers: edgeBuffers)
edgeBuffers[minEdgeIndex].selected = true
let nodeAIndex = edgeBuffers[minEdgeIndex].nodeIndexA
let nodeBIndex = edgeBuffers[minEdgeIndex].nodeIndexB
var nodeAIsInSet = false
var nodeBIsInSet = false
var nodeAInSetLabel = -1
var nodeBInSetLabel = -1
for i in 0..<nodeIndexes.count {
nodeAIsInSet = isInSet(nodeIndexes[i], nodeAIndex)
if nodeAIsInSet {
nodeAInSetLabel = i
}
}
for i in 0..<nodeIndexes.count {
nodeBIsInSet = isInSet(nodeIndexes[i], nodeBIndex)
if nodeBIsInSet {
nodeBInSetLabel = i
}
}
if nodeAInSetLabel == -1 && nodeBInSetLabel == -1 {
var vec = [Int]()
vec.append(nodeAIndex)
vec.append(nodeBIndex)
nodeIndexes.append(vec)
} else if nodeAInSetLabel == -1 && nodeAInSetLabel != -1 {
nodeIndexes[nodeBInSetLabel].append(nodeAIndex)
} else if nodeAInSetLabel != -1 && nodeAInSetLabel == -1 {
nodeIndexes[nodeAInSetLabel].append(nodeBIndex)
} else if nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel != nodeBInSetLabel {
nodeIndexes[nodeAInSetLabel] =
mergeNodeSets(nodeIndexes[nodeAInSetLabel], nodeIndexes[nodeBInSetLabel])
for i in nodeBInSetLabel..<nodeIndexes.count-1 {
nodeIndexes[i] = nodeIndexes[i + 1]
}
} else if nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel == nodeBInSetLabel {
continue
}
edge[edgeCount] = edgeBuffers[minEdgeIndex]
edgeCount += 1
print(edgeBuffers[minEdgeIndex].nodeIndexA, edgeBuffers[minEdgeIndex].nodeIndexB, edgeBuffers[minEdgeIndex].weightValue)
}
}
private func getMinEdge(buffers edgeBuffers: [Edge]) -> Int {
var minWeight = 0
var edgeIndex = 0
var i = 0
for _ in 0..<edgeBuffers.count {
if !edgeBuffers[i].selected {
minWeight = edgeBuffers[i].weightValue
edgeIndex = i
break
}
i += 1
}
if minWeight == 0 {
return -1;
}
for _ in i..<edgeBuffers.count {
if edgeBuffers[i].selected {
i += 1
continue
} else {
if minWeight > edgeBuffers[i].weightValue {
minWeight = edgeBuffers[i].weightValue
edgeIndex = i
}
}
i += 1
}
return edgeIndex
}
private func isInSet(_ nodeSet:[Int], _ target: Int) -> Bool {
for i in 0..<nodeSet.count {
if nodeSet[i] == target {
return true
}
}
return false
}
private func mergeNodeSets(_ nodeSetA: [Int], _ nodeSetB: [Int]) -> [Int] {
var nodeSet = [Int]()
for i in 0..<nodeSetB.count {
nodeSet.append(nodeSetB[i])
}
return nodeSet
}
kruskal算法就比较复杂了, 首先我们要将所有边放入待选边集合中, 然后在所有边中选出一条权值最小的边放入已选边集合中, 我们选定了边就选定了点并放入已选点集合, 如此往复, 选择次小的边并获取边和点, 重点是需要判断是否和之前已选的边形成闭环, 如果形成闭环则需要抛弃.需要涉及所有的点, 并合成一个点数组才算完成.
let map_s = Map<String>(8)
map_s.addNode(Node<String>(data: "A"))
map_s.addNode(Node<String>(data: "B"))
map_s.addNode(Node<String>(data: "C"))
map_s.addNode(Node<String>(data: "D"))
map_s.addNode(Node<String>(data: "E"))
map_s.addNode(Node<String>(data: "F"))
map_s.addNode(Node<String>(data: "G"))
map_s.addNode(Node<String>(data: "H"))
map_s.setValueToMatrixForUndirectedGraph(row: 0, col: 1)
map_s.setValueToMatrixForUndirectedGraph(row: 0, col: 3)
map_s.setValueToMatrixForUndirectedGraph(row: 1, col: 2)
map_s.setValueToMatrixForUndirectedGraph(row: 1, col: 5)
map_s.setValueToMatrixForUndirectedGraph(row: 3, col: 6)
map_s.setValueToMatrixForUndirectedGraph(row: 3, col: 7)
map_s.setValueToMatrixForUndirectedGraph(row: 6, col: 7)
map_s.setValueToMatrixForUndirectedGraph(row: 2, col: 4)
map_s.setValueToMatrixForUndirectedGraph(row: 4, col: 5)
map_s.printMatrix()
/*
︵
0 1 0 1 0 0 0 0
1 0 1 0 0 1 0 0
0 1 0 0 1 0 0 0
1 0 0 0 0 0 1 1
0 0 1 0 0 1 0 0
0 1 0 0 1 0 0 0
0 0 0 1 0 0 0 1
0 0 0 1 0 0 1 0
︶
*/
map_s.depthFirstTraverse(loc: 0) //(ABEFDGH)
map_s.resetNode()
map_s.breadthFirstTraverse(loc: 0) //(ABDCFGHE)
最后我们来使用下图这个数据结构, 可以看到图这个数据结构还是和之前所学挺不一样的. 看到了矩阵和深度优先和广度优先的差异.
let map = Map<String>(6)
map.addNode(Node<String>(data: "A"))
map.addNode(Node<String>(data: "B"))
map.addNode(Node<String>(data: "C"))
map.addNode(Node<String>(data: "D"))
map.addNode(Node<String>(data: "E"))
map.addNode(Node<String>(data: "F"))
map.setValueToMatrixForUndirectedGraph(row: 0, col: 1, val: 6)
map.setValueToMatrixForUndirectedGraph(row: 0, col: 4, val: 5)
map.setValueToMatrixForUndirectedGraph(row: 0, col: 5, val: 1)
map.setValueToMatrixForUndirectedGraph(row: 1, col: 2, val: 3)
map.setValueToMatrixForUndirectedGraph(row: 1, col: 5, val: 2)
map.setValueToMatrixForUndirectedGraph(row: 2, col: 5, val: 8)
map.setValueToMatrixForUndirectedGraph(row: 2, col: 3, val: 7)
map.setValueToMatrixForUndirectedGraph(row: 3, col: 5, val: 4)
map.setValueToMatrixForUndirectedGraph(row: 3, col: 4, val: 2)
map.setValueToMatrixForUndirectedGraph(row: 4, col: 5, val: 9)
map.printMatrix()
/*
︵
0 6 0 0 5 1
6 0 3 0 0 2
0 3 0 7 0 8
0 0 7 0 2 4
5 0 0 2 0 9
1 2 8 4 9 0
︶
*/
map.primTree(loc: 0)
/*
0 5 1
5 1 2
1 2 3
5 3 4
3 4 2
AFBCDE
*/
map.kruskalTree()
/*
0 5 1
1 5 2
3 4 2
1 2 3
3 5 4
*/
接着我们来看看最小生成树的算法, 可以看到不管是那种算法, 都能够将最小生成树给算出来, 算法真是博大精深啊.
数据结构关键是多练多思考, 有了好的算法思维, 才能够对以后的成长有所帮助!!
🌟源码 请点这里🌟 »> 喜欢的朋友请点喜欢 »> 下载源码的同学请送下小星星 »> 有闲钱的壕们可以进行打赏 »> 小弟会尽快推出更好的文章和大家分享 »> 你的激励就是我的动力!!