第 6 章 C 言語入門
6.18 データ構造
6.18.1 構造体
printf("Could not allocate memory!\n") ; exit(-1) ;
return ; }
qは読み込んだ文字列を格納する領域を指し示すポインタの列で,１行を読み込むごとに,次の１行を格納 する領域と,それを指し示す領域を確保しながらqを構成している.
演習問題
Exercise 6.17.1 Section 6.17.2.2の例で, １行の文字数を制限しなくても良いようにプログラムを書換 えよ.
Exercise 6.17.2 Section 6.17.2.2の例で,プログラム終了直前に,mallocで確保したすべての領域をfree で開放するようにプログラムを書換えよ.
struct {
double real ; double imaginary ; } x ;
Example 6.18.1との違いは,構造体タグを持たないことであるが,この場合には,この後でこの型の構造体
を持つ変数を定義する際に, struct {
double real ; double imaginary ; } y ;
と繰り返し書かなくてはいけなくなる. 一方, Example 6.18.1のように,構造体タグを利用すれば,その後 同じ型の変数を定義する際などに,struct complex yとだけ書けば良い.
構造体メンバーそれ自身が構造体になってもかまわない.
Example 6.18.3 次は複素平面上の円を表す構造体である. 中心を表す複素数と半径を表す実数（倍精度
浮動小数点数）の組からなる構造体である.
struct sphere {
struct complex center ; double radius ;
}
radius real
imaginary stuct complex
struct sphere
このように定義された構造体のメンバーは,先に書かれた順にメモリ内に格納される.
6.18.1.2 構造体のメンバー参照
上のように定義した構造体変数のそれぞれのメンバーを参照するには,. という演算子（構造体メンバー 演算子）を利用する.
Example 6.18.4 構造体complexに値を代入する.
struct complex { double real ; double imaginary ; } ;
int main(int argc, char **argv) {
struct complex z ; z.real = 1.0 ; z.imaginary = 1.0 ; }
すなわち,構造体変数struct_nameに対して,struct_name.member_nameによって,その構造体メンバー member_nameを表すことができる. したがって,上で定義した構造体struct sphere型の変数sに対し て, その中心と半径を代入するには,
s.center.real = 0.0 ; s.center.imaginary = 0.0 ;
s.radius = 1.0
とすれば良いことが分かる.
Id: C8.tex,v 1.11 2001-03-23 14:18:24+09 naito Exp
6.18.1.3 構造体の初期化と代入
構造体を初期化するには,そのメンバーに値を代入しても良いが,一方で, struct sphere s0 = {{0.0, 0.0}, 1.0} ;
struct sphere s1 = {0.0, 0.0, 1.0} ;
という初期化も可能である89. また,構造体の変数への一括代入も可能である.
struct sphere s0 = {{0.0, 0.0}, 1.0} ; struct sphere s1 ;
s1 = s0 ;
によっても,s0の内容をs1に代入することが可能である.
6.18.1.4 構造体と関数
構造体を引数にとる関数,構造体を戻り値とする関数定義することができる90 .
Example 6.18.5 はじめに, struct complex型の変数に対して, そのノルムを返す関数complex_norm をつくってみよう.
double complex_norm(struct complex x) {
if (x.real != 0) {
return abs(x.real)*sqrt(1 + (x.imaginary/x.real)*(x.imaginary/x.real)) ; }
return abs(x.imaginary) ; }
ここで,複素数x+√
−1yのノルムを
x2+y2 と計算してしまうと,x2+y2を計算する時点でオーバ フローが発生するかもしれない. そのため,わざわざ
x2+y2=|x|
1 + (y/x)2と計算していることに
注意.
Example 6.18.6 次に,構造体を戻り値とする関数として,２つの複素数の和を求める関数をつくる.
struct complex complex_add(struct complex z, struct complex w) {
z.real += w.real ;
z.imaginary += w.imaginary ; return z ;
}
Remark 6.18.1 これらの関数complex_norm, complex_add をプロトタイプ宣言なしに利用すると, と もに戻り値がintではないため,コンパイラが正しく関数を判断できない. したがって,それらを利用する 前に,プロトタイプ宣言
extern double complex_norm(struct complex) ;
extern struct complex complex_add(struct complex, struct complex) ; を行う必要がある.
89当たり前だが,上の初期化の方が何をしているかは分かりやすい.
90Kernighan-Ritchieの初版（いわゆるtraditionalなＣ）では,構造体への一括代入,構造体を引数とする関数,構造体を戻り値
とする関数などは許されてはいなかった.したがって, traditional Cでこのようなことを行うためには,すべて,構造体のポインタ を受け渡しする必要があった. また, traditional Cでは,自動構造体（関数内部での自動変数となる構造体）の初期化も許されてい なかった. ANSI規格（Kernighan-Ritchie第２版）では,これら構造体の扱いが簡単になったことが大きな改訂部分である.
Id: C8.tex,v 1.11 2001-03-23 14:18:24+09 naito Exp
このように構造体を引数とする関数,または,構造体を戻り値とする関数では, 関数呼び出し, およびそこ からの復帰の際に,構造体のデータすべての値のコピーが行われる. したがって, 巨大な構造体に対するこ れらの操作には,関数呼び出しのオーバーヘッドが大きくなってしまう. それを避けるには,構造体へのポ インタを利用することが望ましい. ポインタを利用すれば,その指し示す先が何であっても,そのデータは
（ＯＳに依存した）一定のデータ量に過ぎない.
6.18.1.5 構造体へのポインタと関数
はじめに, 構造体へのポインタをつくってみよう. 上で定義したstruct complex 型の構造体へのポイ ンタと,ポインタを経由したメンバーへの参照は次の例のようになる.
Example 6.18.7 はじめに,構造体変数と,そのポインタを作成する.
struct complex z, *pz ; pz = &z ;
これにより, 構造体へのポインタpz は構造体変数zの先頭アドレスを示すこととなる. この時, pzを経 由して,zのメンバーへアクセスするための方法としては,
(*pz).real ; pz->real ;
の２種類が考えられる. ここで,演算子 -> は構造体ポインタの指し示す構造体のメンバーへの参照を表 す演算子であり,実は上の２つの式は等価である.
Remark 6.18.2 ここで,(*pz).realのかわりに*pz.realと書いたとすると,これは演算子の優先順位 より*(pz.real)を表すが,pz.realはポインタではないので,誤りとなる.
Remark 6.18.3 もし, struct sphere s, *ps ; ps = &s ;
と定義されているとき, s.center.real ps->center.real (s.center).real (ps->center).real
は等価である. これは,.,->は最も優先順位が高く,その結合法則が左から右となっているからである.
このような構造体へのポインタを利用して,上でつくった complex_addのポインタ版をつくってみよう.
Example 6.18.8 一つの例は,引数として求めるべき値を入れてしまう方法である.
void complex_add(struct complex *z, struct complex *w, struct complex *x) {
x->real = z->real + w->real ;
x->imaginary = z->imaginary + w->imaginary ; return ;
}
この場合,呼び出し方法は, complex_add(&z,&w,&x) とすれば良い.
Id: C8.tex,v 1.11 2001-03-23 14:18:24+09 naito Exp
Example 6.18.9 もう一つの例として,結果の入っている静的変数へのポインタを返すこともできる.
struct complex *complex_add(struct complex *z, struct complex *w) {
static struct complex x ;
x.real = z->real + w->real ;
x.imaginary = z->imaginary + w->imaginary ; return &x ;
}
この場合,呼び出し方法は, struct complex w,z,*px ; px = complex_add(&z,&w) ; とすれば良い.
6.18.1.6 構造体の配列
構造体はそれ自身を配列にしたり,構造体のフィールドに既に定義されている構造体を用いることがで きる. 構造体を配列にするには,以下のような定義をすれば良い.
struct complex z[10] ;
これは,struct complex型の構造体の１０個の配列を定義している.
また,構造体変数がどれだけのメモリ量を利用しているかを知るには,sizeof演算子を利用すれば良い.
sizeof(struct complex)
とすると,complexというタイプの構造体変数の占めるメモリ量を知ることができる91. Remark 6.18.4 たとえば,
struct { char c ; int n ; } ;
によって定義された構造体は,intが４バイトの時, 必ずしも５バイトを占めるわけではない. 実際, 多く の場合８バイトとなるだろう. これは,int型の変数は（多くのアーキテクチャで）ワード境界に整列され るという性質があるからである. sizeof演算子は正しくそのバイト数を返す.
Example 6.18.10 構造体として,
• 氏名
• 学籍番号
• 試験の得点
をメンバーに持つものを作成し,その構造体を型に持つ要素数３の配列を作成する. さらに,その配列を試 験の得点の高い順に並び替える. もし,試験の得点が同じであれば,学籍番号を文字列の辞書式順序にした がって,順序が小さいものを前にする.
91この例の場合,sizeof(struct complex)とsizeof zでは,返す値が異なっている.sizeof(struct complex)はcomplex 構造体のバイト数を返すのに対し,sizeof z は,変数 z の占めるバイト数を返す. したがって,この場合には sizeof(struct complex)*10がsizeof zに等しい.
したがって,sizeof z / sizeof(struct complex) とすることにより,配列の要素数を得ることができる. これは,sizeof z / sizeof z[0] としても同じである.
Id: C8.tex,v 1.11 2001-03-23 14:18:24+09 naito Exp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct personal_data { char name[40] ; char number[10] ; int point ; } ;
extern int compare(struct personal_data *, struct personal_data *) ; int main(int argc, char **argv)
{
struct personal_data pd[3] = {
{"内藤久資", "0010011", 80}, {"藤原一宏", "0010012", 100}, {"木村芳文", "0010013", 100}
} ; int i ;
qsort((struct personal_data *)pd,
sizeof(pd)/sizeof(struct personal_data), sizeof(struct personal_data),
(int (*)(const void *, const void *))compare) ; for(i=0;i<3;i++)
printf("%s %s %d\n", (pd+i)->name, (*(pd+i)).number, pd[i].point) ; return 0 ;
}
int compare(struct personal_data *a, struct personal_data *b) {
if (a->point > b->point) return -1 ; else if (a->point < b->point) return 1 ; return strcmp(a->number,b->number) ; }
結果表示のところで, 各メンバーへの参照に３種類の方法を用いている. Cの標準関数qsortは
#include <stdlib.h>
void qsort(void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));
と定義され,base で参照されるポインタを先頭にする配列を,compar関数値によってソート（並び替え）
を行う. この時,一つの配列要素の大きさはwidthで表され, 配列要素数はnelで表される.
6.18.1.7 演習問題
Exercise 6.18.1 構造体の構成がどのようなものであっても,その構造体変数２つの内容を入れ替える関 数を書け.
Exercise 6.18.2 Example 6.18.1で作った複素数を表す構造体を利用して,かけ算,割算を計算する関数 を作れ.
Exercise 6.18.3 Example 6.18.2で作った複素平面内の円を表す構造体を利用して,与えられた複素数が 円の内部にあるかどうかを判定する関数を書け.
Exercise 6.18.4 次のプログラムの出力結果がなぜそうなるのかを考えよ.
Id: C8.tex,v 1.11 2001-03-23 14:18:24+09 naito Exp
#include <stdio.h>
int main() {
struct S1 { char c[4], *s ; } s1 = {"abc", "def" } ; struct S2 { char *cp ; struct S1 ss1 ; }
s2 = { "ghi", { "jkl", "mno" }}, s3 = { "pqr", { "stu", "vwx" }} ; struct S3 { struct S1 *sp1[2] ; }
s4 = { &s2.ss1, &s3.ss1} ; struct S1 *sp2 = s4.sp1[0] ;
printf("s1.c[0] = %c\t*s1.s = %c\n", s1.c[0], *s1.s) ;
printf("s1.c = %s\ts1.s = %s\n", s1.c, s1.s) ;
printf("s2.cp = %s\ts2.ss1.s = %s\n", s2.cp, s2.ss1.s) ;
printf("++s2.cp = %s\t++s2.ss1.s = %s\n", ++s2.cp, ++s2.ss1.s) ;
printf("s4.sp1[0]->c = %s\ts4.sp1[0]->s = %s\n", s4.sp1[0]->c, s4.sp1[0]->s) ;
printf("s4.sp1[0]->c[0] = %c\ts4.sp1[1]->s[1] = %c\n", s4.sp1[0]->c[0], s4.sp1[1]->s[1]) ;
printf("*(s4.sp1) = %s\t*(s4.sp1+1) = %s\n",
*(s4.sp1),*(s4.sp1+1)) ; }
6.18.2 構造体を利用したデータ構造
構造体を利用すると,アルゴリズムの実現に役立つリスト(list),ツリー(tree)といったデータ構造を実 現することができる.
これらのデータ構造は,そのデータ量があらかじめわかっているならば,ポインタを利用せずに実現でき るが,データ量がアプリオリにはわからない時にはポインタを使わざるをえない. ここでは,これらのデー タ構造が,どのようなものかを見ていこう.
6.18.2.1 リスト
リストとは,データが一列につながったものである. 各データは次のデータへのポインタを持ち,最後の データが持つ次のデータへのポインタは何も指し示していないという形で実現できる. リストになったデー タを操作するには,ポインタを動かせば良い. 具体的には,次のような形式になっている.
6.18.2.2 ツリー
ツリーとは,各データが１つ以上の他のデータへのポインタを持ったものである. 各データは他のデータ へのポインタを持ち, 最後のデータが持つ他のデータへのポインタは何も指し示していないという形で実 現できる. 具体的には,次のような形式になっている.
Id: C8.tex,v 1.11 2001-03-23 14:18:24+09 naito Exp