@Anvario0

Почему метод push_front() работает неправильно?

Код односвязного списка:
#include <iostream>;
using namespace std;

template <typename T>
class List{
public:
	List();
	~List();

	void clear(); //Очищение списка
	void pop_front(); //Удаление первого элемента списка
	void push_back(T data); //Добавление элемента в конец списка
	void push_front(T data); //Добавление элемента в начало списка
	int GetSize() { return this->size; } //Полчение длины списка

	T& operator[](const int index);
private:

	template <typename T>
	class Node {
	public:
		Node* pNext;
		T data;

		Node(T data = T(), Node* pnext = nullptr) {
			this->pNext = pNext;
			this->data = data;
		}
	};

	int size;
	Node<T>* head;

};

template <typename T>
List<T>::List() {
	this->size = 0;
	this->head = nullptr;
}

template <typename T>
List<T>::~List() {
	this->clear();
}

template<typename T>
void List<T>::clear()
{
	while (this->GetSize()) {
		this->pop_front();
	}
}

template<typename T>
void List<T>::pop_front()
{
	Node<T>* newHead = this->head->pNext;
	delete this->head;

	this->head = newHead;

	size--;
}

template<typename T>
void List<T>::push_back(T data)
{
	if (this->head == nullptr) {
		this->head = new Node<T>(data);
	}
	else {
		Node<T>* current = this->head;

		while (current->pNext != nullptr) {
			current = current->pNext;
		}
		
		current->pNext = new Node<T>(data);
	}
	this->size++;
}

template<typename T>
void List<T>::push_front(T data)
{
	head = new Node<T>(data, head);
	this->size++;
}

template<typename T>
T& List<T>::operator[](const int index)
{
	Node <T>* current = this->head;
	for (int i = 0; current->pNext != nullptr; i++) {
		if (i == index) {
			return current->data;
		}
		current = current->pNext;
	}
	return current->data;
}


int main() {
	setlocale(LC_ALL, "ru");
	List <int> lst;
	
	lst.push_back(12);
	lst.push_back(346);
	lst.push_back(1348);
	lst.push_back(546);

	cout << "Список:" << endl;
	for (int i = 0; i < lst.GetSize(); i++) {
		cout << i + 1 << ") " << lst[i] << endl;
	}
	cout << endl << endl;

	lst.push_front(78);

	cout << endl << endl << "Список после push_front():" << endl;
	for (int i = 0; i < lst.GetSize(); i++) {
		cout << i + 1 << ") " << lst[i] << endl;
	}
	cout << endl << endl;
}

Но метод push_front() почему-то работает неправильно: он делает все элементы 78, то есть в консоли выводится
Список:
1) 12
2) 346
3) 1348
4) 546




Список после push_front():
1) 78
2) 78
3) 78
4) 78
5) 78
  • Вопрос задан
  • 117 просмотров
Решения вопроса 1
old2ev
@old2ev
int main(){for(;;)fork();}
1-е строка 22 проинициализируйте указатель нулём, иначе у Вас функция ловит ошибку сегментации в лучшем случае, в худшем идёт гулять по оперативке:
Node* pNext = nullptr;

2-e строки 25-29 у Вас pNextинициализируется сам собой поскольку аргумент конструктора именован pnext. Замените pnext в аргументе на pNext:
Node(T data = T(), Node* pNext = nullptr) {
  this->pNext = pNext;
  this->data = data;
}

А лучше инициализируйте поля объекта класса через конструктор так:
Node(T data = T(), Node* pNext = nullptr) 
  : pNext(pNext), data(data) {}

В таком случае IDE кидает предупреждение, если поле инициализируется само собой.

После вышеуказанных исправлений всё работает:
Список:
1) 12
2) 346
3) 1348
4) 546




Список после push_front():
1) 78
2) 12
3) 346
4) 1348
5) 546


+Совет сверху: Лучше храните в листе указатель на последний узел списка, чтобы не перебрирать весь список при push_back, так асимптотика будет O(1), а не O(N) при минимальных затратах памяти (+8 байт на x64 или +4 байта на x32)
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
axifive
@axifive
Software Engineer
Опечатка, посмотри на конструктор узла повнимательнее.
...
Node(T data = T(), Node* (pnext) = nullptr) {
      this->pNext = (pNext);
...
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы