GO语言圣经习题：5.2 函数递归

GO语言圣经：函数递归 习题解析

《GO语言圣经》：https://books.studygolang.com/gopl-zh/ch5/ch5-02.html

第五章函数.递归习题与解析

练习 5.1： 修改findlinks代码中遍历n.FirstChild链表的部分，将循环调用visit，改成递归调用。

练习 5.2： 编写函数，记录在HTML树中出现的同名元素的次数。

练习 5.3： 编写函数输出所有text结点的内容。注意不要访问

练习 5.4： 扩展visit函数，使其能够处理其他类型的结点，如images、scripts和style sheets。

递归这一小节需要我们利用html包中的数据结构解析网页标签，在过程中练习递归。书中使用了第一章中fetch函数获取http中的内容，运行时通过管道将所得结果传给本节例子。

$ go build gopl.io/ch5/findlinks1
$ ./fetch https://golang.org | ./findlinks1

我为了不那么麻烦，两个代码综合一下写到一个文件里，可以直接运行。

package main

import (
	"bytes"
	"fmt"
	"golang.org/x/net/html"
	"io/ioutil"
	"net/http"
	"os"
)

func main() {
	url := "http://goland.org" //解析的url
	fmt.Println(url)
	doc, err := html.Parse(bytes.NewReader(fetch(url)))//fetch返回字节类型，使用字节转流，被Parse读取
	if err != nil {
		fmt.Fprintf(os.Stderr, "err: %v\n", err)
		os.Exit(1)
	}
	for _, link := range visit(nil, doc) {
		fmt.Println(link)
	}
	outline(nil, doc)
	fmt.Println("接下来是统计各个标签的数量")
	var m = make(map[string]int)
	m = countH(make(map[string]int), doc)
	for k, v := range m {
		fmt.Printf("%s  ==> %d\n", k, v)
	}
	outText(doc)
}

//访问url
func fetch(url string) []byte {
	resp, err := http.Get(url)
	if err != nil {
		fmt.Fprintf(os.Stderr, "fetch: %v\n", err)
		os.Exit(1)
	}
	b, err := ioutil.ReadAll(resp.Body)
	resp.Body.Close()
	if err != nil {
		fmt.Fprintf(os.Stderr, "fetch: reading %s: %v\n", url, err)
		os.Exit(1)
	}
	//fmt.Printf("%s", b)
	return b
}

//遍历节点树
func visit(links []string, n *html.Node) []string { 
	if n.Type == html.ElementNode && n.Data == "a" { //如果还想处理别的标签，那么就在这里控制，不止是a标签
		for _, a := range n.Attr {
			if a.Key == "href" {
				links = append(links, a.Val) 
				//fmt.Println("+______+")
			}
		}
	}
	//使用递归代替循环，猜测树的结构就是firstchild代表着第标签中的子标签，NextSibing代表的是下一个同一级别的标签
	if n.FirstChild != nil {
		links = visit(links, n.FirstChild) //如果存在子标签结点，就针对子标签结点访问
	}
	//注意这里不是if else的关系，因为两个之间没有存在逻辑关系，不会相互影响，所以不用相互判断
	if n.NextSibling != nil {
		links = visit(links, n.NextSibling) //如果存在下一个标签，就针对下一个标签访问
	}
	return links
}

/* 出现的标签栈 */
func outline(stack []string, n *html.Node) {
	if n.Type == html.ElementNode {
		stack = append(stack, n.Data) // 入栈
		fmt.Println(stack)
	}
	for c := n.FirstChild; c != nil; c = c.NextSibling {
		outline(stack, c) //仍然利用了递归
	}
}
//标签出现的次数
func countH(m map[string]int, n *html.Node) map[string]int {
	if n.Type == html.ElementNode {
		m[n.Data]++
		//fmt.Println(m)
	}
	for c := n.FirstChild; c != nil; c = c.NextSibling {
		m = countH(m, c)
	}
	return m
}
//输出text结点
func outText(n *html.Node) {
	if n.Type == html.TextNode {
		fmt.Println(n.Data)
	}
	if c := n.FirstChild; c != nil && c.Data != "style" && c.Data != "script" {
		outText(c)
	}
	if c := n.NextSibling; c != nil && c.Data != "style" && c.Data != "script" {
		outText(c)
	}
}

练习 5.1： 修改findlinks代码中遍历n.FirstChild链表的部分，将循环调用visit，改成递归调用。

	/* for c := n.FirstChild; c != nil; c = c.NextSibling { //这部分循环可以改为递归
		links = visit(links, c) 
	} */
	if n.FirstChild != nil {
		links = visit(links, n.FirstChild) //如果存在子标签结点，就针对子标签结点访问
	}
	if n.NextSibling != nil {
		links = visit(links, n.NextSibling) 
	}

这里需要明白结点的结构，firstchild是子标签的地址，nextsiling是下一个同级标签。所以将循环转化为递归的时候，进行两次if判断——注意，这里不是else if，两者在逻辑上没有因果关系，没有子标签不一定没有下一标签。我做的时候加上了else出了很大问题。这里明白结点的结构即可完成。

练习 5.2： 编写函数，记录在HTML树中出现的同名元素的次数。

//标签出现的次数
func countH(m map[string]int, n *html.Node) map[string]int {
	if n.Type == html.ElementNode {
		m[n.Data]++
		//fmt.Println(m)
	}
	for c := n.FirstChild; c != nil; c = c.NextSibling {
		m = countH(m, c)
	}
	return m
}

这里我使用map计算出现的次数。思路都差不多。不过注意的是初始化问题，map使用前是需要显式初始化的，不然会报错。

	var m = make(map[string]int)
	m = countH(make(map[string]int), doc)
	//m = countH(make(nil, doc) //error

练习 5.3： 编写函数输出所有text结点的内容。

//输出text结点
func outText(n *html.Node) {
	if n.Type == html.TextNode {
		fmt.Println(n.Data)
	}
	if c := n.FirstChild; c != nil && c.Data != "style" && c.Data != "script" {
		outText(c)
	}
	if c := n.NextSibling; c != nil && c.Data != "style" && c.Data != "script" {
		outText(c)
	}
}

这个问题我一开始不明白text指的是什么，以为是html标签中的属性，如input标签中的text。后面看了html中结点的结构，发现应该是textNode类型的结点，只需要修改一下判断的条件。

练习 5.4： 扩展visit函数，使其能够处理其他类型的结点，如images、scripts和style sheets。

if n.Type == html.ElementNode && n.Data == "a" { //如果还想这个可以处理别的标签，那么就在这里控制，不止是a标签

这个问题只需要增加条件判断就可以。

最后附上html包的结构：

package html

type Node struct {
    Type                    NodeType
    Data                    string
    Attr                    []Attribute
    FirstChild, NextSibling *Node
}

type NodeType int32

const (
    ErrorNode NodeType = iota
    TextNode
    DocumentNode
    ElementNode
    CommentNode
    DoctypeNode
)

type Attribute struct {
    Key, Val string
}

func Parse(r io.Reader) (*Node, error)

《GO语言圣经》：
https://books.studygolang.com/gopl-zh/ch5/ch5-02.html