C言語-リスト構造

C言語アルゴリズム-メモリ領域確保とリスト構造

4.2　リスト構造

　単語格納用にデータ領域を関数mallocで確保し、その先頭番地を格納するためにポインタ配列ptrを宣言している。ファイルgettoken.cでは68個使用したが、残りは未使用になっている。また、さらに大きなプログラムファイルを処理したときWORDMAXで定義した分では足りなくなる可能性もある。なるべくメモリが節約できるように次のように構造体変数に単語を格納していく。

struct word {
        char    *name;          /* 単語の先頭アドレス */
        struct word *next;      /* 次の構造体変数のアドレス */
};

リスト構造(構造体変数)は、1枚のカードをイメージすれば理解しやすい。

　カード番号は、実際はメモリ上のアドレスである。関数mallocでカードが必要になるごとにカード用のデータ領域(構造体)を確保するので連続したアドレスには作成されない。そのため、次のカードのアドレスの情報が必要になる。このようにすることで、メモリが使用できる分だけ処理が可能となる。
　このようなデータ構造をリスト構造といい、特に上図のように一方向にしかカードをたどっていけないものを単方向リストという。
　次のプログラムでは、単方向リストを利用するが、次に双方向リストのイメージ図を示す。

　《双方向リスト》

struct word {
        char    *name;          /* 単語の先頭アドレス */
        struct word *prev;      /* 前の構造体変数のアドレス */
        struct word *next;      /* 次の構造体変数のアドレス */
};

テキストファイルを読み込み、単語(英字で始まる語)の種類を調べる。単語の記憶には、リスト構造を利用する。[malloc2.c]

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "gettoken.h"

void str_upper(char *);         /* 文字列を大文字に変換 */
typedef struct wlist{           /* 単方向リスト */
    char            *name;      /* 単語の先頭アドレス */
    struct wlist    *next;      /* 次の構造体変数のアドレス */
} WLIST;

void main(void)
{
    FILE    *fp;            /* 入力ファイル */
    char    fname[30];      /* ファイル名 */
    WLIST   word_top;       /* 先頭カード */
    WLIST   *p_word;        /* カード用のポインタ */
    int     count = 0;      /* 単語数 */

    printf("ファイル名 : ");
    gets(fname);                /* ファイル名入力 */
    if((fp = fopen(fname, "r")) == NULL){   /* オープン */
        printf("ファイルがオープンできない\n");
        exit(1);
    }
    p_word = &word_top;         /* ポインタの初期化 */
    p_word->name = NULL;        /* 最初のカード初期化 */
    p_word->next = NULL;
    while((fgets(gt_line, STR_MAX, fp)) != NULL){
        while(1){
            get_token();            /* トークン取得 */
            if(*token == '\0')      /* 1行分終了 */
                break;
            str_upper(token);       /* 大文字変換 */
            if(isalpha(*token)){    /* 先頭英字(単語) */
                p_word = &word_top;     /* ポインタ初期化 */
                while(1){               /* 単語検索 */
                    if(!strcmp(token, p_word->name)){   /* 登録済み */
                        *token = '\0';
                        break;
                    }
                    if(p_word->next == NULL)    /* 検索終了 */
                        break;
                    p_word = p_word->next;      /* 次のカード */
                }
                if(*token != '\0'){             /* 未登録 */
                    p_word->name = (char *)malloc(strlen(token) + 1);
                    if(p_word->name == NULL){    /* ↑文字数 +1バイト確保 */
                        printf("データ領域が確保できない\n");
                        exit(1);
                    }
                    strcpy(p_word->name, token); /* 確保した領域に単語コピー */
                    p_word->next = (WLIST *)malloc(sizeof(WLIST));
                    if(p_word->next == NULL){    /* ↑次のカード作成(領域確保) */
                        printf("データ領域が確保できない\n");
                        exit(1);
                    }
                    p_word = p_word->next;      /* カード初期化 */
                    p_word->name = NULL;
                    p_word->next = NULL;
                    ++count;            /* 単語数カウント */
                }
            }
        }
    }
    fclose(fp);             /* クローズ */

    p_word = &word_top;         /* ポインタ初期化 */
    while(p_word->next != NULL){
        printf("(%s) ", p_word->name);
        p_word = p_word->next;
    }
    printf("\n%d種類\n", count - 1);
}
void str_upper(char *pb)
{
    while(*pb != '\0'){             /* ヌル文字まで繰り返す */
        if(*pb >= 'a' && *pb <= 'z')    /* 小文字のとき */
            *pb = *pb -0x20;    /* 大文字に変換 */
        ++pb;               /* ポインタを1つ進める */
    }
}

　7～11行目の構造体定義ではtypedefで別名を付けているが、タグ名を省略していない。これは、構造体定義の中で構造体を使用しているからである。

   8: typedef struct wlist{                8: typedef struct{
   9:     char            *name;           9:     char            *name;
  10:     struct wlist    *next;          10:     WLIST           *next;
  11: } WLIST;                            11: } WLIST;
                                             こちらはエラーになる。