之前看学长他们用过这个动静路由，然而以前也没有太留神，最近在学习框架的建设。第一次让我感触到了算法在写我的项目时候的利用，之前都感觉算法这个货色，就是刷题用的，在实战的时候很少用。明天学习这一块略微有一点吃力，然而还是看懂了，很nice。
<!– more –>
什么是动静路由呢
动静路由在开发的时候，就是说不是像原来写我的项目的时候，这个固定路由绑定固定的函数，而是变动的路由进行固定函数的绑定，这样就能够实现很多的性能。
动静路由的实例：/api/v1/:name
这里咱们要晓得的是，下面这个路由能够匹配很多的路由比方：
/api/v1/lzz /api/v1/ceshi ….等
这里第三个分隔开的字段，就是对name的赋值。这就是动静路由
实现动静路由须要筹备什么
首先咱们要用到的就是前缀树，这里咱们看一下怎么实现前缀树。咱们还是阐明一下，比如说，在咱们路由中咱们能够通过/来宰割节点，而后前面通过这些节点进行寻找正确的路由。
、
下面的这个图就是展现了前缀树。而后上面咱们就来实现一下这个前缀树。
首先定义前缀树的节点：
type node struct {
pattern string //待匹配的路由
part string //路由中的一部分
children []*node //子节点
isWild bool //这里如果是*或者：结尾的就是true
}而后咱们建设一个注册函数，一个查找函数
func (n *node) insert(pattern string, parts []string, height int) {
//查看是不是最初一个，是的话就返回
if len(parts) == height {
n.pattern = pattern
return
}
//取出门路中的一部分
part := parts[height]
//查看当初的树中是不是有这个节点，没有的话就进行创立
child := n.matchChild(part)
//上面是创立的流程。也就是创立
if child == nil {
//如果是动静的就会设置为true
child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
n.children = append(n.children, child)
}
child.insert(pattern, parts, height+1)
}查找函数：
func (n *node) search(parts []string, height int) *node {
if len(parts) == height || strings.HasPrefix(n.part, "*") {
if n.pattern == "" {
return nil
}
return n
}
part := parts[height]
children := n.matchChildren(part)
for _, child := range children {
result := child.search(parts, height+1)
if result != nil {
return result
}
}
return nil
}下面两个函数中有两个要害的函数，就是对路由的匹配，这两个函数我还是看了很久才了解，也是在学习的时候呈现的问题。
//创立节点插入的时候的判断函数
func (n *node) matchChild(part string) *node {
for _, child := range n.children {
if child.part == part || child.isWild {
return child
}
}
return nil
}
//查找门路
func (n *node) matchChildren(part string) []*node {
nodes := make([]*node, 0)
for _, child := range n.children {
if child.part == part || child.isWild {
nodes = append(nodes, child)
}
}
return nodes
}
两个函数的原理都是差不多的，传入须要判断的门路一部分，而后在节点外面去寻找是否有这个节点，而后找到了就返回，没有找到就返回nil，我认为的这两个函数，第一个就是判断有没有这个节点，如果没有就返回，而后建设新的节点进行存储，如果找到了就不做操作。
第二个函数，就是对没有局部的判断，而后进行一个增加。
前缀树残缺的代码：
package gee
import (
"fmt"
"strings"
)
type node struct {
pattern string
part string
children []*node
isWild bool
}
func (n *node) String() string {
return fmt.Sprintf("node{pattern=%s, part=%s, isWild=%t}", n.pattern, n.part, n.isWild)
}
func (n *node) insert(pattern string, parts []string, height int) {
//查看是不是最初一个，是的话就返回
if len(parts) == height {
n.pattern = pattern
return
}
//取出门路中的一部分
part := parts[height]
//查看当初的树中是不是有这个节点，没有的话就进行创立
child := n.matchChild(part)
//上面是创立的流程。也就是创立
if child == nil {
//如果是动静的就会设置为true
child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
n.children = append(n.children, child)
}
child.insert(pattern, parts, height+1)
}
//路由的查找
func (n *node) search(parts []string, height int) *node {
if len(parts) == height || strings.HasPrefix(n.part, "*") {
if n.pattern == "" {
return nil
}
return n
}
part := parts[height]
children := n.matchChildren(part)
for _, child := range children {
result := child.search(parts, height+1)
if result != nil {
return result
}
}
return nil
}
func (n *node) travel(list *([]*node)) {
if n.pattern != "" {
*list = append(*list, n)
}
for _, child := range n.children {
child.travel(list)
}
}
//创立节点插入的时候的判断函数
func (n *node) matchChild(part string) *node {
for _, child := range n.children {
if child.part == part || child.isWild {
return child
}
}
return nil
}
//查找门路
func (n *node) matchChildren(part string) []*node {
nodes := make([]*node, 0)
for _, child := range n.children {
if child.part == part || child.isWild {
nodes = append(nodes, child)
}
}
return nodes
}
发表回复