Double Linked List

[andresmadrid]

Ola a todos, estive aqui a dar umas voltas pelo forum e decidi pedir ajuda!

Foi-me pedido no ambito do meu trabalho escolar que desenvolve-se uma double linked list. Que permitisse introduzir elementos, eliminar elementos. Estes procedimentos deveriam ser regulados por um apontador denominado de current.

Bem o problema e que não tenho bases nenhumas em programar C++ e estou a desesperar. Tudo o que consegui fazer até agora (o professor fez isto para exemplo) foi isto. E mesmo assim não percebo algumas coisas! E não sei o que fazer mais.

Será que alguém me poderá explicar como efectuar o add e o delete dos parametros de acordo com a cosntruçao dos elementos estruturas e classes tal como tenh?

E porque me dão erros ao compilar?

Muito obrigado, o código que tenho é:

#include 
using namespace std;

class CElement {
public:
int *next_, *prev_, val_;
CElement (int val);
~CElement();
int value (){return(val_);}
};


CElement::CElement( int val){
val_ = val;
};

class CList {

CElement *current_;
CList::CList();
CElement* addElement(CElement* element);
CElement* deleteElement(CElement* element);

};


CList::CList(){
current_ = 0;
};

CElement* CList::addElement(CElement *element){

if(current_ == 0)
{
element->next_ = 0;
element->prev_ = 0;
current_ = element;
}


else
{
CElement* nextElement = current_->next_;

current_->next_ = element;
element->next_ = nextElement;

if(nextElement != 0)
{
nextElement->prev_ = element;
}

}
}


CElement* CList::deleteElement(CElement *element){

if(current_ != 0)
{
delete element;
element->next_ = 0;
element->prev_ = 0;

}

else { // what to do in case of not being null
}

}
int main ()
{

return 0;
}

EDIT|pedrotuga: usar gueshi, ver links na minha assinatura.

[andresmadrid]

Não consigo ver nada na tua assinatura...desculpa...

[TheDark]

Em 1º lugar tens um #include sem o nome do ficheiro a incluir. Remove as duas 1ªs linhas que não estão lá a fazer nada (pelo menos para já).

Depois vais ter que rever esta linha:

int *next_, *prev_, val_;

porque não vais quere apontadores para int, mas sim para CElement. Só val_ é que deves querer que seja int.

Quanto à implementação do método add, parece estar tudo bem. Só falta retornar um valor (que vai depender do enunciado).

No delete, vais ter que alterar o próximo do anterior para o próximo (current->next->prev para current->prev) e o anterior do próximo para o próximo (current->prev->next para current->next). Parece confuso? Pega em papel e caneta, constrói uma lista pequena, simula a remoção de um elemento e vê as ligações que tens que alterar 😛

O protótipo do método deleteElement é mesmo esse? Não devia receber um índice como parâmetro?

[andresmadrid]

Caro The Dark, já andei a estudar mais um pouco e realmente tinha muita coisa mal feita...Mas agora penso que consegui estruturar o meu programa...

Grato pela ajuda...Penso que já resolvi a questão!

Abraços!!

[TheDark]

Sem problemas 😛 Podias era pôr aí a solução a que chegaste, pode servir para ajudar alguém no futuro!

[andresmadrid]

Claro... Aqui está ela...

// double_linked_final.cpp : Defines the entry point for the console application.
//
// C++ double linked List
#include "stdafx.h"
#include <iostream>
#include <iterator>
using namespace std;


// Implement Class CElement
class CElement 
  {
	int val_;

public:

	int value () { return( val_ ); }

	CElement *next_;
	CElement *prev_; 

	// Constructor
	CElement  (int val);
	// Destructor
	~CElement ();		//Not defined!

  };

// Implements the construtor and sets the value val = val_ and initialize pointers
CElement::CElement ( int val )
  {
        val_  = val;
	next_ = NULL;
	prev_ = NULL;
  };

// Implement Class CList
class CList
  {

public:
	CElement *current_;
	CElement *head_;
	CElement *prevelem_;


	// Constructor
	CList::CList() { head_ = NULL; }

	// Add an element
	CElement* addElement (CElement* element);
	// Delete an element
	CElement* delElement(CElement *element);
	CElement* Swap2Next( CElement* elem );
	CElement* GetHead( CElement* elem );
	CElement* GetTail( CElement* elem );
	CElement* Sort ( );
  };


// Implement method to add an element
CElement* CList::addElement(CElement *element)
  {
    // If the element is already part of a list it cannot be inserted
if( element->prev_ != NULL || element->next_ != NULL )
{
	return(NULL);
}

// 1. Case of first element added
    if(head_ == NULL)
    {
        head_ = element;
    }

    // 2. Case of not first element to be added the new element will be the list header
    else
    {
  	head_->prev_	= element;
	element->next_	= head_;
	head_			= element;
}

return ( head_ );
  }


//Implement method to delete element;
CElement* CList::delElement(CElement *element){

	// 1. Element is the last one
if(element -> next_ == NULL){
	prevelem_ = element -> prev_;
	prevelem_ -> next_= NULL;
	return 0;
}
// 2. Element is the first one
if(element -> prev_ == NULL){
	head_ = element -> next_;
	return 0;
}

prevelem_ = element -> prev_;
prevelem_ -> next_ = element -> next_;
    return 0;


return 0;
}


// Implement method to swap an element within the next one
CElement* CList::Swap2Next( CElement* elem )
  {
CElement* elem1 = elem;
CElement* elem2	= elem->next_;

if( elem->next_ == NULL )
{
	return elem;
}

if( elem1->prev_ != NULL )
  {
	elem1->prev_->next_ = elem2;
  }

if( elem2->next_ != NULL )
  {
        elem2->next_->prev_ = elem1;
  }

elem1->next_ = elem2->next_;
elem2->prev_ = elem1->prev_;

elem1->prev_ = elem2;
elem2->next_ = elem1;

return elem2;
  }

CElement* CList::GetHead( CElement* elem )
  {
if( elem->prev_ == NULL )
	return ( elem );
else
	return ( GetHead( elem->prev_ ) );
  }

// Implement method to 
CElement* CList::GetTail( CElement* elem )
  {
if( elem->next_ == NULL )
	return ( elem );
else
	return ( GetHead( elem->next_ ) );
  }

// Implement method to sort the list ( Bubble-Sort )
CElement* CList::Sort( )
  {
CElement* temp = head_;
bool swaped;

do{
	swaped = false;
	temp = GetHead( temp );

	while ( temp->next_ != NULL )
	{
		if( temp->value() > temp->next_->value() )
		{
			temp = Swap2Next( temp );
			swaped = true;
		}
		temp = temp->next_;
	}
}
while( swaped );

head_ = GetHead( temp );

return (NULL);
  }

int _tmain(int argc, _TCHAR* argv[])
{
CElement * elem1 = new CElement(10);
    CElement * elem2 = new CElement(6);
    CElement * elem3 = new CElement(70);
    CElement * elem4 = new CElement(120);
    CElement * elem5 = new CElement(65);
CElement * elem6 = new CElement(300);
CElement * elem7 = new CElement(45);
CElement * elem8 = new CElement(60);
CElement * elem9 = new CElement(8);
CElement * elem10 = new CElement(90);

CList * list = new CList();

list->addElement(elem1);
    list->addElement(elem2);
    list->addElement(elem3);
    list->addElement(elem4);
    list->addElement(elem5);
list->addElement(elem6);
list->addElement(elem7);
list->addElement(elem8);
list->addElement(elem9);
list->addElement(elem10);
list->addElement(elem9);

list->delElement(elem3);



list->current_=list->head_;
cout << "The list without being in order :  ";
while(list->current_->next_!=NULL){

	cout << list->current_->value() << ", ";
	list->current_ = list->current_->next_;
}

cout << list->current_->value();

cout << "\n";
cout << "\n";

//Sort the list;
list->Sort();

//Get the header;
list->head_;

//Set current in header;
list->current_=list->head_;

cout << "The order list is:  ";

while(list->current_->next_!=NULL){

	cout << list->current_->value() << ", ";
	list->current_ = list->current_->next_;
}
cout << list->current_->value();
list->current_ = list->current_->next_;

cout << "\n";
cout << "\n";


cout << "The list header is:  " << list->head_->value();


	getchar();

return 0;
}

[andresmadrid]

espero ter ajudado alguém!

Cumprimentos!