Verbesserungsvorschläge, Erweiterungen für meine class list (einfacher verkettete liste)

David_pb

Hi!

Iteratoren würd ich auch vorschlagen.

o Eine Methode um Knoten vor/hinter beliebigen Knoten einzufügen wäre ganz nett.
o Eine Methode um Knoten zu löschen
o Eine Methode um einen bestimmten Knoten zu suchen

Das überladen des [] Operators ist bei verlinkten Listen natürlich Unsinn.
Achja, ich würde einen Zeiger auf das erste Element zeigen lassen und einen auf das letzte. Dann kannst du dir das iterieren bei der Methode Push_Back sparen.

grüße

Erhard Henkes

http://www.wachtler.de/informatik_2/node59.html#loes:einfacheliste

kann mir jemand einen ansatz geben wie ich hier iteratoren einsetze? hm

Erhard Henkes

http://hal.iwr.uni-heidelberg.de/lehre/inf1-ws02/html/node125.html
http://hal.iwr.uni-heidelberg.de/lehre/inf1-ws02/html/node126.html
http://wwwcs.uni-paderborn.de/~tauber//tauber_files/vorlesungen/dvm2/dvm5_1.pdf

aso danke....der iterator ist ja nur ne klasse mit nem zeiger auf einen knoten...
soll ich dann auch anstatt

node *root;

einen interator der auf das erste element und einen iterator der auf das letzte element zeigt nehmen?

beim einfügen des ersten knotens, zeigen da first und last auf den knoten?

David_pb

Entweder so oder du nutzt sog. sentinel Nodes. Also quasi ein dummy Knoten der von Außen nicht sichtbar ist. Nach dem Initialisieren zeigen dann first und last auf dieses Dummy. Wenn dann das erste Element eingefügt wurde musst du darauf achten last wirklich auf das letzte Element zeigen zu lassen.

grüße

bin jetzt am bauen der iterator klasse! soll ich dann node *first; und node *last; auch durch iteratoren ersetzen?
wie mach ich dann aber mit dem iterator folgendes:

node *d = first->next;

operator++() überladen und d = ++first;

?
für delete d; muss ich mir halt noch was überlegen...

cu

groovemaster

-cpp- schrieb:

bin jetzt am bauen der iterator klasse! soll ich dann node *first; und node *last; auch durch iteratoren ersetzen?

Würde ich nicht machen. Iterators sind ja hauptsächlich für Clients gedacht, also für die Leute, die diese Klasse verwenden, damit sie über die einzelnen Elemente iterieren können und Zugriff auf die Daten der Elemente bekommen. Intern kannst du weiterhin Zeiger verwenden.

hi, nun die klasse mit iterator erweitert...ich weiss der operator-- () ist nicht effizient! wie kann ich den operator-> () implementieren bzw dann aufrufen? fallen euch sonst noch verbesserungen ein?

#include <iostream>
#include <cassert>

class list
{
private:
	struct node 
	{
		int x;
		node *next;
		node(int x): x(x) {}; 
	};
public:
	class iterator
	{
	private:
		node *item_first;
		node *item;
	public:
		iterator();
		iterator& operator= (const iterator& iter);
		bool operator== (const iterator& iter);
		bool operator!= (const iterator& iter);
		iterator operator++ ();
		iterator operator-- ();
		int& operator* () const;
		friend class list;
	};
	iterator begin() const;
	iterator end() const;
private:
	node *first;
	node *last;
	int count;
public:
	list(): first(0), last(0), count(0) {};
	~list();
	friend std::ostream &operator<<(std::ostream &os, const list &t); 
	void push_front(int x);
	void push_back(int x);
	void pop_front();
	void pop_back();
	void swap(const int pos1, const int pos2);
	int size() { return count; }
	bool is_empty() { return first == 0; }
};

list::iterator list::begin() const
{
	list::iterator tmp;
	tmp.item_first = first;
	tmp.item = first;
	return tmp;
}

list::iterator list::end() const
{
	list::iterator tmp;
	tmp.item = last;
	return tmp;
}

list::iterator::iterator()
{
	item_first = 0;
	item = 0;
}

list::iterator& list::iterator::operator= (const iterator& iter)
{
	assert(&iter);
	// Zuweisung auf sich selbst abfangen!
    if (this == &iter)
        return *this;

	item_first = iter.item_first;
	item = iter.item;	
	return *this;
}

bool list::iterator::operator== (const iterator& iter)
{
	assert(this);
	assert(&iter);
	return this->item == iter.item;
}

bool list::iterator::operator!= (const iterator& iter)
{
	assert(this);
	assert(&iter);
	return this->item != iter.item;
}

int& list::iterator::operator* () const
{
	assert(item);
	return item->x;
}

list::iterator list::iterator::operator++ ()
{
	assert(item);
	item = item->next;
	return *this;
}

list::iterator list::iterator::operator-- ()
{
	assert(item);
	list::iterator tmp;
	tmp.item = item_first;

	while(tmp.item->next != item)
	{
		tmp.item = tmp.item->next;
	}

	item = tmp.item;
	return *this;
}

std::ostream &operator<<(std::ostream &os, const list &t)
{
	assert(t.first);
	list::node *tmp = t.first;

	while(tmp != 0) 
	{
		os << tmp->x << std::endl;
		tmp = tmp->next;
	}

	return os;
}

list::~list()
{
	node *tmp;

	while(first != 0)
	{
		tmp = first;
		first = first->next;
		delete tmp;
	}
}

void list::push_front(int x)
{
	node *newnode = new node(x);
	newnode->next = first;
	first = newnode;
	if(last == 0) {
		last = newnode;
		last->next = 0;
	}
	count++;
}

void list::push_back(int x)
{
	node *tmp = first;
	node *newnode = new node(x);

	if(first == 0)
	{
		first = newnode;
	}
	else
	{
		// zum letzen knoten gehen
		while(tmp->next != 0)
		{
			tmp = tmp->next;
		}

		// neuen knoten an den letzten knoten anfuegen
		tmp->next = newnode;
		last = newnode;
	}

	newnode->next = 0;
	count++;
}

void list::pop_front()
{
	node *tmp = first;
	if(first != 0)
	{
		if(first->next != 0)
			first = first->next;
		else
			first = last = 0;

		delete tmp;
		count--;
	}
}

void list::pop_back()
{
	node *tmp = first;
	node *d = last;

	if(first != 0)
	{
		if(first->next != 0)
		{
			//beim vorletzten knoten stehen bleiben 
			while(tmp->next->next != 0)
			{
				tmp = tmp->next;
			}
			// d auf letzten knoten zeigen, diesen wollen wir loeschen
			d = tmp->next;
			// last auf letzten knoten zeigen
			last = tmp;
			last->next = 0;
		}
		else
			first = last = 0;

		delete d;
		count--;
	}
}