第９回目 線型リスト（6/5）

今日のキーワード

• 数のリスト
• リストを辿る

■線型リストとは

• データサイズが固定、
• データ系列の途中に新たなデータを挿入しにくい、

• データを次々と追加することができる（mallocの許す限り可能）、
• データの系列の途中に追加することが容易、

• n番目のデータを直接参照することができない
  （n-1個のデータを辿らなければ参照できない）

□基本構成

■数の線型リスト

数の線型リストの使用例 ⇒ list0901.c

プログラム list0901.c の動きは以下のイメージのとおりである。

□演習１

list_make_node を使い、main 関数を参考にしながら、push 動作を行う関数 void list_push(Node *root, int num); を作成せよ。なお、メイン関数は以下のとおりとなる。⇒ prac0901.c

main()
{
  Node root, *p;
  int n, i;

  root.next = NULL;
  for( i = 0; i < 10; i ++ ){
    printf("数を入力して下さい: ");
    scanf("%d", &n);
    list_push( &root, n );
  }    
  list_print( &root );
}

□演習２

pop 動作を行う関数 int list_pop(Node *root); は、上述の図において、(10)の状態から、(9)の状態に変化させ、c の値を return 値とすれば良い。list_pop() を作成せよ。⇒ prac0902.c また、それができた人は、pop で取り除かれたノードを free せよ。⇒ prac0903.c なお、メイン関数は以下のとおりとなる。

main()
{
  Node root, *p;
  int n, i;

  root.next = NULL;
  for( i = 0; i < 10; i ++ ){
    printf("数を入力して下さい: ");
    scanf("%d", &n);
    list_push( &root, n );
  }

  while( root.next != NULL ){
    printf("%d\n", list_pop( &root ));
  }
}

□演習３

リスト構造を操作する際、必ずしも pop 操作をする必要はない。 たとえば、list0901.c の関数 list_print () のように、next を次々と辿ってよい。 リスト内の数の合計値を計算する関数 int list_sum(Node *); を作れ。⇒ prac0904.c なお、メイン関数は以下のとおりとする。それから、list_print によりリストが壊れていないことを確認せよ。

main()
{
  Node root, *p;
  int n, i;

  root.next = NULL;
  for( i = 0; i < 10; i ++ ){
    printf("数を入力して下さい: ");
    scanf("%d", &n);
    list_push( &root, n );
  }
  printf("%d\n", list_sum( &root ));
  list_print(&root);
}

■ 宿題

list0901.c の Node の構造体の定義を強化することで、数以外のデータを格納するリストを作ることができる。名前を格納する文字列型変数 char name[MAX_NAME];、および、年齢を格納する整数型変数 int age; を持つ Node を作れ。メイン関数では、10人の名前と年齢のデータを標準入力より入力し、list_push によりリスト構造に蓄積する。そして、最後に、list_print により全員の名前と年齢を表示する。以上を実現するために、list0901.c の list_push、list_print などを改造せよ。なお、メイン関数は以下のようにする。⇒ prac0905.c

main()
{
  Node root, *p;
  int age, i;
  char buff[BUFSIZ];
  char name[BUFSIZ];

  root.next = NULL;
  for( i = 0; i < 10; i ++ ){
    fgets(buff,BUFSIZ,stdin);
    sscanf(buff,"%s %d", name, &age);
    list_push( &root, name, age );
  }
  list_print(&root);
}

ヒント： 「int val;」の代わりに「char name[MAX_NAME]; int age;」をメンバ変数とすれば良い。