fork download

copy

// Struct thể hiện một node trên danh sách liên kết.
struct Node
{
    int value;
    struct Node* next;
    struct Node* prev;
 
    Node()
    {
        value = 0;
        next = NULL;
        prev = NULL;
    }
 
    void create_node(int _value)
    {
        value = _value;
        next = NULL;
        prev = NULL;
    }
};
 
// Struct thể hiện 1 danh sách liên kết, với head là node đầu tiên và last là node cuối cùng.
struct LinkedList
{
    Node* head = new Node();
    Node* last = new Node();
 
    LinkedList()
    {
        head = NULL;
        last = NULL;
    }
 
    void add_to_front(int value)
    {
        Node* new_node = new Node();
        new_node -> create_node(value);
 
        if (head == NULL)
            head = last = new_node;
        else
        {
            new_node -> next = head;
            head -> prev = new_node;
            head = new_node;
        }
    }
 
    void add_to_last(int value)
    {
        Node* new_node = new Node();
        new_node -> create_node(value);
 
        // Danh sách rỗng thì gán luôn head bằng node mới.
        if (head == NULL)
            head = last = new_node;
        else
        {
            // Ngược lại, tạo một node p để duyệt tới phần tử cuối của danh sách.
            Node* p = new Node();
            p = head;
            while (p -> next != NULL)
                p = p -> next;
 
            // Cho next của phần tử cuối trỏ tới node mới và prev của node mới trỏ vào phần tử cuối.
            // Cập nhật lại node cuối cùng của danh sách sẽ là node mới.
            p -> next = new_node;
            new_node -> prev = p;
            last = new_node;
        }
    }
 
    void add_to_position(int value, int x)
    {
        // Danh sách đang rỗng hoặc x = 1 thì coi như là chèn vào đầu danh sách.
        if (x == 1 || head == NULL) // Có thể đổi thành x = 0 tùy vào cách đánh số danh sách.
        {
            add_to_front(value);
            return;
        }
 
        // Đi tìm node ở vị trí x - 1.
        Node* p = new Node();
        p = head;
        int k = 1;
        while (p != NULL && k + 1 != x)
        {
            p = p -> next;
            ++k;
        }
 
        // Không tìm được node ở vị trí x - 1 thì xử lý riêng.
        if (k + 1 != x)
        {
            // Thông báo vị trí không hợp lệ, hoặc có thể coi như chèn vào cuối danh sách.
            // add_to_last(value);
            cout << "Invalid position\n";
            return;
        }
 
        // Chèn node mới vào sau vị trí k = x - 1, chính là vị trí x.
        Node* new_node = new Node();
        new_node -> create_node(value);
 
        // Xử lý node mới chèn vào.
        new_node -> next = p -> next;
        new_node -> prev = p;
 
        // Xử lý hai node trước và sau node mới chèn vào.
        if (p -> next != NULL)
            p -> next -> prev = new_node;
        p -> next = new_node;
    }
 
    void del_front()
    {
        if (head == NULL)
        {
            cout << "The linked-list is empty!\n";
            return;
        }
 
        head = head -> next;
        head -> prev = NULL;
    }
 
    void del_at_position(int x)
    {
        if (x == 1 || head == NULL || head -> next == NULL) // Hoặc x = 0 tùy vào cách đánh số danh sách.
        {
            del_front();
            return;
        }
 
        // Tìm phần tử liền trước vị trí cần xóa. Tối đa chỉ tới vị trí áp chót.
        Node* p = head;
        int k = 1;
        while (p -> next -> next != NULL && k != x - 1)
        {
            p = p -> next;
            ++k;
        }
 
        // Đã duyệt tới phần tử áp chót mà vẫn chưa tới được phần tử liền trước
        // vị trí cần xóa, thì kết luận không tồn tại vị trí cần xóa.
        if (k != x - 1)
        {
            cout << "The position is invalid\n";
            return;
        }
 
        // Đặt p -> next trỏ tới phần tử liền sau phần tử cần xóa.
        // Đặt prev của phần tử liền sau phần tử cần xóa trỏ vào p.
        if (p -> next -> next == NULL) // Xóa ở cuối.
            p -> next = NULL;
        else // Xóa ở giữa.
        {
            p -> next -> next -> prev = p;
            p -> next = p -> next -> next;
        }
    }
 
