| Autor |
Beitrag |
toom
Hält's aus hier
Beiträge: 6
|
Verfasst: Di 02.12.14 17:41
Hallo,
im Internet bin ich auf folgende Aufgabe gestossen:
Entwickeln Sie eine generische Klasse, die den ADT Queue/FIFO implementiert. Die Methoden sollten sein:
•Enque - ein Element in die Warteschlange stellen
•Dequeue – ein Element aus dem Warteschlange entfernen
•Count – Anzahl der Elemente in der Warteschlange
•Peek – das vorderste Element, ohne es zu entfernen
•TryDequeue – wie Dequeue, allerdings keine Exception, falls die Queue leer; liefert true/false, jenachdem, ob Dequeue erfolgreich
Benutzen Sie keinen Collection-Typ und auch kein Array, um intern die Elemente zu verwalten.
ich würde diese Aufgabe gerne lösen. Kopfzerbrechen bereitet mir das Problem mit dem verwalten der internen Elemente.
Könnt ihr mir ein paar Tipps geben?
Moderiert von  Th69: Titel geändert.
Moderiert von Th69: Topic aus C# - Die Sprache verschoben am Di 02.12.2014 um 16:45
|
|
Th69
Beiträge: 4764
Erhaltene Danke: 1052
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: Di 02.12.14 17:47
Hallo und 
da fällt mir eigentlich nur eine (selbstgebaute) verkettete Liste ein.
|
|
Ralf Jansen
Beiträge: 4700
Erhaltene Danke: 991
VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
|
Verfasst: Di 02.12.14 17:50
Ein Array (logisch wie einen Ringspeicher verwenden) für die Elemente. Am Anfang vielleicht erstmal mit fixer Größe später kann man dann ein resizen einbauen. Dazu 2 Zeiger (Integer mit den Indexen im Array) für Anfang und Ende der Elemente die beim enque/deque passend verschoben werden.
Edit: ich habe den fett geschriebenen Teil übersehen 
|
|
toom 
Hält's aus hier
Beiträge: 6
|
Verfasst: Di 02.12.14 18:23
Th69 hat folgendes geschrieben  : | Hallo und
da fällt mir eigentlich nur eine (selbstgebaute) verkettete Liste ein. |
Vielen Dank!
meinst du damit einen String der die Werte mit Seperator verkettet?
Würde bedeuten das nur Primitive Datentypen verarbeitet werden könnten.
|
|
Ralf Jansen
Beiträge: 4700
Erhaltene Danke: 991
VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
|
Verfasst: Di 02.12.14 18:34
Nein meint er nicht. Eine verkettete Liste kann in ihren Knoten beliebige Daten halten.
de.wikipedia.org/wik..._%28Datenstruktur%29
|
|
toom
Hält's aus hier
Beiträge: 6
|
Verfasst: Mi 03.12.14 18:49
Dann würde das ungefähr so aussehen?
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
| public class MyQueue<T> where T : class
{
T value;
MyQueue<T> next;
public MyQueue() { }
private MyQueue(T t)
{
value = t;
}
public void Enque(T t)
{
if (value == null)
{
value = t;
}
else
{
if (next == null)
{
next = new MyQueue<T>(t);
}
else
{
next.Enque(t);
}
}
}
public void Dequeue()
{
if (next == null)
{
value = default(T);
}
else
{
value = next.value;
next.Dequeue();
}
}
public bool TryDequeue()
{
return false;
}
public T Peek()
{
return value;
}
public string Output()
{
if (value == null)
{
return "leer";
}
else
{
if (next == null)
{
return value.ToString();
}
else
{
return value.ToString() + " - " + next.Ausgabe();
}
}
}
} |
- Das Problem wären jetzt noch die Wertetypen. Da habe ich noch ein weinig Probleme mit der Überprüfung.
- Die Ausgabe ist auch schlecht, da nur ein verketteter String zurückgegeben wird.
|
|
Ralf Jansen
Beiträge: 4700
Erhaltene Danke: 991
VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
|
Verfasst: Mi 03.12.14 19:09
| Zitat: | | Das Problem wären jetzt noch die Wertetypen. Da habe ich noch ein weinig Probleme mit der Überprüfung. |
Du hast auf class eingeschränkt insofern kann das eh nicht gehen. Wenn das Problem ist das du dann value nicht richtig prüfen kannst da jeder Wert in einem Wertetyp gültig ist bleibt dir nichts anders übrig einen 2.te Variable einzuführen die aussagt ob der Inhalt von value gültig ist.
Wobei ich nicht verstanden habe wofür der Test da ist. Wenn eine MyQueue Instanz existiert hat sie auch einen Wert. Es ist doch nur relevant ob es einen Nachfolger gibt oder nicht? Oder ist das ein Folgeproblem da du versucht die Queue Klasse und den Knoten in der Queue durch die gleiche Klasse darzustellen? Die Idee ist möglicherweise zu ~clever~ und es wäre womöglich einfach mit expliziter Queue und Knoten Klasse zu arbeiten. Mit einfacher meine ich hier eher wartbar und vom Verhalten her nachvollziehbarer nicht weniger Code.
|
|
Th69
Beiträge: 4764
Erhaltene Danke: 1052
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: Mi 03.12.14 20:54
Hallo toom,
ich sehe es auch so wie Ralf, daß es besser ist mit zwei Klassen: Queue und Node(Element)
|
|
toom
Hält's aus hier
Beiträge: 6
|
Verfasst: Mi 03.12.14 20:58
Wenn MyQueue durch den public Konstruktor instanziert wird, gibt es noch keinen Wert. Dieser wird erst durch die Methode Enque gesetzt.
Wird Enque ein zweitesmal aufgerufen dann gibt es einen Wert, das wird an der Prüfung festgestellt.
Es wird ein neues MyQueue Objekt mit dem private Konsturktor erzeugt der den Wert aus dem Aufruf entgegennimmt.
Die Einschränkung (class) habe ich gesetzt weil eine Prüfung auf null vorhanden ist. Das würde bei Wertetypen nicht gut gehen
Eine Möglichkeit wäre nur einen Konstruktor anzubieten der einen Wert benötigt, dann würde die Prüfung unnötig sein.
Somit sollte ich dann mit allen Typen arbeiten können. Bin mir aber nicht sicher ob das dann so "schön" ist?
|
|
Ralf Jansen
Beiträge: 4700
Erhaltene Danke: 991
VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
|
Verfasst: Mi 03.12.14 23:25
Könnte funktionieren. Nur für den ~Head~ musst du dir was überlegen um eine leere Queue von einer Queue mit 1 Element zu unterscheiden. Vielleicht sollte das erste MyQueue immer ~leer~ sein und einfach keinen Wert darstellen. Heißt eine Liste mit 1 Element besteht aus 2 MyQueue Objekten.
|
|
toom
Hält's aus hier
Beiträge: 6
|
Verfasst: Do 04.12.14 17:44
Ich habe das soweit gelöst indem ich wie vorher vorgeschlagen 2 Klassen benutze.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
| public class MyQueue2<T> : IEnumerable<T>
{
private class Node
{
public Node next;
public T value;
public Node(T t)
{
value = t;
}
}
Node firstNode;
Node lastNode;
int count = 0;
public int Count
{
get { return count; }
}
public void Enque(T t)
{
if (firstNode == null)
{
firstNode = new Node(t);
}
else if (firstNode.next == null)
{
lastNode = new Node(t);
firstNode.next = lastNode;
}
else
{
lastNode.next = new Node(t);
lastNode = lastNode.next;
}
count += 1;
}
public void Dequeue()
{
if (firstNode != null)
{
if (firstNode.next != null)
{
firstNode = firstNode.next;
count -= 1;
}
else
{
firstNode = null;
count = 0;
}
}
}
public T Peek()
{
if (firstNode != null)
{
return firstNode.value;
}
else
{
throw new IndexOutOfRangeException();
}
}
public IEnumerator<T> GetEnumerator()
{
if (firstNode != null)
{
Node temp = firstNode;
while (temp.next != null)
{
yield return temp.value;
temp = temp.next;
}
yield return temp.value;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
} |
Das arbeitet auch mit jedem Datentyp.
Was mir nicht gefällt sind die vielen gleichen If Statements.
|
|
Ralf Jansen
Beiträge: 4700
Erhaltene Danke: 991
VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
|
Verfasst: Do 04.12.14 19:04
Dein Dequeue liefert noch keinen Wert zurück.
Alternative Implementierung
  C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
| public void Enque(T t)
{
var node = new Node(t);
if (firstNode == null)
firstNode = lastNode = node;
else
lastNode = lastNode.next = node;
count += 1;
}
public T Dequeue()
{
if (firstNode == null)
throw new InvalidOperationException("Queue is empty.");
T value = firstNode.value;
firstNode = firstNode.next;
count -= 1;
if (firstNode == null)
lastNode = null; return value;
} |
Für diesen Beitrag haben gedankt: toom
|
|
matthias schiffler
Hält's aus hier
Beiträge: 1
|
Verfasst: Di 06.01.15 20:24
Für alle die es interessiert mit verketteten Listen. Viel spaß! 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
| class MyQueue<T>
{
private Boolean _first = false;
private T _object = default(T);
private MyQueue<T> _followListObject = null;
private MyQueue<T> _lastObject = null;
public MyQueue()
{
}
private MyQueue(T o)
{
this._object = o;
}
public void Enque(T o)
{
if (this._object == null || this._first == false)
{
this._first = true;
this._object = o;
this._lastObject = this;
}
else
{
MyQueue<T> lst = new MyQueue<T>(o);
this._lastObject._followListObject = lst;
this._lastObject = lst;
}
}
public T Dequeue()
{
if (this._object == null) throw new InvalidOperationException("Queue is empty.");
T returnObj = this._object;
Delete();
return returnObj;
}
public Boolean TryDequeue()
{
if (this._object != null)
{
Delete();
return true;
}
return false;
}
private void Delete()
{
if (this._followListObject != null)
{
if (this._lastObject != null)
{
this._followListObject._lastObject = this._lastObject;
}
this._object = this._followListObject._object;
this._followListObject = this._followListObject._followListObject;
}
else
{
this._first = false;
this._object = default(T);
this._lastObject = null;
}
}
public T Peek()
{
return this._object;
}
public int Count
{
get
{
if (!_first)
{
return 0;
}
return Counting();
}
}
private int Counting()
{
MyMath.Count = 1;
if (this._followListObject != null)
{
this._followListObject.Counting();
MyMath.Count++;
}
return MyMath.Count;
}
} |
Zum testen:
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| MyQueue<string> test = new MyQueue<string>();
bool b = test.TryDequeue(); test.Enque("JAVA");
test.Enque("PHP");
test.Enque("C#");
test.Enque("C++");
test.Enque("PYTHON");
string java = test.Dequeue(); string php = test.Dequeue(); string csharp = test.Peek(); int t = test.Count; |
|
|
