Rekursiver Algorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:40 Mo 20.10.2014 | | Autor: | evinda |
Hallo!!!
Ich soll einen rekursiven Algorithmus schreiben, der, gegeben einer absteigend sortierten Liste mit m Elementen, eine neue Liste kreiert, die die Elemente von L, aufsteigend sortiert, enthält. Wir nehmen an, dass die Liste einfach verbunden ist und dass es einen Pointer gibt, der zum ersten Element der Liste zeigt.
Könntet ihr mir Tipps geben, wie ich so einen rekursiven Algorithmus schreiben könnte?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo!
Rekursion bedeutet ja, daß eine Funktion sich immer wieder selbst aufruft. Dabei gibt es immer eine Abbruchbedingung. Ist die erfüllt, ruft sich die aktuelle Funktionsinstanz nicht mehr selbst auf, sondern beendet sich, und die vorherige Instanz macht weiter.
Deine Funktion bekommt einen Zeiger auf das aktuelle Element der alten Liste übergeben, und es würde genau dieses Element an die neue Liste anhängen. Vorher sollte es sich aber noch selbst aufrufen, und dann müßte noch ne Abbruchbedingung rein.
Noch ein Tipp: Die Funktion kann auch den Zeiger auf das nächste Element der alten Liste berechnen!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:17 Mi 22.10.2014 | | Autor: | evinda |
> Deine Funktion bekommt einen Zeiger auf das aktuelle
> Element der alten Liste übergeben, und es würde genau
> dieses Element an die neue Liste anhängen. Vorher sollte
> es sich aber noch selbst aufrufen, und dann müßte noch ne
> Abbruchbedingung rein.
>
> Noch ein Tipp: Die Funktion kann auch den Zeiger auf das
> nächste Element der alten Liste berechnen!
Ich habe noch nicht verstanden, wie der Algorithmus eine neue Liste kreiert, die die Elemente von L, aufsteigend sortiert, enthält, indem sich die Funktion selbst aufruft.
Könntest du mir das nochmal erklären?
|
|
|
| |
|
Naja, so einfach mach ich es nicht.
Stell dir vor, ganz viele Informatiker sitzen in einer Reihe. Der erste bekommt eine Liste in die Hand gedrückt, in die jeder der Reihe nach, beginnend mit dem letzten Informatiker in der Reihe, seinen Namen eintragen soll.
Schenkt man den Gerüchten glauben, bewegen sich Informatiker nicht so gerne, daher wird der erste nicht aufstehen, und die Liste dem letzten bringen. Jeder kann die Liste nur seinem direkten Nachbarn weitergeben.
Frage: Wie machen die Informatiker das nun, daß am Ende alle Namen in umgekehrter Reihenfolge auf der Liste stehen?
Und genauer: Was sind die einzelnen Schritte, die jeder Informatiker ausführt?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:19 Do 23.10.2014 | | Autor: | evinda |
Sind die Schritte die folgenden?
Der erste Informatiker gibt dem zweiten Informatiker die Liste weiter, der zweite Informatiker gibt dem dritten Informatiker die Liste weiter,...., der vorletzte gibt dem letzten Informatiker die Lister weiter. Er schreibt dann seinen Namen, und gibt die Liste seinem direkten Nachbarn zurück, der vorletzte Informatiker schreibt dann seinen Namen und gibt die Liste den dritten von hinten weiter,..., der erste Informatiker bekommt die Liste und schreibt seinen Namen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:59 Fr 24.10.2014 | | Autor: | evinda |
Also muss der Algorithmus so sein?
Funktion(List1){
Pointer *p,*q;
p=List1;
while (p!=NULL){
p=p->next;
}
q=p;
}
Falls ja, wie kann ich weitermachen?
|
|
|
| |
|
Nein, das ist keine Rekursion. Genau das gleiche Code-Fragment hast du auch schon in einer anderen Frage gestellt. Event_Horizon hat dir ja schon einen guten Tipp gegeben, den du auch richtig verstanden hast. Offensichtlich hat der Transfer auf dein eigentliches Problem nicht geklappt, daher noch ein Tipp von mir: Deine Funktion muss sich selbst aufrufen. Eine while-Schleife ist nicht notwendig.
|
|
|
| |
|
Richtig. Überlege dir nun, wie du das in Code umsetzen kannst. Das Stichwort ist bereits in der ersten Antwort gefallen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:20 Fr 24.10.2014 | | Autor: | evinda |
Ich habe folgendes versucht, bin mir aber nicht sicher ob es richtig ist:
NODE *Change( NODE *L1){
NODE *p1=L1;
NODE *L,new;
while (p1 != NULL){
p1=p1->next;
}
new=newcell(NODE);
new->data=p1->data;
new->next=NULL;
ListDelete(L1,p1);
L=new;
Change(L1);
}
ListDelete wäre ein Algorithmus, der ein Element einer Liste löscht.
Oder könnte man es besser machen?
|
|
|
| |
|
Hallo!
Ich denke,du hast das was konzeptionelles noch nicht verstanden.
Mal einfacher:
Du willst die Summe der Zahlen 1...n rekursiv bestimmen. Eine Funktion dazu sieht so aus:
| 1: | int mySum(int n){
| | 2: | if(n == 0){
| | 3: | return(0);
| | 4: | }
| | 5: | else{
| | 6: | return ( n+ mySum(n-1) );
| | 7: | }
| | 8: | }
| | 9: |
| | 10: |
| | 11: | int s = mySum(7);
| | 12: |
| | 13: | printf(s); |
Das wichtige daran ist, daßdie Funktion sich selbst mit einem anderen parameter aufruft.Versuche mal,dieses Beispiel genau zu verstehen.
Dein Programm müßte eher so aussehen:
| 1: | Node* Change(Node *Lold, Node *Lnew){
| | 2: | if(Lold->next != NULL){ // Es gibt noch weitere Elemente in der Liste
| | 3: | Lnew= Change(Lold->next, Lnew);
| | 4: | }
| | 5: | AddNode(Lnew, Lold->Value);
| | 6: | return (Lnew->next);
| | 7: | } |
Lold ist hier ein Zeiger auf das aktuelle Listenelement der alten Liste. Es muß geprüft werden, ob es noch weitere Listenelemente gibt. Wenn ja, ruft sich die Funktion selbst auf, aber eben mit dem nächsten Element der alten liste als Parameter.
Lnew ist ein Zeiger auf das letzte Element der neuen Liste. Wenn die Funktion ein neues Element an die Liste anhängt, gibt sie den Zeiger auf das nun neue letzte Element zurück, und die aufrufende Funktion muß dies natürlich entgegen nehmen, weil sie ihr Element natürlich auch an dieses neue Ende anhängen will.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:24 Sa 25.10.2014 | | Autor: | evinda |
Warum ist Lnew ein Parameter der Funktion?
Könntest du mir bei einer bestimmten Liste erklären, wie dein Algorithmus funktioniert?
|
|
|
| |
|
Hallo!
Naja, wenn die Funktion doch der neuen Liste ein Element hinzufügen soll, muß sie doch das bisherige letzte Element der neuen Liste kennen.
Wenn also Lnew das letzte Element der neuen Liste ist, wird mit
AddNode(Lnew, Lold->Value);
ein neues Element an die neue Liste angehängt, welches den Wert des aktuellen Elements der alten Liste enthält.
Mit return (Lnew->next); wird anschließend das neue letzte Element der neuen Liste zurück gegeben.
Was denkst du denn, was meine Funktion mit einer konkreten Liste macht?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:36 So 26.10.2014 | | Autor: | evinda |
Ich habe es auch nochmal selbst folgenderweise versucht:
Node *Change(Node *Lold){
if (Lold->next!= NULL)
Change(Lold->next)
Addnode(Lnew, Lold->Value);
return Lnew;
}
Könntest du mir sagen ob es auch richtig ist?
|
|
|
| |
|
Hallo!
Nunja... Lnew ist ja ein Knoten der neuen Liste. Und bei mir sollte Lnew immer das letzte Element der Liste sein.
In der Funktion selbst kommt Lnew gar nicht vor. Das ist durchaus möglich, wenn Lnew eine globale Variable ist. Dann sollte die Funktion AddNode selbst aber Lnew nach dem Anhängen des neuen Elements gegen dieses ersetzen.
Denk bitte auch dran, daß AddNode keine allgemein bekannte Funktion ist. Ich habe AddNode() geschrieben, damit klar ist, daß hier ein Element an eine Liste angehängt werden soll. Im Prinzip mußt du diese Funktion auch noch schreiben.
Noch was: Du benutzt keine geschweiften Klammern hinter dem IF. Das ist korrekt und funktioniert hier bei der einen Zeile, du solltest dir aber dringend angewöhnen, IMMER Klammern zu verwenden. Denn irgendwann schreibst du noch ne Zeile dazu, und vergisst, die dann fälligen Klammern hin zu schreiben. Und dann wunderst du dich, warum der Code nicht das tut, was du willst.
|
|
|
|
