In k nút cuối cùng của danh sách liên kết theo thứ tự ngược lại Phương pháp tiếp cận đệ quy trong ngôn ngữ C

Nhiệm vụ là in k nút bắt đầu từ cuối danh sách được liên kết bằng cách sử dụng phương pháp đệ quy.

Phương pháp tiếp cận đệ quy là phương pháp trong đó hàm tự gọi đi gọi lại cho đến khi thực hiện lệnh gọi và do đó lưu trữ kết quả.

Giả sử, danh sách chứa các nút 29, 34, 43, 56 và 88 và giá trị của k lớn hơn 2 so với kết quả đầu ra sẽ là k nút cuối cùng chẳng hạn như 56 và 88.

Ví dụ

Linked List: 29->34->43->56->88
Input: 2
Output: 88 56

Như đã chỉ định, phương pháp đệ quy sẽ được sử dụng để duyệt qua danh sách từ bản ghi cuối về số lần danh sách được duyệt và hàm đệ quy sẽ được gọi cho đến giá trị thứ k bởi một biến con trỏ.

Đoạn mã dưới đây cho thấy cách triển khai c của thuật toán đã cho.

Thuật toán

START
   Step 1 -> create node variable of type structure
      Declare int data
      Declare pointer of type node using *next
   Step 2 -> Declare function as node* get(int data)
      Create newnode using malloc function
      Set newnode->data = data
      Set newnode->next = NULL
      return newnode
   step 3 -> Declare function void lastval(node* head, int& count, int k)
      IF !head
         Return
      Set lastval(head->next, count, k)
      Set count++
      IF (count <= k)
         Print head->data
   Step 4 -> In Main()
      Generate head using node* head = get(11)
      Set k and count to 0
      Call lastval(head,k,count)
STOP

Ví dụ

#include<stdio.h>
#include<stdlib.h>
// Structure of a node
struct node {
   int data;
   node* next;
};
// Function to get a new node
node* get(int data) {
   struct node* newnode = (struct node*)malloc(sizeof(struct node));
   newnode->data = data;
   newnode->next = NULL;
   return newnode;
}
//print the last k values of a node
void lastval(node* head, int& count, int k) {
   if (!head)
      return;
   lastval(head->next, count, k);
   count++;
   if (count <= k)
      printf("%d ", head->data);
}
int main() {
   node* head = get(11); //inserting elements into the list
   head->next = get(243);
   head->next->next = get(321);
   head->next->next->next = get(421);
   head->next->next->next->next = get(522);
   int k = 2, count = 0;
   printf(" last %d nodes of a list are :",k);
   // print last k nodes
   lastval(head, count, k);
   return 0;
}

Đầu ra

Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau.

last 2 nodes of a list are :522 421