排序
樸素排序
在鏈表建立的過程中可以直接完成排序功能幕袱，即建立一個新鏈表并將源數(shù)據(jù)一個一個存進新鏈表中趾徽，每個元素存儲的位置在小于這個元素的節(jié)點和大于這個元素的節(jié)點之間
排序部分
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++
}
判斷要插入的值是否剛比下一個值小敛摘，若小則插入這一個節(jié)點與下一個節(jié)點之間牢硅。若無比要插入值大的節(jié)點則將待插入值插入鏈表的最后
遍歷部分
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
}
從頭開始順序遍歷瓢宦，直到所有值被取出
基數(shù)排序
這是一種類似于桶排序的排序方法造烁，以基10排序為例明场，首先建立10個桶汽摹，分別是0~9，按十進制數(shù)的最低位送進對應(yīng)的桶中苦锨，再按桶順序取出逼泣，依次再按次低位送進桶中，重復(fù)到最高位舟舒，再依次取出則得到排序結(jié)果（順序均是從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
}
}
“繼承”鏈表的方法，添加從頭取出節(jié)點的方法pop()
初始化桶函數(shù)
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的桶數(shù)組
獲得基數(shù)函數(shù)
func get_num(num int, data int) int {
return int(float64(data)/math.Pow(10, float64(num))) % 10
}
獲取傳入?yún)?shù)data的第num（從0開始計數(shù)）位數(shù)
入桶函數(shù)
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
}
按順序將切片帶入的數(shù)據(jù)根據(jù)獲得的基數(shù)送入對應(yīng)的桶中
出桶函數(shù)
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開始依次將桶中的數(shù)據(jù)取出放入一個切片中
一次桶排序函數(shù)
func card_sort_step(bucket [10]*card_sort, num int) [10]*card_sort {
data := out_bucket(bucket)
return in_bucket(data, num)
}
先出桶秃励，后按給定的位數(shù)num入桶
桶排序函數(shù)
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
使用表的方式可以描數(shù)單元的多項式（如果使用鏈表氏仗，則數(shù)據(jù)部分就是{系數(shù)，冪次數(shù)}）
多項式鏈表結(jié)構(gòu)體
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++
}
}
尋找到恰好大于待插入值的節(jié)點夺鲜，for循環(huán)結(jié)束后皆尔，結(jié)果可能有兩種：
- 待插入值等于現(xiàn)節(jié)點，直接合并
- 待插入值不等于現(xiàn)節(jié)點币励，插入新節(jié)點
結(jié)果顯示方法
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
}
遍歷多項式慷蠕，打印系數(shù)與冪次
多項式相加
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
}
將兩個多項式的節(jié)點取出兩兩相乘（冪指數(shù)相加，系數(shù)相乘）食呻，將結(jié)果插入一個新多項式中完成多項式相加
GO語言筆記
同package多文件
當(dāng)一個package由多個文件描述時流炕，應(yīng)當(dāng)將所有文件放在同一目錄下，運行時包括所有.go文件
自定義包
將包放在一個文件夾中仅胞，文件夾名與package名相同每辟，調(diào)用時路徑寫到文件夾即可。另外包中的需要在包外被調(diào)用的函數(shù)/變量/常量/結(jié)構(gòu)體等首字母要大寫
