Abstrakte Datentypen

Onyx

Also, hier mal ein Beispiel(Nicht von mir)! Hab mal als Komm. das reingeschrieben was ich nicht nachvollziehen kann!
Das Programm liest integer ein bis eine 0 kommt und gibt die Liste dann nach FIFO aus.

#include <stdio.h>
#include <stdlib.h>

struct liste{
int zahl;
struct liste *next;
};

int main (void)
{
struct liste *start = NULL;
struct liste *help = NULL;

start = (struct liste *)malloc(sizeof(struct liste));/*Warum wird hier schon speicher mallokiert und in der do-schleife nochmal?*/
start->next = NULL;

help = start;

printf("Bitte Integer eingeben! 0 zum beenden!\n");

do{
help->next = (struct liste *)malloc(sizeof(struct liste));
help = help->next;
scanf("%i",&help->zahl);
help->next = NULL;
}while (help->zahl != 0);

printf(" Die Liste :\n");

while(start->next!=NULL)
{
printf("%i\n",start->zahl);

start = start->next;
}
return(0); /*An welcher Stelle wird der Zeiger auf das erste Element verwiesen und wo wird er wieder aufgerufen bzw. hochgezählt? Also auf das nächste auszugebende Element verwiesen? */
}

Wäre echt dankbar wenn das mal einer mit mir durchgeht. Sitz schon den ganzen Tag da dran...

c.rackwitz

der code ist mist.

da hab ich mich ausgelassen. reicht das?
http://c-plusplus.net/forum/viewtopic-var-t-is-185014--and-printview-is-1.html
(meine beiden laengeren posts, die sollten relevant sein)

Onyx

Naja das Problem is, des is ein Beispiel meines Profs zu Elemente an Listenanfang und Elemente am Listenende einfügen. Also eines von beiden ;-)!
Hast du ne bessere Idee wie ich des bis Donnerstag reinkrieg?
Langsam macht sich echt ma panik breit wenn ich mir überleg dass ich noch stacks und binärmaum lernen und checken muss! Hast du nen MSN oder skype und morgen ma zeit?

pale dog

http://www.cosc.canterbury.ac.nz/mukundan/dsal/LinkListAppl.html

Onyx

Ja auch diese graphische Veranschaulichung finde ich toll, hab sie aber im script... Naja, wahrscheinlich isses jetzt zu spät noch was zu checken! Danke Euch trotzdem mal für heute und melde mich morgen wieder !

c.rackwitz schrieb:

der code ist mist.

Es ist ganz was anderes, was hier Mist ist

c.rackwitz

wenns denn sooo not tut, icq hab ich und wenn du auf irc.freenode.net kommst, da bin ich oft in #D.

skype is nich, aber wenn die sache kurz und schmerzlos ablaufen soll, besorg dir gobby [1,2] (zum code zerlegen) und VNC [3] (client reicht, nehm ich gerne als whiteboard).

[1] http://gobby.0x539.de/trac/
[2] http://gobby.0x539.de/trac/wiki/Download
[2] http://en.wikipedia.org/wiki/Vnc#See_also

Onyx schrieb:

Naja, wahrscheinlich isses jetzt zu spät noch was zu checken!

Es ist nie zu spät !

Onyx schrieb:

/*Warum wird hier schon speicher mallokiert und in der do-schleife nochmal?*/

Gute Frage, frag deinen Prof. Die Variable zahl der ersten Struktur bleibt deshalb jedenfalls unitialisiert.
Das dürftest du spätestens bei der Ausgabe gemerkt haben.
Oder hast du das Programm nicht kompiliert und laufen lassen ?
Naaahaaa ?!

Onyx schrieb:

/*An welcher Stelle wird der Zeiger auf das erste Element verwiesen ...

Auf das erste Element wird der Zeiger start hier verwiesen,
hierbei wird auch noch gecastet, was vermieden werden sollte:

start = (struct liste *)malloc(sizeof(struct liste));

Besser ist, nicht zu casten:

start = malloc(sizeof(struct liste));

Onyx schrieb:

...und wo wird er wieder aufgerufen bzw. hochgezählt? Also auf das nächste auszugebende Element verwiesen? */

