Lösungen Aufgabenblatt 12

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Lösungen Aufgabenblatt 12
Hi, hab mal meine Lösungen reingestellt, kein Anspruch auf absolute Fehlerfreiheit… , erste Tests gingen aber!
Falls Fehler drin sind bitte ich um Mitteilung…

;Hilfsfkt.
(define (square x) (* x x))

;Aufgabe 12.1.2
;========================================================

; Variante 1 Liste muss übergeben werden
(define (lazy fn lst)
   (for-each (lambda (x) (display (fn x))(newline)) lst))

; Variante 2: Übergeben wird Fkt.name ln + beliebig viele args
;             args wird dann zur Liste gemacht
(define (lzy ln . args)
   (for-each (lambda (x) (display (ln x))(newline)) args)) 

;Aufgabe 12.1.3
;========================================================

;Variante 3: so können der Fkt. auch beliebig viele Args übergeben
;            werden, aus args wird liste gebaut

(define disp              ;entspricht: (define (disp .args) ...)
   (lambda args
      (for-each display args)
      (newline)))

;Aufgabe 12.3: Datentyp: Stack Implementierung als flache Liste
;==============================================================
;Bsp: '(*stack* 9 8 7 6 5 3 1)

;Konstruktor: Erzeugungsfkt.
(define (init-stack!) '(*stack*))

;Prädikate: Typüberprüfungsfkt.
(define (stack? stck)
   (if (list? stck)
      (if (equal? (car stck) '*stack*)
         #t
         #f)
      #f))

(define (is-empty? stck)
   (if (stack? stck)
      (if (equal? (cdr stck) '()) 
         #t
         #f)
      (error "Objekt not a Stack")))

;Selektoren: Auswahlfkt.
(define (front stck)
   (if (not (is-empty? stck))
      (car stck)
      (display "Stack is empty")))
      
;Modifikatoren: Veränderungsfkt. 
(define (push! stck intnr)
   (if (and (integer? intnr) (stack? stck))
      (set-cdr! stck (cons intnr (cdr stck)))
      (display "False Objekt-Typ givenn")))
      
(define (pop! stck)
   (if (not (is-empty? stck))
      (begin (set-cdr! stck (cddr stck)) stck)
      (display "Stack is almost emptyn")))
      


;Aufgabe 12.2
;====================================================

(define (empty-tree? tree) (eq? tree '()))
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right) (list entry left right))

(define (element-of-set? x set)
   (cond ((null? set) #f)
      ((= x (entry set)) #t)
      ((< x (entry set)) (element-of-set? x (left-branch set)))
      ((> x (entry set)) (element-of-set? x (right-branch set)))))

(define (adjoin-set x set)
   (cond 
      ((null? set) (make-tree x '() '()))
      ((= x (entry set)) set)
      ((< x (entry set))
       (make-tree (entry set) (adjoin-set x (left-branch set)) (right-branch set)))
       ((> x (entry set))
        (make-tree (entry set) (left-branch set) (adjoin-set x (right-branch set))))))

(define tree1 (make-tree 1 '() '() ))
(define tree2 (make-tree 5 '() '() ))
(define tree3 (make-tree 30 '() '()))
(define tree4 (make-tree 3 tree1 tree2))
(define tree5 (make-tree 9 '() tree3))
(define tree6 (make-tree 7 tree4 tree5))

(define tree1- (make-tree 1 '() '() ))
(define tree2- (make-tree 15 '() '() ))
(define tree3- (make-tree 30 '() '()))
(define tree4- (make-tree 12 tree1- tree2-))
(define tree5- (make-tree 21 '() tree3-))
(define tree6- (make-tree 17 tree4- tree5-))

;Aufgabe 12.2.a:

(define (liste->baum lst)
   (define (helper lst tree)
      (if (null? lst)
         tree
         (helper (cdr lst) (adjoin-set (car lst) tree))))
   (helper lst '()))

;Aufgabe 12.2.b:

(define (baum->liste tree)
   (cond
      ((and (not (empty-tree? (left-branch tree)))
            (not (empty-tree? (right-branch tree))))
            (append (baum->liste (left-branch tree))
                    (append (list (entry tree)) (baum->liste (right-branch tree)))))
      
      ((and (empty-tree? (left-branch tree))
            (empty-tree? (right-branch tree)))
            (list(entry tree)))
                
      ((empty-tree? (left-branch tree))
       (append (list (entry tree)) (baum->liste (right-branch tree))))
       
      ((empty-tree? (right-branch tree))
       (append (baum->liste (left-branch tree)) (list (entry tree))))))  

;Aufgabe 12.2.c:

(define (baum->liste-praefix tree)
   (cond
      ((and (not (empty-tree? (left-branch tree)))
            (not (empty-tree? (right-branch tree))))
            (append (baum->liste-praefix (right-branch tree))
                    (append (list (entry tree)) (baum->liste-praefix (left-branch tree)))))
      
      ((and (empty-tree? (left-branch tree))
            (empty-tree? (right-branch tree)))
            (list(entry tree)))
                
      ((empty-tree? (left-branch tree))
       (append (baum->liste-praefix (right-branch tree)) (list (entry tree))))
       
      ((empty-tree? (right-branch tree))
       (append (list (entry tree)) (baum->liste-praefix (left-branch tree))))))
       
;Aufgabe 12.2.d:
;Vereinigungsmenge
(define (vereinigungM tr1 tr2)
   
   (define (helper lst newtree)
      (cond
         ((null? lst) newtree)
         ((element-of-set? (car lst) newtree)
          (helper (cdr lst) newtree))
         (else (helper (cdr lst) (adjoin-set (car lst) newtree)))))     
   
   (helper (baum->liste tr2) tr1)) 

;Schnittmenge
(define (schnittM tr1 tr2)
   
   (define (helper lst newtree)
      (cond
         ((null? lst) newtree)
         ((element-of-set? (car lst) tr1)
          (helper (cdr lst) (adjoin-set (car lst) newtree)))
         
         (else (helper (cdr lst) newtree))))     
   
   (helper (baum->liste tr2) '()))
   
;Differenzmenge
(define (differenzM tr1 tr2)
   
   (define (helper lst referenz newtree)
      (cond
         ((null? lst) newtree)
         ((element-of-set? (car lst) referenz)
          (helper (cdr lst) referenz newtree))
         (else (helper (cdr lst) referenz (adjoin-set (car lst) newtree)))))     
   
   (vereinigungM (helper (baum->liste tr2) tr1 '())
                  (helper (baum->liste tr1) tr2 '())))         
   

eine Klammer ist falsch, aber ich sag dir net wo fg


Wenn’s am Englisch mangelt, wie wär’s mit Deutsch? :smiley:

BUG!!!
Ganz fieser schlimmer Fehler!!
Naja, bei der 12.3 sollte die Funktion (front) vielleicht so lauten:

... (cadr stck) ...

um nicht “stack”, sondern das eigentlich 2. Element zurückzugeben.


ist die 12 b.) so nicht wesentlich einfacher?

(define (baum->liste-infix2 baum)
  (if (empty-tree? baum)
      '()
      (append (baum->liste-infix2 (left-branch baum))
              (cons (entry baum)
                    (baum->liste-infix2 (right-branch baum))))))

Danke für Eure Hilfe,…

@frahi Kann Sie net finden, grins :wand:
@Yves … DANKE, is natürlich bockmist gwesen… :wink:
@Krull Werde sicherlich beim nächsten Mal auf absolut fehlerfreies Englisch achten :-p