快捷導(dǎo)航

C++實(shí)現(xiàn)封裝的順序表的操作與實(shí)踐

更新時(shí)間：2025年02月10日 09:24:41 作者：平凡程序猿~

在程序設(shè)計(jì)中,順序表是一種常見(jiàn)的線(xiàn)性數(shù)據(jù)結(jié)構(gòu),通常用于存儲(chǔ)具有固定順序的元素,與鏈表不同,順序表中的元素是連續(xù)存儲(chǔ)的,因此訪(fǎng)問(wèn)速度較快,但插入和刪除操作的效率可能較低,本文將詳細(xì)介紹如何用 C++ 語(yǔ)言實(shí)現(xiàn)一個(gè)封裝的順序表類(lèi),深入探討順序表的核心操作

一、順序表的基本概念

順序表是一種由一組數(shù)據(jù)元素構(gòu)成的線(xiàn)性結(jié)構(gòu)，元素在內(nèi)存中是連續(xù)存儲(chǔ)的。每個(gè)元素都可以通過(guò)索引快速訪(fǎng)問(wèn)。順序表的插入和刪除操作通常需要移動(dòng)元素，尤其是在數(shù)組的中間部分。

在 C++ 中，我們通過(guò)類(lèi)的封裝特性來(lái)實(shí)現(xiàn)順序表，利用動(dòng)態(tài)數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)，保證數(shù)據(jù)的靈活性和高效性。順序表常用于需要快速隨機(jī)訪(fǎng)問(wèn)元素的應(yīng)用場(chǎng)景。

二、順序表類(lèi)的設(shè)計(jì)

我們將通過(guò)一個(gè)簡(jiǎn)單的 C++ 類(lèi)來(lái)實(shí)現(xiàn)順序表，該類(lèi)包含基本的順序表操作，如插入、刪除、查找、修改等。

1. 順序表類(lèi)的成員變量

我們定義了一個(gè) SList 類(lèi)，包含以下成員變量：

a：動(dòng)態(tài)數(shù)組，用于存儲(chǔ)順序表中的元素。
size：當(dāng)前順序表中的元素個(gè)數(shù)。
capacity：數(shù)組的容量。

2. 構(gòu)造函數(shù)和析構(gòu)函數(shù)

順序表類(lèi)的構(gòu)造函數(shù)負(fù)責(zé)初始化成員變量，析構(gòu)函數(shù)負(fù)責(zé)釋放動(dòng)態(tài)分配的內(nèi)存。

class SList {
private:
    static const int N = 10;  // 初始容量
    int* a;  // 動(dòng)態(tài)數(shù)組
    int size;  // 當(dāng)前元素個(gè)數(shù)
    int capacity;  // 數(shù)組的容量

    // 動(dòng)態(tài)擴(kuò)展數(shù)組
    void expand() {
        capacity *= 2;  // 容量翻倍
        int* new_array = new int[capacity];  // 創(chuàng)建一個(gè)新的更大的數(shù)組
        copy(a, a + size, new_array);  // 復(fù)制原數(shù)組到新數(shù)組

        delete[] a;  // 刪除舊數(shù)組
        a = new_array;  // 指向新數(shù)組
    }

public:
    // 構(gòu)造函數(shù)
    SList() : size(0), capacity(N), a(new int[capacity]) {}

    // 析構(gòu)函數(shù)
    ~SList() {
        delete[] a;  // 釋放動(dòng)態(tài)數(shù)組內(nèi)存
    }

    // 尾插操作
    void PushBack(int x) {
        if (size == capacity) {
            expand();  // 如果數(shù)組已滿(mǎn)，擴(kuò)展數(shù)組
        }
        a[size++] = x;  // 將元素插入尾部
    }

    // 頭插操作
    void PushFront(int x) {
        if (size == capacity) {
            expand();  // 如果數(shù)組已滿(mǎn)，擴(kuò)展數(shù)組
        }
        // 將所有元素向后移動(dòng)一位
        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 << "位置無(wú)效！" << endl;
            return;
        }

        if (size == capacity) {
            expand();  // 如果數(shù)組已滿(mǎn)，擴(kuò)展數(shù)組
        }

