题目描述
维护序列。给定一个长度为n的整数序列。现在有m个操作，操作分为三类，格式如下：
1 i：询问序列中第i个元素的值；
2 i v：在序列中第i个元素前加入新的元素v,如果添加的位置错误，输出Insert error!!!；
3 i：删除序列中的第i个元素，如果删除的位置错误，输出Delete error!!!。
输入格式
第1行输入n（1<=n<=1000），表示序列最初的长度；
第2行输入n个空格隔开的数，表示原始的整数序列；
第3行输入m（1<=m<=1000），表示操作数；
第4到m+3行依次输入一个操作。
输出格式
对于操作（1）输出对应的答案，一行输出一个数。
样例数据
input
5
6 31 23 14 5
5
1 2
2 2 7
1 2
3 3
1 3
output
31
7
23
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> list(n);
for (int i = 0; i < n; i++) cin >> list[i];
int m;
cin >> m;
for (int i = 0; i < m; i++)
{
int mode;
cin >> mode;
if (mode == 1)
{
int index;
cin >> index;
cout << list[index - 1] << endl;
}
else if (mode == 2)
{
int index, value;
cin >> index >> value;
if (index < 0 || index > list.size()) cout << "Insert error!!!" << endl;
else list.insert(list.begin() + (index - 1), value);
}
else if (mode == 3)
{
int index;
cin >> index;
if (index < 0 || index >= list.size()) cout << "Delete error!!!" << endl;
else list.erase(list.begin() + (index - 1));
}
}
return 0;
}
#include<iostream>
#include<vector>
using namespace std;
// 定义节点
struct Node {
int value;
struct Node *prev;
struct Node *next;
Node (int val): value(val), prev(nullptr), next(nullptr) {};
};
// 定义链表
class LinkedList {
private:
Node *head; // 头节点指针
Node *tail; // 尾节点指针
int size; // 链表大小
public:
LinkedList(): head(nullptr), tail(nullptr), size(0) {};
~LinkedList(); // 析构函数，释放节点空间
void checkIndex(int index); // 检查索引是否合法
int getSize(); // 获取链表大小
void insert(int index, int value); // 在指定位置插入指定元素
void deleteNode(int index); // 删除指定位置节点
int getValue(int index); // 获取指定位置节点的值
};
LinkedList::~LinkedList() {
Node *p = head;
while(p != nullptr) {
Node *temp = p;
p = p->next;
delete temp;
}
head = nullptr;
tail = nullptr;
size = 0;
}
void LinkedList::checkIndex(int index) {
if(index < 0 || index >= size) { // 索引非法
throw "Index out of range!";
}
}
int LinkedList::getSize() {
return size;
}
void LinkedList::insert(int index, int value) {
if(index < 0 || index > size) { // 插入位置非法
throw "Index out of range!";
}
Node *node = new Node(value);
if(head == nullptr) { // 空链表
head = node;
tail = node;
} else if (index == 0) { // 插入到头节点处
node->next = head;
head->prev = node;
head = node;
} else if (index == size) { // 插入到尾节点处
tail->next = node;
node->prev = tail;
tail = node;
} else { // 插入到中间位置
Node *p = head;
for(int i = 0; i < index - 1; i++) {
p = p->next;
}
node->prev = p;
node->next = p->next;
p->next->prev = node;
p->next = node;
}
size++;
}
void LinkedList::deleteNode(int index) {
if(index < 0 || index >= size) { // 删除位置非法
throw "Index out of range!";
}
Node *p = head;
if(size == 1) { // 只有一个节点
head = nullptr;
tail = nullptr;
} else if (index == 0) { // 删除头节点
head = head->next;
head->prev = nullptr;
} else if (index == size - 1) { // 删除尾节点
p = tail;
tail = tail->prev;
tail->next = nullptr;
} else { // 删除中间节点
for(int i = 0; i < index; i++) {
p = p->next;
}
p->prev->next = p->next;
p->next->prev = p->prev;
}
delete p;
size--;
}
int LinkedList::getValue(int index) {
checkIndex(index);
Node *p = head;
for(int i = 0; i < index; i++) {
p = p->next;
}
return p->value;
}
int main() {
LinkedList l;
l.insert(0, 1);
l.insert(1, 2);
cout << l.getValue(0) << endl; // 1
cout << l.getValue(1) << endl; // 2
try {
l.insert(3, 3); // 插入位置非法
} catch(const char *msg) {
cout << msg << endl;
}
l.insert(2, 3);
cout << l.getValue(2) << endl; // 3
l.deleteNode(1);
cout << l.getValue(1) << endl; // 3
cout << l.getSize() << endl; // 2
try {
l.checkIndex(3); // 索引非法
} catch(const char *msg) {
cout << msg << endl;
}
return 0;
}