当前位置： 首页 > article >正文

C++ 实现封装的顺序表：顺序表的操作与实践

article 2025/2/10 8:26:45

C++ 实现封装的顺序表：顺序表的操作与实践

在程序设计中，顺序表是一种常见的线性数据结构，通常用于存储具有固定顺序的元素。与链表不同，顺序表中的元素是连续存储的，因此访问速度较快，但插入和删除操作的效率可能较低。本文将详细介绍如何用 C++ 语言实现一个封装的顺序表类，深入探讨顺序表的核心操作，并展示完整的代码示例。

一、顺序表的基本概念

顺序表是一种由一组数据元素构成的线性结构，元素在内存中是连续存储的。每个元素都可以通过索引快速访问。顺序表的插入和删除操作通常需要移动元素，尤其是在数组的中间部分。

在 C++ 中，我们通过类的封装特性来实现顺序表，利用动态数组来存储数据，保证数据的灵活性和高效性。顺序表常用于需要快速随机访问元素的应用场景。

二、顺序表类的设计

我们将通过一个简单的 C++ 类来实现顺序表，该类包含基本的顺序表操作，如插入、删除、查找、修改等。

1. 顺序表类的成员变量

我们定义了一个 SList 类，包含以下成员变量：

  • a：动态数组，用于存储顺序表中的元素。
  • size：当前顺序表中的元素个数。
  • capacity：数组的容量。
2. 构造函数和析构函数

顺序表类的构造函数负责初始化成员变量，析构函数负责释放动态分配的内存。

class SList {
private:
    static const int N = 10;  // 初始容量
    int* a;  // 动态数组
    int size;  // 当前元素个数
    int capacity;  // 数组的容量

    // 动态扩展数组
    void expand() {
        capacity *= 2;  // 容量翻倍
        int* new_array = new int[capacity];  // 创建一个新的更大的数组
        copy(a, a + size, new_array);  // 复制原数组到新数组

        delete[] a;  // 删除旧数组
        a = new_array;  // 指向新数组
    }

public:
    // 构造函数
    SList() : size(0), capacity(N), a(new int[capacity]) {}

    // 析构函数
    ~SList() {
        delete[] a;  // 释放动态数组内存
    }

    // 尾插操作
    void PushBack(int x) {
        if (size == capacity) {
            expand();  // 如果数组已满，扩展数组
        }
        a[size++] = x;  // 将元素插入尾部
    }

    // 头插操作
    void PushFront(int x) {
        if (size == capacity) {
            expand();  // 如果数组已满，扩展数组
        }
        // 将所有元素向后移动一位
        for (int i = size; i > 0; i--) {
            a[i] = a[i - 1];
        }
        a[0] = x;  // 插入元素到头部
        size++;
    }

    // 指定位置插入元素
    void Insert(int pos, int x) {
        if (pos < 0 || pos > size) {
            cout << "位置无效！" << endl;
            return;
        }

        if (size == capacity) {
            expand();  // 如果数组已满，扩展数组
        }

        // 将从 pos 位置开始的元素向后移动一位
        for (int i = size; i > pos; i--) {
            a[i] = a[i - 1];
        }
        a[pos] = x;  // 插入元素
        size++;
    }

    // 尾删操作
    void PopBack() {
        if (size > 0) {
            size--;  // 删除尾部元素
        } else {
            cout << "顺序表为空，无法进行删除操作！" << endl;
        }
    }

    // 头删操作
    void PopFront() {
        if (size > 0) {
            // 将所有元素向前移动一位
            for (int i = 0; i < size - 1; i++) {
                a[i] = a[i + 1];
            }
            size--;
        } else {
            cout << "顺序表为空，无法进行删除操作！" << endl;
        }
    }

    // 打印顺序表
    void PrintList() {
        for (int i = 0; i < size; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }

    // 按值查找元素
    int find(int x) {
        for (int i = 0; i < size; i++) {
            if (a[i] == x) {
                return i;  // 返回元素的索引
            }
        }
        return -1;  // 未找到
    }

    // 按位置查找元素
    int at(int pos) {
        if (pos >= 0 && pos < size) {
            return a[pos];  // 返回指定位置的元素
        }
        return -1;  // 无效位置
    }

    // 修改指定位置的元素
    void change(int pos, int x) {
        if (pos >= 0 && pos < size) {
            a[pos] = x;  // 修改元素
        } else {
            cout << "位置无效, 修改失败" << endl;
        }
    }

    // 获取顺序表的大小
    int GetSize() const {
        return size;
    }
};
三、顺序表的操作实现
  • PushBack: 在顺序表的尾部插入新元素。
  • PushFront: 在顺序表的头部插入新元素。
  • Insert: 在指定位置插入新元素。
  • PopBack: 删除顺序表的尾元素。
  • PopFront: 删除顺序表的头元素。
  • PrintList: 打印顺序表中的所有元素。
  • find: 根据值查找元素，返回其索引。
  • at: 根据位置查找元素，返回该位置的元素。
  • change: 修改指定位置的元素。
四、测试与演示

下面的 main 函数展示了如何使用上述顺序表类实现基本操作：

int main() {
    SList sl;
    sl.PushBack(1);
    sl.PushBack(2);
    sl.PushBack(3);
    sl.PushBack(4);
    sl.PushBack(5);
    sl.PrintList();

    sl.PopFront();
    sl.PopBack();
    sl.PushFront(9);
    sl.PrintList();
    sl.Insert(1, 1);
    sl.PrintList();

    sl.PopFront();
    sl.PopBack();
    sl.PrintList();

    sl.change(0, 33);
    sl.PrintList();
    cout << sl.GetSize() << endl;
    return 0;
}
五、顺序表操作的复杂度
  1. PushBack 和 PopBack：在最坏情况下时间复杂度为 O(1)，但在数组扩展时，复杂度为 O(n)。
  2. PushFront 和 PopFront：这两个操作的时间复杂度为 O(n)，因为需要移动元素。
  3. Insert：时间复杂度为 O(n)，因为需要移动部分元素。
  4. PrintList：打印顺序表的时间复杂度为 O(n)，需要遍历所有元素。
六、完整代码
#include <iostream>
using namespace std;
class SList
{
private:
    static const int N = 10;//初始容量
    int* a;  // 动态数组
    int size;  // 当前元素个数
    int capacity;  // 数组的容量
    // 动态扩展数组
    void expand() {
        capacity *= 2;  // 容量翻倍
        int* new_array = new int[capacity];  // 创建一个新的更大的数组
        copy(a, a + size, new_array);

        delete[] a;
        a = new_array;
    }

public:
    SList() : size(0), capacity(N), a(new int[capacity]) {
        // 构造函数体可以为空，所有初始化已在初始化列表中完成
    }


    ~SList() {
        delete[] a;  // 释放动态数组内存
    }

    void PushBack(int x)  // 尾插
    {
        if (size == capacity) {
            expand();  // 如果数组已满，扩展数组
        }
        a[size++] = x;  // 将元素插入尾部
    }

    void PushFront(int x)  // 头插
    {
        if (size == capacity) {
            expand();  // 如果数组已满，扩展数组
        }
        // 将所有元素向后移动一位
        for (int i = size; i > 0; i--) {
            a[i] = a[i - 1];
        }
        a[0] = x;  // 插入元素到头部
        size++;
    }

    void Insert(int pos, int x)  // 指定位置插入元素
    {
        if (pos < 0 || pos > size) {
            cout << "位置无效！" << endl;
            return;
        }

        if (size == capacity) {
            expand();  // 如果数组已满，扩展数组
        }

        // 将从 pos 位置开始的元素向后移动一位
        for (int i = size; i > pos; i--) {
            a[i] = a[i - 1];
        }
        a[pos] = x;  // 插入元素
        size++;
    }

