发表于

这是我参与11月更文挑战的第3天，活动详情查看：2021最后一次更文挑战

1 引言

多边形的绘制一般包括4个步骤，即：求交，排序，配对，填色

在填色阶段，采用4-连通边界种子填充算法

种子：边界/内点表示区域内的任意一点

种子填充算法较多用于多边形填充，多边形可以采用自定义绘制，或者矩阵输入

在本文中，还考虑将一张图片作为研究对象，改变其填充色，以实现种子填充算法的进阶运用~

2 思路

算法大致思路如下，循环进行以下操作，当栈顶为空时退出循环：

  1. 首先指定一个种子像素，并将其出栈
  2. 将出栈像素置成填充色
  3. 检查出栈像素的4-邻接点，若其中某个像素点是边界色且未置成多边形色，则把该像素入栈

3 过程

函数参数设置为5个，分别是种子像素的X,Y坐标，多边形矩阵及其长宽seed_fill4(x,y,Pic,vm,vn)

首先初始化栈，并显示待填充的图形

1
2
3
4
5
6
7
8
9
matlab复制代码figure(1);
imshow(Pic); %显示待填充的图形，用于与填充后的图形对比
a=[];
b=[];
top=0;
top=top+1;
a(1,top)=x;
b(1,top)=y;
Pic(x,y)=0;

再进入循环，判断种子像素的4-邻接点，并更新多边形矩阵Pic，当top>0时退出循环

最后显示填充后的多边形

1
2
matlab复制代码figure(2)
imshow(Pic);

完整代码请见
seed_fill4(gitee.com)

4 结果

4.1 自定义多边形及其填充结果

自定义多边形既可以在绘图软件中绘制，也可以矩阵的方式直接定义多边形。本文采用直接定义矩阵，即

1
2
3
4
matlab复制代码Pic([3:99],[3:99])=1;
Pic([2:99],[99:100])=0;
Pic([99:100],[1:100])=0;
seed_fill4(95,80,Pic,100,100);

由于计算机将白色像素点处理为“1”,黑色像素点处理为“0”，故初始多边形设置成边界为黑、内容为白：

填充色设置为黑色，填充效果如下：

4.2 图片及其填充结果

图片填充步骤如下：

  1. 使用imread()读取图片
  2. 进行灰度化
  3. 提取像素值大于125的矩阵，并获取长宽
  4. 调用种子填充函数，输入参数中的矩阵为第3步得到的矩阵

初始图片为：

填充色设置为黑色，填充效果如下：

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

📖 Net/http 底层实现原理.

了解到能够使用net/http对外进行简单进行扩展，更深层次的理解以后进行分析。

📜 一、net/http库的简单使用.

1
2
3
4
5
6
7
8
9
10
11
go复制代码func main() {
	
	http.HandleFunc("/test", func(response http.ResponseWriter, request *http.Request) {
		// 请求.
		str := "Hello Word"
		fmt.Println(str)
		response.Write([]byte(str))
	})
	// 不传handler,则使用默认的handler, 而上面直接通过包名来进行诸如HandleFunc底层则是会注入到DefaultServeMux中.
	http.ListenAndServe(":8080", nil)
}

结果：可以看到其比Java中开启一个Web应用是多么便捷，但这不是本文的重点.

image-20211125220304937

📜 二、底层实现原理分析.

我们仍然从上图代码块分析，首先先分析http.HandlerFunc注入Handler来具体分析.

先说下最终结果就是，其注入的Handler最后都会注入到下面的结构体中.

1
2
3
4
5
6
go复制代码type ServeMux struct {
	mu    sync.RWMutex
	m     map[string]muxEntry  // entry 具体存放具体请求的Handler,由请求路径和具体的Handler构成.
	es    []muxEntry // slice of entries sorted from longest to shortest.
	hosts bool       // whether any patterns contain hostnames
}

虽然说最终会存入改结构体中，但是我们要知道其实如何存入的呢？ 存入之后又是怎么进行调用的，所以，接着往下看.

当我们点进去我们写得代码之后，会发现，其会将我们自己的Handler转换为HandlerFunc，而改结构体实现了net\http下的Handler接口，并重写了ServerHTTP方法，在该方法内部直接调用我们自己的handler.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
go复制代码// HandleFunc registers the handler function for the given pattern.
func (mux *ServeMux) HandleFunc(pattern string, handler func(ResponseWriter, *Request)) {
	if handler == nil {
		panic("http: nil handler")
	}
	// 将func表示的handler转换为net/http中的HandlerFunc，并在其接口ServerHTTP中调用handler.
	mux.Handle(pattern, HandlerFunc(handler))
}

// HandlerFunc定义.
type HandlerFunc func(ResponseWriter, *Request)

// ServeHTTP calls f(w, r).
func (f HandlerFunc) ServeHTTP(w ResponseWriter, r *Request) {
	f(w, r)
}

接下来就是分析ServerMux是如何进行保存Handler的.

可以看到会将Handler注册到ServeMux中的m和es中.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
go复制代码// Handle registers the handler for the given pattern.
// If a handler already exists for pattern, Handle panics.
func (mux *ServeMux) Handle(pattern string, handler Handler) {
	mux.mu.Lock()
	defer mux.mu.Unlock()

	if mux.m == nil {
		mux.m = make(map[string]muxEntry)
	}
	e := muxEntry{h: handler, pattern: pattern}
	mux.m[pattern] = e
	if pattern[len(pattern)-1] == '/' {
		mux.es = appendSorted(mux.es, e)
	}

	if pattern[0] != '/' {
		mux.hosts = true
	}
}

那么到了这里，我们就会发现，我们所有的的Handler最终都会转换成net/http中的Handler，并且保存在ServerMux中的Map中.

**现在我们来看看其具体是如何进行分发请求的：**其最终会执行到如何下代码： 在这里我将一些基本简单的代码将会进行删除掉. 注释也是很重要的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
go复制代码func (srv *Server) Serve(l net.Listener) error {

	defer srv.trackListener(&l, false)

	var tempDelay time.Duration // how long to sleep on accept failure
	
	ctx := context.WithValue(baseCtx, ServerContextKey, srv)
	for {
        // 重点：通过for循环来接受请求.
		rw, err := l.Accept()
		connCtx := ctx
		tempDelay = 0
		// 构造一个新的conn,然后开启goroutine去执行本次请求.
		c := srv.newConn(rw)
		c.setState(c.rwc, StateNew, runHooks) // before Serve can return
		go c.serve(connCtx)
	}
}

其最终会执行到

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
go复制代码// TODO 很重要的方法.
serverHandler{c.server}.ServeHTTP(w, w.req)

func (sh serverHandler) ServeHTTP(rw ResponseWriter, req *Request) {
	handler := sh.srv.Handler
	// 如果当前的Server中的Handler为空,那么就使用http库中默认的Handler.
	// 我们可以将这一部分替换成我们自己实现的代码.
	if handler == nil {
        // 使用默认.
        // 我们可以自己构造这个. 然后就是当代码执行到这这里之后将会根据我们自己的意图来进行实现.
		handler = DefaultServeMux
	}
    
	if req.RequestURI == "*" && req.Method == "OPTIONS" {
		handler = globalOptionsHandler{}
	}

	// handler--->ServerMux.
  	// 我们来看看该方法的具体实现.
	handler.ServeHTTP(rw, req)
}

// 就是根据request然后去ServeMux中找到属于当前请求的Handler.
func (mux *ServeMux) ServeHTTP(w ResponseWriter, r *Request) {
	if r.RequestURI == "*" {
		if r.ProtoAtLeast(1, 1) {
			w.Header().Set("Connection", "close")
		}
		w.WriteHeader(StatusBadRequest)
		return
	}
	h, _ := mux.Handler(r)
	h.ServeHTTP(w, r)
}

下面代码就是根据Request来从ServeMux中到属于当前请求的Handler.

