实现常用数据结构(线性表)

线性表按照存储方式大致上分为两种:

• 顺序表示
• 链式表示

顺序表示

线性表的顺序存储又称顺序表。它是用–组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。第 1 个元素存储在线性表的起始位置,第 i 个元素的存储位置后面紧接着存储的是第 i+ 1 个元素，称 i 为元素 a;在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

基本上可以通过 GO 语言内置的列表来实现. 由于经常使用, 故不做过多的描述, 直接放代码.

package Linear_List

import (
    "errors"
)

const Max_Length = 20

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

func InitLineList() *ContiguousList {
    return &ContiguousList{
        MaxLength:       Max_Length,
        LineListContent: make([]interface{}, 0, Max_Length),
    }
}

// 判断是否为空
func (c ContiguousList) IsEmpty() bool {
    if c.Length == 0 {
        return true
    }
    return false
}

// 判断是否满
func (c ContiguousList) IsFull() bool {
    if c.Length == c.MaxLength {
        return true
    }
    return false
}

// 判断是否越界
func (c ContiguousList) indexOver(i int) bool {
    if i < 1 || i > c.Length {
        return true
    }
    return false
}

// 获取指定的数据
func (c ContiguousList) getData(i int) (interface{}, error) {
    if ok := c.indexOver(i); ok {
        return "", errors.New("查找的索引不在线性表范围内")
    }
    return c.LineListContent[i+1], nil
}

//删除任意位置的一个数据
func (c *ContiguousList) Delete(i int) (interface{}, error) {
    if ok := c.indexOver(i); ok {
        return "", errors.New("删除的索引不在线性表内")
    }
    if ok := c.IsEmpty(); ok {
        return "", errors.New("没有可以删除的数据")
    }
    deleteData := c.LineListContent[i-1]
    for j := i - 1; j < c.Length-1; j++ {
        c.LineListContent[j] = c.LineListContent[j+1]
    }
    c.LineListContent = c.LineListContent[:c.Length-1]
    c.Length--
    return deleteData, nil
}

// 在末尾推出一个数据
func (c *ContiguousList) Pop() (interface{}, error) {
    if ok := c.IsEmpty(); ok {
        return "", errors.New("没有可以删除的数据")
    }
    temp := c.LineListContent[c.Length-1]
    c.LineListContent = c.LineListContent[:c.Length-1]
    c.Length--
    return temp, nil
}

// 在末尾添加一个数据
func (c *ContiguousList) Append(data interface{}) (bool, error) {
    if ok := c.IsFull(); ok {
        return false, errors.New("线性表已经满了")
    }
    c.LineListContent = append(c.LineListContent, data)
    c.Length++
    return true, nil
}

// 在任意位置插入一个数据
func (c *ContiguousList) Insert(i int, data interface{}) (bool, error) {
    if ok := c.IsFull(); ok {
        return false, errors.New("线性表已满，无法添加数据")
    }
    if ok := c.indexOver(i); ok {
        return false, errors.New("插入点越界")
    }
    _, _ = c.Append("")
    for j := c.Length - 1; j > i-1; j-- {
        c.LineListContent[j] = c.LineListContent[j-1]
    }
    c.LineListContent[i-1] = data
    return true, nil
}

以下是测试的例子以及输出:

func main() {
    cl := Linear_List.InitLineList()
    _, _ = cl.Append(11)
    _, _ = cl.Insert(1, 34)
    _, _ = cl.Append(90)
    fmt.Println(cl.LineListContent)
    fmt.Println(cl.Length)
    _, _ = cl.Delete(2)
    fmt.Println(cl.LineListContent)
    cd, err0 := cl.Pop()
    if err0==nil{
        fmt.Println(cd)
    }
    fmt.Println(cl.LineListContent)
    fmt.Println(cl.Length)
}

// [34 11 90]
// 3
// [34 90]
// 90
// [34]
// 1

顺序表示-例题

1. 剔除数组最小的元素, 空出的位置由最后的元素填补.
2. 数组原地逆序
3. 删除值为 x 的数据元素, 时间 O(x)、空间 O(1)
4. 删除有序列表中给定值于 s-t 中的所有元素
5. 删除无序列表中给定值于 s-t 中的所有元素
6. 从有序列表中删除所有值重复的元素
7. 将两个有序顺序表合并为一个新的有序顺序表
8. 有序列表的二分查找, 查找到的元素与其后继元素交换

我的题解

能力有限, 只是初步实现功能.

第一题

遍历了一遍顺序表, 找到最小的元素后与最后的元素交换位置, 然后剔除最后的元素.

func (c *ContiguousList) DeleteSmallest() error {
    if c.IsEmpty() {
        return errors.New("列表为空")
    }
    min, list := 0, c.LineListContent
    for i, _ := range list {
        x := list[i].(int)
        if list[min].(int) > x {
            min = i
        }
    }
    list[min], list[c.Length-1] = list[c.Length-1], list[min]
    _, _ = c.Pop()
    return nil
}

第二题

头尾双指针, 同时向中间遍历, 遍历期间不断交换两个指针的值.

func (c *ContiguousList) Reverse() {
    i, j := 0, c.Length-1
    if i == j {
        return
    }
    list := c.LineListContent
    for i < j {
        list[i], list[j] = list[j], list[i]
        i++
        j--
    }
}

第三题 or 第四题、第五题和第六题

从头到尾进行一次遍历, 使用 num 记录目标值个数, 期间如果当前元素是目标值, 则记录并减少 length 长度;如果不是目标值, 则将其复制到应该存在的位置(根据当前的 i 和 num 决定), 最后只用取长度为 length 的顺序表即可.

func (c *ContiguousList) DeleteX(x interface{}) error {
    if c.IsEmpty() {
        return errors.New("列表为空")
    }
    list, num := c.LineListContent, 0
    for i, _ := range list {
        if list[i] == x {  //在这里修改条件
            num++
            c.Length--
        } else {
            list[i-num] = list[i]
        }
    }
    c.LineListContent = list[:c.Length]
    return nil
}

第四题、第五题和第六题我感觉和第三题差不太多, 我的做法是使用第三题的思路, 不过在 for 循环中的 if 的判断条件变了一下, 照样是可以实现 O(n) 和 O(1) 的复杂度的算法.

如果说可能有什么优化的话, 我感觉在第四题中可以使用二分查找搜索 s 和 t 的位置, 然后修改整个列表. 不过我嫌麻烦 😂 就不打算写了.

第五题和第六题我想不出来能怎么优化.

第七题

基本思想: 使用两个指针指向两个有序顺序表, 然后依次比较后录入, 最后将剩下的元素录入.

func MergeOrderList(c1, c2 *ContiguousList) *ContiguousList {
    c := InitLineList()
    l1, l2, it1, it2, le1, le2 := c1.LineListContent, c2.LineListContent, 0, 0, c1.Length, c2.Length
    for it1 < le1 && it2 < le2 {
        if l1[it1].(int) < l2[it2].(int) {
            c.Append(l1[it1])
            it1++
        } else {
            c.Append(l2[it2])
            it2++
        }

    }
    if it1 == le1 {
        for i := it2; i < le2; i++ {
            c.Append(l2[it2])
        }
    } else {
        for i := it1; i < le1; i++ {
            c.Append(l1[it1])
        }
    }
    return c
}

第八题

基础的二分查找, 比较怪的是查找后找到后与后继元素互换位置… 我没怎么搞懂这么做有什么意义…

func (c *ContiguousList) BisInsert(x interface{}) {
    if c.IsEmpty() {
        c.Append(x)
    }
    var mid int
    left, right, list := 0, c.Length-1, c.LineListContent
    for left <= right {
        mid = (right-left)/2 + left
        if list[mid].(int) == x.(int) {
            break
        } else if list[mid].(int) > x.(int) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    if left <= right {
        if mid == c.Length-1 {
            return
        } else {
            list[mid], list[mid+1] = list[mid+1], list[mid]
        }
    } else {
        if mid == c.Length-1 {
            c.Append(x)
        } else {
            c.Insert(mid+2, x)
        }
    }
}

链式表示

顺序表可以随时存取表中的任意-一个元素，它的存储位置可以用一个简单直观的公式表示，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置.上也相邻，它通过“链”建立起数据元素之间的逻辑关系, 因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。

想要实现线性表的链式表示, 需要自定义一个结点结构, 一部分保存值, 一部分保存下一个元素的地址.

type Node struct {
    data interface{}
    next *Node
}

然后让我们来实现其基本函数

package SinglyLinkedList

import "fmt"

type Node struct {
    data interface{}
    next *Node
}

func InitLinkList() *Node {
    return &Node{"The head node", nil}
}

// 获取第一个结点
func (n *Node) GetFirstNode() *Node {
    if n.next == nil {
        return nil
    }
    return n.next
}

//获取最后一个结点
func (n *Node) GetEndNode() *Node {
    if n.next == nil {
        return nil
    }
    for n.next != nil {
        n = n.next
    }
    return n
}

// 在末尾添加一个结点
func (n *Node) EndAppend(data interface{}) bool {
    tempNode := &Node{data, nil}
    for n.next != nil {
        n = n.next
    }
    n.next = tempNode
    return true
}

// 在开头添加一个结点
func (n *Node) HeadAppend(data interface{}) bool {
    tempNode := &Node{data, n.next}
    n.next = tempNode
    return true
}

// 查找一个结点, 返回其距离头结点的长度
func (n *Node) GetOneNode(i int) *Node {
    length := 0
    for n.next != nil {
        length++
        if i == length {
            return n.next
        }
        n = n.next
    }
    return nil
}

// 删除一个结点
func (n *Node) Delete(i int) *Node {
    length := 0
    for n.next != nil {
        length++
        if i == length {
            temp := n.next
            n.next = n.next.next
            return temp
        }
        n = n.next
    }
    return nil
}

func (n *Node) GetLinkLength() (length int) {
    for n.next != nil {
        length++
        n = n.next
    }
    return length
}

// 插入一个结点
func (n *Node) Insert(i int, data interface{}) bool {
    needAppend := &Node{data, nil}
    if i > n.GetLinkLength() || i < 1 {
        panic("插入位置错误")
        return false
    }
    length := 1
    for n.next != nil {
        if i == length {
            temp := n.next
            n.next = needAppend
            needAppend.next = temp
            return true
        }
    }
    return false
}

// 在控制台按顺序打印出所有的元素
func (n *Node) MapTheLinkList() {
    length := n.GetLinkLength()
    for i := 0; i < length; i++ {
        fmt.Println(n.next.data)
        n = n.next
    }
}

// 删除所有元素
func (n *Node) Clear() bool {
    if n.next == nil {
        return true
    }
    n.next = nil
    return true
}

以下是测试的例子以及输出:

func main() {
    li := SinglyLinkedList.InitLinkList()
    fmt.Println(li)
    li.EndAppend("aaa")
    li.HeadAppend("bbb")
    li.EndAppend("ccc")
    li.MapTheLinkList()
    fmt.Println(*li.GetFirstNode())
    fmt.Println(*li.GetEndNode())
    fmt.Println(li.GetLinkLength())
    fmt.Println("delete = ", li.Delete(1))
    li.MapTheLinkList()
    li.Clear()
    fmt.Println(li)
}

// &{The head node <nil>}
// bbb
// aaa
// ccc
// {bbb 0x140000a6048}
// {ccc <nil>}
// 3
// delete =  &{bbb 0x140000a6048}
// aaa
// ccc
// &{The head node <nil>}

更加复杂的双链表以及循环链表, 其实和单链表的原理相差不多, 下次再研究吧.

链式表示-例题

1. 设计一个递归算法，删除不带头结点的单链表 L 中所有值为 x 的结点。
2. 在带头结点的单链表 L 中，删除所有值为 x 的结点，并释放其空间，假设值为 x 的结点不唯一，试编写算法以实现上述操作。
3. 设 L 为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。
4. 试编写在带头结点的单链表 L 中删除一个最小值结点的高效算法(假设最小值结点是唯一的)。
5. 试编写算法将带头结点的单链表就地逆置，所谓“就地” 是指辅助空间复杂度为 0(1)。
6. 有一个带头结点的单链表 L,设计一个算法使其元素递增有序。
7. 设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值(作为函数参数给出)之间的元素的元素(若存在)。
8. 给定两个单链表，编写算法找出两个链表的公共结点。
9. 给定一个带表头结点的单链表，设 head 为头指针，结点结构为(data, next)，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素,并释放结点所占的存储空间(要求:不允许使用数组作为辅助空间)。
10. 将一个带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B,使得 A 表中含有原表中序号为奇数的元素,而 B 表中含有原表中序号为偶数的元素，且保持其相对顺序不变。
11. 设 C= {a1, b1, a2, b2.,.,an, bn}为线性表，采用带头结点的 hc 单链表存放，设计一个就地算法，将其拆分为两个线性表，使得 A= {a1, a2,…,an}, B= {b1, b2,…,bn}。
12. 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素,使表中不再有重复的元素,例如(7, 10, 10, 21, 30, 42, 42, 42, 51, 70)将变为(7, 10, 21, 30, 42,51, 70)。
13. 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
14. 设 A 和 B 是两个单链表(带头结点),其中元素递增有序。设计一个算法从 A 和 B 中的公共元素产生单链表 C,要求不破坏 A、B 的结点。
15. 已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。编制函数，求 A 与 B 的交集，并存放于 A 链表中。
16. 两个整数序列 A=a1,a2,…,am 和 B= b1, b2,…,bn 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的连续子序列。

我的题解

第一题 or 第二题/第七题

每次判断下一个节点的值是否等于 x, 如果等于则舍弃. 然后使用下一个节点调用该函数.

func (n *Node) DeleteX(x interface{}) {
    if n.next == nil {
        return
    } else {
        if n.next.data == x {
            n.next = n.next.next
        }
        n.next.DeleteX(x)
    }
    return
}

第二题、第七题与本题基本相似. 第一题只用在前面加上自身的判断即可.

第三题

使用递归, 首先使用下一个节点调用函数, 再输出当前节点的值.

func (n *Node) PrintTail() {
    if n.next != nil {
        n.next.PrintTail()
    }
    fmt.Print(n.data, " ")
}

第四题

思路基本和顺序表相同, 就是使用两个指针, 一个指针用来遍历链表, 一个用来记录最小值 .

不过需要注意的是, 记录最小值需要记录最小节点的前驱节点, 也就是判断 min.next.data 是否为最小, 这样才便于删除.

func (n *Node) DeleteMin() {
    var min, idx *Node
    min, idx = n, n
    if idx.next != nil {
        if idx.next.data.(int) < min.next.data.(int) {
            min = idx
        }
        idx = idx.next
    }
    min.next = min.next.next
    return
}

第五题

就地逆置的核心思想就是在遍历过程中, 使用头插法依次重新插入一遍节点, 不过需要额外一个指针 next 来标明下一个节点的地址.

func (n *Node) Reverse() {
    var idx, next *Node
    idx = n.next
    n.next = nil
    for idx != nil {
        next = idx.next      // 保存下一个节点
        idx.next = n.next
        n.next = idx        // 头插法将当前节点加入到主链表中
        idx = next            // 处理下一个节点
    }
}

第六题

采用自底向上归并排序的做法, 能够做到时间复杂度为 O(nlgn) 空间复杂度为 O(1)

func (n *Node) SortList() *Node {
    if n == nil {
        return n
    }
    length := n.GetLinkLength()
    fmt.Println(length)
    l := n
    for curI := 1; curI < length; curI <<= 1 {
        pre, cur := l, l.next
        for cur != nil {
            head1 := cur
            for i := 1; i < curI; i++ {
                cur = cur.next
            }
            head2 := cur.next
            cur.next = nil
            cur = head2
            for i := 1; i < curI && cur != nil && cur.next != nil; i++ {
                cur = cur.next
            }
            var next *Node
            if cur != nil {
                next = cur.next
                cur.next = nil
            }
            pre.next = Merge(head1, head2)
            for pre.next != nil {
                pre = pre.next
            }
            cur = next
        }
    }
    return n
}

第八题

两个指针分别遍历两个链表, 如果遍历完了就到对方到链表中. 这样如果两个链表有相交, 则必定在指针遍历对方的链表时同时到达相交的位置.

两个结点不断的去对方的轨迹中寻找对方的身影，只要二人有交集，就终会相遇 ❤

func getIntersectionNode(list1, list2 *Node) *Node {
    l1, l2 := list1, list2
    for l1 != l2 {
        if l1 != nil {
            l1 = l1.next
        } else {
            l1 = list2
        }
        if l2 != nil {
            l2 = l2.next
        } else {
            l2 = list1
        }
    }
    return l1
}

第九题

没啥好说的, 就是调用了第六题的函数

func (n *Node) IncreasePrint() {
    n.SortList()
    cur := n
    for cur.next != nil {
        fmt.Print(cur.next.data, " ")
        cur = cur.next
    }
    fmt.Println()
}

第十题 or 第十一题

这道题只用在遍历时使用一个变量记录当前节点的奇偶, 然后分别赋值给两个新链表即可. 需要注意的是最后需要将两个链表的末尾节点的 next 指向 nil, 不然会出现错误.

func ParitySplit(n *Node) (odd, even *Node) {
    odd, even = InitLinkList(), InitLinkList()
    o, e := odd, even
    cur, length := n, 0
    for cur.next != nil {
        length++
        if length%2 == 0 {
            e.next = cur.next
            e = e.next
        } else {
            o.next = cur.next
            o = o.next
        }
        cur = cur.next
    }
    o.next, e.next = nil, nil
    return
}

而第十一题, 大致上是相同的, 不过注意偶数链表的节点是逆序的, 所以对于偶数链表我们可以使用头插法加入节点, 这样就可以实现逆序.

第十二题

如果相同就跳过, 不相同就不管.

func (n *Node) RemoveDuplicates() {
    cur := n.next
    for cur != nil && cur.next != nil {
        if cur.data == cur.next.data {
            cur.next = cur.next.next
        }
        cur = cur.next
    }
}

第十三题

合并两个升序链表和合并两个升序顺序表差不多, 不多做赘述.

func Merge(list1, list2 *Node) *Node {
    newList := &Node{}
    l1, l2, nl := list1, list2, newList
    for l1 != nil && l2 != nil {
        if l1.data.(int) <= l2.data.(int) {
            nl.next = l1
            l1 = l1.next
        } else {
            nl.next = l2
            l2 = l2.next
        }
        nl = nl.next
    }
    if l1 != nil {
        nl.next = l1
    } else {
        nl.next = l2
    }
    return newList.next
}

第十四题

因为, 如果两个链表存在公共节点, 则公共节点后一定相同. 所以只需要获取两个链表的公共节点即可.

func IntersectionNode(list1, list2 *Node) *Node {
    c := InitLinkList()
    c.next = getIntersectionNode(list1, list2)
    return c
}

第十五题

使用两个指针分别遍历两个链表, 如果相等则将其加入到 A 链表后, 由于都是递增排列, 所以如果小于, 则之后第元素都小于, 因此不存在相等的, 所以 A 的指针移动. 如果大于, 则可能 B 中会存在相等的, 所以 B 的指针移动.

func (n *Node) Intersection(another *Node) {
    l1, l2 := n, another
    idx := n
    for l1.next != nil && l2.next != nil {
        if l1.next.data.(int) == l2.next.data {
            idx.next = l1.next
            idx = idx.next
            l1 = l1.next
            l2 = l2.next
        } else if l1.next.data.(int) < l2.next.data.(int) {
            l1 = l1.next
        } else {
            l2 = l2.next
        }
    }
    idx.next = nil
}

第十六题

类似于暴力版的字符串匹配, 遍历主链表的每一个元素, 如果相等则代表有机会是连续子序列. 所以创建两个指针遍历两个链表, 如果目标链表的指针到底了, 说明全部匹配, 则返回 true. 如果遍历到主链表的最后一个元素了,则说明无法匹配, 则返回 false

func (n *Node) ContinuousSubsequence(target *Node) bool {
    cur := n
    for cur.next != nil {
        if cur.next.data.(int) == target.next.data {
            l1, l2 := cur.next, target.next
            for l1 != nil && l2 != nil {
                if l1.data.(int) != l2.data.(int) {
                    break
                }
                l1, l2 = l1.next, l2.next
            }
            if l2 == nil {
                return true
            }
        }
        cur = cur.next
    }
    return false
}