Aufgerufen und hochgezählt wird er wieder hier:

start = start->next;

Dabei hangelt sich der Zeiger durch wiederholten Aufruf in der while-Schleife von einer Struktur zur anderen.

Für das Veständnis der Bildung einer verketteten Liste ist es sehr hilfreich, wenn man sich die einzelnen Schritte auf ein Blatt Papier aufzeichnet.

************* schrieb:

Für das Veständnis der Bildung einer verketteten Liste ist es sehr hilfreich, wenn man sich die einzelnen Schritte auf ein Blatt Papier aufzeichnet.

So ist es.

Jede Struktur wird mit einem Kästchen dargestellt.
Der Inhalt des Kästchens sind die Variablen.
Ein Zeiger ist ein Pfeil, der einen Namen hat.
( start, help, help-next )

start = malloc(sizeof(struct liste));
start->next = NULL;

Eine Struktur vom Typ liste wurde mit malloc erzeugt.
Malloc liefert als Rückgabewert eine Adresse, diese
Adresse ist eine Zahl, diese Zahl ist die Nummer der
Speicherzelle im Arbeitsspeicher, an der die erzeugte Struktur beginnt.

Im Zeiger start ist jetzt also die Adresse der ersten erzeugten Struktur
gespeichert. Mann sagt auch, der Zeiger zeigt auf die Struktur.

Grafisches vorgehen:

Kästchen Nr.1 malen. Was kommt ins Kästchen rein ?
Die Variablen zahl, next.

start zeigt auf das Kästchen Nr.1, also male einen
Pfeil namens start, der auf das Kästchen Nr.1 zeigt.

Was steht in zahl ? Undefiniert, Datenmüll.
Auf was zeigt start->next ? Auf nichts, auf NULL.
Also ins Kästchen Nr.1 schreiben: zahl = Müll.
Einen Pfeil malen, der von next im Kästchen Nr.1
ausgehend nach NULL zeigt.

help = start;

Pfeil namens help malen, der auf das Kästchen
Nr. 1 zeigt.

Es zeigen jetzt also zwei Pfeile auf das erste Kästchen, nämlich
start und help.

Wir betreten die do-while-Schleife.

help->next = malloc(sizeof(struct liste));
Die zweite Struktur vom Typ liste wurde erzeugt.
Kästchen Nr.2 malen, Variablen(zahl, next) reinschreiben.

Der Zeiger help->next zeigt auf diese Struktur, weil ihm ja von malloc
die Adresse geliefert wurde.

help->next, ist aber nichts weiter, als die Variable next im Kästchen Nr.1 .
Darum zeigt die Variable next im ersten Kästchen nicht mehr auf NULL, wegradieren.
Pfeil malen der von der Variable next ausgehend auf das Kästchen Nr.2 zeigt.

help = help->next;
Der Zeiger help zeigt jetzt nicht mehr auf das erste Kästchen, sondern auf
das zweite, weil ja help->next die Adresse der zweiten Struktur hat.

Also, Pfeil namens help wegradieren. Einen neuen Pfeil namens help,
der jetzt auf Kästchen Nr.2 zeigt, malen.

scanf("%i",&help->zahl);
Da ja help auf das Kästchen Nr.2 zeigt, steht nun eine Zahl in der Variabe zahl
des zweiten Kästchens, die mit scanf eingelesen wurde, weil ja help->zahl
auf die Zahl im zweiten Kästchen zeigt.

help->next = NULL;
Der Zeiger des Kästchens Nr.2 zeigt auf nichts, auf NULL.
Pfeil malen, der von der Variable next im zweiten Kästchen rausgeht und auf
NULL zeigt.

Damit wären wir am Ende der do-while-Schleife angekommen.
Das ganze wiederholt sich jetzt so lange, bis der Benutzer eine 0,
oder dusseliger weise einen Buchstaben eintippt.
Im letzteren Fall dürfte dann das Programm abschmieren, wei scanf zu dämlich ist,
solche Situationen zu meistern.

Alles klar ?

Gruß.

Onyx

Hehe okay, genauso eine Anleitung für Vollidioten(<-hier: ICH!!!) hba ich gesucht! Vielen Dank! Jetzt wird langsam der Dimmer hochgedreht und es wird heller

Achwas, sieh das nicht so pessimistisch.
Das ganze in nunmal ziemlich abstrakt und das mit der grafischen Darstellung sehr gut geeignet, um sich das ganze etwas klar zu machen.
Ein ganz normaler Vorgang

Okay, klappt soweit.
Wie kann ich denn jetzt, an obigem Beispiel:
1. Das erste Element löschen
2. Das letzte Element löschen
3. Ein beliebiges Element der Liste löschen? Also zum Beispiel die dritte Eingabe oder die Zahl 5(die ich vorher eingegeben habe)?
4. Anzahl der Listenelemente bestimmen
5.Datensatz an best. Position finden?
6. Einfügen an vorgegebener Position?

Ich weiss ich weiss, ich nerv euch... Seid aber meine einzige Hilfe

c.rackwitz

jetz waer ne runde lisp nicht schlecht. da sind alle (normalen) listen verkettete listen.

ein element ist ein paar. es hat 2 "faecher", car (wert) und cdr (naechstes) genannt.

int length(Pair *s)
{
    if (!s)
        return 0;
    else
        return 1 + length(s->next);
}

(define (length s)
  (if (null? s)
      0
      (+ 1 (length (cdr s)))))

umformung nach C mit pointern sei dir ueberlassen.

dass lineare rekursion aequivalent zu iteration ist, sollte dir bekannt sein.
deine aufgabe ist es, diese linear rekursive funktion in eine explizit iterative zu verwandeln.

Onyx

Also ich hab ma einen weiteren Zeiger namens *zeiger erstellt und das so versucht!

struct zahlen *zeiger;

nach der do-schleife dann:

zeiger = start->next;
free(start);
start = zeiger;

komischerweise ist der erste wert aber immernoch in der ausgabe drin...

Und noch ne Frage.
Gibts einen einfachen Befehl um die komplette Liste zu löschen? Also ohne dass ich die zeiger von element zu element springen lassen muss um sie einzeln auszulösen und mit free freizugeben?

Was ist bei dir der erste Wert ? Der nicht initialisierte Datenmüll in der ersten Struktur oder der erste von Dir eingegebene Wert ?

Naaahaaa ??

c.rackwitz

du musst die liste selber loeschen. machs einfach und stell dich nicht so an.

Onyx schrieb:

komischerweise ist der erste wert aber immernoch in der ausgabe drin...

Noch einmal:
Was ist bei dir der erste Wert ? Der nicht initialisierte Datenmüll in der ersten Struktur oder der erste von Dir eingegebene Wert ?

Onyx schrieb:

Und noch ne Frage.
Gibts einen einfachen Befehl um die komplette Liste zu löschen? Also ohne dass ich die zeiger von element zu element springen lassen muss um sie einzeln auszulösen und mit free freizugeben?

Nein.

Wären es z.B. 10 erzeugte Strukturen mit malloc:
start = malloc( 10 * sizeof( struct liste ) );
Dann wäre es ein im Arbeitsspeicher zusammenhängender Block und ein free(start)
würde den reservierten Speicher der 10 Strukturen wieder freigeben.

Hier sind die Strukturen sind im Arbeitsspeicher jedoch 'verstreut'. Nur start kennt die erste Struktur und jede next Variable kennt die Adresse der nächsten Struktur im Arbeitsspeicher.
Also bleibt nichts anderes übrig, als von Zeiger zu Zeiger zu hüpfen.
Generell gilt die Regel:
für jedes malloc ein free

Na der erste eingegebene Wert!

Und das wundert dich jetzt ?