如果我们要自己开发框架的话，我们可以复用net/http解析请求的流程，直接使用期解析请求好之后的流程，就好比复用Java中的Servlet一样，我当初自己实现过自己解析HTTP请求，最终只实现了Get和POST请求，但是图片并没有实现，最终解析图片失败. 所以我要自己实现Web框架的话会复用net/http底层库.

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
go复制代码func (mux *ServeMux) Handler(r *Request) (h Handler, pattern string) {

	// CONNECT requests are not canonicalized.
	if r.Method == "CONNECT" {
		// If r.URL.Path is /tree and its handler is not registered,
		// the /tree -> /tree/ redirect applies to CONNECT requests
		// but the path canonicalization does not.
		if u, ok := mux.redirectToPathSlash(r.URL.Host, r.URL.Path, r.URL); ok {
			return RedirectHandler(u.String(), StatusMovedPermanently), u.Path
		}

		return mux.handler(r.Host, r.URL.Path)
	}

	// All other requests have any port stripped and path cleaned
	// before passing to mux.handler.
	host := stripHostPort(r.Host)
	path := cleanPath(r.URL.Path)

	// If the given path is /tree and its handler is not registered,
	// redirect for /tree/.
	if u, ok := mux.redirectToPathSlash(host, path, r.URL); ok {
		return RedirectHandler(u.String(), StatusMovedPermanently), u.Path
	}

	if path != r.URL.Path {
		_, pattern = mux.handler(host, path)
		u := &url.URL{Path: path, RawQuery: r.URL.RawQuery}
		return RedirectHandler(u.String(), StatusMovedPermanently), pattern
	}

    // 直接从map中取出自己的对应的handler.
	return mux.handler(host, r.URL.Path)
}

📜 三、总结.

net/http其实就是将我们自己的HandleFunc注册到默认的ServeMux也就是DefaultServeMux中，监听端口时会构建一个Server，而该Server内的Handler将会时为Nil, 当请求解析完毕之后会直接调用serverHandler{c.server}.ServeHTTP(w, w.req)再该方法内部，如果Server的Handler为nil，那么就会使用默认的DefaultServerMux作为当前Server的Handler，然后进行ServerHTTP，如果我们进行实现我们自己的框架，我们可以通过实现一个自己的Handler，并且在创建Server的时候通过给Server赋值Handler从而达到实现我们自己的目的.
欢迎关注公众号：小马正在写Bug.

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第25天，活动详情查看：2021最后一次更文挑战

前情回顾

上篇文章，我们讲到了为什么要选择JWT来实现统一认证授权，其优点更符合初期项目的形成，同样可以通过双token来增强用户的体验度种种，而这些纸上谈兵式的谈论过去，迎来的就是如何去实现这些。

本篇文章就是告诉大家如何在SpringCloud项目中使用JWT实现统一授权。

使用JWT来加密解密

在集成到SpringCloud项目中之前，我们要先做一些JWT技术的调研，但是要调研到什么程度才能做到集成的基本要素呢？

如果你问我，我会告诉你，最起码也要将JWT的token加密、解密弄清楚，或者是调试成功，才能去进行集成至SpringCloud中。

准备工作

首先我们要先提供一个密钥，通过此密钥来进行加解密。

JWT加密

直接贴代码：

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码String key = Base64.getEncoder().encodeToString("zhegekeysuibianshejijiuxingkannixinqing".getBytes(Charsets.UTF_8));
//用户信息
Map<String,String> map = new HashMap<>();
map.put("userId","zhangsan");
//加密
SignatureAlgorithm signatureAlgorithm = SignatureAlgorithm.HS256;
byte[] apiKeySecretBytes = Base64.getDecoder().decode(key);
Key signingKey = new SecretKeySpec(apiKeySecretBytes, signatureAlgorithm.getJcaName());
JwtBuilder builder = Jwts.builder().signWith(signingKey);
map.forEach(builder::claim);
//输出token
System.out.println(builder.compact());

根据上述代码，我们会生成如下图的一大串token。

image.png

JWT解密

解密的话，其实就是将token解析出相应的用户信息。

1
2
3
java复制代码Claims claims = Jwts.parserBuilder().setSigningKey(Base64.getDecoder().decode(JwtUtil.key)).build()
      .parseClaimsJws(token).getBody();
System.out.println(claims.get("userId"));

可以得到下图：

image.png

将JWT集成到Gateway中

登录认证

我们在Controller层书写一个LoginController.java类，在其中书写一个获取token的api接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
java复制代码@RestController
public class LoginController {

    @PostMapping("/token")
    public R<AuthInfo> token(@RequestParam(required = false) String account,
                                      @RequestParam(required = false) String password) {
        Map<String,String> map = new HashMap<>(16);
        map.put("account", account);
        map.put("password", password);
        String token = JwtUtil.createJwt(map);
        if (userInfo == null || userInfo.getUser() == null || userInfo.getUser().getId() == null) {
            return R.fail();
        }
        return R.success(token);
    }

}

编写过滤器验证token

既然搞定了登录获取token的api接口，我们就要将所有访问的URL链接进行过滤器中进行过滤。

所以接下来我们来书写一个认证过滤器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
java复制代码public class AuthFilter implements GlobalFilter, Ordered {

   @Override
   public Mono<Void> filter(ServerWebExchange exchange, GatewayFilterChain chain) {
      String path = exchange.getRequest().getURI().getPath();
      ServerHttpResponse resp = exchange.getResponse();
      String headerToken = exchange.getRequest().getHeaders().getFirst("auth");
      if (StringUtils.isBlank(headerToken)) {
         return unAuth(resp, "缺失令牌,鉴权失败");
      }
      Claims claims = JwtUtil.parseJWT(headerToken);
      if (claims == null) {
         return unAuth(resp, "请求未授权");
      }
      return chain.filter(exchange);
   }

   @Override
   public int getOrder() {
      return -99;
   }

}

总结

Gateway中集成统一认证授权，是微服务网关中必然要集成的功能之一，重要性不言而喻，希望大家可以有所重视。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

今天，准备重新学习一下 Java 中的枚举类型。

为什么现在要去重新学习呐？因为在刚开始学习 Java 的时候，对于枚举这一块的学习不太重视，工作之后呐，又基本上没用过枚举。导致对枚举这个数据类型不太明白，有时候看到别人的代码里用的枚举类型以及相关操作，觉得用的还挺好，就有了重新学习一下的冲动。

话不多说，开始学习！

定义

枚举是什么意思呐？百度百科的说法是这样的：

在数学和计算机科学理论中，一个集的枚举是列出某些有穷序列集的所有成员的程序，或者是一种特定类型对象的计数。这两种类型经常（但不总是）重叠。是一个被命名的整型常数的集合。

枚举在日常生活中很常见，例如表示星期的 SUNDAY、MONDAY、TUESDAY、WEDNESDAY、THURSDAY、FRIDAY、SATURDAY 就是一个枚举。

由此映射到 Java 语言中，即可定义一个表示星期的枚举类：

1
2
3
4
5
java复制代码public enum Week {

    SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY

}

定义枚举类的关键字是 enum,
枚举类对象不能通过 new 出来，里面的 SUNDAY、MONDAY…这些其实就相当于是枚举类 Week 的实例。固定的就这几个，不能在外部创建新的实例。引用的时候直接类.实例名

1
java复制代码Week w = Week.MONDAY;

构造器

枚举类也有构造器，默认是 private 修饰的，并且也只能是 private。观察这段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
java复制代码public enum Week {
    SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY;

    Week(){
        System.out.println("hello");
    }

}

public class Test {
    public static void main(String[] args) {
        Week w = Week.FRIDAY;
    }
}

你会发现这样的结果：

hello

hello

hello

hello

hello

hello

hello
构造函数共执行了7次，正好对应类中枚举项的数量。其实此类的枚举项的创建，就相当于其他类调用无参构造器 new 出来的对象，也就是这个枚举类创建了7次实例，所以输出了7个 hello。

除了无参构造器，枚举类也有有参构造器。

1
2
3
4
5
6
7
8
java复制代码public enum Week {
    SUNDAY(7), MONDAY(1), TUESDAY(2), WEDNESDAY(3), THURSDAY(4), FRIDAY(5), SATURDAY(6);

    Week(int weekNum){
        System.out.println(weekNum);
    }

}

这次将会输出：

7

1

2

3

4

5

6

枚举类成员

枚举类和正常类一样，也可以有成员变量、实例方法、静态方法等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
java复制代码public enum Week {
    SUNDAY(7), MONDAY(1), TUESDAY(2), WEDNESDAY(3), THURSDAY(4), FRIDAY(5), SATURDAY(6);

    private int weekNum;

    Week(int weekNum){
        this.weekNum = weekNum;
    }

    public int getWeekNum() {
        return weekNum;
    }

}

使用：

1
2
3
4
5
6
java复制代码public class Test {
    public static void main(String[] args) {
        Week w = Week.FRIDAY;
        System.out.println(w.getWeekNum());
    }
}

