第 11 回線形リスト

本日の内容

11-1. 線形リスト
11-2. 双方向リスト

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

11-1. 線形リスト

配列の問題点

複数のデータを扱うのに従来は配列を使用してきました。これはあらゆるプログラミング言語に存在するデータ形式です。メモリーのある区画に連続してデータを配置し、添字を利用してデータにアクセスします。しかし、配列は前もって領域を確保する必要があるため、未知のサイズのデータを取り扱うことができません。また、そのため、コンピュータのメモリ量に応じて処理を行なうこともできません。

未知の容量のデータ対してメモリの使用量を制御するためには、新たなデータ構造を使用する必要があります。そのためには、まとめて大きな領域を確保するような記憶方法ではなく、データ一つずつに対して、一つずつメモリ領域を確保するような記憶法が必要となります。

線形リストの操作

線形リストとは図のような特殊な二分木です。

これを計算機上で取り扱うには通常、左の値が入る葉とそうでないノードを結合し、頂点に値が入るものとして扱った方が便利です。つまり次の図のようにして実現するのが便利です。

このような構造を作るに動的なメモリの確保をする必要があります。まず各ノードに対応する構造体を定義します。


typedef struct lst {
  struct lst *next;
  char item;
} LIST;

まず、LIST型の変数を利用して、線形リストを表現することを考えます。管理変数はLISTのポインタ型で、各データを表現しているのをLIST型の変数で表します。すると、次のように表せます。


LIST* kanri;
LIST a,b,c,nil;

a.item='a';
b.item='b';
c.item='c';
nil.next=NULL;

kanri=&a;
a.next=&b;
b.next=&c;
c.next=&nil;

これで、図と同等の線形リストを表現できました。

次に、この線形リストに対して、データを順に取り出すことを考えます。線形リストは、途中から見ても線形リストの構造になってますから、再帰的なプログラムを組むことができます。つまり、データを取り出すには次のようなアルゴリズムを考えれば良いことになります。

データの終端であれば終了する
注目しているデータを取り出す
残りの部分を再帰的に取り出す

例えば、各文字を一行ずつ表示するshow(LIST* p)関数は次のように作れます。


void show(LIST* p){
  if(p->next == NULL) return;
  printf("%c\n", p->item);
  show(p->next);
}

次に、データ一つ一つに対して、この構造体を作り、データを入れることを考えます。そのためには、ポインタで、次のデータの入っている位置を管理します。そうすることで、あらかじめデータの数を決めず、いくつでもデータを取り扱うことができます。そのため、この構造体を malloc を利用してメモリ上に作り、ポインタの操作でこの線形リスト構造ができるようにします。

例えば、要素を a, b, c の順に与えて、上の図のような線形リストを作ることを考えます。つまり、メインルーチンでは add('a'), add('b'), add('c') を順番に呼び出すだけで上の構造を作ることを考えます。つまり、 add を呼び出すたびに次のようにリストが作られていきます。

そのために、 add() が何をするかを考えます。 add() として次のような処理が考えられます。

nil のノードを探す。
nil のノードの直前に、指定された値が含まれるノードを追加する。

但し、ノードを追加するのに、新たに作ったノードに指定された値を入れ、nil ノードの直前にあった頂点のポインタ(図の赤い矢印)を変更する必要があります。これは nil ノードの前の頂点を覚える必要があります。また、管理変数を変更する必要があるため、管理変数のポインタを関数に渡すことになったります。

しかし、次のようにするとそのような複雑な状況を解消できます。それは、nil 頂点にデータを入れ、新しく nil 頂点を作るという方法です。この方法だと、もともとの nil 頂点だけに注目して全ての作業ができます。この方法で作成したのが以下のプログラムです。


#include <stdio.h>
#include <stdlib.h>
typedef struct lst {
  struct lst *next;
  char item;
} LIST;
LIST* newnode(void){
   LIST *p;
   p=malloc(sizeof(LIST));
   if(p!=NULL){
     p->next=NULL;
     p->item='\0';
   }
   return p;
}
LIST* add(LIST *p,char c){
  while(p->next != NULL){
    p= p->next;
  }
  if((p->next=newnode())!=NULL){
    p->item=c;
  }
  return p;
}
void show(LIST* p){
  if(p->next ==NULL)return;
  printf("%c\n",p->item);
  show(p=p->next);
}
void delnode(LIST* p){
  if(p!=NULL){
    delnode(p->next);
    free(p);
  }
}
int main(void){
  LIST *pointer;
  if((pointer=newnode())==NULL){
    fprintf(stderr,"メモリを確保できませんでした\n");
    return 1;
  }
  if((add(pointer,'a')!=NULL) &&
     (add(pointer,'b')!=NULL) &&
     (add(pointer,'c')!=NULL)){
     show(pointer);
  }
  delnode(pointer);
  return 0;
}

