6.18 データ構造
6.18.2 構造体を利用したデータ構造
構造体を利用すると,アルゴリズムの実現に役立つリスト(list),ツリー(tree)といったデータ構造を実 現することができる.
これらのデータ構造は,そのデータ量があらかじめわかっているならば,ポインタを利用せずに実現でき るが,データ量がアプリオリにはわからない時にはポインタを使わざるをえない. ここでは,これらのデー タ構造が,どのようなものかを見ていこう.
6.18.2.1 リスト
リストとは,データが一列につながったものである. 各データは次のデータへのポインタを持ち,最後の データが持つ次のデータへのポインタは何も指し示していないという形で実現できる. リストになったデー タを操作するには,ポインタを動かせば良い. 具体的には,次のような形式になっている.
6.18.2.2 ツリー
ツリーとは,各データが１つ以上の他のデータへのポインタを持ったものである. 各データは他のデータ へのポインタを持ち, 最後のデータが持つ他のデータへのポインタは何も指し示していないという形で実 現できる. 具体的には,次のような形式になっている.
6.18.2.3 自己参照構造体
構造体は,それ自身を参照することができる. これを利用して,リストやツリーといったデータ構造を実 現することができる.
例えば,リストを実現するには, 次のような方法を利用する.
Example 6.18.11 80文字からなる文字列と,次のデータへのポインタを持った構造体は以下のように定 義できる.
struct data { char str[80] ; struct data *next ; } data ;
このように定義した構造体を利用して, リストを実現することができる.
Example 6.18.12 Example 6.18.11で定義した構造体を初期化する. 即ち,一番始めのデータには何も入 れない.
strcpy(data.str,"") ; data.next = NULL ;
次に必要なことは,一番最後のデータ（最初は一番はじめのデータと同じ）にデータを入力したら,もう一 つデータを持ってきて,それを初期化することである.
Example 6.18.13 ここでは, ポインタのつなぎ変えと,次のデータ領域の取得をしている.
struct data *p ;
if ((p = (struct data *)malloc((unsigned int)(sizeof(struct data)))) != NULL) { strcpy(p->str,"b") ;
p->next = NULL ; data.next = p ; }
ここで,malloc関数は,必要なメモリ領域を確保するための関数である. ここで確保したメモリ領域は,
必要がなくなったら, free関数で領域を開放する必要がある.
このようにして作った リスト形式のデータを一番最初のデータから順にアクセスするためには,最初のデー タを指し示すポインタを作成して,nextが次のデータを指ししていることを利用して, ループを使ってア クセスすれば良い.
Example 6.18.14 ここでは, リストの途中にデータを挿入するための手順を示している.
struct data *p ; struct data *q ;
if ((q = (struct data *)malloc((unsigned int)(sizeof(struct data))))
!= NULL) {
q->next = p->next ; p->next = q ; }
ここで,pは,挿入したい位置を示しているポインタである.
p
p
p->next
q->next
q
Example 6.18.15 各データが２つのポインタを持ったツリーを実現するには, 次のようなデータ形式を
利用すれば良い.
struct tree_data { char c ;
struct tree_data *r ; struct tree_data *l ; } ;
Example 6.18.15定義した二分木構造を実際に使ってみよう.
Example 6.18.16 ここでは, 以下の図のような二分木を構成する.
c
e
g f CCd CC
b i
l m CCk n
JJj hCC , ee,
a root
はじめに二分木を入力するための関数enter を定義する.
char *enter(struct tree_data **t, char *str) {
struct tree_data *p ; printf("%c", *str) ;
if (*str == ’\0’) return str ; if (*str != ’.’) {
if ((p = (struct tree_data *)malloc(sizeof(struct tree_data))) == NULL) {
printf("Could not allocate memory!\n") ; exit(-1) ; }
p->c = *str ; p->l = NULL ; p->r = NULL ;
*t = p ;
str = enter(&(p->l),++str) ; str = enter(&(p->r),++str) ; }
return str ; }
関数enterは
struct tree_data *root ;
char str[] = "abc..de..fg...hi..jkl..m..n.." ; と定義された変数に対して
enter(&root, str) ; printf("\n") ;
として呼び出すと,二分木の構造にデータを格納し, そのデータを表示する.
このようにして構成した二分木を３つの方法で巡回してみよう. はじめは,左優先に探索し,通ったノー ドを順に印字するものである.
void preorder(struct tree_data *t) {
if (t == NULL) return ; printf("%c", t->c) ; preorder(t->l) ; preorder(t->r) ; return ;
}
次に左優先に探索し, ノードを分岐するときに印字するものである.
void inorder(struct tree_data *t) {
if (t == NULL) return ; inorder(t->l) ;
printf("%c", t->c) ; inorder(t->r) ; return ;
}
最後は,左優先に探索し,戻るときにノードを印字するものである.
void postorder(struct tree_data *t) {
if (t == NULL) return ; postorder(t->l) ;
postorder(t->r) ; printf("%c", t->c) ; return ;
}
これら３つの関数を
enter(&root, str) ; printf("\n") ; preorder(root) ; printf("\n") ; postorder(root) ; printf("\n") ; inorder(root) ; printf("\n") ; として呼び出すと,
abc..de..fg...hi..jkl..m..n..
abcdefghijklmn cegfdbilmknjha cbedgfaihlkmjn
という結果を得る. これが「二分木の巡回」である.
Example 6.18.17 Kernighan & Ritchieの教科書[2]の6.5章には,二分木の興味ある応用例が述べられ ている. そこに述べられているプログラムを掲載しておこう. （ただし,多少改変してある.）
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAXLINE 1024
#define FMT " .,"
struct tnode { char *word ; int count ;
struct tnode *left ; struct tnode *right ; } ;
extern struct tnode *addtree(struct tnode *, char *) ; extern struct tnode *talloc(void) ;
extern void error_jmp(void) ;
extern void print_tree(struct tnode *) ; int main(int argc, char **argv)
{
struct tnode *root ;
char *p, *q, buf[MAXLINE] ; root = NULL ;
while((!feof(stdin))&&((p = fgets(buf, MAXLINE, stdin)) != NULL)) { /* 入力のトークン分解と二分木への挿入 */
q = strtok(buf,FMT) ; if (isalpha(q[0])) {
q[0] = tolower(q[0]) ; root = addtree(root,q) ; }
while((q = strtok(NULL,FMT)) != NULL) { if (isalpha(q[0])) {
q[0] = tolower(q[0]) ; root = addtree(root,q) ; }
} }
/* 二分木の出力 */
print_tree(root) ; return 0 ;
}
void print_tree(struct tnode *p) {
if (p == NULL) return ; print_tree(p->left) ;
printf("%4d: %s\n", p->count, p->word) ; print_tree(p->right) ;
return ; }
struct tnode *addtree(struct tnode *p, char *s) {
int str_cond ;
if (p == NULL) { /* 新しい単語？ */
if ((p = talloc()) == NULL) /* 領域確保に失敗 */
error_jmp() ;
if ((p->word = strdup(s)) == NULL) /* 領域確保に失敗 */
error_jmp() ;
p->left = NULL ; p->right = NULL ; p->count = 1 ;
}
else if ((str_cond = strcmp(s,p->word)) == 0) /* 同じ単語があるので, カウンタをインクリメント */
p->count += 1 ;
else if (str_cond < 0) /* 小さければ左に */
p->left = addtree(p->left,s) ;
else /* 大きければ右に */
p->right = addtree(p->right,s) ; return p ;
}
/* p の領域を確保する */
struct tnode *talloc(void) {
struct tnode *p ;
if ((p = (struct tnode *)malloc(sizeof(struct tnode))) != NULL) return p ;
return NULL ; }
/* s で与えられた文字列を duplicate する */
char *strdup(const char *s) {
char *p ;
if ((p = (char *)malloc(strlen(s)+1)) != NULL) { strcpy(p,s) ;
return p ; }
return NULL ; }
void error_jmp(void) {
fprintf(stderr, "Could not allocate memory!\n") ; exit(-1) ;
return ; }
このプログラムは標準入力から入力されたテキストファイルを,FMTで与えられた文字列の要素を区切り子 としてトークン分解し（すなわち,単語に分解し）, それを二分木構造に展開する. 二分木構造は, すべて の葉に対して,
• 左部分木は,単語の辞書式順序で葉よりも小さいものを,
• 右部分木は,単語の辞書式順序で葉よりも大きいものを
格納する. 与えられた順序に対してこのような構造を持つ二分木を整列二分木 (heap)と呼ぶ. この二分木
をinorderで巡回すると,順序に対して整列された出力を得る.
例えば,以下のようなテキストファイルを入力する.
This is a test for a binary tree, which is called heap.
this is a test for a binary tree, which is called heap.
Thats are test for binary trees.
この場合の出力結果は 5: a
1: are 3: binary 2: called 3: for 2: heap 4: is 3: test 1: thats 2: this 3: tree 2: which
となる. これは確かに単語の辞書式順序となっている. （ただし,各単語の先頭文字が大文字の時は,それ を小文字に変更している.）
また,リストの特別な形式として,双方向リスト,循環リストという形式もある.
双方向リスト
循環リスト
これらのリストは, 単純に“自分の次” だけを示すのではなく, “自分の前” などを示すポインタを持って いる.
6.18.2.3.1 typedef Cの文法上は記憶クラス指定子となっているtypedefを用いると, struct data {
char str[80] ;
struct data *r_next ; struct data *l_next ; } data ;
といった構造体を記述する際に持っと簡単に書くことができる.
typedef [元の型] 新しい型の識別子
という形をとる. ここで定義された識別子はtypedef名と呼ばれる. 文法的には「元の型」はなくても 良い.
Example 6.18.18 もっとも簡単なものは,
typedef int Length ;
というものであって,これ以後Lengthという型の識別子が定義され, それはintと同じである.
Example 6.18.19 もう少し複雑なものは, typedef struct tnode *treeptr ; typedef struct tnode {
char str[80] ; treeptr *r_next ; treeptr *l_next ; } treenode ;
これは,treeptr,treenodeという２つの新しい型を定義している.
typedef と section 6.20 で述べる #define の違いは, typedef が型を定義しているのに対し, プリプロ セッサ文の#defineはコンパイル以前に展開されてしまうところにある. すなわち,
#define peach int unsigned peach i ;
はpeach がintにプリプロセッサで置き換えられるので,問題なくコンパイル出来るが,
typdef peach int unsigned peach i ; は文法エラーとなる.
一旦typedefによって型を宣言してしまうと,その型はそれ以後で自由に利用可能である. したがって,
typedef struct complex Complex ;
によってComplexを定義すれば,それ以後はわざわざstruct complexと書かなくても良い. また,typedef
では同じtypedef名をより狭いスコープで再宣言できるが,その場合には「元の型」を明示しなければ,再
宣言したことにはならない. (cf. [2, A8.9].)
これまでに出てきたsize tなどの型は,typedefにより,処理系・ＯＳによって適切な型にtypedefさ れている. 実際にtypedefが有効に利用できるのは,このような処理系依存の部分を吸収する場合が多い.
6.18.3 その他の構造を持った型
6.18.3.1 共用体
余り使わないが,共用体というものがある. 基本的には構造体と同じようなものであり,その定義方法も, structの代りに,unionという予約語を使って宣言を行う.
6.18.3.1.1 共用体の定義
Example 6.18.20 次はint,doubleの型を持つ２つのメンバーがある共用体の定義である.
union int_double { double x ; int n ; } u ;
共用体と構造体との違いは, 各メンバーが重なり合うメモリ領域を共有していることである. すなわち, 共 用体では,各メンバーを同時に（意味のある方法では）アクセスすることができない. これ以外のことに関 しては,共用体は構造体と同じ性質を持つ.
double x int n struct int_double {
double x ; int n ; }
と定義すると,２つのメンバーの領域は重な らない.
double xまたはint n
union int_double { double x ;
int n ;
}
と定義すると,２つのメンバーの領域が重なっ てしまう.
Example 6.18.21 上のint_double共用体では, u.n = 1 ;
u.x = 1.0 ;
といったように,そのメンバーの識別子にしたがって, どの型でもとりうることができるが, 代入時と異な る型で参照したときの値は保証されない. すなわち,共用体においては,そのメンバー変数がすべてメモリ として確保されるのではなく,（この例の場合はnとx）が同じメモリ領域に確保される.
6.18.3.1.2 共用体のメモリ内でのアロケート 共用体はメモリ内では, もっとも大きなメモリを必要と
するフィールドの分だけ確保される. 例えば, Example 6.18.21 の場合は,intと doubleのメモリサイズ の大きい方の分だけのメモリが使われ, その整合も各型に沿った方法で行われる.
6.18.3.1.3 共用体の初期化 共用体の初期化は,その最初のメンバーの型の値のみで行うことができる.
すなわち, 上のint_double 共用体では,メンバー nを用いた初期化は行えるが,メンバーx を用いた初 期化は行うことができない. つまり,
union int_double x = {1} ;
とすると,xには正しくint型の1という値が入るが, union int_double x = {1.0} ;
はxには1.0をintに変換した1が入ることとなる.
6.18.3.1.4 共用体（その他） 共用体の配列,共用体を構造体メンバーとすること,共用体メンバーに配
列, 構造体を使うことなどはすべて許される.
実際に共用体を利用する場面は少ないが,構造体メンバーとして, Pascalにおける「可変レコード」のよ うに,構造体のメンバーの一部の内容によって, その後のメンバー構成が変る時に利用される他に, 古くは
Intel社の80286 CPUのレジスタを表現する構造体