tailieunhanh - Giáo trình cấu trúc dữ liệu part 8

Tham khảo tài liệu 'giáo trình cấu trúc dữ liệu part 8', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Cấu trúc dữ liệu Chương IV Tập hợp Để xoá một phần tử nào đó ta phải tiến hành tìm kiếm nó trong danh sách. Vì danh sách không có thứ tự nên ta có thay thế phần tử bị xoá bằng phần tử cuối cùng trong danh sách để khỏi phải dời các phần tử nằm sau phần tử bị xoá lên một vị trí. void DeleteSET ElementType X SET L if EmptySET L printf Tap hop rong else Position Q 1 while Q L .Last L .Data Q X Q if L .Data Q X for int i Q i L .Last i L .Data i L .Data i 1 L .Last-- Cài đặt tự điển bằng mảng đòi hỏi tốn n phép so sánh để xác định xem một phần tử có thuộc từ điển n phần tử hay không thông qua hàm Member. Trên từ điển việc tìm kiếm một phần tử được xác định bằng hàm Member sẽ thường xuyên được sử dụng. Do đó nếu hàm Member thực hiện không hiệu quả sẽ làm giảm đi ý nghĩa của từ điển vì nói đến từ điển là phải tìm kiếm nhanh chóng . Mặt khác hàm Member còn được gọi từ trong thủ tục InsertSet và nó cũng dẫn đến là thủ tục này cũng không hiệu quả. Kỹ thuật băm cho phép chúng ta khắc phục nhược điểm trên. 2. Cài đặt từ điển bằng bảng băm . Cài đặt từ điển bằng bảng băm mở Định nghĩa bảng băm mở Trang 113 Cấu trúc dữ liệu Chương IV Tập hợp Băm mở là một mảng một chiều có B phần tử có chỉ số từ 0 đến B-1. Mỗi phần tử là một con trỏ trỏ tới một danh sách liên kết mà dữ liệu sẽ của từ điển sẽ được lưu trong các danh sách liên kết này. Mỗi danh sách được gọi là một Bucket một danh sách có chứa các phần tử có cùng giá trị hàm băm . Hàm băm Hàm băm là một ánh xạ từ tập dữ liệu A đến các số nguyên h A------ Theo đó giả sử x e A thì h x là một số nguyên 0 h x B-1. Có nhiều cách để xây dựng hàm băm cách đơn giản nhất là nguyên hóa x và sau đó lấy h x x B. Ví dụ Cho tập hợp A 1 5 7 2 4 15 Bảng băm là mảng gồm 5 phần tử và hàm băm h x x 5 Ta có bảng băm lưu trữ A như sau Hàm băm có thể được thiết kế như sau Ham bam H X X Mod B int H ElementType X return X B Sử dụng bảng băm mở để cài đặt từ điển Trang 114 Cấu trúc dữ liệu Chương IV Tập hợp Dưới đây là các thủ tục cài đặt từ