ch5/ch5-06 #145

2022-12-08T14:39:05Z

giscus[bot]
bot Dec 8, 2022

ch5/ch5-06

中文版

https://golang-china.github.io/gopl-zh/ch5/ch5-06.html

dugulingping · 2022-12-08T14:39:07Z

dugulingping
Dec 8, 2022 — with giscus

练习5.10 - 注释由ChatGPT生成

func topoSort(m map[string][]string) []string {
	// order 存储了项目的拓扑排序顺序。
	var order []string
	// seen 记录了已访问过的项目。
	seen := make(map[string]bool)
	// visitAll 函数递归访问 items 切片中的每个项目，并将它们按照正确的拓扑顺序添加到 order 切片中。
	var visitAll func(items []string)
	visitAll = func(items []string) {
		for _, item := range items {
			// 如果当前项目还没有被访问过，则递归调用 visitAll 函数，并将当前项目加入到 order 切片中。
			if !seen[item] {
				seen[item] = true
				visitAll(m[item])
				order = append(order, item)
			}
		}
	}
	// keys 存储了 m 中所有键的切片。
	var keys []string
	// 遍历 m 中的每个键，并将它们存储到 keys 切片中。
	for key := range m {
		keys = append(keys, key)
	}
	// 调用 visitAll 函数，并传入 keys 切片，从而从依赖图中的“叶子”节点（即没有依赖的项目）开始，
	// 逐步往上遍历依赖关系，并将项目添加到 order 切片中。
	visitAll(keys)
	// 返回 order 切片，表示拓扑排序后项目的顺序。
	return order
}

func main() {
	// 调用 topoSort 函数，并将返回值存储到 courses 切片中。
	courses := topoSort(prereqs)
	// 遍历 courses 切片中的每个项目，并以“索引：项目”的格式将它们输出到屏幕上。
	// 这么做的目的是使map的输出是有序的
	for i := 0; i < len(courses); i++ {
		fmt.Printf("%d:\t%s\n", i+1, courses[i])
	}
}

1 reply

Apahno Oct 29, 2024 — with giscus

写了个寂寞，题目要求对于keys ，用 map类型代替切片

dugulingping · 2022-12-08T14:45:33Z

dugulingping
Dec 8, 2022 — with giscus

练习5.11

// prereqs记录了每个课程的前置课程
var prereqs = map[string][]string{
	"algorithms":     {"data structures"},
	// ---环---
	"linear algebra": {"calculus"},
	"calculus":       {"linear algebra"},
	// ---环---
	"compilers": {
		"data structures",
		"formal languages",
		"computer organization",
	},
	"data structures":       {"discrete math"},
	"databases":             {"data structures"},
	"discrete math":         {"intro to programming"},
	"formal languages":      {"discrete math"},
	"networks":              {"operating systems"},
	"operating systems":     {"data structures", "computer organization"},
	"programming languages": {"data structures", "computer organization"},
}

// hasCycle 检查图中是否存在环
func hasCycle(m map[string][]string) bool {
	// visited 记录已经访问过的节点
	visited := make(map[string]bool)
	// dfs 函数用来进行深度优先搜索
	var dfs func(string, map[string]bool) bool
	dfs = func(item string, path map[string]bool) bool {
		// 如果当前节点已经被访问过，则返回 false
		if visited[item] {
			return false
		}
		// 将当前节点标记为已访问，并加入访问路径
		visited[item] = true
		path[item] = true
		// 遍历当前节点的所有相邻节点
		for _, next := range m[item] {

			// 如果相邻节点已经在访问路径上，说明存在环，返回 true
			if path[next] || dfs(next, path) {
				return true
			}
		}
		// 将当前节点从访问路径中移除，并返回 false
		delete(path, item)
		return false
	}
	// 遍历 map 中的每个节点，并调用 dfs 函数检查是否存在环
	for k := range m {
		path := make(map[string]bool)
		if dfs(k, path) {
			return true
		}
	}
	// 如果所有节点都检查完，则说明图中不存在环，返回 false
	return false
}
func main() {
	// 有环则输出true
	fmt.Println(hasCycle(prereqs))
}

0 replies

dugulingping · 2022-12-08T14:58:05Z

dugulingping
Dec 8, 2022 — with giscus

练习5.12

文件Practice5.12.go

package main

import (
	"Study/src/study/day7Function/HtmlTools"
	"fmt"
	"golang.org/x/net/html"
)

// forEachNode 针对每个结点x，都会调用pre(x)和post(x)。
// pre和post都是可选的。
// 遍历孩子结点之前，pre被调用
// 遍历孩子结点之后，post被调用
func forEachNode(n *html.Node, pre, post func(n *html.Node)) {
	if pre != nil {
		pre(n)
	}
	for c := n.FirstChild; c != nil; c = c.NextSibling {
		forEachNode(c, pre, post)
	}
	if post != nil {
		post(n)
	}
}

func main() {
	var depth int
	var startElement func (n *html.Node) = func (n *html.Node) {
		if n.Type == html.ElementNode {
			fmt.Printf("%*s<%s>\n", depth*2, "", n.Data)
			depth++
		}
	}
	endElement := func (n *html.Node) {
		if n.Type == html.ElementNode {
			depth--
			fmt.Printf("%*s</%s>\n", depth*2, "", n.Data)
		}
	}
	forEachNode(HtmlTools.GetHtml(), startElement, endElement)
}

文件 /HtmlTools/Tools.go

package HtmlTools

import (
	"fmt"
	"golang.org/x/net/html"
	"log"
	"net/http"
)

func GetHtml() *html.Node {
	resp, err := http.Get("https://golang-china.github.io/gopl-zh/ch5/ch5-02.html")
	if err != nil {
		log.Fatal(err)
	}
	if resp.StatusCode != http.StatusOK {
		err := resp.Body.Close()
		if err != nil {
			log.Fatal(err)
			return nil
		}
	}
	doc, err := html.Parse(resp.Body)
	if err != nil {
		log.Fatal(err)
		return nil
	}
	return doc

}

1 reply

zhangbest5 Jan 12, 2023 — with giscus

好家伙，我的顺序就不一样。。。
1: discrete math
2: data structures
3: algorithms
4: linear algebra
5: calculus
6: formal languages
7: computer organization
8: compilers
9: databases
10: intro to programming
11: discrete
12: operating systems
13: networks
14: programming languages

dugulingping · 2022-12-08T17:17:46Z

dugulingping
Dec 8, 2022 — with giscus

练习5.13

文件 Practice5.13.go

package main

import (
	"Study/src/study/day7Function/HtmlTools"
	"bufio"
	"fmt"
	"golang.org/x/net/html"
	"log"
	"os"
	"path"
	"path/filepath"
	"runtime"
	"strings"
)

// BreadthFirst 队列中的每节点都调用f()。
// f()返回的所有节点都被添加到队列中。
// 对每个节点最多调用一次f()。
func BreadthFirst(f func(item string) []string, worklist []string) {
	// seen
	seen := make(map[string]bool)
	for len(worklist) > 0 {
		// 复制当前队列
		items := worklist
		// 清空队列
		worklist = nil
		// 遍历复制的当前队列
		for _, item := range items {
			// 判断seen, 防止重复添加到队列
			if !seen[item] {
				seen[item] = true
				// 添加到队列
				worklist = append(worklist, f(item)...)
			}
		}
	}
}

// ExtractRestructure 从HTML文档中提取链接，并将相对路径转换为绝对路径
//
//		URL			string,		要提取链接的HTML文档
//		isSave		bool,		是否保存提取到的链接对应的页面
//		saveOriginOnly bool,	是否只保存与当前页面域名相同的页面
//
//	 return		[]string, error,	提取到的链接列表和错误信息
func ExtractRestructure(URL string, isSave bool, saveOriginOnly bool) ([]string, error) {
	// 检查参数
	if URL == "" {
		URL = "https://go.dev/"
	}
	node, resp := HtmlTools.GetHtmlResponse(URL)
	originURL := resp.Request.URL.Host
	var links []string
	visitNode := func(n *html.Node) {
		if n.Type == html.ElementNode && n.Data == "a" {
			for _, a := range n.Attr {
				if a.Key != "href" {
					continue
				}
				// 将相对路径和url的内容组合在一起形成完整的绝对路径
				link, err := resp.Request.URL.Parse(a.Val)
				if err != nil {
					// 忽略掉报error的URL
					fmt.Println(err)
					continue
				}

				// 将link添加到切片
				links = append(links, link.String())
				// 判断是否只保存同一域名下的地址 
				if saveOriginOnly && (link.Host != originURL) {
					continue
				}
				// 保存页面
				if isSave && link.String() != "" {
					filePath := getCurrentAbPath() + "/www/urls.txt"
					file, err := os.OpenFile(filePath, os.O_WRONLY|os.O_CREATE|os.O_APPEND, 0666)
					if err != nil {
						fmt.Println("文件打开失败", err)
					}
					//及时关闭file句柄
					defer file.Close()
					//写入文件时，使用带缓存的 *Writer
					write := bufio.NewWriter(file)
					if _, err := write.WriteString(link.String() + "\r\n"); err != nil {
						panic(err)
					}
					// 将缓存写入文件
					if err := write.Flush(); err != nil {
						panic(err)
					}
				}
			}
		}
	}
	HtmlTools.ForEachNode(node, visitNode, nil)
	return links, nil
}

