RadixSort mit Queues implementieren

B

BassSportler

Grünschnabel
Hey,
ich soll das Radixsortverfahren mit Queues in Java implementieren. Leider hab ich jetzt schonmla ein Problem mit den Warteschlangen. Ich hab ne Klasse dafür geschrieben
PHP: 
public class Queue {
	private int laenge;
	private int queue[];
//	private int f;
//	private int r;
	
	public Queue (int N) {
		int queue[] = new int[N];
	}
	
//	public abstract void enqueue(int x);
//	public abstract int dequeue();
//	public abstract int size();

	int f=0;
	int r=0;


	public void enqueue (int x) {
		queue[r] = x;
		r++;//= r+1%queue.length;
	}
	
	public int dequeue () {
		return queue[f++];
//		f = f+1%queue.length;
	}
	
	public int size() {
		return r-f;
	}	

}
und compilieren geht auch, aber wenn ich dann in der eig. Klasse versuchsweise mal die Queues ausprobieren will,
PHP: 
public class Radix {
	
	public static void main (String[] args) {
		long eingabe[] = new long[args.length];
		
		for(int i=0; i<args.length; i++) {
			try {
				eingabe[i] = Long.parseLong(args[i]);
			} catch (NumberFormatException nfe) {
				System.out.println("Falscher Typ! Nur ganze 4-stellige Zahlen eingeben!");
				}
		}
		
		Queue wart1 = new Queue(args.length);
		
		wart1.enqueue(7);
//		wart1.enqueue(8);
//		wart1.enqueue(9);
//		int x=wart1.dequeue();
//		System.out.println(x);
		
	}
}
bekomm ich eine NullPointerException bei der MEthode "enqueue" (erste Klasse) die ja in der 2. Klasse aufgerufen wird, welche , was einer was falsch ist?
PS: PHP-Code weils schöner aussieht ;-)
 
danke, das Rad neu Erfinden, weil es der Prof so will! hab jetzt fast alles, nur noch ein kleiner Fehler:
PHP: 
public class Radix {
	
	public static void main (String[] args) {
		long eingabe[] = new long[args.length];
		
		for(int i=0; i<args.length; i++) {
			try {
				eingabe[i] = Long.parseLong(args[i]);
			} catch (NumberFormatException nfe) {
				System.out.println("Falscher Typ! Nur ganze 4-stellige Zahlen eingeben!");
				}
		}
		
		Queue wart[][] = new Queue[10][4];
		for(int g=0; g<10; g++) {
			for(int i=0; i<4; i++) {
				wart[g][i] = new Queue(args.length);
			}
		}


		for(int j=0; j<eingabe.length; j++) {
			int y = Integer.parseInt((Long.toString(eingabe[j])).substring(3,4));
			wart[y][0].enqueue(eingabe[j]);
		}
		
//		for(int g=0; g<10; g++) {
//		while(wart[g][0].size()>0) {
//			System.out.println(wart[g][0].dequeue());}
//		}
		
		
		for(int h=2; h>=0; h--) {
			for(int d=1; d<4; d++) {
				for(int k=0; k<=9; k++) {
					while (wart[k][d-1].size() > 0) {
						int x = Integer.parseInt((Long.toString(wart[k][d-1].top())).substring(h,h+1));//hier Fehler
						wart[x][d].enqueue(wart[k][d-1].dequeue());
					}
				}
			}
		}
		
		for(int j=0; j<10; j++) {
			while (wart[j][3].size() > 0) {
				System.out.println(wart[j][3].dequeue());
			}
		}
		
//		int hj = Integer.parseInt(((Long.toString(156).substring(0,1))));
//	System.out.println(1052.len);
			
	}
}

in der kommentierten Zeile gibt er mir einen StringIndexOutOfBoundsException-Fehler aus, obwohl ich nur 4-stellige Zahlen eingebe. Müsste meiner Meinung nach Passen, sieht jemand, was ich nicht sehe?
 
Adrian_Broher hat gesagt.:
Benutz bitte sprechende Variablennamen.
Zum Vergrößern anklicken....

na hab ich doch, "eingabe" ist der Array in dem die Kommandozeileneingaben gespeichert werden (die sollen auch sortiert werden) und wart, die verscheidenen Wartechlangen, die ich brauche um die Zahlen jeweils in die "Kisten" zu schieben. Ich hab das Problem schon größtenteils gelöst, ich schaffs nur nicht eine (bereits) Queue, bzw. ein Queuearray zu erzeugen.
Die Info das ich die Queues selber machen muss, war falsch, nur verstehe ich die Syntax zum erzeugen unter dem Link oben nicht, kann mir die jemand vll. erkären?
Besten Dank schonmal!
 
BassSportler hat gesagt.:
na hab ich doch,
Zum Vergrößern anklicken....

d, g, h, i, j, k und y sind nicht sprechend.

Der Link beschreibt die Schnittstelle "Queue". Eine konkrete Implementierung davon waere die LinkedList. Die <> geben an welchen Datentyp die Queue aufnehmen kann.

