(26) Cài đặt từ điển bởi bảng băm đóng – Hash table – Bùi Thế Tâm

Cài đặt từ điển bởi bảng băm đóng – Hash table – Cau truc du lieu va giai thuat – Kênh Bùi Thế Tâm | Thuật toán
Bui The Tam, Hanoi, Vietnam
Từ điển là mô hình dữ liệu tập hợp mà chỉ giữ lại 3 phép toán: chèn x vào tập hợp, xóa x khỏi tập hợp, tìm trong tập hợp có phần tử x hay không. Bảng băm đóng dùng để xử lý các tập hợp cỡ lớn.
Trong bảng băm đóng ta không chia tập hợp các phần tử thành các lớp mà chứa chúng trong một mảng cố định t(n), do đó n phải khá lớn và là một số nguyên tố. Chương trình BangBamDong.cpp minh hoạ cách làm việc với bảng băm đóng để cài đặt một từ điển gồm các xâu ký tự chứa họ tên của một người (gọi là giá trị khoá), độ dài xâu không quá 25 ký tự.
Dòng 4-6: cách cài đặt bảng băm đóng, khai báo n=7 để tiện theo dõi quá trình làm việc của bảng băm trên màn hình, khi bảng băm đóng cần lưu trữ nhiều phần tử ta phải tăng n lên (ví dụ số nguyên tố 6997 hay 1317493).
Lúc đầu ta gán cho tất cả các phần tử của bảng băm giá trị “Trống”. Nếu một phần tử t(i) đã được xếp tên và ta xoá tên này khỏi bảng băm thì gán cho t(i) giá trị “DaXoa” để đánh dấu
Giả sử h(x) là hàm băm, x là giá trị khoá. Để xếp x vào bảng băm ta tính i = h(x), nếu t(i) = “Trống” hay ” DaXoa” thì xếp x vào t(i). Nhưng nếu t(i) đang lưu giữ một khoá khác thì ta phải tiến hành băm lại bằng cách dùng các hàm băm lại h1(x), h2(x), h3(x), . . . Ta sẽ xét lần lượt các vị trí h1(x), h2(x), h3(x),. . . cho tới khi tìm được vị trí “Trống” hoặc ” DaXoa” để đặt x vào đó, nếu không tìm được vị trí như thế thì bảng đã đầy và ta không thể đưa x vào bảng được nữa.
Trường hợp đơn giản nhất là dùng các hàm băm lại tuyến tính: hi(x) = (h(x) + i) % n, tức là xem bảng là vòng tròn và lần lượt xem xét các vị trí h(x)+1, h(x)+2, h(x)+3, . . ., (h(x) + i) % n. Giá trị của các hàm băm lại chỉ phụ thuộc vào khoá x. Trong chương trình dùng hàm băm lại tuyến tính.
Trong chương trình cho một kiểu hàm băm h(x) với đối số là Xâu ký tự: tính s là tổng mã ASCII của tất cả các ký tự trong xâu, lấy phần dư của phép chia s cho n gán cho hàm.
Để thực hiện các phép toán chèn, loại bỏ và tìm kiếm một phần tử có khoá x trên bảng băm trước tiên ta cần thăm dò khoá x.
Hàm ThamDo(x, k, j) nhằm thăm dò khoá x tại vị trí t(i) với i = h(x), nếu t(i) = x hoặc t(i)= “Trống” thì k = j = i và dừng, nếu trái lại thì ta thăm dò tiếp các vị trí t[k] với k = h1(x), h2(x), h3(x), . . .
Quá trình thăm dò sẽ dừng lại khi xảy ra một trong ba trường hợp (xem lệnh ở dòng 19): t(k) = “Trống”, t(k) = x, k = i. Tham số k trong hàm ThamDo() lưu chỉ số của mảng t mà tại đó quá trình thăm dò dừng lại.
Tham số j trong hàm có nghĩa: j là chỉ số đầu tiên trong quá trình thăm dò mà tại đó t(j) = ” DaXoa ” hoặc “Trống”, nếu cần chèn khoá x thì sau này t(j) sẽ được gán bằng x.
Hàm Chen(x): chèn khoá x vào từ điển.
Hàm Xoa(x): xoá khoá x khỏi từ điển và điền vào vị trí này xâu “DaXoa”.
Hàm Tim(x) cho giá trị 1 nếu khoá x có trong từ điển và cho 0 nếu trái lại.
Hàm InTD(): in toàn bộ từ điển (mảng t).
HỌC TIN HỌC ONLINE MIỄN PHÍ
Dạy lập trình ngôn ngữ C – Cài đặt từ điển bởi bảng băm đóng – Hash table – Bùi Thế Tâm | Ngôn ngữ lập trình C
Bài giảng về lập trình C, pascal, tin học văn phòng, word, excel, powerpoint, thuật toán
Kênh Yotube chính thức của Bùi Thế Tâm.
Youtube:
Bùi Thế Tâm là kênh đào tạo về lĩnh vực công nghệ thông tin, Lập trình ngôn ngữ C, tin học văn phòng, các thuật toán toán tối ưu và lập trình trên C, hướng dẫn sử dụng Microsoft office 2007, 2010, 2013.
Mô hình dữ liệu tập hợp và từ điển:
Cài đặt từ điển bởi bảng băm mở – Hash table:
Cài đặt từ điển bởi bảng băm đóng:
Kênh Bùi Thế Tâm hướng dẫn sử dụng word, excel, powerpoint, lập trình ngôn ngữ C cho người mới bắt đầu, cho học sinh, sinh viên, sinh viên năm thứ nhất, sinh viên năm thứ hai, cho học sinh, giáo viên vùng sâu vùng xa, người cao tuổi muốn học tin học ở nhà, các bạn thi viên chức và người đi làm…
Với nhiều năm kinh nghiệm giảng dậy và viết sách nên các bài giảng trong kênh Bùi Thế Tâm rất dễ hiểu, đơn giản, chính xác và đầy đủ.
Trong bài giảng phần lý thuyết, bài tập xen kẽ nhau, với nhiều dạng bài tập từ dễ đến khó có hướng dẫn giải chi tiết cẩn thận giúp các bạn có thể nắm vững được kiến thức.
Facebook:
Twitter:
Blog:
Youtube:
Hãy like và chia sẻ cho bạn bè và những người bạn quen đang muốn học về Microsoft office, tin học văn phòng ( hay còn gọi là tin học cơ sở, tin học đại cương, tin học căn bản, tin học phổ thông, tin học cho người mới bắt đầu), ngôn ngữ lập trình C.
Mọi hình thức copy và sao chép đều vi phạm bản quyền của youtube nếu không được sự đồng ý của tác giả Bùi Thế Tâm
Đừng quên đăng ký kênh để học thêm các bài mới
Subscribe Youtube:

Nguồn: https://ephraimturner.com

Xem thêm bài viết khác: https://ephraimturner.com/cong-nghe/