Професионална програма
Loading...
Yoana_Borisova avatar Yoana_Borisova 4 Точки

07. List

Здравейте! Изпитвам затруднения със задача 07. List от упражнението за правилото на 3/5/0. И по-точно с имплементирането на функцята static List getReversed(List l) и деструктора. Когато рънна програмата ми изписва exit code -1073741819, което до колкото разбрах е от неправилно освобождаване на памет. Чудя се дали не трябва да напиша някаква функция за изтриването и на всеки нов Node, който създавам или той сам ще се изтрие, когато излезе от скоуп. Ето го кода ми ще съм благодарна на малко помощ:

#include "List.h"
#include <sstream>

List::List()=default;
List::List(const List& other){
 *this = other;
}
int List::first() const{
    return head->getValue();
}



void List::add(int value){
    Node* newV;
    newV->setValue(value);
    newV->setPrev(tail);
    newV->setNext(nullptr);

    Node* help=newV;
    newV=tail;
    tail=help;

    newV->setNext(tail);

}

void List::addAll(const List& other){
   tail->setNext(other.head);
   other.head->setPrev(tail);
}

void List::removeFirst(){
    Node* newFirst=head->getNext();
    Node* help = tail;
    tail=newFirst;
    newFirst=tail;

}

void List::removeAll(){
    head->setNext(nullptr);
    head->setValue(0);
    tail->setPrev(head);
    tail->setValue(0);
}

size_t List::getSize() const{
    if(isEmpty()){return 0;}
    size_t size=1;
    Node* curr=head;
    while(curr!=tail){
        curr=head->getNext();

      size++;
    }

    return size;
}

bool List::isEmpty() const{
    if(head->getNext()==nullptr){
        return true;
    }
    return false;
}

List List::getReversed(List l){
    //??
   return l;
}

std::string List::toString() const{
    Node* curr=head;
    std::ostringstream out;
    while(curr!=tail||curr==tail){
        out<<curr->getValue()<<" ";
    }
    return out.str();
}

List& List::operator<<(const int& value){
    add(value);
    return *this;
}


List& List::operator<<(const List& other){
    addAll(other);
    return *this;
}

List& List::operator=(const List& other){
    head=other.head;
    tail=other.tail;
    size=other.size;
    return *this;
}

List::~List() {
    //??
    Node *curr = head;
    while (curr != tail) {
        curr = curr->getNext();
        delete curr->getPrev();
        curr->setPrev(nullptr);
    }
    delete curr;
    curr = nullptr;
}

//Node part

List::Node::Node(int value, Node * prev, Node * next){
    this->value=value;
    this->next=next;
    this->prev=prev;

}

int List::Node::getValue() const{
    return this->value;
}
void List::Node::setValue(int value){
    this->value=value;
}
List::Node* List::Node::getNext() const{
    return this->next;
}
void List::Node::setNext(Node * next){
    value=next->value;
    next=next->next;
    prev=next->prev;
}

List::Node * List::Node::getPrev() const{
    return this->prev;
}
void List::Node::setPrev(Node * prev){
    value=prev->value;
    next=prev->next;
    prev=prev->prev;
}


 

Тагове:
1
C++ OOP
j.petrov_90 avatar j.petrov_90 372 Точки

Привет, Йоанче,

Задачата хич не е лесна.
Имай предвид, че тази задача е една от "класиките" - да си имплементираш std::list без да ползваш на готово функционалности от STL-а.
Във всеки един университет е гаранция, че ще минеш от там.
До колко помня (дано не греша) на теб ти е рано за университет, така че давай смело - ще помагаме! :)

Колегата @ditchev ти е дал добри насоки.
И аз не искам да ти "изплювам" готовото решение, а искам ти сама да си намериш грешките и да ги коригираш.

Да запомнем от там, че сме хора, а не сме машини.
Като виждаш, че имаш грешка - не се чуди какво се случва - а пуски дебъгера.
Започни да минаваш пред кода ред по ред, функция по функция и разжлеждай стойностите на променливите.
Ще се очудиш колко лесно се хващат грешки :)

Няколко жокера:
- в деструктора ползваш delete, но никъде не си заделила памет динамично. Може би там където създаваш нещо - там трябва да има заделяне на памет
- в решението ти няма абсолютно нито една проверка
Представи си, че имаш само 1 елемент в списъка. Неговият next трябва да е nullptr. Ти обаче никъде не проверяваш за nullptr. Т.е. никъде не гледаш дали имаш curr element, да не говорим за next
- default-ния ти конструктор много прецеква работата. По този начин всичките ти променливи са неинициализирани
- относно функцията getReversedList - ами как трябва да изглежда? Листа си има глава (head) има си и опашка (tail). Тогава създаваш един нов списък и започваш да прибавяш елементи от към главата му, докато в оригиналния списък ги взимаш в обратен ред (от опашката към главата).