func main() {
	// crawl 此函数返回一个[]string, 内容为url
	crawl := func(url string) []string {
		fmt.Println("Crawl:", url)
		list, err := ExtractRestructure(url, true, true)
		if err != nil {
			log.Print(err)
		}
		return list
	}

	// Crawl the web breadth-first,
	// starting from the command-line arguments.
	BreadthFirst(crawl, []string{"https://go.dev/"})
}

// see https://zhuanlan.zhihu.com/p/363714760
// 最终方案-全兼容
func getCurrentAbPath() string {
	dir := getCurrentAbPathByExecutable()
	if strings.Contains(dir, getTmpDir()) {
		return getCurrentAbPathByCaller()
	}
	return dir
}

// 获取系统临时目录，兼容go run
func getTmpDir() string {
	dir := os.Getenv("TEMP")
	if dir == "" {
		dir = os.Getenv("TMP")
	}
	res, _ := filepath.EvalSymlinks(dir)
	return res
}

// 获取当前执行文件绝对路径
func getCurrentAbPathByExecutable() string {
	exePath, err := os.Executable()
	if err != nil {
		log.Fatal(err)
	}
	res, _ := filepath.EvalSymlinks(filepath.Dir(exePath))
	return res
}

// 获取当前执行文件绝对路径（go run）
func getCurrentAbPathByCaller() string {
	var abPath string
	_, filename, _, ok := runtime.Caller(0)
	if ok {
		abPath = path.Dir(filename)
	}
	return abPath
}

文件 /HtmlTools/Tools.go

package HtmlTools

import (
	"fmt"
	"golang.org/x/net/html"
	"log"
	"net/http"
)

func GetHtmlResponse(url string) (*html.Node, *http.Response) {
	// 检查参数
	if url == "" {
		url = "https://go.dev/"
	}
	resp, err := http.Get("https://go.dev/")
	if err != nil {
		log.Fatal(err)
	}
	if resp.StatusCode != http.StatusOK {
		err := resp.Body.Close()
		if err != nil {
			log.Fatal(err)
			return nil, nil
		}
	}
	doc, err := html.Parse(resp.Body)
	if err != nil {
		log.Fatal(err)
		return nil, nil
	}
	return doc, resp

}

// ForEachNode 深度遍历 n, pre和post分别表示压栈和出栈时执行的动作
//
//	n			*html.Node
//	pre			func(n *html.Node)
//	post		func(n *html.Node)
//
// 将 ForEachNode() 移动到单独的软件包，供以后方便调用
func ForEachNode(n *html.Node, pre, post func(n *html.Node)) {
	if n == nil {
		return
	}
	if pre != nil {
		pre(n)
	}
	//for c := n.FirstChild; c != nil; c = c.NextSibling {
	//	forEachNode(c, pre, post)
	//}
	ForEachNode(n.FirstChild, pre, post)
	ForEachNode(n.NextSibling, pre, post)
	if post != nil {
		post(n)
	}
}

0 replies

dugulingping · 2022-12-09T04:17:17Z

dugulingping
Dec 9, 2022 — with giscus

练习5.14

只做了有向图的BFS,树和无向图差不多,只要你能理解队列的思想,应该不难~~

func breadthFirstDigraph(m map[string][]string) []string {
	var worklist, res []string
	// 将第一层节点加入到队列
	for k, _ := range m {
		worklist = append(worklist, k)
	}
	// seen
	seen := make(map[string]bool)
	for len(worklist) > 0 {
		// 复制当前队列
		items := worklist
		// 清空队列
		worklist = nil
		// 遍历复制的当前队列
		for _, item := range items {
			// 判断seen, 防止重复添加到队列
			if !seen[item] {
				seen[item] = true
				// 添加到队列
				worklist = append(worklist, m[item]...)
				fmt.Println(item)
				res = append(res, item)
			}
		}
	}
	return res
}

0 replies

zhangbest5 · 2023-01-12T03:36:41Z

zhangbest5
Jan 12, 2023 — with giscus

好家伙，我的顺序就不一样。。。
1: discrete math
2: data structures
3: algorithms
4: linear algebra
5: calculus
6: formal languages
7: computer organization
8: compilers
9: databases
10: intro to programming
11: discrete
12: operating systems
13: networks
14: programming languages

0 replies

zhangbest5 · 2023-01-12T04:06:21Z

zhangbest5
Jan 12, 2023 — with giscus

dir := dir ，这里还是没有说明白，例子举得也不好，确实最后都是同一个值，但没理解了为啥

1 reply

haiki Oct 10, 2023 — with giscus

看文中描述，是因为函数值中引用了变量的地址，for 循环的变量dir只声明一次，for多少次地址都是当前地址，所有的函数值用的都是这个

houxianyu1997 · 2023-06-19T16:53:20Z

houxianyu1997
Jun 19, 2023 — with giscus

5.10 输入为Map类型

func topoSortMap(m map[string][]string) []string {
	var order []string
	seen := make(map[string]bool)
	var visitAll func(map[string][]string)
	visitAll = func(mp map[string][]string) { 
		mp1 := make(map[string][]string, len(m))
		for k, v := range mp {
			if !seen[k] {
				seen[k] = true
				for _, v1 := range v { // 遍历预修课程
					if !seen[v1] { // 判断预修课程是否被观测。由于图中某些节点存在多个边，因此，如果预修课程被提前观测，则不再观测该课程。
						value, ok := m[v1] // 判断预修课程是否存在学习序列
						if ok {
							mp1[v1] = value // 存在则继续观测
						} else {
							mp1[v1] = make([]string, 0) // 不存在则结束观测
						}
					}
				}
				visitAll(mp1)
				order = append(order, k)
			}
		}
	}
	visitAll(m)

	return order
}

0 replies

xq-120 · 2023-11-06T14:55:19Z

xq-120
Nov 6, 2023 — with giscus

练习5.10

func exerciseTopoSort(m map[string][]string) []string {
	seen := make(map[string]bool)
	var order []string
	var visitAll func(dict map[string][]string)
	visitAll = func(dict map[string][]string) {
		for k, v := range dict {
			if !seen[k] {
				seen[k] = true
				for _, item := range v {
					var mCourse = make(map[string][]string)
					course := m[item] 
					if course != nil {
						mCourse[item] = course
					} else {
						mCourse[item] = []string{}
					}
					visitAll(mCourse)
				}
				order = append(order, k)
			}
		}
	}
	visitAll(m)
	return order
}

输出结果：

1: intro to programming
2: discrete math
3: data structures
4: algorithms
5: formal languages
6: computer organization
7: operating systems
8: networks
9: programming languages
10: linear algebra
11: calculus
12: compilers
13: databases

0 replies

A-caibird · 2024-02-04T17:30:38Z

A-caibird
Feb 4, 2024 — with giscus

// squares返回一个匿名函数。
// 该匿名函数每次被调用时都会返回下一个数的平方。
func squares() func() int {
var x int
return func() int {
x++
return x * x
}
}
func main() {
f := squares()
fmt.Println(f()) // "1"
fmt.Println(f()) // "4"
fmt.Println(f()) // "9"
fmt.Println(f()) // "16"
}
这里写错了,这里返回的是一个函数啊,还没有调用她,()符号是函数调用

必须要
fmt.Println(f()())

1 reply

lllxh Feb 29, 2024 — with giscus

这里main中fmt.Println()内是否只需要一次调用，即fmt.Println(f())
main中squares()已返回了匿名函数给f，f()即是对匿名函数的调用

Fisher0825 · 2024-05-07T07:56:49Z

Fisher0825
May 7, 2024 — with giscus

5.6.1中，不知道是不是因为我是用最新版本的go解释器，我没有将循环体中的循环变量赋值给新的变量，直接用的循环体变量给到函数值中，所有的文件夹都被删除了。并没有出现只会删除最后一个文件夹的情况。

5 replies

haofeng98 May 12, 2024 — with giscus

func RangeNoNameFunc() {
	a := [3]int{1, 2, 3}
	var recs []func()
	for i, v := range a {
		a[i] = 0
		recs = append(recs, func() {
			fmt.Printf("i=%d, v=%d\n", i, v)
			a[i] = v
		})
	}

	// do something

	// 试图恢复原来的值
	for _, rec := range recs {
		rec()
	}
	// i = 2, v = 3
	// i = 2, v = 3
	// i = 2, v = 3

	fmt.Println(a) // 打印 [0 0 3]
}

Sauce-amide May 31, 2024 — with giscus

我打印出来还是
i=0, v=1
i=1, v=2
i=2, v=3
[1 2 3]
感觉并没有使用引用变量

Sauce-amide May 31, 2024 — with giscus

已经解决了，在目前最新的Go 1.22 中解决了这个问题 https://go.dev/ref/spec#For_clause。在 Go 1.22 中，循环变量的作用域规则发生了变化，每次迭代都会获得该变量的一个新实例。

