Thật dễ dàng để thực hiện danh sách liên kết trong C++, nơi bạn có con trỏ. Nhưng làm thế nào chúng được thực hiện bằng các ngôn ngữ khác (như java, python, vv). Tôi không muốn sử dụng được xây dựng trong lớp (được hỗ trợ trong JAVA) cho danh sách liên kết nhưng những gì tôi muốn là làm thế nào để thay thế con trỏ để tạo ra danh sách liên kết?Danh sách liên kết được triển khai như thế nào mà không cần sử dụng con trỏ?
Chúng được triển khai bằng cách sử dụng các tham chiếu về cơ bản (trừ cú pháp) mà bạn không thể làm số học con trỏ với (trong một số ngôn ngữ mà chúng cũng không thể rỗng). Trong nhiều ngôn ngữ, tài liệu tham khảo là cách mặc định của việc sử dụng các biến, không giống như C++, nơi mặc định là theo giá trị.
+1 Tôi thích lời giải thích đó để tham khảo. Nó rất nhanh chóng, dễ dàng và chính xác, ngoài việc hiển nhiên cho các cựu chiến binh C và cho người khác một lý do để tìm hiểu khía cạnh lập trình đó. – delnan
Với các ngôn ngữ khác, bạn xử lý các tham chiếu liên quan chặt chẽ đến con trỏ.
Khi bạn viết lớp của riêng bạn, hãy nói class node, và có mỗi node giữ một trường để tiếp theo node, Bạn thực sự giữ một tham chiếu đến mà nút tiếp theo (hoặc null nếu đó là người cuối cùng)
Thay vì con trỏ trỏ đến một khối bộ nhớ, các tham chiếu được sử dụng, như đã nêu trước đây. Vì vậy, như bạn sẽ có trong C++
Struct Node {
Node *last;
Node *next;
}
nó sẽ trông như thế này:
Struct Node {
Node last;
Node next;
}
Câu cuối cùng là không may. Nếu chúng ta lấy nó như là giá trị mặt, tức là "' Node' là một kiểu giá trị ", nó ngụ ý định nghĩa thứ hai của bạn về' Node' là không hợp lệ bởi vì nó có kích thước vô hạn. Tài liệu tham khảo không phải là địa chỉ thực sự, nhưng chúng * là * indirections. – delnan
Tôi vừa nhận thấy rằng ví dụ thứ hai của bạn không hợp lệ ngay cả khi bỏ qua giải thích đã xóa ngay bây giờ. (Nếu nó được cho là C++ đó là.) – delnan
Nó chỉ đơn giản là nghĩa vụ phải là một hình dung trong mã giả. Cấu trúc chỉ xuất phát từ nền của anh ấy trong C++ –
Một tốt cấu trúc dữ liệu lớp sẽ cho bạn thấy rằng một danh sách liên kết có thể được thực hiện trong bất kỳ ngôn ngữ sử dụng mảng, chẳng hạn như FORTRAN.
Thay vì sử dụng con trỏ, bạn sẽ sử dụng một số phương tiện khác để định vị liên kết tiếp theo. Với mảng, thay vì một con trỏ, bạn sẽ sử dụng một chỉ mục cho phần tử tiếp theo.
Vì vậy, bạn có thể triển khai danh sách được liên kết trong tệp truy cập ngẫu nhiên bằng cách sử dụng vị trí tệp thay vì con trỏ.
Tôi không chắc liệu điều này có được tính là danh sách được liên kết hay không. Nó chắc chắn có những đặc điểm khác nhau từ việc triển khai dựa trên con trỏ, ở chỗ nó bị hạn chế hơn. Ngoài ra, điều này là hoàn toàn bên cạnh điểm vì bạn * có thể * xây dựng các danh sách liên kết "thông thường" (và tất cả các cấu trúc dữ liệu khác dựa trên indirection) với các tham chiếu. – delnan
Đó là một danh sách, và nó được liên kết. Nó không sử dụng con trỏ để liên kết các nút. Đó là một * triển khai * khác của danh sách được liên kết. Tôi đã được dạy điều này trong lớp Data Structures của tôi tại trường đại học. –
Bạn có thể tìm thấy câu trả lời hay trong cuốn sách này - http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 - Tôi sẽ tóm tắt những gì tôi gọi lại cho bạn.
Về cơ bản bạn sẽ có hai mảng có kích thước bằng nhau (hy vọng lớn hơn n trong đó n = số phần tử bạn muốn lưu trữ). Chúng tôi sẽ gọi chúng là Mảng A và Mảng B.
Mảng A [i] giữ giá trị dữ liệu. Mảng B [i] giữ giá trị 'tiếp theo' 'k' sao cho A [i] -> next = A [k].
Hy vọng điều này sẽ hữu ích.
Xem nhận xét của tôi về câu trả lời của Thomas Matthew. – delnan
Hãy nhớ khái niệm về danh sách được liên kết là bạn có thể lấy từ phần tử này sang phần tử khác. Làm thế nào bạn làm điều đó có thể rất khác nhau.
Trong C++ chẳng hạn như bạn đã đề cập, bạn có thể sử dụng con trỏ. Nói cách khác là bạn sử dụng địa chỉ bộ nhớ của đối tượng.
Nhưng đó chỉ là một cách. Nếu tất cả các đối tượng của bạn được tham chiếu từ một mảng, thì bạn sẽ có thể tham chiếu một đối tượng bằng chỉ mục của nó trên mảng đó. Vì vậy, mỗi phần tử trong danh sách được liên kết của bạn sẽ có một số nguyên chỉ định chỉ mục của đối tượng được kết nối.
Để cung cấp cho bạn một ví dụ khác. Nếu bạn có một từ điển mà bạn liên kết các đối tượng với các chuỗi. Sau đó, bạn có thể sử dụng các chuỗi để tham chiếu lẫn nhau.
Khái niệm cốt lõi đối với danh sách được liên kết không phải là con trỏ, đó là các yếu tố trong danh sách có trách nhiệm theo dõi yếu tố được kết nối.
Đọc điều này và xem liệu có đủ địa chỉ cho câu hỏi của bạn không: http://stackoverflow.com/questions/7480783/pointers-in-java –
@asawyer Không có gì được chuyển qua tham chiếu bằng Python và Java. Không phải trong nhiều ngôn ngữ khác sử dụng tài liệu tham khảo trong cùng một ý nghĩa. – delnan
@asawyer: đồng ý với delnan. Java được truyền theo giá trị. Luôn luôn. Giá trị đó có thể là một tham chiếu, nhưng giá trị là giá trị được chuyển. –