【C】基本的なアルゴリズムを使用した実装例

10年以上前に下記書籍で C言語の基本的なアルゴリズムの実装を学習したときのコードです。

Cプログラミングとデータ構造

 
2018年現在の今となっては古い本ですが、単方向リンクリスト、双方向リンクリスト、クイックソートなどなど基本的なアルゴリズムですので、古くなることはありません。
本書のサンプルコードは流用・応用しやすいコードが載せられており、中古で 200 円程度で買えるのであれば即買いで良いかと思います。
 

 

配列を使った連結リスト

/*
 * Cプログラミングとデータ構造(9.8)
 * 配列を使った連結リストのサンプルプログラム
 * 整数値をノードのデータ部、ポインタ部に次ノードの要素番号を持つ
 * ニ次元の整数型配列を使った連結リスト構造へデータを追加する。
 * ただし、追加されるデータを記憶するノードはその値が昇順になる位
 * 置へ追加または挿入され、同じ値を持つノードが存在する場合はそれ
 * を削除する
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define LIMIT   11

int
main()
{
  /* ノード用配列. [list[0][n]:データ、list[1][n]:ポインタ */
  int                 list[2][LIMIT];
  int                 indt = 0;    /* データ入力用 */
  int                 pos = 0;    /* ノード探索用指標 */
  int                 store = 0;    /* 配列使用位置記憶用の指標 */

  list[1][0] = 99;   /* 探索用指標を更新 */
  store = 1;    /* 配列使用位置記憶用の指標を初期化 */

  while (1)
  {
    printf("Data -> ");
    scanf("%d", &indt);
    if (indt < 0)
    {
      break;
    }
    pos = 0;

    while (1)
    {
      if (list[1][pos] == 99)  /* リスト終端? */
      {
        if (store >= LIMIT)  /* バッファは一杯か */
        {
          printf("Buffer Full\n");
        }
        else
        {
          list[0][store] = indt;
          list[1][store] = 99;
          list[1][pos] = store;
          store++;
        }
        break;
      }
      else if (list[0][list[1][pos]] == indt)  /* 等しいデータあり? */
      {
        list[1][pos] = list[1][list[1][pos]];   /* ノード削除処理 */
        store--;
        break;
      }
      else if (indt < list[0][list[1][pos]])
      {
        if (store >= LIMIT)
        {
          printf("Buffer Full\n");    /* バッファは一杯か? */
        }
        else    /* ノード挿入処理 */
        {
          list[0][store] = indt;
          list[1][store] = list[1][pos];
          list[1][pos] = store;
          store++;
        }
        break;
      }
      else
      {
        pos = list[1][pos]; /* 探索用指標を更新 */
      }
    }
    /* リストデータの表示 */
    if (list[1][0] == 99)    /* 有効なノードなし? */
    {
      printf("No data\n");
    }
    else
    {
      printf("list data -> ");
      pos = 0;
      do
      {
        pos = list[1][pos]; /* 次のノードへ移動 */
        printf("%d ", list[0][pos]);
      } while (list[1][pos] != 99);
    }
    printf("\n");
  }

  return  0;
}

 

バランスした2分木を構築する

/*
 * Cプログラミングとデータ構造(9.17)
 * バランスした2分木を構築するサンプル
 * a(A) : ノードの追加
 * b(B) : 木の再構築
 * v(V) : 木の視覚化表示
 * i(I) : ノードの初期化
 * q(Q) : プログラムの終了
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define     LIMIT       10  /* 処理できるデータ数の上限 */

typedef struct  node    NODE;
struct  node
{
  int           data;     /* key部分 */
  struct node * left;     /* 左の子ノードへのポインタ */
  struct node * right;    /* 右の子ノードへのポインタ */
};


int  add_tree(struct node ** pp, int dt, int cnt);
NODE    * build_tree(int stack[], int n);
void save_tree(NODE * p, int stack[]);
void print_tree(struct node * p);
NODE    * free_tree(NODE * p);



int
main()
{
  struct  node        head;
  struct  node     ** ppt;        /* 戻り値記憶用(ノード型ポインタのポインタ) */
  int                 ret;        /* 戻り値記憶用 */
  int                 buff[LIMIT];/* 再構築用バッファ */
  int                 indt = 0; /* キーデータ入力用 */
  int                 count = 0; /* ノード数カウント用 */
  int                 status;
  char                cmd[2];

  cmd[0] = ' ';
  head.left = head.right = NULL;

  while (cmd[0] != 'q' && cmd[0] != 'Q')
  {
    printf("Command ? ");
    scanf("%s", cmd);

    switch (cmd[0])
    {
    case 'a':
    case 'A':
      printf("Append data -> ");
      scanf("%d", &indt);
      ret = add_tree(&(head.left), indt, count);    /* 追加処理 */
      if (ret == 0)    /* 件数上限? */
      {
        fprintf(stderr, "Limit of data count\n");
      }
      else if (ret == -1)
      {
        fprintf(stderr, "Memory allocation Error\n");
      }
      else if (ret == -2)
      {
        fprintf(stderr, "Duplicate key Error\n");
      }
      else
      {
        count = ret;    /* ノード数カウンタ更新 */
      }
      break;
    case 'b':
    case 'B':
      if (head.left == NULL)   /* 木は空か? */
      {
        printf("Tree empty\n");
      }
      else
      {
        save_tree(head.left, buff); /* 木 → バッファ */
        head.left = free_tree(head.left);       /* 木の初期化 */
        head.left = build_tree(buff, count);    /* 再構築 */
        printf("Rebuild a tree\n");
      }
      break;
    case 'v':
    case 'V':
      if (head.left == NULL)
      {
        printf("Tree empty\n");
      }
      else
      {
        print_tree(head.left);  /* 木の視覚化表示 */
      }
      break;
    case 'i':
    case 'I':
      if (head.left == NULL)
      {
        printf("Tree empty\n");
      }
      else
      {
        head.left = free_tree(head.left);   /* 木の初期化 */
        count = 0;
        printf("Tree initialized\n");
      }
      break;
    default:
      break;
    }
    printf("\n");
  }

  return 0;
}

/* 2分木へデータを追加する */
int
add_tree(struct node ** pp, int dt, int cnt)
{
  struct  node    * ptn;
  if (cnt >= LIMIT)
  {
    printf("cnt(%d) > LIMIT(%d)\n", cnt, LIMIT);
    return  0;
  }
  else
  {
    while (1)
    {
      if (*pp == NULL)
      {
        ptn = malloc(sizeof(NODE)); /* 新ノード確保 */
        if (ptn == NULL)
        {
          fprintf(stderr, "ERROR: malloc at add_tree\n");
          return  -1;
        }
        else
        {
          ptn->data = dt;                 /* Keyデータ格納 */
          ptn->left = ptn->right = NULL;  /* 葉ノードとする */
          *pp = ptn;                      /* 親ノードとリンク */
          return  cnt + 1;                  /* ノード数を返す */
        }
      }
      else if ((*pp)->data == dt)  /* 同じKey値? */
      {
        return  -2;
      }
      else
      {
        if (dt < (*pp)->data)        /* 左部分木か? */
        {
          pp = &((*pp)->left);    /* 左へ移動 */
        }
        else
        {
          pp = &((*pp)->right);   /* 右へ移動 */
        }
      }
    }
  }
}

/* 昇順に並べられた整数の並びからバランスした木を構築する */
NODE    *
build_tree(int stack[], int n)
{
  static  int pos = 0;
  int         nleft;
  int         nright;
  NODE    *   p;

  if (n == 0)
  {
    return  NULL;
  }
  else
  {
    nleft = (n - 1) / 2;          /* 左部分木のノード数を求める */
    nright = n - nleft - 1;    /* 右部分木のノード数を求める */
    p = malloc(sizeof(NODE)); /* ノード領域を確保 */
    if (!p)
    {
      fprintf(stderr, "Memory allocation error\n");
      exit(-1);
    }
    p->left = build_tree(stack, nleft); /* 左部分木の構築 */
    p->data = stack[pos++];             /* key値格納 */
    p->right = build_tree(stack, nright);/* 右部分木の構築 */
    return  p;  /* 作成したノードアドレスを返す */
  }
}

/* 2分木を中間順序で巡回し、ノードの Key値を巡回順に一次元配列に格納する */
void
save_tree(NODE * p, int stack[])
{
  static  int cnt = 0;    /* 格納位置を記憶するための変数 */
  if (p)   /* 節点ノード */
  {
    save_tree(p->left, stack);      /* 左部分木へ移動 */
    stack[cnt] = p->data;          /* key値格納 */
    cnt++;
    save_tree(p->right, stack);     /* 右部分木へ移動 */
  }
}

/* 2分木を視覚化して表示する */
void
print_tree(struct node * p)
{
  static  int indent;     /* 字下げ数記憶用 */
  int         i;

  if (p)                   /* ノードあり? */
  {
    indent += 6;       /* 字下げ数 +6 */
    print_tree(p->right);
    for (i = 6; i < indent; i++)
    {
      printf(" ");    /* 字下げ */
    }
    printf("%6d\n", p->data);
    print_tree(p->left);
    indent -= 6;
  }
}

/* 2分木のノードを後行順序で巡回しながら木を初期化する */
NODE    *
free_tree(NODE * p)
{
  if (p)
  {
    free_tree(p->left); /* 左部分木へ再帰的に移動 */
    free_tree(p->right);/* 右部分木へ再帰的に移動 */
    free(p);
  }
  return  (NODE *)NULL;
}

 

重連結・循環リスト構造

/*
 * Cプログラミングとデータ構造(9.12)
 * 重連結・循環リスト構造のサンプルプログラム
 * a(A) : ノードの追加
 * s(S) : ノードの探索
 * i(I) : ノードの挿入
 * d(D) : ノードの削除
 * p(P) : リストデータと件数の表示
 * c(C) : リストの初期化
 * q(Q) : プログラムの終了
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct  node
{
  int           data;
  struct node * prev;
  struct node * next;
};

/* algorithm_doublelist_cycle.c */
int main();
int append(int dt, struct node * p_h);
struct node * search(int dt, struct node * p_h);
int insert(int dt, int ldt, struct node * p_h);
int delete(int ldt, struct node * p_h);
int print(struct node * p_h);
void initialize(struct node * p_h);

