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 373 Точки

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

Задачата хич не е лесна.
Имай предвид, че тази задача е една от "класиките" - да си имплементираш 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 373 Точки

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

Доближаваш се до целта, но има още път, който трябва да изминеш.
Дали листа държи данните си в "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
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.