Doppelt verkettete Liste umordnen

C

carlos1976

Grünschnabel
Hallo zusammen und noch ein frohes Neues!

Ich habe ein Problem damit, eine doppelt verkettete Liste umzuorden.

Liste----A-----B-----C----D soll später folgendes Aussehen haben:

Liste----B-----D-----A----C

Das Umsortieren soll nur durch Verschieben der Zeiger erfolgen (aso kein Löschen oder Einfügen nötig).

Jedes Element der Liste besitzt neben den Daten noch einen Next- und prev-Zeiger zum Nachfolger/Vorgänger.

first->__ A-----------B---------C----------D

______Next____Next___Next___Next --> Null
null<-__prev____prev___ prev___prev

first verweist auf das erste Listelement der Sequenz. Next ist Teil des Listenelements und verweist auf den jeweiligen Nachfolger bzw. ist NULL für das letzte Listenelement. Der prev-Zeiger verweist auf das vorhergehende Listenelementbei dem ersten Element der Liste wird prev auf NULL gesetzt.

Wie schaffe ich es mit den beiden Funktionen (s.u.) die Elemente an das Ende/den Anfang zu verschieben?

Code: 
//Element ans Ende schieben
void List::moveToEnd(ListElem* elemMove)
{
	if(!isEmpty())
	{
		if ( elemMove != NULL ) 
		{
			//Zwei neue Pointer: Der Vorgänger des zu verschiebenden...
			ListElem* elemPrev = elemMove->getPrev();
			//...und der Nachfolger
			ListElem* elemNext = elemMove->getNext();
			//		
		}
	}
}

//Element an den Anfang schieben 
void List::moveToFront(ListElem* elemMove)
{
	//Wenn die Liste nicht leer ist...
	if (!isEmpty())
	{
		//Kann eigentlich nicht passieren, aber sicher ist sicher...
		if ( elemMove != NULL ) 
		{
			//Zwei neue Pointer: Der Vorgänger des zu verschiebenden...
			ListElem* elemPrev = elemMove->getPrev();
			//...und der Nachfolger
			ListElem* elemNext = elemMove->getNext();
			//
		}
	}
}
 
Wie sieht denn die Funktion isempty()? aus

Du musst natürlich "die Lücke" füllen und die anderen "nachschieben". Also wenn du z.B. Element 3 an den Anfang
bringen willst und es das letzte Element ist, musst du folgendes tun:
  • first=E3
  • E2->Next=NULL

Sonst:
  • E2->Next=E4
  • E4->Prev=E2

Ich hoffe, ich habe kein Denkfehler

EDIT: Um ein Element ans Ende zu bringen musst du seinen Vor- und Nachfolger ändern sowie das letzte Element
 
Hallo,

vielleicht hilft es ja, wenn du die Operationen in zwei Einzelschritte zerlegst. Beispiel:

Code: 
        front
          |
          v
NULL <--- A <--> B <--> C <--> D ---> NULL

moveToFront(C)
==============

