Algorithms and Data Structures on C
リストと配列
Algorithms and Data Structures on C
この回の要点
• C言語における変数
– プリミティブ型とポインタの違い
– 参照型における実体オブジェクトへの参照
• リストとは？
• 配列によるリスト
– 配列の利点と欠点
– C言語による配列の実現
– 配列の代入と複製の違い
Algorithms and Data Structures on C
データ構造
• アルゴリズム＋データ構造＝プログラム
– アルゴリズム・・・データをどのように加工するか
– データ構造・・・データをどのように表現するか
• アルゴリズムと、データ構造とは、互いに密接に関
係している
– プログラムを書くとき、アルゴリズムとデータ構造とを同時
に考えていく必要がある
– 並べ替えアルゴリズムの場合
• データの移動がほとんどないアルゴリズム・・・配列による表現
• データの削除・挿入が頻繁にあるアルゴリズム・・・リンクリストに
よる表現
– どちらでも可能であるが、効率が問題
Algorithms and Data Structures on C
変数
• 変数（variables）とは
– プログラム中で、値が変化するデータを格納する箱
– １つの箱に、１つのデータを格納できる
– 箱にはいろいろな大きさがある（型、Type）
• 変数には名前をつける＝変数名（識別子）
箱
x =
変数名
123
pi =
str =
3.141592
“Hello World”
pt =
(100,120)
p =
PersonalData
箱にはいろいろな
データが入っている
Algorithms and Data Structures on C
C言語の基本型（プリミティブ）
種類
型
長
signed
unsigned
型なし
void
ー
ー
ー
文字型
char
8
-128 ~ 127
0 ~ 255
short
16 -32768 ~ 32767
int
32
-2147483648
~ 2147483647
0 ~ 4294967295
long
32
-2147483648
~ 2147483647
0 ~ 4294967295
long long
64
-9223372036854775808
~ 9223372036854775807
0~
18446744073709551615
float
32
最小の正の数1.175494351e-38
最大値3.402823466e+38
double
64
最小の正の数2.2250738585072014e-308
最大値1.7976931348623158e+308
整数型
浮動小
数点型
0 ~ 65535
ILP32（一般的な32ビット環境）での例
Algorithms and Data Structures on C
ポインタ型
• メモリへの参照を示す
• 参照するメモリのアドレスが格納されている
• 型の後に＊（アスタリスク）を付けた型
– int* ip;
– double* dp;
（変数名の方に＊を付けて宣言することも多い。が、＊は変数名ではない）
アドレス幅
ip
参照
dp
参照
123
4バイト
3.14
8バイト
メモリ
メモリ
Algorithms and Data Structures on C
プリミティブとポインタ
実体（値）
プリミティブ
int x =
double pi =
int* ip =
実体
（オブジェクト）
123
3.141592
123
参照
“Hello World”
char* str =
参照
MyData* dp =
参照
ポインタ
構造体
実体への参照
Algorithms and Data Structures on C
変数への代入
• プリミティブ
int x=123;
double pi=3.141592;
MyPoint pt={3,4};
• ポインタ
プリミティブには直接数値を代入
構造体の初期化
プリミティブのアドレスを代入
int* ip=&x;
double* dp=π
const char* str=“Hello World”;
int* data=(int*)malloc(100*sizeof(int));
MyPoint* pt1=(MyPoint*)malloc(sizeof(MyPoint));
malloc() を使用
free()でメモリを解放すること！
Algorithms and Data Structures on C
構造体
• いくつかのデータをまとめた型
–
–
–
–
キーワードstructで定義する
タグ名を付ける
内部に複数の異なる型の変数を持つ
構造体の宣言の形
struct タグ名 {
データ型 メンバー名
データ型 メンバー名
・・・
};
– 変数の宣言
struct タグ名 変数名;
– メンバーへのアクセス（.か->を使用）
変数.メンバー名
ポインタ変数->メンバー名
Algorithms and Data Structures on C
構造体の例１
#include <stdio.h>
struct MyPoint {
int x;
int y;
};
構造体タグの宣言
初期化
int main(void){
struct MyPoint pt1;
struct MyPoint pt2={ 3,4 };
struct MyPoint *pt3=&pt2;
構造体タグを使って
変数を宣言
printf(“(%d,%d)¥n”,pt1.x,pt1.y);
printf(“(%d,%d)¥n”,pt2.x,pt2.y);
printf(“(%d,%d)¥n”,pt3->x,pt3->y);
}
Algorithms and Data Structures on C
構造体の例２
#include <stdio.h>
typedef struct {
int x;
int y;
} MyPoint;
int main(void){
MyPoint pt1;
MyPoint pt2={ 3,4 };
MyPoint *pt3=&pt2;
typedefを使った場合
タグ名は省略
構造体型の定義
構造体型を使って
変数を宣言
printf("(%d,%d)¥n",pt1.x,pt1.y);
printf("(%d,%d)¥n",pt2.x,pt2.y);
printf("(%d,%d)¥n",pt3->x,pt3->y);
}
Algorithms and Data Structures on C
抽象データ型とリスト（list）
• 抽象データ型とは
– データが持つ性質＋データに行える操作
– 「クラス」として表現される
– 中にどんなデータが入るかは関知しない
• リストとは
– 一般には、一覧表、目録、名簿
– 要素を順番に並べた構造を表す総称
•
•
•
•
•
•
データを一列に並べたもの→線形リスト
リスト x の k 番目の要素→ x[k] とすると、
それの1つ前→ x[k-1]
番号によって
それの1つ後→ x[k+1]
要素にアクセス可能
先頭の要素→ x[1]
（ただし、C言語の配
末尾の要素→ x[n] （n個の場合）
列の添字は0から始
まるので注意）
Algorithms and Data Structures on C
抽象データ型としてのリスト
• リストのメンバ変数
– そのリストに格納されているデータ
• リストが持つべきメソッド
–
–
–
–
–
–
–
–
–
–
k番目の要素の内容を読む・書く
k番目の要素の前に要素を挿入する
k番目の要素の後に要素を挿入する
k番目の要素を削除する
特定のキーを持つ要素を取り出す
複数のリストを1つにまとめる
1つのリストを複数のリストに分割する
リストを複製する
リストの要素数を得る
・・・
• すべのメソッドを効率よく実現するリストは困難
– 必要に応じて、どのメソッドを重視するかで、データ構造が決まる
Algorithms and Data Structures on C
配列（array）
0
• リストの実現の一種
• たくさんの箱を一列に並べた構造
1
2
– 箱の数（配列の大きさ）は固定
3
• 配列を作るときに決める
• あとから変更はできない
– 箱には番号（添え字）がつけられる
N－1
• 0,1,2,・・・,N－1（JavaやCの場合）
– 番号を使って、中のデータにアクセス可能
• たくさんのデータを１つの名前（配列名）で管理できる
• 多くのデータを扱うプログラムで有効
• 多次元配列
– 配列の添え字が２つ以上
Algorithms and Data Structures on C
配列の利点と欠点
• 利点
– 箱の番号を利用してデータに直接アクセスできる＝O(1)
– データだけから構成され、無駄なメモリが不要
• 欠点
– サイズが固定
– 途中に要素を挿入、削除する際、前後のデータを移動さ
せる必要がある＝O(N)
0 1 2 3 ・・・
削除
後ろにずらす
前にずらす
挿入
N-1
Algorithms and Data Structures on C
C言語の配列１
• C言語の配列は連続するメモリ領域（＝ポインタ）
• 変数名に[]をつけて宣言する
int a[10];
// 10個の箱を持つ配列変数a
int b[5]={1,2,3,4,5}; // 初期化
int c[]={1,2,3}; // 初期化すればサイズは不要
• 配列要素へのアクセス
a[0]=3;
a[9]=123;
• ２次元配列
int x[3][4];
// ３行４列の２次元行列
int y[][2]={{1,2},{3,4},{5,6}};
// ３行２列
（実際には２次元配列も１次元として確保されている）
• 注意
– C言語の配列のインデックスはチェックされない
– 初期化しなければ、何が入ってるかは不定
Algorithms and Data Structures on C
C言語の配列２
• ポインタとしての配列
int* a=(int*)malloc(10*sizeof(int)); // 10個の配列
MyPoint* pt=(MyPoint*)malloc(5*sizeof(MyPoint));
// 5個のMyPointの配列
• 配列へのアクセス
– 前ページの配列同様、[]でアクセスできる
a
参照
配列
変数
a[0]
?
a[1]
?
a[2]
?
a[3]
?
a[9]
?
pt
参照
配列
変数
pt[0]
MyPoint
pt[1]
MyPoint
pt[2]
MyPoint
pt[3]
MyPoint
pt[4]
MyPoint
Algorithms and Data Structures on C
ポインタの配列
• MyPointクラスのポインタの配列
MyPoint** pt=(MyPoint**)malloc(5*sizeof(MyPoint*));
pt[1]=(MyPoint*)malloc(sizeof(MyPoint)) // 実体
pt[3]=(MyPoint*)malloc(sizeof(MyPoint));
pt[4]=(MyPoint*)malloc(sizeof(MyPoint));
pt
参照
配列自体
の参照
pt[0]
?
pt[1]
参照
pt[2]
?
pt[3]
参照
pt[4]
参照
２段階の参照
(x,y)
実体
（ヒープメモリ）
(x,y)
MyPoint
型の参照
(x,y)
Algorithms and Data Structures on C
配列の代入と複製
• 配列の代入
– 参照だけが代入され、その先は同じもの
• 配列の複製（コピー）
– 配列の先は別々なオブジェクトとなる
memcpy(c,a,sizeof(a));
int a[5]
参照
a[0]
5
a[1]
14
a[2]
3
a[3]
8
a[4]
4
b=a
int *b
参照
int c[5]
参照
c[0]
5
c[1]
14
c[2]
3
c[3]
8
c[4]
4
別なメモリ
Algorithms and Data Structures on C
代入と複製の違い
• 代入と複製の違いを確認する
–
–
–
–
–
–
配列 a を { 5,14,3,8,4 } で初期化
a を配列 b に代入
a を配列 c に複製
a と b , c を表示
a の2番目 a[1] の 14 を 99 に変更
a と b , c を表示
• 結果
– 代入・・・b[1] は 99 に変わる
– 複製・・・c[1] は 14 のまま
Algorithms and Data Structures on C
ArrayTest.c
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
void printArray(char c,int *a,int s){
printf("%c: ",c);
int i;
for(i=0;i<s;i++)
printf("%d ",a[i]);
printf("¥n");
}
実行結果：
int main(void){
int a[5]={5,14,3,8,4};
int *b=a;
int c[5];
memcpy(c,a,sizeof(a));
a[1]=99;
printArray('a',a,5);
printArray('b',b,5);
printArray('c',c,5);
}
$ gcc –o ArrayTest ArrayTest.c
$ ./ArrayTest.exe
a: 5 99 3 8 4
b: 5 99 3 8 4
c: 5 14 3 8 4
$
Algorithms and Data Structures on C
プログラムの作成方法
• 実際にプログラム
– ヘッダファイルと実装ファイルに分けて作る
• ヘッダファイル（.h）
– データ型（クラス）の宣言
– データ操作（関数）のプロトタイプ宣言
• 実装ファイル（.cc）
– 関数の具体的なコード
– 拡張子.ccで書くことで、コンパイラがソースコードをC++として
扱うようになる
– C++言語はC言語の拡張
– この講義ではC言語の機能だけを用いるが、C++として扱って
おくと後々便利（かもしれない）
– ということで、以下ではコンパイラとしてg++を用いる
Algorithms and Data Structures on C
ヘッダファイル
• ソースファイルを分割する手段
• 拡張子 .h
• #include文で読み込む
– プリプロセッサによる作業
– 標準ヘッダ <stdio.h>
– 自作ヘッダ “hogehoge.h”
.h
.h
.h
#include
• 目的
–
–
–
–
複数のソースで共通して使う場合
定義を書く場合
プロトタイプ宣言
関数の実体を書いてはいけない
• リンクエラーになる場合がある
.cc
コンパイル
.o
Algorithms and Data Structures on C
コンパイルとリンク
• コンパイル
– .hと.ccから.oを作る
– 共通で使える.oを使う場合
– 規模が大きい場合
.o
.o
• リンク
リンク
– .oから.exeを作る
• コンパイル＆リンク
– .hと.ccから直接.exeを作る
– 規模が小さい場合はこれでもよい
具体例：
$ g++ –o test1 test1.cc
$ ./test1
.o
.exe
Algorithms and Data Structures on C
成績型Seiseki
• 小学生の1回の試験の成績
– 名前と国語、算数、理科、社会の点数
– 成績の生成と表示ができる
メンバー
const char*
name
名前
int
kokugo
国語の点数
int
sansuu
算数の点数
int
rika
理科の点数
int
shakai
社会の点数
Seiseki*
makeSeiseki(const char*,int,int,int,int)
成績の生成
void
print(Seiseki*)
成績の表示
関数
Algorithms and Data Structures on C
Seiseki.h
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#ifndef __Seiseki__h
#define __Seiseki__h
#include <stdio.h>
#include <stdlib.h>
ヘッダファイルの重複読み込みを回避
// データ型宣言
typedef struct {
const char* name;
int kokugo;
int sansuu;
int rika;
int shakai;
} Seiseki;
// プロトタイプ宣言
Seiseki* makeSeiseki(const char*,int,int,int,int);
void print(Seiseki*);
void free(Seiseki*);
#endif // __Seiseki__h
Algorithms and Data Structures on C
Seiseki.cc
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
#include "Seiseki.h"
ヘッダファイルの読み込み
// 成績の生成（コンストラクタ）
Seiseki* makeSeiseki(const char *n,int k,int m,int r,int h){
Seiseki *s=(Seiseki*)malloc(sizeof(Seiseki));
s->name=n;
s->kokugo=k;
s->sansuu=m;
Seiseki型のメモリを確保し、
s->rika=r;
中にデータを入れて、返す
s->shakai=h;
return s;
}
// 成績の表示
void print(Seiseki *s){
printf(“%s 国%d 算%d 理%d 社%d¥n",
s->name,s->kokugo,s->sansuu,s->rika,s->shakai);
}
// 成績の解放
void free(Seiseki *s){
free((void*)s);
}
Algorithms and Data Structures on C
TestSeiseki.cc
1. #include "Seiseki.h"
2.
3. int main(){
4.
Seiseki *s[3];
5.
s[0]=makeSeiseki("山田太郎",78,55,80,88);
6.
s[1]=makeSeiseki("佐藤花子",90,80,85,87);
7.
s[2]=makeSeiseki("中村裕次郎",40,62,72,21);
8.
9.
for(int i=0;i<3;i++)
s
s[0]
10.
print(s[i]);
s[1]
“山田太郎”
11.
78 55 80 88
12.
for(int i=0;i<3;i++)
s[2]
13.
free(s[i]);
14. }
“佐藤花子”
“中村裕次郎”
90 80 85 87
40 62 72 21
Algorithms and Data Structures on C
課題151019
• TestSeiseki.ccをコンパイルして実行し、実行結果を示せ。
• 次のページのTestSeiseki2.ccは、ポインタ配列の代わりに二重ポインタ
をつかって、同じプログラムを書きなおしたものである。このコードの不足
分を埋めて完成させ、完成したコードと実行結果を示せ。
•
作成方法：ワードで作成し、実行結果は図として貼り付けること。
• ファイル名は”scXXXXXX-al151019.docx”
• 提出方法：メールで渕田まで送付すること。
• メールの本文中にも学籍番号を氏名を明記すること。
• 提出先：[email protected]
• メールタイトル：”アルゴリズム課題151019” ← 厳守！
• 期限：2015年10月25日（日） 24：00
Algorithms and Data Structures on C
TestSeiseki2.cc
1. #include "Seiseki.h"
2.
ここを変えた
3. int main(){
4.
Seiseki **s;
5.
/* ここにs用のメモリを確保するコードを追加する */
6.
s[0]=makeSeiseki("山田太郎",78,55,80,88);
7.
s[1]=makeSeiseki("佐藤花子",90,80,85,87);
8.
s[2]=makeSeiseki("中村裕次郎",40,62,72,21);
9.
10.
for(int i=0;i<3;i++)
11.
printSeiseki(s[i]);
12.
13.
for(int i=0;i<3;i++)
14.
freeSeiseki(s[i]);
15.
/* ここにs用のメモリを開放するコードを追加する */
16. }
Algorithms and Data Structures on C
リストと配列
終了
© Copyright 2024 ExpyDoc
