リスト構造の追加と削除(1)

[教材トップへ] [次の課題へ]


演習内容

追加と削除(1)

リスト構造を作成するプログラムを作り,リスト構造の基本を把握する.


基本事項の説明

リストとは

データ部とポインタ部からなるデータを鎖状につなげたデータ構造をリスト(線形リスト)という.リストの各要素は次の要素の場所を示す(ポインタを持つ).
基本課題では線形リストを実現する.

自己参照的構造体

リストの要素をノード(node)と呼ぶ.C言語ではノードを次のような構造体で表現するとよい.
(ただし,下のソースは,課題データをリストに格納する場合を想定している)

   typedef struct _node{
     char index[StrSIZE];                       /* 見出し文字列を格納する配列 */
     int num;                                /* 特徴の数を格納する変数 */
     char attr[ATTR_NUM][StrSIZE];              /* 特徴を格納する配列 */
     struct _node *next;                        /* 後のデータを指すポインタ部 */
   } node;

このように自分自身の構造体へのポインタ(上の例の下線部)を持つ構造体を自己参照的構造体と呼ぶ.

記憶領域の取得

リストと配列の記憶領域の扱いを比較してみると.配列は,コンパイル時にそのサイズを固定してしまうやり方で記憶領域を取得する(静的記憶領域割当).これに対して,リストでは,データのサイズがどんどんと膨れ上がって行く性質を持っているので,上記のような静的な記憶割り当てでは都合が悪い.そこで,必要なときに必要なサイズの領域を取得するやり方で記憶領域を取得する(動的記憶領域割当)が有効となる.
動的な記憶割り当てでは,動的記憶(メモリ)取得関数 malloc を用いて,struct _node型のデータ領域を取得する関数 talloc を定義する(下記参照).このとき,動的記憶(メモリ)を取得する記憶(メモリ)領域を,特に,ヒープ領域と呼ぶ.ヒープ領域については後で木構造を習得する際に詳しく説明がある(と思う).

   node *talloc(void)
   {
     return((node *)malloc(sizeof(node)));   /* node型ポインタへのキャストとnode型のメモリ領域の計算 */
   }

この関数を用いて,

  struct _node *ptr;
  ptr = talloc();

あるいは

   node *ptr;
   ptr = talloc();

のようにポインタ変数 ptr を宣言すると,node(struct _node)型のデータ領域が新たに取得されて,その領域を指すポインタが ptr に返される.
このとき,ポインタを用いた構造体メンバは以下のように参照できる.

ptr->index ・・・ 1番目の構造体メンバを参照
ptr->num ・・・ 2番目の構造体メンバを参照
ptr->attr ・・・ 3番目の構造体メンバを参照
ptr->next ・・・ 次のノードを参照





課題

基本課題(必須)''' 課題ID L-1A

* 課題ファイルからデ−タを読み込み,リスト構造として構成するプログラムを作成せよ.
* 配列とリスト構造を比較し,それぞれのメリットとデメリットについて考察せよ.


課題ファイル

課題ファイル中のデ−タは,ひと組の各要素がカンマで区切られて格納されている.このようなカンマ区切りデータをCSVデータと呼ぶ.
データの内容は,あるものの顕著な特徴をデータベース化したものである.

   雲,白い,軽い,ふわふわした,流れる
   ヒマワリ,大きい,黄色い,高い,綺麗な,可愛い

※「,」で区切られた各要素を構造体に格納し,ポインタで繋げるようにする.

プログラムの要求仕様
  • STEP1 ファイルdata1(ここからダウンロードする)を読み込む.

  • STEP2 読み込んだデータを解析し,リスト構造を作成する.作成されるリスト構造の各ノードでは

  index(見出し)
  num(登録されたattr1,attr2,..の数)
  attr(登録するattr1,attr2,...の見出し)
  *next(次のノードへのポインタ)

を格納する(基本的な実装イメージ).
attrに対応付けられるデータattr1, attr2, ... の格納は通常の配列を用いても実現可能であるが,attrの個数が不定の場合は対応が難しい.少し工夫をするならば二次元配列を用いるとよい.

  • STEP3 作成したリスト構造を読み出して表示する.

  • STEP4 メニュー(「追加」と「終了」)を表示して入力待ちとなる.

   > a.out* data0000.csv
   index        attr1   attr2   attr3   attr4   attr5   ・・・
   雲    白い      軽い      ふわふわした  流れる
   ヒマワリ 大きい     黄色い     高い      綺麗な     可愛い
   MENU: 1. 追加  2. 終了
   メニューの数字を入力して下さい:
  • STEP5 メニュー「1.追加」が選択されたら,STEP6へ進む.メニュー「2.終了」が選択されたらSTEP8へ進む.

  • STEP6 キーボードからの入力を受け付ける.読み込んだデータを解析し,リスト構造を作成する.入力データは,index,attr1,attr2,...である.
    作成されるリスト構造は,index,num(attr1,attr2,...の数),attr(attr1, attr2,...の見出し),next(次のノードへのポインタ),となる.
    入力は,data2(ここを参照する)に書かれてある語を用いる.

    • 書かれてある語を入力 → 構造体メンバ(見出し語)に格納
    • その語の特徴を思い浮かべて順に入力 → 構造体メンバ(attr1)のリスト構造として格納する.特徴は思いつく限り入力する(最大10個: attr1, attr2, ..., attr10)
    • 1. に戻る
  • STEP7 STEP3へ戻る.

MENU: 1. 追加  2.終了
メニューの数字を入力して下さい: 1
index に登録する文字列を入力して下さい: パイン
 「パイン」 を受け付けました。
さらに入力しますか? (y/n)  y
attr1 に登録する文字列を入力して下さい: 甘酸っぱい
 「甘酸っぱい」 を受け付けました。
さらに入力しますか? (y/n)  y
attr2 に登録する文字列を入力して下さい: 丸い
 「丸い」 を受け付けました。
さらに入力しますか? (y/n)  y
attr3 に登録する文字列を入力して下さい: 大きい
 「大きい」 を受け付けました。
さらに入力しますか? (y/n)  n
登録されているデータを表示します。

index   attr1   attr2   attr3   attr4   attr5   ・・・
雲       白い      軽い      ふわふわな   流れる             
ヒマワリ    大きい     黄色い     高い      綺麗な     可愛い     
パイン     甘酸っぱい   丸い      大きい                     
夜       暗い      怖い      寂しい     静かだ             
ネズミ     小さい     すばしこい   可愛い                     
会議      長い      真剣な                             
大学祭     楽しい     賑やかな                            
MENU: 1. 追加  2.終了
メニューの数字を入力して下さい: 2
登録されているデータを保存します。
保存ファイル名を入力して下さい: data_2.csv
保存しました。
終了します。
  • STEP8 「終了」メニューが選択された場合,リスト構造をファイルに書き出し,プログラムを終了する.
    書き出したファイルは次の演習時に入力データとして読み込むので,csv形式で書き出しておくこと.



応用課題(1) ・・ 難易度★★ ・・ 課題ID L-1B

* リスト構造に付与するポインタを増やし,双方向リストを実現せよ.(実装イメージ
* 双方向リストによる実装を,線形リストによる実装と比較し,そのメリットとデメリットについて考察せよ.



応用課題(2) ・・ 難易度★★★ ・・ 課題ID L-1C

* attrに対応する複数の見出しの格納を,リスト構造の二重化によって実現せよ.
* リストの二重化による実装のメリットとデメリットについて考察せよ.


プログラムの要求仕様

基本的な処理の流れは基本課題と同じである.以下,リストの二重化によって差異の生じる部分のみを示す.

  • STEP2 読み込んだデータを解析し,リスト構造を作成する.作成されるリスト構造(1)の各ノードでは

      index(見出し)
      num(登録されたattr1,attr2,..の数)
      *attr(登録されたattr1,attr2を格納するリスト構造へのポインタ)
      *next(次のノードへのポインタ)
     

    を格納する.*attrに対応付けられるデータattr1, attr2, ... は,実際にはリスト構造(2)に格納される.
    作成されるリスト構造(2)の各ノードでは

      attrn(n<10)(登録されるattr1,attr2)
      num(ノード番号)
      *index(リスト構造(1)へのポインタ)
      *next(次のノードへのポインタ)
     

実装イメージ

  • STEP3 作成したリスト構造を読み出して表示する.

  • STEP4 メニュー(「追加」と「終了」)を表示して入力待ちとなる.

   > a.out* data0000.csv
   index        attr1   attr2   attr3   attr4   attr5   ・・・
   雲    白い      軽い      ふわふわした  流れる
   ヒマワリ 大きい     黄色い     高い      綺麗な     可愛い
   MENU: 1. 追加  2. 終了
   メニューの数字を入力して下さい:
  • STEP5 メニュー「1.追加」が選択されたら,STEP6へ進む.メニュー「2.終了」が選択されたらSTEP8へ進む.

  • STEP6 キーボードからの入力を受け付ける.読み込んだデータを解析し,リスト構造を作成する.入力データは,index,attr1,attr2,...である. 作成されるリスト構造は,index,num(attr1,attr2,...の数),attr(attr1, attr2,...リスト構造へのポインタ),next(次のノードへのポインタ),となる.入力は,data2(ここを参照する)に書かれてある語を用いる.

    • 書かれてある語を入力 → 構造体メンバ(見出し語)に格納
    • その語の特徴を思い浮かべて順に入力 → 構造体メンバ(attr1)のリスト構造として格納する.特徴は思いつく限り入力する(最大10個: attr1, attr2, ..., attr10)
    • 1. に戻る


補足情報

双方向リスト
  • 線形リストに付与されている後ろ向きのポインタに加えて,前向きのポインタを付与したもの.ソートやサーチを効率よく行う際に有効な場合が多い.(双方向リストの実装イメージ)


動的記憶領域割当のプチ知識
  • 上記の説明では動的記憶領域確保に malloc 関数を用いたが,より汎用的なプログラムとして記述した場合は,少し高級な calloc 関数を使う方法がある.

  node *talloc(void)
  {
    return((node*)calloc(1, sizeof(node)));
  }


初期ノード作成時のプチ知識
  • 本課題では,初期データとしてタイトル行となるデータを読み込んでリスト構造を作成するため,特に先頭ノードを特別扱いする必要はない.しかし,一般には初期データなしでリスト構造を作成する場合も少なくない.このような場合,先頭ノードと末尾ノードの扱いには少々気をつけなければいけない.先頭ノード(head)や末尾ノード(tail)を指すポインタを作るには下記のようにすればよい.

     typedef struct{
        node *head;
        node *tail;
      } cont_node;

ダミーノードを作る場合,以下のような関数を作っておけばよい.

     void init_node( cont_node *cont )
      {
        cont->head = cont->tail = talloc();
        }


その他参考となりそうな情報


提出要綱

基本課題の提出
  • 基本課題内容を実装し,実装プログラムの出力画面および指示された考察結果を提出のこと.
    出力画面とは,STEP8で保存するcsvファイルである.

応用課題果の提出
  • 応用課題内容を実装したものは,これを(基本課題とは別に)提出してもよい.この場合は実装プログラムを提出すること.
  • 提出期限: 今週金曜日午後8時
  • 注意事項: 提出メールでは件名(Subject)に必ず課題ID,学籍番号,氏名を付与すること.
    • 提出メールでは件名(Subject)に必ず課題ID,学籍番号,氏名を付与して下さい.
      課題IDが正しく付与されていない場合は提出と見做しません.

      • Subject: [THEME-5-L-1A] 06012345 赤星憲広

      メール本文の最初には以下の情報を付与すること.
      • 授 業 名: 上級プログラミング演習II
        演習テーマ: リスト構造によるデータ管理
        実 施 日: 第 1 週目,2008 年 11 月 10 日
        報告年月日: 2007 年 11 月 14 日
        報 告 者: 06012345,平野恵一

        ※太字の部分は各自該当する情報を記入すること

※電子メールの提出先は,他のテーマと同じ adv-programming[at]info.mie-u.ac.jp である.([at]はアットマークの意味)


[教材トップへ] [次の課題へ]

Recent