基本概念

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

线性表的存储

顺序存储结构

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

package linelistimport (    "errors")const MaxLength = 20type 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个位置插入元素datafunc (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 linelistimport "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 linelistimport (    "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}

给这篇文章的作者打赏

微信扫一扫打赏

支付宝扫一扫打赏

×

打赏 点赞(0)