表的应用——排序与描述多项式排序多项式ADTGO语言笔记

排序

朴素排序

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

排序部分

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名相同,调用时路径写到文件夹即可。另外包中的需要在包外被调用的函数/变量/常量/结构体等首字母要大写

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C++

python笔记:#005#算数运算符

1632
来自专栏我和PYTHON有个约会

32.企业级开发进阶4:正则表达式

本节内容,要讲解的和我们的信息检索有关系,这一方面也是Python在目前非常流行的一个应用方向:爬虫。

1031
来自专栏Android干货园

Kotlin中级(8)- - - Kotlin类之接口、枚举.md

772
来自专栏Script Boy (CN-SIMO)

Qt Quick编程(1)——QML的核心部分ECMAScript

说道QML,不得不先说一下ECMAScript: ECMAScript语言的标准是由Netscape、Sun、微软、Borland等公司基于JavaScript...

4660
来自专栏Golang语言社区

谈谈Go语言的反射三定律

简介 Reflection(反射)在计算机中表示 程序能够检查自身结构的能力,尤其是类型。它是元编程的一种形式,也是最容易让人迷惑的一部分。 虽然Go语言没...

48911
来自专栏转载gongluck的CSDN博客

python笔记:#005#算数运算符

算数运算符 计算机,顾名思义就是负责进行 数学计算 并且 存储计算结果 的电子设备 目标 算术运算符的基本使用 01. 算数运算符 算数运算符是 运算符的一种 ...

3877
来自专栏软件开发

C语言 第五章 循环结构

一、for 请在屏幕上输出1000个*号 printf("*************************...."); #include "stdio.h"...

2155
来自专栏Micro_awake web

JavaScript实现八大内部排序算法

? 注:基数排序中:r是关键字的基数,d是长度,n是关键字的个数 1.插入排序 基本思想:在序号i之前的元素(0到i-1)已经排好序,本趟需要找到i对应的元素...

2479
来自专栏编程

Python变量与数据类型

1 Python中数据类型 1、整数 Python可以处理任意大小的整数,当然包括负整数,在Python程序中,整数的表示方法和数学上的写法一模一样,例如:,,...

2926
来自专栏诸葛青云的专栏

python入门:进来吧,给自己10分钟,这篇文章带你直接学会python

假设你希望学习Python这门语言,却苦于找不到一个简短而全面的入门教程。那么本教程将花费十分钟的时间带你走入Python的大门。本文的内容介于教程(Totur...

430

扫码关注云+社区

领取腾讯云代金券