排序

朴素排序

在链表建立的过程中可以直接完成排序功能，即建立一个新链表并将源数据一个一个存进新链表中，每个元素存储的位置在小于这个元素的节点和大于这个元素的节点之间

排序部分

1
2
3
4
5
6
7
8
9
10
func (s *sort_table) append(data int) {
	node := s.head
	for (node.next != nil) && (node.next.data.data <= data) {
		node = node.next
	}
	new_data := table_data{data}
	new_node := &table_node{new_data, node.next}
	node.next = new_node
	s.length++
}

判断要插入的值是否刚比下一个值小，若小则插入这一个节点与下一个节点之间。若无比要插入值大的节点则将待插入值插入链表的最后

遍历部分

1
2
3
4
5
6
7
8
9
func (s *sort_table) return_result() []int {
	result := []int{}
	node := s.head.next
	for node != nil {
		result = append(result, node.data.data)
		node = node.next
	}
	return result
}

从头开始顺序遍历，直到所有值被取出

基数排序

这是一种类似于桶排序的排序方法，以基10排序为例，首先建立10个桶，分别是0~9，按十进制数的最低位送进对应的桶中，再按桶顺序取出，依次再按次低位送进桶中，重复到最高位，再依次取出则得到排序结果（顺序均是从0桶到9桶，同一个桶先进先出）

桶ADT

1
2
3
4
5
6
7
8
9
10
11
12
13
type card_sort struct {
	link_table
}

func (c *card_sort) pop() int {
	if c.head.next == nil {
		return -1
	} else {
		data := c.head.next.data.data
		c.head.next = c.head.next.next
		return data
	}
}

“继承”链表的方法，添加从头取出节点的方法pop()

初始化桶函数

1
2
3
4
5
6
7
8
func initial_bucket() [10]*card_sort {
	bucket := [10]*card_sort{}
	new_data := link_table{table_node{table_data{}, nil}, 0}
	for i := 0; i < len(bucket); i++ {
		bucket[i] = &card_sort{new_data}
	}
	return bucket
}

初始化一个尺寸为10的桶数组

获得基数函数

1
2
3
func get_num(num int, data int) int {
	return int(float64(data)/math.Pow(10, float64(num))) % 10
}

获取传入参数data的第num（从0开始计数）位数

入桶函数

1
2
3
4
5
6
7
func in_bucket(data []int, num int) [10]*card_sort {
	bucket := initial_bucket()
	for i := range data {
		bucket[get_num(num, data[i])].append(table_data{data[i]})
	}
	return bucket
}

按顺序将切片带入的数据根据获得的基数送入对应的桶中

出桶函数

1
2
3
4
5
6
7
8
9
10
11
12
13
func out_bucket(bucket [10]*card_sort) []int {
	temp := 0
	data := []int{}
	for i := range bucket {
		temp = bucket[i].pop()
		for temp != -1 {
			data = append(data, temp)
			temp = bucket[i].pop()
		}
	}
	// fmt.Println(data)
	return data
}

从桶0开始依次将桶中的数据取出放入一个切片中

一次桶排序函数

1
2
3
4
func card_sort_step(bucket [10]*card_sort, num int) [10]*card_sort {
	data := out_bucket(bucket)
	return in_bucket(data, num)
}

先出桶，后按给定的位数num入桶

桶排序函数

1
2
3
4
5
6
7
func card_sort_eval(data []int, num int) []int {
	bucket := in_bucket(data, 0)
	for i := 1; i < num; i++ {
		bucket = card_sort_step(bucket, i)
	}
	return out_bucket(bucket)
}

多项式ADT

使用表的方式可以描数单元的多项式（如果使用链表，则数据部分就是{系数，幂次数}）

多项式链表结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type Table_data struct {
	coefficient int
	index       int
}

type table_node struct {
	data Table_data
	next *table_node
}

type Mult struct {
	head   *table_node
	length int
}

多项式插入方法

1
2
3
4
5
6
7
8
9
10
11
12
13
func (s *Mult) Append(data Table_data) {
	node := s.head
	for (node.next != nil) && (node.next.data.index <= data.index) {
		node = node.next
	}
	if node.data.index == data.index {
		node.data.coefficient += data.coefficient
	} else {
		new_node := &table_node{data, node.next}
		node.next = new_node
		s.length++
	}
}

寻找到恰好大于待插入值的节点，for循环结束后，结果可能有两种：

  • 待插入值等于现节点，直接合并
  • 待插入值不等于现节点，插入新节点

结果显示方法

1
2
3
4
5
6
7
8
9
func (s *Mult) Return_result() []Table_data {
	result := []Table_data{}
	node := s.head.next
	for node != nil {
		result = append(result, node.data)
		node = node.next
	}
	return result
}

遍历多项式，打印系数与幂次

多项式相加

1
2
3
4
5
6
7
func (self *Mult) Add_(adder *Mult) {
	adder_node := adder.head.next
	for adder_node != nil {
		self.Append(adder_node.data)
		adder_node = adder_node.next
	}
}

将一个多项式的全部取出并插入另一个多项式即完成多项式相加

多项式相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func (self *Mult) Dot(mul *Mult) *Mult {
	mul_node, node := mul.head.next, self.head.next
	new_index, new_co := 0, 0
	new_table := New_mult()
	for node != nil {
		mul_node = mul.head.next
		for mul_node != nil {
			new_index = mul_node.data.index + node.data.index
			new_co = mul_node.data.coefficient * node.data.coefficient
			new_table.Append(Table_data{new_co, new_index})
			mul_node = mul_node.next
		}
		node = node.next
	}
	return new_table
}

将两个多项式的节点取出两两相乘（幂指数相加，系数相乘），将结果插入一个新多项式中完成多项式相加

GO语言笔记

同package多文件

当一个package由多个文件描述时，应当将所有文件放在同一目录下，运行时包括所有.go文件

自定义包

将包放在一个文件夹中，文件夹名与package名相同，调用时路径写到文件夹即可。另外包中的需要在包外被调用的函数/变量/常量/结构体等首字母要大写