6.18 データ構造
6.18.1 構造体
void error_jmp(void) {
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 で開放するようにプログラムを書換えよ.
ここで, complexが構造体タグであり,double 型の２つのメンバー real とimaginary を持つ構造体と して定義されている. さらに,識別子xはstruct complexという型を持ったオブジェクトとして定義さ れる.
real
imaginary struct complex
Example 6.18.2 上の例(Example 6.18.1)と同じ構造体を定義するが,構造体タグを持たないもの：
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
とすれば良いことが分かる.
6.18.1.3 構造体の初期化と代入
構造体を初期化するには,そのメンバーに値を代入しても良いが,一方で, struct sphere s0 = {{0.0, 0.0}, 1.0} ;
struct sphere s1 = {0.0, 0.0, 1.0} ;
という初期化も可能である92. また,構造体の変数への一括代入も可能である.
struct sphere s0 = {{0.0, 0.0}, 1.0} ; struct sphere s1 ;
s1 = s0 ;
によっても,s0の内容をs1に代入することが可能である.
6.18.1.4 構造体と関数
構造体を引数にとる関数,構造体を戻り値とする関数定義することができる93.
92当たり前だが,上の初期化の方が何をしているかは分かりやすい.
93Kernighan-Ritchieの初版（いわゆるtraditionalなＣ）では,構造体への一括代入,構造体を引数とする関数,構造体を戻り値
とする関数などは許されてはいなかった.したがって, traditional Cでこのようなことを行うためには,すべて,構造体のポインタ を受け渡しする必要があった. また, traditional Cでは,自動構造体（関数内部での自動変数となる構造体）の初期化も許されてい なかった. ANSI規格（Kernighan-Ritchie第２版）では,これら構造体の扱いが簡単になったことが大きな改訂部分である.
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) ; を行う必要がある.
このように構造体を引数とする関数,または,構造体を戻り値とする関数では, 関数呼び出し, およびそこ からの復帰の際に,構造体のデータすべての値のコピーが行われる. したがって,巨大な構造体に対するこ れらの操作には,関数呼び出しのオーバーヘッドが大きくなってしまう. それを避けるには,構造体へのポ インタを利用することが望ましい. ポインタを利用すれば,その指し示す先が何であっても,そのデータは
（ＯＳに依存した）一定のデータ量に過ぎない. (cf. Remark 6.18.4.)
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) とすれば良い.
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) ; とすれば良い.
Remark 6.18.4 構造体を戻り値とする関数と,構造体のポインタを戻り値とする関数に関する比較をし
てみよう. ここでは,次のような３つの例を考えてみる.
1. 有理数を表す構造体 struct fractional {
int n ; /* 分子 */
int d ; /* 分母 */
} ; に対して,
struct fractional
frac_add(struct fractional a, struct fractional b) {
struct fractional c ; c.n = a.d*b.n + b.d*a.n ; c.d = a.d*b.d ;
return c ; }
struct fractional
*frac_add(struct fractional a, struct fractional b) {
static struct fractional c ; c.n = a.d*b.n + b.d*a.n ;
c.d = a.d*b.d ; return &c ; }
を考えよう.
2. 複素数を表す構造体 struct complex {
double re ; /* 実部 */
double im ; /* 虚部 */
} ; に対して,
struct complex
complex_add(struct complex a, struct complex b) {
struct complex c ; c.re = a.re + b.re ; c.im = a.im + b.im ; return c ;
}
struct complex
*complex_add(struct complex a, struct complex b) {
static struct complex c ; c.re = a.re + b.re ; c.im = a.im + b.im ; return &c ;
} を考えよう.
3. さらに, もっと極端な例として, 構造体 struct test_str {
char a ; } ;
に対して,
struct test_str
test_func(struct test_str a) {
struct test_str b ; b.a = 2*a.a ; return b ; }
struct test_str
*test_func(struct test_str a) {
static struct test_str b ; b.a = 2*a.a ;
return &b ; }
を考えよう.
これら３つの構造体に関するそれぞれ２種類の呼出しに掛る時間を計測すると, およそ次のような結果が 得られる94.
値を返す アドレスを返す
有理数 4.19 s 3.79 s
複素数 3.19 s 2.28 s
char 1.13 s 1.64 s
この環境では, 有理数の構造体のサイズは64ビット,複素数の構造体は128 ビット,最後の例の構造体は 8ビットであり,ポインタのサイズは32ビットである. 戻り値として利用されるメモリサイズが実行時間 に反映されていることに注意しよう. すなわち,構造体のサイズが大きくなると,「ポインタを戻り値とす る関数」の方が,実行時間の上からは有利に働く.
しかしながら, 「ポインタを戻り値とする関数」では, そのポインタは関数内部の静的ポインタである ので,
94これは,10000000回呼出しを行った結果をtimeコマンドで計測した結果である.環境は, Solaris 2.6, gcc 2.95.1, UltraSparc 400MHzである.
struct complex w,z,*px ; px = complex_add(z,w) ; のようにして得た結果は, px = complex_add(z,w) ; z = *px ;
として保存しておかなければならない. すなわち, px = complex_add(z,w) ;
px = complex_add(px,w) ;
とすると,２度めの呼出しの際に, メモリ領域が破壊されるため, 正しい結果を得ることが出来ない.
6.18.1.6 構造体の配列
構造体はそれ自身を配列にしたり,構造体のフィールドに既に定義されている構造体を用いることがで きる. 構造体を配列にするには,以下のような定義をすれば良い.
struct complex z[10] ;
これは,struct complex型の構造体の１０個の配列を定義している.
また,構造体変数がどれだけのメモリ量を利用しているかを知るには,sizeof演算子を利用すれば良い.
sizeof(struct complex)
とすると,complexというタイプの構造体変数の占めるメモリ量を知ることができる95. Remark 6.18.5 たとえば,
struct { char c ; int n ; } ;
によって定義された構造体は,intが４バイトの時, 必ずしも５バイトを占めるわけではない. 実際, 多く の場合８バイトとなるだろう. これは,int型の変数は（多くのアーキテクチャで）ワード境界に整列され るという性質があるからである. sizeof演算子は正しくそのバイト数を返す.
Example 6.18.10 構造体として,
• 氏名
• 学籍番号
• 試験の得点
95この例の場合,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] としても同じである.
をメンバーに持つものを作成し,その構造体を型に持つ要素数３の配列を作成する. さらに,その配列を試 験の得点の高い順に並び替える. もし,試験の得点が同じであれば,学籍番号を文字列の辞書式順序にした がって,順序が小さいものを前にする.
#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は