输出：

5

枚举类中还可以有抽象方法。

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
java复制代码public enum Week {
    SUNDAY(){
        @Override
        public void getWeekNum() {
            System.out.println(7);
        }
    },
    MONDAY() {
        @Override
        public void getWeekNum() {
            System.out.println("星期一");
        }
    },

    TUESDAY(){
        @Override
        public void getWeekNum() {
            System.out.println("礼拜二");
        }
    },
    WEDNESDAY(){
        @Override
        public void getWeekNum() {
            System.out.println("周三");
        }
    };

    public abstract void getWeekNum();
}

public class Test {
    public static void main(String[] args) {
        Week w = Week.TUESDAY;
        w.getWeekNum();
    }
}

输出：

礼拜二

values()、valueOf(String name) 方法

每个枚举类都有两个 static 方法：

  • static Direction[] values()：返回本类所有枚举常量；
  • static Direction valueOf(String name)：通过枚举常量的名字返回Direction常量，注意，这个方法与Enum类中的valueOf()方法的参数个数不同。
1
2
3
4
5
6
7
8
java复制代码public class Test {
    public static void main(String[] args) {
        for (Week w : Week.values()) {
            System.out.println(w);
        }
        System.out.println("星期天：" + Week.valueOf("SUNDAY"));
    }
}

结果如下：

SUNDAY

MONDAY

TUESDAY

WEDNESDAY

THURSDAY

FRIDAY

SATURDAY

星期天：SUNDAY

枚举的用法

1. 类型约束

相信大家平时开发过程中，肯定这样定义过常量来使用：

1
2
3
4
5
6
7
java复制代码public class Discount {
    public static final double EIGHT_DISCOUNT = 0.8;

    public static final double SIX_DISCOUNT = 0.6;

    public static final double FIVE_DISCOUNT = 0.5;
}

这样定义其实也没有什么问题，但是如果有一个方法是这样的：

1
2
3
java复制代码BigDecimal calculatePrice(double discount){
    //...
}

需要传入商品折扣计算价格，使用上面的常量定义就没有类型上的约束，传入任何 double 类型的值都可以，编译器不会发出警告。单如果你使用枚举来定义这种情况，就会有更强的类型约束:

1
2
3
4
5
6
7
8
9
10
11
12
13
java复制代码public enum Discount {
    EIGHT_DISCOUNT(0.8), SIX_DISCOUNT(0.6), FIVE_DISCOUNT(0.5);

    private double discountNum;

    Discount(double discountNum) {
        this.discountNum = discountNum;
    }

    double getDiscountNum(){
        return discountNum;
    }
}

使用：

1
2
3
4
5
6
7
8
9
10
11
java复制代码public class Test {
    public static void main(String[] args) {
        calculatePrice(Discount.EIGHT_DISCOUNT);
    }

    static BigDecimal calculatePrice(Discount discount){
        System.out.println(discount.getDiscountNum());
        //...
        return null;
    }
}

0.8

2. switch 中使用

1
2
3
4
5
6
7
8
9
10
11
java复制代码public class Test {
    public static void main(String[] args) {
        Week w = Week.MONDAY;
        switch (w) {
            case MONDAY:
                System.out.println("周一"); break;
            case TUESDAY:
                System.out.println("周二"); break;
        }
    }
}

周一

3. 实现接口，消除 if/else

我们创建的枚举类默认是被final修饰，并且默认继承了Enum类。因此不能再继承其他的类。但是可以去实现接口。

有这样一个判断场景。

1
2
3
4
5
6
7
java复制代码if ("dog".equals(animalType)){
    System.out.println("吃骨头");
} else if ("cat".equals(animalType)) {
    System.out.println("吃鱼干");
} else if ("sheep") {
    System.out.println("吃草");
}

怎样用枚举来消除掉 if/else 呐，看下面的代码：

先定义一个接口，里面有一个通用方法 eat()

1
2
3
4
java复制代码public interface Eat {
    //吃
    String eat();
}

然后创建枚举类实现这个接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
java复制代码public enum AnimalEnum implements Eat {

    Dog(){
        @Override
        public void eat() {
            System.out.println("吃骨头");
        }
    },

    Cat() {
        @Override
        public void eat() {
            System.out.println("吃鱼干");
        }
    },

    Sheep() {
        @Override
        public void eat() {
            System.out.println("吃草");
        }
    }

}

调用的时候只需要一行代码：

1
2
3
4
5
java复制代码public class Test {
    public static void main(String[] args) {
        AnimalEnum.valueOf("Cat").eat();
    }
}

吃鱼干

而且这样一来，以后假如我想扩充新的动物，只需要去枚举类中加代码即可，而不用改任何老代码，符合开闭原则！

4. 单例模式中应用

枚举在单例模式的一种实现方式中也可以用到。

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
java复制代码/**
 * @Author:
 * @Description: 枚举  线程安全
 */
public class SingletonExample {

    /**
     * 构造函数私有化，避免外部创建实例
     */
    private SingletonExample(){}

    private static SingletonExample getInstance() {
        return Singleton.INSTANCE.getInstance();
    }

    private enum Singleton {
        INSTANCE;
        private SingletonExample instance;

        // JVM 保证这个方法绝对只调用一次
        Singleton() {
            instance = new SingletonExample();
        }

        public SingletonExample getInstance() {
            return instance;
        }
    }
}

总结

Java 中其实还有专门用于枚举的集合类，EnumSet 和 EnumMap，这里我们不再叙述。

学习下来还是收获蛮多的。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第24天，活动详情查看：2021最后一次更文挑战」

前言

1
复制代码大家好，我是程序猿小白 gw_Gw，很高兴能和大家一起学习进步。

以下内容部分来自于网络，如有侵权，请联系我删除，本文仅用于学习交流，不用作任何商业用途。

摘要

1
arduino复制代码本文主要介绍JSP脚本中的9个内置对象中的config对象,exception对象和out对象。

1.2 config对象

通过之前查看_jspService()方法我们知道config是ServletConfig类型的一个实例，该对象可以通过getInitParameter(String paramName)来获取配置参数。

首先要在web.xml中通过需要把JSP当成Servlel来配置，通过init-param元素来配置参数，然后才能在JSP页面中获得该参数。

实例展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
xml复制代码<servlet>
        <!--servlet名字，为下面的jsp页面起的Servlet名-->
        <servlet-name>servletTest</servlet-name>
        <!--指定把哪个JSP页面配置成Servlet-->
        <jsp-file>/test.jsp</jsp-file>
​
        <!--配置参数-->
        <init-param>
            <param-name>age</param-name>
            <param-value>20</param-value>
        </init-param>
​
</servlet>

把JSP当作Servlet来配置还不够，如果要想要配置的参数生效，还需要通过servlet-mapping元素来为JSP页面配置路径。

实例展示：

1
2
3
4
xml复制代码<servlet-mapping>
    <servlet-name>servletTest</servlet-name>
    <url-pattern>/servletTest</url-pattern>
</servlet-mapping>

经过以上的两步已经把一个JSP页面当成了一个Servlet，并且为Servlet配置了age属性，同时为Servlet指定了路径。

在浏览器就可以输入指定的路径来访问该Servlet(JSP)

image-20211126185803774

1.3 exception对象

exception对象是Throwable的一个实例，该实例代表了其他页面的错误和异常，只有当前页面被设置为错误处理页面时该实例才存在。

在JSP页面遇到异常时，通过forward转发到错误和处理页面，异常处理页面会调用exception对象来方法输出对应的错误和异常。

实例展示：

index.jsp:

1
2
3
4
5
6
7
8
9
10
11
12
13
xml复制代码<%@ page contentType="text/html; charset=UTF-8" pageEncoding="UTF-8" errorPage="ErrorHandlePage.jsp" %>
<!DOCTYPE html>
<html>
<head>
  <title>JSP - Hello World</title>
</head>
<body>
<%!
  int num=1;
%>
<%=num/0%>
</body>
</html>

ErrorHandlePage.jsp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
css复制代码<%--
  Created by IntelliJ IDEA.
  User: Poison
  Date: 2021/11/26
  Time: 19:10:34
  To change this template use File | Settings | File Templates.
--%>
<%@ page contentType="text/html;charset=UTF-8" language="java" isErrorPage="true" %>
<html>
<head>
    <title>ErrorHandlePage</title>
