Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
Bảng giá phần mềm
Educations Software

Đại Lý - Chi Nhánh

Bản tin điện tử
 
Đăng nhập/Đăng ký
Bí danh
Mật khẩu
Mã kiểm traMã kiểm tra
Lặp lại mã kiểm tra
Ghi nhớ
 
Quên mật khẩu | Đăng ký mới

 
Giỏ hàng

Xem giỏ hàng


Giỏ hàng chưa có sản phẩm

 
Xem bài viết theo các chủ đề hiện có
  • Hoạt động của công ty (701 bài viết)
  • Sản phẩm mới (217 bài viết)
  • Dành cho Giáo viên (552 bài viết)
  • Lập trình Scratch (3 bài viết)
  • Mô hình & Giải pháp (155 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (126 bài viết)
  • Hỗ trợ khách hàng (482 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (242 bài viết)
  • Học tiếng Việt (182 bài viết)
  • Thông tin khuyến mại (80 bài viết)
  • Download - Archive- Update (289 bài viết)
  • Các Website hữu ích (71 bài viết)
  • Cùng Học (98 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (74 bài viết)
  • Thông tin tuyển dụng (55 bài viết)
  • School@net 15 năm (153 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (123 bài viết)
  • Khám phá phần mềm (122 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (36 bài viết)
  • Phần mềm cho em (13 bài viết)
  • ĐỐ VUI - THƯ GIÃN (360 bài viết)
  • Các vấn đề giáo dục (1209 bài viết)
  • Bài học trực tuyến (1033 bài viết)
  • Hoàng Sa - Trường Sa (17 bài viết)
  • Vui học đường (276 bài viết)
  • Tin học và Toán học (220 bài viết)
  • Truyện cổ tích - Truyện thiếu nhi (181 bài viết)
  • Việt Nam - 4000 năm lịch sử (97 bài viết)
  • Xem toàn bộ bài viết (8179 bài viết)
  •  
    Thành viên có mặt
    Khách: 10
    Thành viên: 0
    Tổng cộng: 10
     
    Số người truy cập
    Hiện đã có 55910034 lượt người đến thăm trang Web của chúng tôi.

    Tập hợp và Cấu trúc dữ liệu tập hợp

    Ngày gửi bài: 22/07/2008
    Số lượt đọc: 2647

    “Hãy cho tôi một điểm tựa, tôi sẽ nâng cả trái đất lên” - Archimède. Lý thuyết tập hợp được đưa ra bởi George Cantor năm 1895, thực sự là một “điểm tựa” như thế của toán học hiện đại. Lý thuyết tập hợp là cơ sở tuyệt vời cho việc giải quyết sự khủng hoảng của giải tích toán học, hơn thế nó cung cấp một nền tảng thống nhất cho việc xây dựng, và phát triển hầu như toàn bộ các ngành toán học khác. Thật không sai khi nói: “George Cantor là nhà toán học xuất sắc nhất thế kỷ, và của mọi thế kỷ” - David Hilbert. Khái niệm tập hợp được hiểu như là nhóm của các đối tượng không được sắp thứ tự gọi là phần tử. Trong tin học tập hợp được biết đến như là một cấu trúc dữ liệu trừu tượng cơ bản, góp phần xây dựng nên nhiều cấu trúc phức tạp khác như từ điển, hàng ưu tiên..., và là nền tảng của nhiều thuật toán quan trọng.

    Trên quan điểm của cấu trúc dữ liệu, một tập hợp là một nhóm không có thứ tự các phần tử, trên đó định nghĩa các phép toán cơ bản: phép giao hai tập hợp S1, S2, ký hiệu S1 S2, là một tập hợp có các phần tử thuộc hai tập hợp đó. Hợp của S1, S2, ký hiệu S1 S2, là tập hợp có các phần tử thuộc S1, thuộc S2, hay thuộc cả hai tập hợp đó. Hiệu của S1, S2, ký hiệu S1-S2, là tập hợp gồm các phần tử thuộc S1 nhưng không thuộc S2. Giản đồ Venn (hình 1) là sự minh họa trực quan cho những phép toán này.

     

    Tập hợp là kiểu dữ liệu tiền định trong một số ngôn ngữ lập trình bậc cao, nhưng hầu hết chúng đều có những hạn chế về kiểu và số lượng các phần tử. Đơn cử như trong ngôn ngữ lập trình Pascal, kiểu phần tử của một tập hợp chỉ có thể là kiểu có thứ tự (Ordinal type), và có số lượng không quá 256. Dễ nhận thấy rằng tập hợp được sử dụng rất nhiều trong các thuật toán quan trọng, việc sử dụng chúng làm cho thuật toán trở nên “gọn gàng” và “sáng sủa”, mà các thuật toán trên đồ thị là một ví dụ. Chính vì lẽ đó ta sẽ cài đặt tập hợp trở thành một cấu trúc dữ liệu mềm dẻo hơn, chấp nhận các phần tử có kiểu bất kỳ phù hợp với yêu cầu của nhiều bài toán. Có nhiều phương pháp cài đặt tập hợp với đặc trưng về hiệu xuất của các phép toán khác nhau, như phương pháp vector bit, bảng băm” Chúng ta sẽ xem sét một cài đặt tập hợp bằng danh sách móc nối. Bằng cách này cấu trúc của một tập hợp được mô tả nhưhình 2.

     

    Dưới đây trình bày cài đặt tập hợp bằng C++, trong Borland Turbo C++ 4.5 for windows hoặc trong TC++3.0 bạn xây dựng tệp TAPHOP.H có nội dung như sau:

     

    #include "stdio.h"

    #include "conio.h"

    #include "dos.h"

    #include "memory.h"

    #include "malloc.h"

    typedef struct node

    {

    void*element;

    node*link;

    };

    typedef struct SET

    {

    unsigned int size;

    node*data;

    };

     

    //** thu tuc khoi tao tap hop rong **//

    voidinit( SET&s, unsigned int sizeset)

    {

    s.size=sizeset;

    s.data=NULL;

    }

    //** kiem tra tap hop rong **//

    intempty( SETs)

    {

    return (s.data==NULL);

    }

    //** ham kiem tra mot doi tuong co thuoc tap hop khong **//

    int in (SET s, void *item)

    {

    node *p; int result=0;

    p=s.data;

    while ((p != NULL)&&(!result))

    {

    if (!memcmp(p->element,item,s.size)) result=1;

    p=p->link;

    }

    return result;

    }

    //** ham them mot phan tu vao tap hop **//

    int add(SET &s, void *item)

    {

    node *p, *tg;

    int result=0;

    if (in(s,item))

    result=0;

    else

    {

    tg= new(node);

    tg->element= malloc(s.size);

    movedata(FP_SEG(item),FP_OFF(item),FP_SEG(tg->element),FP_OFF(tg->element),s.size);tg->link = s.data;

    s.data= tg;

    result= 1;

    }

    return result;

    }

    //** phep loai bo mot phan tu khoi tap hop **//

    int remove(SET &s,void*item)

    {

    node *p,*q;

    int result =1, found=0 ;

    if(!in(s,item) )

    result=0;

    else

    {

    p=s.data;

    while ((p!=NULL)&&(!found))

    {

    if (!memcmp(p->element,item,s.size)) found=1;

    else

    p=p->link;

    }

     

    if (result)

    {

    q=s.data;

    if (q==p) // xoa nut dau

    {

    s.data=p->link;

    free (p->element);

    delete (p);

    }

    else // xoa nut giua

    {

    while (q->link!=p)

    q=q->link;

    q->link=p->link;

    free (p->element);

    delete (p);

    }

    }

    }

    return result;

    }

    //** phep xoa mot tap hop **//

    void deleteset(SET &s)

    {

    node *p,*tg;

    p=s.data;

    while (p != NULL )

    {

    tg=p;

    p=p->link;

    free (tg->element);

    delete (tg);

    }

    s.data=NULL;

    }

    // ** phep gan tap s1 cho tap s2 **//

    void assign(SET s1, SET &s2)

    {

    node *p;

    deleteset(s2);

    p=s1.data;

    while (p !=NULL)

    {

    add(s2,p->element);

    p=p->link;

    }

    }

    //** toan tu hop cua hai tap hop **//

    SET operator || (SET s1, SET s2)

    {

    SET tem; node *p;

    init(tem,s1.size);

    assign(s2,tem);

    p=s1.data;

    while (p !=NULL)

    {

    add(tem,p->element);

    p=p->link;

    }

    return tem;

    }

    // ** toan tu giao cua hai tap hop**//

    SET operator && (SET s1, SET s2)

    {

    SET tem; node *p;

    init(tem,s1.size);

    p=s1.data;

    while (p != NULL)

    {

    if ( in(s2,p->element) )add(tem,p->element);

    p=p->link;

    }

    return tem;

    }

    //** toan tu tru tap hop s1 cho tap hop s2 **//

    SET operator - (SET s1, SET s2)

    {

    SET tem; node *p;

    init(tem,s1.size);

    p=s1.data;

    while (p !=NULL )

    {

    if ( !in(s2,p->element)) add(tem,p->element);

    p=p->link;

    }

    return tem;

    }

     

    Cấu trúc dữ liệu SET cài đặt ở trên chấp nhận các phần tử có kiểu bất kỳ, có nghĩa là ta có thể khai báo một tập hợp của các số phức, vector, ma trận hay thậm chí là tập hợp. Các bạn có thể thực hiện cài đặt này trong các môi trường lập trình khác nhau. Trong Visual C++, với một sự thay đổi nhỏ là ta dùng hàm memcpy(item,(tg->element),s.size), thay cho hàm movedata(FP_SEG(item),FP_OFF(item),FP_SEG(tg->element),FP_OFF(tg->element),s.size), còn trong Pascal hay Delphi ta sử dụng kỹ thuật “đối không kiểu”.

    Ví dụ áp dụng:Ta cài đặt thuật toán sàng Eratosthens để tìm các số nguyên tố bằng tập hợp.

     

    #include "stdio.h"

    #include "conio.h"

    #include "taphop.h"

    const intnumber = 1000;

    void main()

    {

    SET sang, nguyento; int i,j;

    init(nguyento,sizeof(int)); init(sang,sizeof(int));

    for (i=2;i<=number;i++) add(sang,&i);

    i=2;

    while (!empty(sang))

    {

    while ((i<=number)&&(!in(sang,&i))) i=i+1;

    add(nguyento,&i);

    j=i;

    while (j<=number)

    {

    remove(sang,&j);

    j=j+i;

    }

    }

    for (i=1; i<=number;i++) // hienthi

    if (in(nguyento,&i))

    {

    printf("%4d ",i); remove(nguyento,&i);

    }

    }

    “Tôi thấy, nhưng tôi không tin” - George Cantor. Để có thể hiểu thấu đáo, thấy được ứng dụng của cấu trúc đữ liệu trên; không có cách nào tốt hơn là chúng ta hãy cài đặt và sử dụng nó. Chúc các bạn thành công!

    Bùi Văn Tân

    School@net (Theo THNT)



     Bản để in  Lưu dạng file  Gửi tin qua email


    Những bài viết khác:



    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 1407 - Nhà 17T2 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Điện thoại: (024) 62511017 - Fax: (024) 62511081
    Email: school.net@hn.vnn.vn / thukhachhang@yahoo.com


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.