In danh sách liên kết chuyển tiếp C++
|
Xin chào các bạn, đảo ngược danh sách được liên kết là một vấn đề mã hóa phổ biến trong các cuộc phỏng vấn Việc làm Lập trình và tôi chắc rằng bạn đã từng gặp điều này trong sự nghiệp của mình, nếu chưa, có thể bạn là người mới hơn và bạn sẽ tìm hiểu về . Trong bài viết trước, tôi đã hướng dẫn các bạn cách sử dụng đệ quy để đảo ngược danh sách liên kết, và hôm nay, tôi sẽ hướng dẫn các bạn cách đảo ngược danh sách liên kết đơn trong Java mà không cần đệ quy. Danh sách liên kết đơn hay còn gọi là danh sách chỉ liên kết là tập hợp các nút chỉ có thể duyệt theo một hướng như theo chiều thuận từ đầu đến đuôi. Mỗi nút trong danh sách liên kết chứa hai thứ, dữ liệu và một con trỏ tới nút tiếp theo trong danh sách. Show
Triển khai danh sách liên kết của riêng bạn trong các cuộc phỏng vấnVì việc sử dụng các lớp Java hiện có hiện được cho phép trong các cuộc phỏng vấn Việc làm Lập trình, nên bạn cần tạo lớp của riêng mình để viết mã. Trong ví dụ này, tôi đã tạo lớp danh sách liên kết đơn của riêng mình. Tương tự với java. sử dụng. LinkedList cũng chứa một lớp tĩnh lồng nhau Nút , đại diện cho một nút trong danh sách được liên kết.Lớp này chứa thuộc tính số nguyên để giữ phần dữ liệu và một Nút khác . Nếu bạn muốn tạo một danh sách liên kết Chung, bạn nên thay thế reference to point to the next one in the list. If you want to create a Generic linked list, you should replace int bằng T, a generic type, as shown here. Để chứng minh rằng phương pháp đảo ngược của chúng ta đang hoạt động, chúng ta không chỉ phải tạo một danh sách được liên kết mà còn cần điền vào danh sách được liên kết. Để điền, bạn cần triển khai phương thức add() trên danh sách liên kết đơn. Bạn có hai lựa chọn, thêm phần tử ở đầu hoặc ở phần đuôi, việc thêm phần tử vào phần đầu rất dễ dàng vì nó không yêu cầu duyệt cho đến cuối nhưng nếu bạn muốn . Tôi cũng đã tạo một phương thức print() để in tất cả các nút của danh sách liên kết đơn, được phân tách bằng dấu cách. Phương pháp này rất hữu ích để chứng minh rằng phương pháp đảo ngược của chúng ta có thực sự hoạt động hay không, vì bạn có thể in danh sách được liên kết trước và sau khi đảo ngược. Nếu bạn gặp khó khăn với việc triển khai các cấu trúc dữ liệu thiết yếu như danh sách được liên kết, cây nhị phân, bảng băm bằng mã của riêng bạn trên bất kỳ ngôn ngữ lập trình nào như Java thì tôi khuyên bạn nên tham gia Thuật toán và cấu trúc dữ liệu - Phần 1 . Chúng sẽ không chỉ giúp bạn viết cấu trúc dữ liệu mà còn cả cách tính toán độ phức tạp của không gian và thời gian.  Chương trình Java đảo ngược danh sách liên kết đơn mà không cần đệ quyĐây là chương trình mẫu của chúng tôi để trình bày cách đảo ngược danh sách liên kết trong Java. Để đảo ngược, trước tiên tôi đã tạo một lớp có tên là SinglyLinkedList , đại diện cho cấu trúc dữ liệu danh sách được liên kết. Tôi đã triển khai thêm phương thức add() và print() để thêm .Logic đảo ngược danh sách liên kết được gói gọn bên trong phương thức reverse() . Nó duyệt qua danh sách liên kết từ đầu đến đuôi và đảo ngược liên kết trong từng bước giống như từng nút thay vì trỏ đến phần tử tiếp theo bắt đầu trỏ đến nút trước, theo cách này, toàn bộ danh sách được liên kết sẽ bị đảo ngược khi bạn đến phần tử cuối cùng, điều này . Đây là một sơ đồ hay giải thích thuật toán đảo ngược danh sách liên kết mà không cần đệ quy trong Java. Bạn có thể thấy rằng các liên kết được đảo ngược trong mỗi bước bằng cách sử dụng trước đó và tiếp theo của con trỏ. Đây còn gọi là thuật toán lặp đảo ngược danh sách liên kết trong Java. Đối với thuật toán đệ quy, bạn cũng có thể xem sách Giới thiệu về thuật toán của Thomas H. Cormen. ______0 Bạn có thể thấy danh sách liên kết đã đảo ngược, trước đó 1 là phần tử đầu tiên bây giờ nó là cuối cùng và 3 là phần tử đầu tiên của danh sách liên kết hoặc . Đó là tất cả về cách đảo ngược danh sách liên kết đơn trong Java mà không cần sử dụng đệ quy. Có, chúng tôi đã không sử dụng đệ quy trong giải pháp này, thay vào đó, chúng tôi đã sử dụng phép lặp. Bạn có thể thấy vòng lặp while bên trong phương thức reverse() . Nhân tiện, nếu bạn nhận được câu hỏi này trong cuộc phỏng vấn thực tế, rất có thể bạn sẽ được yêu cầu đảo ngược danh sách được liên kết bằng cách sử dụng đệ quy ngay bây giờ. Vì vậy, hãy chờ một bài viết khác để xem giải pháp đó hoặc xem cuốn sách Phỏng vấn viết mã có giải pháp cho vấn đề này cùng với một số giải pháp khác.
Thanks for reading this article so far. If you like this article then please share it with your friends and colleagues. If you have any questions or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome. P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check these free data structure and algorithms courses on Udemy. Làm cách nào để in danh sách liên kết trong C?Để in dữ liệu của từng nút, chúng ta phải duyệt danh sách liên kết cho đến hết. . Tạo một nút tạm thời (tạm thời) và gán địa chỉ của nút đầu In dữ liệu có trong nút tạm thời Sau khi in dữ liệu, di chuyển con trỏ tạm thời đến nút tiếp theo Làm quá trình trên cho đến khi chúng ta kết thúc Làm cách nào để in danh sách được liên kết theo thứ tự ngược lại trong C?Làm cách nào để đảo ngược Danh sách được liên kết? . Bước 1 – Lấy một con trỏ ptr Bước 2 – Kiểm tra Linked List có node hay không Bước 3 – Nếu danh sách liên kết trống, trả về 0 Bước 4 – Nếu danh sách được liên kết có các nút, hãy di chuyển con trỏ về phía trước cho đến khi nó đạt NULL Bước 5 – Quay lại và in dữ liệu của các nút Làm cách nào để duyệt dữ liệu trong danh sách được liên kết theo hướng tiến và lùi?Có thể sử dụng ListIterator để duyệt qua các phần tử theo hướng thuận cũng như hướng ngược lại trong Danh sách được liên kết . Phương thức hasPrevious() trong ListIterator trả về true nếu có nhiều phần tử hơn trong LinkedList khi di chuyển theo hướng ngược lại và trả về false nếu không.
Làm cách nào để tìm kiếm một phần tử trong danh sách liên kết trong C?Triển khai Chương trình C để tìm kiếm một phần tử trong danh sách liên kết. - . Khởi tạo đầu = Null Thêm một vài mục vào Danh sách liên kết Lấy đầu vào từ người dùng cho mục anh ta muốn tìm kiếm Duyệt tuyến tính Danh sách được liên kết từ đầu đến cuối cho đến khi bạn chạm vào nút null |
