2005-02-27 φ(-_-)

■ [lang]プログラミング言語 C

クイックソートプログラムを次の本を参考に実際に動かしてみた。

「基礎Ｃ言語」(isbn:4000078569) p192-197


初めに q_sort.c ファイルにちょっとコードを追加、

 1. /* quick_sort.c */
 2. #include <stdio.h>

 3. void q_sort();
 4. void swap();

 5. void quick_sort(int a[], int n)
 6. {
 7. 	q_sort(a, 0, n); /* left の値に前もって 0 を入れておく */
 8. }

 9. void q_sort(int v[], int left, int right)
10. {
11. 	int i;
12. 	int last;

13. 	if (left >= right)
14. 		return;

15. 	swap(v, left, (left + right)/2);
16. 	last = left;

17. 	for (i = left + 1; i <= right; i++)
18. 		if (v[i] < v[left])
19. 			swap(v, ++last, i);

20. 	swap (v, left, last);

21. 	q_sort(v, left, last - 1);
22. 	q_sort(v, last + 1, right);
23. }

24. void swap(int v[], int i, int j)
25. {
26. 	int tmp;

27. 	tmp = v[i];
28. 	v[i] = v[j];
29. 	v[j] = tmp;
30. }

次は読み込み用の read_array.c ファイル、

 1. /* read_array.c */
 2. #include <stdio.h>

 3. int read_array(int a[], int limit)
 4. {
 5. 	int n = 0;

 6. 	printf("Input whole numbers upto %d.\n", limit);
 7. 	printf("standard input:[enter][ctrl+d]\n");
 8. 	/*上の 2行は説明文のため、コメントアウトしても OK */

 9. 	while (n < limit && scanf("%d", &a[n]) != EOF)
10. 		++n;

11. 	return --n; /* 初期値分を 1つ減らしておく */
12. }

ソートの結果を出力する print_array.c ファイル、

 1. /* print_array.c */
 2. #include <stdio.h>

 3. void print_array(int a[], int n)
 4. {
 5. 	int i;

 6. 	for (i = 0; i <= n; i++) {
 7. 		printf("%3d ", a[i]);
 8. 		if ((i + 1) % 10 == 0) { /* データは 1行に 10個ずつ出力 */
 9. 			putchar('\n');
10. 		}
11. 	}

12. 	if (i % 10 != 0) /* この i は全データ数 */
13.		putchar('\n');
14. }

関数 main() ファイル、これは簡単に、

 1. /* q_main.c */
 2. #include <stdio.h>
 3. #include "q_header.h"
 4. /* クイックソートプログラム */

 5. main()
 6. {
 7. 	int a[MAX];
 8. 	int n; /* 全データ数 */

 9. 	n = read_array(a, MAX);
10. 	quick_sort(a, n);
11. 	print_array(a, n);

12. 	return 0;
13. }

最後にヘッダファイルを作成、

 1. /* q_header.h */
 2. #define MAX 100
 3. int read_array();
 4. int print_array();
 5. void quick_sort();

コンパイルしてみます。まずオブジェクトファイルの作成。

cc -c q_main.c quick_sort.c read_array.c print_array.c

コンパイルエラーがあればここで訂正して、実行ファイルを作成。

cc -o q_sort q_main.o quick_sort.o read_array.o print_array.o


元になる数字のリストですが、その前に、以前つくった random.c ファイルを少しいじ
っておく。

 1. /* random.c */
 2. #include <stdio.h>
 3. #include <stdlib.h>

 4. /* ランダムな数値のファイルを用意する */

 5. #define MAX 88

 6. struct List {
 7. 	int data;
 8. 	struct List *next;
 9. };

10. main()
11. {
12. 	FILE *fp;

13. 	int i;
14. 	int seed;
15. 	char buf[64];
16. 	struct List *prev, *curr;
17. 	prev = NULL;

18. 	printf("Input seed = ");
19. 	for ( ; scanf("%d", &seed) != 1 ; ) {
20. 		printf("It's not finger. Input seed = ");
21. 		scanf("%s", buf);
22. 	}
23. 	srand(seed);
24. 	printf("OK, make 'random.txt' now.\n");

25. 	fp = fopen("random.txt", "w");

26. 	if (fp != NULL) {
27. 		for (i = 0; i < MAX; i++) {
28. 			curr = (struct List *)malloc(sizeof(struct List));
29. 			fprintf(fp, "%d ", curr->data = rand() % 1000);
30. 			curr->next = NULL;
31. 			if (prev != NULL) {
32. 				prev->next = curr;
33. 			}
34. 			prev = curr;
35. 		}
36. 		fprintf(fp, "\n");
37. 		fclose(fp);
38. 	}
39. 	return 0;
40. }

コンパイル後、$./random として適当な数値を入力すると random.txt が作成される。

$./q_sort < random.txt > sort.txt; cat sort.txt として確認。


2005-03-12 φ(-_-)

■ [lang]プログラミング言語 C

    ポインタは他の変数のアドレスを内容とする変数であり、C では頻繁に使用される
    。その一つの理由は、それが時に計算を表現する唯一の方法である場合であり、も
    う一つの理由は、他の方法で得られるより通常、もっとコンパクトで効率のよいプ
    ログラムが書けるからである。
   
    ポインタは、理解できないようなプログラムをつくってしまう要因として、goto 文
    と並び称されてきた。不用意に使うと、確かにこれは事実であって、(まちがって)
    予想もしない場所を指し示すポインタをつくるのは簡単である。
   
    しかし十分に注意すれば、ポインタを用いて明快でシンプルなプログラムをつくる
    ことができる。
   
    ポインタの宣言、
    int *p;
    は、表記法として設けられたもので *p という表現が int であることを表す (ポイ
    ンタが指す先の値 - オブジェクト - が int 型である、という意味)。
   
    このことは関数の宣言でもあてはまる。例えば、
    double *p, atof(char *);
    では、*p と atof() とは double の型をもっており、atof() の引数が char 型
    (のオブジェクト) へのポインタであることを表現している。
   
    単項演算子 & はオブジェクトのアドレスを与えるから、
    p = &c;
    では、変数 p に c のアドレスが代入される。このとき p は c を "指し示す" と
    いう。& 演算子はメモリ中のオブジェクト、すなわち変数および配列要素にのみ適
    用できる。& 演算子を式や定数、レジスタ変数に適用することはできない。
   
    次に、単項演算子 * は、間接演算子すなわち逆参照演算子である。これをポインタ
    に適用すると、そのポインタが指すオブジェクトがアクセスできる。
   
    int x;
    p = &x;
    p は x を指す -> p に x のアドレスが代入される。
   
    *p = 1
    p の指すオブジェクトに '1' が代入される。
   
    y = *p
    p の指すオブジェクトが y に代入される。
   
    p が (int 型で) 整数 x を指すとすると、*p は x が使われるコンテクストではど
    こでも使うことができる。
   
    *p = *p + 10
    では、*p (p の指すオブジェクト) を 10 増やしている。
   
    単項演算子 & と * は、算術演算子よりも束縛力が強い。そのため、
    y = *p + 1;
    では、p の指すオブジェクトが何であれ、それが取り出され '1' が加えられて、そ
    の結果が y に代入される。
   
    (*p)++;
    も同様である。ただし、この場合にはカッコが必要となる。(なぜなら) * や ++ の
    ような単項演算子では、右から左へと計算されるため、カッコがないと p の指すオ
    ブジェクトではなく、p そのものをインクリメントしてしまう。
   
   
    最後に、ポインタは変数であるので逆参照なしに (* 演算子を用いずに) 使うこと
    ができる。例えば、
    int *p, int *q;
    int x = 1;
    p = &x;
    q = p;
    とすると、 p そのものが q へ代入され (結果として) q は p の指すオブジェクト
    を指すこととなる (この場合は '1')。(p113-116)
   

2005-03-14 φ(-_-)

■ [lang]プログラミング言語 C

C では関数に対して引数を値で渡すから、呼ばれた関数のほうで呼び出した関数内の変
数を直接変更することはできない。

