第 11 回線形リスト

本日の内容

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

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

11-1. 線形リストの操作

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

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

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


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 *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("%c\n",p->item);
    p=p->next;
  }
}
main(){
  root=(LIST *)malloc(sizeof(LIST));
  root->next=NULL;
  add('a');
  add('b');
  add('c');
  show();
}

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

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

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


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

演習11-1

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

ヒント

文字へのポインタをしまえるスタックを使って次のようにします。


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

11-2. 双方向リスト

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

演習11-2

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

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

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

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

第 11 回 線形リスト