抽象数据结构(ADT)是一些操作的集合,集合了一些必要且重用性高的操作,这些操作在一个项目中只被编写一次。抽象数据结构只定义操作的存在,并不定义操作的实现
表是一种基础的数据结构,是一系列逻辑上"顺序"的数据(顺序指具有连续的数值索引)。例如$A_{0},A_{1},A_{2}$就是一个表,数据具有连续索引1,2,3。此外,还有前驱元和后继元的概念:
//表中数据类型
type table_data struct {
data int
}
//链表节点类型
type table_node struct {
data table_data
next *table_node
}
//方法接口
type table_adt interface {
is_empty() bool
is_last(node table_node) bool
size() int
find(data table_data) *table_node
find_previous(data table_data) *table_node
find_last() *table_node
visit(num int) *table_node
delete(data table_data)
insert(data table_data, previous *table_node)
append(data table_data)
}
//链表结构体
type link_table struct {
head table_node
length int
}
func (table *link_table) is_empty() bool {
return table.head.next == nil
}
func (table *link_table) is_last(node table_node) bool {
return node.next == nil
}
func (table *link_table) find(data table_data) *table_node {
node := table.head.next
for (node != nil) && (node.data != data) {
// fmt.Println(node.data, data, (node.data != data))
node = node.next
}
return node
}
func (table *link_table) find_previous(data table_data) *table_node {
node := &table.head
for (node.next.data != data) && (node.next != nil) {
node = node.next
}
return node
}
func (table *link_table) find_last() *table_node {
node := &table.head
for node.next != nil {
node = node.next
}
return node
}
func (table *link_table) visit(num int) *table_node {
node := table.head.next
for i := 0; i < num; i++ {
node = node.next
}
return node
}
func (table *link_table) delete(data table_data) {
previous := table.find_previous(data)
if previous != nil {
previous.next = previous.next.next
previous.next.next = nil
}
table.length -= 1
}
func (table *link_table) insert(data table_data, previous *table_node) {
node := &table_node{data, previous.next}
previous.next = node
table.length += 1
}
func (table *link_table) append(data table_data) {
last := table.find_last()
table.insert(data, last)
}
func (table *link_table) size() int {
return table.length
}
//构造函数
func new_link_table() *link_table {
head := table_node{table_data{}, nil}
return &link_table{head, 0}
}
func (a *b) name () [return_type] {}
其中(a *b)
表示该函数是哪个类型的方法,调用过程中,.
运算符将运算符前的变量赋给a,类似于Python中的self
和C++中的this
指针