一、顺序表的基本概念
顺序表是一种由一组数据元素构成的线性结构，元素在内存中是连续存储的。每个元素都可以通过索引快速访问。顺序表的插入和删除操作通常需要移动元素，尤其是在数组的中间部分。
在 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;
}
五、顺序表操作的复杂度
- 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 == 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++实现封装的顺序表的操作与实践的文章就介绍到这了,更多相关C++封装的顺序表内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！
来源链接：https://www.jb51.net/program/335463hzw.htm
© 版权声明
本站所有资源来自于网络，仅供学习与参考，请勿用于商业用途，否则产生的一切后果将由您(转载者)自己承担！
如有侵犯您的版权，请及时联系3500663466#qq.com(#换@)，我们将第一时间删除本站数据。
如有侵犯您的版权，请及时联系3500663466#qq.com(#换@)，我们将第一时间删除本站数据。
THE END
暂无评论内容