//
you're reading...
00 - Chủ đề chung

Danh sách liên kết đơn

Danh sách đơn là kiểu liên kết cơ bản nhất của tất cả các cấu trúc dữ liệu được liên kết. Một danh sách liên kết đơn là một chuỗi các đối tượng được cấp phát động, mỗi phần tử trong danh sách đó trỏ đến phần tử kế sau của nó trong danh sách. Mặc dù có sự đơn giản rõ ràng này, có những biến thể khi thực hiện có thể có vô số. Hình  dưới đây cho thấy một số các biến thể danh sách liên kết đơn phổ biến nhất.

   figure3190
Hình 1: Các mô tả biến danh sách liên kết đơn.

Danh sách đơn lẻ liên kết cơ bản được thể hiện trong hình

(a). Mỗi phần tử của danh sách trỏ đến phần tử kế tiếp của nó và phần tử cuối cùng chứa tham chiếu rỗng. Một biến, nhãn head trong hình (a), được sử dụng để theo dõi đầu danh sách.

Danh sách liên kết đơn về cơ bản là không hiệu quả trong những trường hợp khi chúng ta muốn thêm các phần tử ở cả hai đầu của danh sách. Trong khi đó sẽ là dễ dàng để thêm các phần tử vào phần đầu của danh sách, để thêm phần tử vào cuối ( tail ) chúng ta cần phải xác định vị trí của phần tử cuối cùng. Nếu danh sách đơn được sử dụng, toàn bộ danh sách cần phải được đi qua để tìm ra cái đuôi của nó.

Hình (b) cho thấy một cách để làm cho việc thêm phần tử vào đuôi của một danh sách hiệu quả hơn. Các giải pháp sử dụng một biến thứ hai, tail , trong đó chỉ tới phần tử cuối cùng của danh sách. Tất nhiên, hiệu quả thời gian này đi kèm với chi phí của các không gian thêm được sử dụng để lưu trữ các biến đuôi .

Danh sách liên kết đơn có gắn nhãn (c) trong hình minh họa hai thủ thuật lập trình phổ biến. Có một phần tử thêm ở phần đầu của danh sách được gọi là một lính canh (sentinent) . Phần tử này không bao giờ được sử dụng để lưu trữ dữ liệu và nó luôn luôn hiện diện. Ưu điểm chính của việc sử dụng một phần tử lính canh là nó đơn giản hóa việc lập trình các hoạt động nhất định. Ví dụ, vì luôn có một biến canh gác đứng, chúng ta không bao giờ cần phải sửa đổi các đầu biến. Tất nhiên, bất lợi của việc cò một lính canh  như vậy được chỉ ra trong (c) là phải thêm không gian cần thiết, và các lính canh cần được tạo ra khi danh sách được khởi tạo.

Danh sách (c) cũng là một danh sách tròn  . Thay vì sử dụng một tham khảo rỗng để phân ranh giới cuối danh sách, phần tử cuối cùng của danh sách trỏ đến các hần tử lính canh. Ưu điểm của cách lập trình này là chèn ở đầu danh sách, chèn vào đuôi của danh sách, và chèn vào một vị trí tùy ý trong danh sách đều là những hoạt động giống hệt nhau.

Tất nhiên, cũng có thể làm cho một danh sách liên kết đơn trở thành tròn mà không sử dụng một phần tử lính canh. Hình  (d) cho thấy một sự thay đổi trong đó một biến duy nhất được sử dụng để theo dõi các danh sách, nhưng lần này biến, tail , trỏ đến phần tử cuối cùng của danh sách. Từ đó danh sách này là thông suốt trong trường hợp này, phần tử  đầu tiên liền sau phần tử cuối cùng của danh sách. Vì vậy, nó là tương đối đơn giản để chèn cả ở đầu và ở đuôi của danh sách này. Sự thay đổi này làm giảm thiểu các yêu cầu lưu trữ,chi phí ít thời gian cho các hoạt động nhất định.

Hình  2 minh họa cách danh sách rỗng (tức là, danh sách không chứa phần tử nào) được đại diện cho mỗi biến thể đưa ra trong hình 1. Chú ý rằng các phần tử lính canh luôn có mặt trong danh sách biến thể (c). Mặt khác, trong các biến danh sách mà không sử dụng một lính canh, các tham khảo rỗng được sử dụng để chỉ ra danh sách trống.

figure3388
Hình 2: Danh sách rỗng được thể hiện trong danh sách liên kết đơn.

Trong phần sau, chúng tôi sẽ trình bày chi tiết thi hành một danh sách đơn lẻ liên kết chung. Chúng tôi đã chọn để trình bày sự biến đổi (b) – một trong đó sử dụng một đầu và một cái đuôi – kể từ khi là hỗ trợ thêm và hoạt động thêm vào trước một cách hiệu quả.


About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: