Problem mit Zeigern in einer verketteten Liste

Nozdrum

Ich möchte mir eine verkette Liste erstellen, dafür habe ich mir erstmal zwei Datensätze erstellt:

struct inh{
	inh *next;
	int wert;
};

struct l_typ{
	inh anf,pos;
};

Zuerst der Inhaltstyp, wobei hier irgendein Wert gespeichert werden soll und natürlich der Verweis auf das nächste Listenelement.
Der Listentyp dann ist auch wieder ein Datensatz bestehend aus einem starren Anfangselement und meinem Positionselement, welches das genutzt werden soll die Liste zu durchlaufen.

Dann habe ich mir noch zwei Funktionen erstellt bei denen ich mir, aufgrund meiner geringen Erfahrung mit Zeigern, nicht sicher bin ob sie so richtig sind.
Liste erstellen:

void l_create(l_typ& liste)
{
	liste.anf.wert = 0;
	liste.anf.next = NULL;
	liste.pos = liste.anf;
};

Und ein Listenelement hinzufügen:

void l_add_element(l_typ& liste, int v)
{
	while (liste.pos.next != NULL )
		liste.pos = *liste.pos.next;//Springe ich so wirklich zum nächsten Listenelement?
	liste.pos.next  = new inh;
	liste.pos.next->next = NULL;//Mit dem -> Operator veränder ich doch den Wert auf den der Zeiger zeigt?
	liste.pos.next->wert = v;
};

Hoffe ihr könnt mir helfen

Hi Nozdrum,

struct l_typ{
    inh anf,pos; // An dieser Stelle wäre ein Zeiger sicherlich sinnvoller
    // und der Zeiger auf eine Position ist denke ich auch keine Member-Variable ... (oder ist es nen Zeiger auf last?)
    inh* anf;
};

Ansonsten Erstellst du dir bei jeder Wertzuweisung eine Kopie des Objektes, das
du zuweist.
z. B. hier erstellst du eine Kopie:

liste.pos = *liste.pos.next;//Springe ich so wirklich zum nächsten Listenelement?

und in l_create erzeugst du auch eine Kopie:

void l_create(l_typ& liste)
{
    liste.anf.wert = 0;
    liste.anf.next = NULL;
    liste.pos = liste.anf; // Hier!!! Folglich sind anf und pos verschiedene
    // Speicherbereiche und eine Änderung eines Wertes, ändert den anderen nicht...
};

Zur Verdeutlichung:

int main(){

	l_typ liste;
	liste.anf.wert = 22;
	liste.anf.next = NULL;
	liste.pos = liste.anf;
	std::cout << liste.anf.wert << std::endl;
	std::cout << liste.pos.wert << std::endl;
	liste.anf.wert = 23;
	std::cout << liste.anf.wert << std::endl;
	std::cout << liste.pos.wert << std::endl;
	return 0;
}

AUSGABE:

22
22
23
22

Gruß,
CSpille

Nozdrum

Danke für die Antwort CSpille.

Also mein neues Datenkonzept:

struct inh_typ{
     inh_typ *next;
     int wert;
 };

 struct l_typ{
     inh_typ *anf,*pos;
 };

Jetzt habe ich mir das so gedacht:

void l_create(l_typ& liste)
{
	liste.anf->next = NULL;
	liste.anf->wert = 0;
	liste.pos->next = NULL;
	liste.pos->wert = 0;
};
void l_add_element(l_typ& liste,int v)
{
	while ( liste.pos->next != NULL )
		liste.pos = liste.pos->next; 
	liste.pos->next = new inh_typ;
	liste.pos->next->next = NULL;
	liste.pos->next->wert = v;
};

Im main-Teil steht dann als Bsp:

int main()
{
	l_typ liste;
	l_create(liste);
	l_add_element(liste,10);
	return 0;
};

Jedoch bekomme ich da Fehler wegen Speicherverletzung schon in l_create bei der ersten Anweisung

drakon

Naja. Das Problem ist, dass du bei l_create davon ausgehst, dass

liste.anf->next = NULL;

hier bereits ein Element dort drinn ist.

Also schau dir das mal an:

liste.anf->next = NULL; //liste ist ja eine Referenz auf:

l_typ liste; // aber das hier ist ja lediglich:

 struct l_typ{
     inh_typ *anf,*pos; //und hier hast du ja einen zeiger drin, der nicht auf ein gültiges Objekt zeigt..
 };