int
main()
{
  struct  node        head;
  struct  node      * p_ret;
  char                cmd[2];
  int                 indt = 0;
  int                 listdt = 0;
  int                 ret = 0;

  cmd[0] = ' ';
  head.prev = head.next = &head;     /* ヘッドノードの初期化 */

  while (cmd[0] != 'q' && cmd[0] != 'Q')
  {
    printf("Command ? ");
    scanf("%s", cmd);

    switch (cmd[0])
    {
    case 'a':
    case 'A':
      printf("Append data -> ");
      scanf("%d", &indt);
      ret = append(indt, &head);
      if (ret == -1)
      {
        fprintf(stderr, "Memory Allocation Error\n");
      }
      break;
    case 's':
    case 'S':
      printf("Search data -> ");
      scanf("%d", &indt);
      p_ret = search(indt, &head);
      if (p_ret == NULL)
      {
        printf("Search Error\n");
      }
      else
      {
        printf("Node address = %p\n", p_ret);
        printf("List Data    = %d\n", p_ret->data);
      }
      break;
    case 'i':
    case 'I':
      printf("Insert data -> ");  /* 挿入データ入力 */
      scanf("%d", &indt);         /* 挿入先ノードの入力 */
      printf("List node data -> ");
      scanf("%d", &listdt);
      ret = insert(indt, listdt, &head);
      if (ret == -1)
      {
        printf("Memory Allocation Error\n");
      }
      else if (ret == -2)
      {
        printf("Insert Node Not Found\n");
      }
      break;
    case 'd':
    case 'D':
      printf("Delete data -> ");
      scanf("%d", &indt);
      ret = delete(indt, &head);
      if (ret == -1)
      {
        printf("Delete Node Not Found\n");
      }
      break;
    case 'p':
    case 'P':
      printf("List Data = ");
      ret = print(&head);
      printf("\nNode Count = %d\n", ret); /* ノード数表示 */
      break;
    case 'c':
    case 'C':
      initialize(&head);
      printf("List Initialized\n");
      break;
    default:
      break;
    }
    printf("\n");
  }

  return 0;
}

int
append(int dt, struct node * p_h)
{
  struct  node  * p_new;

  p_new = malloc(sizeof(struct node));    /* 追加ノード確保 */
  if (!p_new)
  {
    return  -1;
  }
  else
  {
    p_new->data = dt;          /* 新ノードへデータ格納 */
    p_h->prev->next = p_new;       /* 現終端ノードの後ポインタを新ノードへリンク */
    p_new->prev = p_h->prev;   /* ヘッドノードの前ポインタを新ノードへコピー */
    p_h->prev = p_new;       /* ヘッドノードの前ポインタで新ノードをリンク */
    p_new->next = p_h;         /* 新ノードの後ポインタでヘッドノードをリンク */
    return  0;
  }
  return 0; /* not reached */
}

struct node *
  search(int dt, struct node * p_h)
{
  struct  node    * p_s;

  p_s = p_h->next;
  while (p_s != p_h)           /* ヘッドノードでなければループ */
  {
    if (dt == p_s->data)     /* 目的のノード */
    {
      break;
    }
    else
    {
      p_s = p_s->next;   /* p_sを次のノードへ移動 */
    }
  }
  if (p_s == p_h)
  {
    return  NULL;           /* ヘッドノードまで一巡したか */
  }
  else
  {
    return  p_s;            /* 目的ノードのアドレスを返す */
  }
  return p_s; /* not reached */
}

int
insert(int dt, int ldt, struct node * p_h)
{
  struct  node      * p_new;

  p_h = search(ldt, p_h);       /* 挿入位置ノード探索 */
  if (p_h == NULL)
  {
    return -2;
  }
  else
  {
    p_new = malloc(sizeof(struct node));
    if (!p_new)
    {
      return -1;
    }
    else
    {
      p_new->data = dt;                /* 新ノードへデータコピー */
      p_new->next = p_h->prev->next;  /* 新ノード後ポインタ */
      p_new->prev = p_h->prev;         /* 新ノード前ポインタ */
      p_new->prev->next = p_new;             /* 一つ前になるノード後ポインタ */
      p_h->prev = p_new;             /* 目的ノード前ポインタ */
      return 0;
    }
  }
  return 0;
}

int
delete(int ldt, struct node * p_h)
{
  p_h = search(ldt, p_h);   /* 削除ノード探索 */
  if (p_h == NULL)    /* 目的ノードなし */
  {
    return -1;
  }
  else
  {
    p_h->prev->next = p_h->next;  /* p_h の前ノードの後ポインタ */
    p_h->next->prev = p_h->prev;   /* p_h の後ノードの前ポインタ */
    free(p_h);                      /* p_h の領域を解放 */
    return 0;             /* 番兵ノードのアドレスを返す */
  }
  return 0;
}

int
print(struct node * p_h)
{
  struct  node    * p_s = NULL;
  int               i = 0;

  p_s = p_h->next;
  while (p_s != p_h)
  {
    printf("%d ", p_s->data);
    p_s = p_s->next;
    i++;
  }
  return i;
}

void
initialize(struct node * p_h)
{
  struct node     * p_s;
  struct node     * p_ss;

  p_s = p_h->next;
  while (p_s != p_h)               /* 終端ノードでなければループ */
  {
    p_ss = p_s->next;
    free(p_s);
    p_s = p_ss;
  }
  p_h->prev = p_h->next = p_h;   /* ヘッドノードと番兵ノードをリンク */
}

 

重連結・循環リストを使ったキュー構造のサンプルプログラム

/*
 * Cプログラミングとデータ構造(9.13)
 * 重連結・循環リストを使ったキュー構造のサンプルプログラム
 * (配列を環状に使うアルゴリズム)
 * e(E) : データの追加(EnQueue)
 * d(D) : データの削除(DeQueue)
 * i(I) : キューの初期化
 * o(O) : キューデータと件数の表示
 : q(Q) : プログラムの終了
 */
 /*=========*/
 /* include */
 /*=========*/
#include <stdio.h>
#include <stdlib.h>

/*========*/
/* define */
/*========*/

/*========*/
/* struct */
/*========*/

struct  node
{
  int             data;
  struct  node  * left;
  struct  node  * right;
};

/*==========*/
/* function */
/*==========*/
int enqueue(int dt, struct node * p_h);
int dequeue(struct node * p_h);
int print(struct node * p_h);
void initialize(struct node * p_h);

/*===============*/
/* routine start */
/*===============*/
int
main()
{
  struct  node    head;   /* ヘッドノード */
  int             ret = 0;
  char            cmd[2] = { ' ', '\0' };
  int             indt = 0;     /* input data */
  head.left = head.right = &head; /* ヘッドノードの初期化 */

  while (cmd[0] != 'q' && cmd[0] != 'Q')
  {
    printf("Command ? ");
    scanf("%s", cmd);
    switch (cmd[0])
    {
    case    'e': /* エンキュー */
    case    'E': /* エンキュー */
      printf("EnQueue Data -> ");
      scanf("%d", &indt);
      ret = enqueue(indt, &head); /* 追加処理 */
      if (ret == -1)
      {
        printf("memory allocation error\n");
      }
      break;
    case    'd': /* デキュー */
    case    'D': /* デキュー */
      ret = dequeue(&head);
      if (ret == -1)
      {
        printf("Queue buffer Empty\n");
      }
      else
      {
        printf("DeQueue data = %d\n", ret);
      }
      break;
    case 'i': /* キューをInitialize */
    case 'I': /* キューをInitialize */
      initialize(&head);
      printf("Queue Initialized\n");
      break;
    case 'p': /* キューを表示する */
    case 'P': /* キューを表示する */
      ret = print(&head);
      if (ret == 0)
      {
        printf("Queue buffer Empty\n");
      }
      else
      {
        printf("Queue count = %d\n", ret);
      }
      break;
    }
    printf("\n");
  }
  return 0;
}

/* キューへ1件追加 */
int
enqueue(int dt, struct node * p_h)
{
  struct  node    * p_new = NULL;

  p_new = malloc(sizeof(struct node)); /* 追加ノード確保 */

  if (p_new == NULL)
  {
    return -1;
  }
  else
  {
    p_new->data = dt;       /* 新ノードへデータ格納 */
    p_h->left->right = p_new;    /* 現終端ノードの右ポインタを新ノードへリンク */
    p_new->left = p_h->left;/* ヘッドノードの左ポインタを新ノードへコピー */
    p_h->left = p_new;    /* ヘッドノードの左ポインタで新ノードをリンク */
    p_new->right = p_h;      /* ヘッドノードの右ポインタで新ノードをリンク */
    return  0;
  }
}

/* キューから1件削除 */
int
dequeue(struct node * p_h)
{
  int dqdt;

  if (p_h->right == p_h)   /* キューリストは空? */
  {
    return  -1;
  }
  else
  {
    p_h = p_h->right;   /* 第一(dequeue)ノードへ p_h を移動 */
    dqdt = p_h->data;    /* p_h が指すノードのデータ部を dqdt に得る */
    p_h->left->right = p_h->right;   /* p_h の左ノードの右ポインタ */
    p_h->right->left = p_h->left;    /* p_h の右ノードの左ポインタ */
    free(p_h);                          /* p_h の領域を解放 */
    return  dqdt;                       /* dequeueデータを返す */
  }
}

/* ヘッドノードを除くリストに登録されている全てのキューデータを表示 */
int
print(struct node * p_h)
{
  struct  node    * p_s = NULL;
  int               i = 0;

  p_s = p_h->right;       /* 第一ノードのアドレスを p_h に得る */
  while (p_s != p_h)       /* 終端ノードでなければループ */
  {
    printf("%d\n", p_s->data);  /* データ部表示 */
    p_s = p_s->right;           /* p_h を次のノードのポインタ部へ移動 */
    i++;
  }
  return  i;
}


/* キューリストを初期化する */
void
initialize(struct node * p_h)
{
  struct  node    * p_s = NULL;
  struct  node    * p_ss = NULL;

  p_s = p_h->right;   /* 第一ノードのアドレスを p_s にセット */
  while (p_s != p_h)       /* 終端ノードでなければループ */
  {
    p_ss = p_s->right;  /* p_s の次のノードのアドレスを p_ss に得る */
    free(p_s);          /* p-s のメモリ領域を解放 */
    p_s = p_ss;         /* p_s を次のノードへ移動 */
  }
  p_h->left = p_h->right = p_h;   /* ヘッドの左右ポインタにヘッドのアドレスをセット */
}

 

年齢帯別人口表を多重連結リスト構造を使って表現したサンプルプログラム

/* 
 * Cプログラミングとデータ構造(9.15)
 * 年齢帯別人口表を多重連結リスト構造を使って表現したサンプルプログラム
 * l(L) : ファイルからデータを読み込む
 * s(S) : ファイルへデータを書き込む
 * a(A) : 表へのデータ追加
 * m(M) : 表データの修正
 * d(D) : 表からのデータ削除
 * p(P) : 表データと件数の表示
 * c(C) : 縦横集計と集計結果の表示
 * i(I) : 表の初期化
 * q(Q) : プログラム終了
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define     WIDE    10
#define     HIGH    10

/* 地区ヘッドのテンプレート */
struct  t_tiku
{
    int               no;
    struct  node    * next;
};

/* 年齢帯ヘッドのテンプレート */
struct  t_nen
{
    int no;
    struct  node    *next;
};

/* データノードの構造 */
struct  node
{
    int data;
    struct  t_nen   * p_hn;
    struct  t_tiku  * p_ht;
    struct  node    * p_nn;
    struct  node    * p_nt;
};