Java: 
Queue<Integer> myQueue = new LinkedList<Integer>();

myQueue.offer(new Integer(17));
myQueue.offer(new Integer(42));
myQueue.offer(new Integer(23));

// myQueue enthaelt > 17, 42, 23

System.out.println(myQueue.peek()); // 23
// myQueue enthaelt > 17, 42, 23

System.out.println(myQueue.poll()); // 23
// myQueue enthaelt > 17, 42

System.out.println(myQueue.poll()); // 42
// myQueue enthaelt > 17
 
BassSportler hat gesagt.:
Zählvariablen hab ich bisher nie Namen gegeben :-(
Zum Vergrößern anklicken....

Dann fang am besten mal jetzt damit an.

BassSportler hat gesagt.:
aber danke für den queue-Hinweis, kann man damit auch Arrays erzeugen?
Zum Vergrößern anklicken....

Java: 
Typ variable = new Typ; // fuer Objektvariablen

Typ ist in diesem Fall ein Array von Arrays von Queues, welche Integer Objekte aufnehmen oder kurz:

Queue<Integer>[][]

Java: 
Queue<Integer>[][] wart = Queue<Integer>[10][4];
 
Habs jetzt selber gelöst, trotzdem vielen Dank für die Hilfe!
Falls es jemand interessiert:
Java: 
import java.text.*;

class FalseValueException extends Exception {				//Fehlerklasse erstellen
    public FalseValueException(String fehlermeldung) {
        super(fehlermeldung);
    }
}


class Queue {
	private int laenge;
	private long queue[];

	
	public Queue (int N) {		//erzeugt eine Queue (aus Array) der Länge N
		queue = new long[N];
	}
	
	int f=0;		//Variablen zum verwalten der Queue
	int r=0;


	public void enqueue (long x) {		//etwas in die Queue einfügen
		queue[r] = x;
		r++;//=(r+1)%queue.length;
	}
	
	public long dequeue () {		//etwas in die Queue entfernen
		long x = queue[f];
		queue[f] = 0;
		f++;// = (f+1)%queue.length;
		return x;
	}
	
	public long top () {		//oberstes Element der Queue betrachten
		return queue[f];
	}
			
	public int size() {		//Anzahl der Elemente der Queue
		return r-f;
	}	

}


public class Radix {
	
	public static void main (String[] args) {
		long eingabe[] = new long[args.length];	//Array zum Speichern der Kommandozeileneingaben
		
		DecimalFormat df = new DecimalFormat("0000");		//erstellt aus Zahl String, für den führende Nullen eingefügt werden, damit auch 0001 etc, beachtet wird
		
		Queue wart[][] = new Queue[10][4];			//Erstellen des Queue-Array, für jede mögliche Stellen-Ziffern-Kombination einen
		for(int g=0; g<10; g++) {
			for(int i=0; i<4; i++) {
				wart[g][i] = new Queue(args.length);
			}
		}
		
		for(int i=0; i<args.length; i++) {
			try {
				if (args[i].length()!=4) throw new FalseValueException("Nur 4-stellige Zahlen eingeben!");		//gibt Fehlermeldung aus, da eine nicht 4-stellige Zahl eingegeben wurde
			} catch(FalseValueException e) {
				System.out.println(e.toString());
				}
				
			try {
				eingabe[i] = Long.parseLong(args[i]);		//Übernahme der Kommandozeileneingaben in den int-Array
			} catch (NumberFormatException nfe) {			//Fehlermelldung falls keine int-Zahl eingeben wird
				System.out.println("Falscher Typ! Nur ganze 4-stellige Zahlen eingeben!");
				}
		}


		for(int j=0; j<eingabe.length; j++) {		//erster Durchlauf der letzte Stelle überprüft und dementsprechend in Warteschlange(Bucket) einfügt
			int y = Integer.parseInt((df.format(eingabe[j])).substring(3,4));	//nutzt oben definierte int-to-String Umwandlung für Ziffertest
			wart[y][0].enqueue(eingabe[j]);
		}
			
		
		for(int runden=1,stellen=2; runden<4&&stellen>=0; runden++,stellen--) {		//restlichen Durchlääufe analog zum ersten, nur dass hier die Eingaben nicht aus einem Array sondern aus den vorigen Warteschlangen kommen
				for(int ziffern=0; ziffern<=9; ziffern++) {
					while (wart[ziffern][runden-1].size() > 0) {
						int x = Integer.parseInt((df.format(wart[ziffern][runden-1].top())).substring(stellen,stellen+1));		//nutzt oben definierte int-to-String Umwandlung für Ziffertest
						wart[x][runden].enqueue((wart[ziffern][runden-1].dequeue()));
					}
			}
		}


		for(int zeile=0; zeile<10; zeile++) {			//Auslesen des letzten Warteschlangendurchlaufs um korrekt sortierte Reihenfolge zu sehen
			while (wart[zeile][3].size() > 0) {
				System.out.println(wart[zeile][3].dequeue());
			}
		}
		

	}
}
 
Zuletzt bearbeitet von einem Moderator:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück