Rekursives Zusammenfügen zweier Queue in C

24.01.2016, 21:54

Chirs

Rekursives Zusammenfügen zweier Queue in C

Meine Frage:
Hallo,

ich hätte nochmal eine Frage bezüglich Queue.

Und zwar möchte ich eine Funktion schreiben, die zwei bestehende Queue zu einer zusammenfügen. Dabei kann eine in die andere angefügt werden. Ich möchte diese Aufgabe rekursiv lösen.

Ich habe einmal einen Code zusammen gebastelt aber leider ist der noch nicht fertig,da ich mir nicht sicher bin ob der rekursiven Aufruf so richtig ist.
Vielleicht kann mir hier jemand bei dieser Aufgabe weiterhelfen.

Vielen Dank schon mal :-)

Grüße

Meine Ideen:
Hierzu habe ich mir folgende Terminierungsfälle überlegt:

wenn beide leer sind dann soll 0 zurückgegeben werden.
wenn Erste 0 ist soll die Zweite zurückgegeben werden.
wenn Zweite 0 ist soll die Erste zurückgegeben werden.
sonst soll erstes Element von der ersten Queue hinten an die zweite Queue angefügt werden.

Ich habe bereits folgende Funktionen gegeben:

isempty() -> prüft ob Queue leer ist
append() -> fügt hinten ein Element an die Queue an
top() -> gibt erstes Element der Queue zurück
rest() -> löscht erstes Element der Queue

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:


int merge(queue *a,queue *b)
{if (isempty(a) == 0 && isempty(b) == 0))
  return 0;
else if isempty(a) != 0 && isempty(b) == 0)
  return a;
else if isempty(a) == 0 && isempty(b) != 0)
  return b;
else return merge((append(b,top(a)),rest(a))
}

25.01.2016, 06:12

Auf diesen Beitrag antworten »

eulerscheZahl

Gibt isempty wirklich eine 0 zurück, wenn die queue leer ist? Das hätte ich genau anders herum erwartet, weil man dann einfach isempty() bzw. !isempty() schreiben könnte.
Ich habe mir nochmal deinen Code der Funktion angeschaut: Rekursives Suchen in Queue.
Das kommt mir komisch vor, da 0 zurückgegeben wird, egal ob die queue leer ist.

25.01.2016, 07:39

Auf diesen Beitrag antworten »

Chirs

Danke für die Antwort.

Du meinst dann bestimmt so:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:


int merge(queue *a,queue *b)
{if (isempty(a)&& isempty(b))
  return 0;
else if (!isempty(a)&& isempty(b) )
  return a;
else if (isempty(a)&& !isempty(b))
  return b;
else return merge((append(b,top(a)),rest(a))
}

oder ?

Da hast du recht da habe ich einen Fehler gemacht, da der Vergleich mit 0 dann wenig Sinn macht.

Theoretisch könnte ich es aber auch so schreiben:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:


int merge(queue *a,queue *b)
{if (a == NULL && b == NULL)
  return 0;
else if (a != NULL && b == NULL )
  return a;
else if (a == NULL && b != NULL)
  return b;
else return merge((append(b,top(a)),rest(a))
}

oder ?

Grüße

25.01.2016, 12:39

Auf diesen Beitrag antworten »

eulerscheZahl

Sieht gut aus.

Neue Frage »

Antworten »

Rekursives Zusammenfügen zweier Queue in C

Verwandte Themen