Permutationen einer linearen Liste

D

Dantesa

Grünschnabel
Hi,

wie der Threadtitel schon sagt, soll ich alle Permutationen von n Zahlen ausgeben, die in einer linearen Liste stehen (template Klasse)

Nun is bei mir irgendwie der Wurm drin !
Den Weg kenne ich, aber irgendwie scheiterts an der Umsetzung !
Bekomme immer folgende Fehlermeldung :

Eine nicht behandelte Ausnahme des Typs "System.AccessViolationException" ist in Liste2222.exe aufgetreten.

Zusätzliche Informationen: Es wurde versucht, im geschützten Speicher zu lesen oder zu schreiben. Dies ist häufig ein Hinweis darauf, dass anderer Speicher beschädigt ist.


-------------------

Hantiere nicht gerne mit Zeigern, da wird wahrscheinlich auch der Fehler liegen !

Hier mein Code :

Code: 
// ListePermutationen.cpp: Hauptprojektdatei.

#include "stdafx.h"
# include <iostream>
# include <string >
using namespace std ;

template <class T>
class List ; // forward reference

 template <class T>
 class ListNode
 { 
	 friend class List <T>;
 
 public :

	 ListNode (T& t , ListNode<T>* p) : data ( t ) , next (p) { }

 protected :
 
	 T data ; // data field
	 ListNode<T>* next ; // points to next

} ;

template <class T>

class List
{ 
public :

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

	void insert (T t ) ;
	int remove (T& t ) ;
	bool isEmpty ( ) { return ( first==NULL) ; }
	void print ( ) ;
	unsigned int size();
	void permutiere(List<T> m){
		List<T> temp = *this;
		permute(m,temp);
	}

	void permute( List<T>,List<T>);
	T last();

	


protected :

	ListNode<T>* first ;
	
	ListNode<T>* newNode(T& t ,ListNode<T>* p){ 
		
		ListNode<T>*q = new ListNode<T>( t , p ) ;
		return q ;
 
	}

 } ;

 int main ( ){ 
	 

	 unsigned int  n;
	
	 List <int> Menge;
	 List<int> Menge1;
	 cout<<"Wie groß ist die Menge ? "<<endl;
	 cin>>n;

	 for(int i = n ; i >=1;i--) Menge.insert(i);

	 Menge.print();
	 cout<<endl<<endl;	 
	 Menge.permutiere(Menge1);

	 cin>>n; 
	 return 0 ;
 }

 template <class T>
 List<T>::~List(){
	 ListNode<T>* temp;
	 
	 for(ListNode<T>* p = first;p;){

		 temp = p;
		 p = p->next;
		 delete temp;

	 }

 }

 template <class T>
 void List<T>::insert(T t){

	 ListNode<T> * p = newNode(t,first);
	 first = p ;
 }

 template <class T>
 void List<T>::print(){

	 for(ListNode<T>* p=first ; p; p = p->next)
		 cout<<p->data <<" ";
	

 }

 template <class T>
 unsigned int List<T>::size(){
	 
	 int n;
	 ListNode<T>* p=first;

	 while(p){
		 
		 n++;
		 p=p->next;
	 }

	 return n;
 }




 


template <class T>
int List<T>::remove(T& t){

	if(isEmpty()) return 0;

	t=first->data;
	ListNode<T>*p = first;
	first = first->next;
	delete p;

	return 1;

}


template <class T>
T List<T>::last(){

	ListNode<T>* p=first;

	while(p->next){
		p=p->next;
	}

	return p->data;

}


template <class T>
void List<T>::permute(List<T> fest,List<T> string){

	//cout<<"fest = ";
	//fest.print();


	if(string.size() <= 1){

		string.print();
		fest.print();
		
		cout<<endl;

	}

	else {
		
		for(ListNode<T> * p = string.first; p->data < string.last() ;p=p->next){
			
			fest.insert(p->data);
			string.remove(p->data);
			permute(fest,string);
			string.insert(p->data);
			//cout<<"S string = ";
			//string.print();
			//cout<<endl;
		}


	}



}

Danke für Eure Hilfe :)
 
Willkommen bei tutorials.de :D

Ja, die Fehlermeldung deutet ziemlich sicher auf ein Pointerproblem hin.

Werd mir den Code einmal anschauen...

edit: In last ist der letzte next-Pointer nicht immer NULL.
 
Zuletzt bearbeitet:
Hallo sheel und danke für die fixe Antwort :)

Nanu, wieso das ?

Was mir auch unklar ist, bzw wo ich mir unsicher bin :

ich übergeben an die Funktion permute ein Listenelement!
Möchte, dass sich dieses Element lokal verhält, also das sich Veränderungen an string nicht global auswirken !
Aufgrund der zeiger, bin ich mir nicht sicher, ob sich die Veränderungen nicht doch global auf string auswirken !
Ich hoffe es wird klar, was ich meine !? :D
 
Wahrscheinlich ist meine angesprochene Sache auch ein Problem ! Da ich ja keinen Copykonstruktor definiert habe, also der Standard benutzt wird. Und dieser kopiert in der Regel auch die Zeiger ...
Habe nun nen Copykonstruktor gebastelt und last ein wenig modifiziert (lasse nur Werte > 0 zu)!

