Cơ bản về cấu trúc dữ liệu và giải thuật - Danh sách P1

[trungndm]

Trong bài này mình xin giới thiệu kiểu dữ liệu tiếp theo đó là “danh sách” – list.

Danh sách là một tập hợp các phần tử sắp xếp theo thứ tự nhất định.

Để cài đặt một danh sách, ta cần các dữ liệu sau:

• Đối tượng biểu hiện của danh sách (L).
• Đối tượng biểu hiện một nút trong danh sách (x).
• Dữ liệu biểu thể hiện vị trí của một phần tử trong danh sách (p).
• Một hàm trả về vị trí tiếp theo ngay sau vị trí cuối cùng của danh sách END(L).

Một số thao tác với danh sách liên kết L:

• Insert(x,p,L): chèn phần tử x vào vị trí p trong dánh sách L
• Locate(x,L): lấy vị trị của x trong danh sách L
• Retrieve(p,L): truy cập phần tử có vị trí p trong danh sách L
• Delete(p,L): xóa phần tử có vị trí p trong danh sách L
• Next(p,L): trả về phần tử ngay sau phần tử có vị trí p trong L
• Prev(p,L): trả về phần tử ngay trước phần tử có vị trí p trong L
• MakeNull(L): làm trống danh sách L và trả về giá trị END(L)
• First(L): trả về vị trí đầu tiên trong L
• PrintList(L): in ra tất cả các phần tử theo thứ tự có trong L

So sánh danh sách liên kết và mảng:

Ví dụ danh sách liên kết đơn:

Trên đây là phần giới thiệu qua về “Danh sách liên kết” . Ở phần tiếp theo chúng ta sẽ tìm hiểu cách cài đặt 1 số hàm với danh sách liên kết