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

2025-02-10 16:50
文章标签 c++ 实现 实践 封装 操作 顺序

本文主要是介绍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) {
      LxqgkvoYQ  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&nLxqgkvoYQbsp;函数展示了如何使用上述顺序表类实现基本操作：

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 ==javascript capacity) {
            expand();  // 如果数组已满，扩展数组
        }

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

    vohttp://www.chinasem.cnid 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;
}

七、总结

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

到此这篇关于C++实现封装的顺序表的操作与实践的文章就介绍到这了,更多相关C++封装的顺序表内容请搜索China编程(www.chinasem.cn)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程China编程(www.chinasem.cn)！

这篇关于C++实现封装的顺序表的操作与实践的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1153380。

相关文章

关于集合与数组转换实现方法

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》：本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
使用Python实现可恢复式多线程下载器

使用Python实现可恢复式多线程下载器

《使用Python实现可恢复式多线程下载器》在数字时代,大文件下载已成为日常操作,本文将手把手教你用Python打造专业级下载器,实现断点续传,多线程加速,速度限制等功能,感兴趣的小伙伴可以了解下... 目录一、智能续传：从崩溃边缘抢救进度二、多线程加速：榨干网络带宽三、速度控制：做网络的好邻居四、终端交互
阅读更多...
mysql表操作与查询功能详解

mysql表操作与查询功能详解

《mysql表操作与查询功能详解》本文系统讲解MySQL表操作与查询,涵盖创建、修改、复制表语法,基本查询结构及WHERE、GROUPBY等子句,本文结合实例代码给大家介绍的非常详细,感兴趣的朋友跟随... 目录01.表的操作1.1表操作概览1.2创建表1.3修改表1.4复制表02.基本查询操作2.1 SE
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
java实现docker镜像上传到harbor仓库的方式

java实现docker镜像上传到harbor仓库的方式

《java实现docker镜像上传到harbor仓库的方式》：本文主要介绍java实现docker镜像上传到harbor仓库的方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 前 言2. 编写工具类2.1 引入依赖包2.2 使用当前服务器的docker环境推送镜像2.2
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Java easyExcel实现导入多sheet的Excel

Java easyExcel实现导入多sheet的Excel

《JavaeasyExcel实现导入多sheet的Excel》这篇文章主要为大家详细介绍了如何使用JavaeasyExcel实现导入多sheet的Excel,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录1.官网2.Excel样式3.代码1.官网easyExcel官网2.Excel样式3.代码
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...
python实现对数据公钥加密与私钥解密

python实现对数据公钥加密与私钥解密

《python实现对数据公钥加密与私钥解密》这篇文章主要为大家详细介绍了如何使用python实现对数据公钥加密与私钥解密,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录公钥私钥的生成使用公钥加密使用私钥解密公钥私钥的生成这一部分，使用python生成公钥与私钥，然后保存在两个文
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2