file, data structures

リスト 11.8 には問題がある．リスト 11.6 でいろいろなテストデータを入力し，自分で発見することを試みよ．

すべての入力をテストすることはできないので，テストはある程度戦略をもって行う必要がある．シビアなテストができることは優秀なプログラマの必要条件である．

基本的な戦略として，例えばプログラムが 2 つに分岐するならそれぞれの処理に流れるような入力を考えてどちらもテストする．取りうる値の範囲があるならそのぎりぎりの値を処理させてみる，などがあげられる．今回は口座番号が 1 から 100 なので 1 のデータ，100 のデータが正しく処理されるかどうかは最低限テストすべきである．

口座番号 100 のデータを入力し，リスト 11.8 を実行すると最後のデータが 2 回表示される不具合が確認できる．

これはリスト11.8 のプログラムの問題で， feof() が返す値が偽から真へ変わるタイミングが原因である．feof() はファイルの内容全てをちょうど読み切った段階では偽であり，次の読み込みで読み込みを失敗して初めて真になる．

これを修正するには出力するかどうかを判断する if 文の条件を修正し， fread が成功したときだけ client.acctNum を調べるようにすればよい． fread は読み込みに成功した個数を返すので，今回の場合は fread の返り値が 1 であれば成功と判断できる．fread の実行自体もこのテスト文の第一項で行うようにすると，以下のような修正になる．修正して実行せよ．

fread(&client, sizeof(struct clientData), 1, cfPtr);

if (client.accNum != 0)

リスト 11.8 の一部（修正前）

if (fread(&client, sizeof(struct clientData), 1, cfPtr) == 1
    && client.accNum != 0)

リスト 11.8 の一部（修正後）

11.10節

リスト 11.9 にもリスト 11.8 までと同様の問題がある．修正したものを用意したのでダウンロードして利用せよ．

12章

12.1 概要

配列など，変数宣言文が実行されたときにメモリ領域が確保され，その後は領域に変化のないデータ構造を今まで扱って来た．メモリ領域が固定であると，確保した領域が大きすぎると少量のデータを扱うときに無駄であるし，領域が足りないと正常に動作しない．

この章では実行時に必要に応じて確保するメモリ領域が増減するデータ構造について解説する．有名なデータ構造として，連結リスト，スタック，キュー，二分木を紹介する．

12.2 自己参照構造体

自己参照構造体とは自分の型を指すポインタをメンバに含む構造体のこと．

struct node {
   int data;
   struct node *nextPtr;
};

自己参照構造体の例

自己参照構造体は，リスト，木構造にとってきわめて重要である．教科書 p.441 図 12.1 は，上の struct node 構造体について，

struct node a,b;

a.data = 15;
a.nextPtr = &b
b.data = 10;
b.nextPtr = NULL;

図 12.1 を作るコード

12.3 動的メモリ配置

プログラムの実行に応じて必要なメモリ領域を確保したり不要なメモリ領域を解放したりすることを動的メモリ配置という．必要になってからメモリを確保することができるので，メモリを効率的に利用できる．

動的メモリ配置には関数 malloc, free と sizeof 演算子が重要．特に malloc の使い方が最大のポイントになる．この章の最初の目的は的確に malloc が使えるようになることとである．

malloc のプロトタイプ宣言は stdlib.h にあるので malloc を使用するときは stdlib.h をインクルードする． malloc は引数としてバイト数を与えると，メモリ上のどこかにそのバイト数の領域を確保し，確保した場所のアドレスを返す．malloc は指示されたバイト数しか知らない．すなわちどんな型の変数かを知らないのでアドレスは void へのポインタとして返す．領域確保に失敗すると NULL ポインタを返す．

12.4 連結リスト

要素数が数個に固定されている簡単なリストの作成から順に複雑なリストを利用するプログラムへ書き換えてゆく形でサンプルプログラムを紹介する．

最初にリストに文字を1個格納し，それを出力するプログラムを示す．関数 malloc により listNode 構造体を格納する領域が確保される．構造体はポインタを用いてアクセスする．

/* リストに文字を 1 個格納する */
#include <stdio.h>
#include <stdlib.h>

struct listNode { /* 自己参照構造体 */
   int data;
   struct listNode *nextPtr;
};

typedef struct listNode LISTNODE;

main()
{
   LISTNODE *startPtr;

   startPtr = malloc(sizeof(LISTNODE));
   if (startPtr != NULL){
      startPtr->data = 93;
      startPtr->nextPtr = NULL;
   }

   printf("%3d ", startPtr->data);
   putchar('\n');
   
   return 0;
}

list12x1.c

このプログラムを実行した後，リストは以下の状態になる．

2 個目の要素のための領域を，再び関数 malloc を呼び出すことで確保するコードを追加する．今回の例では，リスト上の順序として 後で挿入したほうの要素が前 にくるように追加する．また startPtr が常にリスト先頭の要素を指す ようにする．そのためには

ことが重要である．どの行でその処理がなされているか確認せよ．

/* リストに逆順に文字を 2 個格納する */
#include <stdio.h>

#include <stdlib.h>

struct listNode {
   int data;
   struct listNode *nextPtr;
};

typedef struct listNode LISTNODE;

main()
{
   LISTNODE *startPtr, *currentPtr;

   startPtr = malloc(sizeof(LISTNODE));
   if (startPtr != NULL){
      startPtr->data = 93;
      startPtr->nextPtr = NULL;
   }
   currentPtr = malloc(sizeof(LISTNODE));
   if (currentPtr != NULL){
      currentPtr->data = 29;
      currentPtr->nextPtr = startPtr;
      startPtr = currentPtr;
   }

   printf("%3d ", startPtr->data);
   printf("%3d ", startPtr->nextPtr->data);
   putchar('\n');
   
   return 0;
}

list12x2.c

このプログラムを実行した後，リストは以下の状態になる．

3 個目の要素のための領域を，再び関数 malloc を呼び出すことで確保するコードを追加する．今回格納するデータがリストの先頭となる． 2 個目を追加したときと同じ処理で実行できる

/* リストに逆順に文字を 3 個格納する */
#include <stdio.h>
#include <stdlib.h>

struct listNode {
   int data;
   struct listNode *nextPtr;
};

typedef struct listNode LISTNODE;

main()
{
   LISTNODE *startPtr, *currentPtr;

   startPtr = malloc(sizeof(LISTNODE));
   if (startPtr != NULL){
      startPtr->data = 93;
      startPtr->nextPtr = NULL;
   }
   currentPtr = malloc(sizeof(LISTNODE));
   if (currentPtr != NULL){
      currentPtr->data = 29;
      currentPtr->nextPtr = startPtr;
      startPtr = currentPtr;
   }
   currentPtr = malloc(sizeof(LISTNODE));
   if (currentPtr != NULL){
      currentPtr->data = 17;
      currentPtr->nextPtr = startPtr;
      startPtr = currentPtr;
   }

   printf("%3d ", startPtr->data);
   printf("%3d ", startPtr->nextPtr->data);
   printf("%3d ", startPtr->nextPtr->nextPtr->data);
   putchar('\n');
   
   return 0;
}

list12x3.c

このプログラムを実行した後，リストは以下の状態になる．

出力に注目する．リストの最後の要素の nextPtr には NULL が格納されているので，それを利用してループでリストの要素を出力する構造に変更する．こうすることで任意の要素数のリストを出力できる．また，カレントポインタをループ変数として， currentPtr = currentPtr->nextPtr でポインタを NULL が出るまで進める処理はリスト処理のプログラムの基本であり，重要である

/* 出力をループ構造にし，任意の個数に対応する．*/
#include <stdio.h>
#include <stdlib.h>

struct listNode {
   int data;
   struct listNode *nextPtr;
};

typedef struct listNode LISTNODE;

main()
{
   LISTNODE *startPtr, *currentPtr;

   startPtr = malloc(sizeof(LISTNODE));
   if (startPtr != NULL){
      startPtr->data = 93;
      startPtr->nextPtr = NULL;
   }
   currentPtr = malloc(sizeof(LISTNODE));
   if (currentPtr != NULL){
      currentPtr->data = 29;
      currentPtr->nextPtr = startPtr;
      startPtr = currentPtr;
   }
   currentPtr = malloc(sizeof(LISTNODE));
   if (currentPtr != NULL){
      currentPtr->data = 17;
      currentPtr->nextPtr = startPtr;
      startPtr = currentPtr;
   }

   currentPtr = startPtr;
   while (currentPtr != NULL) {
      printf("%3d ", currentPtr->data);
      currentPtr = currentPtr->nextPtr;
   }
   putchar('\n');
   
   return 0;
}

list12x4.c

このプログラムの実行中の currentPtr の変化は以下の通りである．

入力もループ構造にして任意個の入力に対応したい．最初に 1 個目の処理だけ他と違っていたのを共通にできないかどうか考える．

/* リスト 1 個目の処理を 2 個目以降と共通にする*/
#include <stdio.h>
#include <stdlib.h>

struct listNode {
   int data;
   struct listNode *nextPtr;
};

typedef struct listNode LISTNODE;

main()
{
   LISTNODE *startPtr, *currentPtr;

   startPtr = NULL;
   currentPtr = malloc(sizeof(LISTNODE));
   if (currentPtr != NULL){
      currentPtr->data = 93;
      currentPtr->nextPtr = startPtr;
      startPtr = currentPtr;
   }
   currentPtr = malloc(sizeof(LISTNODE));
   if (currentPtr != NULL){
      currentPtr->data = 29;
      currentPtr->nextPtr = startPtr;
      startPtr = currentPtr;
   }
   currentPtr = malloc(sizeof(LISTNODE));
   if (currentPtr != NULL){
      currentPtr->data = 17;
      currentPtr->nextPtr = startPtr;
      startPtr = currentPtr;
   }

   currentPtr = startPtr;
   while (currentPtr != NULL) {
      printf("%3d ", currentPtr->data);
      currentPtr = currentPtr->nextPtr;
   }
   putchar('\n');
   
   return 0;
}

list12x5.c

全ての要素の挿入が同じ処理でできることが分かったのでループの形に書き直す．

/* 任意個の入力に対応する．*/
#include <stdio.h>
#include <stdlib.h>

struct listNode {
   int data;
   struct listNode *nextPtr;
};

typedef struct listNode LISTNODE;

void printList(LISTNODE *);

main()
{
   LISTNODE *startPtr, *currentPtr;
   int value;

   startPtr = NULL;

   printf("要素の非負整数を入力して下さい（-1で終了）:\n? ");
   scanf("%d", &value);
   while (value >= 0) {
      currentPtr = malloc(sizeof(LISTNODE));
      if (currentPtr != NULL){
         currentPtr->data = value;
         currentPtr->nextPtr = startPtr;
         startPtr = currentPtr;
      }
      printf("要素の非負整数を入力して下さい（-1で終了）:\n? ");
      scanf("%d", &value);
   }

   printList(startPtr);

   return 0;
}

void printList(LISTNODE * cPtr)
{
   while (cPtr != NULL) {
      printf("%3d ", cPtr->data);
      cPtr = cPtr->nextPtr;
   }
   putchar('\n');
}

list12x6.c

要素を先頭に追加していく処理は以下で説明するスタックでも使われる．

説明の順序の変更

本章では教科書の説明する順序を変更する． 12.5 スタック，12.6 キューの後に 12.4 のリストに戻り，12.7 のツリーを説明する．

file, data structures
ファイル入出力，データ構造

11章

リスト 11.8 の問題点

11.10節

12章

12.1 概要

12.2 自己参照構造体

12.3 動的メモリ配置

12.4 連結リスト

説明の順序の変更

file, data structures ファイル入出力，データ構造

11章

リスト 11.8 の問題点

11.10節

12章

12.1 概要

12.2 自己参照構造体

12.3 動的メモリ配置

12.4 連結リスト

説明の順序の変更

file, data structures
ファイル入出力，データ構造