线性表.md

线性表

线性表

• 定义：由n个数据元素组成的有限序列；原则上数据类型可以不一致，但存储类型可能会做出一定的限制
• 特性:
  • 除第一个元素外,其他元素只有一个直接前驱;除了最后一个元素,其他元素只有一个直接后继.
  • 表示方式:顺序存储方式/链表存储方式

顺序表

• 定义:将线性表中的元素相继存放在一个连续的存储空间中,可以利用一维数组描述数据结构
• 特性:所有元素的逻辑先后顺序和物理存放顺序一致

const MAX_SIZE = 100

// SQListA 顺序表的静态存储表示
type SQListA struct{
    data    [MAX_SIZE]int64
    length  int
}

// SQListB 顺序表的动态存储表示
type SQListB struct{
    data    *int64
    length  int
}

// Init_SQ 初始化顺序表
func Init_SQ(list *SQListA) bool{
    list.data = new [MAX_SIZE]int64
    if (!list.data) return false
    list.length = 0
    return true
}

• 顺序表的插入算法
  • 在某一个位置插入某一个元素,将后面位置的元素依次移动
  • 性能分析:O(n)
• 顺序表的删除算法
  • 在某一个位置删除某元素,将后面位置的元素依次移动
  • 性能分析:O(n)
• 顺序表的搜索算法
  • 依次比较,某一个值对应的时候返回
  • 性能分析:O(n)
• 顺序存储的线性表特点:
  • 优点: 表中的任一结点的存取很方便(随机访问)
  • 缺点:插入和删除操作不方便,操作中需要移动大量元素;会造成大量的空间浪费以及不容易扩充数据(内存的碎片)

单链表

• 特点:每个元素由表项和结点组成,结点之间可以连续,也可以非连续;逻辑顺序和物理顺序可以不一致;可以扩充
• 结点定义：

type LNode struct{
    Data int64
    Next *LNode
}
p = new(LNode) // 创建一个新链表
p.Data = 20
p.Next = nil   // 赋值数据和下一结点的链接

• 单链表生成代码：

// 生成没有头结点的链表，需要在代码中多做一次判断
func CreateListTailWithoutHead(L *LNode, n int64) {
    q := new(LNode)
    for range n {
        p := new(LNode)
        p.Next = nil
        p.Data = rand.Intn(100)
        if (L == nil) {
            L = p
        } else {
            q.Next = p
        }
        q = p
    }
}

// 生成有头结点的链表
func CreateListTailWithHead(L *LNode, n int64) {
    L = new(LNode)
    q = new(LNode)

    L.Next = nil
    q = L
    for range n {
        p = new(LNode)
        p.Data = rand.Intn(100)
        p.Next = nil
        q.Next = p
        q = p
    }
}

• 使用带头结点的单链表的优点
  • 链表的第一个位置上的操作和其他位置上的操作一致，不需要单独操作
  • 无论链表是否为空，其头指针都指向了头结点的非空指针，空表和非空表的处理统一
• 单链表获取某一元素代码

func GetElem(L *LNode, n int64)(elem int64, err error) {
    var (
        p *LNode
    )
    p = L.Next
    for range n {
        if p = p.Next; p == nil {
            return 0, fmt.Errorf("链表越界")
        }
    }
    elem = p.Data
    return elem, nil
}

循环链表

• 特性：循环链表的最后一个结点的next指向头
• 只要直到了某一结点的地址，就能知道所有结点的地址

双向链表

• 特性：指在前驱和后继都能遍历的线性链表。双向链表是为了克服单链表的单向性的缺陷。
• 双向链表通常采用带头结点的循环链表