Naja.. Hier besteht noch viel Verbesserungspotenzial. Wenigstens deleten solltest du die Elemente wieder, wenn du die mal in einer Liste hast..

Nozdrum

drakon schrieb:

Naja. Das Problem ist, dass du bei l_create davon ausgehst, dass
liste.anf->next = NULL;
hier bereits ein Element dort drinn ist.

Ahh Danke. So funzt es:

void l_create(l_typ& liste)
{
	liste.anf = new inh_typ;
	liste.pos = liste.anf;
	liste.anf->next = NULL;
	liste.anf->wert = 0;
};

drakon schrieb:

Naja.. Hier besteht noch viel Verbesserungspotenzial. Wenigstens deleten solltest du die Elemente wieder, wenn du die mal in einer Liste hast..

Hehe. Wie delete ich ein Element dann wieder? Oder meinst die eine delete-Funktion wo die Werte wieder frei gegeben werden?

drakon

Du weisst ja, dass man alles, dass man per new Operator anfordert auch weider von dir freigegeben werden muss per delete/delete[]..

hier die hatte ich mal geschrieben, weil ich nem kumpel beweisen wollte, dass die qlist aus qt4 fehlerhaft wäre... es stellte sich raus, das meine liste das selbe verhalten zeigte^^ aber ich konnte so den fehler besser finden.
nicht böse sein, ich war im rausch als ich sie geschrieben hatte und sie jetzt auch etwas kompliziert...
weis jemand wie man iteratoren hinzufügen kann? wäre ganz witzig wenn man als forumspiel diese liste verbessert oder/und erweitert.

#include <iostream>

template <class T>
class vector
{
private:
	T *data;

public:
	//! eigentlich priv
	int index;
	vector *next;
	vector *prev;

	//!konstruktor
	vector();
	vector(T &v);
	vector(vector &v);
	~vector();

	//! setter
	bool push_back(T data);
	//! cleaner
	void removeAt(int i);
	void clear();
	//! getter
	T get_last();
	T get_first();
	T at(int index);
}; 

//! konstrukoren & destruktoren
template <class T>
vector<T>::vector() {
	next = NULL;
	prev = NULL;

	index = 0;
	data = new T;
}

template <class T>
vector<T>::~vector()
{

}

//! daten-settups
template <class T>
bool vector<T>::push_back(T data) {
	vector *new_node = new vector;
	*new_node->data = data;
	new_node->next = NULL;

	//verknüpfung zum alten beim neuen element
	new_node->prev = this->next;

	//verknüpfung zum neuen beim alten element
	this->next = new_node;

	new_node->index = index;
	index++;
}

//! getter
template <class T>
T vector<T>::get_last()
{
	if(next->data != NULL)
		return *next->data;
}

template <class T>
T vector<T>::get_first()
{
	vector *old_pointer = next;

	while(true) {
		if(next->index == 0) {
			T data;
			if(next->data != NULL)
				data = *next->data;
			next = old_pointer;
			return data;
		}
		else {
			next = next->prev;
		}
	}
}

//! getter
template <class T>
T vector<T>::at(int ind)
{
	vector *old_pointer = next;

	if(ind > index-1)
		return *next->data;
	if(ind < 0)
		return get_at(0);

	while(true) {
		if(next->index == ind) {
			T data;
			if(next->data != NULL)
				data = *next->data;
			next = old_pointer;
			return data;
		}
		else {
			next = next->prev;
		}
	}
}

//! cleaner
template <class T>
void vector<T>::clear()
{
	vector *old_pointer = next;

	for(int i = 0; i < index; i++) {
		old_pointer = next;
		next = next->prev;

		delete old_pointer;
	}
}

template <class T>
void vector<T>::removeAt(int ind)
{
	vector<T> *temp = new vector<T>;
	T buffer[index];

	for(int i = index-1; i >= 0; i--) {
		T data = *next->data;
		buffer[i] = data;
		next = next->prev;
	}

	for(int i = 0; i < index; i++) {
		if(i != ind) {
			temp->push_back(buffer[i]);
		}
	}

	next = temp->next;
}

drakon

Also gute Listen gibt es hier im Forum bereits zur genüge. - Und auch wie man Iteratoren dazu schreibt. Musst nur danach suchen..