int load(struct t_tiku h_t[], struct t_nen h_n[], char * p_fname);
int save(struct t_tiku h_t[], struct t_nen h_n[], char * p_fname);
int append(struct t_tiku h_t[], struct t_nen h_n[], int tno, int nno, int dt);
int modify(struct t_tiku h_t[], struct t_nen h_n[], int tno, int nno, int dt);
int delete(struct t_tiku h_t[], struct t_nen h_n[], int tno, int nno);
int print(struct t_tiku h_t[], struct t_nen h_n[]);
void calculate(struct t_tiku h_t[], struct t_nen h_n[]);
void initialize(struct t_tiku h_t[], struct t_nen h_n[]);
int cnv_age(int age);

int
main()
{
    struct  t_tiku  head_t[HIGH];
    struct  t_nen   head_n[WIDE];
    char    cmd[2];
    char    fname[16];      /* ファイル名入力用 */
    int     in_tno  = 0;    /* 地区番号入力用 */
    int     in_nno  = 0;    /* 年齢帯番号入力用 */
    int     in_dt   = 0;    /* データ入力用 */
    int     ret     = 0;
    int     i       = 0;

    cmd[0] = ' ';

    /* 地区ヘッドの初期化 */
    for(i = 0; i < HIGH; i++)
    {
        head_t[i].no    = i;
        head_t[i].next  = NULL;
    }
    /* 年齢帯ヘッドの初期化 */
    for(i = 0; i < HIGH; i++)
    {
        head_n[i].no    = i;
        head_n[i].next  = NULL;
    }

    while(cmd[0] != 'q' && cmd[0] != 'Q')
    {
        printf("Command ? ");
        scanf("%s", cmd);

        switch(cmd[0])
        {
        case 'l':
        case 'L':
            printf("Load file name -> ");
            scanf("%s", fname);
            ret = load(head_t, head_n, fname);  /* 読込み */
            if(ret == -1)
            {
                printf("File open error\n");    /* ファイルオープン異常 */
            }
            else if(ret == -2)                  /* 登録異常 */
            {
                printf("Append error\n");
            }
            break;
        case 's':
        case 'S':
            printf("Save file name -> ");
            scanf("%s", fname);
            ret = save(head_t, head_n, fname);
            if(ret == -1)
            {
                printf("File open error\n");
            }
            break;
        case 'a':
        case 'A':
            printf("Block -> ");    /* 地区番号入力 */
            scanf("%d", &in_tno);
            printf("Age   -> ");    /* 年齢入力 */
            scanf("%d", &in_nno);
            in_nno = cnv_age(in_nno);   /* 年齢帯番号へ変換 */

            printf("Population -> ");
            scanf("%d", &in_dt);
            ret = append(head_t, head_n, in_tno, in_nno, in_dt);    /* 人口を追加 */
            if(ret == -1)
            {
                printf("Memory allocation error\n");
            }
            else if (ret == -2)
            {
                printf("Block or age number error\n");
            }
            else if(ret == -3)
            {
                printf("Node exist in list\n");
            }
            break;
        case 'm':
        case 'M':
            printf("Block -> ");    /* 地区番号入力 */
            scanf("%d", &in_tno);
            printf("Age   -> ");    /* 年齢入力 */
            scanf("%d", &in_nno);
            in_nno = cnv_age(in_nno);   /* 年齢帯番号へ変換 */

            printf("Population -> ");
            scanf("%d", &in_dt);
            ret = modify(head_t, head_n, in_tno, in_nno, in_dt);    /* 修正 */
            if(ret == -1)
            {
                printf("Block or age number error\n");
            }
            else if (ret == -2)
            {
                printf("Node do not exist\n");
            }
            break;
        case 'd':
        case 'D':
            printf("Block -> ");    /* 地区番号入力 */
            scanf("%d", &in_tno);
            printf("Age   -> ");    /* 年齢入力 */
            scanf("%d", &in_nno);
            in_nno = cnv_age(in_nno);

            ret = delete(head_t, head_n, in_tno, in_nno);    /* 削除処理 */
            if(ret == -1)
            {
                printf("Block or age number error\n");
            }
            else if (ret == -2)
            {
                printf("Node do not exist\n");
            }
            break;
        case 'p':
        case 'P':
            printf("Block/Age");    /* 地区番号入力 */
            for(i = 0; i < WIDE; i++)
            {
                if(i == WIDE - 1)
                {
                    printf(" %3d-", i*10);
                }
                else
                {
                    printf(" %2d-%2d", i*10, i*10+9);
                }
            }
            printf("\n");
            ret = print(head_t, head_n);
            printf("\nNode count = %d\n", ret);
            break;
        case 'c':
        case 'C':
            calculate(head_t, head_n);  /* 縦横集計 */
            break;
        case 'i':
        case 'I':
            initialize(head_t, head_n); /* 初期化処理 */
            printf("List initialized\n");
            break;
        default:
            break;
        }
        printf("\n");
    }
    return 0;
}

/* ファイルから地区別人口データを読み込み重連結リストへ登録する */
int
load(struct t_tiku h_t[], struct t_nen h_n[], char * p_fname)
{
    FILE      * fp      = NULL;
    int         tno     = 0;
    int         nno     = 0;
    int         dt      = 0;

    if((fp = fopen(p_fname, "r")) == NULL)
    {
        return  -1;
    }
    else
    {
        initialize(h_t, h_n);   /* 重連結リスト初期化 */
        /* EOFが検出されるまで1レコードずつ読込み、リストに登録 */
        while((fscanf(fp, "%d %d %d", &tno, &nno, &dt)) != EOF)
        {
            if((append(h_t, h_n, tno, nno, dt)) != 0)   
            {   /* 追加処理で異常あり */
                fclose(fp);
                return  -2;
            }
        }
        fclose(fp);
        return  0;
    }
    return 0;
}

/* 重連結リストにリンクされているノードの情報をファイルへ保存する */
int
save(struct t_tiku h_t[], struct t_nen h_n[], char * p_fname)
{
    FILE      * fp      = NULL;
    int         t_pos   = 0;
    int         nno     = 0;
    int         dt      = 0;
    struct  node    ** pp_s = NULL;

    if((fp = fopen(p_fname, "w")) == NULL)
    {
        return  -1;
    }
    else
    {   /* 地区ヘッドを起点にリンクを辿りながら番号と人口をファイルへ書き込む */
        for(t_pos = 0; t_pos < HIGH; t_pos++)
        {
            pp_s = &(h_t[t_pos].next);  /* 地区方向の第一ノードを指す */
            while(*pp_s != NULL)
            {
                dt  = (**pp_s).data;        /* 人口を得る */
                nno = ((**pp_s).p_hn)->no;  /* 年齢帯番号を得る */
                fprintf(fp, "%d %d %d\n", t_pos, nno, dt);  /* 書き込み */
                pp_s = &((**pp_s).p_nt);    /* 地区方向の次のノードへ移動 */
            }
        }
        fclose(fp);
        return  0;
    }
    return 0;
}


/* 重連結リストへデータを追加する */
int
append(struct t_tiku h_t[], struct t_nen h_n[], int tno, int nno, int dt)
{
    struct  node    *  p_new    = NULL;
    struct  node    ** pp_t     = NULL;
    struct  node    ** pp_n     = NULL;

    if(nno < 0 || nno >= WIDE || tno < 0 || tno >= HIGH)    /* 番号異常? */
    {
        return  -2;
    }
    else
    {
        p_new = malloc(sizeof(struct node));    /* 新ノード確保 */
        assert(p_new);
        /* 年齢方向の終端ノードを発見し、新ノードをリンクする */
        pp_n = &(h_n[nno].next);    /* 年齢帯ヘッド配列ポインタ部 */
        while(*pp_n != NULL)
        {
            if(((**pp_n).p_ht)->no == tno)
            {
                return  -3;
            }
            else
            {
                pp_n = &((**pp_n).p_nn);    /* 次のノードへ移動 */
            }
        }
        *pp_n = p_new;  /* 年齢方向の終端にリンク */
        /* 地区方向の終端ノードを発見し、新ノードをリンク */
        pp_t = &(h_t[tno].next);    /* 地区ヘッド配列ポインタのポインタ */
        while(*pp_t != NULL)        /* 地区方向のノードあり? */
        {
            pp_t = &((**pp_t).p_nt);    /* 次の地区方向のノードへ */
        }
        *pp_t = p_new;  /* 地区方向の終端にリンク */
        /* 新ノードの処理 */
        p_new->p_hn = &h_n[nno];    /* 年齢帯ヘッド配列へのポインタ */
        p_new->p_ht = &h_t[nno];    /* 地区ヘッド配列へのポインタ */
        p_new->p_nn = NULL; /* 年齢並び次ノードへのポインタ */
        p_new->p_nt = NULL; /* 地区並び次ノードへのポインタ */
        p_new->data = dt;   /* 人口格納 */
        return 0;
    }

    return 0;
}

/* 重連結リスト中のノードの値(人口)を修正する */
int
modify(struct t_tiku h_t[], struct t_nen h_n[], int tno, int nno, int dt)
{
    struct  node    ** pp_t = NULL;
    struct  node    ** pp_n = NULL;

    if(nno < 0 || nno >= WIDE || tno < 0 || tno >= HIGH)    /* 番号異常? */
    {
        return  -2;
    }
    else
    {
        /* 同じ年齢番号と地区番号にリンクされたノードを探す */
        pp_n    = &(h_n[nno].next); /* 年齢帯ヘッド配列ポインタ部 */
        while(*pp_n != NULL)
        {
            if(((**pp_n).p_ht)->no == tno)  /* 同じ地区番号か? */
            {
                (**pp_n).data = dt; /* 人口修正 */
                return  0;  /* 修正完了 */
            }
            else
            {
                pp_n    = &((**pp_n).p_nn); /* 次のノードへ移動 */
            }
        }
        return  -2; /* 指示されたノード無し */
    }
    return 0;
}

/* 重連結リスト中のノードを削除する */
int
delete(struct t_tiku h_t[], struct t_nen h_n[], int tno, int nno)
{
    struct  node    ** pp_t   = NULL;
    struct  node    ** pp_n   = NULL;
    struct  node    *  p_node = NULL;
    int                no     = 0;
    
    if(nno < 0 || nno >= WIDE || tno < 0 || tno >= HIGH)    /* 番号異常? */
    {
        return  -2;
    }

    pp_n = &(h_n[nno].next);    /* 年齢帯ヘッド配列のポインタ部 */

    while(*pp_n != NULL)    /* 年齢帯方向ノードあり? */
    {
        no = ((**pp_n).p_ht)->no;   /* 地区方向の親番号を no に得る */
        if(no == tno)   /* 指示された地区番号と同じ番号か? */
        {
            pp_t = &(h_t[tno].next);    /* 地区ヘッド配列のポインタ部アドレスを得る */
            while(*pp_t != *pp_n)       /* 削除ノードまで地区並びのサーチ */
            {
                pp_t = &((**pp_t).p_nt);    /* 次の地区方向ノードへ移動 */
            }
            p_node = *pp_n;         /* 削除ノードのアドレスを p_node に得る */
            *pp_n  = (**pp_n).p_nn; /* 削除ノードを年齢方向のリンクから外す */
            *pp_t  = (**pp_t).p_nt; /* 削除ノードを地区方向のリンクから外す */ 
            free(p_node);           /* 削除ノードのメモリ領域を解放 */
            return  0;  /* 削除完了 */
        }
        else
        {
            pp_n = &((**pp_n).p_nn);    /* 次の年齢方向ノードへ移動 */
        }
    }
    return  -2; /* 指示されたノードが存在しない */
}

