• Chủ Nhật, 08/05/2011 13:36 (GMT+7)

    Khai báo danh sách liên kết đơn không có ô đầu mục

    Lượt xem 3531
    Đánh giá

    Câu hỏi :

    Xin hỏi cách khai báo danh sách liên kết đơn không có ô đầu mục trong cấu trúc dữ liệu.



    Trả lời :

    Như bạn đã biết, hiện nay các thuật ngữ tiếng Việt miêu tả các khái niệm trong lĩnh vực tin học chưa được chuẩn hóa, mỗi người mỗi kiểu nên dễ làm cho người đọc hiểu lầm, hiểu sai và thậm chí không hiểu được. Thí dụ trong câu hỏi của bạn có thuật ngữ "ô đầu mục", lúc đầu chúng tôi cũng không hiểu ý muốn nói gì. Sau khi truy tìm trên mạng, chúng tôi thấy thuật ngữ này được dùng trong bài giảng môn "Cấu trúc dữ liệu" của BM. Khoa học Máy tính Trường Đại học Hàng hải.

    Trước hết, chúng tôi xin tóm tắt lại nội dung giới thiệu về danh sách liên kết đơn trong bài giảng: Danh sách liên kết đơn là một trong nhiều cách khác nhau để miêu tả danh sách nhiều phần tử dữ liệu có cấu trúc giống nhau và có mối quan hệ với nhau mà không đòi hỏi các phần tử này nằm liên tục nhau. Để cài đặt danh sách liên kết đơn, ta cài đặt mỗi phần tử trong danh sách thành 1 ô (item), mỗi ô là 1 mẫu tin (record, structure) có 2 trường (field) thông tin chức năng: Trường "value" chứa giá trị của phần tử trong danh sách, trường "next" là một con trỏ (pointer) giữ địa chỉ của ô kế tiếp. Trường "next" của phần tử cuối trong danh sách chỉ đến một giá trị đặc biệt là NULL. Sau đây là hình minh họa sự cài đặt 1 danh sách liên kết đơn có n phần tử (dùng n ô miêu tả n phần tử thật của danh sách và 1 ô khác (ô đầu mục) để miêu tả đầu danh sách):



    Thật ra, thường không ai cài đặt y như hình trên, vì như vậy là không cần thiết và không hiệu quả. Chúng ta sẽ cài đặt theo hình sau:

    Sự khác nhau giữa 2 hình trên là thay vì ta phải tốn 1 ô đầu mục để chứa địa chỉ phần tử đầu danh sách, ta chỉ tốn 1 biến pointer (dài 4 byte trong ứng dụng chạy trên Windows hay Linux). Chúng tôi dùng ngôn ngữ C++ (ngôn ngữ được dùng trong bài giảng kể trên) để thể hiện danh sách liên kết đơn theo tinh thần của hình trên như sau:



    //định nghĩa kiểu của từng item (ô)
    #define NULL 0
    typedef struct Element {
    int value; //giả sử nội dung phần tử là số nguyên
    Element* next; //trỏ tới phần tử kết tiếp
    } Element;
    //định nghĩa biến miêu tả header của danh sách
    Element* head=NULL;
    //tạo n phần tử từ an đến a1 và thêm vào đầu danh sách liên kết
    int i;
    int n = 10;
    Element* item;
    for (i=n; i >0; i--) {
    item = new Element;
    item->value = i;
    item->next = head;
    head = item;
    }
     

    Ý kiến phản hồi và bình luận      Gởi ý kiến của bạn ?
    Chuyên mục: Cơ sở dữ liệu