tailieunhanh - Giáo trình Cấu trúc dữ liệu và Thuật giải 2: Phần 2 - Ng.Thị Thanh Bình, Ng.Văn Phúc

Phần 1 của "Giáo trình Cấu trúc dữ liệu và Thuật giải 2" gồm nội dung chương 3 và 4 của giáo trình. Nội dung trình bày cấu trúc dữ liệu bảng băm, các hàm băm, cách tổ dữ liệu trên bảng băm nhằm phục vụ cho bài toán tìm kiếm được hiệu quả, giới thiệu về một số phương pháp thiết kế giải thuật cơ bản giúp sinh viên bước đầu làm quen với một số phương pháp thiết kế giải thuật. | Chương III Bảng Băm Mục tiêu Trong chương này chúng ta sẽ nghiên cứu bảng băm. Bảng băm là cấu trúc dữ liệu được sử dụng để cài đặt KDL từ điển. Nhớ lại rằng KDL từ điển là một tập các đối tượng dữ liệu được xem xét đến chỉ với ba phép toán tìm kiếm xen vào và loại bỏ. Đương nhiên là chúng ta có thể cài đặt từ điển bởi danh sách hoặc bởi cây tìm kiếm nhị phân. Tuy nhiên bảng băm là một trong các phương tiện hiệu quả nhất để cài đặt từ điển. Kiến thức cơ bản cần thiết Để học tốt chương này sinh viên cần phải nắm vững kỹ năng lập trình cơ bản như - Cấu trúc mảng danh sách - Các cấu trúc điều khiển lệnh vòng lặp. - Lập trình hàm thủ tục cách gọi hàm. Nội dung Trong chương này chúng ta sẽ đề cập tới các vấn đề sau đây - Phương pháp băm và hàm băm. - Các chiến lược giải quyết sự va chạm. - Cài đặt KDL từ điển bởi bảng băm. I. Phương pháp băm Vấn đề được đặt ra là chúng ta có một tập dữ liệu chúng ta cần đưa ra một cấu trục dữ liệu CTDL cài đặt tập dữ liệu này sao cho các phép toán tìm kiếm xen loại được thực hiện hiệu quả. Trong các chương trước chúng ta đã trình bày các phương pháp cài đặt KDL tập động từ điển là trường hợp riêng của tập động khi mà chúng ta chỉ quan tâm tới ba phép toán tìm kiếm xen loại . Sau đây chúng ta trình bày một kỹ thuật mới để lưu giữ một tập dữ liệu đó là phương pháp băm. Nếu như các giá trị khoá của các dữ liệu là số nguyên không âm và nằm trong khoảng chúng ta có thể sử dụng một mảng data có cỡ SIZE để lưu tập dữ liệu đó. Dữ liệu có khoá là k sẽ được lưu trong thành phần data k của mảng. Bởi vì mảng cho phép ta truy cập trực tiếp tới từng thành phần của mảng theo chỉ số do đó các phép toán tìm kiếm xen loại được thực hiện trong thời gian O 1 . Song đáng tiếc là khoá có thể không phải là số nguyên thông thường khoá còn có thể là số thực là ký tự hoặc xâu ký tự. Ngay cả khoá là số nguyên thì các giá trị khoá nói chung không chạy trong khoảng . Trong trường hợp tổng quát khi khoá không phải là các số nguyên trong khoảng .