Golang数据结构-线性表

基本概念
  • 定义：零个或者多个数据元素的有限序列，在复杂的线性表中，一个数据元素可以由若干个数据项组成。
  • 直接前驱元素：若线性表记为(a1a2a3...an),则表中a2领先于a3，则称a2是a3的直接前驱元素，且有且仅有一个直接前驱元素
  • 直接后继元素：称a3是a2的直接后继元素，且有且仅有一个直接后继元素
  • 线性表的长度：线性表的元素个数n，为线性表的长度，随着线性表插入和删除操作，该值是变动的，线性表的存储长度一般小于数组的长度
  • 数组的长度：存放线性表的存储空间的长度，存储分配后这个值一般是不变的
  • 空表：长度n为0时，该线性表为空表
  • 地址：存储器的每个存储单元都有自己在内存的编号，简称为地址
线性表的存储
顺序存储结构

线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素，可以用一维数组来实现。

package linelist

import (
    "errors"
)

const MaxLength = 20

type LineList struct {
    MaxLength       int
    Length          int
    LineListContent []interface{}
}

//线性表的初始化操作
func InitLineList() *LineList {
    return &LineList{MaxLength: MaxLength, Length: 0, LineListContent: make([]interface{}, 0)}
}

//判断线性表是否为空
func (l *LineList) Empty() bool {
    return l.Length == 0
}

//获取线性表第i个元素的值，第一个元素对应线性表下表为0的元素
func (l *LineList) GetElem(i int) (interface{}, error) {
    if i < 1 || i > l.Length {
        return "", errors.New("查找的元素不在线性表范围内")
    }
    return l.LineListContent[i-1], nil
}

//删除线性表的第i个元素
func (l *LineList) DelElem(i int) (bool, error) {
    if i < 1 || i > l.Length {
        return false, errors.New("查找的元素不在线性表范围内")
    }
    if l.Empty() {
        return false, errors.New("空表没有可以删除的数据")
    }
    for j := i - 1; j < l.Length-1; j++ {
        l.LineListContent[j] = l.LineListContent[j+1]
    }
    l.LineListContent = l.LineListContent[:l.Length-1]
    l.Length--
    return true, nil
}

// 在线性表中的第i个位置插入元素data
func (l *LineList) Insert(i int, data interface{}) (bool, error) {
    if i < 1 || i > l.Length {
        return false, errors.New("查找的元素不在线性表范围内")
    }
    if b, _ := l.Append(""); !b {
        return false, errors.New("线性表已满，无法添加数据")
    }
    for j := l.Length - 1; j > i-1; j-- {
        l.LineListContent[j] = l.LineListContent[j-1]
    }
    l.LineListContent[i-1] = data
    return true, nil
}

// 从末尾弹出一个元素
func (l *LineList) Pop() (interface{}, error) {
    if l.Empty() {
        return "", errors.New("线性表长度为0，没有可弹出的元素")
    }
    result := l.LineListContent[l.Length-1]
    l.LineListContent = l.LineListContent[:l.Length-1]
    l.Length--
    return result, nil
}

// 从末尾插入一个元素
func (l *LineList) Append(data interface{}) (bool, error) {
    if l.Length == l.MaxLength {
        return false, errors.New("线性表已满，无法添加数据")
    }
    l.LineListContent = append(l.LineListContent, data)
    l.Length++
    return true, nil
}
链式存储结构
  • 特点：是用一组任意的存储单元存储线性表的数据元素，可以是连续的也可以是不连续的。
  • 数据域：为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置)，存储信息的域叫数据域
  • 指针域：把存储直接后继位置的域称为指针域
  • 指针|链：指针域中存储的信息称为指针或域
  • 结点：数据域和指针域组成数据元素ai的存储映像，称为结点
  • 头指针：把链表中第一个结点的存储位置叫做头指针，线性表的最后一个结点指针为空
  • 头结点：在单链表的第一个结点前附设一个结点，称为头结点，头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。
单链表

