プログラミング 11 - Soft Forum P.C. Club

container

はじめに

配列などを宣言する場合に, int i[100];などとやっていました. では, 100を超えた場合どうするのでしょうか?

Containerはデータ構造であり, 動的に大きさを変更したりすることができます. Containerにはさまざまな種類があり, それぞれ特徴があります.

List

単方向(片方向) or 双方向 listを学び, list構造を作ることにします.

+-+    +-+
| | -> | |
+-+    +-+

ある要素が, 次の要素へのpointerをもっている, それによって前からたどっていくことができるデータ構造を一般にListと呼びます.

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

struct list {
  int val;
  struct list* next;
};

int main(int argc, const char **argv) {
  struct list *head = NULL, *p;
  int i;
  for (i = 0; i < 10; ++i) {
    p = (struct list*)malloc(sizeof(struct list));
    p->val = i;
    p->next = head;
    head = p;
  }
  p = head;
  while (p != NULL) {
    printf("%d\n", p->val);
    p = p->next;
  }
  return 0;
}

listの先頭(はじめの要素)をNULLにして, それにlistのitemをつないでいきます. mallocは動的なメモリの確保で, stdlib.hに定義されています.

stackの話で, 関数を抜けると変数などで確保されたメモリは消去されるといいました. では消去されない, かつ好きなだけの大きさをとるメモリを確保するにはどうするのでしょうか?

これは mallocを使って行われます.

p = (struct list*)malloc(sizeof(struct list));

struct list分の大きさのメモリを確保し, その先頭領域へのポインターがmallocから返って来るので, それをstruct list*にcastして使います.

ちなみに, mallocは寿命のないメモリ領域を確保しますが, 当然寿命がないということは, 使い終わったら自分で開放しないといけないということです.

free(p);

mallocで確保した領域はfreeで開放します.

freeはmallocで確保した領域にしか使ってはいけません. それ以外の領域に使ってしまった場合の動作は未定義です.

では先ほどのlistの要素をすべて開放して見ましょう.

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

struct list {
  int val;
  struct list* next;
};

int main(int argc, const char **argv) {
  struct list *head = NULL, *p;
  int i;
  for (i = 0; i < 10; ++i) {
    p = (struct list*)malloc(sizeof(struct list));
    p->val = i;
    p->next = head;
    head = p;
  }
  p = head;
  while (p != NULL) {
    printf("%d\n", p->val);
    free(p);
    p = p->next;
  }
  return 0;
}

freeが増えただけですね.

このようにnextへのポインターだけを持っているlistを単方向リストといいます. 単方向分しかもっていないということです.

一般に単方向リストは先頭をNULLにするこのような実装を行います.

listへの挿入を行ってみましょう.

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

struct list {
  int val;
  struct list* next;
};

void list_insert(int, int);

struct list* head = NULL;

int main(int argc, const char **argv) {
  struct list *p;
  int i;
  for (i = 0; i < 10; ++i) {
    list_insert(0, i);
  }
  p = head;
  while (p != NULL) {
    printf("%d\n", p->val);
    free(p);
    p = p->next;
  }
  return 0;
}

void list_insert(int num, int val) {
  struct list *p, *temp;
  p = head;
  while (num--) {
    p = p->next;
  }
  temp = (struct list*)malloc(sizeof(struct list));
  temp->val = val;
  temp->next = p;
  head = temp;
}

このように挿入をすることもできます. しかし, 見ればわかりますが, globalにheadを置いて書き換える, もしくは,

struct list* list_insert(struct list* p, int num, int val) {
  // ...
  return head;
}

として変更後のポインターをもらう, もしくはポインターのポインターを渡すなどもありますが, 基本的には管理用のinterfaceの下にlistを作るという形式が多く見られます.

Soft Forum P.C. Club