第 9 回線形リスト

本日の内容

9-1. 配列の問題点
9-2. 動的なメモリの確保
9-3. 線形リストの操作
9-4. 双方向リスト

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

9-1. 配列の問題点

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

そのため、未知の容量のデータ対して、メモリの使用量を制御するような新たなデータ構造を使用する必要があります。この講義では、まずプログラム実行中にメモリを確保する仕方を学び、次に複数のデータをメモリに格納する方法を学びます。

C 言語の配列はあらかじめ容量を決めておく必要があります。しかし、それでは処理できる情報量に限りがあります。そのため、任意の長さのメモリを確保する関数 malloc が C 言語に提供されています。 malloc 関数は必要なバイト数を引数にすると、OS から確保したメモリの先頭の番地を値として返します。一方、 free 関数はメモリの番地を引数とすると、そのメモリを OS に返します。確保した領域を C 言語の変数として使うには、変数に必要なメモリのバイト数を求め、そのバイト数だけ確保し、返ってきたメモリの番地をその変数の型にキャストする必要があります。型からその型に必要なバイト数を求めるにはsizeof 演算子を使います。なお、利用できるメモリがない場合に malloc 関数が呼ばれた場合、メモリは確保されず、 NULL が返されます。 NULL が返された時に返ってきた値(NULL)で処理を続けるとプログラムが異常動作を起こし、最悪プログラムが暴走(操作不能な誤動作)を起こします。そのため、malloc 関数の戻り値が NULL かどうかを検査する必要があります。

malloc の使用例を次に示します。


#include <stdio.h>
#include <stdlib.h>
main(){
  int x;
  int *y;
  if((y=(int *)malloc(50*sizeof(int)))!=NULL){
    for(x=0; x<50; x++){
      printf("%d ",y[x]=x);
    }
    printf("\n");
    for(x=0; x<50; x++){
      printf("%d ",*y++);
    }
    printf("\n");
    free(y);
  }else{
    fprintf(stderr,"メモリを確保できませんでした\n");
  }
}

9-3. 線形リストの操作

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

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

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


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

この構造体を malloc を利用してメモリ上に作り、ポインタで結合します。

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

NULL のノードを探す。
NULL のノードの位置に、指定された値が含まれるノードを追加する。

ノードを追加するのに、新たに作ったノードに指定された値を入れると NULL の直前の頂点の内容を変更する必要があります。しかし、NULL の入っている頂点に指定された値を入れ、新たに NULL の頂点を作成すると、もともと NULL の入っている頂点と新たに作ったノードだけの操作で頂点を足すことができます。一方、線形リストに含まれているものを表示するにはノードへのポインタを用意し、 next が NULL でない限り、 item を表示し、ポインタを次のノードに進めるようにします。したがって、この方式でプログラムを組むと次のようになります。


#include <stdio.h>
#include <stdlib.h>
typedef struct lst {
  char item;
  struct lst *next;
} LIST;
LIST* newnode(){
   LIST *p;
   p=(LIST *)malloc(sizeof(LIST));
   if(p!=NULL){
     p->next=NULL;
   }
   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){
  while(p->next !=NULL){
    printf("%c\n",p->item);
    p=p->next;
  }
}
void delnode(LIST* p){
  if(p!=NULL){
    delnode(p->next);
    free(p);
  }
}
main(){
  LIST *pointer;
  pointer=newnode();
  if((add(pointer,'a')!=NULL) &&
     (add(pointer,'b')!=NULL) &&
     (add(pointer,'c')!=NULL)){
     show(pointer);
  }
  delnode(pointer);
}

このプログラムで 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){
    if((p->next=newnode())!=NULL){
      p->item=c;
    }
    return p;
  }else{
    return add(p->next,c);
  }
}
void show(LIST *p){
  if(p->next !=NULL){
    printf("%c\n",p->item);
    show(p->next);
  }
}

演習9-1

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

ヒント

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


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

文字へのポインタをしまえる線形リストを作り、一行毎に線形リストに貯めるようにプログラムを変更します。
```
      }else{
	buffer[i]='\0';
	add(pointer,strdup(buffer));
	i=0;
      }
```

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


void reverseshow(LIST *p){
  if(p->next != NULL){
    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(読み込み用バッファの番地, 文字数, ファイルハンドル) 関数を使うと一行をまとめて読み込むことができます。但し、文字数分だけいっぱいに読んでしまったかどうかは最終文字が改行記号かどうかで判定する必要があります。

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

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


#include <iostream>
#include <list>
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;
  }
}

9-4. 双方向リスト

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

演習9-2

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

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


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();
  }
  close(input);
}

付録 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=(BLIST *)malloc(sizeof(BLIST));
  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;
  }else{
    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);
 }
}
    
main(){
  BLIST *l=(BLIST *)malloc(sizeof(BLIST));
  BLIST *p;
  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);
  }
}

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

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

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=(LIST *)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;
  }
}
main(int argc, char *argv[]){
  FILE *fp;
  char buffer[BUFFSIZE];
  char *s;
  root=(LIST *)malloc(sizeof(LIST));
  root->next=NULL;
  if(argc <2 ){
    fprintf(stderr, "Specify the file name.\n");
    return;
  }
  if((fp=fopen(argv[1],"r"))==NULL){
    fprintf(stderr, "File Not Found.\n");
    return;
  }
  while(fgets(buffer,BUFFSIZE, fp)!=NULL){
    s=(char *)malloc(strlen(buffer)*sizeof(char));
    strcpy(s,buffer);
    printf("%s\n",s);
    add(s);
  }
  show();
}

C++ 版


#include <iostream>
#include <fstream>
#include <string>
#include <list>
#define BUFFSIZE 80
using std::cerr;
using std::endl;
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;
  }
}

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科

第 9 回 線形リスト