

数据结构与算法
Sun Jul 02 2023
Guide
C++代码
摘要
下面的代码完成了链表的增删改查等功能
#include <iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<stack>
#include<string>
using namespace std;
class LinkedNode {
public:
int val;
LinkedNode* next;
LinkedNode(int val) :val(val), next(nullptr) {};
};
int _size = 0;
LinkedNode* _dummyNode = new LinkedNode(0);
int get(int index) {
if (index > _size - 1 || index < 0)
{
return -1;
}
LinkedNode* cur = _dummyNode->next;
while (index--)
{
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
LinkedNode* temp = new LinkedNode(val);
temp->next = _dummyNode->next;
_dummyNode->next = temp;
_size++;
}
void addAtTail(int val) {
LinkedNode* temp = new LinkedNode(val);
LinkedNode* cur = _dummyNode;
while (cur->next != nullptr) {
cur = cur->next;
}
cur->next = temp;
_size++;
}
int addAtIndex(int index, int val) {
LinkedNode* temp = new LinkedNode(val);
if (index<0 || index>_size)return -1;
LinkedNode* cur = _dummyNode;
while (index--) {
cur = cur->next;
}
temp->next = cur->next;
cur->next = temp;
_size++;
return 0;
}
int deleteAtIndex(int index) {
if (index<0 || index>_size - 1)return -1;
LinkedNode* cur = _dummyNode;
while (index--)
{
cur = cur->next;
}
LinkedNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
temp = nullptr;
_size--;
return 0;
}
int printLinkedlist() {
LinkedNode* cur = _dummyNode;
if (cur->next == nullptr)return -1;
while (cur->next != nullptr)
{
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
return 0;
}
int main() {
int n, a, m, k, f;
string s;
cin >> n;
while (n--)
{
cin >> a;
addAtHead(a);
}
cin >> m;
while (m--) {
cin >> s;
if (s == "show") {
if (printLinkedlist() == -1)cout << "Link list is empty" << endl;
}
else if (s == "get") {
cin >> k;
int temp = get(k - 1);
if (temp == -1) {
cout << "get fail" << endl;
}
else {
cout << temp << endl;
}
}
else if (s == "delete") {
cin >> k;
int temp = deleteAtIndex(k - 1);
if (temp == -1) {
cout << "delete fail" << endl;
}
else {
cout << "delete OK" << endl;
}
}
else if (s == "insert") {
cin >> k >> f;
int temp = addAtIndex(k - 1, f);
if (temp == -1) {
cout << "insert fail" << endl;
}
else {
cout << "insert OK" << endl;
}
}
}
}