Проблемы с сортировкой - PullRequest
Новая
       34

Проблемы с сортировкой

0 голосов
/ 29 октября 2010

Я изучаю Scheme в классе, и мой профессор не отвечает на вопросы после 8:00, поэтому я надеюсь, что вы все сможете мне помочь.По сути, у меня есть тип семейного древа, и я пытаюсь собрать всех предков одного человека и отобразить их в виде одной строки, отсортированной по алфавиту.

Проблема в том, что из-за рекурсии каждое поколение объединяется в свою собственную строку, поэтому вместо того, чтобы получать "человек", "человек б", я получаю "человек человек б".Поэтому, когда я собираюсь отсортировать их, прежде чем добавить их все к одной строке, он сортирует только первое имя в паре, что означает, что второе имя не сортируется.Я не совсем уверен, как это объяснить сам.Я надеюсь, что код объяснит большую часть этого для меня. 

(define-struct person  
  (
  first    ; a string: first name
  last    ; a string: last name
  sex     ; a symbol: 'male, 'female
  eyes     ; a symbol: 'blue, 'brown', 'green
  hair     ; a symbol: 'blonde, 'brown, 'black, 'red
  mother; a person: empty if not known
  father; a person: empty if not known
  born    ; a number: year of birth
  )
)

(define P-00000 (make-person "Alexandra" "Harper" 'female 'blue 'red empty empty 1897))
(define P-10000 (make-person "Joshua" "Sherman" 'male 'green 'blonde empty empty 1881))
(define P-20000 (make-person "Alexandra" "Hazel" 'female 'brown 'red empty empty 1906))
(define P-30000 (make-person "Christopher" "Abdul" 'male 'brown 'brown empty empty 1904))
(define P-01000 (make-person "Lauren" "Sherman" 'female 'green 'black P-00000 P-10000 1914))
(define P-21000 (make-person "Alexander" "Abdul" 'male 'blue 'brown P-20000 P-30000 1927))
(define P-01100 (make-person "Justine" "Abdul" 'female 'blue 'black P-01000 P-21000 1949))

(define (strlist-to-str StrLst Sep)
   (cond
      [(empty? StrLst) ""]
      [(equal? (first StrLst) "")  (strlist-to-str (rest StrLst) Sep)]
      [(empty? (rest StrLst)) (first StrLst)]
      [else (string-append (first StrLst) Sep (strlist-to-str (rest StrLst) Sep))]
   )
)

(define (person-to-lfn ; string
   who                 ; person
   )
   (cond
     [(string? who)  who]
     [else  (string-append (person-last who) "," (person-first who))]
   )
)

(define (ancestors ; string
   who             ; person
   )
   (cond
     [(empty? (person-mother who))  ""]
     [else  
      (strlist-to-str (sort (list (person-to-lfn (person-mother who))
                                  (person-to-lfn (person-father who))
                                  (ancestors (person-mother who))
                                  (ancestors (person-father who))) string<?) " ")]
   )
)
(check-expect (ancestors P-01100) "Abdul,Alexander Abdul,Christopher Harper,Alexandra Hazel,Alexandra Sherman,Joshua Sherman,Lauren")

Проверьте ошибки: 

Actual value "Abdul,Alexander Abdul,Christopher Hazel,Alexandra Harper,Alexandra Sherman,Joshua Sherman,Lauren" differs from "Abdul,Alexander Abdul,Christopher Harper,Alexandra Hazel,Alexandra Sherman,Joshua Sherman,Lauren", the expected value.
at line 64, column 0 <code>

1 Ответ

2 голосов
/ 29 октября 2010

Проблема, как вы сказали, в том, что в рекурсивном случае ancestors возвращает одну строку, содержащую всех предков, которая затем не может быть отсортирована должным образом, потому что это одно, а не несколько вещей.

Вы должны изменить ancestors так, чтобы вместо возврата одной строки она возвращала список строк (то есть не вызывайте strlist-to-str в ней). Затем, когда он повторяется, вы получаете список предков матери и список предков отца; сложите эти списки вместе с отцом и матерью и сведите их в один список.

Только в качестве последнего шага, после завершения всей рекурсии, следует вызывать strlist-to-str, чтобы объединить окончательный список имен в одну строку.

...