深度优先搜索和广度优先搜索(非递归).
深度优先:
- 将openlist中的最后一项取出.
-
将其未标记的邻项标记为已访问.并放入openlist.
-
重复此步骤1.2.直到openlist为空.
例:
上图中图从P开始,openlist:
[p] [r,s,q] [r,s,t] [r,s,u] [r,s] [r] []
广度优先则是将openlist中的第一项取出.有:
[p] [r,s,q] [s,q,u] [q,u] [u,t] [t] []
Grabbing the last element means you are using a "stack". Grabbing the first means you are using a "queue". -MLL
深度优先使用的是栈.广度优先使用的是队列.
[scheme学习笔记]二叉树的遍历
(define BT1 (make-node 63 'a (make-node 29 'b (make-node 15 'c (make-node 10 'd false false) (make-node 24 'e false false)) false) (make-node 89 'f (make-node 77 'g false false) (make-node 95 'h false (make-node 99 'i false false))))) (define BT2 (make-node 63 'a (make-node 29 'b (make-node 15 'c (make-node 87 'd false false) (make-node 24 'e false false)) false) (make-node 89 'f (make-node 33 'g false false) (make-node 95 'h false (make-node 99 'i false false)))))
;;inorder:BT->list (define (inorder BT) (cond ((boolean? BT) empty) (else (append (inorder (node-left BT)) (list (node-ssn BT)) (inorder (node-right BT))))))
(define (preorder BT) (cond ((boolean? BT) empty) (else (append (list(node-ssn BT)) (preorder (node-left BT)) (preorder (node-right BT)))))) (define (postorder BT) (cond ((boolean? BT) empty) (else (append (postorder (node-left BT)) (postorder (node-right BT)) (list(node-ssn BT))))))
[scheme学习笔记]scheme中的快速排序和合并排序
;;filter:listX-listX (define (filter pred list) (cond ((empty? list) list) (else (cond ((pred (car list)) (cons (car list) (filter pred (cdr list)))) (else (pred (cdr list)))))))
(define (q-sort lst) (if (null? lst) lst (append (q-sort (filter (lambda (x) (<= x (car lst))) (cdr lst))) (list (car lst)) (q-sort (filter (lambda (x) (> x (car lst))) (cdr lst))))))
;;merge-sort:list->list (define (merge-sort x) (define (merge-sort-worker x) (if (= (length x) 1) (car x) (merge-sort-worker (merge-all-neighbors x)))) (merge-sort-worker (make-singles x))) ;;make-singles:alon-> lists of number (define (make-singles alon) (cond ((empty? alon) empty) (else (cons(cons (first alon) empty) (make-singles (rest alon)))))) ;;merge-all-neighbors:lists->list (define (merge-all-neighbors alist) (cond ((empty? alist) empty) ((empty? (rest alist)) empty) (else (cons (sort (append (first alist)(second alist))<)(merge-all-neighbors (rest (rest alist)))))))
另..
how to design programs中文版下载地址
ftp://ftp.cs.sjtu.edu.cn:990/huanglp/程序设计方法/如何设计程序.PDF
[scheme学习笔记]递归插入排序
对数表进行排序,排序函数读入一个表,产生另一个表
即
;; sort : list-of-numbers -> list-of-numbers ;; to create a sorted list of numbers from all the numbers in alon (define (sort alon) ...)
例子为:
(sort empty) ;; expected value: empty (sort (cons 1297.04 (cons 20000.00 (cons -505.25 empty)))) ;; expected value: (cons 20000.00 (cons 1297.04 (cons -505.25 empty)))
如果输入为empty.则输出empty
(define (sort alon) (cond ((empty? alon)empty) (else (...(first alon)...(sort (rest alon))))))
接着,需要处理的就是sort函数cond字句的第二部分.该部分包含两个表达式.先弄清楚他们结果分别是什么.
1.(first alon)输出数表的第一个数
;; insert : number list-of-numbers -> list-of-numbers ;; to create a list of numbers from n and the numbers on alon ;; that is sorted in descending order; alon is already sorted (define (insert n alon) ...))
如此.就可以给出sort的定义
(define (sort alon) (cond ((empty? alon) empty) (else (insert (first alon) (sort (rest alon))))))
现在.cond第二个字句的意义清晰了.要产生最终值.可先取出非空表的第一个数.再对其它部分进行排序.最后把前者插入到后者的合适部分.
(insert 5 empty) ;; expected value: (cons 5 empty)
如果insert的第二个参数是非空表,
(insert 1297.04 (cons 20000.00 (cons -505.25 empty))) ;; expected value: (cons 20000.00 (cons 1297.04 (cons -505.25 empty)))
可以给出函数的模板
(define (insert n alon) (cond ((empty? alon) ...) (else ... (first alon) ... (insert n (rest alon)) ...)))
首先给出的表达式的结果
;; sort : list-of-numbers -> list-of-numbers (sorted) ;; to create a list of numbers with the same numbers as ;; alon sorted in descending order (define (sort alon) (cond [(empty? alon) empty] [(cons? alon) (insert (first alon) (sort (rest alon)))])) ;; insert : number list-of-numbers (sorted) -> list-of-numbers (sorted) ;; to create a list of numbers from n and the numbers on ;; alon that is sorted in descending order; alon is sorted (define (insert n alon) (cond [(empty? alon) (cons n empty)] [else (cond [(>= n (first alon)) (cons n alon)] [(< n (first alon)) (cons (first alon) (insert n (rest alon)))])]))