Ein Telefonbuch

1. Aufgabe

Unter einem Nachschlagewerk (engl. Dictionary) versteht man eine Datenstruktur, die zu einem beliebigen Index eine bestimme Information abspeichert. Ein Beispiel für ein Dictionary stellt ein englisches Wörterbuch dar: Der Index wird durch ein deutsches Wort gegeben, dahinter verbirgt sich die englische Übersetzung des Wortes. Ein weiteres Beispiel ist ein Telefonbuch. Als Index dient der Name einer Person, die Telefonnummer der Person verbirgt sich hinter dem Index:

Implementieren Sie ein Dictionary, das die Funktionalität eines Telefonbuchs besitzt. Entwerfen Sie zu diesem Zweck eine Klasse Phonebook, die wiederum Objekte einer Klasse Entry verwaltet. Alles personenspezischen Daten (Vorname, Nachname, Telefonnummer, usw.) sind in einem Entry-Objekt abzulegen, die Verwaltung der Entry-Objekte wiederum wird von einem übergeordneten Phonebook-Objekt übernommen. Eine genaue Spezifikation der Phonebook-Klasse können Sie Tabelle 1 entnehmen. Die Entry-Klasse kommt mit dem Anwender eines Phonebook-Objekts nicht in Berührung, sie wird also nur zu internen Hilfszwecken eingesetzt. Sie haben deshalb im Entwurf der Entry-Klasse freie Wahl.

Element

Schnittstelle und Beschreibung

Konstruktor

TelephoneBook ();

Der Standard-Konstruktor initialisiert ein leeres Telefonbuch.

Methode Count

public int Count();

Liefert die Anzahl der Einträge des Telefonbuchs zurück.

Methode Insert

public bool Insert(String name, int number);

Einfügen einer Person in das Telefonbuch. Zur Vereinfachung besitzt eine Person nur einen einzigen Namen (Parameter name) sowie eine Telefonnummer (Parameter number). Ist bereits eine Person mit dem Namen name im Telefonbuch enthalten, liefert die Methode den Wert false zurück, andernfalls true.

Methode Remove

public bool Remove(String name);

Entfernt die Daten der Person mit dem Namen name aus dem Telefonbuch. Mit dem Rückgabewert wird der Erfolg der Ausführung mitgeteilt.

Methode Contains

public bool Contains(String name);

Liefert true zurück, wenn eine Person mit dem Namen name im Telefonbuch enthalten ist, andernfalls false.

Methode Get

public int Get(String name);

Liefert die Telefonnummer einer Person mit dem Namen name zurück. Ist die Person nicht vorhanden, wird der Wert -1 zurückgegeben.

Tabelle 1. Öffentliche Elemente der Klasse Phonebook.


Da diese Aufgabe unter der Rubrik Arrays eingeordnet ist, sollten diese bei der Implementierung auch zum Einsatz kommen.

2. Lösung

Wie in der Aufgabenstellung schon nahe gelegt wurde, ist die Realisierung des Telefonbuchs auf zwei Klassen aufzuteilen. Die spezifischen Daten einer Person wie Name und Telefonnummer sind in Objekten des Typs Entry abzulegen. Eine zweite Klasse Phonebook wiederum verwaltet die Gesamtheit aller Entry-Objekte. Auf die Frage, inwieweit die Anzahl der möglichen Einträge im Telefonbuch nach oben begrenzt ist oder nicht, gehen wir jetzt näher ein. Wenn Sie sich unter dem Telefonbuch ganz klassisch – ich wollte nicht das Wort altmodisch verwenden – ein gedrucktes Taschenbuch mit einer festen Anzahl von Seiten vorstellen, dann wissen wir, dass die Anzahl der Seiten begrenzt ist. Elektronische Telefonbücher weisen diese Einschränkung nicht auf, sie können potentiell unendlich viele Einträge aufnehmen. Warum hebe ich diesen Aspekt hervor? Es geht dabei mit Hinblick auf die programmiersprachliche Umsetzung um die Frage, ob die Anzahl der Entry-Objekte bereits zum Übersetzungszeitpunkt fest vorgegeben ist oder aber zur Laufzeit des Programms dynamisch veränderbar ist. Beide Varianten ziehen eine unterschiedliche Implementierung nach sich, zum Zwecke des Übens ist es sinnvoll, sie beide zu betrachten.

Bei fest vorgegebener maximaler Anzahl von Entry-Objekten ist im Phonebook-Objekt bei seiner Erzeugung ein Array mit Referenzen für Entry-Objekte fester Länge zu allokieren. Dieser Sachverhalt wird in Abbildung 1 dargestellt, die Konstante MaxEntries bewirkt, dass ein Array für 100 Entry-Referenzen angelegt wird.

Entry-Arrayobjekt fester Länge.

Abbildung 1. Entry-Arrayobjekt fester Länge.


Typischerweise ist das Feld mit Entry-Referenzen zu Beginn des Programms leer, das heißt, alle Einträge sind mit der null-Referenz vorbelegt. Im laufenden Betrieb des Telefonbuchs werden neue Entry-Objekte dynamisch allokiert und ihre Referenzen in das Feld aufgenommen. Einträge im Telefonbuch, die zu Löschen sind, werden .NET-konform so gelöscht, dass ihre Referenz im m_entries-Array wieder auf den Wert null gesetzt werden. Das Entry-Objekt selbst wird so nicht mehr durch eine Referenz referenziert, der Garbage Collector gibt es zu einem späteren Zeitpunkt frei.

Etwas anders sieht die Strategie aus, möchte man eine beliebige Anzahl von Entry-Objekte in einem Phonebook-Objekt verwalten. Die einfachste Vorgehensweise sieht so aus, dass ein Feld mit Referenzen für Entry-Objekte stets so allokiert wird, dass es exakt die Referenzen aller vorhandenen Entry-Objekte aufnehmen kann und darüber hinaus keine weiteren null-Einträge besitzt (siehe Abbildung 2 ). Der Nachteil dieser Strategie besteht darin, dass bei jedem Einfügen eines neuen Eintrags oder Löschen eines vorhandenen Eintrags ein neues Entry-Arrayobjekt anzulegen ist und durch einen Umkopiervorgang zu füllen ist. Vorteilig wirkt sich die exakte Längenanpassung des Entry-Arrayobjekts dahingehend aus, dass beim Traversieren des Arrays null-Referenzen nicht störend im Weg herum liegen.

Entry-Arrayobjekt variabler Länge.

Abbildung 2. Entry-Arrayobjekt variabler Länge.


Den Sachverhalt, dass das Feld mit Entry-Referenzen niemals null-Einträge besitzt, untermauern wir noch einmal mit Abbildung 3. Ein zu Beginn leeres Telefonbuch wird sukzessive mit Insert-Methodenaufrufen gefüllt. Das m_entries-Array ist bzgl. seiner Länge immer exakt an die vorhandenen Entry-Objekte angepasst. Nach dem ersten Entfernen eines Entry-Objekts (durch Remove) erkennt man, dass ein neues, um einen Eintrag kürzeres Entry-Arrayobjekt vorhanden ist, das keine null-Referenzen aufweist und ausschließlich mit den Referenzen aktueller Entry-Objekte gefüllt ist.

Betrachtung der Arbeitsweise der Insert- und Remove-Methoden an einem Telefonbuchobjekt im zeitlichen Ablauf.

Abbildung 3. Betrachtung der Arbeitsweise der Insert- und Remove-Methoden an einem Telefonbuchobjekt im zeitlichen Ablauf.


Nach diesen Vorüberlegungen kommen wir nun auf die Realisierung zu sprechen. Sinnigerweise sollte die Klasse Entry nur in einer Implementierung vorhanden sein (Listing 1) und damit keinerlei Abhängigkeiten zu den Implementierungsdetails des umgebenden Telefonbuchs besitzen.

01: class Entry
02: {
03:     private String name;
04:     private int number;
05: 
06:     // c'tors
07:     public Entry()
08:     {
09:         this.name = null;
10:         this.number = -1;
11:     }
12: 
13:     public Entry(String name, int number)
14:     {
15:         this.name = name;
16:         this.number = number;
17:     }
18: 
19:     // properties
20:     public String Name
21:     {
22:         get
23:         {
24:             return this.name;
25:         }
26:     }
27: 
28:     public int Number
29:     {
30:         get
31:         {
32:             return this.number;
33:         }
34:     }
35: 
36:     // overrides
37:     public override String ToString()
38:     {
39:         return String.Format("{0}: {1}", this.name, this.number);
40:     }
41: 
42:     public override bool Equals(Object obj)
43:     {
44:         Entry e = (Entry) obj;
45:         return
46:             this.name.Equals(e.name) && this.number == e.number;
47:     }
48: 
49:     // just to prevent compiler warning
50:     public override int GetHashCode()
51:     {
52:         return base.GetHashCode();
53:     }
54: }

Beispiel 1. Klasse Entry.


Damit ist das Telefonbuch, also die Klasse Phonebook an der Reihe. Listing 2 können Sie die Realisierung einer Klasse Phonebook zur Verwaltung einer fest vorgegeben Anzahl von Entry-Objekten entnehmen:

001: class Phonebook
002: {
003:     private const int MaxEntries = 100;
004: 
005:     private Entry[] entries;
006: 
007:     // c'tors
008:     public Phonebook()
009:     {
010:         this.entries = new Entry[MaxEntries];
011:     }
012: 
013:     // properties
014:     public int Count
015:     {
016:         get
017:         {
018:             int count = 0;
019: 
020:             for (int i = 0; i < this.entries.Length; i++)
021:                 if (this.entries[i] != null)
022:                     count++;
023: 
024:             return count;
025:         }
026:     }
027: 
028:     // public interface
029:     public bool Contains(String name)
030:     {
031:         for (int i = 0; i < this.entries.Length; i++)
032:         {
033:             if (this.entries[i] != null)
034:                 if (this.entries[i].Name.Equals(name))
035:                     return true;
036:         }
037: 
038:         return false;
039:     }
040: 
041:     public bool Insert(String name, int number)
042:     {
043:         if (this.Contains(name))
044:             return false;
045: 
046:         for (int i = 0; i < this.entries.Length; i++)
047:         {
048:             if (this.entries[i] == null)
049:             {
050:                 this.entries[i] = new Entry(name, number);
051:                 return true;
052:             }
053:         }
054: 
055:         return false;
056:     }
057: 
058:     public bool Remove(String name)
059:     {
060:         if (!this.Contains(name))
061:             return false;
062: 
063:         for (int i = 0; i < this.entries.Length; i++)
064:         {
065:             if (this.entries[i] != null)
066:             {
067:                 if (this.entries[i].Name.Equals(name))
068:                 {
069:                     this.entries[i] = null;
070:                     return true;
071:                 }
072:             }
073:         }
074: 
075:         // should never be reached
076:         return false;
077:     }
078: 
079:     public int Get(String name)
080:     {
081:         for (int i = 0; i < this.entries.Length; i++)
082:         {
083:             if (this.entries[i] != null)
084:             {
085:                 if (this.entries[i].Name.Equals(name))
086:                     return this.entries[i].Number;
087:             }
088:         }
089: 
090:         return -1;
091:     }
092: 
093:     // overrides
094:     public override String ToString()
095:     {
096:         String s = "";
097:         for (int i = 0; i < this.entries.Length; i++)
098:         {
099:             if (this.entries[i] != null)
100:             {
101:                 s += this.entries[i].ToString();
102:                 s += Environment.NewLine;
103:             }
104:         }
105:         return s;
106:     }
107: }

Beispiel 2. Klasse Phonebook mit fester Anzahl von Entry-Objekten.


Charakteristisch für die gesamte Realisierung der einzelnen Methoden in Listing 2 ist, dass sie zu jedem Zeitpunkt auf null-Referenzen im Entry-Array achten müssen. Der Vorteil dieser Strategie ist, dass während der gesamten Lebensdauer eines solchen Phonebook-Objekts das Entry-Array bzgl. seiner Allokation unverändert bleibt, es finden also keine zeitaufwändigen Umkopiervorgänge statt. Nachteilig und geringfügig zeitaufwändiger sind offensichtlich die vielen Abfragen wie beispielsweise in den Zeilen 21, 33, 48 usw.

Damit dürfte klar geworden sein, wo die Unterschiede in der Implementierung einer Phonebook-Klasse liegen, wenn Sie die Anzahl der Telefonbucheinträge variabel gestalten wollen. Nehmen Sie sich bitte die Zeit und vergleichen Sie aus diesem Grund nachfolgend in Listing 3 eine Realisierung des Telefonbuchs mit variabler Anzahl von Entry-Objekten. Wo erkennen Sie im Vergleich zu Listing 2 die wesentlichen Unterschiede?

01: class Phonebook
02: {
03:     private Entry[] entries;
04: 
05:     // c'tors
06:     public Phonebook()
07:     {
08:         this.entries = new Entry[0];
09:     }
10: 
11:     // properties
12:     public int Count
13:     {
14:         get
15:         {
16:             return this.entries.Length;
17:         }
18:     }
19: 
20:     // public interface
21:     public bool Contains(String name)
22:     {
23:         for (int i = 0; i < this.entries.Length; i++)
24:         {
25:             if (this.entries[i].Name.Equals(name))
26:                 return true;
27:         }
28: 
29:         return false;
30:     }
31: 
32:     public bool Insert(String name, int number)
33:     {
34:         if (this.Contains(name))
35:             return false;
36: 
37:         Entry[] tmp = new Entry[this.entries.Length + 1];
38:         for (int i = 0; i < this.entries.Length; i++)
39:             tmp[i] = this.entries[i];
40: 
41:         // add new entry
42:         tmp[this.entries.Length] = new Entry(name, number);
43: 
44:         // switch buffer
45:         this.entries = tmp;
46:         return true;
47:     }
48: 
49:     public bool Remove(String name)
50:     {
51:         if (!this.Contains(name))
52:             return false;
53: 
54:         for (int i = 0; i < this.entries.Length; i++)
55:         {
56:             if (this.entries[i].Name.Equals(name))
57:             {
58:                 // decrease array
59:                 Entry[] tmp = new Entry[this.entries.Length - 1];
60:                 for (int k = 0; k < i; k++)
61:                     tmp[k] = this.entries[k];
62:                 for (int k = i + 1; k < this.entries.Length; k++)
63:                     tmp[k - 1] = this.entries[k];
64: 
65:                 // switch buffer
66:                 this.entries = tmp;
67:                 return true;
68:             }
69:         }
70: 
71:         return false;
72:     }
73: 
74:     public int Get(String name)
75:     {
76:         for (int i = 0; i < this.entries.Length; i++)
77:         {
78:             if (this.entries[i].Name.Equals(name))
79:                 return this.entries[i].Number;
80:         }
81: 
82:         return -1;
83:     }
84: 
85:     // overrides
86:     public override String ToString()
87:     {
88:         String s = "";
89:         for (int i = 0; i < this.entries.Length; i++)
90:         {
91:             s += this.entries[i].ToString();
92:             s += Environment.NewLine;
93:         }
94:         return s;
95:     }
96: }

Beispiel 3. Klasse Phonebook mit variabler Anzahl von Entry-Objekten.


In Listing 3 stellen Sie fest, dass vor allem die Methoden Insert und Remove jetzt umfangreicher ausfallen. Es genügt nicht einfach, ein neues Entry-Objekt zu allokieren oder eine vorhandene Entry-Objektreferenz in einem Array auf den Wert null zu setzen. Zusätzlich ist jedes Mal ein neues Entry-Objektarray zu allokieren und mit den vorhandenen Referenzen adäquat zu füllen.

Zum Testen legen wir einen kleinen Testrahmen zu Grunde, der in seinem Ablauf Abbildung 3 entspricht:

Beispiel:

Phonebook pb = new Phonebook();
pb.Insert("Franz", 123);
pb.Insert("Peter", 456);
pb.Insert("Susan", 789);
pb.Remove("Peter");
Console.WriteLine(pb);

int number = pb.Get("Franz");
Console.WriteLine("Phone Nr. of Franz: {0}", number);

Ausführung:

Franz: 123
Susan: 789

Phone Nr. of Franz: 123