2 リスト

　　 2.2 一方向リスト
　ここでは、構造体を使った連結リストの一つである一方向リストの操作方法について説明します。一方向リストとは、リストになっているデータを参照するときに先頭から順に後ろのデータをたどることはできるけれど、あるデータよりも前のデータへはたどることができないものです。つまり、あるデータは次のデータの場所を知っているのみで、自分の場所を知っているデータがどこにあるかは分からないという構造になっています。

一方向リストのイメージ

　このようなリストの操作を行う方法について説明します。ここでは例として名前と電話番号のリストを考えます。具体的には次のような自己参照的構造体によって一方向リストを構成します。 
typedef struct name_tag{
　char name[10];
　double phone;
　struct name_tag *next;
} name_t;
　また連結リストの一つの要素となるデータのまとまり(構造体)をノード(node)またはセル(cell)と呼びます。上の図の場合には5つのノードが存在することになります。

　またここでは各ノードは"malloc"関数によるメモリ領域を確保してから利用するものとします。 　一連の手順をCで実現すると次のようなプログラムになります。 
#include <stdio.h>
#include <stdlib.h> /* malloc */
#include <string.h> /* strcpy */


/*** name_t 型(ノード)の宣言 ***/
typedef struct name_tag{
　 char name[10];           /* 名前 */
　double phone;            /* 電話番号 */
　struct name_tag *next_p;  /* 次のノードへのポインタ */
} name_t;

/*** プロトタイプ宣言 ***/
name_t *add_node(name_t *fow_p); /* ノードの追加 */
void list(name_t *top_p);        /* リストの参照(一覧表示) */


/*** main 関数 ***/
int main(void){

　 name_t *top_p = NULL; /* リストの先頭用のポインタ変数(NULL で初期化) */
　name_t *ref_p;        /* 参照用のポインタ変数 */
　name_t *tmp_p;        /* 一時記憶用のポインタ変数 */
　int i, num;

　/*** リストの作成(3 人分のデータを入力) ***/
　 for (i=0; i<3; i++){
　　top_p = add_node(top_p);
　}

　/*** リストの参照 ***/
　list(top_p);

  /*** ノードの挿入 ***/
　 num = 2;  /* num 番目のノードの後に挿入 */
　printf("===== input node after %d node =====\n", num);
　ref_p = top_p;
　 for (i=0; i<num-1; i++){
　　ref_p = ref_p->next_p;
　}
　ref_p->next_p = add_node(ref_p->next_p);

　/*** リストの参照 ***/
　list(top_p);


  /*** ノードの削除 */
　 num = 3;  /* num 番目のノードを削除 */
　printf("===== delete %d node =====\n", num);
　ref_p = top_p;
　for (i=0; i<num-2; i++){
　　ref_p = ref_p->next_p;
　 }
　tmp_p = ref_p->next_p;         /* 削除するノードのアドレス */
　ref_p->next_p = tmp_p->next_p;
　free(tmp_p);                   /* メモリの開放 */

　/*** リストの参照 ***/
　list(top_p);
}


/*** ノードの作成 ***/
name_t *add_node(name_t *fow_p){
  name_t *new_p; /* 新規のノード用のポインタ変数 */

　/*** メモリ領域の確保 ***/
　 new_p = (name_t *)malloc(sizeof(name_t)); /* 先頭のノード作成 */

　/*** データの入力 ***/
　printf("===== make new node =====\n");
　printf("input name: ");
　 scanf("%s", new_p->name);
　printf("input phone: ");
　scanf("%lf", &new_p->phone);
　new_p->next_p = fow_p;

　/*** 新しいノードのポインタを返す ***/
　return new_p;
}

/*** リストの参照 ***/
void list(name_t *ref_p){

　printf("===== Data list =====\n");
　while(ref_p != NULL){   /* 最後のノードになるまで繰り返す */

　　/*** ノードデータの表示 ***/
　　printf("name: %s: %.0f\n", ref_p->name, ref_p->phone);
　　ref_p = ref_p->next_p;  /* 次のノードへ移動 */
　}
}

2003年11月15日 16:50 更新