《How to Design Programs 》第16章的挑战题【drracket吧】

(define-struct file (name size content))
file（文件）是结构体：
(make-file n s x)
其中n是符号，s是数，而x是某个Scheme值。
list-of-files（文件表）是下列二者之一
1． empty，
2． (cons s lof)，其中s是file，而lof是文件表。
(define-struct dir (name dirs files))
dir（目录）是结构体：
(make-dir n ds fs)
其中n是符号，ds是目录的表，fs是文件的表。
list-of-directories（目录表）是下列二者之一
1． empty；
2． (cons s lod)，其中s是dir，lod是目录表。

习题16.3.4 开发函数find?，该函数读入一个dir和一个文件名，判断在该目录树中有没有某个文件的名字为这个文件名。

挑战：开发函数find。这个函数读入目录d和文件名f。如果(find? d f)为真，该函数返回一条到达该文件的路径；否则，它返回false。路径是目录名的表，表中的第一个目录是给定的目录；最后一个目录是files
表包含f的子目录。例如：
(find TS 'part3)
;; 期望值：
(list 'TS 'Text)
(find TS 'read!)
;; 期望值：
(list 'TS)
假设TS被define定义为图16.1中的目录。
在图16.1中，find 应该找到哪个read!文件？一般化这个函数，使得它返回一个路径的表，如果给定的文件名出现了多次的话。每一条路径应该到达不同的文件，而且每一个文件都应该出。

@zzd3zzd

;htdp第16章练习
#| directory结构体
(make-dir n ds fs); n--sym,ds--lod,fs--lof
lod--1.empty;2.(cons dir lod)
lof--1.empty;2.(cons file lof)
|#
(define-struct dir (name dirs files))
#| file结构体
(make-file n s x);n--sym,s--number,x--value of scheme
|#
(define-struct file (name size content))

;;;建立图16.1的目录
(define dir161
(make-dir 'TS
;'TS-d-'Text,'Libs
(cons (make-dir 'Text
;'Text-d-empty
empty
;'Text-f-'part1,'part2,'part3
(cons (make-file 'part1 2 99)
(cons (make-file 'part2 2 52)
(cons (make-file 'part3 2 17)
empty))))
(make-dir 'Libs
;'Libs-d-'Code,'Docs
(cons (make-dir 'Code
;'Code-d-empty
empty
;'Code-f-'hang,'draw
(cons (make-file 'hang 1 8)
(cons (make-file 'draw 1 2)
empty)))
(make-dir 'Docs
;'Docs-d-empty
empty
;'Docs-f-'read!
(cons (make-file 'read! 2 19)
empty)))
;'Libs-f-empty
empty))
;'TS-f-'read!
(cons (make-file 'read! 2 10)
empty)))
;-------------------------
;(define-struct dir (name dirs files))
;(define-struct file (name size content))
(define (display-dir dir)
(define (dd-h dir)
(cond ((null? dir) '())
((dir? dir)
(list (list 'd (dir-name dir))
(dd-h (dir-dirs dir))
(dd-h (dir-files dir))))
((file? dir)
(list 'f (file-name dir) (file-size dir) (file-content dir)))
((pair? dir)
(list (dd-h (car dir))
(dd-h (cdr dir))))
(else
(error "Error!! Directory!!!" dir))))
(dd-h dir))
(display-dir dir161)

;格式整理后的结果
'((d TS)
(((d Text)
()
((f part1 2 99) ((f part2 2 52) ((f part3 2 17) ()))))
((d Libs)
(((d Code)
()
((f hang 1 8) ((f draw 1 2) ())))
((d Docs)
()
((f read! 2 19) ())))
()))
((f read! 2 10) ()))

;;挑战题 find函数
;;都能遍历了，还不会搜索??
(define (find dir name)
(define stop-flag #f)
(define find-result "\nNo The File!!")
(define (f-h dir rr)
(cond ((or (null? dir) stop-flag) '())
((dir? dir)
;这里两句语句的先后，关系到是广度优先搜索还是深度优先搜索
;对于例子里的测试 (find 'read!)
;现在结果是'((read!) TS)
;如果改变先后，结果是'((read!) TS Libs Docs)
(f-h (dir-files dir) (cons (dir-name dir) rr))
(f-h (dir-dirs dir) (cons (dir-name dir) rr)))
((file? dir)
(cond ((eq? (file-name dir) name)
(set! stop-flag #t)
(set! find-result
(reverse rr)))))
((pair? dir)
(f-h (car dir) rr)
(f-h (cdr dir) rr))
(else
(error "Error!! Directory!!" dir))))
(f-h dir '())
(cons (list name) find-result))
(find dir161 'part3)
(find dir161 'read!)
;;找到一个文件就停止
#|
'((part3) TS Text)
'((read!) TS)
|#

;搜索所有符合条件的目录
(define (find-all dir name)
(define find-result '())
(define (f-h dir rr)
(cond ((null? dir) '())
((dir? dir)
;这里两句语句的先后,关系到是广度优先搜索还是深度优先搜索
(f-h (dir-files dir) (cons (dir-name dir) rr))
(f-h (dir-dirs dir) (cons (dir-name dir) rr)))
((file? dir)
(cond ((eq? (file-name dir) name)
(set! find-result
(cons (reverse rr) find-result)))))
((pair? dir)
(f-h (car dir) rr)
(f-h (cdr dir) rr))
(else
(error "Error!! Directory!!" dir))))
(f-h dir '())
(if (null? find-result)
"\nNo The File in Dir!!"
(cons (list name) find-result)))
(find-all dir161 'part3)
(find-all dir161 'read!)
#|
'((part3) (TS Text))
'((read!) (TS Libs Docs) (TS))
|#

源代码复制到编辑器中
按 ctrl + I 全文调整缩进就能看清程序结构了。
程序只对范例进行了粗略测试。
----------------------------------
另外目录是手工建立的。
继续，挑战题：
1.设计加入删除等，目录文件操作函数~~~~
2.自行设计几种文件目录组织形式，并提供完整的文件操作函数。
3.预留目录结构操作接口，并与各系统实际目录操作函数连接，实现真实的目录操作。

日	一	二	三	四	五	六

《How to Design Programs 》第16章的挑战题

扫二维码下载贴吧客户端