[Previous: 3 リストを使わない方法] [Up: リスト] [Next: 5 練習問題]
Subsections

4 リストを使う方法

4.1 配列とリストとの違い

リストと配列はともにデータの列をメモリーに確保するという点では似ている．ここで話 を簡単にするために，データは整数とする．データは整数の数列である．配列の場合，こ の数列はメモリーの連続した領域に格納される．そして，配列の添え字を使って，目的の データにアクセスする.

それに対して，リストは前後のデータのある位置をメモリーに入れておく．それを元に数 列を構成する．

ここのところの図は，本日間に合わなかったので，来週渡す．

4.2 リストを使ったプログラム

4.2.1 原理

データを入力する毎に，新たにノードを作成して，そのノードにデータを格納している． 前後のデータの関係は，リストを用いて表現している．

4.2.2 フローチャート

教科書のList 2-1(p.37)あるいはこのプリントのリスト1のプログラム のフローチャートを図1に示す．
図 4: リストを使ったプログラムのリスト4のフローチャート．
\includegraphics[keepaspectratio,scale=0.85]{figure/flow_4.eps}

4.2.3 プログラム

固定長の配列を使うプログラムのリスト4に示す．これは，教科書の List 3-4(p.75-77)と同じである(転載について)．

このプログラムで使われている主なテクニックは，以下の通りである．


リスト4 リストを使っ たプログラム(転載について)

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 
   4 /* リストの要素（ノード）を表す構造体 */
   5 typedef struct tagListNode
   6 {
   7     struct tagListNode *prev;    /* 前の要素へのポインタ */
   8     struct tagListNode *next;    /* 次の要素へのポインタ */
   9     int data;   /* この要素がもっているデータ */
  10 } ListNode;
  11 
  12 int main(void)
  13 {
  14     int buf,sum;
  15     ListNode *firstnode,*lastnode,*newnode,*thisnode,*removenode;
  16 
  17     firstnode=lastnode=NULL;
  18 
  19     do
  20     {
  21         printf("整数を入力してください（0を入力すると終了）:");
  22         scanf("%d",&buf);
  23         if(buf)     /* 新たな入力があったら */
  24         {
  25             /* 新しいノードを作成 */
  26             newnode=(ListNode*)malloc(sizeof(ListNode));
  27             newnode->data=buf;
  28             newnode->next=NULL;
  29 
  30             if(lastnode!=NULL)
  31             {
  32                 /* すでにあるリストの末尾に
  33                    新しいノードをつなげる */
  34                 lastnode->next=newnode;
  35                 newnode->prev=lastnode;
  36                 lastnode=newnode;
  37             }
  38             else
  39             {
  40                 /* これが最初の要素だった場合 */
  41                 firstnode=lastnode=newnode;
  42                 newnode->prev=NULL;
  43             }
  44         }
  45     } while(buf != 0);
  46 
  47     /* 合計値を算出 */
  48     printf("--入力されたのは以下の数です--\n");
  49     sum=0;
  50     for(thisnode=firstnode;thisnode!=NULL;
  51                                 thisnode=thisnode->next)
  52     {
  53         printf("%d\t",thisnode->data);
  54         sum+=thisnode->data;
  55     }
  56     printf("\n----\n以上の数の合計値は%dです。\n",sum);
  57 
  58     /* リストの全ノードを削除 */
  59     for(thisnode=firstnode; thisnode!=NULL;)
  60     {
  61         removenode=thisnode;
  62         thisnode=thisnode->next;
  63         free(removenode);
  64     }
  65 
  66     return EXIT_SUCCESS;
  67 }

4.3 リストと配列の違い


表 1: 配列とリストとの違い
  配列 リスト
データへのアクセス 添え字によるランダムアクセス可能 リストを順にたどる
アクセスのための計算量 $ O(1)$ $ O(N)$
データの挿入/削除 計算コスト大($ O(N)$ ) 計算コスト小($ O(1)$ )
メモリーのコスト 小 配列より大

[転載について]
このペー ジ中のリスト4のプログラムは，教科書として使用している以下の書籍
書名プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8
著作者紀平拓男・春日伸弥
出版社ソフトバンク　パブリッシング株式会社
から転載しました．この転載に関しては，著者と版元に許諾を得ています．




[Previous: 3 リストを使わない方法] [Up: リスト] [Next: 5 練習問題]
[Top:ページの先頭に戻る]

ホームページ: Yamamoto's laboratory
著者: 山本昌志
Yamamoto Masashi
2005-11-21

no counter