このプログラムで add 関数が && でつながれています。 C 言語の && 演算子は左から値を解釈していきます。但し、途中で 0 を発見したらそれ以降の解釈は止めます。したがって、この例ではもし途中で add が NULL を返してきたら、それ以上他の add は行なわれず、式全体の値が偽(0)に確定します。つまり if 文として指定した処理は行われないことになり、メモリーオーバ時の正しい対処になります。

なお、このような先に入れたものを先に出力するような記憶方式を先入れ先出し方式(First In First Out FIFO) と言います。一方、これとは逆に先入れ後出し方式(First In Last Out FILO)の記憶方式をスタックと言います。これは次回に講義します。

なお add 関数、show 関数は再帰処理を使うと次のようにも書けます。


LIST* add(LIST *p,char c){
  if(p->next != NULL){
    return add(p->next,c);
  }
  if((p->next=newnode())!=NULL){
    p->item=c;
  }
  return p;
}
void show(LIST *p){
  if(p->next == NULL){
    return;
  }
  printf("%c\n",p->item);
  show(p->next);
}

演習11-1

上で定義した線形リストに対して、文字列を入れられるように改造しなさい。 add のプロトタイプ宣言は次のようになります。


LIST* add(LIST *p, char *s)

そして次のプログラムを動かしなさい。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* LIST の定義群 */
int main(void){
  LIST *list;
  if((list=newnode())==NULL){
    fprintf(stderr,"メモリを確保できませんでした\n");
    return 1;
  }
  if((add(list,"abc")!=NULL) &&
     (add(list,"def")!=NULL) &&
     (add(list,"ghi")!=NULL)){
     show(list);
  }
  delnode(list);
  return 0;
}

演習11-2

テキストファイルをそのまま線形リストにしまい、出力時に行を逆順に表示するプログラムを作りなさい。

ヒント

ファイルを一行ずつ読み込むプログラムを作ります。


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SIZE 80
char buffer[SIZE+1];
int main(void){
  int c;
  int i=0;
  char filename[]="input.txt";
  FILE *fh;
  if((fh=fopen(filename,"r"))==NULL){
    fprintf(stderr,"ファイル %s がありません。\n",filename);
    return 1;
  }
  while((c=getc(fh))!=EOF){
    if(c=='\n'){
      buffer[i]='\0';
      printf("%s\n",buffer);
      i=0;
    }else{
      if(i>=SIZE){
        fprintf(stderr,"一行の長さを越えました。\n");
	return 2;
      }
      buffer[i++]=c;
    }
  }
  return 0;
}

文字へのポインタをしまえる線形リストを作り、一行毎に線形リストに貯めるようにプログラムを変更します。ここで、 buffer は繰り返し使うので、線形リストの要素としてアドレスを渡すわけには行きません。そこで、新たな領域を作り、同じ文字列をコピーする関数 strdup を使います。
```
    if(c=='\n'){
      buffer[i]='\0';
      add(pointer,strdup(buffer));
      i=0;
    }else{
```

そして線形リストを逆順に出す仕組みを考えます。次のように再帰を利用した reverseshow 関数を作るとうまくいきます。


void reverseshow(LIST *p){
  if(p->next == NULL){
    return;
  }
  reverseshow(p->next);  /* 始めに後ろを表示させてから */
  printf("%s\n",p->item);/* ポインタの位置の行を表示する */
}

参考

なお、文字列へのポインタを入力として、新しい領域に内容をコピーしてその領域へのポインタを返す関数 strdup() を使うと上の処理は次のように簡単になります。


#include <string.h>
char buffer[81]; /* 文字数+1 */
while(ファイルの終りまで){
  bufferに一行(最大80文字)読む;
  add(strdup(buffer));
}

buffer と呼ばれる領域の先頭番地は変化しないため、 add(buffer) では毎回同じ番地が登録されてしまうことに注意して下さい。

参考

fgets(読み込み用バッファの番地, 文字数, ファイルハンドル) 関数を使うと一行をまとめて読み込むことができます。但し、文字数分だけいっぱいに読んでしまったかどうかは最終文字が改行記号かどうかで判定する必要があります。

線形リストの効率化

