• 周四. 12月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

(一)用go实现单链表

admin

11月 28, 2021

本篇,我们用go简单的实现单链表这种数据结构。

1.节点定义

type Node struct{
    data int
    next *Node	
}

2.节点的添加

// 尾插法插入节点
func (p *Node) Append(data int) {
    for p.next != nil {
        p = p.next
    }
    var newNode *Node = new(Node)
    newNode.data = data
    p.next = newNode
    
    fmt.Printf("插入数据:%d
", data)
}

3.节点的删除

// 删除尾节点并返回其值
func (p *Node) Pop() (int, error) {
    if p.next == nil {
        return 0, errors.New("Error: pop from empty list!")
    }

    var tmp *Node
    for p.next != nil {
        tmp = p
        p = p.next
    }
    tmp.next = nil
    fmt.Printf("删除数据:%d
", p.data)
    return p.data, nil

}

4.节点的查询

// 查询第i个节点的值
func (p *Node) Find(i int) (int, error) {
    for p.next != nil && i > 0 {
        p = p.next
        i -= 1
    }
    if i > 0 {
        return 0, errors.New("Error: the node not exist!")
    }

    return p.data, nil
}

5.节点的修改

// 修改第i个节点的值
func (p *Node) Update(i, data int) (error) {
    for p.next != nil && i > 0 {
        p = p.next
        i -= 1
    }
    if i > 0 {
        return errors.New("Error: the node not exist!")
    }
    p.data = data
    return nil
}

6.节点的遍历

// 遍历输出
func (p *Node) Traverse() {
    fmt.Printf("遍历结果:")
    for p.next != nil {
        fmt.Printf("%d ", p.next.data)
        p = p.next
    }
    fmt.Printf("
")
}

7.测试代码

func main() {
    var head *Node
    head = new(Node)

    for a := 0; a < 10; a++ {
        head.Append(a)
    }
    head.Traverse()

    data, err := head.Pop()
    if err != nil {
        fmt.Println(err)
    }
    fmt.Printf("Pop返回数据:%d
", data)
    head.Traverse()

    data, err = head.Find(3)
    if err != nil {
        fmt.Println(err)
    }
    fmt.Printf("查询的数据为:%d
", data)

    err = head.Update(2, 20)
    if err != nil {
        fmt.Println(err)
    }
    head.Traverse()

}

// 测试结果
插入数据:0
插入数据:1
插入数据:2
插入数据:3
插入数据:4
插入数据:5
插入数据:6
插入数据:7
插入数据:8
插入数据:9
遍历结果:0 1 2 3 4 5 6 7 8 9
删除数据:9
Pop返回数据:9
遍历结果:0 1 2 3 4 5 6 7 8
查询的数据为:2
遍历结果:0 20 2 3 4 5 6 7 8

8.完整代码

package main

import (
    "fmt"
    "errors"
)

type Node struct{
    data int
    next *Node	
}

// 遍历输出
func (p *Node) Traverse() {
    fmt.Printf("遍历结果:")
    for p.next != nil {
        fmt.Printf("%d ", p.next.data)
        p = p.next
    }
    fmt.Printf("
")
}

// 尾插法插入节点
func (p *Node) Append(data int) {
    for p.next != nil {
        p = p.next
    }
    var newNode *Node = new(Node)
    newNode.data = data
    p.next = newNode
    
    fmt.Printf("插入数据:%d
", data)
}

// 删除尾节点并返回其值
func (p *Node) Pop() (int, error) {
    if p.next == nil {
        return 0, errors.New("Error: pop from empty list!")
    }

    var tmp *Node
    for p.next != nil {
        tmp = p
        p = p.next
    }
    tmp.next = nil
    fmt.Printf("删除数据:%d
", p.data)
    return p.data, nil

}

// 查询第i个节点的值
func (p *Node) Find(i int) (int, error) {
    for p.next != nil && i > 0 {
        p = p.next
        i -= 1
    }
    if i > 0 {
        return 0, errors.New("Error: the node not exist!")
    }

    return p.data, nil
}

// 修改第i个节点的值
func (p *Node) Update(i, data int) (error) {
    for p.next != nil && i > 0 {
        p = p.next
        i -= 1
    }
    if i > 0 {
        return errors.New("Error: the node not exist!")
    }
    p.data = data
    return nil
}

func main() {
    var head *Node
    head = new(Node)

    for a := 0; a < 10; a++ {
        head.Append(a)
    }
    head.Traverse()

    data, err := head.Pop()
    if err != nil {
        fmt.Println(err)
    }
    fmt.Printf("Pop返回数据:%d
", data)
    head.Traverse()

    data, err = head.Find(3)
    if err != nil {
        fmt.Println(err)
    }
    fmt.Printf("查询的数据为:%d
", data)

    err = head.Update(2, 20)
    if err != nil {
        fmt.Println(err)
    }
    head.Traverse()

}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注