intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Đỗ Ngọc Như Loan

Chia sẻ: Dien_vi10 Dien_vi10 | Ngày: | Loại File: PPTX | Số trang:18

41
lượt xem
1
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 5: Bảng băm (Hashtable)" trình bày các khái niệm về bảng băm, giải quyết đụng độ bằng kết nối, định nghĩa bảng băm, các thao tác, độ phức tạp,... Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Đỗ Ngọc Như Loan

  1. GV: Đỗ Ngọc Như Loan
  2. Khái niệm  Bảng băm là một cấu trúc dữ liệu có thể lưu  trữ một tập các đối tượng có số phần tử tùy ý  Các thao tác tìm kiếm, chèn, xoá trên bảng  băm rất hiệu quả  Phần tử có khoá k (nguyên) được lưu trữ  trong slot h(k), trong đó h là hàm băm (hash  function) từ tập U các khóa đến tập các slot  của bảng băm T[0..m­1]
  3. Khái niệm  Hàm băm có dạng h: U → {0,1,..., m­1}, m là  kích thước của bảng băm  h(k) là giá trị băm (hash value) của khoá k  hay còn nói phần tử có khoá k băm slot h(k)  Với hàm băm chỉ cần xử lý m giá trị thay vì | U| giá trị
  4. Bảng băm  Có thể có sự dụng độ (collision) lưu trữ các  khóa, ví dụ k2 dụng độ k5, nghĩa là h(k2)=  h(k5)  Các phương pháp giải quyết đụng độ § Thiết kế hàm băm h(U) phân bố đều trên T  (không triệt để) § Giải quyết dụng độ bằng danh sách liên kết  collision resolution by chaining) § Giải quyết dụng độ bằng địa chỉ mở (open  addressing)
  5. GiẢI QUYẾT ĐỤNG ĐỘ  BẰNG KẾT NỐI  Đặt tất cả các phần tử có cùng giá trị hàm  băm vào một danh sách liên kết  Slot j chứa pointer chỉ đến đầu của danh  sách liên kết của tất cả các phần tử được lưu  trữ có hàm băm là j  Nếu không có khóa k để h(k)=j thì thì slot j trỏ  đến NULL
  6. ĐỊNH NGHĨA BẢNG BĂM  Định nghĩa bảng băm trong C++, các khóa là  số nguyên typedef struct CELL *LIST; struct CELL { int key; LIST next; }; typedef LIST TABLE[MAX]; TABLE T;
  7. CÁC THAO TÁC  HashInitialize(T): Khởi tạo bảng băm  HashInsert(T, k): Chèn một phần tử có khóa k  vào bảng băm T  HashSearch(T, k): Tìm một phần tử có khoá k  trong T  HashDelete(T, k): Xoá một phần tử có khóa k  khỏi T
  8. HashInitialize void HashInitialize(TABLE &T,int &m) // m là kích thước {  // bảng băm for(int i=0; i
  9. HashInsert void HashInsert(TABLE &T, int m, int k) { ListInsert(T[Hash(k, m)], k); } int Hash(int k, int m) //hàm băm { return k%m; }
  10. HashSearch LIST HashSearch(TABLE T, int k, int m) { return ListSearch(T[Hash(k,m)], k); }
  11. HashDelete void HashDelete(TABLE & T, int m, int k) { ListDelete(T[Hash(k,m)], k); }
  12. ĐỘ PHỨC TẠP  HashInsert(T, k) có T(n) = O(1)  HashSearch(T, k) và HashDelete(T, k) có độ  phức tạp trung bình T(n) = O(n/m), trong đó m  là kích thước bảng băm
  13. HÀM BĂM  Một hàm băm là tốt nếu h(k) có thể là bất kỳ  slot nào trên bảng băm  Trong ứng dụng cần tìm các hàm băm thích  hợp  Luôn giả sử mỗi khoá là một số tự nhiên  Có một số cách xây dựng hàm băm như:  phương pháp chia (division method), phương  pháp nhân (multiplication method) v.v
  14. HÀM BĂM  Với phương pháp chia, tạo hàm băm bằng  cách đặt tương ứng mỗi khoá k với số dư  trong phép chia k cho số slot m  Vậy h(k) = k mod m  Tập các khoá được chia thành m lớp  Nên chọn m là số nguyên tố không quá gần  với lũy thừa của 2
  15. HÀM BĂM  Phương pháp nhân, hàm băm có dạng: § h(k) =                    ,A là hằng thỏa 0 
  16. Yêu cầu: Cho dãy số nguyên dương gồm n số  đôi một khác nhau và số k. Hãy kiểm tra xem  có giá trị k trong dãy không? Input: Dữ liệu vào từ file HASH.INP gồm 2  dòng: + Dòng 1: Gồm 2 số nguyên n và k (n
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2