Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/2.顺序表.md

2. 顺序表

概念

顺序表（Sequential List）是线性表的一种顺序存储实现：用一组地址连续的存储单元依次存放数据元素。逻辑上相邻的元素在物理位置上也是相邻的。

• 逻辑结构：线性结构，每个元素（除第一个外）有且仅有一个直接前驱，每个元素（除最后一个外）有且仅有一个直接后继。
• 存储结构：顺序存储。数组下标 i 与元素一一对应，由起始地址 base 可得任意元素地址：loc(i) = base + i * sizeof(元素)，因此支持随机存取（O(1) 找到第 i 个元素）。
• 特点：
  • 优点：随机存取快；存储密度高（无指针额外开销）；实现简单。
  • 缺点：插入/删除需要移动大量元素（平均移动 n/2 个）；表长固定（动态扩容也需要整体搬移）；需要大片连续内存。
• 适用场景：表长基本不变、按位置频繁访问、很少做插入删除的场景。

核心操作

操作	说明
初始化	分配存储空间，表长置 0
判空 / 判满	判断表长是否为 0 / 是否等于容量
按位查找	取第 i 个位置上的元素（O(1)）
按值查找	从头扫描，返回第一个值为 x 的元素位置
按位插入	在第 i 个位置插入元素 x，其后的元素后移
按值插入	在第一个值为 x 的元素之后插入（演示用）
删除	删除第 i 个位置的元素，其后的元素前移
遍历打印	按顺序输出所有元素

复杂度分析

操作	时间复杂度	空间复杂度	原因
初始化	O(1)	O(n)	一次性分配 n 个单元
按位查找	O(1)	O(1)	地址可由公式直接计算，随机存取
按值查找	O(n)	O(1)	最坏需要扫描整个表
按位插入	O(n)	O(1)	最坏/平均需移动 n/2 个元素
按位删除	O(n)	O(1)	最坏/平均需移动 (n-1)/2 个元素
遍历打印	O(n)	O(1)	顺序扫描一遍
判空 / 判满	O(1)	O(1)	只比较表长与容量

插入/删除的平均移动次数约为 n/2，所以是 O(n)；顺序表唯一的 O(1) 查找优势来自随机存取特性。

语言实现

C

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];  // 静态数组存储
    int length;         // 当前长度
} SeqList;

// 初始化：表长置 0
void initList(SeqList *L) {
    L->length = 0;
}

// 判空
int isEmpty(SeqList *L) {
    return L->length == 0;
}

// 判满
int isFull(SeqList *L) {
    return L->length == MAXSIZE;
}

// 按位查找：返回第 i 个元素 (i 从 1 开始)，失败返回 -1 并置 ok=0
int getElem(SeqList *L, int i, int *ok) {
    if (i < 1 || i > L->length) {
        *ok = 0;
        return -1;
    }
    *ok = 1;
    return L->data[i - 1];
}

// 按值查找：返回第一个值为 x 的位置(1起)，找不到返回 0
int locateElem(SeqList *L, int x) {
    for (int i = 0; i < L->length; i++)
        if (L->data[i] == x)
            return i + 1;
    return 0;
}

// 按位插入：在第 i 个位置插入 x
int insertList(SeqList *L, int i, int x) {
    if (isFull(L))          return 0;  // 表满
    if (i < 1 || i > L->length + 1) return 0;  // 位置非法
    for (int j = L->length; j >= i; j--)
        L->data[j] = L->data[j - 1];   // 后移
    L->data[i - 1] = x;
    L->length++;
    return 1;
}

// 按值插入：在第一个值为 x 的元素之后插入 y
int insertAfter(SeqList *L, int x, int y) {
    int pos = locateElem(L, x);
    if (pos == 0) return 0;
    return insertList(L, pos + 1, y);
}