</head>
<body>
异常类型是：<%=exception.getClass()%><br>
异常信息是：<%=exception.getMessage()%><br>
<%
    System.out.println("异常栈信息是：");
    exception.printStackTrace();
%>
</body>
</html>

image-20211126193540670

image-20211126193606138

可以看到，进行错误处理时，并地址栏地址并没有改变，也证明是使用的forward来转发页面。

注意：需要在index.jsp设置错误处理页面,在错误处理页面设置isErrorPage属性为true。

1.4 out对象

out对象是JspWriter的一个实例，代表页面输出流，用于在页面上输出变量值和常量值。out对象就相当于JSP输出表达式。

实例展示：

1
2
3
erlang复制代码<%
  out.print("这是out对象产生的输出！");
%>

image-20211126201701032

小结

以上就是JSP脚本中的9个内置对象中的config对象,exception对象和out对象的一些介绍，希望对读者有所帮助，如有不正之处，欢迎留言评论。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第25天，活动详情查看：2021最后一次更文挑战」

GridLayout布局管理器

网格布局管理器使用纵横线将容器分成n行m列大小相等的网格。每个网格中放置一个组件。添加到容器中的组件首先放置在第1行第1列(左上角)的网格中，然后在第1行的网格中从左向右依次放置其他组件。行满后，继续在下一行中从左到右放置组件。与FlowLayout不同的是放置在GridLayout布局管理器中的组件，将自动占据网格的整个区域。

1.GridLayout类在java.awt包中

  1. GridLayout布局使得容器中的各个组件以规则的网格状分布，平均占据整个容器空间

3.当容器的大小发生变化时，其中的组件大小也发生变化，但始终平均占据容器空间

4.GridLayout容器中的组件始终充满网格某个块
的所有空间
5.GridLayout容器中添加组件时，以行为主序：
第一行第一个，第一行第二个……第二行第一个……
在这里插入图片描述

GridLayout的构造方法

1.public GridLayout(int rows, int cols)
—— 创建rows行cols列的GridLayout对象，行列之间的默认宽度为5个像素

2.public GridLayout(int rows, int cols, int hgap,int vgap)
—— 创建rows行cols列的GridLayout对象，行列之间的宽度分别为hgap个像素和vgap个像素

GridLayout类的常用构造方法如下:

1.GridLayout(): 构建一个一行一列的GridLayout对象。

2.GridLayout(int rows, int cols): 用指定行数和列数去构建GridLayout对象。

3.GridLayout(int rows, int cols, int hgap, int vgap): 指定行数、列数、水平间隔和垂直间隔去构建GridLayout对象。

总结:

1、将容器像棋盘一样进行m行n列的网格分布

2、网格每行高度(每列宽度)相同，等于容器的高度(宽度)除以网格的行数(列数)

3、不能改变组件大小只能改变组件之间的水平和垂直间隔

4、添加到容器的组件 从左向右 自上而下 依次放置

5、当容器大小发生改变时，各组件的相对位置不变，大小会改变。

使用GridLayout要注意的地方:

因为GirdLayout是4.0后才推出的,所以minSDK版本要改为14或者以上的版本, 不然写布局代码的时候,这玩意就会莫名其妙地出错,说找不到这个GridLayout, 当然,如果你要低版本兼容的话,就要看下面的内容了！

低版本sdk如何使用GridLayout:

解决方法很简单:只需要导入v7包的gridlayout包即可! v7包一般在sdk下的:sdk\extras\android\support\v7\gridlayout目录下 如果你没有的话,也可以到这里下载: gridlayout_v7_jay.rar但是用的时候,标签却是这样写的:

