C++實現(xiàn)封裝的順序表的操作與實踐
更新時間：2025年02月10日 09:24:41 作者：平凡程序猿~
在程序設(shè)計中,順序表是一種常見的線性數(shù)據(jù)結(jié)構(gòu),通常用于存儲具有固定順序的元素,與鏈表不同,順序表中的元素是連續(xù)存儲的,因此訪問速度較快,但插入和刪除操作的效率可能較低,本文將詳細介紹如何用 C++ 語言實現(xiàn)一個封裝的順序表類,深入探討順序表的核心操作
一、順序表的基本概念
順序表是一種由一組數(shù)據(jù)元素構(gòu)成的線性結(jié)構(gòu)，元素在內(nèi)存中是連續(xù)存儲的。每個元素都可以通過索引快速訪問。順序表的插入和刪除操作通常需要移動元素，尤其是在數(shù)組的中間部分。
在 C++ 中，我們通過類的封裝特性來實現(xiàn)順序表，利用動態(tài)數(shù)組來存儲數(shù)據(jù)，保證數(shù)據(jù)的靈活性和高效性。順序表常用于需要快速隨機訪問元素的應(yīng)用場景。
二、順序表類的設(shè)計
我們將通過一個簡單的 C++ 類來實現(xiàn)順序表，該類包含基本的順序表操作，如插入、刪除、查找、修改等。
1. 順序表類的成員變量
我們定義了一個 SList 類，包含以下成員變量：
a：動態(tài)數(shù)組，用于存儲順序表中的元素。size：當前順序表中的元素個數(shù)。capacity：數(shù)組的容量。
2. 構(gòu)造函數(shù)和析構(gòu)函數(shù)
順序表類的構(gòu)造函數(shù)負責初始化成員變量，析構(gòu)函數(shù)負責釋放動態(tài)分配的內(nèi)存。
class SList {
private:
static const int N = 10; // 初始容量
int* a; // 動態(tài)數(shù)組
int size; // 當前元素個數(shù)
int capacity; // 數(shù)組的容量
// 動態(tài)擴展數(shù)組
void expand() {
capacity *= 2; // 容量翻倍
int* new_array = new int[capacity]; // 創(chuàng)建一個新的更大的數(shù)組
copy(a, a + size, new_array); // 復制原數(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; // 釋放動態(tài)數(shù)組內(nèi)存
}
// 尾插操作
void PushBack(int x) {
if (size == capacity) {
expand(); // 如果數(shù)組已滿，擴展數(shù)組
}
a[size++] = x; // 將元素插入尾部
}
// 頭插操作
void PushFront(int x) {
if (size == capacity) {
expand(); // 如果數(shù)組已滿，擴展數(shù)組
}
// 將所有元素向后移動一位
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(); // 如果數(shù)組已滿，擴展數(shù)組
}
// 將從 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;
}
};
三、順序表的操作實現(xiàn)
- PushBack: 在順序表的尾部插入新元素。
- PushFront: 在順序表的頭部插入新元素。
- Insert: 在指定位置插入新元素。
- PopBack: 刪除順序表的尾元素。
- PopFront: 刪除順序表的頭元素。
- PrintList: 打印順序表中的所有元素。
- find: 根據(jù)值查找元素，返回其索引。
- at: 根據(jù)位置查找元素，返回該位置的元素。
- change: 修改指定位置的元素。
四、測試與演示
下面的 main 函數(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;
}
五、順序表操作的復雜度
- PushBack 和 PopBack：在最壞情況下時間復雜度為 O(1)，但在數(shù)組擴展時，復雜度為 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; // 動態(tài)數(shù)組
int size; // 當前元素個數(shù)
int capacity; // 數(shù)組的容量
// 動態(tài)擴展數(shù)組
void expand() {
capacity *= 2; // 容量翻倍
int* new_array = new int[capacity]; // 創(chuàng)建一個新的更大的數(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; // 釋放動態(tài)數(shù)組內(nèi)存
}
void PushBack(int x) // 尾插
{
if (size == capacity) {
expand(); // 如果數(shù)組已滿，擴展數(shù)組
}
a[size++] = x; // 將元素插入尾部
}
void PushFront(int x) // 頭插
{
if (size == capacity) {
expand(); // 如果數(shù)組已滿，擴展數(shù)組
}
// 將所有元素向后移動一位
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(); // 如果數(shù)組已滿，擴展數(shù)組
}
// 將從 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;
}
七、總結(jié)
通過面向?qū)ο蟮姆绞綄崿F(xiàn)順序表，我們能夠更加方便和安全地進行順序表操作。封裝了內(nèi)存管理、擴展策略以及順序表操作函數(shù)的類，使得順序表操作更加直觀并且易于維護。在實際開發(fā)中，順序表結(jié)構(gòu)廣泛應(yīng)用于各種需要快速隨機訪問的場景，掌握順序表的使用將幫助我們高效地處理許多數(shù)據(jù)管理問題。
到此這篇關(guān)于C++實現(xiàn)封裝的順序表的操作與實踐的文章就介紹到這了,更多相關(guān)C++封裝的順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細介紹了C語言實現(xiàn)電話簿管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
這篇文章主要為大家詳細介紹了C語言實現(xiàn)電子秒表，毫秒級秒表，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要為大家介紹了c語言習題之逆序字符串，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
C++中的包裝器是一種結(jié)構(gòu)型設(shè)計模式,用于包裝已有對象以轉(zhuǎn)換接口或增強功能,下面就來詳細的介紹一下如何使用,具有一定的參考價值,感興趣的可以了解一下2026-02-02
這篇文章主要為大家詳細介紹了C++構(gòu)造函數(shù)，深度學習C++構(gòu)造函數(shù)，感興趣的小伙伴們可以參考一下2016-08-08
這篇文章主要介紹了C語言中如何實現(xiàn)單鏈表刪除指定結(jié)點，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要介紹了c++代碼調(diào)試方式的幾點建議，幫助大家更好的理解和學習c++，感興趣的朋友可以了解下2020-08-08
這篇文章主要介紹了C++定時器實現(xiàn)和時間輪介紹，定時器可以由很多種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，比如最小堆、紅黑樹、跳表、甚至數(shù)組都可以，其本質(zhì)都是拿到最小時間的任務(wù)，然后取出該任務(wù)并執(zhí)行，更多相關(guān)內(nèi)容介紹，需要的小伙伴可以參考一下2022-09-09
對于C語言中的while與do-while，相信很多都再熟悉不過了，最近在工作中就用到了，所以想著總結(jié)一下，方便自己或者有需要的朋友們參考借鑒，文中通過示例代碼介紹的很詳細，感興趣的朋友們下面來一起學習學習吧。2016-10-10
std::functional是C++標準庫中一個非常強大的工具,它提供了一種類型擦除機制,讓你能夠存儲、傳遞和調(diào)用任何可調(diào)用對象,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2026-02-02