Archief - [PROG][C++] Linked list

jodeman · 12 dec 2006

Hello, der is iets mis met mijn linked list. Alles werkt behalve de remove. Kan iemand mij vertellen wat ik verkeerd doe? Dit was de derde poging en krijg altijd een beveiligingswaarschuwing van windows :crazy:

.

Code:

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include "listnode.h"

#include <iostream>
using std::cout;

template <typename NODETYPE>
class LinkedList
{
public:
	LinkedList();
	~LinkedList();

	void addSorted( const NODETYPE & );
	bool exists( const NODETYPE & );
	bool remove( const NODETYPE & );
	bool isEmpty() const;                  
    void print() const;
private:
	ListNode<typename NODETYPE> * Ptr_first;
	ListNode<typename NODETYPE> * Ptr_last;

	ListNode< NODETYPE > * getNewNode( const NODETYPE & );
};

template <typename NODETYPE>
LinkedList<NODETYPE>::LinkedList() : Ptr_first (0),Ptr_last(0)
{ }

template <typename NODETYPE>
LinkedList<NODETYPE>::~LinkedList()
{
	if (!isEmpty()) 
	{
		cout << "Destroying nodes..";
	}

	ListNode<NODETYPE> * Ptr_current = Ptr_first;
	ListNode<NODETYPE> * Ptr_temp;

	while (Ptr_current != 0)
	{
		Ptr_temp = Ptr_current;
		cout << Ptr_temp->data << "\n";
		Ptr_current = Ptr_temp->Ptr_Next;
		delete Ptr_temp;
	}

	cout << "All nodes are destroyed";
}

template <typename NODETYPE>
void LinkedList<NODETYPE>::addSorted(const NODETYPE &value)
{
	ListNode<NODETYPE> * Ptr_new = getNewNode(value);

	if (isEmpty())
	{
		Ptr_first = Ptr_new;
		Ptr_last = Ptr_new;
	}
	else
	{
		if (value < Ptr_first->data)
		{
			Ptr_new->Ptr_Next = Ptr_first;
			Ptr_first = Ptr_new;
			return;
		}

		ListNode<NODETYPE> * Ptr_current = Ptr_first->Ptr_Next;
		ListNode<NODETYPE> * Ptr_prev = Ptr_first;
		bool found = false;

		while (Ptr_current != 0)
		{
			if (value < Ptr_current->data)
			{
				Ptr_prev->Ptr_Next = Ptr_new;
				Ptr_new->Ptr_Next = Ptr_current;
				found = true;
			}

			Ptr_prev = Ptr_current;
			Ptr_current = Ptr_current->Ptr_Next;
		}

		if (!found)
		{
			Ptr_last->Ptr_Next = Ptr_new;
		}
	}
}

template <typename NODETYPE>
bool LinkedList<NODETYPE>::exists(const NODETYPE &value)
{
	ListNode<NODETYPE> * Ptr_current = Ptr_first;

	while (Ptr_current != 0)
	{
		if (Ptr_current->data == value)
		{
			return true;
		}

		Ptr_current = Ptr_current->Ptr_Next;
	}
	return false;
}

template <typename NODETYPE>
bool LinkedList<NODETYPE>::remove( const NODETYPE &value)
{
	if (isEmpty())
	{
		return false;
	}
	else
	{
		ListNode<NODETYPE> * Ptr_current = Ptr_first;
		ListNode<NODETYPE> * Ptr_next = Ptr_current->Ptr_Next;

		if (Ptr_current->data == value)
		{
			Ptr_first->Ptr_Next = Ptr_next;
			delete Ptr_current;
			return true;
		}
		else
		{
			while (Ptr_next != 0)
			{
				if (Ptr_next->data == value)
				{
					Ptr_current->Ptr_Next = Ptr_next->Ptr_Next;
					delete Ptr_next;
					return true;
				}

				Ptr_current->Ptr_Next = Ptr_next;
				Ptr_next = Ptr_current->Ptr_Next;
			}
		}
	}
	return false;
}

template <typename NODETYPE>
bool LinkedList<NODETYPE>::isEmpty() const
{
	return Ptr_first == 0;
}

template <typename NODETYPE>
void LinkedList<NODETYPE>::print() const
{
	cout << "print started\n";
	if (isEmpty())
	{
		cout << "The list is empty";
		return;
	}
	
	ListNode<NODETYPE> * Ptr_current = Ptr_first;

	while (Ptr_current != 0)
	{
		cout << Ptr_current->data << " ";
		Ptr_current = Ptr_current->Ptr_Next;
	}

	cout << "\n\n";
}

template <typename NODETYPE>
ListNode<NODETYPE> * LinkedList<NODETYPE>::getNewNode(const NODETYPE &value)
{
	return new ListNode<NODETYPE>(value);
}

#endif

BuiZe · 12 dec 2006

Code:

bool LinkedList<NODETYPE>::remove( const NODETYPE &value)
{
      ...
		ListNode<NODETYPE> * Ptr_current = Ptr_first;
		...
		if (Ptr_current->data == value)
		{
			Ptr_first->Ptr_Next = Ptr_next;
			[B]delete Ptr_current;[/B]
			return true;
		}

Je delete Ptr_current==Ptr_first, dus update je best ook Ptr_first naar Ptr_next, of bij een volgende aanroep wijst Ptr_first naar geinvalideerd geheugen.

Voor het tweede deel is de code niet helemaal netjes (middenin een return), maar ik zou eerder zoiets doen:

Code:

	while (Ptr_next != 0)
	{
		if (Ptr_next->data == value)
		{
			Ptr_current->Ptr_Next = Ptr_next->Ptr_Next;
			delete Ptr_next;
			return true;
		}
[B]
		Ptr_current = Ptr_next;
		Ptr_next = Ptr_next->Ptr_Next;[/B]
	}

Verder beschikken we niet over de klasse ListNode dus kan in principe daar ook iets misgaan in de destructor (if any).

jodeman · 12 dec 2006

Dat was geen probleem blijkbaar. Tmoest

Code:

bool LinkedList<NODETYPE>::remove( const NODETYPE &value)
{
      ...
		ListNode<NODETYPE> * Ptr_current = Ptr_first;
		...
		if (Ptr_current->data == value)
		{
			Ptr_first = Ptr_next; // DIT DUS
			[B]delete Ptr_current;[/B]
			return true;
		}

zijn. Maar dat kon ge niet goed zien omdat ge ListNode niet had. Sorry, had het er moeten bijzetten.
Return daar zetten doe ik gewoon voor performantie. Anders voert hij toch onnodige code uit of ben ik verkeerd?
Thanks!

Vich · 12 dec 2006

't Is offtopic, maar ik wil het toch even kwijt:
Je zou je klasse nog een klein beetje universeler kunnen maken als je bij addSorted een functiepointer naar een functie meegeeft die 2 items sorteert. Iets als:

template class
void SortNodes(NODETYPE*& nodeOne, NODETYPE*& nodeTwo);

Dan kan je in principe alles in je list zetten en sorteren, ook al heeft deze geen > of < operator. (sommige klassen zou je mbv andere voorwaarden kunnen sorteren)

jodeman · 12 dec 2006

ah dat wist ik niet, bedankt!

Archief - [PROG][C++] Linked list

jodeman

Legacy Member

BuiZe

Legacy Member

jodeman

Legacy Member

Vich

Legacy Member

jodeman

Legacy Member