Từ 1 tới 9 trên tổng số 9 kết quả

Đề tài: Bảng băm (HashTable) thực hiện trên C

  1. #1
    Ngày gia nhập
    01 2007
    Bài viết
    412

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

    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é.

  2. #2
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    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 ?
    None!

  3. #3
    Ngày gia nhập
    01 2007
    Bài viết
    412

    Trích dẫn Nguyên bản được gửi bởi pete_87 Xem bài viết
    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.

    Trích dẫn Nguyên bản được gửi bởi pete_87 Xem bài viết
    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)

  4. #4
    Ngày gia nhập
    01 2007
    Bài viết
    412

    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
    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. #define M 11  // khai bao kich thuoc bang bam
    4. #define NULLKEY -365  // khai bao nut rong co gia tri la -365
    5. #define TRUE 1
    6. #define FALSE 0
    7. int BangBam[M];  // tao bang bam voi kich thuoc M
    8. int SoNut; // so nut cua bang bam
    9. int HamBam(int k)
    10. {
    11.     return k%M;
    12. }
    13. void KhoiTaoBangBam()
    14. {
    15.     for(int i=0;i<M;i++)
    16.         BangBam[i]=NULLKEY;
    17. }
    18. int Full()  // kiem tra xem bang bam da day hay chua?
    19. {
    20.     if (SoNut==M-1) return TRUE;
    21.     else return FALSE;
    22. }
    23. int Search(int k)  // tim kiem khoa K co o trong bang bam hay khong?
    24. {
    25.     int i=HamBam(k);
    26.     while (BangBam[i]!=k && BangBam[i]!=NULLKEY)
    27.     {
    28.         i++;
    29.         if (i>=M) i=i-M;
    30.     }
    31.     if (BangBam[i]==k) return i;
    32.     else return M;
    33. }
    34. int ThemPhanTu(int k) // them khoa k vao bang bam
    35. {
    36.     int i,j;
    37.     if (Full())
    38.     {
    39.         printf("\nBang bam da day");
    40.         return 0;
    41.     }
    42.     i=HamBam(k);
    43.     while (BangBam[i]!=NULLKEY)
    44.     {
    45.         i++;
    46.         if (i>=M) i=i-M;
    47.     }
    48.     BangBam[i]=k;
    49.     SoNut++;
    50.     return i;
    51. }
    52. void InBangBam()  
    53. {
    54.     printf("\nBANG BAM CUA BAN:\n");
    55.     printf("\n\t\tVi tri\t\t\tKhoa\n");
    56.     for(int i=0;i<M;i++)
    57.         if (BangBam[i]!=NULLKEY)
    58.             printf("\n\t\t%d\t\t\t%d",i,BangBam[i]);
    59.         else
    60.             printf("\n\t\t%d\t\t\tNULL",i);
    61. }
    62.  
    63. void main()
    64. {
    65.     clrscr();
    66.     int khoa_nhap,khoa_tim;
    67.     KhoiTaoBangBam();
    68.     printf("\tCHUONG TRINH MINH HOA BANG BAM DUNG PHUONG PHAP TIM TUYEN TINH");
    69.     for(int i=0;i<M-1;i++)
    70.     {
    71.         printf("\nNhap phan tu thu %d:",i+1);
    72.         scanf("%d",&khoa_nhap);
    73.         ThemPhanTu(khoa_nhap);
    74.     }
    75.     InBangBam();
    76.     printf("\n\nNhap vao khoa ban can tim:");
    77.     scanf("%d",&khoa_tim);
    78.     int result=Search(khoa_tim);
    79.     if (result==M) printf("Khong tim thay %d trong bang bam",khoa_tim);
    80.     else printf("\nTim thay roi! %d nam o vi tri thu %d trong bang bam",khoa_tim,result);
    81.     getch();
    82. }

    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.

  5. #5
    Ngày gia nhập
    02 2009
    Bài viết
    2

    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

  6. #6
    Ngày gia nhập
    11 2010
    Bài viết
    1

    Mặc định Hỏi về bài viết

    Trích dẫn Nguyên bản được gửi bởi neverland87 Xem bài viết
    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
    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. #define M 11  // khai bao kich thuoc bang bam
    4. #define NULLKEY -365  // khai bao nut rong co gia tri la -365
    5. #define TRUE 1
    6. #define FALSE 0
    7. int BangBam[M];  // tao bang bam voi kich thuoc M
    8. int SoNut; // so nut cua bang bam
    9. int HamBam(int k)
    10. {
    11.     return k%M;
    12. }
    13. void KhoiTaoBangBam()
    14. {
    15.     for(int i=0;i<M;i++)
    16.         BangBam[i]=NULLKEY;
    17. }
    18. int Full()  // kiem tra xem bang bam da day hay chua?
    19. {
    20.     if (SoNut==M-1) return TRUE;
    21.     else return FALSE;
    22. }
    23. int Search(int k)  // tim kiem khoa K co o trong bang bam hay khong?
    24. {
    25.     int i=HamBam(k);
    26.     while (BangBam[i]!=k && BangBam[i]!=NULLKEY)
    27.     {
    28.         i++;
    29.         if (i>=M) i=i-M;
    30.     }
    31.     if (BangBam[i]==k) return i;
    32.     else return M;
    33. }
    34. int ThemPhanTu(int k) // them khoa k vao bang bam
    35. {
    36.     int i,j;
    37.     if (Full())
    38.     {
    39.         printf("\nBang bam da day");
    40.         return 0;
    41.     }
    42.     i=HamBam(k);
    43.     while (BangBam[i]!=NULLKEY)
    44.     {
    45.         i++;
    46.         if (i>=M) i=i-M;
    47.     }
    48.     BangBam[i]=k;
    49.     SoNut++;
    50.     return i;
    51. }
    52. void InBangBam()  
    53. {
    54.     printf("\nBANG BAM CUA BAN:\n");
    55.     printf("\n\t\tVi tri\t\t\tKhoa\n");
    56.     for(int i=0;i<M;i++)
    57.         if (BangBam[i]!=NULLKEY)
    58.             printf("\n\t\t%d\t\t\t%d",i,BangBam[i]);
    59.         else
    60.             printf("\n\t\t%d\t\t\tNULL",i);
    61. }
    62.  
    63. void main()
    64. {
    65.     clrscr();
    66.     int khoa_nhap,khoa_tim;
    67.     KhoiTaoBangBam();
    68.     printf("\tCHUONG TRINH MINH HOA BANG BAM DUNG PHUONG PHAP TIM TUYEN TINH");
    69.     for(int i=0;i<M-1;i++)
    70.     {
    71.         printf("\nNhap phan tu thu %d:",i+1);
    72.         scanf("%d",&khoa_nhap);
    73.         ThemPhanTu(khoa_nhap);
    74.     }
    75.     InBangBam();
    76.     printf("\n\nNhap vao khoa ban can tim:");
    77.     scanf("%d",&khoa_tim);
    78.     int result=Search(khoa_tim);
    79.     if (result==M) printf("Khong tim thay %d trong bang bam",khoa_tim);
    80.     else printf("\nTim thay roi! %d nam o vi tri thu %d trong bang bam",khoa_tim,result);
    81.     getch();
    82. }

    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!

  7. #7
    Ngày gia nhập
    06 2009
    Bài viết
    1

    Mặc định Giải bài 2 đi bạn ơi!

    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!

  8. #8
    Ngày gia nhập
    02 2012
    Bài viết
    5

    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

  9. #9
    Ngày gia nhập
    02 2012
    Bài viết
    5

    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.

Các đề tài tương tự

  1. Xin ví dụ về bảng băm -hashtable
    Gửi bởi faq.c trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 4
    Bài viết cuối: 27-10-2012, 03:44 AM
  2. Sử dụng dc Hashtable trong webservice lỗi: The type System.Collections.Hashtable is not supported
    Gửi bởi hoanghieu883 trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 1
    Bài viết cuối: 25-08-2011, 12:08 PM
  3. Xử lý nút tìm kiếm 1 phần tử trên HashTable như thế nào?
    Gửi bởi thegioi911 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 7
    Bài viết cuối: 05-05-2010, 11:55 AM
  4. HashTable trên C# có tính mở hay đóng?
    Gửi bởi hoangsan_c trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 3
    Bài viết cuối: 17-06-2009, 12:37 AM
  5. Lập trình tìm kiếm | Tìm kiếm với mảng băm (hashtable): ý tưởng & cài đặt
    Gửi bởi sonhn trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 10
    Bài viết cuối: 28-05-2007, 06:05 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn