てけもぐ Tech 忘備録

リンクリストを再帰的に逆順実行する

対象読者

言語初学者

解決すること

リンクリストの再帰的な逆順実行

内容

以前ここにリンクリストを再帰的に逆順にする話を書いたのですけど、リンクリストの順番を変えずに各ノード(?)に対して何某かの関数を逆順に実行する例を書いておきます。忘れるので。。

#include<stdio.h>
#include<stdlib.h>

typedef struct Node Node;
struct Node {
  int value;
  Node *next;
}; 

Node *init_list(Node *n, int value){
  if(value < 0){
    return n;
  }
  Node *tn = malloc(sizeof(struct Node));
  tn->value = value;
  tn->next = n;
  return init_list(tn, --value);
}

void show_list(Node *n){
  if(!n){ return; }
  printf("%d ", n->value);
  show_list(n->next);
}

void fn_exec(Node *n){
  printf("@@ Do something for node of: '%d' @@\n", n->value);
}

void reverse_exec(Node *n, void (*fn)(Node *nn)){
  if(!n){
    return;
  } 
  // do recursive call first
  reverse_exec(n->next, fn);
  // then execute function on 'n' given before recursive call
  fn(n);
}

int main(){
  Node *n = init_list(NULL, 10);
  printf("## Given list: ");
  show_list(n);
  printf("\n");
  reverse_exec(n, fn_exec);
}

前のポストにも書きましたが、再帰呼び出しの前にやるか後にやるか、帰って来たノードに対して処理をするか、行きにもらったノードに処理をするか、そんなところが大事かなと。

Tags

#C