抽象数据结构与表抽象数据结构表

抽象数据结构

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

概念

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

  • 前驱元:某个元素之前的元素被称为该元素的前驱元(不定义第一个元素的前驱元)
  • 后继元:某个元素之后的元素被称为该元素的后继元(不定义最后一个元素的后继元)

表的实现方法

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

表需要的方法

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

实现

接口与结构体

//表中数据类型
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}
}

go笔记

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习与计算机视觉

算法-数字在排序数组中出现的次数

题目: 统计一个数字在排序数组中出现的次数,比如排序数组为{1,2,3,3,3,4,5},那么数字3出现的次数就是3。 解题思路: 1.首先,遍历数组肯...

2095
来自专栏用户3030674的专栏

java集合框架(hashSet自定义元素是否相同,重写hashCode和equals方法)

/*HashSet 基本操作 * --set:元素是无序的,存入和取出顺序不一致,元素不可以重复 * (通过哈希值来判断是否是同一个对象) * ---...

1482
来自专栏JavaNew

Java集合类:AbstractCollection源码解析

1113
来自专栏python3

python 数据类型

3.23和52.3E-4是浮点数的例子。E标记表示10的幂。在这里,52.3E-4表示52.3 * 10-4。

1482
来自专栏编程

Python基础1

数据类型 Python3中有6钟标准的数据类型:Number(数字)、String(字符 串)、List(列表)、Tuple(元组)、Sets(集合)、Dict...

22110
来自专栏用户3030674的专栏

java集合的操作(set,Iterator)

Iterator、Collection、Set和HashSet关系  Iterator<——Collection<——Set<——HashSet  Iterat...

2413
来自专栏闻道于事

Java之集合初探(一)

一、集合概述、区别 集合是一种容器,数组也是一种容器 在Java编程中,装各种各样的对象(引用类型)的叫做容器。 为什么出现集合类? 面向对象语言对事物的体现都...

2527
来自专栏陈树义

Java集合总结系列2:Collection接口

Collection 接口是 Java 集合类的一个根接口,Java 在 Collection 接口中定义了许多通用的数据操作类方法以及判断类方法。 通过查看 ...

2746
来自专栏Ryan Miao

java中List对象列表去重或取出以及排序

面试碰到几次list的去重和排序。下面介绍一种做法: 1. list去重 1.1 实体类Student List<Student>容量10k以上,要求去重复。这...

7129
来自专栏java一日一条

Java面试题:如何对HashMap按键值排序

Java中HashMap是一种用于存储“键”和“值”信息对的数据结构。不同于Array、ArrayList和LinkedLists,它不会维持插入元素的顺序。

752

扫码关注云+社区

领取腾讯云代金券