141210-U.md

Aufgabenblatt 12

Aufgabe 33

Wird in der Ubung präsentiert. (Dies war Teil einer Klausuraufgabe. Zeit 20 Minuten.)

Schrieben Sie eine Funktion, die einen eindimensionalen Vektor vom Typ int spiiegelt, d.h. das erste Elm wird zum letzten Elm, das letzte Elm zum ersten, das zweite zum vorletzten, das vorletzte zum zweiten usw.

int f(int a[], l){ int i,t; if(l <= 0)return -1; //Fehler, da Array-Länge <= 0 for(i=0; i < l/2; i++){ //von 0 bis l halbe, danach t=a[l-i-1]; a[l-i-1]=a[i]; a[i]=t; } return 0; }

Aufgabe 34

Erklären Sie, was die Funktion f macht und wie sie funktioniert. Geben Sie dazu eine Skizze an.

/* über eine externe liste l, Suche nach v, Rueckgabe 1=true wenn gefunden, 0=false wenn nicht  */
int f(list *l, int v) {
	if(l == NULL) return 0;				// Wenn l leer ist (Ende der Kette), false
	/*else */if(l->item == v) return 1;	// Wenn aktuelles Elm in l mit v übereinstimmt, true
	/*else */return f(l->next , v);		// Sonst suche beim nächsten Elm (Nachfolger) weiter
}

v=2
{1}->{2}->{3}->NULL
 ^==v -> f(l-next, 2)
{1}->{2}->{3}->NULL
      ^==v -> f(l-next, 2)

Aufgabe 35

Ein Wurzelbaum ist ein Baum, der einen Knoten besitzt, der als Wurzel ausgezeichnet ist. Ein binärer Wurzelbaum ist ein Wurzelbaum, in dem jeder Knoten, der kein Blatt (Endknoten) ist, genau zwei Nachfolger besitzt.

a) Geben Sie die Deklaration einer Datenstruktur an, die einen binären Wurzelbaum darstellt.

struct _rtree {
	int item;
	struct _rtree *nextl;
	struct _rtree *nextr;
};
typedef struct _rtree rtree;

b) Geben Sie eine Funktion an, die einen binären Wurzelbaum durchsucht.

rtree *search_rtree(rtree *t, int v) {
	if(t == NULL) return 0;
	if(t->item == v) return t;
	if(v < t->item) return search(t->nextl, v);
	return search(t->nextr, v);
}

/* ohne sortierten baum */
int s(rtree *t, int v){
	if(t==NULL) return 0;
	if(t->item==v)return 1;
	/*if(s(item->nextl,v ))return 1;
	if(s(item->nextr,v ))return 1;
	return 0;*/
	if(s(item->nextl,v ) || s(item->nextr,v ))
		return 1;
	else
		return 0;
}