前述の線形リストの add は毎回 nil の位置を最初から検索していました。でも、これは覚えておけば検索する必要はありません。そこで、先頭のノードの位置と、nil の位置両方を覚えるようにします。この二つの管理変数を一つの変数で取り扱うようにするため、管理変数自体も構造体にします。今まで LIST と呼んでいたデータを入れる部分を NODE と呼ぶことにし、新たに管理変数二つの入った構造体を LIST と呼ぶことにします。すると下記のようなプログラムになります。このようにすると、全体のデータ量とは無関係に一定時間でデータの追加ができます。


#include <stdio.h>
#include <stdlib.h>
typedef struct node {
  struct node *next;
  char *data;
} NODE;
typedef struct list {
  NODE *top,*bottom;
} LIST;
LIST* newlist(void){
  LIST* l;
  NODE* n;
  if((l=malloc(sizeof(LIST)))==NULL){
    return NULL;
  }
  if((n=malloc(sizeof(NODE)))==NULL){
    free(l);
    return NULL;
  }
  n->next=NULL;
  n->data=NULL;
  l->top=l->bottom=n;
  return l;
}
int add(LIST *list, char *value){
  NODE *newnode;
  if((newnode=malloc(sizeof(NODE)))==NULL){
    return 0;
  }
  newnode->next=NULL;
  list->bottom->next=newnode;
  list->bottom->data=value;
  list->bottom=newnode;
  return 1;
}
void show(LIST *list){
  NODE *p;
  for(p=list->top; p!=list->bottom; p=p->next){
    printf("%s\n",p->data);
  }
}
void dellist(LIST *list){
  NODE *p,*q;
  p=list->top;
  do{
    q=p;
    p=p->next;
    free(q);
  }while(p!=NULL);
  free(list);
}
int main(void){
  LIST *list;
  list=newlist();
  if(list!=NULL){
    add(list,"abc");
    add(list,"def");
    add(list,"ghi");
    show(list);
    dellist(list);
  }
  return 0;
}

補足 C++ での線形リスト

C++ では Standard Template Library (STL) により線形リストを提供しています。線形リストの(オブジェクト)変数の定義をした後、「変数名.操作()」という書式で操作します。また、ポインタを制限した形のイテレータ(反復子)という概念が導入され、リスト上の操作はイテレータを使用して行われます。例えば、一番最初の例と同じプログラムを C++ で実現させると次のようになります。なお C++ ではシステムの提供するものには std:: をつける必要があります。


#include <iostream>
#include <list>
int main(){
  std::list<char> l;
  l.insert(l.end(),'a');
  l.insert(l.end(),'b');
  l.insert(l.end(),'c');
  for(std::list<char>::iterator i=l.begin(),e=l.end();
      i!=e; i++){
    std::cout << *i << std::endl;
  }
  return 0;
}

11-2. 双方向リスト

双方向リストとは、次の頂点へのポインタと前の頂点へのポインタの両方を保持するものです。特定の頂点に注目して処理する場合に便利です。エディタなど、特定の行に注目した処理をするのに用いられます。実は C++ の list は双方向リストです。 C++ では Iterator に対して -- 演算が可能です。

演習11-3

双方向リストを使って less を作りなさい。 less とは more を拡張したコマンドで、次の動作をします。

ファイル名をコマンドラインで指定します。
ファイル名からファイルをオープンし、ファイルを読み込みます。
先頭の 24 行を表示します。
空白か d の入力で次の 24 行を表示します。
u の入力で前の 24 行を表示します。
q の入力で終了します。
< で先頭へ、 > で最後(から 24 行前)へ注目行を移動します。


int main(int argc, char *argv[]){
   FILE *input;
   BLIST *bl;
   char c;
   bl=newnode();
   /*ファイル名のチェック*/
   /*ファイルのオープン*/
   readfile(input,bl);
   firstline(bl);
   show();
   while((c=getchar())!='q'){
     switch(c){
     case ' ': case 'd': addline(bl,24); break;
     case 'u': addline(bl,-24); break;
     case '<': firstline(bl); break;
     case '>': lastline(bl); break;
     default: continue;
     }
     show();
  }
  fclose(input);
  return 0;
}

付録 C 言語での双方向リストの実装


#include <stdio.h>
#include <stdlib.h>
typedef struct blst {
  char *item;
  struct blst  *next;
  struct blst  *previous;
} BLIST;
void add(BLIST *base, BLIST *pointer, char *i){
  BLIST *newnode;
  if((newnode=malloc(sizeof(BLIST)))==NULL){
    fprintf(stderr,"メモリーを確保できませんでした\n");
    exit(2);
  }
  newnode->item = i;
  newnode->next = pointer->next;
  if(pointer->next == NULL){
    newnode->previous = base->previous;
    base->previous = newnode;
  }else{
    newnode->previous = (pointer->next)->previous;
    (pointer->next)->previous = newnode;
  }
  pointer->next = newnode;
}

