C++线性表中的顺序表的9种基本运算的算法的程序实现

在C++中，顺序表（也称为数组列表）是一种简单的数据结构，它将元素存储在一个连续的内存块中。以下是九种常见操作的简单实现：

1. 插入元素 (插入首部)

void insertAtHead(int value) {
    if (_size == _capacity) resize(2 * _size); // 如果满，则扩容
    _data[0] = value; // 将新值放在第一个位置
    ++_size;
}

2. 删除元素 (删除首部)

void removeHead() {
    if (_size > 0) {
        _data[0] = _data[_size - 1]; // 将最后一个元素替换到第一个
        --_size;
        if (_size == _capacity / 4 && _capacity != 1) resize(_capacity / 2); // 缩容条件
    }
}

3. 查找元素

int search(const int& target) const {
    for (int i = 0; i < _size; ++i) {
        if (_data[i] == target) return i;
    }
    return -1; // 未找到目标，返回-1
}

4. 遍历所有元素

void traverse() const {
    for (int i = 0; i < _size; ++i) {
        std::cout << _data[i] << " ";
    }
    std::cout << std::endl;
}

5. 添加元素 (在指定索引插入)

void insertAtPosition(int position, int value) {
    if (position >= 0 && position <= _size) {
        if (_size + 1 == _capacity) resize(_capacity * 2); // 扩容
        for (int i = _size; i > position; --i) {
            _data[i] = _data[i - 1];
        }
        _data[position] = value;
        ++_size;
    } else {
        throw std::out_of_range("Index out of range");
    }
}

6. 删除元素 (按索引删除)

void removeAtPosition(int position) {
    if (position >= 0 && position < _size) {
        memmove(&_data[position], &_data[position + 1], sizeof(_data[_size - 1]) * (_size - position - 1)); // 移动元素
        --_size;
        if (_size == _capacity / 4 && _capacity != 1) resize(_capacity / 2); // 缩容
    } else {
        throw std::out_of_range("Index out of range");
    }
}

7. 获取元素大小

int size() const { return _size; }

8. 获取容量

int capacity() const { return _capacity; }

9. 判断是否为空

bool isEmpty() const { return _size == 0; }