C "aushängen":
        front
          |        ___________
          v       /           `v
NULL <--- A <--> B      C      D ---> NULL
                 ^.___________/

C neu "einhängen" (zwischen front und front.next):
        front
          |
          v
NULL <--- C <--> A <--> B <--> D ---> NULL
Ein moveToFront ist also nichts anderes als ein Delete gefolgt von einem insertFront. Für moveToEnd entsprechend mit insertEnd.

Grüße,
Matthias
 
Thx für die Hilfe!

an Delet und InsertFront hatte ich auch schon gedacht, aber man soll das ja nur durch "verschieben" der Zeiger hinbekommen....:confused:

Hier nochmal der gesamte Code und die Header Datei :

Code: 
#include "liste.h"

/************************************************************************/
/* Klasse ListElem                                                      */
/************************************************************************/

ListElem::ListElem(string data)
{
	this->data = data;
	next = NULL;
	prev = NULL;
}

string ListElem::getData(void) const
{
	return data;
}

void ListElem::setNext(ListElem* elem)
{
	next = elem;
}

ListElem* ListElem::getNext() const
{
	return next;
}

void ListElem::setPrev(ListElem* elem)
{
	prev = elem;
}

ListElem* ListElem::getPrev() const
{
	return prev;
}

/************************************************************************/
/* Klasse List                                                          */
/************************************************************************/

List::List()
{
	first = NULL;
}

List::~List()
{
	while (!isEmpty()) 
	{
		removeFirst();
	}
}

//am Ende anhängen
void List::append(string data)
{
	ListElem *newElem = new ListElem(data);
	if(!isEmpty())
	{
		ListElem *curr = first;
		while(curr->getNext() != NULL)
		{
			curr = curr->getNext();
		}
		curr->setNext(newElem);
		newElem->setPrev(curr); //
	}
	else
	{
		first = newElem;
	}
}


// Löschen am Anfang
void List::removeFirst(void)
{
	if ( isEmpty() ) return;

	// Zu löschendes Element
	ListElem* delElem = first;

	first = first->getNext();
	if(first != NULL)
	{
		first->setPrev(NULL);
	}
	delete delElem;    // lösche Listenelement
	
	
}

//Element ans Ende schieben
void List::moveToEnd(ListElem* elemMove)
{
	if(!isEmpty())
	{
		if ( elemMove != NULL ) 
		{
			//Zwei neue Pointer: Der Vorgänger des zu verschiebenden...
			ListElem* elemPrev = elemMove->getPrev();
			//...und der Nachfolger
			ListElem* elemNext = elemMove->getNext();

			/************************************************************************/
			/* ?wie verschieb ich hier die Zeiger?                       
			/************************************************************************/


		}
	}
}


//Element an den Anfang schieben 
void List::moveToFront(ListElem* elemMove)
{
	//Wenn die Liste nicht leer ist...
	if (!isEmpty())
	{
		//Kann eigentlich nicht passieren, aber sicher ist sicher...
		if ( elemMove != NULL ) 
		{
			//Zwei neue Pointer: Der Vorgänger des zu verschiebenden...
			ListElem* elemPrev = elemMove->getPrev();
			//...und der Nachfolger
			ListElem* elemNext = elemMove->getNext();

			/************************************************************************/
	        	/* ?wie verschieb ich hier die Zeiger?               
			/************************************************************************/

			//...

		}
	}
}


//Element an den Anfang schieben: Die Funktion wird in der main-Methode aufgerufen, 
//ihr wird ein string übergeben. Sie sucht in der Liste das Listenelement, welches
//den gesuchten String enthält. Wenn kein solches Listenelement vorhanden ist, 
//gibt sie dies aus. 
//Wurde das passende Element gefunden, wird moveToFront(ListElem* moveElem) aufgerufen. 
void List::moveToFront(const string& s)
{
	if (!isEmpty())
	{
		// Aktuelles Element 
		ListElem* e = find(s);
		if (e != NULL) {
			moveToFront(e);
		} else {
			cout << "Zu verschiebendes Element nicht gefunden!" << endl;
		}
	}
}

//Element ans Ende schieben: Die Funktion wird in der main-Methode aufgerufen, 
//ihr wird ein string übergeben. Sie sucht in der Liste das Listenelement, welches
//den gesuchten String enthält. Wenn kein solches Listenelement vorhanden ist, 
//gibt sie dies aus. 
//Wurde das passende Element gefunden, wird moveToEnd(ListElem* moveElem) aufgerufen. 

void List::moveToEnd(const string& s)
{
	if (!isEmpty())
	{
		ListElem* e = find(s);
		if (e != NULL) 
		{
			moveToEnd(e);
		}
		else 
		{
			cout << "Zu verschiebendes Element nicht gefunden!" << endl;
		}
	}
}


ListElem* List::find(const string &d)
{
	ListElem* result = first;
	while ( result != NULL && result->getData() != d ) 
	{
		result = result->getNext();
	}
	return result;
}

const ListElem* List::getFirst()
{ 
	return first; 
}

bool List::isEmpty(void) 
{ 
	return first == NULL; 
}

//Global deklarierte Funktionen zum Ausgeben der Liste (Von vorn nach hinten)
void printList(List &list)
{
	const ListElem* curr; // Zeiger auf das aktuelle Element
	curr = list.getFirst();// Beginne beim ersten Element
	cout << "Rentier --- ";
	while( curr != NULL ) 
	{
		// tu etwas mit dem Element (hier ausdrucken)
		cout << curr->getData() << " --- ";
		// gehe zum nächsten Listenelement
		curr = curr->getNext();
	}
	cout << endl;
}

//Global deklarierte Funktion zum Ausgeben der Liste (Von hinten nach vorn)
void printListBackwards(List &list)
{
	const ListElem* curr; // Zeiger auf das aktuelle Element
	curr = list.getFirst();// Beginne beim ersten Element
	while( curr->getNext() != NULL ) 
	{
		// gehe zum nächsten Listenelement
		curr = curr->getNext();
	}
	//jetzt sind wir ganz hinten, also gib die Daten aus und geh eins vorwärts
	while(curr->getPrev() != NULL)
	{
		cout << curr->getData() << " --- ";
		curr = curr->getPrev();
	}
	cout << curr->getData() << " ";
	cout << " --- Rentier";	
	cout << endl;
}

int main(void)
{
	List gespann; // Das Rentiergespann, noch ohne Schlitten...
	
	gespann.append("A");	//Schlitten für Dorf A
	gespann.append("B");	//Schlitten für Dorf B
	gespann.append("C");	//Schlitten für Dorf C
	gespann.append("D");	//Schlitten für Dorf D

	cout << "Rentiergespann zu Beginn der Ausfahrt...\n";
	printList(gespann);
	printListBackwards(gespann);
		
	/************************************************************************/
	/* /* Hier soll das eigentlich umsortiren erfolgen..                                                              */
	/************************************************************************/
	
	cout << "Rentiergespann nach erfolgreichem Umsortieren der Schlitten...\n";
	printList(gespann);
	printListBackwards(gespann);

	return 0;

}



Code: 
#ifndef 
#define 

#include <iostream>
#include <string>

using namespace std;

class ListElem
{
public:
	ListElem(string s);

	string    getData(void) const;
	ListElem* getNext(void) const;
	ListElem* getPrev()     const;

	void setNext(ListElem* elem);
	void setPrev(ListElem* elem);

private:
	string data;
	ListElem *next;
	ListElem *prev;
};

class List
{
public:
	List();
	~List();

	// Einfügen am Anfang
	void append(string data);
	
	// Löschen
	void removeFirst(void);
	
	// Verschieben
	void moveToEnd(const string& s);   
	void moveToFront(const string& s);

	// Abfragen
	bool isEmpty(void); 

	// Zugriff auf Listenelemente
	const ListElem *getFirst();

// PRIVATE MEMBERFUNKTIONEN
private:
	void moveToEnd(ListElem* e);
	void moveToFront(ListElem* e);
	ListElem* find(const string &d);

// PRIVATE MEMBERVARIABLEN
private:
	ListElem* first;
};

#endif
 
Zuletzt bearbeitet:
Eine kleine Anmerkung: Wieso deklarierst du NEXT und PREV in private?
Es wäre doch schneller, wenn du direkt darauf zugreifs, als auf eine Funktion, die sowieso nur diese Eigenschaft setzt.

Ich habe noch die Funktion getEnd verwendet, Definition siehe unten.

Code: 
void List::moveToEnd(ListElem* elemMove)
{
	if(!isEmpty() && elemMove!=NULL)
	{
                      if (elemMove==first)  // Element am Anfang
                      {
                        first = elemMove->getNext();
                        getEnd()->getNext = elemMove;
                      }
                      if (elemMove!=first && elemMove!=getEnd())  // Element in der Mitte
                      {
                        elemMove->getPrev()->getNext() = elemMove->getNext;
                        getEnd()->getNext = elemMove;
                      }
                }
        }
}

Ich würde außerdem noch die Funktion ListElem *List::getEnd() implenmentieren:

Code: 
ListElem *List::getEnd()
{
  ListElem *curr = first;
  while(curr->getNext() != NULL)
  {
    curr = curr->getNext();
  }
  return curr;
}

Vielleicht schaffst du ja moveToFront alleine?

EDIT: Die Funktion getEnd ist im Prinzip von dir schonmal benutzt worden: bei append()
Vielleicht hilft dir es, wenn du ein Bild mit Pfeilen auf Papier malst
 
Zuletzt bearbeitet:
Wenn du ohne getEnd auskommen willst, kannst du moveToEnd beispielsweise so implementieren:

C++: 
void List::moveToEnd(ListElem* elemMove)
{
  if(!isEmpty() && elemMove!=NULL)
  {
    while (elemMove->getNext() != null)  
	{
	  elemMove->getNext()->setPrev(elemMove->getPrev());
	  elemMove->getPrev()->setNext(elemMove->getNext());
	  elemMove->setPrev(elemMove->getNext());
	  elemMove->setNext(elemMove->getPrev()->getNext());
	  elemMove->getPrev()->setNext(elemMove);
	  if ( elemMove->getNext() != null }
	  { elemMove->getNext()->setPrev(elemMove); }
	}
  }
}

moveToFront kannst du dann entsprechend programmieren, aber achte genau auf die Reihenfolge, in der du die Zeiger manipulierst!
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück