Tài Liệu Giáo Trình Cấu Trúc Dữ Liệu Và Giải Thuật_Chương 6: Bảng Băm

Tài liệu đại học Toggle navigation

• Miễn phí (current)
• Danh mục
  • Khoa học kỹ thuật
  • Công nghệ thông tin
  • Kinh tế, Tài chính, Kế toán
  • Văn hóa, Xã hội
  • Ngoại ngữ
  • Văn học, Báo chí
  • Kiến trúc, xây dựng
  • Sư phạm
  • Khoa học Tự nhiên
  • Luật
  • Y Dược, Công nghệ thực phẩm
  • Nông Lâm Thủy sản
  • Ôn thi Đại học, THPT
  • Đại cương
  • Tài liệu khác
  • Luận văn tổng hợp
  • Nông Lâm
  • Nông nghiệp
  • Luận văn luận án
  • Văn mẫu
• Luận văn tổng hợp

1. Home
2. Luận văn tổng hợp
3. Tài liệu Giáo trình cấu trúc dữ liệu và giải thuật_Chương 6: Bảng băm

Trich dan Tài liệu Giáo trình cấu trúc dữ liệu và giải thuật_Chương 6: Bảng băm - Pdf 97

Chương 7BẢNG BĂMCác tác vụ trên các cấu trúc như danh sách, cây nhị phân,…phần lớn được hiện thực bằng cách so sánh các nút của cấu trúc, do vậy thời gian truy xuất không nhanh và phụ thuộc vào kích thước của cấu trúc. Chương này chúng ta sẽ xét một cấu trúc mới là bảng băm (hash table), các tác vụ trên bảng băm hạn chế số lần so sánh với mong muốn thời gian truy xuất là tức thời có bậc O(1) và không phụ thuộc vào kích thước của bảng băm.Với mỗi bảng băm người ta xây dựng một phép băm (hash function) để chuyển đổi số học các khoá của nút thành các địa chỉ trên bảng băm. Bảng băm là cấu trúc dung hòa tốt giữa thời gian truy xuất và dung lượng bộ nhớ. Bảng băm được ứng dụng nhiều trong thực tế, rất thích hợp khi tổ chức dữ liệu có kích thước lớn và được lưu trữ ở bộ nhớ ngoài.1. MÔ TẢ BẢNG BĂM1.1 Mô tả dữ liệuBảng băm được mô tả bằng các thành phần sau:• Có tập khoá của các nút trên bảng băm gọi là tập K.• Có tập các địa chỉ của bảng băm được gọi là tập M.• Có hàm băm để ánh xạ một khoá trong tập K thành 1 địa chỉ trong tập M.Bảng băm được mô tả bằng hình vẽ như sau:1.2 Các tác vụ trên bảng bămBảng băm có thể có các tác vụ sau:• Tác vụ khởi động: Cấp phát bộ nhớ và khởi động các giá trị ban đầu cho bảng băm.• Tác vụ tìm kiếm: Đây là một trong những tác vụ thường được sử dụng nhất của bảng băm. Tác vụ này sẽ tìm kiếm các phần tử trong bảng băm dựa vào khoá của từng phần tử.• Tác vụ thêm một phần tử:Tác vụ này thêm một phần tử mới vào bảng băm.• Tác vụ xoá một phần tử: Tác vụ này được dùng để xoá một phần tử ra khỏi bảng băm.• Tác vụ duyệt bảng băm: Tác vụ này dùng để duyệt qua tất cả các phần tử trên bảng băm.Bảng băm là một cấu trúc dung hoà tốt giữa thời gian truy xuất và dung lượng bộ nhớ:• Nếu không có sự giới về bộ nhớ thì chúng ta có thể xây dựng bảng băm với mỗi khoá ứng với một địa chỉ với mong muốn thời gian truy xuất tức thời.• Nếu dung lượng của bộ nhớ có giới hạn thì tổ chức một số khoá có cùng địa chỉ. Lúc này thời gian truy xuất có bị giảm đi.Bảng băm được ứng dụng nhiều trong thực tế, rất thích hợp khi tổ chức dữ liệu có kích thước lớn và được lưu trữ ở bộ nhớ ngoài.2. BẢNG BĂM VỚI PHƯƠNG PHÁP KẾT NỖI TRỰC TIẾP2.1 Mô tảBảng băm được cài đặt bằng danh sách liên kết, các nút trên bảng băm được băm thành M danh sách liên kết (từ danh sách 0 đến danh sách M-1). Các nút bị xung đột tại địa chỉ i được nối kết trực tiếp với nhau qua danh sách liên kết i.Khi thêm một nút có khoá key vào bảng băm, hàm băm f(key) sẽ xác định địa chỉ i trong khoảng 0 đến M – 1 ứng với danh sách liên kết i mà nút này sẽ được thêm vào.Khi tìm kiếm một nút có khoá key trên bảng băm, hàm băm f(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M – 1 ứng với danh sách liên kết i có thể chứa nút, việc tìm kiếm nút trên bảng băm quy về bài toán tìm kiếm trên danh sách liên kết.Sau đây là minh hoạ cho bảng băm có tập khoá là tập số tự nhiên, tập địa chỉ có 10 địa chỉ và chọn hàm băm là f(key)=key % 10.2.2 Cài đặt2.2.1Khai báo cấu trúc bảng băm#define M 10struct nodes{int key; struct nodes *next;};typedef struct nodes *NODEPTR;NODEPTR bucket[M];2.2.2 Hàm bămint hashfunc(int key){q=NULL;for(p=bucket[b];p!=NULL && k>p->key;p=p->next)q=p;if(q==NULL){ push(b,k);}else{ insafter(q,k);} }//them mot node co khoa la k vao trong bang bamvoid insert(int k){int b;b=hashfunc(k);place(b,k);}2.2.5 Xoá một phần tửint delafter(NODEPTR p){NODEPTR q;int k;if(p==NULL||p->next==NULL){printf("\n Khong xoa node duoc"); return 0;}q=p->next;k=q->key;p->next=q->next;freenode(q); return k;}//Xoa mot phan tu co khoa k ra khoi bang bam};typedef struct nodes *NODEPTR;NODEPTR bucket[M];// khoi tao bang bamvoid initbucket(){int b;for(b=0;b<M;b++){bucket[b]=NULL;}}//cap nhat mot node moi cho bang bamNODEPTR getnode(){NODEPTR p;p=(NODEPTR)malloc(sizeof(struct nodes)); return p;}//xoa mot node trong bo nhovoid freenode(NODEPTR p){free(p);}//Kiem tra mot bucket co phai empty?int emptybucket(int b){if(bucket[b]==NULL)return TRUE;else return FALSE;}//kiem tra toan bo bang bam co null hay khongint empty(){int b; freenode(q);} bucket[b]=NULL;}//Xoa toan bo bang bamvoid clear(){int b;for(b=0;b<M;b++){ clearbucket(b);}}//Ham hash functionint hashfunc(int key){return (key % M);}//them mot node vao dau bucketvoid push(int b, int x){NODEPTR p;p=getnode();p->key=x;p->next=bucket[b]; bucket[b]=p;}//Xoa mot node o dau bucketint pop(int b){NODEPTR p;int k;if(emptybucket(b)){printf("Bucket %d bi rong, khong xoa duoc",b); return 0;}//them mot node co khoa la k vao trong bang bamvoid insert(int k){int b;b=hashfunc(k);place(b,k);}//Tac vu tim kiem mot khoa trong bang bamint search(int k){NODEPTR p;int b;b=hashfunc(k);p=bucket[b];while(k>p->key&&p!=NULL)p=p->next;if(p==NULL || k!=p->key)return -1;else return b;}//Xoa mot node ngay sau node pint delafter(NODEPTR p){NODEPTR q;int k;if(p==NULL||p->next==NULL){printf("\n Khong xoa node duoc"); return 0;}q=p->next;k=q->key;printf("\n 1: Them mot node vao bang");printf("\n 2: Them ngau nhien nhieu node vao bang bam");printf("\n 3: Xoa mot node trong bang bam");printf("\n 4: Xoa toan bo bang bam");printf("\n 5: Duyet bang bam");printf("\n 6: Tim kiem tren bang bam");printf("\n 0: ket thuc chuong trinh");printf("\n chuc nang ban chon: ");scanf("%d",&chucnang);switch(chucnang){case 1:{printf("\n Them mot node vao trong bang bam");printf("\n Nhap vao khoa cua node can them vao: ");scanf("%d",&key);insert(key); break;}case 2:{printf("\n them mot bang ngau nhien nhieu node vao bang");printf("\n So node ban muon them: ");scanf("%d",&n);for(i=0;i<n;i++){key=random(100); insert(key);} break;}case 3:{printf("\n Xoa mot node tren bang bam");Bảng băm trong trường hợp này được cài đặt bằng danh sách liên kết dùng mảng, có M nút. Các nút bị xung đột địa chỉ được nối kết với nhau qua một danh sách liên kết.Mỗi nút của bảng băm là một mẫu tin có hai trường:• Trường key: chứa khoá của nút.• Trường next: con trỏ chỉ nút kế tiếp nếu có xung đột.Khi khởi động bảng băm thì tất cả trường key được gán giá trị là NULLKEY, tất cả các trường next được gán là -1.Hình vẽ sau mô tả bảng băm ngay sau khi khởi động:Khi thêm một nút có khoá key vào bảng băm, hàm băm f(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M – 1.• Nếu chưa bị xung đột thì thêm nút mới tại địa chỉ i này.• Nếu bị xung đột thì nút mới được cấp phát là nút trống phía cuối mảng. Cập nhật liên kết next sao cho các nút bị xung đột hình thành một danh sách liên kết.Khi tìm một nút có khoá key trong bảng băm, hàm băm f(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M – 1, tìm nút khoá key trong danh sách liên kết xuất phát từ địa chỉ i.Minh hoạSau đây là minh hoạ cho bảng băm có tập khoá là số tự nhiên, tập địa chỉ có 10 địa chỉ (M=10), chọn hàm băm f(key)=key % 10. Hình vẽ sau đây minh hoạ cho tiến trình thêm các nút 10, 15, 26, 30, 25, 35 vào bảng băm.Hình (a): Sau khi thêm 3 nút 10, 15, 26 vào bảng băm – lúc này chưa bị xung đột.Hình (b): Thêm nút 30 vào bảng băm - bị xung đột tại địa chỉ 0 – nút 30 được cấp phát tại địa chỉ 9, trường next của nút tại địa chỉ 0 được gán là 9.Hình (c): Thêm nút 25 vào bảng băm - bị xung đột tại địa chỉ 5 – nút 25 được cấp phát tại địa chỉ 8, trường next của nút tại địa chỉ 5 được gán là 8.Hình (d): Thêm nút 35 vào bảng băm - bị xung đột tại địa chỉ 5 và địa chỉ 8 – nút 35 được cấp phát tại địa chỉ 7, trường next của nút tại địa chỉ 8 được gán là 7.3.2 Cài đặt3.2.1 Khai báo cấu trúc bảng băm#define M 10 struct node{printf("\n khoa %d bi trung, khong them vao duoc",k); return i;}i=hashfunc(k);while(hashtable[i].next>=0)i=hashtable[i].next;if(hashtable[i].key==NULLKEY)j=i;//khong co su dung do, first timeelse{j=getempty();if(j <0){printf("\n Bang bam bi day khong them vao duoc");return j;}else{ hashtable[i].next=j;}}hashtable[j].key=k;return j;}3.2.5 Tác vụ duyệt bảng bămvoid viewtable(){int i;for(i=0;i<M;i++){printf("\n table[%2d]: %4d %4d",i,hashtable[i].key,hashtable[i].next);}}3.3 Chương trình minh hoạ#include<stdio.h>#include<stdlib.h>} return TRUE;}//Xem chi tiet thong tin bang bamvoid viewtable(){int i;for(i=0;i<M;i++){printf("\n table[%2d]: %4d %4d",i,hashtable[i].key,hashtable[i].next);}}//tim mot khoa co trong bang bam hay khong, tim thay tra ve dia chi//khong thayy tra ve Mint search(int k){int i;i=hashfunc(k);while(k!=hashtable[i].key && i !=-1)i=hashtable[i].next;if(k==hashtable[i].key)return i;else return M;}//chon node con trong phia duoi bang hash de cap nhat khi xay ra xung dotint getempty(){while(hashtable[avail].key !=NULLKEY)avail ; return avail;}//them mot node co khoa k vao bang bamint insert(int k){printf("\n 2: Them ngau nhien nhieu node vao bang bam");printf("\n 3: Xoa toan bo bang bam");printf("\n 4: Xem chi tiet bang bam");printf("\n 5: Tim kiem tren bang bam");printf("\n 0: Ket thuc chuong trinh");printf("\n\n Chuc nang ban chon: ");scanf("%d",&chucnang);switch(chucnang){case 1:{printf("\n THEM MOT NODE MOI VAO BANG BAM");printf("\n Khoa cua node moi: ");scanf("%d",&key);insert(key); break;}case 2:{printf("\n THEM NGAU NHIEN NHIEU NODE VAO BANG BAM");printf("\n Ban muon them vao bao nhieu node: ");scanf("%d",&n);for(i=0;i<n;i++){key=random(1000); insert(key);}break;}case 3:{printf("\n XOA TOAN BO BANG BAM"); initialize(); break;1 sẽ xét địa chỉ kế tiếp, nếu lại bị xung đột thì hàm băm lại lần 2 f2 sẽ xét địa chỉ kế tiếp nữa… quá trình cứ thế cho đến khi nào tìm được địa chỉ trống và thêm nút vào địa chỉ này.Khi tìm một nút có khoá key trong bảng băm, hàm băm f(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M – 1, tìm nút khoá key trong khối đặc chứa các nút xuất phát từ địa chỉ i.Hàm băm lại của phương pháp dò tìm tuyến tính là truy xuất địa chỉ kế tiếp. Hàm băm lại được biểu diễn bằng công thức sau:f(key)=(f(key)+i)%MMinh hoạ:Sau đây là minh hoạ cho bảng băm có tập khoá là tập số tự nhiên, tập địa chỉ có 10 địa chỉ, chọn hàm băm f(key)=key %10.Hình vẽ sau miêu tả tiến trình thêm các nút 32, 53, 22, 92, 17, 34 vào bảng băm.Hình (a): Sau khi thêm 2 nút 32 và 53 vào bảng băm – lúc này chưa bị xung đột.Hình (b): Thêm nút 22 và 92 vào bảng băm - bị xung đột tại địa chỉ 2, nút 22 được cấp phát tại địa chỉ 4, nút 92 được cấp phát tại địa chỉ 5.Hình (c): thêm nút 17 và 34 vào bảng băm – nút 17 không bị xung đột cấp phát tại địa chỉ 7, nút 34 bị xung đột tại địa chỉ 4, được cấp tại địa chỉ 6.4.2 Cài đặt4.2.1 Mô tả cấu trúc#define M 10struct node{int key;};struct node hashtable[M];int N;4.2.2 Tác vụ khởi độngi++;if(i>=M) i=i-M;}hashtable[i].key=k;N++; return i;}void viewtable(){int i;for(i=0;i<M;i++){ printf("\n table[%2d]: %4d",i,hashtable[i].key);}}4.3 Chương trình minh hoạ #include <stdio.h>#include <stdlib.h>#include <conio.h>#define TRUE 1#define FALSE 0#define NULLKEY -1#define M 10struct node{int key;};struct node hashtable[M];int N;int hashfunc(int key){return (key %M);}if(hashtable[i].key==k)return i;else return M;}//them khoa k vao bang bamint insert(int k){int i,j;if(full()){printf("\n Bang bam bi day, khong them vao duoc"); return M;}i=hashfunc(k);while(hashtable[i].key !=NULLKEY){i++;if(i>=M) i=i-M;}hashtable[i].key=k;N++; return i;}void viewtable(){int i;for(i=0;i<M;i++){ printf("\n table[%2d]: %4d",i,hashtable[i].key);}}void main(){int i,n; break;}case 3:{ break;}case 4:{printf("\n XOA TOAN BO CAY TREN BANG BAM"); initialize();break;}case 5:{printf("\n THONG TIN CHI TIET TREN BANG BAM"); viewtable(); break;}case 6:{printf("\n TIM KIEM TREN BANG BAM");printf("\n khoa can tim: ");scanf("%d",key);if(search(key)==M)printf("\n Khong thay");else printf("\n Tim thay khoa trong bang bam tai dia chi: %d trong bang",search(key)); break;}}}while(chucnang!=0);}BÀI TẬP Tải File Word Nhờ tải bản gốc Tài liệu, ebook tham khảo khác

• Giáo trình Cấu trúc dữ liệu
• Giáo trình cấu trúc dữ liệu và giải thuật
• Giáo trình cấu trúc dữ liệu và giải thuật - Giới thiệu
• Giáo trình: Cấu trúc dữ liệu và giải thuật
• Tài liệu Giáo trình Cấu trúc dữ liệu & Giải Thuật
• Tài liệu Giáo trình cấu trúc dữ liệu và giải thuật_Chương 1: Tổng quan
• Tài liệu Giáo trình cấu trúc dữ liệu và giải thuật_Chương 2: Danh sách
• Tài liệu Giáo trình cấu trúc dữ liệu và giải thuật_Chương 3: Cấu trúc Stack & Queue
• Tài liệu Giáo trình cấu trúc dữ liệu và giải thuật_Chương 4: Cây nhị phân
• Tài liệu Giáo trình cấu trúc dữ liệu và giải thuật_Chương 5: Cây nhiều nhánh tìm kiếm doc
• Một số giải pháp nhằm mở rộng thị trường tiêu thụ sản phẩm của Công ty cổ phần Sứ Viglacera Thanh Trì.
• Thúc đẩy hoạt động xuất khẩu hàng dệt may sang thị trường Hoa Kì của Tập đoàn dệt may Việt Nam.
• Giải pháp nâng cao chất lượng tín dụng đối với các doanh nghiệp vừa và nhỏ tại Chi nhánh NHNo&PTNT Tỉnh Bắc Kạn
• Phân tích thống kê hiệu quả sản xuất kinh doanh công ty trách nhiệm hữu hạn thương mại Minh Tiến giai đoạn 2005 – 2010.
• Tăng cường vai trò của Kế hoạch kinh doanh tại Công ty Cổ phần chế tạo máy điện Việt Nam – Hunggari sau cổ phần hóa
• Quản trị bán hàng tại công ty cổ phần Nhân Luật Bắc Miền Trung - thực trạng và giải pháp hoàn thiện
• Hoàn thiện công tác đào tạo và phát triển nguồn nhân lực tại Công ty xây dựng Lũng Lô- Bộ Tư lệnh Công Binh
• Một số giải pháp nâng cao năng lực cạnh tranh của công ti thông tin di động VMS - MobiFone Việt Nam
• Nâng cao hiệu quả công tác Tuyển dụng tại Công ty Cổ phần Việt Nam IT
• Phân tích thống kê hiệu quả sản xuất kinh doanh của công ty cổ phần sữa Vinamilk Việt Nam giai đoạn 2005 đến 2009

Hệ thống tự động tổng hợp link tải tài liệu, ebook miễn phí cho các bạn sinh viên tham khảo.

Học thêm

• Nhờ tải tài liệu
• Từ điển Nhật Việt online
• Từ điển Hàn Việt online
• Văn mẫu tuyển chọn
• Tài liệu Cao học
• Tài liệu tham khảo
• Truyện Tiếng Anh

Music ♫

Copyright: Tài liệu đại học ©

Top