极客笔记C++ 中的插入操作
在编程中，插入操作是一种常见的操作，特别是在处理数据结构时经常会用到。在C++语言中，有多种方式可以进行插入操作，比如对数组、向量、链表等数据结构的插入操作。本文将详细探讨C++中的插入操作，包括数组、向量和链表的插入操作，以及各种数据结构中插入的复杂度分析和示例代码。
数组的插入操作
数组是一种线性数据结构，其元素在内存中是连续存储的。在C++中，对数组的插入操作通常包括在指定位置插入元素或在末尾添加新元素两种情况。
在指定位置插入元素
在数组中插入元素时，需要将插入位置后的元素依次向后移动，为新元素腾出空间。以下是一个简单的C++示例代码，展示了如何在数组的指定位置插入元素：
#include <iostream>
const int MAX_SIZE = 100;
int main() {
int arr[MAX_SIZE] = {1, 2, 3, 4, 5};
int size = 5; // 当前数组大小
int pos = 2; // 插入位置
int value = 10; // 要插入的值
// 检查插入位置是否合法
if (pos < 0 || pos > size) {
std::cout << "Invalid position for insertion." << std::endl;
return 0;
}
// 后移元素
for (int i = size; i > pos; i--) {
arr[i] = arr[i-1];
}
// 插入新元素
arr[pos] = value;
size++;
// 输出数组
std::cout << "After insertion:" << std::endl;
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
以上代码演示了在数组的指定位置插入新元素的过程，输出如下：
After insertion:
1 2 10 3 4 5
在末尾添加元素
另一种常见的数组插入操作是在数组的末尾添加新元素。在这种情况下，只需将新元素放在数组的最后一个位置即可。以下是一个简单的C++示例代码，展示了如何在数组末尾添加元素：
#include <iostream>
const int MAX_SIZE = 100;
int main() {
int arr[MAX_SIZE] = {1, 2, 3, 4, 5};
int size = 5; // 当前数组大小
int value = 10; // 要插入的值
// 在末尾添加新元素
arr[size] = value;
size++;
// 输出数组
std::cout << "After insertion:" << std::endl;
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
以上代码演示了在数组的末尾添加新元素的过程，输出如下：
After insertion:
1 2 3 4 5 10
向量的插入操作
向量（vector）是C++标准库中提供的一种动态数组，它具有自动扩展和动态调整大小的特性。在向量中插入元素时，同样需要考虑插入位置和插入值。以下是一个简单的C++示例代码，展示了如何在向量中进行插入操作：
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
int pos = 2; // 插入位置
int value = 10; // 要插入的值
// 检查插入位置是否合法
if (pos < 0 || pos > vec.size()) {
std::cout << "Invalid position for insertion." << std::endl;
return 0;
}
// 在指定位置插入元素
vec.insert(vec.begin() + pos, value);
// 输出向量
std::cout << "After insertion:" << std::endl;
for (int i = 0; i < vec.size(); i++) {
std::cout << vec[i] << " ";
}
std::cout << std::endl;
return 0;
}
以上代码演示了在向量中的插入操作，输出如下：
After insertion:
1 2 10 3 4 5
链表的插入操作
链表是一种常见的数据结构，包括单向链表、双向链表和循环链表等。对链表进行插入操作时，需要考虑插入位置、插入节点和调整指针等操作。以下是一个简单的C++示例代码，展示了如何在单向链表中进行插入操作：
#include <iostream>
struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};
void insertNode(Node* head, int pos, int value) {
Node* newNode = new Node(value);
Node* prev = head;
int count = 0;
// 遍历链表找到插入位置的前一个结点
while (prev && count < pos - 1) {
prev = prev->next;
count++;
}
// 插入新节点
if (prev) {
newNode->next = prev->next;
prev->next = newNode;
}
}
void printList(Node* head) {
Node* cur = head;
while (cur) {
std::cout << cur->data << " ";
cur = cur->next;
}
std::cout << std::endl;
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
int pos = 2; // 插入位置
int value = 10; // 要插入的值
insertNode(head, pos, value);
printList(head);
return 0;
}
以上代码演示了在单向链表中进行插入操作，输出如下：
1 2 10 3 4
复杂度分析和总结
对于数组和向量的插入操作，时间复杂度均为O(n)，其中n为插入位置之后的元素个数。在最坏情况下，需要将元素依次后移，因此时间复杂度为线性的。而对于链表的插入操作，时间复杂度为O(1)，因为只需简单的指针操作即可完成插入操作。
总结来说，在C++中，数组、向量和链表都提供了插入操作的实现方式，开发者根据具体的需求可以选择合适的数据结构来进行插入操作。在实际编程中，要注意处理边界情况和异常情况，确保插入操作的正确性和稳定性。另外，不同数据结构的插入操作的时间复杂度是不同的，开发者需要根据具体场景选择合适的数据结构来保证程序的效率。