抽象數(shù)據(jù)結(jié)構(gòu)

抽象數(shù)據(jù)結(jié)構(gòu)（ADT）是一些操作的集合，集合了一些必要且重用性高的操作，這些操作在一個項目中只被編寫一次。抽象數(shù)據(jù)結(jié)構(gòu)只定義操作的存在，并不定義操作的實現(xiàn)

表

概念

表是一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，是一系列邏輯上"順序"的數(shù)據(jù)（順序指具有連續(xù)的數(shù)值索引）。例如$A_{0},A_{1},A_{2}$就是一個表，數(shù)據(jù)具有連續(xù)索引1,2,3。此外，還有前驅(qū)元和后繼元的概念：

• 前驅(qū)元：某個元素之前的元素被稱為該元素的前驅(qū)元（不定義第一個元素的前驅(qū)元）
• 后繼元：某個元素之后的元素被稱為該元素的后繼元（不定義最后一個元素的后繼元）

表的實現(xiàn)方法

• 數(shù)組實現(xiàn)：查找快，插入與刪除慢，大小固定，內(nèi)存中一般連續(xù)
• 鏈表實現(xiàn)：查找較慢，插入與刪除相對較快，大小可變，內(nèi)存中一般不連續(xù)

表需要的方法

• is_empty：判斷是否為空表
• is_last：判斷是否為結(jié)尾
• find：根據(jù)值獲得在表中的節(jié)點（find_previous：獲得前驅(qū)元）
• visit：根據(jù)位置獲得值（find）
• delete：刪除元素
• insert：插入元素

實現(xiàn)

接口與結(jié)構(gòu)體

//表中數(shù)據(jù)類型
type table_data struct {
    data int
}

//鏈表節(jié)點類型
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)
}

//鏈表結(jié)構(gòu)體
type link_table struct {
    head   table_node
    length int
}

復(fù)制

方法的實現(xiàn)

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
}

//構(gòu)造函數(shù)
func new_link_table() *link_table {
    head := table_node{table_data{}, nil}
    return &link_table{head, 0}
}

復(fù)制

go筆記

• go語言的面向?qū)ο笫褂胹truct實現(xiàn)，方法和屬性分開定義
• 方法的定義是func (a *b) name () [return_type] {}其中(a *b)表示該函數(shù)是哪個類型的方法，調(diào)用過程中，.運算符將運算符前的變量賦給a，類似于Python中的self和C++中的this指針
• 接口與C++中接口類似，可用于實現(xiàn)多態(tài)，另外如果使用接口訪問"對象"，可以保護對象的屬性和未在接口中聲明的方法，實現(xiàn)類似私有方法的功能