У меня есть программа с реализацией двусвязного списка. Как сделать его кольцевым? Вот…
- User
У меня есть программа с реализацией двусвязного списка. Как сделать его кольцевым? Вот программа: #include #include using namespace std;
class Node //элемент списка { public: int data; Node* prev, * next; public: Node(int data) { this->data = data; this->prev = this->next = NULL; }
};
class LinkedList //список { public: Node* head, * tail;
public: LinkedList() //конструктор (создаёт пустой список) { head = tail = NULL; }
~LinkedList() //деструктор (освобождение памяти) { while (head != NULL) pop_front(); } Node* push_front(int data) //добавление элемента в начало (влево) { Node* ptr = new Node(data); ptr->next = head; if (head != NULL) head->prev = ptr; if (tail == NULL) tail = ptr; head = ptr; return ptr; } Node* push_back(int data) //добавление элемента в конец (вправо) { Node* ptr = new Node(data); ptr->prev = tail; if (tail != NULL) tail->next = ptr; if (head == NULL) head = ptr; tail = ptr; return ptr; } void pop_front() //удаление первого элемента (самого левого) { if (head == NULL) return; Node* ptr = head->next; if (ptr != NULL) ptr->prev = NULL; else tail = NULL; delete head; head = ptr; } void pop_back() //удаление последнего элемента (самого правого) { if (tail == NULL) return; Node* ptr = tail->prev; if (ptr != NULL) ptr->next = NULL; else head = NULL; delete tail; tail = ptr; } Node* getAt(int index) //доступ к произвольному элементу списка { Node* ptr = head; int n = 0; while (n != index) { if (ptr == NULL) return ptr; ptr = ptr->next; n++; } return ptr; } Node* operator [](int index) //возвращает элемент по индексу { return getAt(index); } Node* insert(int index, int data) //вставка элемента в список, согласно индексу { Node* right = getAt(index); if (right == NULL) return push_back(data); Node* left = right->prev; if (left == NULL) return push_front(data); Node* ptr = new Node(data); ptr->prev = left; ptr->next = right; left->next = ptr; right->prev = ptr; return ptr; } void erase(int index) //удалить элемент по индексу { Node* ptr = getAt(index); if (ptr == NULL) return; if (ptr->prev == NULL) { pop_front(); return; } if (ptr->next == NULL) { pop_back(); return; } Node* left = ptr->prev; Node* right = ptr->next; left->next = right; right->prev = left; delete ptr; }};
int main() {
}
- Assistant
Чтобы сделать двусвязный список кольцевым, необходимо изменить несколько методов класса LinkedList.
- В методе push_front необходимо добавить проверку наличия элементов в списке и в случае их отсутствия сделать tail указателем на новый элемент. Это позволит установить связь между первым и последним элементами списка.
- В методе push_back также нужно добавить проверку наличия элементов и установку связи между последним и первым элементами.
- В методе pop_front нужно изменить проверку наличия элементов, чтобы в случае отсутствия обновить tail указатель.
- В методе pop_back необходимо добавить проверку наличия элементов и обновление head указателя, если список станет пустым.
- В методе insert добавить проверку наличия элементов и установить связь между последним и первым элементами при добавлении нового элемента в конец списка.
- В методе erase также добавить проверку наличия элементов и обновить head и tail указатели, если список станет пустым.
Измененный код будет выглядеть следующим образом:
#include #include using namespace std;
class Node //элемент списка { public: int data; Node* prev, * next; public: Node(int data) { this->data = data; this->prev = this->next = NULL; }
};
class LinkedList //список { public: Node* head, * tail;
public: LinkedList() //конструктор (создаёт пустой список) { head = tail = NULL; }
~LinkedList() //деструктор (освобождение памяти) { while (head != NULL) pop_front(); } Node* push_front(int data) //добавление элемента в начало (влево) { Node* ptr = new Node(data); ptr->next = head; if (head != NULL) head->prev = ptr; if (tail == NULL) tail = ptr; head = ptr; tail->next = head; // устанавливаем связь между последним и первым элементами return ptr; } Node* push_back(int data) //добавление элемента в конец (вправо) { Node* ptr = new Node(data); ptr->prev = tail; if (tail != NULL) tail->next = ptr; if (head == NULL) head = ptr; tail = ptr; head->prev = tail; // устанавливаем связь между последним и первым элементами return ptr; } void pop_front() //удаление первого элемента (самого левого) { if (head == NULL) return; Node* ptr = head->next; if (ptr != NULL) ptr->prev = NULL; else tail = NULL; delete head; head = ptr; if (head != NULL) tail->next = head; // обновляем связь между последним и первым элементами } void pop_back() //удаление последнего элемента (самого правого) { if (tail == NULL) return; Node* ptr = tail->prev; if (ptr != NULL) ptr->next = NULL; else head = NULL; delete tail; tail = ptr; if (tail != NULL) head->prev = tail; // обновляем связь между последним и первым элементами } Node* getAt(int index) //доступ к произвольному элементу списка { Node* ptr = head; int n = 0; while (n != index) { if (ptr == NULL) return ptr; ptr = ptr->next; n++; } return ptr; } Node* operator [](int index) //возвращает элемент по индексу { return getAt(index); } Node* insert(int index, int data) //вставка элемента в список, согласно индексу { Node* right = getAt(index); if (right == NULL) return push_back(data); Node* left = right->prev; if (left == NULL) return push_front(data); Node* ptr = new Node(data); ptr->prev = left; ptr->next = right; left->next = ptr; right->prev = ptr; if (right == head) tail->next = head; // обновляем связь между последним и первым элементами return ptr; } void erase(int index) //удалить элемент по индексу { Node* ptr = getAt(index); if (ptr == NULL) return; if (ptr->prev == NULL) { pop_front(); return; } if (ptr->next == NULL) { pop_back(); return; } Node* left = ptr->prev; Node* right = ptr->next; left->next = right; right->prev = left; delete ptr; if (head == NULL) tail = NULL; // обновляем head и tail, если список станет пустым else if (tail == ptr) head->prev = tail; // обновляем связь между последним и первым элементами }};
int main() {
}
Теперь ваш двусвязный список стал кольцевым.