1
xml复制代码<android.support.v7.widget.GridLayout>`

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战」。

通过前面几篇图片转字符、灰度图的文章介绍之后，接下来我们再来看一个有意思的东西，基于前文的基础，实现位图转矢量图的功能

关于位图与矢量图的简单理解如下：

  • 位图：如Jpg/png，放大之后会失真，看到像素块
  • 矢量图：如svg，放大图片也不会失真

1. 实现策略

要实现位图转矢量图，可不是一个简单的活；当然我们这里也不追求完美实现，在前文的基础上，可以想到一个实现策略

  • 首先根据位图输出字符画
  • 然后通过字符画，来生成矢量图

基于上面这个策略，第一步生成字符前一篇博文已经介绍过了；接下来重点就是如何根据输出的字符数组，来生成svg呢？

2. 实现方法

第一步位图输出字符画的代码就不贴了，有兴趣的小伙伴可以参考前文

接下来我们重点看一下如何根据生成的List<String>来生成svg图

首先我们定义一个svg模板，用于来表示基于字符输出的矢量图，如下

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
svg复制代码<?xml version="1.0" encoding="UTF-8" ?>
<svg xmlns="http://www.w3.org/2000/svg"
        viewBox="0 0 {width} {height}"
        style="width: 100%; height: 100%; overflow: auto; fill: {BG_COLOR}">
    <script type="text/javascript"><![CDATA[
window.addEventListener('load',function() {
    var bounding_rect = document.getElementById("bounding-rect");
    var text = document.getElementById("ascii");
    var bb_text = text.getBBox();
    var font_size = Math.round(1e3 * bb_text.height / bb_text.width) / 1e3;
    text.setAttribute("font-size", font_size + "px");
    bb_text = text.getBBox();
    bounding_rect.setAttribute("width", bb_text.width);
    bounding_rect.setAttribute("height", bb_text.height);
}, false);
    ]]></script>
    <style type="text/css">
    text.ascii-art {
        user-select: none;
        whiteSpace: "pre";
        fill: {FONT_COLOR};
        -webkit-user-select:none;
        -khtml-user-select:none;
        -moz-user-select:none;
        -ms-user-select:none;
    }
    </style>
    <rect x="0" y="0" height="100%" width="100%" id="bounding-rect"/>
    <text x="0" y="0" id="ascii" font-family="monospace, courier" text-anchor="start" font-size="1px" class="ascii-art">
    <tspan x="0" dy="0.794%" textLength="100%" xml:space="preserve">                                                                             ux                                               </tspan>
    <tspan x="0" dy="0.794%" textLength="100%" xml:space="preserve">                                                                     .....  </tspan>
    </text>
</svg>

对于上面的模板中，有几个关键值需要替换

  • svg 标签中
    • {width}: 生成矢量图的宽度
    • {height}: 生成矢量图的高度
    • {BG_COLOR}: 背景颜色
  • style 样式设置
    • {FONT_COLOR}: 字符渲染颜色

其次tspan标签内容就是我们需要输出的字符，一行字符对应一个tspan标签

因此我们的实现逻辑就是上面这个模板的关键字替换输出了

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
java复制代码/**
 * 字符转svg矢量图
 *
 * @param lines
 * @param bgColor
 * @param fontColor
 * @return
 */
public static String ascii2svg(List<String> lines, String bgColor, String fontColor) {
    StringBuilder builder = new StringBuilder();
    int height = lines.size();
    int width = lines.stream().max(Comparator.comparingInt(String::length)).get().length();
    builder.append(StrUtil.replace(SVG_START, "{width}", String.valueOf(width), "{height}", String.valueOf(height), "{BG_COLOR}", bgColor, "{FONT_COLOR}", fontColor));

	 // 计算tspan标签中的dy值
    float dy = 100.0f / height;
    String start = String.format("<tspan x=\"0\" dy=\"%.3f%%\" textLength=\"100%%\" xml:space=\"preserve\">", dy);
    String end = "</tspan>";
    for (String line : lines) {
        builder.append(start)
        		// 转义支持
                .append(StrUtil.replace(line,"&", "&amp;", "\"", "&quot;", "<", "&lt;", ">", "&gt;"))
                .append(end).append("\n");
    }

    builder.append(SVG_END);
    return builder.toString();
}

注意上面的实现逻辑中的几个变量就是上面模板的关键值，就不重复输出了；详情看文末的源码查看

  • SVG_START
  • SVG_END

3. 实测演示

上面已经贴出了核心的实现代码，接下来我们根据成品来看一下输出效果如何；下面是直接使用封装好的方法来调用测试

项目源码：github.com/liuyueyi/qu…

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码@Test
public void testSvg() throws Exception {
    String file = "http://pic.dphydh.com/pic/newspic/2017-12-13/505831-1.png";
	// String file = "http://5b0988e595225.cdn.sohucs.com/images/20200410/76499041d3b144b58d6ed83f307df8a3.jpeg";
    ImgPixelWrapper.build()
            .setSourceImg(file)
            .setBlockSize(3)
            .setRate(0.6)
            .setPixelType(PixelStyleEnum.CHAR_BLACK)
            .build()
            .asSvgFile(prefix + "/out.svg");
}

输出的svg文件如下

实例图:

00.jpg

一灰灰的联系方式

尽信书则不如无书，以上内容，纯属一家之言，因个人能力有限，难免有疏漏和错误之处，如发现bug或者有更好的建议，欢迎批评指正，不吝感激

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第26天，活动详情查看：2021最后一次更文挑战」

前言

前面把后台功能完成了，今天准备把后端关于登录的接口写出来。

新建模型

需要做一个简单的后台用户表，做一个最简单的功能，用户名，密码，后台显示的头像。然后需要一个token字段，一般token存放在redis里面，为了简单易用，我准备直接放在后台用户表里面，然后设置一个过期时间。
在model.go里面加上ORM映射的结构体，在自动迁移的代码里加上这个结构体

1
2
3
4
5
6
7
8
go复制代码type AdminUser struct {
	ID           uint `gorm:"primary_key"`
	Name         string
	Avatar       string
	Password     string
	Token        string
	ExpirationAt time.Time `json:"created_at"`
}
1
less复制代码db.AutoMigrate(&UrlList{}, &UrlType{}, &AdminUser{}) //自动迁移

启动项目自动会在数据库创建数据表，然后新建数据

image.png

新建中间件方法

在需要中间件验证的地方使用这个Token中间件。每次经过中间件的时候查询admin_user这张表是否存在这个token,且没有过期。然后把token携带的内容设置到上下文提供给某些接口使用。这里需要注意中间件的拦截需要使用c.about()方法不能只用return。不然还是会继续走路由方法会有两个return。

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
43
44
45
46
47
48
49
50
51
go复制代码import
...
"main/model"
...
func Token() gin.HandlerFunc {
	return func(context *gin.Context) {
		token := context.Request.Header.Get("X-Token")
		token_exsits, err := model.TokenInfo(token)
		if err != nil {
			resospnseWithError(401, "非法请求", context)
			return
		}
		fmt.Println(token_exsits)
		if len(token_exsits) != 0 {
			//先做时间判断
			target_time, _ := time.ParseInLocation("2006-01-02 15:04:05", time.Time(token_exsits[0].ExpirationAt).Format("2006-01-02 15:04:05"), time.Local) //需要加上time.Local不然会自动加八小时
			if target_time.Unix() <= time.Now().Unix() {
				fmt.Println("过期报错")
				//过期报错
				resospnseWithError(401, "timeout", context)
				return
			}
			//token没过期，更新到期时间
			now := time.Unix(time.Now().Unix()+7200, 0).Format("2006-01-02 15:04:05")
			err = model.UpdateTokenTime(token, now)
			context.Set("name", token_exsits[0].Name)
			context.Set("avatar", token_exsits[0].Avatar)
			context.Set("token", token)
		} else {
			fmt.Println("没了")
			resospnseWithError(401, "已退出", context)
			return
		}

		context.Next()
	}
}

type ResultCont struct {
	Code int         `json:"code"` //提示代码
	Msg  string      `json:"msg"`  //提示信息
	Data interface{} `json:"data"` //数据
}

func resospnseWithError(code int, message string, c *gin.Context) {
	var res ResultCont
	res.Code = code
	res.Msg = message
	c.JSON(200, res) //前端返回也要返回200才能拦截
	c.Abort()
}

新建修改路由，使用中间件

主要有三个方法login,info，logout三个方法都不需要走token中间件，info和logout和都是从get方法的param中获取token。login用于传递用户名密码就不需要中间件，涉及到的路由代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
css复制代码	admin := router.Group("/admin")
	admin.Use(middleware.Token())
	{
		// 路径映射
		// api:=controller.NewDyController()
		admin.GET("/getTypeList", controller.GetTypeList)
		admin.POST("/DelType", controller.DelType)
		admin.POST("/AddType", controller.AddType)
		admin.POST("/EditType", controller.EditType)
		admin.POST("/getUrlList", controller.GetUrlList)
		admin.POST("/DelUrl", controller.DelUrl)
		admin.POST("/AddUrl", controller.AddUrl)
		admin.POST("/EditUrl", controller.EditUrl)
		admin.POST("/user/logout", controller.Logout)
	}

	adminuser := router.Group("/admin/user")
	{
		adminuser.POST("/login", controller.Login)
		adminuser.GET("/info", controller.Info)
	}

新建控制器

控制器获取服务方法的内容判断，还有获取中间件设置的上下文的内容交给服务方法，处理错误，规范返回

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
go复制代码func Login(c *gin.Context) {
	var json request.LoginRequest
	if err := c.ShouldBindJSON(&json); err != nil {
		c.JSON(http.StatusBadRequest, gin.H{"error": err.Error()})
		return
	}
	result := global.NewResult(c)
	data, err := service.Login(json)
	if err != nil {
		result.Error(5201, err.Error(), "登录失败")
		return
	}
	result.Success(data)
}

func Info(c *gin.Context) {
	token := c.DefaultQuery("token", "")
	result := global.NewResult(c)
	data, err := service.Info(token)
	if err != nil {
		result.Error(5201, err.Error(), "登录失败")
		return
	}
	result.Success(data)
}

func Logout(c *gin.Context) {
	token := c.MustGet("token").(string)
	result := global.NewResult(c)
	err := service.Logout(token)
	if err != nil {
		result.Error(5201, err.Error(), "退出登录失败")
		return
	}
	result.Success("退出登录成功")
}

验证器

验证器的内容很少，主要是登录必须要字符串的用户名密码

1
2
3
4
c复制代码type LoginRequest struct {
	Username string `form:"username" json:"username" binding:"required"`
	Password string `form:"password" json:"password" binding:"required"`
}

服务方法

文件位置是service/service.go,今天逻辑最重要的地方，主要是登录，自己做了一些注释，判断有没有token，token过期时间，根据这些判断进行生成随机token或者直接返回操作，这里还引入了一些新的包，专门存放自己写的公共方法,util包：

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
scss复制代码func Login(json request.LoginRequest) (data string, err error) {
	//判断有没有这个用户密码
	//没有报错,有了就判断token有没有，没有就创建返回，有就判断时间，时间没过期就返回，过期了就重新生成返回
	var user []model.AdminUser
        json.Password = util.FixMd5(json.Password + "boomxiakalaka")
	user, err = model.Login(json.Username, json.Password)
	if len(user) > 0 {
		//成功
		if user[0].Token == "" {
			//token为空，创建更新返回
			now := time.Unix(time.Now().Unix()+7200, 0).Format("2006-01-02 15:04:05")
			token := util.GetRandomString(32)
			err = model.LoginCreateToken(json.Username, json.Password, token, now)
			return token, err
		} else {
			//token不为空 ，判断时间，时间不过期直接返回
			target_time, _ := time.ParseInLocation("2006-01-02 15:04:05", time.Time(user[0].ExpirationAt).Format("2006-01-02 15:04:05"), time.Local) //需要加上time.Local不然会自动加八小时
			if target_time.Unix() >= time.Now().Unix() {
				return user[0].Token, nil
			} else {
				//时间过期
				token := util.GetRandomString(32)
				now := time.Unix(time.Now().Unix()+7200, 0).Format("2006-01-02 15:04:05")
				err = model.LoginCreateToken(json.Username, json.Password, token, now)
				return token, err
			}
		}
	}
	return "登陆失败", errors.New("登陆失败")
}

func Info(token string) (data interface{}, err error) {
	list, err := model.Info(token)
	return list, err
}

func Logout(token string) (err error) {
	err = model.Logout(token)
	return err
}

公共方法

主要是生成随机的32未字符串,MD5混淆，在根目录下新建util/util.go文件,引入了两个内置包，一个是用于随机的包，和时间处理的包，这里就可以看到goalng的简陋了，随机竟然还需要获取时间来做一个随机种子来做成真正的随机；MD5混淆主要是用于密码保存，总所周知密码原文直接存放在数据库是非常不安全的，以下是整个文件内容：

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
go复制代码package util

import (
	"math/rand"
	"time"
)

// 随机生成指定位数的大写字母和数字的组合
func GetRandomString(l int) string {
	str := "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
	bytes := []byte(str)
	result := []byte{}
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	for i := 0; i < l; i++ {
		result = append(result, bytes[r.Intn(len(bytes))])
	}
	return string(result)
}

//MD5混淆
func FixMd5(str string) string {
	data := []byte(str)
	has := md5.Sum(data)
	md5str := fmt.Sprintf("%x", has)
	return md5str
}

模型方法

对于GORM操作不是很熟悉，用了很多方法实现了各种需求，获取用户信息，创建token，删除token。

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
43
go复制代码func Login(name string, password string) (list []AdminUser, err error) {
	var user []AdminUser
	db.Debug().Where("name = ? and password = ?", name, password).First(&user)

	return user, nil
}

func LoginCreateToken(name string, password string, token string, expiration_at string) (err error) {
	return db.Debug().Table("admin_user").Where("name = ? and password = ?", name, password).Updates(map[string]interface{}{"token": token, "expiration_at": expiration_at}).Error
}

func TokenInfo(token string) (list []AdminUser, err error) {
	var user []AdminUser
	db.Debug().Where("token = ? ", token).First(&user)
	return user, nil
}

func Info(token string) (data interface{}, err error) {
	type Result struct {
		Name   string
		Avatar string
	}
	var result Result
	db.Debug().Table("admin_user").Select("name, avatar").Where("token = ? ", token).Scan(&result)
	return result, nil
}

func Logout(token string) (err error) {
	return db.Debug().Table("admin_user").Where("token = ? ", token).Updates(map[string]interface{}{"token": ""}).Error
}
func UpdateTokenTime(token string, expiration_at string) (err error) {
	return db.Debug().Table("admin_user").Where("token = ? ", token).Updates(map[string]interface{}{"expiration_at": expiration_at}).Error
}

func TokenFind(token string) (status bool) {
	var user []AdminUser
	rowsAffects := db.Debug().Where("token = ? ", token).First(&user).RowsAffected
	if rowsAffects == 0 {
		return false
	} else {
		return true
	}
}

总结

主要登录逻辑最为复杂，对于简单的内容系统，一般是直接在数据库添加数据，不做账户注册，我们公司后台就是。先需要把密码混淆后对数据库对比，有了就登录成功了，成功之前还需要更新token给前端使用，还需要动态更新设置token的到期时间。代码比较多，下篇更新前端关于的设置。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战」。

二叉树的遍历（traversing binary tree）是指从根节点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

本文介绍了4种二叉树的遍历方法，分别是前序、中序、后续、层序遍历，并且每种方法均提供了详尽的Java语言的代码演示，在最后还介绍了遍历结果推导的方法。

1 概述

二叉树的遍历（traversing binary tree）是指从根节点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等，它算作是一个抽象操作。在这里我们可以简单地假定访问就是输出结点的数据信息。

二叉树的遍历次序不同于线性结构，最多也就是从头至尾、循环、双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。因此遍历的方式也有很多种，主要的方式有先序遍历、中序遍历、后序遍历、层序遍历。

关于二叉树的知识，如果不是很了解，可以看这篇文章：二叉树的入门以及Java实现案例详解。

本文将以下面的二叉树来作为样例进行遍历：

在这里插入图片描述

2 构建二叉树

首先，构建出上图中二叉树，下面是二叉树的简单链式存储结构的实现。二叉树的实现在：二叉树的入门以及Java实现案例详解中有讲解。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
java复制代码/**
 * 二叉树的链式存储结构的简单实现
 */
public class LinkedBinaryTree<E> {

    /**
     * 外部保存根节点的引用
     */
    private BinaryTreeNode<E> root;

    /**
     * 树节点的数量
     */
    private int size;

    /**
     * 内部节点对象
     *
     * @param <E> 数据类型
     */
    public static class BinaryTreeNode<E> {

        //数据域
        E data;
        //左子节点
        BinaryTreeNode<E> left;
        //右子节点
        BinaryTreeNode<E> right;

        public BinaryTreeNode(E data) {
            this.data = data;
        }

        public BinaryTreeNode(E data, BinaryTreeNode<E> left, BinaryTreeNode<E> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return data.toString();
        }
        /*@Override
        public String toString() {
            return "BinaryTreeNode{" +
                    "data=" + data +
                    '}';
        }*/
    }

    /**
     * 空构造器
     */
    public LinkedBinaryTree() {
    }

    /**
     * 构造器,初始化root节点
     *
     * @param root 根节点数据
     */
    public LinkedBinaryTree(E root) {
        checkNullData(root);
        this.root = new BinaryTreeNode<>(root);
        size++;
    }

    /**
     * 添加子节点
     *
     * @param parent 父节点的引用
     * @param data   节点数据
     * @param left   是否是左子节点,true 是;false 否
     */
    public BinaryTreeNode<E> addChild(BinaryTreeNode<E> parent, E data, boolean left) {
        checkNullParent(parent);
        checkNullData(data);
        BinaryTreeNode<E> node = new BinaryTreeNode<>(data);
        if (left) {
            if (parent.left != null) {
                throw new IllegalStateException("该父节点已经存在左子节点,添加失败");
            }
            parent.left = node;
        } else {
            if (parent.right != null) {
                throw new IllegalStateException("该父节点已经存在右子节点,添加失败");
            }
            parent.right = node;
        }
        size++;
        return node;
    }

    /**
     * 是否是空树
     *
     * @return true 是 ;false 否
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获取根节点
     *
     * @return 根节点 ;或者null--表示空树
     */
    public BinaryTreeNode<E> getRoot() {
        return root;
    }

    /**
     * 获取左子节点
     *
     * @param parent 父节点引用
     * @return 左子节点或者null--表示没有左子节点
     */
    public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.left;
    }

    /**
     * 获取右子节点
     *
     * @param parent 父节点引用
     * @return 右子节点或者null--表示没有右子节点
     */
    public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.right;
    }


    /**
     * 数据判null
     *
     * @param data 添加的数据
     */
    private void checkNullData(E data) {
        if (data == null) {
            throw new NullPointerException("数据不允许为null");
        }
    }


    /**
     * 检查父节点是否为null
     *
     * @param parent 父节点引用
     */
    private void checkNullParent(BinaryTreeNode<E> parent) {
        if (parent == null) {
            throw new NoSuchElementException("父节点不能为null");
        }
    }
}

2.1 添加节点数据

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
java复制代码public class TreeTest {
    /**
     * 构建二叉树,添加根节点r
     */
    LinkedBinaryTree<String> integerLinkedBinaryTree = new LinkedBinaryTree<>("r");

    @Before
    public void buildTree() {
        /*构建二叉树*/
        LinkedBinaryTree.BinaryTreeNode<String> r = integerLinkedBinaryTree.getRoot();
        //添加r根节点的左子结点a
        LinkedBinaryTree.BinaryTreeNode<String> a = integerLinkedBinaryTree.addChild(r, "a", true);
        //添加r根节点的右子结点b
        LinkedBinaryTree.BinaryTreeNode<String> b = integerLinkedBinaryTree.addChild(r, "b", false);
        //添加a节点的左子结点c
        LinkedBinaryTree.BinaryTreeNode<String> c = integerLinkedBinaryTree.addChild(a, "c", true);
        //添加a节点的右子结点d
        LinkedBinaryTree.BinaryTreeNode<String> d = integerLinkedBinaryTree.addChild(a, "d", false);
        //添加b节点的左子结点e
        LinkedBinaryTree.BinaryTreeNode<String> e = integerLinkedBinaryTree.addChild(b, "e", true);
        //添加b节点的右子结点f
        LinkedBinaryTree.BinaryTreeNode<String> f = integerLinkedBinaryTree.addChild(b, "f", false);
        //添加c节点的左子结点g
        LinkedBinaryTree.BinaryTreeNode<String> g = integerLinkedBinaryTree.addChild(c, "g", true);
        //添加c节点的右子结点h
        LinkedBinaryTree.BinaryTreeNode<String> h = integerLinkedBinaryTree.addChild(c, "h", false);
        //添加d节点的左子结点i
        LinkedBinaryTree.BinaryTreeNode<String> i = integerLinkedBinaryTree.addChild(d, "i", true);
        //添加f节点的左子结点j
        LinkedBinaryTree.BinaryTreeNode<String> j = integerLinkedBinaryTree.addChild(f, "j", true);
    }
}

3 先序遍历 preorder traversal

3.1 先序遍历的介绍

规则是：若二叉树为空，则空操作返回；否则，从根节点开始，先遍历根，然后是左子树，最后遍历右子树；对于子树，同样从子树根开始，先遍历根，然后是左子树，最后遍历右子树。采用了递归的思想。

先序遍历中，对节点的遍历工作，是在对该节点的儿子节点的遍历之前进行遍历的。这也就是“先序”的得来。

先序遍历也叫前序遍历。

从r根节点开始，其遍历流程如下：

在这里插入图片描述

3.2 先序遍历的简单实现

以下代码添加到LinkedBinaryTree类中。

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
43
44
45
java复制代码/**
 * 保存遍历出来的节点数据
 */
ThreadLocal<StringBuilder> threadLocal = ThreadLocal.withInitial(StringBuilder::new);

/**
 * 先序遍历,提供给外部使用的api
 *
 * @return 遍历的数据
 */
public String toPreorderTraversalString() {
    //如果是空树,直接返回空
    if (isEmpty()) {
        return null;
    }
    //从根节点开始递归
    preorderTraversal(root);

    //获取遍历结果
    String s1 = threadLocal.get().toString();
    threadLocal.remove();
    return s1.substring(0, s1.length() - 3);
}

/**
 * 先序遍历 内部使用的递归遍历方法
 *
 * @param root 节点,从根节点开始
 */
private void preorderTraversal(BinaryTreeNode<E> root) {
    //添加数节点
    threadLocal.get().append(root).append("-->");
    //获取节点的左子节点
    BinaryTreeNode<E> left = getLeft(root);
    if (left != null) {
        //如果左子节点不为null,则继续递归遍历该左子节点
        preorderTraversal(left);
    }
    //获取节点的右子节点
    BinaryTreeNode<E> right = getRight(root);
    if (right != null) {
        //如果右子节点不为null,则继续递归遍历该右子节点
        preorderTraversal(right);
    }
}

3.2.1 测试

1
2
3
4
5
6
7
8
java复制代码/**
 * 先序遍历
 */
@Test
public void preorderTraversal() {
    String s = integerLinkedBinaryTree.toPreorderTraversalString();
    System.out.println(s);
}

查看输出：

r–>a–>c–>g–>h–>d–>i–>b–>e–>f–>j

确实图中的遍历顺序一致。

4 中序遍历 inorder traversal

4.1 中序遍历的介绍

规则是：若树为空，则空操作返回；否则，从根节点开始，先遍历根结点的左子树，然后是访问根结点，最后遍历右子树；对于子树，同样，先遍历子树根节点的左子树，然后是访问子树根结点，最后遍历右子树。采用了递归的思想。

中序遍历中，对节点的遍历工作，是在对该节点的左儿子节点的遍历之后、右儿子节点的遍历之前进行遍历的。这也就是“中序”的得来。

对图中的树采用中序遍历，从r根节点开始，顺序如下：
在这里插入图片描述

4.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
33
34
35
36
37
38
39
40
java复制代码/**
 * 中序遍历,提供给外部使用的api
 *
 * @return 遍历的数据
 */
public String toInorderTraversalString() {
    //如果是空树,直接返回空
    if (isEmpty()) {
        return null;
    }
    //从根节点开始递归
    inorderTraversal(root);

    //获取遍历结果
    String s1 = threadLocal.get().toString();
    threadLocal.remove();
    return s1.substring(0, s1.length() - 3);
}

/**
 * 中序遍历 内部使用的递归遍历方法
 *
 * @param root 节点,从根节点开始
 */
private void inorderTraversal(BinaryTreeNode<E> root) {

    BinaryTreeNode<E> left = getLeft(root);
    if (left != null) {
        //如果左子节点不为null,则继续递归遍历该左子节点
        inorderTraversal(left);
    }
    //添加数据节点
    threadLocal.get().append(root).append("-->");
    //获取节点的右子节点
    BinaryTreeNode<E> right = getRight(root);
    if (right != null) {
        //如果右子节点不为null,则继续递归遍历该右子节点
        inorderTraversal(right);
    }
}

4.2.1 测试

1
2
3
4
5
6
7
8
java复制代码/**
 * 中序遍历
 */
@Test
public void inorderTraversal() {
    String s = integerLinkedBinaryTree.toInorderTraversalString();
    System.out.println(s);
}

查看输出：

g–>c–>h–>a–>i–>d–>r–>e–>b–>j–>f

确实图中的遍历顺序一致。

5 后序遍历 postorder traversal

5.1 后序遍历的介绍

规则是：若树为空，则空操作返回；否则，从根节点开始，先遍历根结点的左子树，然后是遍历右子树，最后遍历根结点；对于子树，同样，先遍历子树根节点的左子树，然后是遍历右子树，最后遍历子树根结点。采用了递归的思想。

后序遍历中，对节点的遍历工作，是在对该节点的儿子节点的遍历之后进行遍历的。这也就是“后序”的得来。

对图中的树采用后序遍历，从r根节点开始，顺序如下：

在这里插入图片描述

5.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
33
34
35
36
37
38
39
40
41
42
java复制代码/**
 * 后序遍历,提供给外部使用的api
 *
 * @return 遍历的数据
 */
public String toPostorderTraversalString() {
    //如果是空树,直接返回空
    if (isEmpty()) {
        return null;
    }
    //从根节点开始递归
    postorderTraversal(root);

    //获取遍历结果
    String s1 = threadLocal.get().toString();
    threadLocal.remove();
    return s1.substring(0, s1.length() - 3);
}

/**
 * 后序遍历 内部使用的递归遍历方法
 *
 * @param root 节点,从根节点开始
 */
private void postorderTraversal(BinaryTreeNode<E> root) {

    BinaryTreeNode<E> left = getLeft(root);
    if (left != null) {
        //如果左子节点不为null,则继续递归遍历该左子节点
        postorderTraversal(left);
    }

    //获取节点的右子节点
    BinaryTreeNode<E> right = getRight(root);
    if (right != null) {
        //如果右子节点不为null,则继续递归遍历该右子节点
        postorderTraversal(right);
    }

    //添加数据节点
    threadLocal.get().append(root).append("-->");
}

5.2.1 测试

1
2
3
4
5
6
7
8
java复制代码/**
 * 后序遍历
 */
@Test
public void postorderTraversal() {
    String s = integerLinkedBinaryTree.toPostorderTraversalString();
    System.out.println(s);
}

查看输出：

g–>h–>c–>i–>d–>a–>e–>j–>f–>b–>r

确实图中的遍历顺序一致。

6 层序遍历 level traversal

6.1 层序遍历的介绍

规则是：若树为空，则空操作返回；否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
层序遍历中，对节点的遍历工作，上层节点的遍历先于下层节点的遍历。这也就是“层序”的得来。

对图中的树采用层序遍历，从r根节点开始，顺序如下：

在这里插入图片描述

6.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
33
34
35
36
37
38
39
40
41
42
java复制代码/**
 * 层序遍历,提供给外部使用的api
 *
 * @return 遍历的数据
 */
public String toLevelTraversalString() {

    //如果是空树,直接返回空
    if (isEmpty()) {
        return null;
    }
    //从根节点开始遍历,借用队列
    levelTraversal(root);

    //获取遍历结果
    String s1 = threadLocal.get().toString();
    threadLocal.remove();
    return s1.substring(0, s1.length() - 3);
}

/**
 * 层序遍历 内部使用的借用了队列
 *
 * @param root 节点,从根节点开始
 */
private void levelTraversal(BinaryTreeNode<E> root) {
    Queue<BinaryTreeNode<E>> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        BinaryTreeNode<E> nowNode = q.poll();
        //添加数据节点
        threadLocal.get().append(nowNode.data).append("-->");
        if (nowNode.left != null) {
            //如果左子节点不为null,则将子节点加入队列
            q.add(nowNode.left);
        }
        if (nowNode.right != null) {
            //如果右子节点不为null,则将子节点加入队列
            q.add(nowNode.right);
        }
    }
}

6.2.1 测试

1
2
3
4
5
6
7
8
java复制代码/**
 * 层序遍历
 */
@Test
public void levelTraversal() {
    String s = integerLinkedBinaryTree.toLevelTraversalString();
    System.out.println(s);
}

查看输出：

r–>a–>b–>c–>d–>e–>f–>g–>h–>i–>j

确实图中的遍历顺序一致。

7 遍历结果推导

题目：已知一棵二叉树的前序遍历序列为r–>a–>c–>h–>d–>i–>b–>e–>j–>k–>f，中序遍历序列为c–>h–>a–>d–>i–>r–>e–>k–>j–>b–>f，请问这棵二叉树的后序遍历结果是多少？

这样的题目常出现在面试中，这个原理其实并不是很复杂，并且有一定的规律性。下面一起来推导。

7.1 寻找根节点

找到前序遍历的第1个字符：r，可知r是根节点；

再找到中序遍历中的根节点r的位置，r的左边c–>h–>a–>d–>i，这就是最大的左子树Ⅰ，e–>k–>j–>b–>f就是最大的右子树Ⅱ。

7.2 推导左子树

找到前序遍历的第2个字符：a，然后在中序遍历的子树Ⅰ中也能找到节点a，可知a是r根节点的左子节点，也是左子树Ⅰ的根节点，；那么可以推导出来，左子树Ⅰ还具有左子树Ⅲ：c–>h和右子树Ⅳ：d–>i

找到前序遍历的第3、4个字符：c–>h，可知，c作为子树Ⅰ的左子结点，对比中顺序遍历顺序c–>h，可知h是c节点的右子结点；

找到前序遍历的第5、6个字符：d–>i，可知，d作为子树Ⅰ的右子结点，对比中顺序遍历顺序d–>i，可知 i是d节点的右子节点；

到此可以推导出最大的左子树的数据结构如下：

在这里插入图片描述

下面推导右子树。

7.3 推导右子树

右子树Ⅱ的前序遍历节点就是排除左子树和根节点剩下的节点：b–>e–>j–>k–>f，中序遍历为e–>k–>j–>b–>f

前序遍历的第一个节点是b，可以b是右子树Ⅱ的根节点；

在中序遍历中b节点的左边是e–>k–>j，右边是f。可以f是节点b的右子结点，并且是叶子节点；这样还剩下最后的左子树Ⅴ；

左子树Ⅴ的前序遍历就是排除子树Ⅱ的根节点和子树Ⅱ的右子数节点，剩下：e–>j–>k，对应中序遍历为e–>k–>j。三个节点的前序排序和中序排序的结果一样，那么只有一种可能，那就是每个节点作为一层，并且最底层j是节点k的左子结点，中间层k是节点e右子节点，剩下的e节点，自然作为左子树Ⅴ的左子节点。

到此树结构推导完毕！树结构图如下：

在这里插入图片描述

有了树的结构，后序遍历的结果自然很明朗了：h–>c–>i–>d–>a–>k–>j–>e–>f–>b–>r。

7.4 快速推导

前序遍历序列为r–>a–>c–>h–>d–>i–>b–>e–>j–>k–>f，中序遍历序列为c–>h–>a–>d–>i–>r–> e–>k–>j–>b–>f。

后序排序的顺序为左子树、右子树、根节点。

r作为根节点，一定排在后序排序的最后一位。

最大的左子树Ⅰ中序排序为c–>h–>a–>d–>i，对应前序排序为a–>c–>h–>d–>i，根节点a。那么最大的右子树Ⅱ的其中序排序为e–>k–>j–>b–>f，前序排序为b–>e–>j–>k–>f，根节点b。

到此确定的顺序为： a–>b–>r。

下面看左子树Ⅰ，根节点为a，那么它的左右子节点别成子树Ⅲ、子树Ⅳ。

子树Ⅲ中序排序为c–>h，对应前序排序c–>h。到此可以确定的顺序为h–>c–>a–>b–>r。

子树四中序排序为d–>i，对应前序排序d–>i。到此可以确定的顺序为h–>c–>i–>d–>a–>b–>r。实际上到此已经把左子树进行了后序遍历。

下面看右子树Ⅱ，根节点为b，那么它的左右子节点别成子树Ⅴ、子树Ⅵ。

子树Ⅴ中序排序为e–>k–>j，对应前序排序e–>j–>k，根节点为e，由于中序排序和前序排序顺序一致，那么可以确定有三层，每层一个节点，第一层e、第二层k、第三层j。到此可以确定的顺序为h–>c–>i–>d–>a–>k–>j–>e–>b–>r。

剩下一个节点f，自然知道了位置唯一左子树节点和根节点之间，最终位置为：h–>c–>i–>d–>a–>k–>j–>e–>f–>b–>r。

完成推导。

7.5 补充

  1. 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
  2. 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
  3. 已知前序和后序遍历，是不能确定一棵二叉树的。

案例如下，前序序列是ABC，后序序列是CBA，可能的结果又如下几种：

在这里插入图片描述

8 总结

本文对于二叉树的遍历，介绍了4种，前三种实际上都依赖了方法的递归，其底层是依赖了JVM的栈结构的方法调用；第四种层序遍历，依赖了队列。 关于方法的递归调用和栈的关系，可以看这篇文章：Java中的栈数据结构详解以及实现和应用案例演示。

实际上，先序、中序、后序遍历又被称为深度优先遍历（DFS），其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次；层序遍历又被称为广度优先遍历（BFS），之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。

上面很多专业术语是如此的陌生，因为它属于图论算法中的一部分，实际上树（tree）就是一种特殊的没有闭环的图（map）。想要学好图吗？先跟我学好树吧！

如果有什么不懂或者需要交流，可以留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

学习笔记：

文档搜索

早期的全文检索会为整个文档集合建立一个很大的倒排索引并将其写入到磁盘。 一旦新的索引就绪，旧的就会被其替换，这样最近的变化便可以被检索到。

倒排索引被写入磁盘后是 不可改变 的:它永远不会修改。

不变性有重要的价值：

  • 不需要锁。如果你从来不更新索引，你就不需要担心多进程同时修改数据的问题。
  • 一旦索引被读入内核的文件系统缓存，便会留在哪里，由于其不变性。只要文件系统缓存中还有足够的空间，那么大部分读请求会直接请求内存，而不会命中磁盘。这提供了很大的性能提升。
  • 其它缓存(像filter缓存)，在索引的生命周期内始终有效。它们不需要在每次数据改变时被重建，因为数据不会变化。
  • 写入单个大的倒排索引允许数据被压缩，减少磁盘 I/O 和 需要被缓存到内存的索引的使用量。

当然，一个不变的索引也有不好的地方。主要事实是它是不可变的! 你不能修改它。如果你需要让一个新的文档 可被搜索，你需要重建整个索引。这要么对一个索引所能包含的数据量造成了很大的限制，要么对索引可被更新的频率造成了很大的限制。

动态更新索引

如何在保留不变性的前提下实现倒排索引的更新？

答案是: 用更多的索引。通过增加新的补充索引来反映新近的修改，而不是直接重写整个倒排索引。每一个倒排索引都会被轮流查询到，从最早的开始查询完后再对结果进行合并。

Elasticsearch 基于 Lucene, 这个java库引入了按段搜索的概念。 每一 段 本身都是一个倒排索引， 但索引在 Lucene 中除表示所有段的集合外， 还增加了提交点的概念 — 一个列出了所有已知段的文件

image.png

按段搜索会以如下流程执行：

  1. 新文档被收集到内存索引缓存

image.png

  1. 不时地, 缓存被提交
  • 一个新的段—​一个追加的倒排索引—​被写入磁盘。
  • 一个新的包含新段名字的 提交点 被写入磁盘
  • 磁盘进行 同步 — 所有在文件系统缓存中等待的写入都刷新到磁盘，以确保它们被写入物理文件
  1. 新的段被开启，让它包含的文档可见以被搜索
  2. 内存缓存被清空，等待接收新的文档

image.png
当一个查询被触发，所有已知的段按顺序被查询。词项统计会对所有段的结果进行聚合，以保证每个词和每个文档的关联都被准确计算。 这种方式可以用相对较低的成本将新文档添加到索引。

段是不可改变的，所以既不能从把文档从旧的段中移除，也不能修改旧的段来进行反映文档的更新。 取而代之的是，每个提交点会包含一个 .del 文件，文件中会列出这些被删除文档的段信息。

当一个文档被 “删除” 时，它实际上只是在 .del 文件中被 标记 删除。一个被标记删除的文档仍然可以被查询匹配到， 但它会在最终结果被返回前从结果集中移除。

文档更新也是类似的操作方式：当一个文档被更新时，旧版本文档被标记删除，文档的新版本被索引到一个新的段中。 可能两个版本的文档都会被一个查询匹配到，但被删除的那个旧版本文档在结果集返回前就已经被移除。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%