(go)线性表的次序存储

线性表的"顺序存储"本质是：用一段连续内存存元素，用 Last 记录当前元素个数。这个模型在 C 语言里是经典教材，换到 Go 里主要变成"用切片 []T 代替数组 + 一个长度游标"的写法。本文用 Go 把建表、查找、插入、删除、遍历这套操作走一遍，顺带指出几个容易踩的下标坑。

先定义数据结构

package main

import "fmt"

const MAXSIZE = 100

type ElementType int

type List struct {
    Data []ElementType  // 顺序存元素
    Last int            // 最后一个元素的下标，空表时为 -1
}

这里 Last 是关键：它既表示长度，也表示最后一个元素的位置，取值是 [-1, MAXSIZE-1]。空表 Last = -1，元素个数就是 Last + 1。

建表

func MakeEmpty() *List {
    return &List{
        Data: make([]ElementType, MAXSIZE),
        Last: -1,
    }
}

切片一次性 make 出 100 个位置，逻辑上只用前 Last+1 个。空间固定，超出就得拒绝插入。

查找

func Find(x ElementType, PtrL *List) int {
    i := 0
    for i <= PtrL.Last && PtrL.Data[i] != x {
        i++
    }
    if i > PtrL.Last {
        return -1
    }
    return i + 1
}

这里有个新旧约定混用的细节值得注意：循环里用的是 Go 惯用的 0 基于下标，返回时却 return i + 1 变成 1 基于序号，找不到返回 -1。而下面 FindKth 的写法又是另一套：

func FindKth(K int, PtrL List) ElementType {
    if K < 1 || K > PtrL.Last+1 {
        return -1
    }
    return PtrL.Data[K+1]
}

两处下标基准不一致，是这套代码里最危险的地方。实际使用时必须统一——要么全 0 基于（返回下标、访问 Data[K]），要么全 1 基于（访问 Data[K-1]）。调用时搞混就会读错位置甚至越界。写工具函数时把基准写在函数名或注释里，能省掉大量调试时间。

插入

func Insert(x ElementType, i int, PtrL *List) {
    if PtrL.Last == MAXSIZE-1 {           // 满了
        fmt.Println("Data Full")
        return
    }
    if i < 1 || i > PtrL.Last+2 {         // 位置非法
        fmt.Println("Position abnormal")
        return
    }
    for j := PtrL.Last; j >= i-1; j-- {
        PtrL.Data[j+1] = PtrL.Data[j]      // 整体后移
    }
    PtrL.Data[i-1] = x                     // 填空
    PtrL.Last++
}

顺序存储插入的代价就在这行双重循环:先把 i 及其后元素整体右移一格，再写入，然后 Last 加一。表越大、插在越靠前的位置，搬得越多。

删除

func Delete(i int, PtrL *List) {
    if i < 1 || i > PtrL.Last+1 {
        fmt.Println("Not Find Element")
        return
    }
    for j := i; j <= PtrL.Last; j++ {
        PtrL.Data[j-1] = PtrL.Data[j]      // 整体前移
    }
    PtrL.Last--
}

删除是把 i 之后的元素往前搬一格，Last 减一。注意搬完把最后一个位置留了重复值，逻辑上被 Last 屏蔽掉了，但如果你想彻底清干净可以加一句置零。

改值与长度

func Alter(x ElementType, i int, PtrL *List) {
    if i < 1 || i > PtrL.Last+1 {
        fmt.Println("No find element:", i)
        return
    }
    PtrL.Data[i] = x
}

func Length(PtrL List) int {
    return PtrL.Last + 1
}

顺带一提，Alter 里 PtrL.Data[i] 这个下标和前面的 1 基于约定又是冲突的（越界风险）。这正是刚才说的基准问题，改的时候统一一下就好。

遍历

func PrintL(PtrL *List) {
    for i := 0; i <= PtrL.Last; i++ {
        fmt.Printf(" %d", PtrL.Data[i])
    }
    fmt.Println()
}

遍历以 Last 为界，不用管 MAXSIZE 那 100 个空位——这是 Last 存在的重要意义。

一个完整测试

func main() {
    L := MakeEmpty()
    for i := 1; i <= 6; i++ {
        Insert(ElementType(i), i, L)
    }
    PrintL(L)      //  1 2 3 4 5 6
    Delete(2, L)
    PrintL(L)      //  1 3 4 5 6
    Alter(2, L)
    PrintL(L)
    x := Find(2, L)
    fmt.Println("result:", x)
    length := Length(*L)
    fmt.Println("len:", length)
}

先建表，删掉第 2 个，再改第 2 个，最后查长度。把输出和预期对上，整套操作就算摸清了。

复杂度记一下

操作	顺序存储	说明
访问（给定下标）	O(1)	连续内存，随机访问
插入	O(n)	要搬动后半段
删除	O(n)	要搬动后半段
查找（未排序）	O(n)	线性扫描

对比链式存储（插入删除 O(1) 但要找位置 O(n)），顺序存储赢在访问快、缓存友好、不需要节点指针。没有绝对优劣，看你的操作分布。

qidao123.com企服评测-应用市场 编辑提示

本文由齐道123 IT 运维社区整理，讲解顺序存储线性表的 Go 实现，并指出原著代码中 0 基于 / 1 基于下标混用的风险点。示例代码仅作数据结构学习用途，实际项目请使用 Go 标准库的 container/list 或切片原生能力；涉及生产代码请补充边界用例测试，尤其是空表、满表与越界分支。