3. Meine "verkettete Liste"!

Meine "verkettete Liste"!

  • B

    hey leute..
    ich habe mir hier eine kleine "list" klasse gebastelt die auf <list> aus der
    stl basiert..
    diesen kleinen skript habe ich mir selber zur erleichterung geschrieben und
    ich hoffe mal das ihr mit tips geben könnt wie ich diese klasse noch erweitern bzw. verbessern kann..da ich diesen skript für eine klausur verwenden möchte,
    sollte er "fehlerfrei" funktionieren..

    hier die klasse:

    template <class T> class Liste

{
public:
	Liste() {pos=data.begin();}
	//virtual ~Liste();

	void insert(T i) { data.push_back(i); }

	void insert(int i, T w) 
	{ 
		to_pos(i);
		data.insert(pos,w);
	}	

	T get_first() { return data.front(); }

	T get_last() { return data.back(); }

	int size() { return data.size(); }

	void swap(int q, int z)
	{
		T tmp_q = this->get(q);
		T tmp_z = this->get(z);
		this->del(q);
		this->insert(q, tmp_z);
		this->del(z);
		this->insert(z, tmp_q);
	}

	void replace(int i, T w)
	{
		this->del(i);
		this->insert(i, w);
	}

	T get(int i)
	{
		to_pos(i);
		T p = *pos;
		re_pos(i);
		return p;
	}

	void print()
	{
		tmp=pos;
		for(pos=data.begin();pos!=data.end();++pos) 
			cout << *pos;  
		pos=tmp;
	}

	void sort() { data.sort(); }

	void clear() { data.clear(); pos=data.begin();}

	void del(int i)
	{
		to_pos(i);
		data.erase(pos);
	}

	void show_pos()
	{ cout << *pos << endl; }

	void del_first() { data.pop_front(); }
	void del_last() { data.pop_back(); }

private:
	void to_pos(int i) { pos=data.begin(); for (int x=1; x<=i; x++) pos++;}
	void re_pos(int i) { for (int y=0; y<=i; y++) pos--;}

	list<T> data;
	list<T>::iterator pos;
	list<T>::iterator tmp;
};

    methoden der klasse:

    Liste<int> list;		//liste mit int werten erzeugen

	list.clear();			//löscht die liste
	list.del(0);			//löscht das element an der position 0
	list.del_first();		//löscht das erste element
	list.del_last();		//löscht das letzte element
	list.get(0);			//gibt das element an der position 2 zurück
	list.get_first();		//gibt das erste element zurück
	list.get_last();		//gibt das letzte element zurück
	list.insert(0, 23);		//fügt an der position 0 das element 23 ein
	list.insert(23);		//fügt ans ende der liste das element 23 ein
	list.print();			//gibt alle elemente der liste aus
	list.replace(0, 23);		//tauscht das element an der position 0 mit dem element 23 aus
	list.show_pos();		//gibt das element der aktuellen position aus
	list.size();			//gibt die anzahl der elemente in der liste zurück
	list.sort();			//sortiert die elemente der liste von a-z
	list.swap(0, 5);		//tauscht das element von der position 0 mit der position 5 aus

    würde mich über ein paar feedbacks freuen!

    0
  • .

    1. Wofür brauchst du das?

    2. Die Membervariable tmp ist Quatsch.

    3. show_pos . to_pos entspricht einem Indexoperator.

    4. get ist Quatsch (siehe 3)

    5. swap bedeutet für STL-Container etwas anderes. Was du meinst ist std::swap

    6. Es gibt einen Grund, warum man auf Listen nicht mit Indizes sondern Iteratoren arbeitet ...

    7. print entspricht:

    std::copy (liste.begin(), liste.end(), std::ostream_iterator<char> (std::cout, ' ');

    8. replace ist viel ineffektiver als nötig.

    0
  • B

    ich kenne mich mit der stl leider nicht so gut aus..habe mich quasi erst heute damit richtig beschäftigt!

    da ich viel mit listen zutun habe, wollte ich die stl mal ausprobieren und dachte mir das ich meine methoden die ich habe durch die stl methoden ersetzen kann..vielleicht ist das schwachsinn aber für mich, der so gut wie kein plan von der stl hat, ist das komfortabler zu benutzen..

    ich dachte auf stl listen ist kein indexoperator möglich?

    0
  • G

    brainwave81 schrieb:

    ich dachte auf stl listen ist kein indexoperator möglich?

    korrekt, du kannst nur mit Iteratoren auf einer std::list operieren. Der Index-Op müsste sich ja vom Ersten bzw. Letzten Element zum ausgewählten hangeln (das im Ungünstigsten Fall in der Mitte rumgurkt). Bei einem Array (bzw. vector) kann er einfach hinspringen, denn der Compiler weiß ja, wie groß ein einzelnes Element ist und so ist er ruck-zuck beim gewünschten Element.

    MfG

    GPC

    0
  • B

    diese möglichkeit habe ich doch mit to_pos() und re_pos() genutzt, oder?!

    0
  • .

    brainwave81 schrieb:

    ich dachte auf stl listen ist kein indexoperator möglich?

    Von "möglich" kann nicht die Rede sein. Es ist nur extrem ineffektiv. Ich habe auch nicht gesagt, dass du einen machen sollst, sondern dass du einen hast und das gebührend bemängelt 😉 :

    .filmor schrieb:

    3. show_pos . to_pos entspricht einem Indexoperator.
    4. get ist Quatsch (siehe 3)
    6. Es gibt einen Grund, warum man auf Listen nicht mit Indizes sondern Iteratoren arbeitet ...

    Mit show_pos . to_pos ist "Ausführung von show_pos nach to_pos" gemeint. Haskell ist toll 😉

    0
  • J

    Ja, das machst Du. Bei einer Liste muß man allerdings durchlaufen (so wie du das auch machst). Dadurch ist das ganze erheblich viel langsamer. Praktisch sozusagen nicht einsetzbar. Daher macht es keinen Sinn das anzubieten.

    0
  • B

    auf die performance wird hier kein rücksicht genommen 😉
    wie gesagt, ich muss eine liste schnell parat haben..

    ich muss mich auch nach graphen und bäume informieren..kennt ihr
    gute seiten wo die stl gut beschrieben ist? (was bäume und graphen anbetrifft!)

    0
  • J

    brainwave81 schrieb:

    auf die performance wird hier kein rücksicht genommen 😉
    wie gesagt, ich muss eine liste schnell parat haben..

    Dann lern doch lieber std::list richtig zu benutzen, statt Dir so ein Monstrum zu bauen, das auch noch die Laufzeit drückt. Dann hast Du's auch schnell parat. Ich weiß nicht, ob Dir das O-Kalkül was sagt, aber wenn Du einen Algorithmus, der mit nem std::vector O(n) Laufzeit hat für Deine Liste ganz naiv hinschreibst wird das plötzlich O(n^2) Laufzeit haben, was deutlich schlechter ist.

    ich muss mich auch nach graphen und bäume informieren..kennt ihr
    gute seiten wo die stl gut beschrieben ist? (was bäume und graphen anbetrifft!)

    Graphen gibt's nicht in der STL, bei boost (www.boost.org) ist da aber was zu finden. Für (Such)Bäume schau Dir mal std::map an. Generell lohnt sich vielleicht ein Blick auf www.cppreference.com

    0
  • B

    ich werde versuchen mich näher mit der stl zu beschäftigen..scheint viele
    vorteile mit sich zubringen..

    was graphen oder bäume anbetrifft, gibt es doch sowas wie "maps" wenn ich mich nicht täusche, oder?

    0
  • J

    Ja, std::map. Aber für graphen gibt's nix fertiges.

    0
  • ?

    brainwave81 schrieb:

    ich werde versuchen mich näher mit der stl zu beschäftigen..scheint viele
    vorteile mit sich zubringen..

    http://www.informatik.hs-bremen.de/~brey/stlb.html 😉

    0
  • B

    vielen dank! 😉

    0
Anmelden zum Antworten