Sauce-amide May 31, 2024 — with giscus

https://go.dev/ref/spec#For_clause

XiongGG1989 Jun 6, 2024 — with giscus

func num() {
	var funcs []func()
	for i := 0; i < 10; i++ {
		funcs = append(funcs, func() {
			fmt.Println(i)
		})
	}
	for _, f := range funcs {
		f()
	}
}

在 1.22 版本中，确实正确输出了 0到9

lwc18 · 2024-07-24T07:47:23Z

lwc18
Jul 24, 2024 — with giscus

出现环的充要条件是有课程在seem里面但不再order里面
所以在每一个item开始都检查这个item的前置课程中是否存在课程在seem里但不在order里
package main

import (
"fmt"
)

// prereqs记录了每个课程的前置课程
var prereqs = map[string][]string{
"algorithms": {"data structures"},
"calculus": {"linear algebra"},
"linear algebra": {"calculus"},
"compilers": {
"data structures",
"formal languages",
"computer organization",
},
"data structures": {"discrete math"},
"databases": {"data structures"},
"discrete math": {"intro to programming"},
"formal languages": {"discrete math"},
"networks": {"operating systems"},
"operating systems": {"data structures", "computer organization"},
"programming languages": {"data structures", "computer organization"},
}

func main() {
for i, course := range topoSort(prereqs) {
fmt.Printf("%d:\t%s\n", i+1, course)
}
}

func topoSort(m map[string][]string) []string {
var order []string
seen := make(map[string]bool)

var visitAll func(items []string)
visitAll = func(items []string) {
	for _, item := range items {
		if seen[item] {
			for _, x := range m[item] {  
				if !contains(order, x) { 
					fmt.Println("出现环")
				}
			}
		}
		if !seen[item] {
			seen[item] = true
			visitAll(m[item])
			order = append(order, item)
		}
	}
}

var keys []string
for key := range m {
	keys = append(keys, key)
}
visitAll(keys)
return order

}

func contains(slice []string, target string) bool { // 新增函数用于判断元素是否在切片中
for _, item := range slice {
if item == target {
return true
}
}
return false
}

0 replies

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ch5/ch5-06 #145

{{title}}

Replies: 12 comments 9 replies

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

Select a reply

ch5/ch5-06 #145

giscus[bot] bot Dec 8, 2022

ch5/ch5-06

Replies: 12 comments · 9 replies

dugulingping Dec 8, 2022 — with giscus

练习5.10 - 注释由ChatGPT生成

Apahno Oct 29, 2024 — with giscus

dugulingping Dec 8, 2022 — with giscus

练习5.11

dugulingping Dec 8, 2022 — with giscus

练习5.12

文件Practice5.12.go

文件 /HtmlTools/Tools.go

zhangbest5 Jan 12, 2023 — with giscus

dugulingping Dec 8, 2022 — with giscus

练习5.13

文件 Practice5.13.go

文件 /HtmlTools/Tools.go

dugulingping Dec 9, 2022 — with giscus

练习5.14

zhangbest5 Jan 12, 2023 — with giscus

zhangbest5 Jan 12, 2023 — with giscus

haiki Oct 10, 2023 — with giscus

houxianyu1997 Jun 19, 2023 — with giscus

5.10 输入为Map类型

xq-120 Nov 6, 2023 — with giscus

练习5.10

A-caibird Feb 4, 2024 — with giscus

lllxh Feb 29, 2024 — with giscus

Fisher0825 May 7, 2024 — with giscus

haofeng98 May 12, 2024 — with giscus

Sauce-amide May 31, 2024 — with giscus

Sauce-amide May 31, 2024 — with giscus

Sauce-amide May 31, 2024 — with giscus

XiongGG1989 Jun 6, 2024 — with giscus

lwc18 Jul 24, 2024 — with giscus

giscus[bot]
bot Dec 8, 2022

Replies: 12 comments 9 replies

dugulingping
Dec 8, 2022 — with giscus

dugulingping
Dec 8, 2022 — with giscus

dugulingping
Dec 8, 2022 — with giscus

dugulingping
Dec 8, 2022 — with giscus

dugulingping
Dec 9, 2022 — with giscus

zhangbest5
Jan 12, 2023 — with giscus

zhangbest5
Jan 12, 2023 — with giscus

houxianyu1997
Jun 19, 2023 — with giscus

xq-120
Nov 6, 2023 — with giscus

A-caibird
Feb 4, 2024 — with giscus

Fisher0825
May 7, 2024 — with giscus

lwc18
Jul 24, 2024 — with giscus