Cấu trúc dữ liệu_chương 5

Ta biết rằng việc lập trình phụ thuộc phần lớn vào cách mô hình hóa dữ liệu của bài toán cần giải. Mối quan hệ giữa thuật toán và cấu trúc dữ liệu trong lập trình đã được Niclaus Wirth, tác giả ngôn ngữ lập trình Pascal, đưa ra một công thức rất nổi tiếng.
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu_chương 51CHƯƠNG V. CẤU TRÚC DỮ LIỆU a biết rằng việc lập trình phụ thuộc phần lớn vào cách mô hình hoá dữ liệu của bài toánT cần giải. Mối quan hệ giữa thuật toán và cấu trúc dữ liệu trong lập trình đã đượcNiclaus Wirth, tác giả ngôn ngữ lập trình Pascal, đưa ra một công thức rất nổi tiếng : Cấu trúc dữ liệu + Thuật toán = Chương trình (Data structure + Algorithms = Programs) Như đã thấy, thuật toán mới chỉ phản ánh các thao tác cần xử lý, còn đối tượng để xử lýtrong máy tính lại là dữ liệu. Nói đến thuật toán là nói đến thuật toán đó tác động lên dữ liệunào. Còn nói đến dữ liệu là nói đến dữ liệu ấy cần được tác động bởi thuật toán nào để đưađến kết quả mong muốn. Dữ liệu biểu diễn thông tin cần thiết để giải bài toán, gồm dữ liệuđưa vào, dữ liệu đưa ra và dữ liệu tính toán trung gian. Một cấu trúc dữ liệu liên quan đến bayếu tố : kiểu dữ liệu, các phép toán tác động lên dữ liệu và cách biểu diễn dữ liệu trong bộnhớ của máy tính tuỳ theo công cụ lập trình. Trong chương này, chúng ta sẽ trình bày một số cấu trúc dữ liệu tiêu biểu như tập hợp,ngăn xếp, danh sách móc nối, cây...V.1 Tập hợp Trong toán học, tập hợp (set) là một nhóm hay một bộ sưu tập các đối tượng1 phân biệt{x1, x2, …, xn}, được gọi là các phần tử (elements) của tập hợp. Do mỗi phần tử của một tậphợp chỉ được liệt kê một lần và không được sắp xếp thứ tự nên người ta không nói đến phầntử thứ nhất, phần tử thứ hai, v.v... Ví dụ hai tập hợp sau đây là đồng nhất : { a, b, d, a, d, e, c, d } = { a, b, c, d } Do tập hợp cũng là một danh sách, người ta có thể sử dụng cấu trúc danh sách để biểudiễn tập hợp trong Scheme. Như vậy, một tập hợp rỗng là một danh sách rỗng. Để so sánh haitập hợp có bằng nhau không, ta có thể sử dụng vị từ equal? như sau : (define (setequal? E1 E2) (cond ; hai tập hợp rỗng thì bằng nhau ((and (null? E1) (null? E2)) #t) ; hai tập hợp có hai phần tử đầu tiên bằng nhau1 Khái niệm đối tượng của tập hợp có tính trực giác, do nhà toán học người Đức G. Cantor đưa ra từ năm 1985. Đến năm 1902, nhà triết học người Anh B. Russell đã chỉ ra những nghịch lý toán học (paradox) hay những mâu thuẫn lôgic trong lý thuyết tập hợp. 147148 LẬP TRÌNH HÀM ((equal? (car E1) (car E2)) (setequal? (cdr E1) (cdr E2))) ; hai tập hợp có hai phần tử đầu tiên khác nhau thì khác nhau !!! (else #f))) (setequal? ’(1 3 4 5 6) ’(1 3 4 5 6)) --> #thoặc : (define E1 ’(a b c d e)) (define E2 E1) (setequal? E1 E2) --> #t Để ý rằng trong vị từ setequal? trên đây, ta chưa xử lý hai tập hợp có các phần tửgiống y nhau và có cùng số phần tử, nhưng không được sắp xếp thứ tự như nhau : (setequal? (1 5 4 3 6) (1 3 4 5 6)) --> #f Sau đây ta sẽ sử dụng thường xuyên hàm member để xử lý tập hợp. Hàm này kiểm tramột phần tử có thuộc một danh sách đã cho hay không : ; Trường hợp phần tử kiểm tra có kiểu đơn giản (member ’c ’(a b c d e)) --> ’(c d e) ; Trường hợp phần tử kiểm tra có kiểu phức hợp (member (list ’a) ’(b (a) c)) --> ’((a) c) Vị từ in? kiểm tra một phần tử có thuộc một tập hợp đã cho hay không ? (define (in? x E) (cond ((null? E) #f) ; danh sách rỗng ((member x E) #t) ; x là phần tử kiểu đơn giản (else (in? x (cdr E))))) ; x là phần tử kiểu phức hợp (in? ’c E1) --> #t Để xây dựng một tập hợp từ một danh sách, người ta phải loại bỏ các phần tử trùng lặp.Hàm list->set sau đây sử dụng hàm member lần lượt kiểm tra các phần tử của danhsách đã cho. Kết quả trả về chỉ giữ lại phần tử cuối cùng đối với những phần tử trùng nhau vàchưa sắp xếp lại các phần tử theo thứ tự (xem phương pháp sắp xếp nhanh ở cuối chương). (define (list->set L) (cond ((null? L) ’()) ((member (car L) (cdr L)) (list->set (cdr L))) (else (cons (car L) (list->set (cdr L))))) (list->set ’(a b d a d e c d)) --> ’(b a e c d) (define (union2 E1 E2) (cond ((null? E1) E2)CẤU TRÚC DỮ LIỆU 149 ((member (car E1) E2) (union2 (cdr E1) E2)) (else (cons (car E1) (union2 (cdr E1) E2)))))1. Phép hợp trên các tập hợp Giả sử cho hai tập hợp E1 và E2, ta cần tìm kết quả của phép hợp của hai tập hợp E1∪E2 làmột tập hợp như sau : (define (union2 E1 E2) (cond ; tập hợp thứ nhất là rỗng thì kết quả là tập hợp thứ hai ( ...