Trong các ví dụ trước, chúng ta xây dựng nên các mô hình cho hai loại dữ liệu phức hợp: phân số và các biểu thức đại số. Trong đó các ví dụ chúng ta đã chọn đơn giản các biểu thức tối đa ở các lần khởi tạo hoặc truy xuất, nhưng hơn nữa việc chọn trình bày các cấu trúc này trong các điều khoản của các list là một lợi thế lớn. Khi chúng ta biến đổi trong sự trình bày các set, lựa chọn trình bày không rõ ràng. Thật sự, có nhiều cách để trình bày và chúng khác biệt đáng kể so với một cách khác.
Thật ra, một set đơn giản là một sự tập hợp của các object khác nhau. Chúng ta định nghĩa “set” và các toán tử được sử dụng trên set. Chúng là union-set, intersection-set, element-ofset?, và adjoin-set. element-of-set? dự đoán liệu rằng một phần tử có trong set hay không. adjoin-set với đối số là object và một set , trả về một set mới khi đã thêm object vào set. … Từ quan điểm của data abstraction, chúng ta tự do để thiết kế bất kỳ sự trình bày data nào mà nó thực thi các hoạt đoạn tính toán này trong một cách nhất quán với trình biên dịch đã cho ở trên.
Các set như là các list chưa được sắp xếp
Một cách để trình bày một set như là một list các thành phần trong nó không có phần tử nào xuất hiện hơn một lần. Set trống trình bày list trống. Trong việc biễu diễn nay, element-of-set? tương tự như procedure memq. Nó sử dụng equal? thay vì eq? vì vậy các thành phần của set không cần phải là các symbols.
(define (element-of-set? x set)
(cond ((null? set) false)
((equal? x (car set)) true)
(else (element-of-set? x (cdr set)))))Sử dụng lại procedure để viết procedure adjoin-set. Nếu object đã có trong set ta chỉ cần trả về set ban đầu, ngược lại chúng ta sử dụng cons để thêm object vào list trình bày set.
(define (adjoin-set x set)
(if (element-of-set? x set)
set
(cons x set)))
Với procedure intersection-set chúng ta sử dụng chiến lược đệ quy. Nếu car set1 có trong set 2 thì sử dụng cons để tạo ra list mới của car set1 và đệ quy của cdr set1 và set 2.
(define (intersection-set set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((element-of-set? (car set1) set2)
(cons (car set1) (intersection-set (cdr set1) set2)))
(else (intersection-set (cdr set1) set2))))Xem xét, số bước để thực hiện các hoạt động của set. Tất cả chúng sử dụng element-of-set?, tốc độ của procedure này ảnh hưởng chính đến toàn bộ việc thực thi của set. Bây giờ, để kiểm tra liệu rằng một object có là member trong set , element-of-set? phải duyệt toàn bộ set(trong trường hợp element k có trong set). Vì thê, nếu set có n phần tử , element-of-set? tiêu tốn n bước. Số lượng bước yêu cầu là Θ(n). Số lượng bước yêu cầu để thực hiện adjoin-set cũng tăng lên tuyến tính Θ(n). Với intersection-set, số lượng bước yêu cầu tăng tuyến tính với kích thước của hai set, nếu hai set đều có kích thước là n thì nó là Θ(n^2) . Điều này cũng đúng với procedure union-set.
Bài tập: Hãy thực thi procedure union-set.
