連結リスト続き

面倒くさくなって放置していた連結リストに、欠ていた関数を足してみた。

連続してノード削除を行うとSEGVが出ていたDeleteNodeは、消した後のカーソル（list->cursor）を後ろのノードに持っていっていたため、実はいちばんお尻のものを消そうとしたときにカーソルがNULLを指すことがあったのが原因だった。ノードを消した後のカーソルを前のノードに持ってくることもできるけど、たぶん、これは不自然。「abcde」とあって、「c」にカーソルがある時にdeleteキーを押したら、「c」が消えてカーソルは「d」の上に残る。というわけで、条件分岐して最後の1ノードを消すときには別処理とした。

もう1つ、カーソル位置にノードを追加する関数「InsertCursor」を付け加えた。関数名は「InsertNodeAtCursor」が正しいんじゃないのかとか思いつつ。

さらにもう1つ、リストを全部消すClearList関数。

void InsertCursor(List *list, Data *data) {
  if (list->head == NULL) {
    InsertHead(list, data);
  } else {
    Node *node, *new_next;
    node = list->head;
    while (node->next != list->cursor) {
      node = node->next;
    }
    // PRINT_CURSOR;
    new_next = node->next;
    node->next = list->cursor = AllocNode();
    SetNode(list->cursor, data, new_next);
  }
}

void DeleteNode(List *list) {
  Node *pre, *node = list->head;

  if (node == NULL) {
    return;
  } else if (node->next == NULL) {
    InitList(list);
    free(node);
  } else {
    while (1) {
      pre = node;
      node = node->next;
      if (node == list->cursor) {
        if (node->next == NULL) {
          list->cursor = pre;
          pre->next = NULL;
          free(node);
        } else {
          pre->next = node->next;
          list->cursor = node->next;
          free(node);
        }
        break;
      }
    }
  }
}

void ClearList(List *list) {
  Node *node, *target;
  node = list->head;
  while (node->next != NULL) {
    target = node;
    node = node->next;
    free(target);
  }
  free(node);
  InitList(list);
}

うーん、InsertCursorではポインタの付け替えが面倒で、new_nextという一時的なポインタ変数を用意したけど、これは不要な気がしてきた。

void InsertCursor(List *list, Data *data) {
  if (list->head == NULL) {
    InsertHead(list, data);
  } else {
    Node *node;
    node = list->head;
    while (node->next != list->cursor) {
      node = node->next;
    }
    list->cursor = AllocNode();
    SetNode(list->cursor, data, node->next);
    node->next = list->cursor;
  }
}

というふうに書き換えてもオッケーらしい。

何が分かりづらいかって、node->nextが、右辺にあって評価されるときには矢印の先っちょを表現しているのに、左辺に置いてデータの代入先を示すときには矢印の根元を表現しているってことじゃないかと思った。

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

#define PRINT_CURSOR printf("[cursor:%d]\n",list->cursor->data.size)

// Data structure definition

typedef struct {
  int x;
  int y;
  int size;
} Data;

typedef struct __node {
  Data data;
  struct __node *next;
} Node;

typedef struct {
  Node *head;
  Node *cursor;
} List;

// initialize and set objects

void InitList(List *list) {
  list->head = NULL;
  list->cursor = NULL;
}

Node *AllocNode(void) {
  return malloc(sizeof(Node));
}

void SetNode(Node *node, Data *data, Node *next) {
  node->data = *data;
  node->next = next;
}

// Print the list given

void PrintData(Data data) {
  //  printf("x, y: %d, %d\n", data.x, data.y);
  printf("size: %d\n", data.size);
}

void PrintList(List *list) {
  if (list->head == NULL) {
    puts("The list is empty");
  } else {
    Node *node;
    for (node = list->head; node != NULL; node = node->next) {
      PrintData(node->data);
    }
    PRINT_CURSOR;
    //    printf("[cursor:%d]\n",list->cursor->data.size);
  }
}

// list operations

void InsertHead(List *list, Data *data) {
  Node *node = list->head;
  list->head = list->cursor = AllocNode();
  SetNode(list->head, data, node);
}

void AppendTail(List *list, Data *data) {
  if (list->head == NULL) {
    InsertHead(list, data);
  } else {
    Node *node;
    for (node = list->head; node->next != NULL; node = node->next);

    node->next = list->cursor = AllocNode();
    SetNode(node->next, data, NULL);
  }
}

void InsertCursor(List *list, Data *data) {
  if (list->head == NULL) {
    InsertHead(list, data);
  } else {
    Node *node;
    node = list->head;
    while (node->next != list->cursor) {
      node = node->next;
    }
    list->cursor = AllocNode();
    SetNode(list->cursor, data, node->next);
    node->next = list->cursor;
  }
}

void DeleteNode(List *list) {
  Node *pre, *node = list->head;

  if (node == NULL) {
    return;
  } else if (node->next == NULL) {
    InitList(list);
    free(node);
  } else {
    while (1) {
      pre = node;
      node = node->next;
      if (node == list->cursor) {
        if (node->next == NULL) {
          list->cursor = pre;
          pre->next = NULL;
          free(node);
        } else {
          pre->next = node->next;
          list->cursor = node->next;
          free(node);
        }
        break;
      }
    }
  }
}

void ClearList(List *list) {
  Node *node, *target;
  node = list->head;
  while (node->next != NULL) {
    target = node;
    node = node->next;
    free(target);
  }
  free(node);
  InitList(list);
}

void SearchSize(List *list, int size) {
  if (list->head == NULL)
    return;
  else {
    Node *node;
    for (node = list->head; node != NULL; node = node->next) {
      if (node->data.size == size) {
        list->cursor = node;
        break;
      }
    }
  }
}

// ------------------------------

int main(void) {
  List l, *list;
  Data d, *data;
  list = &l; data = &d;
  int s, i;

  InitList(list);

  data->x = 320; data->y = 240;
  for (s = 100; s < 140; s += 5) {
    data->size = s;
    InsertHead(list, data);
  }
  for (i = 1; i <= 10; i++) {
    AppendTail(list, data);
    data->size++;
  }
  InsertHead(list, data);
  PrintList(list);

  SearchSize(list, 105);
  printf("\nfound this\n");
  PrintData(list->cursor->data);
  PRINT_CURSOR;

  data->size = 333;
  InsertCursor(list, data);
  PrintList(list);

  ClearList(list);

  for (i = 1; i <= 20; i++) {
    DeleteNode(list);
    PrintList(list);
  }
}