抽象数据结构

抽象数据结构（ADT）是一些操作的集合，集合了一些必要且重用性高的操作，这些操作在一个项目中只被编写一次。抽象数据结构只定义操作的存在，并不定义操作的实现

表

概念

表是一种基础的数据结构，是一系列逻辑上”顺序”的数据（顺序指具有连续的数值索引）。例如$A{0},A{1},A_{2}$就是一个表，数据具有连续索引1,2,3。此外，还有前驱元和后继元的概念：

  • 前驱元：某个元素之前的元素被称为该元素的前驱元（不定义第一个元素的前驱元）
  • 后继元：某个元素之后的元素被称为该元素的后继元（不定义最后一个元素的后继元）

表的实现方法

  • 数组实现：查找快，插入与删除慢，大小固定，内存中一般连续
  • 链表实现：查找较慢，插入与删除相对较快，大小可变，内存中一般不连续

表需要的方法

  • is_empty：判断是否为空表
  • is_last：判断是否为结尾
  • find：根据值获得在表中的节点（find_previous：获得前驱元）
  • visit：根据位置获得值（find）
  • delete：删除元素
  • insert：插入元素

实现

接口与结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//表中数据类型
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
}

方法的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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}
}

go笔记

  • go语言的面向对象使用struct实现，方法和属性分开定义
  • 方法的定义是func (a *b) name () [return_type] {}其中(a *b)表示该函数是哪个类型的方法，调用过程中，.运算符将运算符前的变量赋给a，类似于Python中的self和C++中的this指针
  • 接口与C++中接口类似，可用于实现多态，另外如果使用接口访问”对象”，可以保护对象的属性和未在接口中声明的方法，实现类似私有方法的功能