void printlist(BLIST *base){
  BLIST *p=base;
  while((p=p->next)!=NULL){
    printf("%s ",p->item);
  }
  printf("\n");
}
void printreverse(BLIST *base){
  BLIST *p=base;
  while((p=p->previous)!=NULL){
    printf("%s ",p->item);
  }
  printf("\n");
}
int empty(BLIST *base){
  return base->next == NULL;
}
int size(BLIST *base){
  BLIST *p=base;
  int i=0;
  while((p=p->next) != NULL){
    i++;
  }
  return i;
}
int removenode(BLIST *base, BLIST *pointer){
  BLIST *p,*n;
  if(base==pointer){
    return -1;
  }
  p = pointer->previous;
  n = pointer->next;
  if(p==NULL){
    base->next = n;
  }else{
    p->next = n;
  }
  if(n==NULL){
    base->previous = p;
  }else{
    n->previous = p;
  }
  /* free(pointer->item) */
  free(pointer);
}
    
int main(void){
  BLIST *l;
  BLIST *p;
  if((l=malloc(sizeof(BLIST)))==NULL){
    fprintf(stderr,"メモリーを確保できませんでした\n");
    exit(2);
  }
  l->next=l->previous=NULL;
  add(l,l,"abc");
  printlist(l); printreverse(l);  printf("size = %d\n",size(l));
  add(l,l,"def");
  printlist(l);  printreverse(l);  printf("size = %d\n",size(l));
  add(l,l->previous,"ghi");
  printlist(l);  printreverse(l);  printf("size = %d\n",size(l));
  add(l,l->previous,"jkl");
  printlist(l);  printreverse(l);  printf("size = %d\n",size(l));
  add(l,l->next->next->next,"mno");
  printlist(l);  printreverse(l);  printf("size = %d\n",size(l));
  while(!empty(l)){
    printlist(l);  printreverse(l);  printf("size = %d\n",size(l));
    removenode(l, l->next);
  }
  return 0;
}

参考: 指定したファイルを読み込み、表示するプログラム

以下はコマンドラインからファイル名を指定すると、そのファイルを線形リストに入れた後、線形リストの内容を表示するプログラムです。

C 言語版

線形リストに入れる時、毎回全線形リストをたどるという非効率な実装がされています。線形リストの最後の要素を指すポインタを設定し、そこに対して挿入するようにするとかなり効率が良くなります。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUFFSIZE 80
typedef struct lst {
  char *item;
  struct lst *next;
} LIST;
LIST *root;
void add(char *c){
  LIST *p=root;
  while(p->next != NULL){
    p= p->next;
  }
  p->next=malloc(sizeof(LIST));
  p->item=c;
  (p->next)->next=NULL;
}
void show(){
  LIST *p=root;
  while(p->next !=NULL){
    printf("%s",p->item);
    p=p->next;
  }
}
int main(int argc, char *argv[]){
  FILE *fp;
  char buffer[BUFFSIZE];
  char *s;
  if((root=malloc(sizeof(LIST)))==NULL){
    fprintf(stderr,"メモリーを確保できませんでした\n");
    exit(2);
  }
  root->next=NULL;
  root->item=NULL;
  if(argc <2 ){
    fprintf(stderr, "Specify the file name.\n");
    exit(3);
  }
  if((fp=fopen(argv[1],"r"))==NULL){
    fprintf(stderr, "File Not Found.\n");
    exit(4);
  }
  while(fgets(buffer,BUFFSIZE, fp)!=NULL){
    if((s=malloc(strlen(buffer)*sizeof(char)))==NULL){
      fprintf(stderr,"メモリーを確保できませんでした\n");
      exit(2);
    }
    strcpy(s,buffer);
    printf("%s\n",s);
    add(s);
  }
  show();
  return 0;
}

C++ 版


#include <iostream>
#include <fstream>
#include <string>
#include <list>
#define BUFFSIZE 80
using std::cerr;
using std::endl;
int main(int argc, char *argv[]){
  if(argc<2){
    std::cerr << "Specify the file name." << std::endl;
    return 1;
  }
  std::ifstream ifs(argv[1], std::ios::in);
  if(!ifs){
    std::cerr << "File Not Found." << std::endl;
    return 2;
  }
  char buffer[BUFFSIZE];
  std::list<std::string> l;
  while(!ifs.eof()){
    ifs.getline(buffer,BUFFSIZE);
    l.insert(l.end(),buffer);
  }
  for(std::list<std::string>::iterator i=l.begin(),j=l.end();i!=j;i++){
    std::cout << *i << std::endl;
  }
  return 0;
}

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 11 回 線形リスト