/* 重連結リストにリンクされている全てのノードのデータ部を表形式で表示する */
int
print(struct t_tiku h_t[], struct t_nen h_n[])
{
    int     buff[WIDE];         /* 1行分のデータを格納する配列 */
    int     h_pos   = 0;        /* 年齢帯ヘッド配列ポジショナ */
    int     cnt     = 0;        /* ノード数カウント用 */
    int     i       = 0;
    struct  node    ** pp_s = NULL;

    for(h_pos = 0; h_pos < HIGH; h_pos++)
    {
        for(i = 0; i < WIDE; i++)
        {
            buff[i] = 0;
        }

        pp_s = &(h_t[h_pos].next);  /* 地区並びの第一ノードを指す */

        while(*pp_s != NULL)
        {
            buff[((**pp_s).p_hn)->no] = (**pp_s).data;  /* データ取り出し */
            pp_s = &((**pp_s).p_nt);    /* 地区並びの次のノードへ移動 */
            cnt++;
        }
        printf("%5d    ", h_pos);   /* 地区番号表示 */
        for(i = 0; i < WIDE; i++)   /* 1行分(0~WIDE-1)ループ */
        {
            printf("%4d    ", buff[i]); /* データを一件表示 */
        }
        printf("\n");
    }
    return  cnt;    /* ノード数を返す */
}

/* 重連結リストの縦横集計を行い結果を表示する */
void
calculate(struct t_tiku h_t[], struct t_nen h_n[])
{
    int sum_nen[WIDE];
    int sum_tiku[WIDE];
    int h_pos   = 0;
    int i       = 0;
    struct  node    ** pp_s = NULL;

    for(i = 0; i < WIDE; i++)
    {
        sum_nen[i] = 0;
    }
    for(i = 0; i < HIGH; i++)
    {
        sum_tiku[i] = 0;
    }

    for(h_pos = 0; h_pos < HIGH; h_pos++)
    {
        pp_s = &(h_t[h_pos].next);
        while(*pp_s != NULL)
        {
            sum_tiku[h_pos] += (**pp_s).data;
            sum_nen[((**pp_s).p_hn)->no] += (**pp_s).data;
            pp_s = &((**pp_s).p_nt);
        }
    }

    printf("Age sum\n");
    for(i = 0; i < WIDE; i++)
    {
        if(i == WIDE-1)
        {
            printf(" %3d-", i*10);
        }
        else
        {
            printf(" %2d-%2d", i*10, i*10+9);
        }
    }
    printf("\n");

    for(i = 0; i < WIDE; i++)
    {
        printf(" %4d", sum_nen[i]);
    }
    printf("\n\n");

    printf("Block sum\n");
    for(i = 0; i < HIGH; i++)
    {
        printf("%4d", i);
    }
    printf("\n");

    for(i = 0; i < HIGH; i++)
    {
        printf("%4d", sum_tiku[i]);
    }
    printf("\n");
}

/* 重連結リストを初期化する */
void
initialize(struct t_tiku h_t[], struct t_nen h_n[])
{
    struct  node    * p_n = NULL;
    struct  node    * p_s = NULL;
    int               pos = 0;

    for(pos = 0; pos < WIDE; pos++)
    {
        p_n = h_n[pos].next;
        while(p_n != NULL)
        {
            p_s = p_n->p_nn;
            free(p_n);
            p_n = p_s;
        }
        h_n[pos].next = NULL;   /* pos番目の年齢帯ヘッド配列ポインタ部初期化 */
    }
    
    for(pos = 0; pos < HIGH; pos++) /* 地区ヘッド配列を 0~HIGH-1 まで */
    {
        h_t[pos].next = NULL;   /* 地区ヘッド配列ポインタ部初期化 */
    }
}

/* 年齢を年齢帯番号(0~9)に変換する */
int
cnv_age(int age)
{
    int age_no = 0;

    age_no = age/10;
    if(age_no > 9)
    {
        age_no = 9;
    }
    return age_no;
}

 

動的な連結リスト構造によるスタック構造のサンプルプログラム

/* 
 * Cプログラミングとデータ構造(9.11)
 * 動的な連結リスト構造によるスタック構造のサンプルプログラム
 * p(P) : データ追加(Push)
 * g(G) : データ取り出し(Pop)
 * i(I) : スタックの初期化
 * o(O) : スタックデータと件数の表示
 * q(Q) : プログラムの終了
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct  node
{
    int           data; /* データ部 */
    struct node * next; /* ポインタ部 */
};

int push(int dt, struct node * p_head);
int pop(struct  node    * p_head);
void initialize(struct   node    * p_head);
int print(struct node * pt);

int
main()
{
    struct  node        head;
    char                cmd[2];
    int                 indt   = 0;
    int                 ret    = 0;

    head.next = NULL;
    cmd[0] = ' ';

    while(cmd[0] != 'q' && cmd[0] != 'Q')
    {
        printf("Command ? ");
        scanf("%s", cmd);

        switch(cmd[0])
        {
        case 'p':
        case 'P':
            printf("Push data -> ");
            scanf("%d", &indt);
            ret = push(indt, &head);
            if(ret == -1)
            {
                fprintf(stderr, "Memory Allocation Error\n");
            }
            break;
        case 'g':
        case 'G':
            ret = pop(&head);
            if(ret == -1)
            {
                printf("Stack Empty\n");
            }
            else
            {
                printf("Pop data = %d\n", ret);
            }
            break;
        case 'i':
        case 'I':
            initialize(&head);
            printf("Stack Initialized\n");
            break;
        case 'o':
        case 'O':
            ret = print(&head);
            if(ret == 0)    /* スタックは空か? */
            {
                printf("Stack Empty\n");
            }
            else
            {
                printf("Stack Count = %d\n", ret);  /* スタック件数 */
            }
            break;
        default:
            break;
        }
        printf("\n");
    }

    return 0;
}

int
push(int dt, struct node * p_head)
{
    struct  node    * p_new = NULL;

    p_new = malloc(sizeof(struct node));
    if(p_new == NULL)
    {
        return  -1;
    }
    else
    {
        p_new->data     = dt;               /* 新ノードへデータ格納 */
        p_new->next     = p_head->next;     /* 新ノードのポインタ部 */
        p_head->next    = p_new;            /* ノードヘッドのポインタ部 */
        return  0;
    }
}

int
pop(struct  node    * p_head)
{
    struct  node    * p_pop = NULL;
    int               dt;

    if(p_head->next == NULL) 
    {
        return  -1;
    }
    else
    {
        p_pop           = p_head->next; /* 第一ノードのアドレスを p_pop に得る */
        dt              = p_pop->data;  /* データを dt に得る */
        p_head->next    = p_pop->next;  /* ヘッドのリンクを変更 */
        free(p_pop);                    /* popしたノードのメモリを解放 */
        return  dt;                     /* データを返す */
    }
}

void
initialize(struct   node    * p_head)
{
    struct  node    * pt        = NULL;
    struct  node    * pt_del    = NULL;

    pt  = p_head->next; /* 第一ノードのアドレスを pt に得る */
    while(pt != NULL)   /* 終端ノードでなければループ */
    {
        pt_del  = pt;       /* 消去するノードのアドレスを p_del へ */
        pt      = pt->next; /* pt を次のノードへ進める */
        free(pt_del);  
    }
    p_head->next    = NULL;
}

int
print(struct node * pt)
{
    int i   = 0;

    pt  = pt->next;                 /* 第一ノードのアドレスを pt へ */
    while(pt != NULL)               /* 終端ノードでなければループ */
    {
        printf("%d\n", pt->data);
        pt  = pt->next;             /* ptを次ノードへ進める */
        i++;                        /* ノードカウンタ +1 */
    }

    return  i;      
}

 

配列を使ったキュー構造のサンプルプログラム

/*
 * Cプログラミングとデータ構造(9.5)
 * 配列を使ったキュー構造のサンプルプログラム
 * (2つの指標を使うアルゴリズム)
 * e(E) : データの追加(EnQueue)
 * d(D) : データの削除(DeQueue)
 * i(I) : キューの初期化
 * o(O) : キューデータと件数の表示
 * q(Q) : プログラムの終了
 */


 /*=========*/
 /* include */
 /*=========*/
#include <stdio.h>

/*========*/
/* define */
/*========*/
#define    LIMIT    5

/*==========*/
/* function */
/*==========*/
int get_cmd();
int en_queue(int[], int, int, int);
int de_queue(int[], int *, int *, int *);
int output(int[], int, int);

/*===============*/
/* routine start */
/*===============*/
int
main()
{
  get_cmd();
  return 0;
}

int
get_cmd()
{
  int    ret;
  int    eqpos = 0; /* index about EnQueue */
  int    dqpos = 0; /* index about DeQueue */
  int    indt;      /* input data */
  int    queue[LIMIT];
  char   cmd[2] = { ' ', '\0' };

  while (cmd[0] != 'q' && cmd[0] != 'Q')
  {
    printf("Command ? ");
    scanf("%s", cmd);
    switch (cmd[0])
    {
    case    'e':
    case    'E':
      printf("EnQueue Data -> ");
      scanf("%d", &indt);
      ret = en_queue(queue, indt, eqpos, LIMIT);
      if (ret == -1)
      {
        printf("Queue buffer Full\n");
      }
      else
      {
        eqpos = ret;
      }
      break;
    case    'd':
    case    'D':
      ret = de_queue(queue, &eqpos, &dqpos, &indt);
      if (ret == -1)
      {
        printf("Queue buffer Empty\n");
      }
      else
      {
        printf("DeQueue data = %d\n", indt);
      }
      break;
    case 'i':
    case 'I':
      eqpos = dqpos = 0;
      printf("Queue Initialized\n");
      break;
    case 'o':
    case 'O':
      ret = output(queue, eqpos, dqpos);
      if (ret == 0)
      {
        printf("Queue buffer Empty\n");
      }
      printf("Queue count = %d\n", ret);
      break;
    }
    printf("\n");
  }
  return 0;
}

int
en_queue(int dis[], int dt, int pos, int max)
{
  if (pos >= max)
  {
    return    -1;
  }
  else
  {
    dis[pos] = dt;
    return    (pos + 1);
  }
}

int
de_queue(int dis[], int *epos, int *dpos, int *pdt)
{
  if (*epos == *dpos)
  {
    return -1;
  }
  else
  {
    *pdt = dis[*dpos];
    (*dpos)++;
    if (*epos == *dpos)
    {
      *epos = *dpos = 0;
    }
    return    0;
  }
}

int
output(int dis[], int epos, int dpos)
{
  int    i;

  if (epos == dpos)
  {
    return    0;
  }
  else
  {
    for (i = dpos; i < epos; i++)
    {
      printf("%d\n", dis[i]);
    }
    return (epos - dpos);
  }
}

 

