|
|
| Line 28: |
Line 28: |
|
| |
|
| ====Aufgabe: doppelt verkettete Liste==== | | ====Aufgabe: doppelt verkettete Liste==== |
| Eine doppelt verkettete Liste ist Reihe von Elementen (auch Knoten genannt), die durch zwei Zeiger miteinander verbunden sind. Zusätzlich zu einem Zeiger, der auf das nächste Element zeigt gibt es einen, der auf das vorhergehende Element zeigt. Eine doppelt verkettete Liste kann man also in beide Richtungen durchlaufen. Die Operationen auf einer doppelt verketteten Liste sind analog zu denen einer einfach verketteten Liste. | | Eine doppelt verkettete Liste ist Reihe von Elementen (auch Knoten/Nodes genannt), die durch zwei Zeiger miteinander verbunden sind. Zusätzlich zu einem Zeiger, der auf das nächste Element zeigt gibt es einen, der auf das vorhergehende Element zeigt. Eine doppelt verkettete Liste kann man also in beide Richtungen durchlaufen. Die Operationen auf einer doppelt verketteten Liste sind analog zu denen einer einfach verketteten Liste. |
|
| |
|
| Die Elemente einer Liste sind vom Typ struct. Wir geben uns folgendes vor:
| | [[File:DLL1.png]]<br> |
|
| |
|
| struct node{ | | Folgene Funktionalität sollte unsere Liste zumindest haben: |
| int data;
| | |
| struct node* prev;
| | appendNode |
| struct node* next;
| | printList |
| }; | | printListReverse |
| | listLength |
| | seekList |
| | seekListReverse |
| | deleteNode |
|
| |
|
| typedef struct node node;
| | Wie auch bei der einfach verketteten Liste kannst du gerne Generics verwenden. |
| | |
| Das folgende kleine Programm erzeugt einen Wurzelknoten und zwei Nachfolger und gibt die Daten aus.
| |
| | |
| /*
| |
| * Eine Wurzel mit zwei Nachfolgern zu Fuß
| |
| */
| |
| void beispiel(){
| |
| puts("beispiel");
| |
| | |
| // Erstellen von root
| |
| node *root = malloc(sizeof(node));
| |
| if (root == NULL) return;
| |
| | |
| root->data = 17;
| |
| root->prev = NULL;
| |
| root->next = NULL;
| |
| | |
| // Anhängen eines Knotens
| |
| node *secondNode = malloc(sizeof(node));
| |
| if (secondNode == NULL) return;
| |
| | |
| root->next = secondNode;
| |
| secondNode->prev = root;
| |
| secondNode->next = NULL;
| |
| secondNode->data = 19;
| |
| | |
| // Anhängen eines weiteren Knotens
| |
| node* last = malloc(sizeof(node));
| |
| if (last == NULL) return;
| |
| | |
| secondNode->next = last;
| |
| last->prev = secondNode;
| |
| last->next = NULL;
| |
| last->data = 21;
| |
| | |
| //Ausgeben der Daten
| |
| for( ; root != NULL; root = root->next)
| |
| printf("%d ", root->data);
| |
| printf("\n");
| |
| | |
| //Daten rückwärts ausgeben
| |
| for( ; last != NULL; last = last->prev)
| |
| printf("%d ", last->data);
| |
| printf("\n");
| |
| }
| |
| | |
| Im Hauptspeicher kann man sich das wie folgt vorstellen.
| |
| | |
| c-linked-list-02.jpg
| |
| | |
| Die Zeiger zeigen natürlich immer auf den Anfang des Speicherbereichs, die Graphik vereinfacht das. Der Zeiger des ersten und des letzten Knotens muß explizit auf NULL gesetzt werden. Alle Algorithmen erkennen den Anfang bzw. das Ende an diesem NULL-Zeiger.
| |
| | |
| createRoot, appendNode, printList, listLength, seekList
| |
| | |
| Die folgenden Funktionen sind einfache Verallgemeinerungen des ersten Beispiels. Bei createRoot und appendNode müssen hier auch die prev-Zeiger gesetzt werden. printList, listLength und seekList sind wie bei der einfach verketteten Liste. printListReverse geht ans Ende der Liste und gibt sie dann rückwärts aus. seektListReverse geht ans Ende der Liste und sucht dann nach vorne.
| |
| | |
| =====createRoot=====
| |
| | |
| /*
| |
| * Die Funktion createroot erzeugt einen ersten Knoten mit Daten
| |
| * Falls kein Speicher angefordert werden kann, gibt die Funktion
| |
| * NULL zurück, ansonsten den Rootknoten.
| |
| */
| |
| node* createRoot(int data){
| |
| node *root = malloc(sizeof(node));
| |
| if (root == NULL) return NULL;
| |
| | |
| root->prev = NULL;
| |
| root->next = NULL;
| |
| root->data = data;
| |
| return root;
| |
| }
| |
| | |
| | |
| =====appendNode=====
| |
| | |
| /*
| |
| * Hängt am Ende an. Falls nicht der letzte Knoten übergeben wurde, wird das Ende gesucht.
| |
| * Auf diese Weise kann man einen beliebigen Knoten übergeben. Es wird nicht geprüft,
| |
| * ob die Daten bereits in der Liste sind. Wenn der erste Parameter NULL ist oder kein
| |
| * Speicher angefordert werden kann gibt die Funktion NULL zurück. Im Erfolgsfall wird
| |
| * der neue Knoten zurückgegeben.
| |
| */
| |
| node* appendNode(node* oldtail, int data){
| |
| if (oldtail == NULL ) return NULL;
| |
| | |
| node *newtail = malloc(sizeof(node));
| |
| if (newtail==NULL) return NULL;
| |
| | |
| while (oldtail->next != NULL) // ans Ende
| |
| oldtail = oldtail->next;
| |
| // nun ist oldtail->next NULL
| |
| oldtail->next = newtail;
| |
| newtail->prev = oldtail;
| |
| newtail->next = NULL;
| |
| newtail->data = data;
| |
| return newtail;
| |
| }
| |
| | |
| | |
| =====printList=====
| |
| | |
| /*
| |
| * Gibt die Liste ab der Stelle root aus
| |
| */
| |
| void printList(node* root){
| |
| if (root == NULL) return;
| |
| for ( ; root != NULL ; root = root->next)
| |
| printf("%d ", root->data);
| |
| printf("\n");
| |
| }
| |
| | |
| | |
| =====printListReverse=====
| |
| | |
| /*
| |
| * Geht ans Ende und gibt die Liste rückwärts aus
| |
| */
| |
| void printListReverse(node* curr){
| |
| if (curr==NULL) return;
| |
| for ( ; curr->next != NULL ; curr = curr->next) ;
| |
| // curr->next ist NULL
| |
| for ( ; curr != NULL ; curr = curr->prev)
| |
| printf("%d ", curr->data);
| |
| printf("\n");
| |
| }
| |
| | |
| | |
| =====listLength=====
| |
| | |
| /*
| |
| * Ermittelt die Länge der Liste ab dem übergebenen Knoten
| |
| */
| |
| int listLength(node* root){
| |
| if (root == NULL) return 0;
| |
| int len = 1;
| |
| for( ; root->next != NULL; len++)
| |
| root = root->next;
| |
| | |
| return len;
| |
| }
| |
| | |
| | |
| =====seekList)))))
| |
| | |
| /*
| |
| * Durchsucht die List nach einem übergebenen Datenelement. Wird es gefunden,
| |
| * so wird ein Zeiger auf den Knoten zurückgegeben, andernfalls NULL. Es wird
| |
| * nur das erste Auftreten des Elements gesucht
| |
| */
| |
| node* seekList(node* root, int data){
| |
| if (root == NULL) return NULL;
| |
| for(; root !=NULL; root = root->next)
| |
| if (root->data == data) return root;
| |
| | |
| return NULL;
| |
| }
| |
| | |
| | |
| =====seekListReverse=====
| |
| | |
| /*
| |
| * Durchsucht vom Ende her die Liste nach einem übergebenen Datenelement. Wird es
| |
| * gefunden, so wird ein Zeiger auf den Knoten zurückgegeben, andernfalls NULL.
| |
| */
| |
| node* seekListReverse(node* curr, int data){
| |
| if (curr == NULL) return NULL;
| |
| for ( ; curr->next != NULL ; curr = curr->next) ;
| |
| // curr->next ist NULL
| |
| | |
| for(; curr != NULL; curr = curr->prev)
| |
| if (curr->data == data) return curr;
| |
| | |
| return NULL;
| |
| }
| |
| | |
| | |
| =====Freigeben der Liste=====
| |
| | |
| Beim Freigeben der ganzen Liste muß man den Zeiger auf den nächsten Knoten zwischenspeichern bevor man den aktuellen Knoten freigibt, damit man noch auf den nächsten Knoten zugreifen kann.
| |
| | |
| /*
| |
| * Gibt den Speicher ab der Stelle curr frei. Ist der übergebene
| |
| * Knoten der Wurzelknoten, so wird die ganze Liste gelöscht.
| |
| */
| |
| void freelist(node* curr){
| |
| if (curr == null) return;
| |
| while (curr->next != null)
| |
| {
| |
| node *nextnode = curr->next;
| |
| free(curr);
| |
| curr = nextnode;
| |
| }
| |
| // jetzt muß noch das letzte gelöscht werden:
| |
| free(curr);
| |
| }
| |
| | |
| | |
| =====Löschen eines Elements der Liste=====
| |
| | |
| Beim Löschen eines Knotens sind drei Fälle zu unterscheiden, Löschen von root, Löschen innerhalb der Liste und Löschen des Endes der Liste. Im ersten Fall muß root neu gesetzt werden, aus diesem Grund wird ein Zeiger auf den Zeiger auf root übergeben. In den letzten beiden Fällen muß der Vorgänger bekannt sein und dessen Zeiger neu gesetzt werden, daher ist die Funktion aufwendiger.
| |
| | |
| /*
| |
| * Löschen eines Elements der Liste
| |
| * Returnwert:
| |
| * 0 falls nichts gelöscht wurde.
| |
| * 1 falls root gelöscht wurde (und es somit eine neue wurzel gibt)
| |
| * 2 falls innen gelöscht wurde
| |
| * 3 falls am ende gelöscht wurde
| |
| */
| |
| int delete(node** pRoot, int data){
| |
| if (pRoot == null || *pRoot == NULL) return 0; // Nichts gelöscht
| |
| | |
| // root löschen
| |
| if ( data == (*pRoot)->data )
| |
| {
| |
| printf("root löschen\n");
| |
| node* newroot = (*pRoot)->next; // kann NULL sein
| |
| if(newroot != NULL) newroot->prev = NULL; // wichtig !!
| |
| free(*pRoot);
| |
| *pRoot = newroot;
| |
| return 1; // neue root
| |
| }
| |
| | |
| /* Beginnend mit (*pRoot)->next wird geprüft, ob ein Knoten die übergebenen daten enthält
| |
| * Der Vorgänger wird gespeichert, damit man im Falles des Findens den Knoten aushängen kann
| |
| * Falls nichts gefunden wird, ist curr->next = NULL und man ist am Ende angekommen
| |
| * Nun wird noch curr untersucht und evtl abgehängt. Kommen Daten mehrmals vor, so wird
| |
| * nur das erste Vorkommen gelöscht. Da ein Löschen am Anfang eine neue Wurzel ergibt,
| |
| * wird immer die Wurzel zurückgegeben.
| |
| */
| |
| printf("löschen nach root\n");
| |
| node* prev = *pRoot;
| |
| node* curr = (*pRoot)->next;
| |
| for (; curr->next != null; prev = prev->next, curr = curr->next)
| |
| {
| |
| if ( curr->data == data )
| |
| {
| |
| printf("löschen innen\n");
| |
| // curr aushängen, curr löschen
| |
| prev->next = curr->next;
| |
| curr->next->prev = prev;
| |
| free(curr);
| |
| return 2; // innen gelöscht
| |
| }
| |
| // else // weitersuchen
| |
| }
| |
| // falls nicht gefunden ist hier curr->next = NULL
| |
| if ( curr->data == data )
| |
| {
| |
| puts("am ende");
| |
| prev->next = curr->next; // NULL
| |
| free(curr);
| |
| return 3; // am ende gelöscht
| |
| }
| |
| // else nichts gefunden
| |
| return 0;
| |
| }
| |
| | |
| | |
| =====Aufbau einer geordneten Liste=====
| |
| | |
| Der Aufbau einer geordneten Liste funktioniert ähnlich wie das Löschen eines Knotens, man unterscheidet die gleichen drei Fälle: Einhängen vor root, Insert nach root und vor dem Ende, und Anhängen am Ende.
| |
| | |
| /*
| |
| * Geordnetes einfügen
| |
| * Erhält einen Zeiger auf root, damit root über die parameterliste
| |
| * aktualisiert werden kann.
| |
| * Returnwert:
| |
| * 0 falls nichts eingefügt wurde.
| |
| * 1 falls vor root eingefügt wurde (und es somit eine neue wurzel gibt)
| |
| * 2 falls ein echtes insert stattfindet
| |
| * 3 falls am ende angehängt wird
| |
| */
| |
| int insert(node** pRoot, int data){
| |
| if (pRoot == null || *pRoot == NULL) return 0;
| |
| | |
| // "einhängen" vor pRoot
| |
| if ( data < (*pRoot)->data )
| |
| {
| |
| node *newroot = malloc(sizeof(node));
| |
| if (newroot != NULL)
| |
| {
| |
| newroot->next = *pRoot;
| |
| newroot->prev = NULL;
| |
| (*pRoot)->prev = newroot;->prev = newroot;
| |
| newroot->data = data;
| |
| *pRoot = newroot;
| |
| return 1; // 1 = neue pRoot
| |
| }
| |
| return 0;
| |
| }
| |
| | |
| /* Beginnend mit root wird geprüft, ob man zwischen
| |
| * root und und root->next einhängen kann. falls
| |
| * diese prüfung posotiv ausfällt wird eingehängt
| |
| * und mit return beendet. falls nicht, kommt man ans ende der liste
| |
| * (curr->next == null) und die schleife wird normal beendet.
| |
| * in diesem fall wird am ende angehängt.
| |
| */
| |
| node* curr = *pRoot;
| |
| for (; curr->next != null; curr = curr->next)
| |
| {
| |
| if ( curr->data < data && data <= curr->next->data)
| |
| {
| |
| //printf("insert nach curr\n");
| |
| node *newnode = malloc(sizeof(node));
| |
| if (newnode != null)
| |
| {
| |
| newnode->next = curr->next;
| |
| newnode->prev = curr;
| |
| curr->next->prev = newnode;
| |
| curr->next = newnode;
| |
| newnode->data = data;
| |
| }
| |
| return 2; // insert
| |
| }
| |
| //else weitersuchen
| |
| }
| |
| // falls kein einfügestelle gefunden, ist hier curr->next = NULL, also anhängen
| |
| node *newnode = malloc(sizeof(node));
| |
| if (newnode != null)
| |
| {
| |
| newnode->next = curr->next; // NULL
| |
| newnode->prev = curr;
| |
| curr->next = newnode;
| |
| newnode->data = data;
| |
| return 3; // append
| |
| }
| |
| return 0;
| |
| }
| |
|
| |
|
| ==Tag 2== | | ==Tag 2== |
Tag 1
Objektorientierung
Aufgabe: Personenverwaltung
Modelliere und Implementiere einen Personenverwaltung!
Die Klasse Personenverwaltung soll die Möglichkeit bieten Personen anzulegen und Personen zu löschen.
Zum Speichern kannst du gerne eine [Liste](https://docs.oracle.com/javase/7/docs/api/java/util/List.html) verwenden.
⚠️ Ziel ist es nicht in der Main Methode den Person-Konstruktor aufzurufen und diese Personen der Personenverwaltung zu übergeben! Stattdessen sollte die Personenverwaltung eine Methode `createPerson` bieten über die Personen erstellt werden können
Personen besitzen verschiedene Eigenschaften u.a. Vorname, Nachname, Geburtsdatum, Adresse, Geschlecht.
Die Klasse Personenverwaltung soll mehrere `create` Methoden zur Erstellung von Personen bieten:
- Eine Person die lediglich mit Vornamen und Nachnamen erstellt wird
- Eine Person die mit allen Werten erstellt wird
- Eine Person die mit Namen, Geschlecht und Geburtstdatum erstellt wird
Versuch für die Abbildung des Geschlechts ein [Java Enum](https://www.w3schools.com/java/java_enums.asp) zu verwenden. Eine Adresse hat vermutlich auch ihre eigene Klasse verdient da sie aus PLZ, Ort, Straßenname und Hausnummer besteht.
⚠️ Vergiss nicht auf die Unit Tests
Aufgabe: verkettete Liste
Wie auch Arrays ist die verkettete Liste eine lineare Datenstruktur, allerdings besteht die verkettete Liste aus einzelnen Elementen (Nodes) die durch Zeiger miteinander verbunden sind.
Um die Liste zu implementieren benötigst du 2 Klassen. Die Klasse Node (im Bild A, B, ..) hat ein Attribut value (z.B.: vom Typ String) und einen Zeiger vom Typ Node auf das nächste Element. Die zweite Klasse ist die Liste selbst. Hier implementieren wir alle Funktionen die unsere Liste haben soll. Zumindest brauchen wir add, remove, size, printList und get.
Für diese Aufgabe benötigst du KEINE anderen Datenstrukturen (Arrays, ArrayList, etc.).
Bonus: Du kannst deine Liste mit Generics(https://www.geeksforgeeks.org/generics-in-java/) implementieren, sodass der gespeicherte Wert value, beim erstellen der Liste dynamisch angegeben werden kann.
Aufgabe: doppelt verkettete Liste
Eine doppelt verkettete Liste ist Reihe von Elementen (auch Knoten/Nodes genannt), die durch zwei Zeiger miteinander verbunden sind. Zusätzlich zu einem Zeiger, der auf das nächste Element zeigt gibt es einen, der auf das vorhergehende Element zeigt. Eine doppelt verkettete Liste kann man also in beide Richtungen durchlaufen. Die Operationen auf einer doppelt verketteten Liste sind analog zu denen einer einfach verketteten Liste.
Folgene Funktionalität sollte unsere Liste zumindest haben:
appendNode
printList
printListReverse
listLength
seekList
seekListReverse
deleteNode
Wie auch bei der einfach verketteten Liste kannst du gerne Generics verwenden.
Tag 2
Aufgabe: Personenverwaltung
Erweitere deine Personenverwaltung um Access Modifier und Datenkapselung
https://wiki.streampy.at/index.php?title=Java_-_OOP_1#Personenverwaltung
