Bảng băm (HashTable) thực hiện trên C

[neverland87]

Mới vào học được 1 buổi về bảng băm, thầy giáo đã nắn gân cả lớp bằng mấy bài tập về bảng băm:

Bài 01:
Viết chương trình minh hoạ bảng băm dùng phương pháp nối kết trong các trường hợp
• Dữ liệu lưu trữ là số nguyên (Khoá tìm kiếm là số nguyên)
• Dữ liệu lưu trữ là hồ sơ học sinh (Khoá tìm kiếm là tên lớp)

Bài 02:
Viết chương trình Từ điển sử dụng cấu trúc bảng băm với các chức năng sau
• Thêm một từ mới
• Tra từ
• Cập nhật từ (sửa đổi nội dung)
• Xoá từ

Bài 03:
Viết chương trình minh hoạ bảng băm dùng phương pháp dò tuyến tính trong các trường hợp
• Dữ liệu lưu trữ là số nguyên (Khoá tìm kiếm là số nguyên)
• Dữ liệu lưu trữ là hồ sơ học sinh (Khoá tìm kiếm là tên lớp)

Bài 04:
Viết chương trình minh hoạ bảng băm dùng phương pháp dò bậc hai trong các trường hợp
• Dữ liệu lưu trữ là số nguyên (Khoá tìm kiếm là số nguyên)
• Dữ liệu lưu trữ là hồ sơ học sinh (Khoá tìm kiếm là tên lớp)


tại mới học 1 buổi nên mình chưa hiểu sâu lắm, mọi người giúp mình nhé.

[Xcross87]

Mấy bài trên hay đó. Rất cơ bản trong Data Structure & Algorithms.
Pete thấy Danh là người đầu tiên post vấn đề về HashTable lên forum. Tại sao Danh không post những kiến thức mà Danh biết về HashTable lên forum nhỉ ? Để những ai chưa biết thì có cơ hội biết và thực hành sau khỏi bỡ ngỡ, còn ai biết rồi thì giúp anh em chưa biết ..
Còn bài 2 thì dùng stack hay hơn chứ nhỉ ? .. Lấy dữ liệu in so sánh với database rồi cứ thế mà push hoặc pop hoặc đưa ra info tương ứng.
Mọi người vào đóng góp ý kiến nha ^.^!
Thêm nữa có nhiều loại HashTable. Nhưng không biết 4 bài trên Danh dùng loại hash table nào ?

[neverland87]

Mấy bài trên hay đó. Rất cơ bản trong Data Structure & Algorithms.
Pete thấy Danh là người đầu tiên post vấn đề về HashTable lên forum. Tại sao Danh không post những kiến thức mà Danh biết về HashTable lên forum nhỉ ? Để những ai chưa biết thì có cơ hội biết và thực hành sau khỏi bỡ ngỡ, còn ai biết rồi thì giúp anh em chưa biết ..
Còn bài 2 thì dùng stack hay hơn chứ nhỉ ? .. Lấy dữ liệu in so sánh với database rồi cứ thế mà push hoặc pop hoặc đưa ra info tương ứng.
Mọi người vào đóng góp ý kiến nha ^.^!
Thêm nữa có nhiều loại HashTable. Nhưng không biết 4 bài trên Danh dùng loại hash table nào ?

Hi, thật ra neverland cũng tính làm nhiều cái tutorial lắm, có điều mình không biết chèn hình vào bài viết như thế nào nữa, hay là thế này nhé, neverland sẽ soạn bài tutorial ra WORD, sau đó copy nhờ pete post dùm, nếu pete đồng ý thì neverland sẽ về nhà soạn, hix, dạo này vào học rồi, toàn thức đêm để viết bài không á.
Còn nói về câu 2: theo neverland là không nên,và không thể sử dụng stack, mà stack thì theo quy luật vào sau-ra trước. Nếu vì dò từ mà phải lấy từ đó ra khỏi database thì không thực tế lắm, với lại các từ trong từ điển được xếp theo ký tự alphabet, ví dụ neverland muốn lấy từ "array" trong mục từ "a" thì sao? hi,khó nhỉ
Nói về stack thì nói nôm na trên đây không hình dung được đâu, cần có hình, neverland vẽ ra cái ví dụ này, nhập các kí tự từ 'A'..'Z' và 'a'.,,'z' :
Đầu tiên ta dùng 1 hàm băm để chuyển đổi các kí tự thành địa chỉ trong bảng băm:
int HamBam(int K) // K là khóa, từ 'A' chẳng hạn
{
return K%65;
}
chẳng hạn ta nhập kí tự A, hàm này sẽ trả về địa chỉ 0; tương tự nhập B sẽ trả về địa chỉ 1 trong bảng băm. Ta có hình sau:
Đ/c 1 ----> a
Đ/c 2 -----> b
.....
Như thế, muốn tìm 1 khóa, ta chỉ cần dùng hàm băm xác định địa chỉ của khóa đó, sau đó trỏ cái vèo đến địa chỉ của khóa đó (khỏi mất công như thằng tìm kiếm tuyến tính và tìm kiếm nhị phân).
Ở trên chỉ là bảng băm mở, tốc độ tìm kiếm luôn là 1 hằng số, tuy nhiên nó sẽ không mạnh bằng hàm băm đóng (được ứng dụng làm từ điển ở câu 2).

He,chiều nay neverland sẽ được học thêm phương pháp dò tuyến tính và phương pháp dò nhị phân, sẽ ráng giải quyết sớm 4 bài trên để nếu rảnh sẽ lên trao đổi với anh em về vấn đề này.

Thêm nữa có nhiều loại HashTable. Nhưng không biết 4 bài trên Danh dùng loại hash table nào ?

Loại HashTale (HT) thì đề bài đã nói rõ rồi đó:
Bài 1: HT được cài đặt bẳng phương pháp nối kết (danh sách liên kết đơn).
- Dữ liệu lưu trữ là số nguyên (không có gì phải bàn rồi pete nhỉ)
- Dữ liệu lưu trữ là kiểu cấu trúc HocSinh (gồm các field: MaHS, TenHS,Lop,.. chẳng hạn), và khóa để tìm kiếm dựa trên field Lop.
Bài 3: HT được cài đặt bằng phương pháp dò tuyến tính (phương pháp này để tránh sự đụng độ địa chỉ)
Bài 4:HT được cài đặt bằng phương pháp dò bậc hai (cái này chưa được học nên chưa biết)

[neverland87]

Hi, mình làm được 1 nửa của bài 3 rồi,phù, cũng hổng khó lắm, nay post code lên cho anh em tham khảo, nếu ai không hiểu thì post lên nhé,anh em mình cùng tham khảo. Nào, let's go, code đây:
CHƯƠNG TRÌNH MINH HỌA BẢNG BĂM DÙNG PHƯƠNG PHÁP DÒ TUYẾN TÍNH, GIÁ TRỊ LƯU TRỮ LÀ SỐ NGUYÊN

#include<stdio.h>#include<conio.h>#define M 11  // khai bao kich thuoc bang bam#define NULLKEY -365  // khai bao nut rong co gia tri la -365#define TRUE 1#define FALSE 0int BangBam[M];  // tao bang bam voi kich thuoc Mint SoNut; // so nut cua bang bamint HamBam(int k) {    return k%M;}void KhoiTaoBangBam(){    for(int i=0;i<M;i++)        BangBam[i]=NULLKEY;}int Full()  // kiem tra xem bang bam da day hay chua?{    if (SoNut==M-1) return TRUE;    else return FALSE;}int Search(int k)  // tim kiem khoa K co o trong bang bam hay khong?{    int i=HamBam(k);    while (BangBam[i]!=k && BangBam[i]!=NULLKEY)    {        i++;        if (i>=M) i=i-M;    }    if (BangBam[i]==k) return i;    else return M;}int ThemPhanTu(int k) // them khoa k vao bang bam{    int i,j;    if (Full())    {        printf("\nBang bam da day");        return 0;    }    i=HamBam(k);    while (BangBam[i]!=NULLKEY)    {        i++;        if (i>=M) i=i-M;    }    BangBam[i]=k;    SoNut++;    return i;}void InBangBam()  {    printf("\nBANG BAM CUA BAN:\n");    printf("\n\t\tVi tri\t\t\tKhoa\n");    for(int i=0;i<M;i++)        if (BangBam[i]!=NULLKEY)            printf("\n\t\t%d\t\t\t%d",i,BangBam[i]);        else            printf("\n\t\t%d\t\t\tNULL",i);} void main(){    clrscr();    int khoa_nhap,khoa_tim;    KhoiTaoBangBam();    printf("\tCHUONG TRINH MINH HOA BANG BAM DUNG PHUONG PHAP TIM TUYEN TINH");    for(int i=0;i<M-1;i++)    {        printf("\nNhap phan tu thu %d:",i+1);        scanf("%d",&khoa_nhap);        ThemPhanTu(khoa_nhap);    }    InBangBam();    printf("\n\nNhap vao khoa ban can tim:");    scanf("%d",&khoa_tim);    int result=Search(khoa_tim);    if (result==M) printf("Khong tim thay %d trong bang bam",khoa_tim);    else printf("\nTim thay roi! %d nam o vi tri thu %d trong bang bam",khoa_tim,result);    getch();}

Mà sao dạo này ít thấy DR va huynguyen quá nhỉ,có 2 người đó giúp thì có thể làm đựơc bài 2 rồi.

[khanhlo89]

các anh em ơi giúp em với có ai biết làm bảng băm với dữ liệu là sinh viên không em đang làm đề tài về nó nè huhuhu.có thì post lên cho em với nha

[tien_cao299]

Hi, mình làm được 1 nửa của bài 3 rồi,phù, cũng hổng khó lắm, nay post code lên cho anh em tham khảo, nếu ai không hiểu thì post lên nhé,anh em mình cùng tham khảo. Nào, let's go, code đây:
CHƯƠNG TRÌNH MINH HỌA BẢNG BĂM DÙNG PHƯƠNG PHÁP DÒ TUYẾN TÍNH, GIÁ TRỊ LƯU TRỮ LÀ SỐ NGUYÊN

#include<stdio.h>#include<conio.h>#define M 11  // khai bao kich thuoc bang bam#define NULLKEY -365  // khai bao nut rong co gia tri la -365#define TRUE 1#define FALSE 0int BangBam[M];  // tao bang bam voi kich thuoc Mint SoNut; // so nut cua bang bamint HamBam(int k) {    return k%M;}void KhoiTaoBangBam(){    for(int i=0;i<M;i++)        BangBam[i]=NULLKEY;}int Full()  // kiem tra xem bang bam da day hay chua?{    if (SoNut==M-1) return TRUE;    else return FALSE;}int Search(int k)  // tim kiem khoa K co o trong bang bam hay khong?{    int i=HamBam(k);    while (BangBam[i]!=k && BangBam[i]!=NULLKEY)    {        i++;        if (i>=M) i=i-M;    }    if (BangBam[i]==k) return i;    else return M;}int ThemPhanTu(int k) // them khoa k vao bang bam{    int i,j;    if (Full())    {        printf("\nBang bam da day");        return 0;    }    i=HamBam(k);    while (BangBam[i]!=NULLKEY)    {        i++;        if (i>=M) i=i-M;    }    BangBam[i]=k;    SoNut++;    return i;}void InBangBam()  {    printf("\nBANG BAM CUA BAN:\n");    printf("\n\t\tVi tri\t\t\tKhoa\n");    for(int i=0;i<M;i++)        if (BangBam[i]!=NULLKEY)            printf("\n\t\t%d\t\t\t%d",i,BangBam[i]);        else            printf("\n\t\t%d\t\t\tNULL",i);} void main(){    clrscr();    int khoa_nhap,khoa_tim;    KhoiTaoBangBam();    printf("\tCHUONG TRINH MINH HOA BANG BAM DUNG PHUONG PHAP TIM TUYEN TINH");    for(int i=0;i<M-1;i++)    {        printf("\nNhap phan tu thu %d:",i+1);        scanf("%d",&khoa_nhap);        ThemPhanTu(khoa_nhap);    }    InBangBam();    printf("\n\nNhap vao khoa ban can tim:");    scanf("%d",&khoa_tim);    int result=Search(khoa_tim);    if (result==M) printf("Khong tim thay %d trong bang bam",khoa_tim);    else printf("\nTim thay roi! %d nam o vi tri thu %d trong bang bam",khoa_tim,result);    getch();}

Mà sao dạo này ít thấy DR va huynguyen quá nhỉ,có 2 người đó giúp thì có thể làm đựơc bài 2 rồi.

Bạn còn giữ code bài 3 ý thứ 2 ko? Bạn có thể share code lên cho mình với được ko? mình cũng đang gặp vấn đề với loại bài nay! cảm ơn bạn!

[ayy1986]

Bài 2 giải thế nào? Có thể post lên cho mình và mọi người xem không?
Nếu được, viết bằng code PHP càng tốt. Mình đang tính làm cái từ điển.

ayy1986!

[dacklayer]

Mình kô thấy nút thank đâu. Cám ơn bạn neverland87 về bài 3. Mình đã làm xong bài thực tập Hàm Băm rồi rồi
Mình cũng có đọc nhiều tài liệu nên hơi thắc mắc 1 chút:
#define NULLKEY -365 : nút rỗng này khai báo giá trị bao nhiêu cũng đc phải kô?
Trước khi tham khảo bài của bạn thì mình cũng có tham khảo 1 số ví dụ khác, họ khai báo bảng băm theo cấu trúc struct. Nhưng đến lúc mình in bảng băm thì bị lỗi. Khai báo theo cách của bạn thì xong

[dacklayer]

Mình có 1 góp ý thế này, trong hàm Search của bạn, mình kô thấy có điều kiện dừng. Vậy giả sử mình nhập vào 1 khóa tìm kiếm kô có trong bảng, nó sẽ lặp vô hạn.