配列を使った環状キュー構造のサンプルプログラム

/*
 * Cプログラミングとデータ構造(9.6)
 * 配列を使った環状キュー構造のサンプルプログラム
 * (配列を環状に使うアルゴリズム)
 * e(E) : データの追加(EnQueue)
 * d(D) : データの削除(DeQueue)
 * i(I) : キューの初期化
 * o(O) : キューデータと件数の表示
 : q(Q) : プログラムの終了
 */
 /*=========*/
 /* include */
 /*=========*/
#include <stdio.h>

/*========*/
/* define */
/*========*/
#define  LIMIT  8

/*==========*/
/* function */
/*==========*/
void get_cmd();
int
en_queue
(
  int    que[], /* キューバッファ  */
  int    data,    /* データ          */
  int    epos,  /* enQueueする位置 */
  int    dpos   /* deQueueする位置 */
);
int
de_queue
(
  int    que[], /* キューバッファ       */
  int    epos,  /* エンキューする位置   */
  int    dpos,  /* デキューする位置     */
  int  * pdata    /* デキューされるデータへのアドレスを入れる */
);
int
output
(
  int    que[], /* キューバッファ       */
  int    epos,  /* エンキューする位置   */
  int    dpos   /* デキューする位置     */
);
int next(int pos);

/*===============*/
/* routine start */
/*===============*/
int
main()
{
  get_cmd();
  return 0;
}

void
get_cmd()
{
  int    eqpos = 0;    /* index about EnQueue */
  int    dqpos = 0;    /* index about DeQueue */
  int    indata = 0;    /* input data */
  int    ret = 0;
  int    queue[LIMIT];
  char   cmd[2] = { ' ', '\0' };

  while (cmd[0] != 'q' && cmd[0] != 'Q')
  {
    printf("Command ? ");
    scanf("%s", cmd);
    switch (cmd[0])
    {
    case    'e': /* エンキュー */
    case    'E': /* エンキュー */
      printf("EnQueue Data -> ");
      scanf("%d", &indata);
      ret = en_queue(queue, indata, eqpos, dqpos);
      if (ret == -1)
      {
        printf("Queue buffer Full\n");
      }
      else
      {
        eqpos = ret;
      }
      break;
    case    'd': /* デキュー */
    case    'D': /* デキュー */
      ret = de_queue(queue, eqpos, dqpos, &indata);
      if (ret == -1)
      {
        printf("Queue buffer Empty\n");
      }
      else
      {
        printf("DeQueue data = %d\n", indata);
        dqpos = ret;
      }
      break;
    case 'i': /* キューをInitialize */
    case 'I': /* キューをInitialize */
      eqpos = dqpos;
      printf("Queue Initialized\n");
      break;
    case 'o': /* キューを表示する */
    case 'O': /* キューを表示する */
      ret = output(queue, eqpos, dqpos);
      if (ret == 0)
      {
        printf("Queue buffer Empty\n");
      }
      printf("Queue count = %d\n", ret);
      break;
    }
    printf("\n");
  }
}

int
en_queue
(
  int    que[], /* キューバッファ  */
  int    data,    /* データ          */
  int    epos,  /* enQueueする位置 */
  int    dpos   /* deQueueする位置 */
)
{
  if (next(epos) == dpos) /* 次の位置はデキューのポイント? */
  {
    return    -1; /* デキューしないと詰められません */
  }
  else
  {
    que[epos] = data;      /* エンキューする */
    return (next(epos)); /* 次のエンキュー位置を返す */
  }
}


int
de_queue
(
  int    que[], /* キューバッファ       */
  int    epos,  /* エンキューする位置   */
  int    dpos,  /* デキューする位置     */
  int  * pdata    /* デキューされるデータへのアドレスを入れる */
)
{
  if (epos == dpos)
  {
    return -1;
  }
  else
  {
    *pdata = que[dpos];    /* デキューされたデータ */
    return (next(dpos));
  }
}

int
output
(
  int    que[], /* キューバッファ       */
  int    epos,  /* エンキューする位置   */
  int    dpos   /* デキューする位置     */
)
{
  int    i, j;
  i = dpos;
  j = 0;

  while (i != epos)
  {
    printf("%d\n", que[i]);
    j++;
    i = next(i);
  }
  return j;
}

int
next(int pos)
{
  return ((pos + 1) % LIMIT);
}

 

環状キュー構造を使ったスケジュール管理プログラム

/*
 * Cプログラミングとデータ構造(9.7)
 * キュー構造を使ったスケジュール管理プログラム
 * データは動的に確保したメモリに格納し、各データの格納されているメモリ・アドレスをポインタ配列に記憶する。
 * このポインタ配列を環状のキューバッファとして扱う.
 * e(E) : データの追加(EnQueue)
 * d(D) : データの削除(DeQueue)
 * i(I) : キューの初期化
 * o(O) : キューデータと件数の表示
 : q(Q) : プログラムの終了
 */
/*=========*/
/* include */
/*=========*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*========*/
/* define */
/*========*/
#define  LIMIT  8

/*========*/
/* struct */
/*========*/
struct  rec
{
    char    date[8];    /* 日付 */
    char    name[16];   /* 名前 */
    char    place[16];  /* 場所 */
};

/*==========*/
/* function */
/*==========*/
void get_cmd();
int
en_queue
(
    struct  rec   * dis[],  /* キューポインタ配列のアドレス */
    struct  rec     dt,     /* 追加するデータを格納したrec型構造体 */
    int             epos,   /* EnQueue位置指標の値 */
    int             dpos    /* DeQueue位置指標の値 */
);
int
de_queue
(
    struct  rec   * dis[],  /* キューポインタ配列のアドレス */
    int             epos,   /* EnQueue位置指標の値 */
    int             dpos,   /* DeQueue位置指標の値 */
    struct  rec   * pdt     /* DeQueueしたデータを格納する領域のアドレス */
);
void init_mem(struct rec * dis[], int epos, int dpos);
int
output
(
    struct rec    * dis[],  /* キューポインタ配列の値 */
    int             epos,   /* enqueue 位置指標の値 */
    int             dpos    /* dequeue 位置指標の値 */
);
int next(int pos);

/*===============*/
/* routine start */
/*===============*/
int
main()
{
    get_cmd();
    return 0;
}

void
get_cmd()
{
    struct  rec   * queue[LIMIT];   /* キューポインタ配列 */
    int             eqpos  = 0;     /* index about EnQueue */
    int             dqpos  = 0;     /* index about DeQueue */
    char            cmd[2] = {' ', '\0'};
    struct  rec     wk;             /* データ入出力用 */
    int             ret    = 0;

    while(cmd[0] != 'q' && cmd[0] != 'Q')
    {
        printf("Command ? ");
        scanf("%s", cmd);
        switch(cmd[0])
        {
        case    'e': /* エンキュー */
        case    'E': /* エンキュー */
            printf("Data  -> "); scanf("%s", wk.date);
            printf("Name  -> "); scanf("%s", wk.name);
            printf("Place -> "); scanf("%s", wk.place);
            ret = en_queue(queue, wk, eqpos, dqpos);    /* 追加処理 */
            if(ret == -1)
            {
                printf("Queue buffer Full\n");
            }
            else if(ret == -2)
            {
                printf("Memory allocation error\n");
            }
            else
            {
                eqpos = ret;    /* EnQueue指標更新 */
            }
            break;
        case    'd': /* デキュー */
        case    'D': /* デキュー */
            ret = de_queue(queue, eqpos, dqpos, &wk);   /* 取り出し処理 */
            if(ret == -1)
            {
                printf("Queue buffer Empty\n");
            }
            else
            {
                printf("DeQueue data  = %s\n", wk.date);
                printf("        Name  = %s\n", wk.name);
                printf("        Place = %s\n", wk.place);
                dqpos = ret;    /* DeQueue指標更新 */
            }
            break;
        case 'i': /* キューをInitialize */
        case 'I': /* キューをInitialize */
            init_mem(queue, eqpos, dqpos);  /* 領域の初期化 */
            eqpos = dqpos;                  /* 指標の初期化 */
            printf("Queue Initialized\n");
            break;
        case 'o': /* キューを表示する */
        case 'O': /* キューを表示する */
            ret = output(queue, eqpos, dqpos);
            break;
        }
        printf("\n");
    }
}

int
en_queue
(
    struct  rec   * dis[],  /* キューポインタ配列のアドレス */
    struct  rec     dt,     /* 追加するデータを格納したrec型構造体 */
    int             epos,   /* EnQueue位置指標の値 */
    int             dpos    /* DeQueue位置指標の値 */
)
{
    struct  rec * pt = NULL;

    if(next(epos) == dpos) /* キューの上限? */
    {
        return    -1; /* デキューしないと詰められません */
    }
    else
    {
        pt = malloc(sizeof(struct rec));
        if(pt == NULL)
        {
            return  -2;
        }
        else
        {
            /* 確保したメモリへスケジュールデータをコピー */
            strcpy(pt->date,  dt.date);
            strcpy(pt->name,  dt.name);
            strcpy(pt->place, dt.place);
            dis[epos] = pt;         /* アドレスをポインタ配列へ登録 */
            return (next(epos));    /* 次のエンキュー位置を返す */
        }
    }
}


int
de_queue
(
    struct  rec   * dis[],  /* キューポインタ配列のアドレス */
    int             epos,   /* EnQueue位置指標の値 */
    int             dpos,   /* DeQueue位置指標の値 */
    struct  rec   * pdt     /* DeQueueしたデータを格納する領域のアドレス */
)
{
    struct  rec     * mem = NULL;

    if(epos == dpos)    /* キューデータ無し */
    {
        return -1;
    }
    else
    {
        mem = dis[dpos];
        strcpy(pdt->date,  mem->date);
        strcpy(pdt->name,  mem->name);
        strcpy(pdt->place, mem->place);
        free(mem);
        return (next(dpos));    /* 次の DeQueue位置を返す */
    }
}

/* 登録されている全てのスケジュールデータが使用しているメモリ解放 */
void
init_mem(struct rec * dis[], int epos, int dpos)
{
    int i = dpos;

    while(i != epos)    /* i が EnQueue指標値になるまで領域を解放 */
    {
        free(dis[i]);
        i = next(i);
    }
}

/* キューに登録されているデータの表示 */
int
output
(
    struct rec    * dis[],  /* キューポインタ配列の値 */
    int             epos,   /* enqueue 位置指標の値 */
    int             dpos    /* dequeue 位置指標の値 */
)
{
    int    i, j;
    i = dpos;
    j = 0;

    while(i != epos)        /* i が EnQueue指標値になるまで */
    {   /* スケジュールデータを表示 */
        printf("[%s], [%s], [%s]\n", dis[i]->date, dis[i]->name, dis[i]->place);
        /* 次の位置を計算して i を更新 */
        j++;
        i = next(i);
    }
    return j;
}

/* リングバッファ内の 1つ後ろの位置を計算する */
int
next(int pos)
{
    return ((pos + 1) % LIMIT);
}

 

動的な単方向リンクリスト

/* 
 * Cプログラミングとデータ構造(9.9)
 * 動的な単方向リンクリスト
 * a(A) : ノードの追加
 * s(S) : ノードの探索
 * i(I) : ノードの挿入
 * d(D) : ノードの削除
 * p(P) : リストデータと件数の表示
 * c(C) : リストの初期化
 * q(Q) : プログラムの終了
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct  node
{
    int           data;
    struct node * next;
};

/* algorithm_single_list.c */
int main();
int append(int dt,struct node ** pp_h);
struct node ** search(int dt,struct node ** pp_h);
int insert(int dt,int ldt,struct node ** pp_h);
int delete(int ldt,struct node ** pp_h);
int print(struct node ** pp_h);
void initialize(struct node ** pp_h);
struct node ** end_node(struct node ** pp_h);

int
main()
{
    struct  node        head;
    struct  node      * pt;
    struct  node     ** ppt;
    char                cmd[2];
    int                 indt   = 0;
    int                 listdt = 0;
    int                 ret    = 0;

    head.next = NULL;
    cmd[0] = ' ';

    while(cmd[0] != 'q' && cmd[0] != 'Q')
    {
        printf("Command ? ");
        scanf("%s", cmd);

        switch(cmd[0])
        {
        case 'a':
        case 'A':
            printf("Append data -> ");
            scanf("%d", &indt);
            ret = append(indt, &(head.next));
            if(ret == -1)
            {
                fprintf(stderr, "Memory Allocation Error\n");
            }
            break;
        case 's':
        case 'S':
            printf("Search data -> ");
            scanf("%d", &indt);
            ppt = search(indt, &(head.next));
            if(*ppt == NULL)
            {
                printf("Search Error\n");
            }
            else
            {
                printf("Search Success\n");
                printf("List Data = %d\n", (*ppt)->data);
            }
            break;
        case 'i':
        case 'I':
            printf("Insert data -> ");  /* 挿入データ入力 */
            scanf("%d", &indt);         /* 挿入先ノードの入力 */
            printf("List node data -> ");
            scanf("%d", &listdt);
            ret = insert(indt, listdt, &(head.next));
            if(ret == -1)
            {
                printf("Memory Allocation Error\n");
            }
            else if(ret == -2)
            {
                printf("Insert Node Not Found\n");
            }
            break;
        case 'd':
        case 'D':
            printf("Delete data -> ");
            scanf("%d", &indt);
            ret = delete(indt, &(head.next));
            if(ret == -1)
            {
                printf("Delete Node Not Found\n");
            }
            break;
        case 'p':
        case 'P':
            printf("List Data = ");
            ret = print(&(head.next));
            printf("\nNode Count = %d\n", ret); /* ノード数表示 */
            break;
        case 'c':
        case 'C':
            initialize(&(head.next));
            printf("List Initialized\n");
            break;
        default:
            break;
        }
        printf("\n");
    }

    return 0;
}

int
append(int dt, struct node ** pp_h)
{
    struct  node  * p_new;

    pp_h  = end_node(pp_h);  /* 終端ノードのポインタ部のアドレスを得る */
    p_new = malloc(sizeof(struct node));
    if(!p_new)
    {
        return -1;
    }
    else
    {
        p_new->data = dt;       /* 新ノードへデータ格納 */
        p_new->next = NULL;     /* 新ノードを終端ノードにする */
        *pp_h       = p_new;    /* 旧終端ノードと新終端ノードをリンク */
        return 0;
    }
    return 0;
}

struct node **
search(int dt, struct node ** pp_h)
{
    while(*pp_h != NULL)
    {
        if(dt == (*pp_h)->data)
        {
            break;
        }
        else
        {
            pp_h = &((*pp_h)->next);    /* pp_h を次のノードへ */
        }
    }
    return pp_h;
}

int
insert(int dt, int ldt, struct node ** pp_h)
{
    struct  node      * p_new;

    pp_h = search(ldt, pp_h);       /* 挿入位置ノード探索 */
    if(*pp_h == NULL)
    {
        return -2;
    }
    else
    {
        p_new = malloc(sizeof(struct node));
        if(!p_new)
        {
            return -1;
        }
        else
        {
            p_new->data = dt;
            p_new->next = *pp_h;
            *pp_h       = p_new;
            return 0;
        }
    }
    return 0;
}

int
delete(int ldt, struct node ** pp_h)
{
    struct  node       * p_d;

    pp_h = search(ldt, pp_h);   /* 削除ノード探索 */
    if(*pp_h == NULL)    
    {
        return -1; 
    }
    else
    {
        p_d   = *pp_h;
        *pp_h = (*pp_h)->next;  /* (**pp_h).next としても同じ */
        free(p_d);
        return 0;
    }
    return 0;
}

int
print(struct node ** pp_h)
{
    int i = 0;

    while(*pp_h != NULL)
    {
        printf("%d ", (*pp_h)->data);
        pp_h = &((**pp_h).next);
        i++;
    }
    return i;
}

void
initialize(struct node ** pp_h)
{
    struct node     * p_c;
    struct node     * p_f;

    p_c = *pp_h;
    while(p_c != NULL)  /* 終端ノードでなければループ */
    {
        p_f = p_c;
        p_c = p_c->next;
        free(p_f);
    }
    *pp_h = NULL;
}

struct  node **
end_node(struct node ** pp_h)
{
    while(*pp_h != NULL)
    {
        pp_h = &((*pp_h)->next);
    }
    return pp_h;
}

 

終端を示す番兵ノードとこれを指すポインタを用いた動的な単方向リンクリスト

/* 
 * Cプログラミングとデータ構造(9.10)
 * 終端を示す番兵ノードとこれを指すポインタを用いた動的な単方向リンクリスト
 * a(A) : ノードの追加
 * s(S) : ノードの探索
 * i(I) : ノードの挿入
 * d(D) : ノードの削除
 * p(P) : リストデータと件数の表示
 * c(C) : リストの初期化
 * q(Q) : プログラムの終了
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct  node
{
    int           data;
    struct node * next;
};

/* algorithm_singlelist_guard.c */
int main();
struct node * append(int dt,struct node * p_e);
struct node * search(int dt,struct node * p_h,struct node * p_e);
int insert(int dt,int ldt,struct node * p_h,struct node * p_e);
struct node * delete(int ldt,struct node * p_h,struct node * p_e);
int print(struct node * p_h,struct node * p_e);
void initialize(struct node * p_h,struct node * p_e);

int
main()
{
    struct  node        head;
    struct  node      * end;    /* 番兵ノードを指すポインタ */
    struct  node      * p_ret;
    char                cmd[2];
    int                 indt   = 0;
    int                 listdt = 0;
    int                 ret    = 0;

    head.next = NULL;
    cmd[0] = ' ';

    /* 番兵ノード確保 */
    end = (struct node *)malloc(sizeof(struct node));
    assert(end);
    head.next = end;

    while(cmd[0] != 'q' && cmd[0] != 'Q')
    {
        printf("Command ? ");
        scanf("%s", cmd);

        switch(cmd[0])
        {
        case 'a':
        case 'A':
            printf("Append data -> ");
            scanf("%d", &indt);
            p_ret = append(indt, end);
            if(p_ret == NULL)
            {
                fprintf(stderr, "Memory Allocation Error\n");
            }
            else
            {
                end = p_ret;    /* 番兵ポインタ更新 */
            }
            break;
        case 's':
        case 'S':
            printf("Search data -> ");
            scanf("%d", &indt);
            p_ret = search(indt, &head, end);
            if(p_ret == end)
            {
                printf("Search Error\n");
            }
            else
            {
                printf("Search Success\n");
                printf("Node address = %p\n", p_ret);
                printf("List Data    = %d\n", p_ret->data);
            }
            break;
        case 'i':
        case 'I':
            printf("Insert data -> ");  /* 挿入データ入力 */
            scanf("%d", &indt);         /* 挿入先ノードの入力 */
            printf("List node data -> ");
            scanf("%d", &listdt);
            ret = insert(indt, listdt, &head, end);
            if(ret == -1)
            {
                printf("Memory Allocation Error\n");
            }
            else if(ret == -2)
            {
                printf("Insert Node Not Found\n");
            }
            break;
        case 'd':
        case 'D':
            printf("Delete data -> ");
            scanf("%d", &indt);
            p_ret = delete(indt, &head, end);
            if(p_ret == NULL)
            {
                printf("Delete Node Not Found\n");
            }
            else
            {
                end = p_ret;    /* 番兵ポインタ更新 */
            }
            break;
        case 'p':
        case 'P':
            printf("List Data = ");
            ret = print(&head, end);
            printf("\nNode Count = %d\n", ret); /* ノード数表示 */
            break;
        case 'c':
        case 'C':
            initialize(&head, end);
            printf("List Initialized\n");
            break;
        default:
            break;
        }
        printf("\n");
    }

    return 0;
}

struct node *
append(int dt, struct node * p_e)
{
    struct  node  * p_new;

    p_new = malloc(sizeof(struct node));    /* 新番兵ノード確保 */
    if(!p_new)
    {
        return  NULL;
    }
    else
    {
        p_e->data = dt;     /* 新ノードへデータ格納 */
        p_e->next = p_new;  /* 新ノードを終端ノードにする */
        return  p_new;      /* 旧終端ノードと新終端ノードをリンク */
    }
    return p_new; /* not reached */
}

struct node *
search(int dt, struct node * p_h, struct node * p_e)
{
    p_h = p_h->next;            /* 始端ノードのアドレスを p_h に得る */
    while(p_h != p_e)           /* 終端ノードでなければループ */
    {
        if(dt == p_h->data)
        {
            break;
        }
        else
        {
            p_h = p_h->next;    /* p_h を次のノードへ */
        }
    }
    return p_h;
}

int
insert(int dt, int ldt, struct node * p_h, struct node * p_e)
{
    struct  node      * p_new;

    p_h = search(ldt, p_h, p_e);       /* 挿入位置ノード探索 */
    if(p_h == p_e)
    {
        return -2;
    }
    else
    {
        p_new = malloc(sizeof(struct node));
        if(!p_new)
        {
            return -1;
        }
        else
        {
            p_new->data = p_h->data;    /* 新ノードへデータコピー */
            p_h->data   = dt;           /* 新データ格納 */
            p_new->next = p_h->next;    /* 新ノードのリンク */
            p_h->next   = p_new;        /* 挿入ノードのリンク */
            return 0;
        }
    }
    return 0;
}

struct node *
delete(int ldt, struct node * p_h, struct node * p_e)
{
    struct  node       * p_s;

    p_h = search(ldt, p_h, p_e);   /* 削除ノード探索 */
    if(p_h == p_e)    /* 目的ノードなし */
    {
        return NULL; 
    }
    else
    {
        if(p_h->next == p_e)
        {
            free(p_e);
            return p_h;
        }
        else
        {
            p_s   = p_h->next;      /* p_sに後ろのノードのアドレスを得る */
            p_h->data = p_s->data;  /* 後ろのノードのデータ部とポインタ部 */
            p_h->next = p_s->next;  /* を削除ノードへコピー */
            free(p_s);              /* 後ろのノードの領域を解放   */
            return p_e;             /* 番兵ノードのアドレスを返す */
        }
    }
    return 0;
}

