Chèn đệ quy và danh sách liên kết duyệt trong C ++

Chúng tôi được cung cấp với các giá trị số nguyên sẽ được sử dụng để tạo thành một danh sách liên kết. Nhiệm vụ trước tiên là chèn và sau đó duyệt qua một danh sách được liên kết đơn lẻ bằng cách sử dụng phương pháp đệ quy.

Bổ sung đệ quy các nút ở cuối

• Nếu phần đầu là NULL → thêm nút vào phần đầu

• Thêm cái khác vào đầu (đầu → tiếp theo)

Truyền tải đệ quy của các nút

• Nếu đầu là NULL → thoát ra

• In khác (đầu → tiếp theo)

Ví dụ

Đầu vào - 1 - 2 - 7 - 9 - 10

Đầu ra - Danh sách liên kết:1 → 2 → 7 → 9 → 10 → NULL

Đầu vào - 12 - 21 - 17 - 94 - 18

Đầu ra - Danh sách liên kết:12 → 21 → 17 → 94 → 18 → NULL

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Trong cách tiếp cận này, chúng tôi sẽ sử dụng các hàm để thêm các nút và duyệt qua danh sách được liên kết đơn lẻ và gọi chúng một cách đệ quy cho đầu vào tiếp theo.

• Lấy cấu trúc SLLNode với SLLNode số nguyên và con trỏ tiếp theo * next.

• Hàm addtoEnd (SLLNode * head, int data) đưa con trỏ đến đầu danh sách và số nguyên cho phần dữ liệu và thêm nút vào cuối danh sách được liên kết.

• Nếu con trỏ đầu là NULL thì danh sách trống, bây giờ hãy thêm một nút mới và đặt nó làm đầu. Thêm đầu → tiếp theo là NULL. Quay lại con trỏ đến nút này

• Nếu head không rỗng thì nút thêm vào head → tiếp theo sử dụng head-> next =addtoEnd (head-> next, data).

• Hàm traverseList (SLLNode * head) bắt đầu duyệt từ head và in từng giá trị.

• Nếu đầu là NULL thì in NULL và trả về.

• Giá trị dữ liệu in khác và duyệt tiếp theo bằng cách sử dụng traverseList (head-> next).

• Bên trong chính, tạo danh sách bằng addtoEnd () và in danh sách bằng traverseList ().

Ví dụ

#include <bits/stdc++.h>
using namespace std;
struct SLLNode {
   int data;
   SLLNode* next;
};
SLLNode* addtoEnd(SLLNode* head, int data){
   if (head == NULL){
      SLLNode *nodex = new SLLNode;
      nodex->data = data;
      nodex->next = NULL;
      return nodex;
   }
   else{
      head->next = addtoEnd(head->next, data);
    }
   return head;
}
void traverseList(SLLNode* head){
   if (head == NULL){
      cout <<"NULL";
      return;
   }
   cout << head->data << " -> ";
   traverseList(head->next);
}
int main(){
   SLLNode* head1 = NULL;
   head1 = addtoEnd(head1, 1);
   head1 = addtoEnd(head1, 8);
   head1 = addtoEnd(head1, 56);
   head1 = addtoEnd(head1, 12);
   head1 = addtoEnd(head1, 34);
   cout<<"Linked List is :"<<endl;
   traverseList(head1);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

Linked List is :
1 -> 8 -> 56 -> 12 -> 34 -> NULL