Profile image
数据结构与算法

数据结构与算法

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;
            }
        }
    }
}