/*
* ilist.c
*/
#include <stdio.h>
#include <malloc.h>
#include "ilist.h"
/*
value (数値) -> +-----------+
| / (NULL)|
+-----------+
| value |
+-----------+
*/
ICell *make_icell( int value ) {
ICell *result;
if ( ( result = malloc ( sizeof (ICell) ) ) != NULL ) {
result -> value = value; /* (*result).value = value */
/* *result.value <-> *(result.value) */
result -> next = NULL; /* (*result).next */
}
return result;
}
void print_list ( ICell *list ) {
printf ( "[ " );
while ( list != NULL ) {
printf ( "%d", list -> value ); /* (*list).value */
list = list -> next; /* list = (*list).next */
if ( list != NULL ) { /* 次の要素があれば */
putchar ( ',' ); /* 区切り記号の , が必要 */
}
putchar ( ' ' );
}
printf ( "]" );
}
/*
先頭に要素を追加する
value=0 ilp = [1,2,3]
|
+--> +-------+
| *-----> ..
+---> +-------+
| | 1 |
[0,1,2,3] | +-------+
+-----------+ |
| *-----------+
+-----------+
| 0 |
+-----------+
*/
ICell *insert( ICell *ilp, int value ) {
ICell *icp;
if ( ( icp = make_icell ( value ) ) != NULL ) {
icp -> next = ilp;
return icp;
}
return NULL;
}
/*
先頭の要素の値を返す
*/
int top ( ICell *ilp ) {
if ( ilp != NULL ) {
return ilp -> value;
}
return 0; /* 本当は、エラーなのだが... */
}
/*
先頭の要素を取り除く
*/
ICell *remove_top ( ICell *ilp ) {
if ( ilp != NULL ) {
ICell *icp = ilp; /* ilp != NULL 時のみ有効 */
/*
「{」から「}」でかこまれた部分は、「ブロック」になる
変数宣言は、ブロックの先頭で行うことができる
いままでは、関数の本体の先頭
その変数の有効範囲は、そのブロック内のみ
ブロックの外に出ると、その変数は利用できなくなる
*/
ilp = ilp -> next;
free ( icp ); /* 使い終わったら free */
} /* icp は、ここでは無効 */
return ilp;
}
#include <stdio.h>
/*
普通の変数宣言を利用した場合
*/
int main(int argc, char *argv[]) {
int ivar; /* 変数を利用するには、変数宣言が必要 */
double dvar; /* 変数を実現するためのメモリの確保を
「コンパイラが事前に自動的」に行うために */
ivar = 10; /* 名前で、メモリ操作が可能になる */
dvar = 123.456;
printf ( "ivar=%d, dvar=%f\n", ivar, dvar );
return 0;
}
#include <stdio.h>
/*
メモリを動的に扱う場合
*/
#include <malloc.h> /* 動的なメモリ確保に必要 */
int main(int argc, char *argv[]) {
int *iptr; /* 整数領域へのポインタ(ポインター値を持つ変数) */
/* ポインタを宣言しても、
実際に、整数や浮動小数点数を保存する
領域は、「自動的には作られない」
*/
iptr = malloc ( sizeof (int) );
/* 整数が入る領域を動的に確保する */
/* *(malloc( sizeof(int))) = 10 */
/* 領域が確保されて、10 を代入できるが..
その後、その 10 を取り出す方法がない */
/*
calloc(配列サイズ、配列の要素のサイズ);
配列の領域を確保
malloc は、サイズが 1 の配列を確保
calloc ( A, B ) <-> malloc( A * B )
malloc( A ) <-> calloc( 1, A )
*/
if ( iptr != NULL ) {
/* 動的メモリ確保は、失敗する可能性がある */
/* メモリの確保に失敗した場合は、alloc 関数は NULL を返す */
/* メモリの確保に成功すれば、
「整数型の変数」として、「*ptr」が利用できる
*/
*iptr = 10; /* ポインタ経由で、確保したメモリに情報を記録 */
printf ( "*iptr=%d\n", *iptr ); /* 参照も可能 */
free ( iptr ); /* 動的に確保した領域は、きちんと自分で後始末 */
/*
以下、iptr が保持しているポインター値の先の
領域は、使うことができない(使ってはいけない)
うっかり、 *iptr = 20 してしまう危険性がある
*/
}
return 0;
}
/*
C 言語で、List という動的なデータ構造を実現してみる
集合 A を考え、それに対し「 A の List」を次のように定義する
A の List は、List の要素 a1, a2, .., an を持つ
ここで n は List の長さ
各 ai は A の要素
# 要素は、順番がついていて、しかも、内容は重複してよい
例 : 整数値のリスト
[] : 空リスト ( 長さ 0 で、要素はなにもはいっていない )
[1,2,3] : 長さが 3 で、要素が 1, 2, 3 の三つが,この順に並んでいる
[3,2,1] : 長さが 3 で、要素が 1, 2, 3 の三つが,逆順に並んでいる
cf. { 1,2,3 } = { 3,2,1 }
[ 1,2,3 ] != [ 3,2,1 ]
[1,1,1] : 長さが 3 で、同じ要素 1 が三つ並んでいる
cf. { 1,1,1 } = { 1 }
[ 1,1,1 ] != [ 1 ]
[目的] List を「実装」する
「List の様に振舞うもの」を作る
リストに要素を追加する、削除する、要素を取り出す
[方法は色々ある]
例 : 要素数は 10 以下と決めうち int の配列で OK
しかし、今回は、いくらでも(メモリがある限り)いくらでも入れられる
List にする
[考え方]
要素をもっている必要がある
int の領域
順番をもっている必要がある
次の情報もっている領域
これは、List (の様に振舞うもの) を実現する一つの手法
# 同じ目的のための複数の手法のうち一つを選択する行為を「設計」
[イメージ] 要素を持ったセルがリンクされている
リンクドリスト ( Linked List )
[1,2,3]
|
| +-------+ +-------+ +-------+
+-> | *-----> | *-----> | / |
+-------+ +-------+ +-------+
| 1 | | 2 | | 3 |
+-------+ +-------+ +-------+
ICell
typedef struct icell {
struct icell *next; 次の人
int value; 値がはいる
} ICell;
本来の構造体の使い方
構造体宣言
struct タグ名 { 中身 }
構造体利用(変数宣言)
struct タグ名 変数名
例:
struct point {
int x;
int y;
};
struct point p1;
例:
typedef struct {
int x;
int y;
} Point;
Point p1;
*/
#include <stdio.h>
typedef struct icell {
struct icell *next;
int value;
} ICell;
/*
list = [1,2,3]
|
| +-------+ +-------+ +-------+
+-> | *-----> | *-----> |/(NULL)|
+-------+ +-------+ +-------+
| 1 | | 2 | | 3 |
+-------+ +-------+ +-------+
one two tree
*/
void print_list ( ICell *list ) {
printf ( "[" );
while ( list != NULL ) {
printf ( "%d, ", (*list).value );
list = (*list).next;
}
printf ( "]" );
}
int main(int argc, char *argv[]) {
ICell zero;
ICell one;
ICell two;
ICell three;
ICell *list;
three.value = 3; /* +-------+ */
three.next = NULL; /* | / | */
/* +-> +-------+ */
/* | | 3 | */
/* | +-------+ */
/* | */
two.value = 2; /* | +-------+ */
two.next = &three; /* +------ * | */
/* +-> +-------+ */
/* | | 2 | */
/* | +-------+ */
one.value = 1; /* | +-------+ */
one.next = &two; /* +------ * | */
/* +-> +-------+ */
/* | | 1 | */
/* | +-------+ */
/* | */
list = &one; /* | +-------+ */
one.next = &two; /* +------ * | */
/* +-------+ */
print_list ( list );
printf ( "\n" );
print_list ( &two );
printf ( "\n" );
zero.value = 0;
zero.next = list;
print_list ( &zero );
printf ( "\n" );
return 0;
}
#include <stdio.h>
#include "ilist.h"
int main(int argc, char *argv[] ) {
ICell *ilp = NULL; /* [] 空リスト */
print_list ( ilp ); putchar( '\n' ); /* [ ] */
/*
ilp -> / (NULL) []
*/
ilp = insert ( ilp, 3 );
print_list ( ilp ); putchar( '\n' ); /* [ 3 ] */
/*
0)
ilp -> / (NULL) []
1)
make_icell
+-------+
| *------> / (NULL)
+-------+
| 3 |
+-------+
2)
make_icell
+-------+
| *------> := ilp := / (NULL)
+-------+
| 3 |
+-------+
2)
+-------+
ipl -> | *------> / (NULL) [3]
+-------+
| 3 |
+-------+
*/
ilp = insert ( ilp, 2 ); /* [2,3] */
ilp = insert ( ilp, 1 ); /* [1,2,3] */
print_list ( ilp ); putchar( '\n' ); /* [ 1,2,3 ] */
ilp = insert ( ilp, 0 ); /* [0,1,2,3] */
print_list ( ilp ); putchar( '\n' ); /* [ 0,1,2,3 ] */
printf ( "top = %d\n", top ( ilp ) ); /* -> 0 */
ilp = remove_top ( ilp ); /* -> [1,2,3] */
print_list ( ilp ); putchar( '\n' ); /* [ 0,1,2,3 ] */
ilp = remove_top ( ilp ); /* -> [2,3] */
ilp = remove_top ( ilp ); /* -> [3] */
ilp = remove_top ( ilp ); /* -> [] */
print_list ( ilp ); putchar( '\n' ); /* [] */
return 0;
}
Download : 20161209-01.c ( utf8 版 )
/*
* 課題 CNAME-01
*
* 2016/12/09 FILENAME
*
* 整数のキュー(queue)
*/
#include <stdio.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;
result -> value = data;
}
return result;
}
/*
* free_icell
*/
int free_icell ( ICell *icp ) {
int result = ERROR;
if ( icp != NULL ) {
resule = free ( icp );
}
return result;
}
/*
* alloc_iqueue
*/
IQueue *alloc_iqueue ( ) {
IQueue *result = (IQueue *)malloc(sizeof(IQueue));
if ( result != NULL ) {
result -> head = result -> tale = 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 -> top = icp;
} else {
iqp -> tail -> next = icp
}
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 );
}
}
/*
* main
*/
int main ( void ) {
IQueue *iqp = alloc_queue();
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", dequle ( iqp ) );
print_que ( iqp ); putchar ( '\n' );
free_que ( iqp );
return 0;
}
$ ./20161209-01-QQQQ.exe $
Download : 20161209-02.c ( utf8 版 )
/*
* 20161209-02-QQQQ.c
* 「Hello, 自分の名前」と出力するプログラム
*/
#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;
}
$ ./20161209-02-QQQQ.exe data.01 data.02 6 byte 目で data.01 は y, data.02 は Y という違いがありました。 $