单链表：n个结点链接成一个链表，即为线性表(a1a2a3...an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起的。

package linelist

// 单链表结点
type SingleList struct {
    Data interface{} //单链表的数据域
    Next *SingleList //单链表的指针域
}

func NewSingleList() *SingleList {
    return &SingleList{Data: "", Next: nil}
}

type SingleListr interface {
    GetFirst() *SingleList
    GetLast() *SingleList
    Length() int
    Add(data interface{}) bool
    GetElem(index int) (interface{}, error)
    Delete(index int) bool
}

//返回第一个结点
func (this *SingleList) GetFirst() *SingleList {
    if this.Next == nil {
        return nil
    }
    return this.Next
}

//返回最后一个结点
func (this *SingleList) GetLast() *SingleList {
    if this.Next == nil {
        return nil
    }
    point := this
    for point.Next != nil {
        point = point.Next
    }
    if point.Next == nil {
        return point
    }
    return nil
}

//获取单链表的长度
func (this *SingleList) Length() int {
    point := this
    length := 0

    for point.Next != nil {
        length++
        point = point.Next
    }
    return length
}

//往单链表的末尾加一个元素
func (this *SingleList) Add(data interface{}) bool {
    point := this
    for point.Next != nil {
        point = point.Next
    }
    tmpSingle := SingleList{Data: data}
    point.Next = &tmpSingle
    return true
}

//获取所有结点的值
func (this *SingleList) GetAll() []interface{} {
    result := make([]interface{}, 0)
    point := this
    for point.Next != nil {
        result = append(result, point.Data)
        point = point.Next
    }
    result = append(result, point.Data)
    return result
}

//获取索引为index的结点
func (this *SingleList) GetElem(index int) *SingleList {
    point := this
    if index < 0 || index > this.Length() {
        panic("check index error")
        return nil
    }
    for i := 0; i < index; i++ {
        point = point.Next
    }
    return point
}

//删除第index个结点
func (this *SingleList) Delete(index int) bool {
    if index < 0 || index > this.Length() {
        panic("please check index")
        return false
    }
    point := this
    for i := 0; i < index-1; i++ {
        point = point.Next
    }
    point.Next = point.Next.Next
    return true
}
单循环链表

定义：将单链表中终端节点的指针端由空指针改为指向头节点，就使得整个单链表形成一个环，这种头尾相接的单链表简称为循环链表

package linelist

import "errors"

//定义单循环链表的节点数据结构
type CircleNode struct {
    data interface{}
    next *CircleNode
}

//定义单循环链表的数据结构
type CircleList struct {
    tail *CircleNode
    size int
}

func InitCircleList() *CircleList {
    return &CircleList{tail: nil, size: 0}
}

func InitCircleNode(data interface{}) *CircleNode {
    return &CircleNode{data: data, next: nil}
}

//单链表在表尾添加数据
func (cl *CircleList) Append(data *CircleNode) bool {
    if data == nil {
        return false
    }
    if cl.size == 0 {
        data.next = data
    } else {
        curNode := cl.tail.next
        data.next = curNode
        cl.tail.next = data
    }
    cl.tail = data
    cl.size++
    return true
}

//单循环链表插入数据
func (cl *CircleList) Insert(num int, data *CircleNode) error {
    if data == nil {
        return errors.New("要插入的节点数据为空")
    }
    if cl.size == 0 || cl.size == num {
        cl.Append(data)
    } else {
        var curNode *CircleNode
        if num == 0 {
            curNode = cl.tail
        } else {
            curNode = cl.Get(num)
            if cl.size == num {
                cl.tail = data
            }
        }
        data.next = curNode.next
        curNode.next = data
        cl.size++
    }
    return nil
}

//单循环链表查询数据
func (cl *CircleList) Get(num int) *CircleNode {
    if num < 0 || num > cl.size-1 {
        return nil
    }
    curNode := cl.tail
    for i := 0; i < num; i++ {
        curNode = curNode.next
    }
    return curNode
}

//单循环链表查询全部数据
func (cl *CircleList) GetAll() []interface{} {
    result := make([]interface{}, 0)
    curNode := cl.tail
    for i := 0; i < cl.size; i++ {
        result = append(result, curNode.data)
        curNode = curNode.next
    }
    return result
}

//单循环链表按序号删除数据
func (cl *CircleList) RemoveInt(num int) error {
    if cl.size == 0 {
        return errors.New("循环链表为空")
    }
    if num > cl.size-1 {
        return errors.New("越界")
    }

    if cl.size == 1 {
        cl.tail = nil
        cl.size = 0
        return nil
    } else {
        var curNode *CircleNode
        var data *CircleNode
        if num == 0 {
            curNode = cl.tail
        } else {
            curNode = cl.Get(num - 1)
        }

        data = curNode.next
        curNode.next = data.next

        if num == cl.size-1 {
            cl.tail = curNode
        }

        data.next = nil
        data = nil
        cl.size--

        return nil
    }
}

//单循环链表删除全部数据
func (cl *CircleList) RemoveAll() bool {
    if cl.size == 0 {
        return false
    }

    for i := 0; i < cl.size; i++ {
        curNode := cl.tail
        cl.tail = curNode.next
        curNode.next = nil
    }
    cl.tail = nil
    cl.size = 0

    return true
}
双向链表

定义：在单链表的每个节点中，再设置一个指向其前驱节点的指针域。所以在双向链表中的节点都有两个指针域，一个指向直接后继，另一个直接指向前驱

package linelist

import (
    "errors"
)

var (
    NUMERROR = errors.New("链表越界")
)
//定义双向链表节点结构体
type DoubleNode struct {
    data interface{}
    prev *DoubleNode
    next *DoubleNode
}

//定义双向链表结构体
type DoubleList struct {
    head *DoubleNode
    tail *DoubleNode
    size int
}

//初始化链表

func InitDoubleList() *DoubleList {
    return &DoubleList{head: nil, tail: nil, size: 0}
}

func InitDoubleNode(data interface{}) *DoubleNode {
    return &DoubleNode{data: data, prev: nil, next: nil}
}

//获取链表的长度
func (dl *DoubleList) GetSize() int {
    return dl.size
}

//获取链表头部节点
func (dl *DoubleList) GetHead() *DoubleNode {
    return dl.head
}

//获取链表尾部节点
func (dl *DoubleList) GetTail() *DoubleNode {
    return dl.tail
}

//在头部追加节点
func (dl *DoubleList) AddHeadNode(node *DoubleNode) int {
    if dl.GetSize() == 0 {
        dl.head = node
        dl.tail = node
        node.prev = nil
        node.next = nil
    } else {
        dl.head.prev = node
        node.prev = nil
        node.next = dl.head
        dl.head = node
    }
    dl.size += 1
    return dl.size
}

//在尾部追加节点
func (dl *DoubleList) AddTailNode(node *DoubleNode) int {
    if dl.GetSize() == 0 {
        dl.head = node
        dl.tail = node
        node.prev = nil
        node.next = nil
    } else {
        dl.tail.next = node
        node.prev = dl.tail
        node.next = nil
        dl.tail = node
    }
    dl.size += 1
    return dl.size
}

//在链表某个序号之后插入节点
func (dl *DoubleList) InsertNextInt(num int, data *DoubleNode) bool {
    if data == nil || num > dl.GetSize()-1 || num < 0 {
        return false
    }
    switch {
    case dl.GetSize() == 0:
        dl.AddHeadNode(data)
    case num == dl.GetSize()-1:
        dl.AddTailNode(data)
    default:
        curNode, err := dl.GetOrder(num)
        if err != nil {
            return false
        }
        data.prev = curNode
        data.next = curNode.next
        curNode.next = data
        curNode.next.prev = data
        dl.size++
    }
    return true
}

//顺序查询某个序号的数据
func (dl *DoubleList) GetOrder(num int) (*DoubleNode, error) {
    switch {
    case dl.GetSize() == 0:
        return nil, NUMERROR
    case num == 0:
        return dl.head, nil
    case num > dl.GetSize()-1:
        return nil, NUMERROR
    case num == dl.GetSize()-1:
        return dl.tail, nil
    default:
        data := dl.head
        for i := 0; i < num; i++ {
            data = data.next
        }
        return data, nil
    }
}

//倒序查询某个序号数据
func (dl *DoubleList) GetReverse(num int) (data *DoubleNode, err error) {
    switch {
    case num == 0:
        data = dl.tail
    case num > dl.GetSize()-1:
        err = NUMERROR
    case num == dl.GetSize()-1:
        data = dl.head
    default:
        data = dl.tail
        for i := 0; i < num; i++ {
            data = data.prev
        }
    }
    return
}

//获取链表中所有数据
func (dl *DoubleList) GetAll() []interface{} {
    result := make([]interface{}, 0)
    if dl.GetSize() == 0 {
        return nil
    }
    curNode := dl.head
    for i := 0; i < dl.GetSize(); i++ {
        result = append(result, curNode.data)
        curNode = curNode.next
    }
    return result
}

//删除某个序号的数据
func (dl *DoubleList) Remove(num int) error {
    if dl.GetSize() == 0 {
        return NUMERROR
    }

    var curNode *DoubleNode
    var err error
    if curNode, err = dl.GetOrder(num); err != nil {
        return err
    }

    if num == 0 {
        curNode.next.prev = nil
        dl.head = curNode.next
    } else if num == dl.size-1 {
        curNode.prev.next = nil
        dl.tail = curNode.prev
    } else {
        curNode.prev.next = curNode.next
        curNode.next.prev = curNode.prev
    }

    curNode.prev = nil
    curNode.next = nil
    dl.size--
    return nil
}

//删除链表中的全部数据
func (dl *DoubleList) RemoveAll() bool {
    for i := 0; i < dl.GetSize(); i++ {
        curNode := dl.head
        dl.head = curNode.next
        curNode.next = nil
        curNode.prev = nil
    }
    dl.tail = nil
    dl.size = 0
    return true
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 219,039评论 6赞 508
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,426评论 3赞 395
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 165,417评论 0赞 356
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,868评论 1赞 295
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,892评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,692评论 1赞 305
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,416评论 3赞 419
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,326评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,782评论 1赞 316
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,957评论 3赞 337
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,102评论 1赞 350
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,790评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,442评论 3赞 331
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,996评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,113评论 1赞 272
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,332评论 3赞 373
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 45,044评论 2赞 355