Frequency Count Einfach verlinkte Liste

[christopher_gies]

Hallo,

habe eine Programmieraufgabe bei der ich eine einfach verlinkte Liste, mit Frequency Count implementieren soll. Frequency Count heißt, das jedem element der Liste ein Häufigkeitszähler zugeordnet wird, der nach jedem Zugriff auf das Element erhöht wird.
Habe das schonmal implementiert. Der Counter funktioniert auch schon. Jetzt scheitere ich nur daran die Liste absteigend nach der Häufigkeit der Zugriffe zu implementieren.
Kann mir da vlt. jemand einen Tipp geben?
Ich poste mal mein bisherigen Code!

Hier die Klasse Node, von der einzelne Knoten erzeugt werden können, die ein Element in der Liste implementiert.

public class Node<E>
{
	private E element;		//Element of this Node
	private Node<E> next;	//reference to next Node
	private int frequencyCounter;	//count elements access. Only Required for FrequencyCountList

	/* Create new Node with given Element and next Node */
	public Node(E element, Node<E> next)
	{
		this.element = element;
		this.next = next;
		frequencyCounter = 0;	//Only Required for FrequencyCountList
	}

	/* Getters */
	public E getElement()
	{
		return element;
	}

	public Node<E> getNext()
	{
		return next;
	}

	//Only Required for FrequencyCountList
	public int getFrequencyCounter()
	{
		return frequencyCounter;
	}

	/* Setters */
	public void setElement(E element)
	{
		this.element = element;
	}

	public void setNext(Node<E> next)
	{
		this.next = next;
	}

	//Only Required for FrequencyCountList
	public void FrequencyCounterStepUp()
	{
		frequencyCounter++;
	}
}

Hier die Klasse FrequencyCountList, die die Liste implementiert.

import java.util.NoSuchElementException;

public class FrequencyCountList<E>
{
	private int n; // Number of elements in the list
	private Node<E> head, tail;

	public FrequencyCountList(E element)
	{
		n = 1;
		head = new Node<E> (element, null); // create head
		tail = head; //at beginning tail is same like head
	}

	public int size()
	{
//		System.out.println(n);
		return n;
	}

	public boolean isEmpty()
	{
		if(size() == 0)
		{
//			System.out.println("true");
			return true;
		}else
		{
//			System.out.println("false");
			return false;
		}

	}

	public void addFirst(E element)
	{
		Node<E> newNode = new Node<E>(element, head);
		head = newNode;
		n++;
//		System.out.println(element);
	}

	public void removeFirst() throws NoSuchElementException 
	{
		if (head.getNext() == null)
			throw new NoSuchElementException("No such elements in this list");
		else
		{
			Node<E> temp = head;
			head = head.getNext();
			temp.setNext(null);
			n--;
//			System.out.println(temp);
		}
	}

	public void addLast(E element)
	{
		Node<E> newNode = new Node<E>(element, null);
		tail.setNext(newNode);
		tail = newNode;
		n++;
//		System.out.println(element);
	}

	public E get(E element)throws IllegalArgumentException
	{
		Node<E> temp = head;

		for(int i = 0; i < n; i++)
		{	
			if (temp.getElement() == element)
			{
				temp.FrequencyCounterStepUp();
				return temp.getElement();
			}else
			{
				temp = temp.getNext();
			}
		}
		throw new IllegalArgumentException("Element not found in List");
	}

	public String toString()
	{
		String zeile1 = "";
		Node<E> knoten = head;
		for(int i = 0; i < n; i++)
		{
			zeile1 += knoten.getElement() + " ";
			knoten = knoten.getNext();
		}
		zeile1 +="\n";
		return zeile1;
	}

	public void ausgeben()
	{
		System.out.println(toString());
	}

	public static void main(String[] args)
	{
		FrequencyCountList<String> test1 = new FrequencyCountList<String>("A");
		test1.addFirst("B");
		test1.addFirst("C");
		test1.addFirst("D");
		test1.ausgeben();
		test1.get("F");
		test1.ausgeben();
	}
}

[CStoll]

christopher_gies schrieb:

Habe das schonmal implementiert. Der Counter funktioniert auch schon. Jetzt scheitere ich nur daran die Liste absteigend nach der Häufigkeit der Zugriffe zu implementieren.

Was genau meinst du mit "implementieren"? Willst du die Liste sortieren nach Verwendungshäufigkeit? Wenn ja, dann gibt es reichlich Algorithmen, die du dafür verwenden kannst (für die linked list würde ich am ehesten MergeSort verwenden).

[christopher_gies]

Ja genau ich will die nun nach Verwendungshäufigkeit sortieren. Allerdings habe ich das Problem, das ich nicht genau weiß wie ich das machen soll mit dem sortieren.

[CStoll]

Du kannst vergleichen, welcher Zähler größer ist - und dann die Elemente entsprechend umhängen. Zu möglichen Sortier-Algorithmen gibt es im Netz genug Beispiele, um dir einen auszusuchen (wie gesagt: mein Vorschlag ist MergeSort).

[christopher_gies]

Hmmm habe gerade mal etwas über merge-sort für verkettete Listen in einem anderen Beitrag gelesen, aber irgendwie werde ich daraus nicht schlau! Haben bis jetzt im Studium leider noch gar keine Sortieralgorithmen besprochen. Weiß auch nicht wie der Prof auf einmal darauf kommt, uns so eine Aufgabe aufzugeben... aber naja das ist ein anderes Thema.
Kannst du mir vlt. noch ein bissl mehr auf die Sprünge helfen? Weiß nicht mal wo ich ansetzten soll. Ich würde jetzt in meiner get Methode meiner Klasse FrequencyCountList vor dem return anfangen und probieren meine Liste umzustruktorieren. Läge ich damit schonmal richtig?

Über deine Hilfe währe ich echt sehr dankbar!

[CStoll]

MergeSort arbeitet rekursiv, indem die gegebene Liste erst aufgeteilt und dann in der richtigen Reihenfolge wieder zusammengeschoben wird.

christopher_gies schrieb:

Ich würde jetzt in meiner get Methode meiner Klasse FrequencyCountList vor dem return anfangen und probieren meine Liste umzustruktorieren. Läge ich damit schonmal richtig?

Das wäre auch ein Ansatz - du müsstest dir noch den Vorgänger des gefundenen Knotens und das letzte Element mit einem größeren Zähler heraussuchen und dann das Element umhängen:

vorgaenger.next = temp.next;
temp.next = ziel.next;
ziel.next = temp;

(Eventuell benötigst du Sonderbehandlung, wenn das Element gan an den Anfang wandern sollte)

Welche Variante günstiger ist, hängt wohl davon ab, ob du häufiger nach Elementen suchst (und damit die bestehende Sortierung kaputt machst) oder häufiger die sortierte Liste ausgeben willst.

[christopher_gies]

Kannst du mir das mit dem umhängen nochmal genauer beschreiben?
Und muss ich das ganze dann in einer while Schleife machen? Und welches Abbruchkriterium setzte ich dann für diese Schleife?

Das Element vor dem gefunden Element hab ich schonmal und schreibe mir gerade noch eine Methode die das letzte höhere Element findet!

Oder könntest du mir nochmal die Rekursion erklähren wenn die leicher zu implementieren bzw. verstehen ist?

Danke

[CStoll]

christopher_gies schrieb:

Und muss ich das ganze dann in einer while Schleife machen? Und welches Abbruchkriterium setzte ich dann für diese Schleife?

Für das Umhängen brauchst du keine Schleife, nur zum Finden der Zielposition. Wenn du alle an der Aktion beteiligten Listenknoten hast, mußt du nur deren Nachfolger-Zeiger auf das jeweils neue Ziel verweisen lassen (siehe der Beispielcode dort oben):

• vom bisherigen Vorgänger des Knotens auf dessen Nachfolger (Umleitung, um an der alten Position vorbeizukommen)
• vom zu verschiebenden Element auf den Nachfolger des Ziels
• vom Ziel auf das verschobene Element

(im Endeffekt wird der Knoten hinter 'ziel' in der Liste neu eingereiht)

[christopher_gies]

Aber was ist denn die Zielposition? Ich hab ja bis jetzt folgende Positionen zur Verfügung:

[] Knoten welcher eigentlich von der Get Methode gesucht und dessen Counter durch den Zugriff eröht wird. → (temp)
[] Das Element vor dem gesuchten Element → (vorgänger)
[*] und das letzte höhere Element als das gesuchte Element (bezogen auf dessen Zugriffscounter) → (ziel???) Müsste das nicht das letzte höhere Element nach temp seien? Oder das letzte höhere Element allgemein in der Liste?

[CStoll]

christopher_gies schrieb:

Aber was ist denn die Zielposition? Ich hab ja bis jetzt folgende Positionen zur Verfügung:

[] Knoten welcher eigentlich von der Get Methode gesucht und dessen Counter durch den Zugriff eröht wird. → (temp)
[] Das Element vor dem gesuchten Element → (vorgänger)
[*] und das letzte höhere Element als das gesuchte Element (bezogen auf dessen Zugriffscounter) → (ziel???) Müsste das nicht das letzte höhere Element nach temp seien? Oder das letzte höhere Element allgemein in der Liste?

Du hast gerade den Counter von temp erhöht, also ist die Zielposition vermutlich weiter vorne (wenn ich mal davon ausgehe, daß du die Einträge absteigend sortieren willst^*) als seine aktuelle Position - und alle Elemente dahinter sind mit Sicherheit kleiner.

^* wenn du die Liste aufsteigend sortieren willst, benötigst du das letzte Element hinter der gefundenen Position, das kleiner ist als temp - der Rest verläuft analog. Außerdem solltest du dann neue Elemente am Anfang der Liste anhängen.

[christopher_gies]

Ohje CStoll glaube das übersteigt meine Programmierkentnisse... ich habe das jetzt mittels Bubblesort realisiert, ist zwar von der Laufzeit her total schlecht, aber es funktioniert. Der Bubblesort war für mich als Anfänger eher zu begreifen.
Aber trotzdem Danke für die Mühen die du dir gemacht hast!

Der Vollstädigkeit halber poste ich mal hier meine Lösung

public class Node<E>
{
	private E element;		//Element of this Node
	private Node<E> next;	//reference to next Node
	private int frequencyCounter;	//count elements access. Only Required for FrequencyCountList

	/* Create new Node with given Element and next Node */
	public Node(E element, Node<E> next)
	{
		this.element = element;
		this.next = next;
		frequencyCounter = 0;	//Only Required for FrequencyCountList
	}

	/* Getters */
	public E getElement()
	{
		return element;
	}

	public Node<E> getNext()
	{
		return next;
	}

	//Only Required for FrequencyCountList
	public int getFrequencyCounter()
	{
		return frequencyCounter;
	}

	/* Setters */
	public void setElement(E element)
	{
		this.element = element;
	}

	public void setNext(Node<E> next)
	{
		this.next = next;
	}

	//Only Required for FrequencyCountList
	public void setFrequencyCounter(int frequencyCounter)
	{
		this.frequencyCounter = frequencyCounter;
	}

	//Only Required for FrequencyCountList
	public void FrequencyCounterStepUp()
	{
		frequencyCounter++;
	}
}

import java.util.NoSuchElementException;

public class FrequencyCountList<E>
{
	private int n; // Number of elements in the list
	private Node<E> head, tail;

	public FrequencyCountList(E element)
	{
		n = 1;
		head = new Node<E> (element, null); // create head
		tail = head; //at beginning tail is same like head
	}

	public int size()
	{
//		System.out.println(n);
		return n;
	}

	public boolean isEmpty()
	{
		if(size() == 0)
		{
//			System.out.println("true");
			return true;
		}else
		{
//			System.out.println("false");
			return false;
		}

	}

	public void addFirst(E element)
	{
		Node<E> newNode = new Node<E>(element, head);
		head = newNode;
		n++;
//		System.out.println(element);
	}

	public void removeFirst() throws NoSuchElementException 
	{
		if (head.getNext() == null)
			throw new NoSuchElementException("No such elements in this list");
		else
		{
			Node<E> temp = head;
			head = head.getNext();
			temp.setNext(null);
			n--;
//			System.out.println(temp);
		}
	}

	public void addLast(E element)
	{
		Node<E> newNode = new Node<E>(element, null);
		tail.setNext(newNode);
		tail = newNode;
		n++;
//		System.out.println(element);
	}

	/**
	 * Get element and sort List
	 * @param element searching for
	 * @return element if found
	 * @throws IllegalArgumentException
	 */
	public E get(E element)throws IllegalArgumentException 
	{
		Node<E> temp = head;

		for(int i = 0; i < n; i++)
		{	
			if (temp.getElement() == element)
			{
				temp.FrequencyCounterStepUp();
				bubblesort();
				return temp.getElement();
			}else
			{
				temp = temp.getNext();
			}
		}
		throw new IllegalArgumentException("Element not found in List");
	}

	/**
	 * Sorts List downwards by access counter
	 */
	public void bubblesort()
	{
		Node<E> aktuellerKnoten = head;

		boolean vertauscht = true;
		while(vertauscht)
		{
			vertauscht = false;
			for(int i = 0; i < n; i++)
			{
				if(aktuellerKnoten.getNext() != null && aktuellerKnoten.getFrequencyCounter() < aktuellerKnoten.getNext().getFrequencyCounter())
				{
					E etemp = aktuellerKnoten.getElement();
					int counterTemp = aktuellerKnoten.getFrequencyCounter();
					aktuellerKnoten.setElement(aktuellerKnoten.getNext().getElement());
					aktuellerKnoten.setFrequencyCounter(aktuellerKnoten.getNext().getFrequencyCounter());
					aktuellerKnoten.getNext().setElement(etemp);
					aktuellerKnoten.getNext().setFrequencyCounter(counterTemp);
					vertauscht = true;
				}
				if(aktuellerKnoten.getNext() != null)
				{
					aktuellerKnoten = aktuellerKnoten.getNext();
				}
			}
			aktuellerKnoten = head;
		}
	}

	public String toString()
	{
		String zeile1 = "";
		Node<E> knoten = head;
		for(int i = 0; i < n; i++)
		{
			zeile1 += knoten.getElement() + " ";
			knoten = knoten.getNext();
		}
		zeile1 +="\n";
		return zeile1;
	}

	public void ausgeben()
	{
		System.out.println(toString());
	}

	public static void main(String[] args)
	{
		FrequencyCountList<String> test1 = new FrequencyCountList<String>("A");
		test1.addFirst("B");
		test1.addFirst("C");
		test1.addFirst("D");
		test1.ausgeben();
		test1.get("A");
		test1.get("B");
		test1.get("C");
		test1.get("B");
		test1.get("C");
		test1.get("D");
		test1.get("D");
		test1.get("C");
		test1.ausgeben();
	}
}