verkettete Liste verdoppeln < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | L1 sei eine einfach verkettete Liste. Implementieren Sie eine C-Funktion verdopple, die jedes Element von L1 verdoppelt, also beispielsweise aus der Liste(a,b,c) die Liste (a,a,b,b,c,c) macht. Dabei seien die Listenelemente wie unten definiert; die Variable anfang weise beim Aufruf von verdopple auf das erste Element der Liste.
struct element { /*Listenelement/
int datum;
struct element *nachfolger;
}
void verdopple (struct element *anfang); |
Hallo,
ich schreibe am Montag eine Informatik-Klausur und bereite mich anhand Alt-Klausuren vor. Nun zu meinem Problem, ich soll wie oben beschrieben die Liste L1 verdoppeln.
Das Prinzip von verketteten Listen habe ich verstanden, nur wie soll ich bei dieser Aufgabe vorgehen. Kann mir jemand einen Tipp geben oder irgendeinen Ansatz.
Bedanke mich schonmal im voraus.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo!
"Verkettete Liste" heißt doch, daß jedes Element die Adresse des Nachfolgers kennt.
Es ist ja klar, daß du zusätzlichen Speicherplatz brauchst, um die zusätzlichen Elemente unterzubringen. Du willst also das n-te Element verdoppeln, und mußt dafür erstmal ein neues Element anlegen, welches den gleichen Dateninhalt hat. Und: das n-te Element kennt die Adresse des ursprünglich (n+1)ten Elements. Was mußt du denn jetzt mit den Adressen machen, damit das neue Element dazwischen eingefügt wird?
|
|
|
| |
|
Hi,
so mein Lösungsansatz:
struct element *hilfszeiger;
hilfszeiger = (struct element *)malloc(sizeof(struct element *));
anfang->datum = 2; /*irgendwas*/
hilfszeiger = anfang; /*hilfszeiger zeigt auf anfang*/
anfang->nachfolger = hilfszeiger;
/*jetzt ist das zweite Element der liste 2 bzw. hilfszeiger*/
hilfszeiger->nachfolger = NULL;
/*das letzte Element zeigt auf NULL*/
so ich habs mal versucht und wollte fragen ob das so in etwa korrekt ist....
|
|
|
| |
|
Hallo!
Nee, da geht was schief.
> Hi,
>
> so mein Lösungsansatz:
>
>
> struct element *hilfszeiger;
>
> hilfszeiger = (struct element *)malloc(sizeof(struct
> element *));
>
> anfang->datum = 2; /*irgendwas*/
>
> hilfszeiger = anfang; /*hilfszeiger zeigt auf anfang*/
Damit ist hilfszeiger jetzt aber identisch mit anfang, sie belegen die gleichen Speicherbereiche. Mit anderen Worten: Du hast zwei Namen für ein Objekt.
Und dein mit malloc angeforderter Speicher dümpelt jetzt herrenlos in der Gegend rum.
Du meinst eher
hilfszeiger->daten = anfang->daten;
denn du willst ja den Inhalt verdoppeln.
>
> anfang->nachfolger = hilfszeiger;
> /*jetzt ist das zweite Element der liste 2 bzw.
> hilfszeiger*/
richtig.
>
> hilfszeiger->nachfolger = NULL;
> /*das letzte Element zeigt auf NULL*/
Ja gut, aber normalerweise besteht eine Liste ja aus mehreren Elementen. Du mußt dafür sorgen, daß dein Hilfszeiger auf das nächste Element zeigt.
Im Prinzip machst du sowas:
naechstes = dieses->nachfolger
neues= malloc(...)
neues->daten=dieses->daten;
neues->nachfolger=naechses;
dieses->nachfolfer=neues;
Und dann mußt du natürlich noch überlegen, wie du das jetzt über die gesamte Liste hinweg laufen läßt, um jedes Element zu verdoppeln. Das kann man übrigens in drei, wenn man böse ist, in 2 Zeilen erledigen.
|
|
|
| |
|
Hi,
danke jetzt wirds ersichtlich.
Also ich würde eine while-schleife benutzen um weitere Listenelemente zu verdoppeln.
while (neues->nachfolger != NULL)
neues=neues->nachfolger; /*hängt immer eine Liste hintedran*/
ist das korrekt oder bin ich ganz auf dem falschen Weg?
|
|
|
| |
|
Hallo!
Nach dem Einfügen von "neues" zwischen "dieses" und "naechstes" mußt du ein weiteres Element hinter "naechstes" einfügen
Also
while(){
/* einfügen wie oben*/
dieses=naechstes;
}
> while (neues->nachfolger != NULL)
> neues=neues->nachfolger; /*hängt immer eine Liste
> hintedran*/
Hier sehe ich das Problem, daß "neues" am Anfang noch gar nicht initialisiert wurde. Es kann also sein, daß neues->nachfolger schon auf NULL zeigt, aus Zufall, oder weil der Pointer nach gutem Programmierstil auf NULL gesetzt wurde.
Und "neues" schon vorher zu erschaffen, nur, damit es in der Schleife nochmal gesetzt wird, ist nicht gut.
Mach es so:
while(dieses != NULL){
/* einfügen wie oben*/
dieses=naechstes;
}
Der Witz hieran ist, daß die Pointer "neues" und "naechstes" nur innerhalb der Schleife gültig sein müssen, außerhalb muß nur "dieses" gültig sein, aber irgendwas muß ja auch als Listenanfang gegeben werden. Nebenbei wird die Schleife komplett übersprungen, wenn die Liste ganz leer ist.
|
|
|
| |
|
Hi,
danke nochmals für die Antwort.
Aber ich bin ein wenig durcheinander gekommen deswegen kriege ich jetzt nichts mehr gebacken. Könntest du mir diese while-schleife posten, damit ich das irgendwie nachvollziehen kann.
Wäre sehr nett.
MfG
|
|
|
| |
|
Hallo!
Na, du mußt eigentlich nur noch das, was ich oben gepostet habe, einfügen:
// Hier sollte die Liste bereits existieren,
// der Pointer "dieses" sollte auf das erste zu
// verdoppelnde Element zeigen
while(dieses != NULL){
element *naechstes, *neues; //Die Pointer brauchen wir
naechstes = dieses->nachfolger;
neues= malloc(...); //Speicher reservieren
neues->daten=dieses->daten; // Daten kopieren
neues->nachfolger=naechses; // neues Element mit dem nachfolgenden verbinden
dieses->nachfolfer=neues; // aktuelles Element mit dem neuen verbinden.
//FERTIG MIT EINSETZEN!
//Im nächsten Schritt müssen wir das nächste ALTE Element verdoppeln, deshalb das hier:
dieses=naechstes;
}
Zur Abbruchbedingung:
Wenn "dieses" das letzte Element der Liste ist, so ist naechstes=dieses->nachfolger==NULL. In der vorletzten Zeile wird in dem Fall auch dieses=NULL gesetzt, und das bricht die Schleife ab.
Wenn die Liste völlig leer ist, ist von Anfang an dieses==NULL.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:47 Mo 12.04.2010 | | Autor: | encephalon |
Danke sehr, jetzt hab ichs begriffen :D.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:53 So 11.04.2010 | | Autor: | rainerS |
Hallo!
> hilfszeiger = (struct element *)malloc(sizeof(struct element *));
Damit allozierst du Speicher in ausreichender Größe für einen Zeiger vom Typ struct element *. Du brauchst aber Speicher für das element selber...
Also:
hilfszeiger = (struct element *)malloc(sizeof(struct element));
Viele Grüße
Rainer
|
|
|
|