    void PopBack()  // 尾删
    {
        if (size > 0) {
            size--;
        } else {
            cout << "顺序表为空，无法进行删除操作！" << endl;
        }
    }

    void PopFront()  // 头删
    {
        if (size > 0) {
            // 将所有元素向前移动一位
            for (int i = 0; i < size - 1; i++) {
                a[i] = a[i + 1];
            }
            size--;
        } else {
            cout << "顺序表为空，无法进行删除操作！" << endl;
        }
    }

    void PrintList()  // 打印顺序表
    {
        for (int i = 0; i < size; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }

    int find(int x)  // 按值查找
    {
        for (int i = 0; i < size; i++) {
            if (a[i] == x) {
                return i;
            }
        }
        return -1;
    }

    int at(int pos)  // 按位查找
    {
        if (pos >= 0 && pos < size) {
            return a[pos];
        }
        return -1;
    }

    void change(int pos, int x)  // 修改
    {
        if (pos >= 0 && pos < size) {
            a[pos] = x;
        } else {
            cout << "位置无效, 修改失败" << endl;
        }
    }

    int GetSize() const  // 获取顺序表的大小
    {
        return size;
    }
};

int main()
{
    SList sl;
    sl.PushBack(1);
    sl.PushBack(2);
    sl.PushBack(3);
    sl.PushBack(4);
    sl.PushBack(5);
    sl.PrintList();

    sl.PopFront();
    sl.PopBack();
    sl.PushFront(9);
    sl.PrintList();
    sl.Insert(1, 1);
    sl.PrintList();

    sl.PopFront();
    sl.PopBack();
    sl.PrintList();

    sl.change(0, 33);
    sl.PrintList();
    cout << sl.GetSize() << endl;
    return 0;
}
七、总结

通过面向对象的方式实现顺序表，我们能够更加方便和安全地进行顺序表操作。封装了内存管理、扩展策略以及顺序表操作函数的类，使得顺序表操作更加直观并且易于维护。在实际开发中，顺序表结构广泛应用于各种需要快速随机访问的场景，掌握顺序表的使用将帮助我们高效地处理许多数据管理问题。

希望本篇博客能够帮助你更好地理解和使用 C++ 实现的顺序表。如果你有任何问题，欢迎留言讨论！在这里插入图片描述


http://www.kler.cn/a/539011.html

相关文章：

  • Qt：常用控件
  • 利用UNIAPP实现短视频上下滑动播放功能
  • 开放式TCP/IP通信
  • 解决bad SQL grammar []； nested exception is java.sql.SQLSyntaxErrorException
  • PAT乙级( 1009 说反话 1010 一元多项式求导)C语言版本超详细解析
  • 人工智能入门 数学基础 线性代数 笔记
  • 浏览器的缓存方式几种
  • 基于Java的在线购物系统的设计与实现
  • 【hive】记一次hiveserver内存溢出排查，线程池未正确关闭导致
  • C++ 中信号转异常机制：在磁盘 I/O 内存映射场景下的应用与解析
  • 49-拓展（1）
  • Docker 部署 verdaccio 搭建 npm 私服
  • Prompt逆向工程:如何“骗“大模型吐露其Prompt?
  • 从零开始人工智能Matlab案例-模拟退火算法
  • 0209作业
  • ollama部署教程
  • Logo语言的测试开发
  • Rust语言的安全开发
  • 硬核技术：小程序能够调用手机的哪些传感器
  • LeetCode热题100- 合并区间【JavaScript讲解】
  • Ubuntu如何开启VNC远程桌面连接
  • Vllm进行Qwen2-vl部署（包含单卡多卡部署及爬虫请求）
  • 解锁国内主流前端与后端框架
  • Java数据结构 | TreeMap 和 TreeSet
  • GPU、CUDA 和 cuDNN 学习研究【笔记】
  • iOS 自动翻滚广告条（榜单条）实现方案