(このとき) ポインタ変数を使えば、関数の中でそれを呼んだ関数中のオブジェクトにア
クセスして (間接的に) 変更することが可能となる。

 1. /* swap_2.c */
 2. #include <stdio.h>
 3. void swap(int *x, int *y);

 4. main()
 5. {
 6.	 int a = 3, b = 5;

 7.	 printf("a = %d, b = %d\n", a, b);
 8.	 swap(&a, &b);
 9.	 printf("swap a = %d, b = %d\n, a, b);

10.	 return 0;
11. }

12. void swap(int *px, int *py)
13. {
14.	 int tmp;

15.	 tmp = *px;
16.	 *px = *py;
17.	 *py = tmp;
18. }

演算子 & は変数のアドレスを与えるから、&a は a へのポインタである。

関数 swap() 内では引数はポインタとして宣言されており、実際の被演算数はポインタ
を通して間接的にアクセスされる。(P116-117)


2005-03-27 φ(-_-)

■ [lang]プログラミング言語 C

自由形式*1 入力変換を実行する関数 getint を作成せよ。

 1. /* getint.c */
 2. #include <stdio.h>
 3. #include <ctype.h> /* 関数 isspace, isdigit に必要 */

 4. #define MAX 100

 5. char buf[MAX];
 6. int buf_pt = 0;

 7. int get_int(int *);
 8. int get_ch(void);
 9. void unget_ch(int);

10. main()
11. {
12. 	int n, m = 0;
13. 	int num[MAX];

14. 	for (n = 0; n < MAX && get_int(&num[n]) != EOF; n++)
15. 		;

17. 	while (m < n ) {
18. 		printf("%5d\n", num[m]);
19. 		m++;
20. 	}
21. 	return 0;
22. }

23. int get_int(int *pn)
24. {
25. 	int c, sign; /* sign は正負記号 */

26. 	while (isspace(c = get_ch()))
27. 		;
28. /* 関数 isspace は c が space のとき真を返す */
29. /* スペース (改行も) をスキップ */

30. 	if (!isdigit(c) & c != EOF &&& c != '+' && c != '-') {
31. 		unget_ch(c);
32. 		return 0;
	}
33. 	/* 関数 isdigit は c が '0'-'9' のとき真を返す */
34. 	/* 入力が数字でないとき (!) 0 を返して終了 */

35. 	sign = (c == '-') ? -1 : 1; /* 負の記号を記憶 */

36. 	if (c == '+' || c == '-')
37. 		c = get_ch();

38. 	for (*pn = 0; isdigit(c); c = get_ch())
39. 		*pn = 10 * *pn + (c - '0');

44. 	*pn *= sign; /* *pn の正負を確定 */

45. 	if (c != EOF)
46. 		unget_ch(c);
47. 	return c;
48. 	/* ファイル終了時には EOF を、整数の入力時には正の値を返す */
49. }

50. int get_ch(void)
51. {
52. 	return (buf_pt > 0) ? buf[--buf_pt] : getchar();
53. }

54. void unget_ch(int c)
55. {
56. 	if (buf_pt >= MAX)
57. 		printf("caution : buffer oversized\n");
58. 	else
59. 		buf[buf_pt++] = c;
60. }

$./getint < random.txt

として実行してみると、最後に別のデータ?がくっついてくる . . . (数以外の文字列も
うまく扱えないし)

あとで直してもいっか。

(追記) 訂正しました (05/10/19)

*1：スペースや改行でデータが区切られたファイル


2005-03-28 φ(-_-)

■ [lang]プログラミング言語 C

配列とポインタには注意すべき違いが一つある。

ポインタは変数であり、したがって pa = a や pa++ は意味のある演算となる。しかし
配列は変数ではない。

配列が関数に渡されるとき、(実際に) 渡されるのは配列の先頭アドレスである。呼び出
された関数内では、この引数は局所的な変数として扱われる。

文字列の長さを求める関数 strlen を (ポインタ変数を使って) 書き換えてみる。

 1. /* strlen : 文字列 s の長さを返す */
 2. int strlen(char *s)
 3. {
 4. 	int n;

 5. 	for (n = 0; *s != '\0'; s++)
 6. 		n++;

 7. 	return n;
 8. }

s のインクリメントは、それがポインタ変数なので演算可能である。s++ は strlen を
呼び出した関数内の文字列には影響しない。

strlen の仮引数は char[] と書くより

char *s

のほうがよいと思うが、それはこのほうが引数がポインタであることを明示的に表して
いるからである。

配列の一部をその先頭のポインタを使って渡すことができる。array が配列だとして、

func(array + 2)

では、関数 func に array[2] の要素から始まる配列のアドレスが渡される。

なお、この関数の宣言は、

func(int *a) { ....}

となる。

要素の存在が確実なら、配列を逆方向にインデックスすることも可能である。

つまり a[-1], a[-2] は構文として正しく、a[0] の直前の要素を参照している。

当然だが、配列の限界内に存在しないオブジェクトは参照してはいけない。(p121-122)


以前でてきた関数 get_line をポインタ変数を使って書いてみる。

 1. /* get_line */
 2. int get_line(char *s, int lim)
 3. {
 4. 	int i;

 5. 	for (i = 0; i < lim - 1 && (*s = getchar()) != EOF && *s != '\n'; ++s)
 6. 		++i;

 7. 	if (*s == '\n')
 8. 		++i;

 9. 	*s = '\0';

10. 	return i;
11. }

(これでいい . . . のかな ?)


2005-04-01 φ(-_-)

■ [lang]プログラミング言語 C

p が配列のどれかの要素へのポインタだとすると、p++ では p はインクリメントされ次
の要素を指す。また p += 1 は (同じく) 現在 p が指しているところから 1要素分先を
指す。

このような構文はアドレス計算の最も単純なスタイルである。

ポインタはある状況のもとでは (互いに) 比較することができる。

つまり p, q が同じ配列内の要素を指していれば ==, !=, <, >= などの関係演算子は正
常に使える。例えば p が q より初めのほうの配列要素を指していれば

p < q

は真である。任意のポインタあるいはゼロと比較して一致または不一致をみることは意
味をもっている。

しかし、同じ配列内を指していないポインタ間の演算や比較を行えば (当然) その結果
は不定になる。

構文

p + n

は p が現在指しているところから n番目先のオブジェクトであることを意味する。これ
は p が指し示しているオブジェクトの型にかかわらず真である。 (なぜなら) n は p
が指しているオブジェクトの大きさに応じてスケールされるからである。

この大きさは p の宣言によって決まってくる。例えば、もし (p が) int型で 4バイト
だとすれば int は 4 でスケールされる (<- n x 4)。

すべてのポインタ操作で、指しているオブジェクトの大きさは (このように) 自動的に
計算されている。

正しいポインタ操作は、

1. 同じ型のポインタの代入

2. ポインタと整数との加算と減算

3. 同じ配列のメンバーに対する 2つのポインタの引算と比較

4. ゼロの代入やゼロとの比較

に限られている。その他のポインタ演算はすべて不正となる。(p122-126)