/*
* 課題 CNAME-01
*
* 2017/12/08 FILENAME
*
* 動的なメモリの確保
* キーボードより正の整数を幾つか入力して、その要素が入った配列を返す
* 0 以下の整数が入力されたら、終了とする
* 配列のサイズは、正の整数の個数 + 1 とし、最後の要素には 0 を入れる
*
* 考え方
* 入力がある限り、再帰呼び出しをする
* 関数が呼び出されるたびに、新しい局所変数の領域が作られる
* ので、そこに、入力データの情報を保存
* 入力が終わりになったら、
* その時点で、入力データ数が確定するので、
* 動的にメモリサイズを指定
* 再帰から戻る段階で、局所変数に保存されている情報を、
* 動的なメモリに保存する
*
* 入力が
* 3, 7, 9, -2 => {3, 7, 9, 0} という領域を作る
*/
/*
* 利用方法
* コンパイル
* cc -I ~/c/include -o BASENAME.exe FILENAME
* 実行
* ./BASENAME.exe
*/
#include <stdio.h>
#include <malloc.h> /* calloc/free を利用するので必要 */
/*
* read_n_integers
* 呼び出されると、(再帰呼び出しをしながら..)
* 入力データを保持する領域を作り、返す
* 引数の size は、既存の入力データ数
*/
int *read_n_integers( int size ) {
int num; /* キーボードから入力された数値を保存する */
int *value; /* 確保された配列の先頭要素へのポインター */
printf ( "正の整数値を入力してください(0 以下だと入力を終了します):" );
scanf ( "%d", &num );
if ( num <= 0 ) { /* 入力が全部終ったので、配列を作成する */
/* 配列のサイズは、引数で指定された個数 + 1 となる */
if ( ( value = (int *)calloc ( size + 1, sizeof ( int ) ) ) != NULL ) {
/* 動的メモリは取り出せるとは限らないので、結果をチェック */
value[ size ] = 0; /* 最後の要素として 0 を代入 */
} /* else {} */ /* NULL が帰った場合は、そのまま、値として返す */
} else { /* 入力が終っていないので、更に、値を読むために再帰呼び出し */
if ( ( value = read_n_integers( size + 1 ) ) != NULL ) {
/* 結果が NULL でなければ、配列が作られている */
/* size 番目の要素を配列に記録 */
value [ size ] = num;
/* value : int * 型なので、配列と思ってよい */
/* これまでに、 size 以後の所にはデータがはいっている */
} /* else {} */ /* NULL が帰った場合は、そのまま、値として返す */
}
/* いずれの場合でも value を返す */
return value; /* value には、NULL が入っている可能性もある */
/* 問題がおきたら、「問題がおきた」ことを報告する */
/* 自分勝手に、「問題に対応」しない */
}
/*
* main
*/
int main ( int argc, char *argv[] ) {
int *array; /* n 個数の要素をもつ配列の先頭をもつ */
int i;
/* read_n_integers を呼び出して、n 個の整数値を入力する */
/* 引数には、入力済のデータ数を指定するので、最初は 0 を指定する */
if ( ( array = read_n_integers( 0 ) ) != NULL ) {
/* read_n_integers は、NULL を返す可能性がある */
/* 入力された要素を画面に出力 */
for ( i = 0; array[i] > 0; i++ ) {
printf ( "%d th data = %d\n", i, array[i] );
}
/* malloc/calloc で確保したメモリは、必ず free で解放する */
free ( array ); /* 動的に確保した領域は free する */
} /* else {} */ /* NULL の場合はエラーなので、何もしない */
return 0;
}
/*
* 課題 CNAME-01
*
* 2017/12/22 FILENAME
*
* 整数のキュー(queue)
* queue は「行列」の事
* 何か並んでいるもの ( じゃあ、配列や List 何が.. ?? )
* 後ろに並んで、前から短くなる
* データの追加(最後)や削除(先頭)に特徴がある
* 実装
* (例によって、配列をつかってもよいが..)
* (Linked) List をうまくつかって、実現
* List は先頭への追加が簡単なので
* List の先頭を Queue の最後と思えば OK
* 削除 (List 先頭の削除が簡単..)
* -> 削除に都合がよいように、List の最後(Queue の最初) の情報を管理
* ==> ここで、方針を変更して、
* Queue は List の先頭と最後を見る
* ( List は先頭だけ )
* => 削除は、List と同じく先頭で行い、
* => 追加は、List とは別のアプローチをする
List : [ 1, 3, 9, 13 ]
Queue --(先頭)----------------------------------------+
--(末尾) ---+ | |
| |
| v
List ---+ v
| +-------+ +-------+ +-------+ +-------+
+---> | *-----> | *-----> | *-----> | *-----> NULL
+-------+ +-------+ +-------+ +-------+
| 1 | | 3 | | 9 | | 13 |
+-------+ +-------+ +-------+ +-------+
*/
#include <stdio.h>
#include <malloc.h>
/*
* 整数のキュー(queue)
*
* 利用方法
* コンパイル
* cc -o BASENAME.exe FILENAME
* 実行
* ./BASENAME.exe
*/
/*
* Queue は、List の先頭に追加し、最後の要素を削除する事で実現
*/
/* 行列に並んでいるデータを管理するデータ */
/* 基本は、Linked List 同じ */
typedef struct icell {
struct icell *next; /* 次の要素 */
int value; /* 行列の要素 */
} ICell;
/* Queue
* Linked List 先頭と最後を保持する
*/
typedef struct {
ICell *head; /* List の先頭 : Queue の先頭 */
ICell *tail; /* List の最後 : Queue の最後 */
} IQueue;
/*
*/
#define NORMAL (0) /* エラー状態 */
#define ERROR (-1)
/*
*/
#define FALSE (0) /* 真偽値 */
#define TRUE (!FALSE)
/*
* alloc_icell
* セルを一つ作成し、初期化する
*
* p -> t <=> (*p).t の省略記号
* p が構造体のデータへのポインタ値
* *p が構造体データになり
* (*p).t が構造体の要素
* () は、「*」「.」では、「.」の方が強い
* *p.t ==> *(p.t) -> 誤り
*/
ICell *alloc_icell ( int data ) {
ICell *result = (ICell *)malloc(sizeof(ICell));
if ( result != NULL ) {
result -> next = NULL;
/* (*result).next = NULL */
result -> value = data;
/* (*result).value = data */
}
return result;
}
/*
* free_icell
*/
void free_icell ( ICell *icp ) {
free ( icp );
}
/*
* alloc_iqueue
*/
IQueue *alloc_iqueue ( ) {
IQueue *result = (IQueue *)malloc(sizeof(IQueue));
if ( result != NULL ) {
result -> head = result -> tail = NULL;
/*
a = b = c;
<=>
b = c;
a = b;
と同じ
Queue = []
もともと Queue は Linked List の先頭と最後だが
List そのものが空 ([]) なので、
指す先がないので、NULL を入れて、「ない」事を表す
*/
}
return result;
}
/*
* is_empty
*/
int is_empty ( IQueue *iqp ) {
if ( iqp != NULL ) {
return iqp -> head == NULL;
}
return FALSE;
}
/*
* enque ( データの追加 )
*
*
QUEUE = [ a, b, c ]
eque ( QUEUE, x )
[ a, b, c, x ]
QUEUEU ---------+
| v
+-> *-->*-->*-->NULL
a b c
|
v
QUEUEU -----------------+
| |
+-> *-->*-->*---+ |
a b c | |
| |
+---+ <-+
|
*-->NULL
x
*/
int enque ( IQueue *iqp, int data ) {
int result = ERROR;
if ( iqp != NULL ) {
ICell *icp = alloc_icell ( data );
if ( icp != NULL ) {
if ( is_empty ( iqp ) ) {
iqp -> head = icp;
} else {
iqp -> tail -> next = icp;
}
iqp -> tail = icp;
result = NORMAL;
}
}
return result;
}
int deque ( IQueue *iqp ) { /* Linked List の削除同じ */
int result = ERROR;
if ( !is_empty ( iqp ) ) {
ICell *top = iqp -> head;
result = top -> value;
if ( ( iqp -> head = top -> next) == NULL ) {
iqp -> tail = NULL;
}
free ( top );
}
return result;
}
void free_que ( IQueue *iqp ) {
if ( iqp != NULL ) {
ICell *icp = iqp -> head;
ICell *next;
while ( icp != NULL ) {
next = icp -> next;
free_icell ( icp );
icp = next;
}
free ( iqp );
}
}
void print_que ( IQueue *iqp ) {
if ( iqp != NULL ) {
ICell *icp = iqp -> head;
ICell *next;
while ( icp != NULL ) {
next = icp -> next;
printf ( "%d ", icp -> value );
icp = next;
}
}
}
/*
* main
*/
int main ( void ) {
IQueue *iqp = alloc_iqueue();
print_que ( iqp ); putchar ( '\n' );
enque ( iqp, 1 );
print_que ( iqp ); putchar ( '\n' );
enque ( iqp, 2 );
enque ( iqp, 3 );
print_que ( iqp ); putchar ( '\n' );
printf ( "%d\n", deque ( iqp ) );
print_que ( iqp ); putchar ( '\n' );
free_que ( iqp );
return 0;
}
#include <stdio.h>
void sub1(void) {
int i; /* ??? sub1 ?????????L?? */
i = 100;
printf ( "sub1 : &i = %p\n", &i );
}
void sub2(void) {
int j; /* ??? sub2 ?????????L?? */
/* ?u???R(?)?v sub1 ?? i ??????W */
printf ( "sub2 : &j = %p\n", &j );
printf ( "j = %d\n", j );
}
int main(int argc, char *argv[]) {
sub1();
sub2();
return 0;
}
#include <stdio.h>
/*
目的
ユーザが指定した個数の整数値を保持し、
その値を入力したあと、
その逆順番に出力する
比較
以前なら...
十分の大きな配列を用意し、それの一部を使う
*/
#define ARRAY_SIZE 1000 /* おそらく十分に多いであろう.. */
int main(int argc, char *argv[]) {
int data[ARRAY_SIZE]; /* 入力するデータを保持する領域 */
int ndata; /* データの個数 */
int i; /* 配列の添え字 */
printf ( "データの個数を入力してください : " );
scanf ( "%d", &ndata );
if ( ndata >= ARRAY_SIZE ) {
printf ( "Error %d は、大きすぎます %d 以下にしてください\n",
ndata, ARRAY_SIZE );
/* 本当は、 ndata <= 0 の場合も考える必要があるが、パス */
} else { /* 正常に処理ができる */
/* data の入力 */
for ( i = 0; i < ndata; i++ ) {
printf ( "%d 番目のデータを入力してください : ", i + 1 );
scanf ( "%d", &data[i] );
}
/* data を入力と逆に出力する */
for ( i = 0; i < ndata; i++ ) {
printf ( "%d\n", data[ndata-i-1] );
}
/*
for ( i = ndata - 1; i >= 0; i-- ) {
printf ( "%d\n", data[i] );
}
*/
}
return 0;
}
#include <stdio.h>
/*
目的
ユーザが指定した個数の整数値を保持し、
その値を入力したあと、
その逆順番に出力する
新規
領域のサイズを、実行時に決める
メモリのマネージメントを行う必要がある
*/
#include <malloc.h>
/* 以下、動的なメモリ利用をするために必要な
関数の宣言が行われている *
/*
#define ARRAY_SIZE 1000
配列のサイズは、動的に変更可能なので、
サイズを「予め」考える必要はない
*/
int main(int argc, char *argv[]) {
/*
int data[ARRAY_SIZE];
*/
int *data; /* 整数型へのポインタ値を持つ変数 */
/* (int *) 型 */
/* 動的的に確保する領域のアドレス値を保持するため */
/* cf.
int data[]; の時は、data は (int *) 型の定数になる
*/
/* 入力するデータを保持する領域 */
int ndata; /* データの個数 */
int i; /* 配列の添え字 */
printf ( "データの個数を入力してください : " );
scanf ( "%d", &ndata );
/* ここで、初めて、必要な領域サイズが解ったので、
この時点で、そのサイズに対応する、領域を「明示的に」確保する */
data = calloc ( sizeof(int), ndata );
/* calloc が、sizeof(int) * ndata byte の空き領域を
(その空きがあれば、その時点で..) 確保し、その先頭のアドレスを
返す */
/* これは、実質 int data[ndata] としたのとほぼ同じ形 */
/* もし、万が一、十分な領域がなかった場合 */
/* 「NULL」という、「意味のないことが保証されているアドレス値」が
値として、返される */
if ( data == NULL ) {
printf ( "Error %d は、大きすぎます\n",
ndata );
/* 本当は、 ndata <= 0 の場合も考える必要があるが、パス */
} else { /* 正常に処理ができる */
/* data の入力 */
for ( i = 0; i < ndata; i++ ) {
printf ( "%d 番目のデータを入力してください : ", i + 1 );
scanf ( "%d", &data[i] );
/* data[i] -> *(data + i) -> data の値が配列の先頭の要素のアドレスと思う */
/* data が「定数(配列で宣言)」なのか「動的に確保(変数)」かは、無関係 */
}
/* data を入力と逆に出力する */
for ( i = 0; i < ndata; i++ ) {
printf ( "%d\n", data[ndata-i-1] );
}
/*
for ( i = ndata - 1; i >= 0; i-- ) {
printf ( "%d\n", data[i] );
}
*/
}
free ( data );
/* 動的に確保した、領域を、「明示的に」開放する */
return 0;
}
/*
動的に領域を確保したい場合
1) #include <mallo.h> をする
2) 変数宣言、「配列名」に相当するポインタ型の変数を宣言
3) calloc を利用して、領域を確保
# 確保できない可能性(NULL が返る..)があるので要チェック
4) 基本は、配列と同様に利用できる
5) free で、領域開放する
*/
#include <stdio.h>
/*
再帰を利用して 1 ? n までの階和を計算する関数
sum(n) = \sum_{i=0}^n i = 0 + 1 + 2 + .. + n = \frac{n(n+1)}{2}
*/
int sum( int n ) {
printf ( "n = %d\n", n ); /* n の値が変化してゆく */
printf ( "&n = %p\n", &n ); /* 実は、再帰呼び出しが起きるたびに
新しいアドレスに割り当てられる */
/* 同じ名前の変数だが、
関数呼び出しの度に、
異なるメモリに割り当てられるので、
混乱はおきない */
if ( n <= 0 ) {
return 0;
} else {
return sum( n - 1 ) + n;
}
}
int main(int argc, char *argv[]) {
printf ( "sum of 0 .. 10 = %d\n", sum(10) );
return 0;
}
#include <stdio.h>
#include <malloc.h>
/* _cell は 構造体タグ名で、構造体を区別する名前が付けられる */
/* これまでは、typedef でつける名前で、区別していたので、
構造体タグ名は利用しなくてもよかった */
/* 今回は、「自分を参照するデータ型」なので、
自分に名前を付ける必要がでた */
typedef struct _cell{
struct _cell *next; /* 次の要素を指す */
int value; /* 要素の値を保持する */
} Cell;
/*
Cell * Cell
cp +-----+ +-------+
| *----> |次 | next
+-----+ +-------+
|値 | value
+-------+
*/
typedef Cell *List; /* List は Cell 型へのポインタ値を持つ */
/*
List の先頭に要素を追加する
*/
List insert ( List lp, int data ) {
Cell *cp;
cp = calloc ( sizeof(Cell), 1 );
/* Cell を一つ作る */
(*cp).next = lp;
(*cp).value = data;
/*
List -> [ a, b, c ]
^x
==> [ x, a, b, c ]
List -> [a] -> [b] ..
List -> [x] -> [a] ...
新しいリスト List ---+
| |
v v
cp -> * -------> *-----> * ----> * ---> NULL
x a b c
^
(*cp).value = data;
*/
return cp;
}
List one_remove ( List lp ) {
if ( lp != NULL ) { /* リストが空でなかった */
Cell *cp = lp;
lp = (*cp).next; /* cp の指す先が free される前に利用 */
free ( cp );
}
return lp;
}
void all_remove( List aList ) {
while ( aList != NULL ) { /* 要素がある限り削除 */
aList = one_remove ( aList );
}
}
void print_list ( List aList ) {
Cell *cp;
printf ( "[" );
for ( cp = aList; cp != NULL; cp = (*cp).next ) {
printf ( "%d", (*cp).value );
if ( (*cp).next != NULL ) {
printf ( "," );
}
}
printf ( "]\n" );
}
int main(int argc, char *argv[] ) {
List aList = NULL; /* 空のリスト [] */
print_list ( aList );
aList = insert( aList, 1 ); /* 1 だけからなるリスト [1] */
print_list ( aList );
aList = insert( aList, 5 ); /* 1 だけからなるリスト [5,1] */
aList = insert( aList, 7 ); /* 1 だけからなるリスト [7,5,1] */
print_list ( aList );
aList = one_remove ( aList ); /* [5,1] */
print_list ( aList );
all_remove ( aList );
return 0;
}
配列の宣言 配列のサイズを指定して宣言する # 普通の変数は、一つ分のサイズで、型が解れば、メモリに対応させる事ができる サイズをしている事の意味 コンパイラ(実行にプログラムが..)自動的にその領域を管理する プログラマは、利用するサイズをプログラム時に指定するという コストを支払う コンパイラが、領域の管理というサービスをしてくれる じゃあ、そのサービスいらない コストもいらない ?? もし、実行時に自由に配列が作れれと便利では ? <= 領域の管理を、自分で行う必要がでてくる C 言語では、動的(実行時)に、自由に配列のサイズを決められる -> その管理を自分で行う必要がある 領域の確保 alloc ( malloc/calloc ) の利用 領域を参照するためのポインターの保持 (普通の変数や配列ならば、アドレスに対応した名前があるが、 これもサービスの一部で、自分やる場合は提供されないので ポインタ値を保持する変数が必要 ) 領域の開放 free の利用 動的なデータ構造 データとデータの関係(データ構造)が、変化するようなデータ型の事 cf. 配列や、構造体は、データ構造が固定(静的) -> 特に、静的なデータ構造はサイズが固定 <- 動的なデータ構造の場合は、データ間の関係や、サイズを変更できる -> より便利 -> 本質的に alloc/free を利用する必要がある。 具体例として: List を考えてみる List : (同じ型の)要素が順に並んでいるもの 具体例: 「1, 3, 9, 13」は、四つの整数値が並んだもの cf. 配列との違いは ? -> 要素の追加や、削除ができる その位置は、既存の要素のどの前後でもよい -> サイズが可変 ( 配列では困難 ) 実装 : これをどのように実現するか ? # cf. 十分に大きなサイズ配列で対応するも「なくはない」 # しかし、ここでは、動的な対応をする Linked List という考え方 ( List の実装の一つ ) Cell +-------+ |次 | +-------+ |値 | +-------+ List : [ 1, 3, 9, 13 ] List ---+ | +-------+ +-------+ +-------+ +-------+ +---> | *-----> | *-----> | *-----> | *-----> NULL +-------+ +-------+ +-------+ +-------+ | 1 | | 3 | | 9 | | 13 | +-------+ +-------+ +-------+ +-------+ List : [ -7, 1, 3, 9, 13 ] 先頭に、新たに -7 という要素を追加した List ---+ | +-------+ +-------+ +-------+ +-------+ +---+ +-> | *-----> | *-----> | *-----> | *-----> NULL | | +-------+ +-------+ +-------+ +-------+ | | | 1 | | 3 | | 9 | | 13 | | | +-------+ +-------+ +-------+ +-------+ | | | +-------+ | | | +-------+ | +-> | *-------+ +-------+ | -7 | +-------+ 動的なデータ構造 動的なメモリ管理 Cell の新たに作られたり、捨てられたりしている
Download : 20171222-01.c
/*
* 課題 CNAME-01
*
* 2017/12/22 FILENAME
*
* 整数のキュー(queue)
*/
#include <stdio.h>
#include <malloc.h>
/*
* 整数のキュー(queue)
*
* 利用方法
* コンパイル
* cc -o BASENAME.exe FILENAME
* 実行
* ./BASENAME.exe
*/
/*
* Queue は、List の先頭に追加し、最後の要素を削除する事で実現
*/
typedef struct icell {
struct icell *next;
int value;
} ICell;
typedef struct {
ICell *head;
ICell *tail;
} IQueue;
/*
*/
#define NORMAL (0)
#define ERROR (-1)
/*
*/
#define FALSE (0)
#define TRUE (!FALSE)
/*
* alloc_icell
*/
ICell *alloc_icell ( int data ) {
ICell *result = (ICell *)malloc(sizeof(ICell));
if ( result != NULL ) {
result -> next = NULL;
/*
** この部分を完成させなさい
*/
}
return result;
}
/*
* free_icell
*/
void free_icell ( ICell *icp ) {
free ( icp );
}
/*
* alloc_iqueue
*/
IQueue *alloc_iqueue ( ) {
IQueue *result = (IQueue *)malloc(sizeof(IQueue));
if ( result != NULL ) {
result -> head = result -> tail = NULL;
}
return result;
}
/*
* is_empty
*/
int is_empty ( IQueue *iqp ) {
if ( iqp != NULL ) {
return iqp -> head == NULL;
}
return FALSE;
}
/*
* enque
*/
int enque ( IQueue *iqp, int data ) {
int result = ERROR;
if ( iqp != NULL ) {
ICell *icp = alloc_icell ( data );
if ( icp != NULL ) {
if ( is_empty ( iqp ) ) {
iqp -> head = icp;
} else {
/*
** この部分を完成させなさい
*/
}
iqp -> tail = icp;
result = NORMAL;
}
}
return result;
}
int deque ( IQueue *iqp ) {
int result = ERROR;
if ( !is_empty ( iqp ) ) {
ICell *top = iqp -> head;
result = top -> value;
if ( ( iqp -> head = top -> next) == NULL ) {
iqp -> tail = NULL;
}
free ( top );
}
return result;
}
void free_que ( IQueue *iqp ) {
if ( iqp != NULL ) {
ICell *icp = iqp -> head;
ICell *next;
while ( icp != NULL ) {
next = icp -> next;
free_icell ( icp );
icp = next;
}
free ( iqp );
}
}
void print_que ( IQueue *iqp ) {
if ( iqp != NULL ) {
ICell *icp = iqp -> head;
ICell *next;
while ( icp != NULL ) {
next = icp -> next;
printf ( "%d ", icp -> value );
/*
** この部分を完成させなさい
*/
}
}
}
/*
* main
*/
int main ( void ) {
IQueue *iqp = alloc_iqueue();
print_que ( iqp ); putchar ( '\n' );
enque ( iqp, 1 );
print_que ( iqp ); putchar ( '\n' );
enque ( iqp, 2 );
enque ( iqp, 3 );
print_que ( iqp ); putchar ( '\n' );
printf ( "%d\n", deque ( iqp ) );
print_que ( iqp ); putchar ( '\n' );
free_que ( iqp );
return 0;
}
$ ./20171222-01-QQQQ.exe 1 1 2 3 1 2 3 $
Download : 20171222-02.c
/*
* 20171222-02-QQQQ.c
* 二つのファイルを比較して最初に異る場所を表示する
*/
#include <stdio.h>
/*
* main
*/
int main ( int argc, char *argv[] ) {
if ( argc != 3 ) {
printf ( "ファイル名を二つ指定して下さい。\n" );
} else {
FILE *fp1;
if ( ( fp1 = fopen ( argv[1], "r" ) ) == NULL ) {
printf ( "ファイル(%s)を開く事ができませんでした。\n", argv[1] );
} else {
FILE *fp2;
if ( ( fp2 = fopen ( argv[2], "r" ) ) == NULL ) {
printf ( "ファイル(%s)を開く事ができませんでした。\n", argv[2] );
} else {
int position;
int ch1;
int ch2;
for ( position = 0; (ch1 = fgetc (fp1)) != EOF; position++ ) {
ch2 = fgetc( fp2 );
if ( ch1 != ch2 ) {
break;
}
}
if ( ch1 == EOF ) {
ch2 = fgetc( fp2 );
}
if ( ch1 == ch2 ) {
printf ( "二つのファイル(%s,%s)は同じ内容です。\n", argv[1], argv[2] );
} else if ( ch1 == EOF ) {
/*
** この部分を完成させなさい
*/
} else if ( ch2 == EOF ) {
printf ( "ファイル(%s) の方がサイズが大きいです。\n", argv[1] );
} else {
printf ( "%d byte 目で %s は %c, %s は %c という違いがありました。\n", position, argv[1], ch1, argv[2], ch2 );
}
fclose ( fp2 );
}
fclose ( fp1 );
}
}
return 0;
}
$ ./20171222-02-QQQQ.exe data.01 data.02 6 byte 目で data.01 は y, data.02 は Y という違いがありました。 $