// 按位删除：删除第 i 个元素，用 e 带回
int deleteList(SeqList *L, int i, int *e) {
    if (i < 1 || i > L->length) return 0;
    *e = L->data[i - 1];
    for (int j = i; j < L->length; j++)
        L->data[j - 1] = L->data[j];   // 前移
    L->length--;
    return 1;
}

// 遍历打印
void printList(SeqList *L) {
    if (isEmpty(L)) {
        printf("空表\n");
        return;
    }
    printf("表长=%d: ", L->length);
    for (int i = 0; i < L->length; i++)
        printf("%d ", L->data[i]);
    printf("\n");
}

int main(void) {
    SeqList L;
    initList(&L);
    printf("初始状态: ");
    printList(&L);
    printf("判空=%d\n", isEmpty(&L));

    // 依次在尾部插入 10 20 30
    insertList(&L, 1, 10);
    insertList(&L, 2, 20);
    insertList(&L, 3, 30);
    // 按位插入：在第 2 位插入 15
    insertList(&L, 2, 15);
    // 按值插入：在 20 之后插入 25
    insertAfter(&L, 20, 25);
    printList(&L);

    // 按位查找
    int ok, e;
    e = getElem(&L, 3, &ok);
    printf("第3个元素=%d (ok=%d)\n", e, ok);

    // 按值查找
    printf("25 的位置=%d\n", locateElem(&L, 25));

    // 删除第 2 个元素
    deleteList(&L, 2, &e);
    printf("删除元素=%d\n", e);
    printList(&L);

    printf("判满=%d\n", isFull(&L));
    return 0;
}

C++

#include <iostream>
#include <vector>
using namespace std;

// 用 vector 封装动态顺序表
class SeqList {
private:
    vector<int> data;

public:
    // 初始化
    SeqList() = default;

    bool isEmpty() const { return data.empty(); }

    size_t length() const { return data.size(); }

    // 按位查找：返回第 i 个元素 (i 从 1 开始)
    bool getElem(size_t i, int &out) const {
        if (i < 1 || i > data.size()) return false;
        out = data[i - 1];
        return true;
    }

    // 按值查找：返回第一个值为 x 的位置(1起)，找不到返回 0
    size_t locateElem(int x) const {
        for (size_t i = 0; i < data.size(); i++)
            if (data[i] == x) return i + 1;
        return 0;
    }

    // 按位插入
    bool insertList(size_t i, int x) {
        if (i < 1 || i > data.size() + 1) return false;
        data.insert(data.begin() + (i - 1), x);
        return true;
    }

    // 按值插入：在第一个值为 x 的元素之后插入 y
    bool insertAfter(int x, int y) {
        size_t pos = locateElem(x);
        if (pos == 0) return false;
        return insertList(pos + 1, y);
    }

    // 按位删除
    bool deleteList(size_t i, int &e) {
        if (i < 1 || i > data.size()) return false;
        e = data[i - 1];
        data.erase(data.begin() + (i - 1));
        return true;
    }

    // 遍历打印
    void print() const {
        cout << "表长=" << data.size() << ": ";
        for (int v : data) cout << v << " ";
        cout << endl;
    }
};

int main() {
    SeqList L;
    cout << "初始状态: ";
    L.print();
    cout << "判空=" << L.isEmpty() << endl;

    L.insertList(1, 10);
    L.insertList(2, 20);
    L.insertList(3, 30);
    L.insertList(2, 15);      // 按位插入
    L.insertAfter(20, 25);    // 按值插入
    L.print();

    int e;
    if (L.getElem(3, e))
        cout << "第3个元素=" << e << endl;
    cout << "25 的位置=" << L.locateElem(25) << endl;

    if (L.deleteList(2, e))
        cout << "删除元素=" << e << endl;
    L.print();
    return 0;
}

Java

import java.util.ArrayList;

public class SeqListDemo {
    // 用 ArrayList 封装动态顺序表
    static class SeqList {
        private ArrayList<Integer> data;

        // 初始化
        SeqList() {
            data = new ArrayList<>();
        }

        boolean isEmpty() {
            return data.isEmpty();
        }

        int length() {
            return data.size();
        }

        // 按位查找：返回第 i 个元素 (i 从 1 开始)，越界返回 null
        Integer getElem(int i) {
            if (i < 1 || i > data.size()) return null;
            return data.get(i - 1);
        }

        // 按值查找：返回第一个值为 x 的位置(1起)，找不到返回 0
        int locateElem(int x) {
            for (int i = 0; i < data.size(); i++)
                if (data.get(i) == x) return i + 1;
            return 0;
        }

        // 按位插入
        boolean insertList(int i, int x) {
            if (i < 1 || i > data.size() + 1) return false;
            data.add(i - 1, x);
            return true;
        }

        // 按值插入：在第一个值为 x 的元素之后插入 y
        boolean insertAfter(int x, int y) {
            int pos = locateElem(x);
            if (pos == 0) return false;
            return insertList(pos + 1, y);
        }

        // 按位删除，返回被删元素；失败返回 null
        Integer deleteList(int i) {
            if (i < 1 || i > data.size()) return null;
            return data.remove(i - 1);
        }

        // 遍历打印
        void print() {
            System.out.print("表长=" + data.size() + ": ");
            for (int v : data) System.out.print(v + " ");
            System.out.println();
        }
    }

    public static void main(String[] args) {
        SeqList L = new SeqList();
        System.out.print("初始状态: ");
        L.print();
        System.out.println("判空=" + L.isEmpty());

        L.insertList(1, 10);
        L.insertList(2, 20);
        L.insertList(3, 30);
        L.insertList(2, 15);      // 按位插入
        L.insertAfter(20, 25);    // 按值插入
        L.print();

        Integer e = L.getElem(3);
        System.out.println("第3个元素=" + e);
        System.out.println("25 的位置=" + L.locateElem(25));

        e = L.deleteList(2);
        System.out.println("删除元素=" + e);
        L.print();
    }
}

Python

class SeqList:
    """动态顺序表（用 Python 列表实现）"""

    def __init__(self):
        # 初始化：空表
        self._data = []

    def is_empty(self) -> bool:
        return len(self._data) == 0

    def length(self) -> int:
        return len(self._data)

    def get_elem(self, i: int):
        """按位查找：返回第 i 个元素（i 从 1 开始），越界返回 None"""
        if i < 1 or i > len(self._data):
            return None
        return self._data[i - 1]

    def locate_elem(self, x) -> int:
        """按值查找：返回第一个值为 x 的位置（1 起），找不到返回 0"""
        for i, v in enumerate(self._data):
            if v == x:
                return i + 1
        return 0

    def insert_list(self, i: int, x) -> bool:
        """按位插入：在第 i 个位置插入 x"""
        if i < 1 or i > len(self._data) + 1:
            return False
        self._data.insert(i - 1, x)
        return True

    def insert_after(self, x, y) -> bool:
        """按值插入：在第一个值为 x 的元素之后插入 y"""
        pos = self.locate_elem(x)
        if pos == 0:
            return False
        return self.insert_list(pos + 1, y)

    def delete_list(self, i: int):
        """按位删除：删除第 i 个元素并返回之，失败返回 None"""
        if i < 1 or i > len(self._data):
            return None
        return self._data.pop(i - 1)

    def print_list(self):
        print(f"表长={len(self._data)}:", *self._data)


if __name__ == "__main__":
    L = SeqList()
    print("初始状态:", end=" ")
    L.print_list()
    print("判空 =", L.is_empty())

    L.insert_list(1, 10)
    L.insert_list(2, 20)
    L.insert_list(3, 30)
    L.insert_list(2, 15)        # 按位插入
    L.insert_after(20, 25)      # 按值插入
    L.print_list()

    print("第3个元素 =", L.get_elem(3))
    print("25 的位置 =", L.locate_elem(25))

    e = L.delete_list(2)
    print("删除元素 =", e)
    L.print_list()