        // 將從 pos 位置開(kāi)始的元素向后移動(dòng)一位
        for (int i = size; i > pos; i--) {
            a[i] = a[i - 1];
        }
        a[pos] = x;  // 插入元素
        size++;
    }

    // 尾刪操作
    void PopBack() {
        if (size > 0) {
            size--;  // 刪除尾部元素
        } else {
            cout << "順序表為空，無(wú)法進(jìn)行刪除操作！" << endl;
        }
    }

    // 頭刪操作
    void PopFront() {
        if (size > 0) {
            // 將所有元素向前移動(dòng)一位
            for (int i = 0; i < size - 1; i++) {
                a[i] = a[i + 1];
            }
            size--;
        } else {
            cout << "順序表為空，無(wú)法進(jìn)行刪除操作！" << 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;  // 無(wú)效位置
    }

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

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

三、順序表的操作實(shí)現(xiàn)

PushBack: 在順序表的尾部插入新元素。
PushFront: 在順序表的頭部插入新元素。
Insert: 在指定位置插入新元素。
PopBack: 刪除順序表的尾元素。
PopFront: 刪除順序表的頭元素。
PrintList: 打印順序表中的所有元素。
find: 根據(jù)值查找元素，返回其索引。
at: 根據(jù)位置查找元素，返回該位置的元素。
change: 修改指定位置的元素。

四、測(cè)試與演示

下面的 main 函數(shù)展示了如何使用上述順序表類(lèi)實(shí)現(xiàn)基本操作：

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

五、順序表操作的復(fù)雜度

PushBack 和 PopBack：在最壞情況下時(shí)間復(fù)雜度為 O(1)，但在數(shù)組擴(kuò)展時(shí)，復(fù)雜度為 O(n)。
PushFront 和 PopFront：這兩個(gè)操作的時(shí)間復(fù)雜度為 O(n)，因?yàn)樾枰苿?dòng)元素。
Insert：時(shí)間復(fù)雜度為 O(n)，因?yàn)樾枰苿?dòng)部分元素。
PrintList：打印順序表的時(shí)間復(fù)雜度為 O(n)，需要遍歷所有元素。

六、完整代碼

#include <iostream>
using namespace std;
class SList
{
private:
    static const int N = 10;//初始容量
    int* a;  // 動(dòng)態(tài)數(shù)組
    int size;  // 當(dāng)前元素個(gè)數(shù)
    int capacity;  // 數(shù)組的容量
    // 動(dòng)態(tài)擴(kuò)展數(shù)組
    void expand() {
        capacity *= 2;  // 容量翻倍
        int* new_array = new int[capacity];  // 創(chuàng)建一個(gè)新的更大的數(shù)組
        copy(a, a + size, new_array);

        delete[] a;
        a = new_array;
    }

public:
    SList() : size(0), capacity(N), a(new int[capacity]) {
        // 構(gòu)造函數(shù)體可以為空，所有初始化已在初始化列表中完成
    }


    ~SList() {
        delete[] a;  // 釋放動(dòng)態(tài)數(shù)組內(nèi)存
    }

    void PushBack(int x)  // 尾插
    {
        if (size == capacity) {
            expand();  // 如果數(shù)組已滿(mǎn)，擴(kuò)展數(shù)組
        }
        a[size++] = x;  // 將元素插入尾部
    }

    void PushFront(int x)  // 頭插
    {
        if (size == capacity) {
            expand();  // 如果數(shù)組已滿(mǎn)，擴(kuò)展數(shù)組
        }
        // 將所有元素向后移動(dòng)一位
        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 << "位置無(wú)效！" << endl;
            return;
        }

        if (size == capacity) {
            expand();  // 如果數(shù)組已滿(mǎn)，擴(kuò)展數(shù)組
        }

        // 將從 pos 位置開(kāi)始的元素向后移動(dòng)一位
        for (int i = size; i > pos; i--) {
            a[i] = a[i - 1];
        }
        a[pos] = x;  // 插入元素
        size++;
    }

    void PopBack()  // 尾刪
    {
        if (size > 0) {
            size--;
        } else {
            cout << "順序表為空，無(wú)法進(jìn)行刪除操作！" << endl;
        }
    }

    void PopFront()  // 頭刪
    {
        if (size > 0) {
            // 將所有元素向前移動(dòng)一位
            for (int i = 0; i < size - 1; i++) {
                a[i] = a[i + 1];
            }
            size--;
        } else {
            cout << "順序表為空，無(wú)法進(jìn)行刪除操作！" << 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 << "位置無(wú)效, 修改失敗" << 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;
}

七、總結(jié)

通過(guò)面向?qū)ο蟮姆绞綄?shí)現(xiàn)順序表，我們能夠更加方便和安全地進(jìn)行順序表操作。封裝了內(nèi)存管理、擴(kuò)展策略以及順序表操作函數(shù)的類(lèi)，使得順序表操作更加直觀并且易于維護(hù)。在實(shí)際開(kāi)發(fā)中，順序表結(jié)構(gòu)廣泛應(yīng)用于各種需要快速隨機(jī)訪(fǎng)問(wèn)的場(chǎng)景，掌握順序表的使用將幫助我們高效地處理許多數(shù)據(jù)管理問(wèn)題。

到此這篇關(guān)于C++實(shí)現(xiàn)封裝的順序表的操作與實(shí)踐的文章就介紹到這了,更多相關(guān)C++封裝的順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: