• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

force of will

[C++] Listas Duplamente Ligadas

2 mensagens neste tópico

Não usei templates porque fiz isto para um trabalho em que nao pudia recorrer a templates, de qualquer forma alterar o código para templates é trivial

#pragma once

#include <stdlib.h>
#include <assert.h>
typedef int Entry;		

//!  LinkedList
/*!
Basic implementation of a linked list
*/
class LinkedList
{
private:
struct Node
{
public:
	Node(Entry val);

	Node();

	Node *next;
	Node *previous;

	Entry val;
};

public:
friend class Iterator;
class Iterator
{
public:
	friend class LinkedList;

	// constructors
	Iterator(const LinkedList *list);
	~Iterator();

	// methods
	void Next();
	void Start();
	bool IsValid();
	const Entry const * GetValue();
private:
	const LinkedList *m_list;		// the list we're iterating
	LinkedList::Node *m_current;	// current node we're in

};


// constructors
LinkedList(void);
~LinkedList(void);

// metods
void Append(const Entry val);
void Prepend(const Entry val);
void RemoveHead();	
void RemoveTail();
void RemoveNode(Iterator *it);
Entry Head();

private:

Node *m_head;	// head of the linked list
Node *m_tail;	// tail fo the linked list

LinkedList(const LinkedList &){};	// enforce that the user will not pass by value a linked list

};

#include "LinkedList.h"


LinkedList::Node::Node(Entry val)
{
		next = NULL;
		previous = NULL;
		this->val = val;
}

LinkedList::Node::Node()
{
		next = NULL;
		previous = NULL;
}


LinkedList::LinkedList()
{
this->m_head = this->m_tail = NULL;
}

LinkedList::~LinkedList()
{
	Node *pTemp = m_head;

	while(pTemp)
	{
		pTemp = pTemp->next;
		delete m_head;
		m_head = pTemp;
	}
}




/*!
Description: Insert a node to the tail of the linked list
Arguments: The value to be inserted on the linked list
*/
void LinkedList::Append(const Entry val)
{
if(!m_head)
{
	m_head = m_tail = new Node(val);
	m_head->previous = NULL;
}
else
{
	Node *pTemp = new Node(val);

	pTemp->previous = m_tail;

	m_tail->next = pTemp;
	m_tail = pTemp;
}
}

/**
*Insert a node to the head of the linked list
*@param val value to be inserted on the linked list
*@return void
*see Append()
*/
void LinkedList::Prepend(const Entry val)
{
if(!this->m_tail)
{
	this->m_head = this->m_tail = new Node(val);
	m_head->previous = NULL;
}
else
{
	Node *pTemp = new Node(val);
	pTemp->next = m_head;
	m_head->previous = pTemp;
	m_head = pTemp;
}
}

/**
*Removes the head node
*@return void
*@see RemoveTail()
*/
void LinkedList::RemoveHead()
{
if(this->m_head)
{
	if(m_tail == m_head)
		m_tail = m_head->next;

	Node *pTemp = m_head->next;
	delete this->m_head;
	m_head = pTemp;
}
}


/**
*Removes the tail node
* this method is much slower than remove head, since we iterate to the entire linked list
*@return void
*@see RemoveHead()
*/
void LinkedList::RemoveTail()
{		
if(m_head == m_tail)
{
	delete m_head;
	m_head = m_tail = NULL;
}

Node *pTemp = m_tail->previous;

delete m_tail;

pTemp->next = NULL;

m_tail = pTemp;
}

void LinkedList::RemoveNode(Iterator *it)
{
	Node *pTemp = it->m_current;

	if(!it->IsValid())
		return;

	if(pTemp == m_tail)
		m_tail = pTemp->previous;

	if(!pTemp->previous) // we're in the head node
	{
		m_head = pTemp->next;
		delete pTemp;

		it->m_current = m_head;
		if(m_head)
			m_head->previous = NULL;
	}
	else
	{
		pTemp->previous->next = pTemp->next;

		if(pTemp->next)
			pTemp->next->previous = pTemp->previous;

		it->m_current = pTemp->previous;
		delete pTemp;
	}
}

Entry LinkedList::Head()
{
	assert(m_head);

	return m_head->val;
}


LinkedList::Iterator::Iterator(const LinkedList *list)
{
m_list = list;
m_current = list->m_head;
}

LinkedList::Iterator::~Iterator()
{
}


// methods
void LinkedList::Iterator::Next()
{
m_current = m_current->next;
}

void LinkedList::Iterator::Start()
{
m_current = m_list->m_head;
}

bool LinkedList::Iterator::IsValid()
{
return m_current != NULL;
}

const Entry const * LinkedList::Iterator::GetValue()
{
return &m_current->val;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu ja percebi mais de C++ do que percebo agora... mas tipo tas a usar uma struct dentro de uma class para fazer listas ligadas???? Não dava para simplesmente usares uma class com propriedades que fossem ponteiros para a proxima lista etc??

Ou sou eu que li mal o codigo?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora