集合の表現

アルゴリズムとデータ構造
補足資料7-1
「メモリでの『構造体の配列』」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
アドレス（32bit）
中身（1記憶単位は8bit）
…
…
0x 40ea 0800
1101 0000
0x 40ea 0801
0000 0111
0x 40ea 0802
x
x.key
0000 0000
0x 40ea 0803
0000 0000
0x 40ea 0804
0000 0110
0x 40ea 0805
0x 40ea 0806
0000 0000
x.name
x.name[0] 0101 1001
0x 40ea 0807
x.name[1] 0100 1110
0x 40ea 0808
x.name[2] 0101 0101
0x 40ea 0809
x.name[3] 0000 0000
0x 40ea 080a
x.name[4] 0100 0001
0x 40ea 080b
x.name[5] 1101 0000
0x 40ea 080c
x.name[7] 0100 1100
0x 40ea 080d
0110 1111
0x 40ea 080e
1010 0111
0x 40ea 080f
0101 0000
0x 40ea 0810
1101 0000
0x 40ea 0811
0100 0001
0x 40ea 0812
0100 1011
0x 40ea 0813
1101 0100
0x 40ea 0814
0100 0001
0x 40ea 0815
0101 0000
0x 40ea 0816
0100 1011
…
…
struct item{
int key;
char name[7];
};
main()
{
struct item x;
x.key = 1536;
x.name[0]=‘Y’;
x.name[1]=‘N’;
x.name[2]=‘U’;
x.name[3]=‘\0’;
…
}
x
x.key
x.name
x.name[0]
struct item{
int key;
char name[7];
};
main()
{
struct item x;
x.name[1]
x.key = 1536;
x.name[0]=‘Y’;
x.name[1]=‘N’;
x.name[2]=‘U’;
x.name[3]=‘\0’;
…
x.name[2]
x.name[3]
x.name[4]
x.name[5]
x.name[7]
}
x
struct item{
int key;
char name[7];
};
x.key
1536
x.name
x.name[0]
x.name[1]
x.name[2]
x.name[3]
Y
N
U
\0
main()
{
struct item x;
x.key = 1536;
x.name[0]=‘Y’;
x.name[1]=‘N’;
x.name[2]=‘U’;
x.name[3]=‘\0’;
…
x.name[4]
x.name[5]
x.name[7]
}
x
struct item{
int key;
char name[7];
};
x.key
x.name
1536
YNU
main()
{
struct item x;
x.key = 1536;
x.name[0]=‘Y’;
x.name[1]=‘N’;
x.name[2]=‘U’;
x.name[3]=‘\0’;
…
}
アドレス（32bit）
中身（1記憶単位は8bit）
…
…
0x 40ea 0800
1101 0000
0x 40ea 0801
0000 0111
0x 40ea 0802
a[0] a[0].key
0000 0000
0x 40ea 0803
0000 0000
0x 40ea 0804
0000 0110
0x 40ea 0805
0000 0000
a[0].name
0x 40ea 0806
a[0].name[0] 0101 1001
0x 40ea 0807
a[0]. name[1] 0100 1110
0x 40ea 0808
a[0]. name[2] 0101 0101
0x 40ea 0809
a[0]. name[3] 0000 0000
0x 40ea 080a
a[0]. name[4] 0100 0001
0x 40ea 080b
a[0]. name[5] 1101 0000
0x 40ea 080c
a[0]. name[7] 0100 1100
0x 40ea 080d
a[1] a[1].key
struct item{
int key;
char name[7];
};
main()
{
struct item a[5];
a[0].key = 1536;
a[0].name[0]=‘Y’;
a[0].name[1]=‘N’;
a[0].name[2]=‘U’;
a[0].name[3]=‘\0’;
0000 0000
0x 40ea 080e
0000 0000
0x 40ea 080f
0000 0001
0x 40ea 0810
0000 0000
a[1].key = 256;
a[1].name[0]=‘M’;
a[1].name[1]=‘I’;
a[1].name[2]=‘T’;
a[1].name[3]=‘\0’;
a[1].name
0x 40ea 0811
a[1].name[0] 0100 1101
0x 40ea 0812
a[1]. name[1] 0100 1001
0x 40ea 0813
a[1]. name[2] 0101 0100
0x 40ea 0814
a[1]. name[3] 0000 0000
0x 40ea 0815
a[1]. name[4] 0101 0000
0x 40ea 0816
a[1]. name[5] 0100 1011
…
… a[1]. name[7]
…
}
a[0] a[0].key
1536
a[0]. name YNU
a[1] a[1].key
256
a[1]. name MIT
a[2] a[2].key
struct item{
int key;
char name[7];
};
main()
{
struct item a[5];
a[0].key = 1536;
a[0].name[0]=‘Y’;
a[0].name[1]=‘N’;
a[0].name[2]=‘U’;
a[0].name[3]=‘\0’;
2049
a[2]. name UCLA
a[3] a[3].key
87
a[1].key = 256;
a[1].name[0]=‘M’;
a[1].name[1]=‘I’;
a[1].name[2]=‘T’;
a[1].name[3]=‘\0’;
a[3]. name TU/e
a[4] a[4].key
1562
a[4]. name BYU
…
}
a[0] a[0].key
a[0] a[0].key
1536
a[0]. name YNU
a[1] a[1].key
a[0]. name TU/e
a[1] a[1].key
256
a[1]. name MIT
a[2] a[2].key
a[3] a[3].key
87
a[3]. name TU/e
a[4] a[4].key
1562
a[4]. name BYU
整列(sort)前
256
a[1]. name MIT
a[2] a[2].key
2049
a[2]. name UCLA
87
sort(a,5)
1536
a[2]. name YNU
a[3] a[3].key
1562
a[3]. name BYU
a[4] a[4].key
2049
a[4]. name UCLA
整列(sort)後
a[0]
a[0].key
a[1]
1536
a[0]. name YNU
a[1].key
a[2]
256
a[1]. name MIT
a[2].key
a[3]
2049
a[2]. name UCLA
a[3].key
a[4]
87
a[4].key
1562
a[3]. name TU/e
a[4]. name BYU
a[3]
a[4]
sort(a,5)
a[0]
a[0].key
a[1]
87
a[0]. name TU/e
a[1].key
a[2]
256
a[1]. name MIT
a[2].key
1536
a[2]. name YNU
a[3].key
1562
a[3]. name BYU
a[4].key
2049
a[4]. nameUCLA

Download Report