c言語双方向循環リスト番兵ノードについて

Question

現在双方向循環リストでrotateをする関数を書いてるのですが、-1である番兵ノードがどうしても出力されてしまい、番兵ノードを出力しない出力方法が思いつきません。
どなたかアドバイスを頂きたいです。

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

struct t_node {
  struct t_node *next;
  struct t_node *prev;
  int data;
};
struct t_node *first_node(int data) {
  struct t_node *head;
  head = malloc(sizeof(struct t_node *));
  head->next = head;
  head->prev = head;
  head->data = data;
}
void add_back(struct t_node *list, int data) {
  struct t_node *node;
  struct t_node *p = list;
  node = malloc(sizeof(struct t_node *));
  if (node == NULL)
    return;
  while (p->next != list) {
    p = p->next;
  }
  p->next->prev = node;
  p->next = node;
  node->prev = p;
  node->data = data;
  node->next = list;
}
void print(struct t_node *head) {
  struct t_node *tmp;
  if (head == NULL)
    return;
  tmp = head->next;
  printf("tmp data is %d\n", tmp->data);//5
  printf("head data is %d\n", head->data);//1
  while (tmp != head) {
    printf("%d  ", tmp->data);
    tmp = tmp->next;
  }
  printf("%d", tmp->data);
  printf("\n");
}
void swap(struct t_node *n1, struct t_node *n2) {
  int tmp;
  tmp = n1->data;
  n1->data = n2->data;
  n2->data = tmp;
}
void rotate(struct t_node *list_head) {
  struct t_node *change_list_head_next;
  struct t_node *head;
  struct t_node *last;
  first_node(0);
  change_list_head_next = list_head->next;
  swap(change_list_head_next, list_head);
  head = list_head->next;
  last = head->prev;
  print(head->next);
  return;
}
int main(void) {
  struct t_node *list_head;
  struct t_node *change_list_head_next;
  list_head = NULL;
  list_head = first_node(-1);
  add_back(list_head, 3);
  add_back(list_head, 1);
  add_back(list_head, 5);
  print(list_head);
  rotate(list_head);
}

出力結果
-1を消したい。

3  1  5  -1
5  3  -1  1

Comments

[ozwk]

実行するとコアダンプ(Illegal instruction (core dumped))が発生して出力結果を得るどころではありません。
おそらくコードを貼り間違えていますので修正してください

[melian]

ところで、memory sanitizer 付きでコンパイルして実行すると、
head = malloc(sizeof(struct t_node *));
と
node = malloc(sizeof(struct t_node *));
の直後で heap buffer overflow が発生します。理由は、、明白ですよね。

[episteme]

関数:first_node() が t_node* を返していません。

Answer 1

折角の双方向リストなのですから、 head->prev を使ったり、循環をノードの(先頭と最後で)移動で行ったりしては如何でしょうか。
(というより、そうしないと双方向リストを使う意味が無いのでは。)

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

typedef struct t_node {
  struct t_node *next;
  struct t_node *prev;
  int data;
} Node;

void initPointers(Node *node) {
  node->next = node;
  node->prev = node;
}

Node *createNode(int data) {
  Node *node = malloc(sizeof(Node));
  if(node == NULL) return NULL; //error
  initPointers(node);
  node->data = data;
  return node;
}
//最後に追加
void addLast(Node *head, Node *node) {
  Node *last = head->prev;
  node->prev = last;
  node->next = head;
  last->next = node;
  head->prev = node;
}
//先頭に追加
void addFirst(Node *head, Node *node) {
  Node *first = head->next;
  node->prev = head;
  node->next = first;
  head->next = node;
  first->prev = node;
}
//最後を削除
Node *removeLast(Node *head) {
  if(head->prev == head) return NULL;
  Node *last = head->prev;
  head->prev = last->prev;
  last->prev->next = head;
  initPointers(last);
  return last;
}
//最初を削除
Node *removeFirst(Node *head) {
  if(head->next == head) return NULL;
  Node *first = head->next;
  head->next = first->next;
  first->next->prev = head;
  initPointers(first);
  return first;
}

void print(Node *head) {
  for(Node *p = head->next; p != head; p = p->next) {
    printf("%d  ", p->data);
  }
  printf("\n");
}

void rotateRight(Node *head) {
  Node *last = removeLast(head);
  if(last != NULL) addFirst(head, last);
}
void rotateLeft(Node *head) {
  Node *first = removeFirst(head);
  if(first != NULL) addLast(head, first);
}

int main(void) {
  Node *head = createNode(-1);

  addLast(head, createNode(3));
  addLast(head, createNode(1));
  addLast(head, createNode(5));
  print(head);

  //rotateLeft(head);
  rotateRight(head);
  print(head);
}

3  1  5  
5  3  1  

---

ikedas さんご提案の構造にしてみました。テストも追加。

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

typedef struct t_node {
  struct t_node *next;
  struct t_node *prev;
  int data;
} Node;

Node *createNode(int data) {
  Node *node = malloc(sizeof(Node));
  if(node == NULL) return NULL; //error
  node->next = NULL;
  node->prev = NULL;
  node->data = data;
  return node;
}
//最後に追加
void addLast(Node **head, Node *node) {
  if(*head == NULL) { //データ無し
    *head = node;
    node->next = node;
    node->prev = node;
  } else {
    node->next = *head;
    node->prev = (*head)->prev;
    node->next->prev = node;
    node->prev->next = node;
  }
}

void print(Node *head) {
  Node *p = head;
  if(p != NULL) {
    do {
      printf("%d  ", p->data);
    } while((p = p->next) != head);
  }
  printf("\n");
}

void rotateRight(Node **head) {
  if(*head != NULL) *head = (*head)->next;
}
void rotateLeft(Node **head) {
  if(*head != NULL) *head = (*head)->prev;
}

int main(void) {
  Node *head = NULL;

  addLast(&head, createNode(3));
  addLast(&head, createNode(1));
  addLast(&head, createNode(5));
  print(head);

  rotateRight(&head); //右へ1回
  print(head);

  addLast(&head, createNode(7)); //7を追加して
  print(head);

  rotateLeft(&head); //左へ2回
  rotateLeft(&head);
  print(head);
}

3  1  5  
5  3  1  
5  3  1  7  
1  7  5  3  

Comments

[ikedas]

というか循環リストなので、リストを変更しなくても``head->prev``や``head->next``が求めるものになっているとも思います。

[jimbe]

head が循環の中に含まない、 3,1,5 のノードだけで循環するようにすれば、 head の位置をずらすだけになりますね。

Answer 2

番兵ノードを設ける理由は、リスト上のノードを渡り歩く際にリスト終端の判定を簡単にしたりするためだと思います。

しかしご提示のコードでは、各関数のループの条件がadd_back()ではp->next != list、print()ではtmp != headとなっていて、関数の引数として与えられたノードに達するとループが停止するようになっています。このように停止すべきノードが毎回与えられるのならば、番兵のような特別なノードはいらないですよね。

つまり、最初にfirst_node()で作成するノードも番兵ノードではなく普通のノードだと考えられますから、出力しないようにする必要はないです。

---

ご質問の点にのみ回答しました。現在のコードを上記のように変えただけで意図した通りの動作をするのかどうかについては確認していません。

Answer 3

void print(struct t_node *head) {
  struct t_node *tmp;
  if (head == NULL)
    return;
  tmp = head->next;
  printf("tmp data is %d\n", tmp->data);//5
  printf("head data is %d\n", head->data);//1
  while (tmp != head) {
    printf("%d  ", tmp->data);
    tmp = tmp->next;
  }
  printf("%d", tmp->data); // ここでもprintfするのはなぜ?
  printf("\n");
}

Comments

[pocomi]

printf("%d", tmp->data); // ここでもprintfするのはなぜ?
出力結果にある最後の1が出力されなくなってしまうのでprintfで出力しています。