Code: 
List<T>(List<T> &m){

		ListNode<T> * p = m.first;
                first = p;

		while(p){

			insert(p->data);
			

		}

	}

und

Code: 
template <class T>
T List<T>::last(){

	ListNode<T>* p=first;

	while((p->data >0) && p->next){
		p=p->next;
	}

	return p->data;

}


Hab nun wohl aber ne Endlosschleife drin ! Ich bleibe aber dran :D
 
Zuletzt bearbeitet:
Soo bin nun nen stück weiter ! Habe aber nun aber erstmal alles ein wenig hingefuscht, feintuning folgt am Ende, möchte nur erstmal, dass das Programm läuft :


Code: 
// ListePermutationen.cpp: Hauptprojektdatei.

#include "stdafx.h"
# include <iostream>
# include <string >
using namespace std ;

unsigned int  n;

template <class T>
class List ; // forward reference

 template <class T>
 class ListNode
 { 
	 friend class List <T>;
 
 public :

	 ListNode (T& t , ListNode<T>* p) : data ( t ) , next (p) { }

 protected :
 
	 T data ; // data field
	 ListNode<T>* next ; // points to next

} ;

template <class T>

class List
{ 
public :

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

List<T>(List<T> &m){

	 //ListNode<T> * p = newNode(m.first->data,first);
		
		
	ListNode<T> * p = m.first;	 
	int i = 0;
		
	*this;
	first = NULL;
	 double *s = 0;
	 s = new double[20];

		while(p){

			
			s[i] = p->data;
			i=i+1;
			p=p->next;

		}
		i--;
		for(i;i>=0;i--){
			
			
			
			insert(s[i]);

		}


	}

	void insert (T t ) ;
	int remove (T& t ) ;
	bool isEmpty ( ) { return ( first==NULL) ; }
	void print ( ) ;
	unsigned int size();
	void permutiere(List<T> m){
		List<T> temp = *this;
		permute(m,temp);
	}

	void permute( List<T>,List<T>);
	T last();

	


protected :

	ListNode<T>* first ;
	
	ListNode<T>* newNode(T& t ,ListNode<T>* p){ 
		
		ListNode<T>*q = new ListNode<T>( t , p ) ;
		return q ;
 
	}

 } ;

 int main ( ){ 
	 

	 
	
	 List <int> Menge;
	 
	 cout<<"Wie groß ist die Menge ? "<<endl;
	 cin>>n;

	 for(int i = n ; i >=1;i--) Menge.insert(i);

	 Menge.print();

	 List<int> Menge1;




	 cout<<endl<<endl;	
	 cout<<"Menge 1 "<<endl;

	

	 Menge1.print();

	 cout<<endl<<endl;
	 Menge.permutiere(Menge1);

	 cin>>n; 
	 return 0 ;
 }

 template <class T>
 List<T>::~List(){
	 ListNode<T>* temp;
	 
	 for(ListNode<T>* p = first;p;){

		 temp = p;
		 p = p->next;
		 delete temp;

	 }

 }

 template <class T>
 void List<T>::insert(T t){

	 ListNode<T> * p = newNode(t,first);
	 first = p ;
 }

 template <class T>
 void List<T>::print(){

	 for(ListNode<T>* p=first ;( p )&& (p->data > 0); p = p->next)
		 cout<<p->data <<" ";
	

 }

 template <class T>
 unsigned int List<T>::size(){
	 
	 int n;
	 ListNode<T>* p=first;

	 while(p){
		 
		 n++;
		 p=p->next;
	 }

	 return n;
 }




 


template <class T>
int List<T>::remove(T& t){

	if(isEmpty()) return 0;

	t=first->data;
	ListNode<T>*p = first;
	first = first->next;
	delete p;

	return 1;

}


template <class T>
T List<T>::last(){

	ListNode<T>* p=first;

	while((p->data >0) && p->next){
		p=p->next;
	}

	return p->data;

}


template <class T>
void List<T>::permute(List<T> fest,List<T> string){

	//cout<<"fest = ";
	//fest.print();
	//cout<<endl<<endl;
	//
	//			
	//cout<<"S string = ";			
	//string.print();			
	//cout<<endl;

	

	if(string.size() < 1){

		cout<<"Ausgabe : ";	


		fest.print();

		cout<<endl<<endl;

	}

	else {
		
		for(int p = string.first->data; p <= string.last() ;p++){
			
			//cout<<"P = "<<p<<endl<<endl;			
			//cout<<"S string = ";
			//string.print();
			//cout<<endl;
			//int n = p;
			
			fest.insert(p);			
			string.remove(p);			
			permute(fest,string);
			//cout<<"n = "<<n<<endl;
			fest.remove(p);				
			
			//cout<<"fest nach einfügen = ";				
			//fest.print();				
			//cout<<endl<<endl;
			//	

			string.insert(p);
				
			//cout<<"S string nach einfügen = ";
			//string.print();		
			//cout<<endl;

			//cout<<"letzter "<<string.last()<<endl;


		}


	}



}



Ausgabe : (Menge = 3)
321
331
322
332
323
333


Die Anzahl der Permutationen stimmen schonmal (n!), auch für andere Werte.
Aber scheinbar läuft da was verkehrt !
Hat vllt noch einen nen Tipp, wo ich mal schauen sollte ! Immer diese Zeiger ... :D

Habt Dank
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück