swift算法手记-9

swift算法手记-9,第1张

概述在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。Trie这个术语来自于retrieval。根据词源学,t 在计算机科学中,trIE,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。TrIE这个术语来自于retrIEval。根据词源学,trIE的发明者EDWard Fredkin把它读作英语发音:/ˈtriː/ "tree"。[1][2]但是,其他作者把它读作英语发音:/ˈtraɪ/ "try"。[1][2][3]在图示中,键标注在节点中,值标注在节点之下。每一个完整的英文单词对应一个特定的整数。TrIE可以看作是一个确定有限状态自动机,尽管边上的符号一般是隐含在分支的顺序中的。键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示trIE的原理。trIE中的键通常是字符串,但也可以是其它的结构。trIE的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trIE中的键是一串位元,可以用于表示整数或者内存地址。
//http://blog.csdn.net/myhaspl/class VIEwController: NSVIEwController {    private let trIEroot:TrIENode = TrIENode (str: " ",nstate: NoteState.Root)//http://blog.csdn.net/myhaspl/        overrIDe func vIEwDIDLoad() {        super.vIEwDIDLoad()        // Do any additional setup after loading the vIEw.    }//http://blog.csdn.net/myhaspl/    overrIDe var representedobject: AnyObject? {        dIDSet {        // Update the vIEw,if already loaded.        }    } //http://blog.csdn.net/myhaspl/     private func createTrIENode(current:TrIENode,mystr:String)->TrIENode    {        let mynode:TrIENode=TrIENode(str: mystr,nstate: NoteState.NoneTerminal)        current.link[mystr]=mynode        return mynode    }    //http://blog.csdn.net/myhaspl/       private func trIEinput(current:TrIENode,str:String,isfind:Bool)->TrIENode?    {        if let nextstate=current.link[str]{            return nextstate        }        else if isfind{            return nil        }        else{            return  createTrIENode(current,mystr:str)        }    }        private func readstr(word:String){        var currnode:TrIENode=trIEroot        var inputstr:String=""        for mychar in word {            inputstr.append(mychar)            currnode = trIEinput(currnode,str: inputstr,isfind: false)!        }        currnode.state=NoteState.Terminal    }//http://blog.csdn.net/myhaspl/    private func findstr(word:String)->Bool{        var mynode:TrIENode=trIEroot        var inputstr:String=""        for mychar in word {            inputstr.append(mychar)            if let nextnode = trIEinput(mynode,isfind: true)            {                mynode=nextnode            }            else{                return false            }        }        if mynode.state==NoteState.Terminal{           return true        }        else{            return false        }    }//http://blog.csdn.net/myhaspl/        @IBOutlet weak var mywords: NSTextFIEld!    @IBOutlet weak var inputtxt: NSTextFIEld!    @IBAction func finDWord(sender: AnyObject) {        let finDW:Bool=findstr(inputtxt.stringValue)        let messageBox:NSAlert=NSAlert()        if finDW==true{            messageBox.messageText="找到"+inputtxt.stringValue        }        else{            messageBox.messageText="没找到"+inputtxt.stringValue        }        messageBox.alertStyle=NSAlertStyle.informationalAlertStyle        messageBox.runModal()      }       @IBAction func createword(sender: AnyObject) {        readstr(inputtxt.stringValue)        mywords.stringValue+=inputtxt.stringValue        mywords.stringValue+=" "    }    }



本博客所有内容是原创,如果转载请注明来源 http://blog.csdn.net/myhaspl/


总结

以上是内存溢出为你收集整理的swift算法手记-9全部内容,希望文章能够帮你解决swift算法手记-9所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/web/1079962.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-27
下一篇 2022-05-27

发表评论

登录后才能评论

评论列表(0条)

保存