第 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 の使用例を次に示します。


#include <stdio.h>
#include <stdlib.h>
main(){
  int x;
  int *y;
  y=(int *)malloc(50*sizeof(int));
  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);
}

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));
   p->next=NULL;
   return p;
}
void add(LIST *p,char c){
  while(p->next != NULL){
    p= p->next;
  }
  p->item=c;
  p->next=newnode();
}
void show(LIST* p){
  while(p->next !=NULL){
    printf("%c\n",p->item);
    p=p->next;
  }
}
main(){
  LIST *pointer;
  pointer=newnode();
  add(pointer,'a');
  add(pointer,'b');
  add(pointer,'c');
  show(pointer);
}

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

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


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

演習9-1

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

ヒント

まず、文字へのポインタをしまえる線形リストを作ります。


#include <string.h>
char buffer[81]; /* 文字数+1 */
while(ファイルの終りまで){
  bufferに一行(最大80文字)読む;
  buffer の長さを strlen() で調べる;
  調べた長さだけ malloc で領域確保;
  stpcpy で buffer から領域に入力された行をコピー;
  add(領域);
}

そして線形リストを逆順に出す仕組みを考えます。次のように再帰を利用した 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) では毎回同じ番地が登録されてしまうことに注意して下さい。

補足 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;
  }
}

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

第 9 回 線形リスト