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

2025-04-10 14:24 开发作者：平凡程序猿~

一、顺序表的基本概念

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

在 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;
}

五、顺序表操作的复杂度

PushBack 和 PopBack：在最坏情况下时间复杂度为 O(1)，但在数组扩展时，复杂度为 O(n)。
PushFront 和 PopFront：这两个操作的时间复杂度为 O(n)，因为需要移动元素。
Insert：时间复杂度为 O(n)，因为需要移动部分元素。
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.devze.comid 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++封装的顺序表内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！

继续阅读：C++实现封装的顺序表 C++封装顺序表 C++顺序表

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

目录

一、顺序表的基本概念

二、顺序表类的设计

1. 顺序表类的成员变量

2. 构造函数和析构函数

三、顺序表的操作实现

四、测试与演示

五、顺序表操作的复杂度

六、完整代码

七、总结

更多精彩内容

精彩评论

最新开发

Go语言开发实现查询IP信息的MCP服务器

Qt实现XML与JSON数据解析全攻略

手把手教你使用VSCode创建和启动一个C#项目

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

关于MongoDB图片URL存储异常问题以及解决

开发排行榜

springboot后端存储富文本内容的思路与步骤(含图片内容)

PyCharm运行python测试,报错“没有发现测试”/“空套件”的解决

return base64.b64encode(b).decode(

基于C语言实现钻石棋游戏的示例代码

Sublime Text 3解决中文乱码问题（实测可用）