表的应用——排序与描述多项式排序多项式ADTGO语言笔记
表的应用——排序与描述多项式排序多项式ADTGO语言笔记
月见樽
发布于 2018-04-27 14:11:12
发布于 2018-04-27 14:11:12
文章被收录于专栏：文武兼修ing——机器学习与IC设计
排序
朴素排序
在链表建立的过程中可以直接完成排序功能，即建立一个新链表并将源数据一个一个存进新链表中，每个元素存储的位置在小于这个元素的节点和大于这个元素的节点之间
排序部分
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++
}判断要插入的值是否刚比下一个值小，若小则插入这一个节点与下一个节点之间。若无比要插入值大的节点则将待插入值插入链表的最后
遍历部分
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
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()
初始化桶函数
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的桶数组
获得基数函数
func get_num(num int, data int) int {
return int(float64(data)/math.Pow(10, float64(num))) % 10
}获取传入参数data的第num（从0开始计数）位数
入桶函数
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
}按顺序将切片带入的数据根据获得的基数送入对应的桶中
出桶函数
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开始依次将桶中的数据取出放入一个切片中
一次桶排序函数
func card_sort_step(bucket [10]*card_sort, num int) [10]*card_sort {
data := out_bucket(bucket)
return in_bucket(data, num)
}先出桶，后按给定的位数num入桶
桶排序函数
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
使用表的方式可以描数单元的多项式（如果使用链表，则数据部分就是{系数，幂次数}）
多项式链表结构体
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
}多项式插入方法
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循环结束后，结果可能有两种：
- 待插入值等于现节点，直接合并
- 待插入值不等于现节点，插入新节点
结果显示方法
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
}遍历多项式，打印系数与幂次
多项式相加
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
}
}将一个多项式的全部取出并插入另一个多项式即完成多项式相加
多项式相乘
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名相同，调用时路径写到文件夹即可。另外包中的需要在包外被调用的函数/变量/常量/结构体等首字母要大写
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017.11.22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
