（答案提出）C言語教室 第20回 - 双方向リスト

リスト操作がちょっとわかってきたような気がします。

（冒頭の写真は、私が大好きなフェルメールによる『デルフトの眺望』。
船が行ったり来たりするイメージが、双方向リストっぽいかなって。）

課題

・リストの最後に要素を追加する関数を書きなさい。
・リストの先頭の要素を削除する関数を書きなさい。
・n番目の要素を返す関数を書きなさい。
・要素の中に指定した値が含まれるかを返す関数を書きなさい。

https://note.com/kazushinakamura/n/n21eed5016ba8

答案 - 課題

Nodeの定義

typedef struct node {
  int val;
  struct node *next;
  struct node *prev;
} Node;

pointerの定義

  Node *head = NULL;
  Node *tail = NULL;

Lesson20−1 リストの最後に要素を追加する関数

void append_node(Node **head, Node **tail, int val) {
  Node *new_node = (Node *)malloc(sizeof(Node));
  new_node->val = val;
  new_node->next = NULL;
  *tail = new_node;

  if (*head == NULL) {
    *head = new_node;
    new_node->prev = NULL;
      
  } else {
    Node *current_node = *head;
    while (current_node->next != NULL) {
        current_node = current_node->next;
    }
    current_node->next = new_node;
    new_node->prev = current_node;
  }
}

lesson19-2に少し手を加えました。
リストの最後にnodeを追加するので、常に*tailを更新することになります。
また、追加したnodeのnextは、常にNULLです。

リストが空だった場合には、*headは新しく追加したnodeです。
また、追加したnodeのprevとnextはNULLです。

リストが既に存在していた場合、既存の最終nodeのnextと、新しく追加したnodeのprevとnextを更新します。

Lesson20−2 リストの先頭の要素を削除する関数

void delete_first_node(Node **head, Node **tail) {
  Node *current_node = *head;
    
  if (current_node->next == NULL){
    *head = NULL;
    *tail = NULL;
        
  } else {
    Node *next_node = current_node->next;
    *head = next_node;
    next_node->prev = NULL;
  }
    
  free(current_node);
}

lesson19-3に少し手を加えました。

nodeがひとつだけだった場合には、*headと*tailはNULLです。
既存のnodeを解放します。

nodeが２つ以上存在していた場合、*headと、既存の２番目のnodeのprevを更新して、最初のnodeを解放します。

Lesson20−3 n番目の要素を返す関数

int get_Nth_node(Node *head, int seq) {
  Node *current_node = head;

  for (int i = 0; i < seq; i++) {
    if (current_node == NULL) return -1;
    current_node = current_node->next;
  }

  return current_node->val;
}

lesson19-4が、基本的にそのままです。

（追記：このコードにはバグがあります。詳しくは、解答 & 再提出を参照）

Lesson20−4 要素の中に指定した値が含まれるかを返す関数

int search_val_in_node(Node *head, int srch_val) {
  int cnt = 0;
  int rtn = -1;

  Node *current_node = head;

  while (current_node->next != NULL) {
    if (current_node->val == srch_val) {
      rtn = cnt;
    }
    cnt++;
    current_node = current_node->next;
  }

  return rtn;
}

lesson19-1に手を加えました。
指定された値を持つnodeが見つかった場合には、何番目のnodeであったかを返します。見つからない場合は-1を返します。
（同じ値を持つnodeが複数あることは想定外。最後に見つけたものが何番目であったかを返します。）

実行結果

上記の記事のベースとなったコードはこちら---> lesson20.c
 Ayumiさんからの指摘に備えて、今回はclangでもコンパイルして警告を最小限となることを確認済みです（笑

lesson20.c

4.18 KB

ファイルダウンロードについて

ダウンロード

Lesson20-1: リストの最後に要素を追加する関数
List(head->tail): 10 20 30 40 50 
List(tail->head): 50 40 30 20 10 
the number of elements in the list : 5

Lesson20-2: リストの先頭の要素を削除する関数
List(head->tail): 20 30 40 50 
List(tail->head): 50 40 30 20 
the number of elements in the list : 4

Lesson20-3: n番目の要素を返す関数
0th val in the list : 20
1st val in the list : 30
2nd val in the list : 40
3rd val in the list : 50

Lesson20-4: 要素の中に指定した値が含まれるかを返す関数(見つからなければ−１を返す)
Seaching value 40 is in 2nd node
Seaching value 90 is in -1st node

ブラウザで動く C言語実行環境

後記

双方向リストが機能していることを証明するために、順方向と逆方向から全件出力してみました。

実際例として双方向リストが何に使えるか、、、イメージがわかない。

蛇足

void ordinal_number(int num, char *buf) {
  int len = 0;

  sprintf(buf, "%d", num);
  len = strlen(buf);

  if ((len > 1) && (buf[len - 2] =='1')) {
    strcat(buf, "th"); 
  
  } else {

    switch (buf[len - 1]) {
      case '1': strcat(buf, "st"); break;
      case '2': strcat(buf, "nd"); break;
      case '3': strcat(buf, "rd"); break;
      default : strcat(buf, "th");
    }
  }
}

序数を正しく表示するための関数を追加してみました。
これまでの答案では無条件に"th"を付加してましたが、妙に目について。

1 --> 1st, 2 --> 2nd, 3 --> 3rd, 4 --> 4th,,,
但し、11 --> 11th, 12 --> 12th, 13 --> 13th

解答 & 再提出

ここまで読んでいただき、有り難うございました。