int
print(struct node * p_h, struct node * p_e)
{
    int i = 0;

    p_h = p_h->next;
    while(p_h != p_e)
    {
        printf("%d ", p_h->data);
        p_h = p_h->next;
        i++;
    }
    return i;
}

void
initialize(struct node * p_h, struct node * p_e)
{
    struct node     * p_s;
    struct node     * p_ss;

    p_s = p_h->next;
    while(p_s != p_e)   /* 終端ノードでなければループ */
    {
        p_ss = p_s->next;
        free(p_s);
        p_s  = p_ss;
    }
    p_h->next = p_e;    /* ヘッドノードと番兵ノードをリンク */
}

 

配列を使ったスタック構造のサンプルプログラム

/*
 * Cプログラミングとデータ構造(9.3)
 * 配列を使ったスタック構造のサンプルプログラム
 * p(P) : データ追加(Push)
 * g(G) : データ取り出し(Pop)
 * i(I) : スタックの初期化
 * o(O) : スタックデータと件数の表示
 * q(Q) : プログラムの終了
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define LIMIT   5

int push(int dis[], int dt, int idx, int max);
int pop(int dis[], int idx, int *pdt);
int output(int dis[], int idx);

int
main()
{
  int                 stack[LIMIT];
  int                 index = 0;
  char                cmd[2];
  int                 indt = 0;
  int                 ret = 0;

  cmd[0] = ' ';

  while (cmd[0] != 'q' && cmd[0] != 'Q')
  {
    printf("Command ? ");
    scanf("%s", cmd);

    switch (cmd[0])
    {
    case 'p':
    case 'P':
      printf("Push data -> ");
      scanf("%d", &indt);
      ret = push(stack, indt, index, LIMIT);  /* push処理 */
      if (ret == -1)
      {
        fprintf(stderr, "Stack Full\n");
      }
      else
      {
        index = ret;  /* インデックス更新 */
      }
      break;
    case 'g':
    case 'G':
      ret = pop(stack, index, &indt);
      if (ret == -1)   /* スタックの底か? */
      {
        printf("Stack Empty\n");
      }
      else
      {
        printf("Pop data = %d\n", ret);
        index = ret;  /* インデックス更新 */
      }
      break;
    case 'i':
    case 'I':
      index = 0;
      printf("Stack Initialized\n");
      break;
    case 'o':
    case 'O':
      ret = output(stack, index);
      if (ret == 0)    /* スタックは空か? */
      {
        printf("Stack Empty\n");
      }
      printf("Stack count = %d\n", ret);  /* スタック件数表示 */
      break;
    default:
      break;
    }
    printf("\n");
  }

  return 0;
}

int
push(int dis[], int dt, int idx, int max)
{
  if (idx >= max)
  {
    return  -1;
  }
  else
  {
    dis[idx] = dt;
    return  (idx + 1);
  }
  return  -1; /* illegal sequence */
}

int
pop(int dis[], int idx, int *pdt)
{
  if (idx <= 0)
  {
    return  -1;
  }
  else
  {
    *pdt = dis[idx - 1];
    return  (idx - 1);
  }
  return  -1; /* illegal sequence */
}

int
output(int dis[], int idx)
{
  int i = 0;

  if (idx > 0)
  {
    for (i = idx - 1; i >= 0; i--)
    {
      printf("%d\n", dis[i]);
    }
  }
  return  idx;
}

 

メモリを動的に使って伸縮する2分木構造のサンプル

/*
 * Cプログラミングとデータ構造(9.16)
 * メモリを動的に使って伸縮する2分木構造のサンプル
 * a(A) : ノードの追加
 * s(S) : ノードの探索
 * d(D) : ノードの削除
 * p(P) : 木の先行・中間・後行順序表示
 * v(V) : 木の視覚化表示
 * i(I) : ノードの初期化
 * q(Q) : プログラムの終了
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct  node
{
  int           data;     /* key部分 */
  struct node * left;     /* 左の子ノードへのポインタ */
  struct node * right;    /* 右の子ノードへのポインタ */
};

struct  node * addnode(struct node * pts, int dt, int * flag);
struct  node    ** search(struct node ** pp, int dt);
void delnode(struct  node ** pp);
void pre_tree(struct node * p);
void in_tree(struct node * p);
void post_tree(struct node * p);
void print_tree(struct node * p);
void free_tree(struct node * p);


int
main()
{
  struct  node        head;
  struct  node     ** ppt;
  int                 indt = 0;
  int                 status;
  char                cmd[2];

  cmd[0] = ' ';
  head.left = head.right = NULL;

  while (cmd[0] != 'q' && cmd[0] != 'Q')
  {
    printf("Command ? ");
    scanf("%s", cmd);

    switch (cmd[0])
    {
    case 'a':
    case 'A':
      printf("Append data -> ");
      scanf("%d", &indt);
      head.left = addnode(head.left, indt, &status);
      if (status == -1)
      {
        fprintf(stderr, "Memory Allocation Error\n");
      }
      else if (status == -2)
      {
        fprintf(stderr, "Duplicate key Error\n");
      }
      break;
    case 's':
    case 'S':
      printf("Search data -> ");
      scanf("%d", &indt);
      ppt = search(&head.left, indt);
      if (*ppt == NULL)
      {
        printf("Search Key not found\n");
      }
      else
      {
        printf("Node address = %p\n", *ppt);
      }
      break;
    case 'd':
    case 'D':
      if (head.left == NULL)
      {
        printf("Tree empty\n");
      }
      else
      {
        printf("Delete key -> ");       /* 削除キー入力 */
        scanf("%d", &indt);
        ppt = search(&head.left, indt); /* 削除ノード探索 */
        if (*ppt == NULL)
        {
          printf("Delete key not found\n");
        }
        else
        {
          delnode(ppt);
        }
      }
      break;
    case 'p':
    case 'P':
      if (head.left == NULL)
      {
        printf("Tree empty\n");
      }
      else
      {
        printf("Pre-order  = ");       /* 先行順序訪問 */
        pre_tree(head.left);
        printf("\n");
        printf("In-order   = ");
        in_tree(head.left);
        printf("\n");
        printf("Post-order = ");
        post_tree(head.left);
        printf("\n");
      }
      break;
    case 'v':
    case 'V':
      if (head.left == NULL)
      {
        printf("Tree empty\n");
      }
      else
      {
        print_tree(head.left);
      }
      break;
    case 'i':
    case 'I':
      if (head.left == NULL)
      {
        printf("Tree empty\n");
      }
      else
      {
        free_tree(head.left);
        head.left = NULL;
        printf("Tree initialized\n");
      }
      break;
    default:
      break;
    }
    printf("\n");
  }

  return 0;
}

struct  node *
  addnode(struct node * pts, int dt, int * flag)
{
  struct  node    * ptn;
  if (pts == NULL) /* 葉ノード? */
  {
    ptn = malloc(sizeof(struct node));  /* 新ノードを確保 */
    if (ptn == NULL)
    {
      *flag = -1;
      return pts;
    }
    else
    {
      ptn->data = dt;                 /* データ格納 */
      ptn->left = ptn->right = NULL;  /* 左右ポインタ部に NULL をセット */
      *flag = 0;                  /* 追加完了 */
      return  ptn;
    }
  }
  else if (pts->data == dt)
  {
    *flag = -2;
    return  pts;
  }
  else
  {
    /* ptsノードのKeyと追加Keyを比較して部分木を選択 */
    if (dt < pts->data)  /* 左部分木を探索すべきか? */
    {
      pts->left = addnode(pts->left, dt, flag);   /* 左 */
    }
    else
    {
      pts->right = addnode(pts->right, dt, flag);  /* 右 */
    }

    return pts;
  }
}

struct  node    **
  search(struct node ** pp, int dt)
{
  while (*pp != NULL && dt != (*pp)->data)
  {
    if (dt < (*pp)->data)
    {
      pp = &(*pp)->left;  /* 左部分木へ移動 *//* &((*pp)->left) ということ */
    }
    else
    {
      pp = &(*pp)->right;  /* 右部分木へ移動 *//* &((*pp)->right) ということ */
    }
  }
  return  pp; /* 目的ノードを指すポインタ部のアドレスまたは NULL を返す */
}

void
delnode(struct  node ** pp)
{
  struct  node     * p;
  struct  node    ** qq;
  struct  node     * q;

  if (*pp != NULL)             /* 削除すべきノードあり? */
  {
    p = *pp;                /* 削除ノードのアドレスを p へ代入 */
    if (p->right == NULL)    /* 右部分木なし? */
    {
      *pp = p->left;
      free(p);
    }
    else if (p->left == NULL)
    {
      *pp = p->right;     /* 右部分木と親ノードをリンク */
      free(p);
    }
    else                    /* 削除ノードの左右に部分木がある場合の処理 */
    {
      /* 左部分木中で最大 key を持つノードを探す */
      qq = &p->left;      /* 左ポインタ部のアドレスを qq に得る */
      while ((*qq)->right != NULL)
      {
        qq = &(*qq)->right;
      }
      /* 最大 keyノードの key値を削除ノードに移した後、qノードを解放 */
      q = *qq;      /* 左部分木最大 key ノードアドレスを q にセット */
      *qq = q->left;  /* qノードの左部分木と親ノードをリンク */
      p->data = q->data;  /* qノードの Key値を削除ノード(p)に移す */
      free(q);
    }
  }
}

/* 2分木を先行順序(preorder)で訪問し、ノードの Key値を表示する */
void
pre_tree(struct node * p)
{
  if (p != NULL)               /* ノードあり? */
  {
    printf("%d ", p->data); /* pが指すノードの Key値を表示 */
    pre_tree(p->left);      /* 左部分木へ再帰的に移動 */
    pre_tree(p->right);     /* 右部分木へ再帰的に移動 */
  }
}

/* 2分木を中間順序(inorder)で訪問し、ノードの Key値を表示する */
void
in_tree(struct node * p)
{
  if (p != NULL)               /* ノードあり? */
  {
    in_tree(p->left);       /* 左部分木へ再帰的に移動 */
    printf("%d ", p->data); /* pが指すノードの Key値を表示 */
    pre_tree(p->right);     /* 右部分木へ再帰的に移動 */
  }
}

/* 2分木を後行順序(postorder)で訪問し、ノードの Key値を表示する */
void
post_tree(struct node * p)
{
  if (p != NULL)               /* ノードあり? */
  {
    post_tree(p->left);     /* 左部分木へ再帰的に移動 */
    pre_tree(p->right);     /* 右部分木へ再帰的に移動 */
    printf("%d ", p->data); /* pが指すノードの Key値を表示 */
  }
}

