使用C語言遞迴方法列印連結串列的最後k個節點


任務是從連結串列的末尾列印k個節點,使用遞迴方法。

遞迴方法是一種函式不斷呼叫自身直到滿足條件的方法,因此會儲存結果。

例如,連結串列包含節點29、34、43、56和88,k的值為2,則輸出將是最後的k個節點,即56和88。

示例

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

如前所述,應使用遞迴方法,該方法將從末尾遍歷列表,跟蹤需要遍歷列表的次數,並且遞迴函式將由指標變數呼叫,直到第k個值。

以下程式碼顯示了給定演算法的C語言實現。

演算法

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

示例

#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;
}

輸出

如果執行以上程式,它將生成以下輸出。

last 2 nodes of a list are :522 421

更新於:2019年8月22日

瀏覽量:117

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告