Очаквам те да се върнеш с по-добро решение :)
Ти си на ход.

Поздрави,
Живко

1
15/08/2021 21:55:38
Smeshan avatar Smeshan 89 Точки

Здравейте колеги,
наслагах пропуснатите size увеличения и намаления, където ги бях изпуснал (надявам се това сте имали предвид).

Иначе копи конструктура тотално го бях изпуснал. Eто как ги направих да изглеждат:
Copy constructor:

List::List(const List& other)
	: head(size ? new Node(other.head->getValue(), other.head->getPrev(), other.head->getNext()) : nullptr)
	, tail(size ? new Node(other.tail->getValue(), other.tail->getPrev(), other.tail->getNext()) : nullptr)
	, size(other.size) {
}

Copy assignment:

List& List::operator=(const List& other) {
	if (this != &other) {
		this->size = other.size;
		Node* newHead = new Node(other.head->getValue(), other.head->getPrev(), other.head->getNext()); // allocate
		if (this->head != nullptr) {
			delete this->head;  // deallocate
		}
		this->head = newHead;

		Node* newTail = new Node(other.tail->getValue(), other.tail->getPrev(), other.tail->getNext()); // allocate
		if (this->tail != nullptr) {
			delete this->tail;  // deallocate
		}
		this->tail = newTail;
	}
	return *this;
}

Доколкото разбирам всъщност "данните" на един лист са в head и tail, и съответно тях трябва да алокиръм и делокиръм. Нали? Защото пробвах нещо от сорта на List* newList = new List(other); , но после не ми дава this = newList;. Или всъщност точно това е задачата да има new List, в който вече правя това с new Node за head и tail?

И уж напълно ми е ясно вече какво трябва да направя и какво трябва да стане, но сега гръмна още повече.. След известно време прекарано с дебъгера, в Copy assignment отнякъде се появява лист с value -587983213 .. незнайно от къде и програмата гърми.
Ето целия код:
List.cpp

Не знам колко е трудна тази задача, защото в главата ми е ясна логиката и как работи един лист, но не мога да го изпиша вярно с код :(

Поздрави,
Илиян

1
16/08/2021 12:55:38
j.petrov_90 avatar j.petrov_90 372 Точки

Привет, Илиян,

Доближаваш се до целта, но има още път, който трябва да изминеш.
Дали листа държи данните си в "head" и "tail"? - Не, не ги държи там.

Разгледай собствена си функция

void List::add(int value) {

и би трябвало да си отговориш на въпроса.

Данните в един лист могат да са безкрайно много. Нищо не пречи да имаш 1 милион Node-a.
Head и Tail са ти само пойнтъри към първия е респективно последния Node от тези 1 милион.

Т.е. не е достатъчно да заделиш нови данни само за Node-а под head-a и tail-а.
защото това ще значи, че останалите (1 милион - 2) елемента имаш shallow copy.
Или казано по друг начиш - в 2 или повече листа ще имаш референции към една и съща динамична памет.
От там нататък задачата ти е бомба със закъснител.

Какво трябваше да направиш?
Да направиш deep copy на абсолютно всички node-ове, които искаш да копираш.

Поздрави

0
Smeshan avatar Smeshan 89 Точки

Борбата и бомбите продължават..
И ето заделям нова памет newHead с датата на other.head. След това казвам head = newHead. След това слагам итератор към следващия елемент (този след other.head) и трия датата на other.head. И би трябвало съм готов с head-a?
След това слагам пойнтър към следващия елемент от this (този след this->head) и започвам да итерирам елемент по елемент, като създавам нова задалена памет за всеки Node с данните на от other, премествам итераторите, трия другите данни и сменям итератора от този node да сочи към новите данни. След това същото и за опашката. 

List::List(const List& other) {
	Node* newHead = new Node(other.head->getValue(), other.head->getPrev(), other.head->getNext());
	head = newHead;
	
	Node* otherIt = other.head->getNext();
	delete other.head;

	Node* thisIt = this->head->getNext();

	while (otherIt != other.tail) {
		Node* newNode = new Node(otherIt->getValue(), otherIt->getPrev(), otherIt->getNext());
		
		otherIt = other.head->getNext();
		delete otherIt;

		thisIt = newNode;
		thisIt = thisIt->getNext();
	}
	Node* newTail = new Node(other.tail->getValue(), other.tail->getPrev(), other.tail->getNext());
	tail = newTail;
	delete other.tail;

	this->size = other.size;

}

Не е ли това логиката :?

Поздрави.

0
Smeshan avatar Smeshan 89 Точки

Само минавам да кажа 100/100 :))

Разбрах как става. Изтрих всичко. Написах го отново, без гледам старото и пак стана. 

Много благодаря за помощта на всички!

1