/* 2分木を視覚化して表示する */
void
print_tree(struct node * p)
{
  int             i;
  static  int     indent;

  if (p != NULL)               /* ノードあり? */
  {
    indent += 6;
    print_tree(p->right);   /* 右部分木へ再帰的に移動 */
    for (i = 6; i < indent; i++)
    {
      printf(" ");
    }
    printf("%6d\n", p->data);
    print_tree(p->left);
    indent -= 6;
  }
}

/* 2分木ノードを後行順序で訪問しながら木を初期化する */
void
free_tree(struct node * p)
{
  if (p != NULL)
  {
    free_tree(p->left);
    free_tree(p->right);
    free(p);
  }
}

 

2次元の表を多重連結リスト構造を使って表現したサンプルプログラム

/*
 * Cプログラミングとデータ構造(9.14)
 * 2次元の表を多重連結リスト構造を使って表現したサンプルプログラム
 * m(M) : 表へのデータ追加
 * d(D) : 表からデータ削除
 * p(P) : 表データと件数の表示
 * c(C) : 表の初期化
 * q(Q) : プログラムの終了
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define WIDE    10
#define HIGH    10

struct  parent
{
  int           no;   /* 番号 */
  struct node * next; /* ノードへのポインタ */
};

struct  node
{
  int               data; /* データ部 */
  struct  parent  * p_vp; /* 上方向のヘッドノードへのポインタ */
  struct  parent  * p_hp; /* 左方向のヘッドノードへのポインタ */
  struct  node    * p_vn; /* 下方向のデータノードへのポインタ */
  struct  node    * p_hn; /* 右方向のデータノードへのポインタ */
};

/* algorithm_xylink.c */
int main();
int append(struct parent v_h[],/* 垂直方向のヘッドノード配列 */ struct parent h_h[],/* 水平方向のヘッドノード配列 */ int v_no,/* 垂直方向のヘッド番号 */ int h_no,/* 水平方向のヘッド番号 */ int dt /* 追加データ */);
int delete(struct parent v_h[],/* 垂直方向のヘッドノード配列 */ struct parent h_h[],/* 水平方向のヘッドノード配列 */ int v_no,/* 垂直方向のヘッド番号 */ int h_no /* 水平方向のヘッド番号 */);
int print(struct parent v_h[], struct parent h_h[]);
void initialize(struct parent v_h[], struct parent h_h[]);

int
main()
{
  struct  parent  v_parent[WIDE]; /* 垂直方向のノードヘッド配列 */
  struct  parent  h_parent[HIGH]; /* 水平方向のノードヘッド配列 */
  char                cmd[2];
  int                 v_no = 0; /* ヘッド番号入力用 */
  int                 h_no = 0; /* ヘッド番号入力用 */
  int                 indt = 0;
  int                 ret = 0;
  int                 i = 0;

  cmd[0] = ' ';

  for (i = 0; i < WIDE; i++)
  {
    v_parent[i].no = i;
    v_parent[i].next = NULL;
  }
  for (i = 0; i < HIGH; i++)
  {
    h_parent[i].no = i;
    h_parent[i].next = NULL;
  }

  while (cmd[0] != 'q' && cmd[0] != 'Q')
  {
    printf("Command ? ");
    scanf("%s", cmd);

    switch (cmd[0])
    {
    case 'a':
    case 'A':
      printf("Line number -> ");
      scanf("%d", &h_no);
      printf("Row number -> ");
      scanf("%d", &v_no);
      printf("Append data -> ");
      scanf("%d", &indt);
      ret = append(v_parent, h_parent, v_no, h_no, indt); /* 追加処理 */
      if (ret == -1)
      {
        fprintf(stderr, "Memory Allocation Error\n");
      }
      else if (ret == -2)
      {   /* ヘッド番号異常 */
        printf("Line or Row number error\n");
      }
      else if (ret == -3)
      {   /* すでにノードあり? */
        printf("Node exist in list\n");
      }
      break;
    case 'd':
    case 'D':
      printf("Line number -> ");
      scanf("%d", &h_no);
      printf("Row number -> ");
      scanf("%d", &v_no);
      printf("Delete data -> ");
      scanf("%d", &indt);
      ret = delete(v_parent, h_parent, v_no, h_no);
      if (ret == -1)
      {
        printf("Delete Node Not Found\n");
      }
      else if (ret == -2)
      {
        printf("Line or Row number error\n");
      }
      break;
    case 'p':
    case 'P':
      printf("  ");
      /* 列番号表示 */
      for (i = 0; i < WIDE; i++)
      {
        printf("%4d", i);
      }
      printf("\n");
      ret = print(v_parent, h_parent);
      printf("\nNode Count = %d\n", ret); /* ノード数表示 */
      break;
    case 'c':
    case 'C':
      initialize(v_parent, h_parent);
      printf("List Initialized\n");
      break;
    default:
      break;
    }
    printf("\n");
  }
  return 0;
}

int
append
(
  struct parent v_h[],    /* 垂直方向のヘッドノード配列 */
  struct parent h_h[],    /* 水平方向のヘッドノード配列 */
  int           v_no,     /* 垂直方向のヘッド番号 */
  int           h_no,     /* 水平方向のヘッド番号 */
  int           dt        /* 追加データ */
)
{
  struct  node    * p_new;
  struct  node   ** pp_v;
  struct  node   ** pp_h;

  if (v_no < 0 || v_no >= WIDE || h_no < 0 || h_no >= HIGH)
  {   /* 範囲外のためエラー */
    return -2;
  }
  else
  {
    p_new = malloc(sizeof(struct node));
    if (p_new == NULL)
    {
      return -1;
    }
    else
    {
      /* 垂直方向の終端ノードを発見し新ノードをリンクする */
      pp_v = &(v_h[v_no].next);   /* 垂直ヘッド配列ポインタのポインタ */
      while (*pp_v != NULL)        /* 垂直方向ノードあり? */
      {
        if (((*pp_v)->p_hp)->no == h_no) /* 重複あり */
        {
          free(p_new);
          return  -3;
        }
        else
        {
          pp_v = &((*pp_v)->p_vn);    /* 次のノードへ移動 */
        }
      }
      *pp_v = p_new;          /* 垂直方向終端にリンク */

      /* 水平方向の終端ノードを発見し新ノードをリンクする */
      pp_h = &(h_h[h_no].next);   /* 水平ヘッド配列ポインタのポインタ */
      while (*pp_h != NULL)        /* 水平方向ノードあり? */
      {
        pp_h = &((*pp_h)->p_hn);
      }
      *pp_h = p_new;          /* 水平方向終端にリンク */

      /* 新ノードの処理 */
      p_new->p_vp = &v_h[v_no];   /* 垂直方向ヘッド配列へのポインタ */
      p_new->p_hp = &h_h[h_no];   /* 水平方向ヘッド配列へのポインタ */
      p_new->p_vn = NULL;         /* 垂直方向次ノードへのポインタ */
      p_new->p_hn = NULL;         /* 水平方向次ノードへのポインタ */
      p_new->data = dt;           /* データ格納 */
    }
    return 0;
  }
  return 0;   /* not reached */
}

int
delete
(
  struct parent v_h[],    /* 垂直方向のヘッドノード配列 */
  struct parent h_h[],    /* 水平方向のヘッドノード配列 */
  int           v_no,     /* 垂直方向のヘッド番号 */
  int           h_no      /* 水平方向のヘッド番号 */
  )
{
  struct  node    ** pp_v;
  struct  node    ** pp_h;
  struct  node     * p_node;
  int                no;

  if (v_no < 0 || v_no >= WIDE || h_no < 0 || h_no >= HIGH)
  {   /* 範囲外のためエラー */
    return -2;
  }
  pp_v = &(v_h[v_no].next);   /* 垂直ヘッド配列のポインタ部のアドレスを pp_v にセット */
  while (*pp_v != NULL)
  {
    no = ((*pp_v)->p_hp)->no;   /* 水平方向のヘッド番号を no に得る */
    if (no == h_no)              /* 指示された水平番号と同じ番号か? */
    {
      pp_h = &(h_h[h_no].next);
      while (*pp_h != *pp_v)   /* 水平方向からのサーチ */
      {
        pp_h = &((*pp_h)->p_hn);    /* 次の水平方向ノードへ移動 */
      }
      p_node = *pp_v;         /* 削除ノードのアドレスを p_node に得る */
      *pp_v = (*pp_v)->p_vn; /* 削除ノードを垂直方向のリンクから外す */
      *pp_h = (*pp_h)->p_hn; /* 削除ノードを水平方向のリンクから外す */
      free(p_node);           /* 削除ノードを解放 */
      return  0;
    }
    pp_v = &((*pp_v)->p_vn);    /* 次の垂直方向ノードへ移動 */
  }
  return -1;  /* 指示されたノードが見つからない */
}

int
print(struct parent v_h[], struct parent h_h[])
{
  int             buff[WIDE]; /* 一行分のデータを格納する配列 */
  int             h_pos;      /* 水平方向ヘッド配列ポジショナ */
  int             cnt;        /* ノード数カウント用 */
  int             i;
  struct  node ** pp_h;

  cnt = 0;

  /* 水平ヘッド配列を 0〜HIGH-1 間チェック */
  for (h_pos = 0; h_pos < HIGH; h_pos++)
  {
    for (i = 0; i < WIDE; i++)
    {
      buff[i] = 0;    /* 1行分データ格納配列を初期化 */
    }
    pp_h = &(h_h[h_pos].next);  /* 水平方向の第一ノードを指す */

    while (*pp_h != NULL) /* 連結ノードがある間ループ */
    {
      buff[((*pp_h)->p_vp)->no] = (*pp_h)->data;  /* データの取り出し */
      pp_h = &((*pp_h)->p_hn);    /* 水平方向の次ノードへ移動 */
      cnt++;  /* ノード数カウンタ+1 */
    }
    printf("%2d", h_pos);   /* 行番号表示 */
    for (i = 0; i < WIDE; i++)   /* 1行分(0〜WIDE-1)ループ */
    {
      printf("%4d", buff[i]); /* データを一件表示 */
    }
    printf("\n");
  }
  return  cnt;    /* ノード数を返す */
}

void
initialize(struct parent v_h[], struct parent h_h[])
{
  struct  node    * p_v;
  struct  node    * p_s;
  int               pos;

  for (pos = 0; pos < WIDE; pos++) /* 垂直方向ヘッド配列を 0〜WIDE-1 */
  {
    p_v = v_h[pos].next;        /* 垂直方向の第一ノードのアドレスを得る */
    while (p_v != NULL)          /* 終端ノードか? */
    {
      p_s = p_v->p_vn;        /* 次のノードアドレスを p_s に記憶 */
      free(p_v);
      p_v = p_s;              /* 次のノードへ */
    }
    v_h[pos].next = NULL;       /* pos番目の垂直方向ヘッド・配列ポインタ部初期化 */
  }

  for (pos = 0; pos < HIGH; pos++) /* 水平方向ヘッド配列を 0〜HIGH-1 */
  {
    h_h[pos].next = NULL;       /* 水平方向ヘッド配列ポインタ部初期化 */
  }
}