У меня есть программа с реализацией двусвязного списка. Как сделать его кольцевым? Вот…
- 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 равен NULL, то это значит, что список пустой и новый элемент станет и головой, но также нужно установить связь между головой и хвостом, чтобы создать зацикленность. Поэтому после установки головы, нужно добавить следующую строку:
tail->next = head;
- Также в методе push_back() нужно добавить проверку, если head равен NULL, то это значит, что список пустой и новый элемент станет и хвостом, но также нужно установить связь между головой и хвостом, чтобы создать зацикленность. Поэтому после установки хвоста, нужно добавить следующую строку:
head->prev = tail;
- В методе pop_front() нужно изменить условие проверки, чтобы оно работало с кольцевым списком. Замените строку:
if (head == NULL) return;
на:
if (head == NULL || head == tail) return;
- В методе pop_back() нужно изменить условие проверки, чтобы оно работало с кольцевым списком. Замените строку:
if (tail == NULL) return;
на:
if (tail == NULL || head == tail) return;
- В методе erase() нужно изменить условие проверки, чтобы оно работало с кольцевым списком. Замените строку:
if (ptr == NULL) return;
на:
if (ptr == NULL || head == tail) return;
Эти изменения обеспечат зацикленность двусвязного списка.