当前位置：首页 > 其他 > 手搓顺序表类代码注释与详解：从零实现动态数组（新手教程）

手搓顺序表类代码注释与详解：从零实现动态数组（新手教程）

1个月前 (06-08)

一、简介和特点

顺序表（Sequential List）是数据结构中基础的一种线性表，其特点是将数据元素存储在连续的内存空间中。通过数组实现，支持随机访问（即通过索引直接访问元素），适用于频繁随机读取的场景。本代码实现了一个简易的顺序表类，包含动态扩容、插入、删除、修改和查找功能，适合新手理解底层原理。

二、与其他数据结构的优点对比

1. 对比链表：

顺序表在内存中连续存储，缓存利用率高，随机访问速度快（O(1)）。

链表需要指针连接节点，访问元素需遍历（O(n)），但插入删除操作更灵活。

2. 适用场景：

当数据量固定或较少变动，且需要频繁随机访问时，顺序表效率更高。

三、步骤解析

1. 定义类与成员变量：

使用 class list 声明类，包含 int* a（指向动态数组的指针）、size（数组容量）、num（当前元素个数）。

2. 构造函数初始化：

传入 listsize 参数创建数组，分配 size * sizeof(int) 空间，num 初始化为0。

3. 析构函数释放内存：

使用 delete[] a 释放数组，避免内存泄漏。

4. 核心操作实现：

插入（ins(idx, data)）：

a. 检查索引是否合法及容量是否已满，若满则扩容至原容量2倍。

b. 将插入位置后的元素后移，腾出空间。

c. 插入数据，更新元素个数。

删除（del(idx)）：

将删除位置后的元素前移覆盖，减少元素个数。

修改（rev(idx, data)）：

直接通过索引赋值，因顺序表支持随机访问。

查找（sel(idx)）：

返回指定索引的元素值。

四、代码及注释

#include <iostream>
using namespace std;

class list {
private:
    int* a;        // 指向动态分配的整数数组
    int size;      // 数组当前容量
public:
    int num = 0;   // 当前元素个数

    // 构造函数：初始化数组
    list(int listsize) {
        size = listsize;         // 设置容量
        a = new int[size];       // 分配内存
    }

    // 析构函数：释放内存
    ~list() {
        delete[] a;              // 释放数组空间
    }

    // 插入元素（索引idx处插入data）
    void ins(int idx, int data) {
        // 检查索引是否越界或容量是否满
        while (idx >= size || num == size) {
            // 扩容：新建2倍容量数组，复制原数据，释放旧数组
            int* tmp = new int[size * 2];
            memset(tmp, 0, size * 2);   // 初始化新数组为0（可选）
            for (int i = 0; i < size; i++) {
                tmp[i] = a[i];
            }
            delete[] a;
            a = tmp;
            size *= 2;              // 更新容量
        }
        // 后移元素腾出位置
        for (int i = num - 1; i > idx; i--) {
            a[i - 1] = a[i];
        }
        a[idx] = data;              // 插入数据
        num++;                      // 元素个数+1
    }

    // 删除索引idx处的元素
    void del(int idx) {
        // 将后续元素前移覆盖
        for (int i = idx + 1; i < num; i++) {
            a[i - 1] = a[i];
        }
        num--;                      // 元素个数-1
    }

    // 修改索引idx处的元素为data
    void rev(int idx, int data) {
        a[idx] = data;
    }

    // 查找并返回索引idx处的元素
    int sel(int idx) {
        return a[idx];
    }
};