数据结构和算法（五）：图、深度优先搜索和广度优先搜索、字符串匹配

2019-11-21  本文已影响0人  冰风v落叶

从广义上来讲：数据结构就是一组数据的存储结构 ， 算法就是操作数据的方法

数据结构是为算法服务的，算法是要作用在特定的数据结构上的。

10个最常用的数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树

10个最常用的算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

本文总结了20个最常用的数据结构和算法，不管是应付面试还是工作需要，只要集中精力攻克这20个知识点就足够了。

数据结构和算法（一）：复杂度、数组、链表、栈、队列的传送门

数据结构和算法（二）：递归、排序、通用排序算法的传送门

数据结构和算法（三）：二分查找、跳表、散列表、哈希算法的传送门

数据结构和算法（四）：二叉树、红黑树、递归树、堆和堆排序、堆的应用的传送门

数据结构和算法（五）：图、深度优先搜索和广度优先搜索、字符串匹配算法、Trie树、AC自动机的传送门

数据结构和算法（六）：贪心算法、分治算法、回溯算法、动态规划、拓扑排序的传送门

第二十一章 图

首先呢，先思考一个问题，如何存储微博、微信等社交网络中的好友关系呢？

一、什么是图？及图中的几个基础概念
二、如何在内存中存储图？

方法一：邻接矩阵法

方法二：邻接表存储法

三、如何在存储微博中的社交关系呢？

第二十二章 深度优先搜索和广度优先搜索

一、什么是搜索算法
二、BFS-广度优先搜索（Breadth-First-Search）
//单链表
class SingleLinkedList{
    var headNode: SingleLinkedNode?
    var nodeMap: Dictionary<String, SingleLinkedNode>?
    var nodeCount: Int = 0
    
    //插入一个节点
    func insertNode(node: SingleLinkedNode){
        nodeMap?.updateValue(node, forKey: node.key)
        nodeCount = nodeCount + 1
        if headNode == nil{
            headNode = node
        }else{
            lastNode().next = node
        }
    }
    
    //获取一个节点
    func lastNode() -> SingleLinkedNode{
        var node = headNode
        while node?.next != nil {
            node = node?.next
        }
        if node != nil{
            return node!
        }else{
            return SingleLinkedNode(key: "error", value: "error")
        }
    }
    
    //根据key获取节点
    func getNode(key: String) -> SingleLinkedNode?{
        return nodeMap?[key]
    }
    
    //删除node的下一个节点
    func deleteNode(_ node: SingleLinkedNode){
        if (nodeMap?[node.key] ?? SingleLinkedNode(key: "", value: "")) == node{
            nodeCount = nodeCount - 1
            node.next = node.next?.next
        }else{
            print("该节点不存在")
        }
    }
    
    func size() -> Int{
        return nodeCount
    }
}

//单链表的节点
class SingleLinkedNode: Equatable{
    static func == (lhs: SingleLinkedNode, rhs: SingleLinkedNode) -> Bool {
        if lhs.key == rhs.key && lhs.value == rhs.value && lhs.next == rhs.next{
            return true
        }
        return false
    }
    
    var key:String = "-1"
    var value: String?
    var next: SingleLinkedNode?
    init(key: String,value: String) {
        self.key = key
        self.value = value
    }
}

//先入先出的顺序队列
class Queue<T>{
    private var array: Array<T> = Array()
    //入队
    func enqueue(_ e: T){
        array.append(e)
    }
    //出队
    func dequeue() -> T?{
        if let first = array.first{
            array.remove(at: 0)
            return first
        }
        return nil
    }
    
    func size() -> Int{
        return array.count;
    }
}

let queue = Queue<Int>()
queue.enqueue(11)
queue.enqueue(2)
queue.enqueue(333)
let testQueue1 = queue.dequeue()
let testQueue2 = queue.dequeue()
let testQueue3 = queue.dequeue()

//无向图
class Graph{
    private var peakCount: Int = 0                          //顶点的个数
    private var linkedArray = Array<SingleLinkedList>()     //单链表的数组
    
    //初始化
    init(peakCount: Int) {
        self.peakCount = peakCount
        let linkedList = SingleLinkedList()
        self.linkedArray = Array(repeating: linkedList, count: self.peakCount)
    }
    
    //增加一条边（无向图一条边需要存两次）
    func addEdge(s: Int,t: Int){
        let nodeT = SingleLinkedNode(key:"\(t)" ,value: "\(t)")
        let nodeS = SingleLinkedNode(key: "\(s)", value: "\(s)")
        linkedArray[s].insertNode(node: nodeT)
        linkedArray[t].insertNode(node: nodeS)
    }
    
    // 广度优先搜索 从顶点开始 寻找到t顶点的路径 打印出来
    func bfs(start_s: Int,target_t: Int){
        //如果起点等于重点 直接return
        if start_s == target_t {
            return
        }
        //已经访问过的顶点
        var visited = Array<Bool>()
        //先入先出的队列，负责存储已经被访问过但其相连的顶点还没有访问的顶点
        let queue = Queue<Int>()
        //将第一个顶点s加入队列
        queue.enqueue(start_s)
        //记录搜索路径
        var recordSearchPath = Array(repeating: -1, count: peakCount)
        while(queue.size() != 0){
            //当前顶点
            let currentPeak = queue.dequeue() ?? 0
            for i in 0..<linkedArray[currentPeak].size(){
                //当前顶点所对应的的节点
                let currentNode = linkedArray[currentPeak].getNode(key: "\(i)")
                //当前节点的位置
                let currentSub = Int(currentNode?.key ?? "0") ?? 0
                if !visited[currentSub]{
                    recordSearchPath[currentSub] = currentPeak
                    if currentSub == target_t{
                        print("找到了")
                        return
                    }
                    visited[currentSub] = true
                    queue.enqueue(currentSub)
                }
            }
        }
    }
}
三、DFS-深度优先搜索（Depth-First-Search）

第二十三章 字符串匹配基础

字符串匹配算法分为单模式串匹配和多模式串匹配。单模式匹配，即一个串和另一个串进行匹配，例如：BF算法、RK算法、BM算法、KMP算法；也有多模式串匹配，即在一个串中同时查找多个串，例如：Tire树。
一、BF算法
二、RK算法
三、BM算法

第二十四章 Trie树

一、什么是Trie树
二、如何实现一颗Trie树？
class TrieNode{
    var data: Character?         //存放一个字符，例如：“h”
    var childArray: [TrieNode]?  //存放子节点指针的数组，例如：存放以h开头的字符的子节点的指针
}
三、Trie树与散列表、红黑树的比较

第二十五章 AC自动机

一、什么是 AC自动机？
二、如何构建AC自动机?
三、如何在AC自动机上匹配主串？
上一篇下一篇

猜你喜欢

热点阅读