    void print_list()
    {
        for (Node* p = head; p != NULL; p = p -> next)
            cout << p -> value << ' ';
    }
 
    int value_at_index(int x)
    {
        int k = 1;
        Node* p = head;
        while (p -> next != NULL && k != x)
        {
            p = p -> next;
            ++k;
        }
 
        return p -> value;
    }
 
    void input_linked_list(int n)
    {
        for (int i = 1; i <= n; ++i)
        {
            int value;
            cin >> value;
 
            add_to_last(value);
        }
    }
};

prog.cpp: In constructor ‘Node::Node()’:
prog.cpp:11:16: error: ‘NULL’ was not declared in this scope
         next = NULL;
                ^~~~
prog.cpp:11:16: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:1:1:
+#include <cstddef>
 // Struct thể hiện một node trên danh sách liên kết.
prog.cpp:11:16:
         next = NULL;
                ^~~~
prog.cpp: In member function ‘void Node::create_node(int)’:
prog.cpp:18:16: error: ‘NULL’ was not declared in this scope
         next = NULL;
                ^~~~
prog.cpp:18:16: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp: In constructor ‘LinkedList::LinkedList()’:
prog.cpp:31:16: error: ‘NULL’ was not declared in this scope
         head = NULL;
                ^~~~
prog.cpp:31:16: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp: In member function ‘void LinkedList::add_to_front(int)’:
prog.cpp:40:21: error: ‘NULL’ was not declared in this scope
         if (head == NULL)
                     ^~~~
prog.cpp:40:21: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp: In member function ‘void LinkedList::add_to_last(int)’:
prog.cpp:56:21: error: ‘NULL’ was not declared in this scope
         if (head == NULL)
                     ^~~~
prog.cpp:56:21: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp: In member function ‘void LinkedList::add_to_position(int, int)’:
prog.cpp:77:31: error: ‘NULL’ was not declared in this scope
         if (x == 1 || head == NULL) // Có thể đổi thành x = 0 tùy vào cách đánh số danh sách.
                               ^~~~
prog.cpp:77:31: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:95:17: error: ‘cout’ was not declared in this scope
                 cout << "Invalid position\n";
                 ^~~~
prog.cpp: In member function ‘void LinkedList::del_front()’:
prog.cpp:118:21: error: ‘NULL’ was not declared in this scope
         if (head == NULL)
                     ^~~~
prog.cpp:118:21: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:119:13: error: ‘cout’ was not declared in this scope
             cout << "The linked-list is empty!\n";
             ^~~~
prog.cpp:122:24: error: ‘NULL’ was not declared in this scope
         head -> prev = NULL;
                        ^~~~
prog.cpp:122:24: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp: In member function ‘void LinkedList::del_at_position(int)’:
prog.cpp:127:31: error: ‘NULL’ was not declared in this scope
         if (x == 1 || head == NULL || head -> next == NULL) // Hoặc x = 0 tùy vào cách đánh số danh sách.
                               ^~~~
prog.cpp:127:31: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:133:37: error: ‘NULL’ was not declared in this scope
         while (p -> next -> next != NULL && k != x - 1)
                                     ^~~~
prog.cpp:133:37: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:142:13: error: ‘cout’ was not declared in this scope
             cout << "The position is invalid\n";
             ^~~~
prog.cpp:147:38: error: ‘NULL’ was not declared in this scope
             if (p -> next -> next == NULL) // Xóa ở cuối.
                                      ^~~~
prog.cpp:147:38: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp: In member function ‘void LinkedList::print_list()’:
prog.cpp:159:35: error: ‘NULL’ was not declared in this scope
         for (Node* p = head; p != NULL; p = p -> next)
                                   ^~~~
prog.cpp:159:35: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:160:13: error: ‘cout’ was not declared in this scope
             cout << p -> value << ' ';
             ^~~~
prog.cpp: In member function ‘int LinkedList::value_at_index(int)’:
prog.cpp:167:29: error: ‘NULL’ was not declared in this scope
         while (p -> next != NULL && k != x)
                             ^~~~
prog.cpp:167:29: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp: In member function ‘void LinkedList::input_linked_list(int)’:
prog.cpp:181:13: error: ‘cin’ was not declared in this scope
             cin >> value;
             ^~~

Standard output is empty