WHAT'S NEW
CONTENTS
- 2015/02/01 C言語の基礎知識 (1)
こんにちはC言語、数と四則演算、局所変数と外部変数、文字と文字列、if 文、比較演算子と論理演算子、三項演算子、while 文による繰り返し、インクリメント演算子とデクリメント演算子、FizzBuzz 問題、数値積分
- 2015/02/01 C言語の基礎知識 (2)
配列、配列の指示初期化子、for 文、繰り返しの制御、パスカルの三角形、文字列は文字型の配列、素数を求める、エラトステネスの篩、素因数分解、switch 文
- 2015/02/07 関数
関数の基礎知識、関数の定義方法、局所変数と外部変数、局所変数の定義と有効範囲、素数を求める (2)、めのこ平方、再帰定義、再帰定義のポイント、ユークリッドの互除法、相互再帰と関数プロトタイプ、再帰定義と繰り返し、めのこ平方の改良、順列の生成
2015/07/25 Appendix: 末尾最適化
- 2015/02/08 Yet Another Clang Problems
九九表、整数の和、累乗、フィボナッチ関数、整数の n 進数表示、組み合わせの数、順列の生成、重複順列の生成、組み合わせの生成、重複組み合わせの生成
- 2015/02/11 ポインタ
メモリの構成、ポインタの基本、ポインタの利点と欠点、配列とポインタ、値呼びと参照呼び、関数にポインタを渡す、配列と関数、多段階のポインタ、ポインタ配列、関数へのポインタ、qsort と bsearch
- 2015/02/14 Yet Another Clang Problems (2)
度数分布表と累積度数表、平均値と標準偏差、最大値と最小値、配列の線形探索、文字列の長さ、コピー、連結、文字の探索、文字列の比較、文字列の探索、二分探索、バブルソート、選択ソート、挿入ソート
- 2015/02/15 ソート
ソートの安定性、テストデータの作成、乱数、配列のシャッフル、実行時間の計測、遅いソート (バブルソート、挿入ソート、単純挿入ソート) の実行結果、シェルソート、コムソート、クイックソート、クイックソートの改良、median-of-9、ライブラリ関数 qsort の実行結果
- 2015/02/21 C言語のメモリアロケーション
スタックとは?、関数呼び出しとスタックの関係、局所変数とスタックの関係、スタック領域について、動的メモリ割り当て、関数 malloc、関数 realloc、関数 free、簡単な使用例
- 2015/02/22 構造体
構造体の定義、構造体の使い方、構造体とポインタ、構造体と配列、構造体と関数、共用体、無名の構造体/共用体、可変長ベクタ、データ型の定義、ベクタの生成と廃棄、要素の参照、要素の更新、実行例
- 2015/02/28 ファイル入出力
標準入出力、行単位の入出力、ファイルのアクセス方法、改行文字の取り扱い、コマンドライン引数の取得、fread と fwrite、エンディアンとは?、書式付き出力関数、書式付き入力関数、scanf の使い方、入出力関数のエラーチェック、ファイルを行単位で連結する
- 2015/02/28 Yet Another Clang Problems (3)
ファイルのコピー、文字数と行数のカウント、文字列の探索、文字の置換、文字列の置換、単語のカウント、タブを空白文字に展開、空白文字をタブに置換、ランレングス符号化、ランレングス復号
- 2015/03/01 連結リスト
連結リストとは?、データ型の定義、連結リストの生成と廃棄、n 番目のセルを求める、データの参照、データの挿入、データの削除、実行例、分割コンパイル、ヘッダファイルの定義、static 宣言、実行ファイルの作成
- 2015/03/01 二分探索木
木構造、二分木、節の定義、データの探索、データの挿入、データの削除、最小値の探索と削除、データ削除のプログラム、巡回 (traverse)、構造体 Tree と操作関数の定義、簡単なテスト、簡単なテスト (2)
- 2015/03/07 キュー
キューとは?、リングバッファによるキューの実装、キューの定義、キューの生成、データの挿入、データの取り出し、実行例、連結リストによるキューの実装、キューの定義と生成、キューの廃棄、データの挿入 (2)、データの取り出し (2)、実行例 (2)
- 2015/03/07 ヒープ
ヒープとは?、ヒープの構築 (1)、ヒープの再構築、ヒープの構築 (2)、優先度付き待ち行列、Heap の生成と廃棄、データの挿入、データの取り出し、実行例
- 2015/03/07 ソート (2)
ヒープソート、実行結果 (1)、マージとは?、マージソートの原理、マージソートのプログラム、実行結果 (2)、マージソートの改良、実行結果 (3)、連結リストのソート、クイックソート、プログラムの作成、実行結果 (4)、リストのマージ、マージソート、実行結果 (5)
- 2015/03/08 経路の探索
グラフ、隣接行列と隣接リスト、バックトラックによる探索、幅優先探索、経路の管理、構造体 Path と操作関数、キューの作成、幅優先探索のプログラム、反復深化、反復深化のプログラム
- 2015/03/08 Yet Another Clang Problems (4)
ハノイの塔、小町算、大町算、覆面算、魔方陣、8 クイーン、騎士の巡歴
- 2015/03/14 整数の論理演算とビット操作
ビット演算子、組み合わせの生成、組み合わせに番号を付ける方法、組み合わせを番号に変換、番号を組み合わせに変換、ちょっと便利なビット操作、ビットが 1 の個数を求める
- 2015/03/14 N Queens Problem
単純な解法の問題点、無駄を省く、実行結果 (1)、プログラムの改良、実行結果 (2)、ビット演算による高速化、実行結果 (3)
- 2015/03/15 Yet Another Clang Problems (5)
水差しの問題、ペグ・ソリテア、マスターマインドの解法
- 2015/03/15 ハッシュ法
ハッシュ法の仕組み、チェイン法、ハッシュ表と操作関数、セルの生成と廃棄、ハッシュ表の生成と廃棄、ハッシュ関数の作成、データの探索、データの挿入、データの削除、実行例1、実行例2、実行例3
- 2015/03/21 ハッシュ法 (2)
オープンアドレス法、データの挿入と探索、データの削除、オープンアドレス法の問題点、データ型の定義、ハッシュ法の生成、キーの探索、データの探索、データの挿入、データの削除、実行例1、実行例2、二重ハッシュ法、実行結果
- 2015/03/21 スライドパズル
パズルの説明 (8 パズル)、データ構造の定義、キューの定義、同一局面のチェック、幅優先探索による解法、実行結果、双方向探索、最長手数の求め方、プログラムの作成、実行結果 (2)
- 2015/03/22 スライドパズル (2)
反復深化による解法、実行結果、下限値枝刈り法、下限値枝刈り法のプログラム、手数の偶奇性、11 パズルの解法
- 2015/03/22 数独の解法
数独とは?、盤面の定義、縦横枠のチェック、単純なバックトラックによる解法、実行結果 (1)、データ構造を工夫する、盤面とフラグの定義、フラグの操作、バックトラックによる解法、実行結果 (2)、確定サーチ、置ける数字がひとつしかないマスを探す、縦横枠で置くことができる数字を探す、実行結果 (3)
- 2015/03/28 Yet Another Clang Problems (6)
順列に番号を付ける、番号から順列を復元する、完全順列、モンモール数、カッコ列、カタラン数、整数の分割、分割数、ラテン方陣、数独 (6 行 6 列盤) の解の総数
- 2015/03/28 C言語のいろいろな機能
引数つきマクロ、可変個引数、goto 文、static 変数、extern 宣言、大域脱出、シグナル、文字列を数値に変換、atexit、可変長配列
- 2015/03/29 電卓プログラムの作成 (前編)
プログラミング言語処理系の基本的な構造、文法の表現、式の構文、字句解析、構文解析、式の入力と評価、実行例、単項演算子の追加、実行例 (2)
- 2015/04/04 電卓プログラムの作成 (後編)
変数、関数、データ型の定義、外部変数とトークンの追加、シンボルの操作関数、組み込み関数の初期化、字句解析の修正、構文解析の修正、代入文の処理、実行例、おわりに
- 2021/11/13 複素数
C言語の数、無限大、負のゼロ、非数、C言語の複素数、複素数の四則演算、複素数の指数関数と対数関数、複素数の三角関数、複素数の双曲線関数、複素数の平方根、逆三角関数、複素数の逆三角関数、逆双曲線関数、複素数の逆双曲線関数
●番外編
- 2015/04/11 ガベージコレクション
ガベージコレクションの基礎知識、リファレンスカウント法、マークスイープ法、Boehm GC の使い方、連結リストによる順列の生成
- 2015/04/11 続・電卓プログラムの作成
構文木の定義、構文解析の修正、式の評価、式の入力と評価の修正、実行例
- 2015/04/18 続・電卓プログラムの作成 (2)
変数 (代入演算子)、関数、データ型の定義、字句解析の修正、構文解析の修正、式の評価の修正、実行例
- 2015/04/25 続・電卓プログラムの作成 (3)
関数定義の文法、字句解析の修正、構文解析の修正、引数の処理、連想リスト、局所変数 (環境) の操作、変数の評価、ユーザ関数の評価、関数定義、実行例
- 2015/05/02 続・電卓プログラムの作成 (4)
論理演算子と比較演算子、優先順位、条件分岐、文法の修正、字句解析の修正、構文解析の修正、否定と条件分岐の処理、式の評価、再帰呼び出しの対応、実行例
- 2015/05/09 続・電卓プログラムの作成 (5)
begin 式と while 式、構文解析の修正、eval の修正、実行例
はじめに
『お気楽C言語プログラミング超入門』は M.Hiroi が Linux でC言語を再学習するために作成したページです。入門講座の体裁をとってはいますが、かけ足で進めていくつもりなので、すこし勾配の急な再入門的な内容になる予定です。プログラミング経験がない方にはちょっと難しいかもしれません。M.Hiroi のサビついた腕をどこまでブラッシュアップできるかわかりませんが、興味のある方はお付き合いくださいませ。
●C言語の特徴
C言語は 1972 年 AT&T ベル研究所の D.M.リッチー氏によって UNIX という OS を開発するために作られたプログラミング言語です。OS というシステムソフトウェアを開発するために設計されているので、アセンブラのような低水準に近い操作が可能になっています。このため、C言語は汎用アセンブラとか高級アセンブラといわれることもあります。
ほかの高水準言語とは違い、C言語は配列の範囲やオーバーフローなどのチェックは行っていません。また、「ポインタ」の使い方を誤れば、プログラムは簡単に暴走してしまいます。それでも、コンパクトで高速なマシン語が出力されることと、拡張性や保守性の点ではアセンブラよりも断然優れていることから、C言語は広く普及するようになりました。たいていの環境でC言語を利用することができます。
プログラミング言語はプログラムを実行する方法によって、コンパイラとインタプリタという 2 つの方法に分けることができます。一般に、C言語はコンパイラ型のプログラミング言語に分類されますが、インタプリタ型のC言語もあります。以前、ROOT: analyzing petabytes of data, scientifically. では、後藤正治さんが開発された C/C++ インタープリタ CINT が使われていましたが、現在では Cling という C++ インタプリタに置き換えられたようです。
Unix 系 OS の場合、標準のCコンパイラに cc がありますが、ほとんどのディストリビューションで GCC (GNU Compiler Collection) が同梱されています。Linux のように、コマンド cc が gcc になっている OS もあります。最近は Clang というコンパイラも使われるようになってきました。Clang - Wikipedia によると、Clang は 『GNUコンパイラコレクション (GCC) を置き換えることのできるコンパイラを提供すること』 を目標にしていて、GCC よりもコンパイルが速く、エラーやワーニングのメッセージがわかりやすいといわれています。
M.Hiroi は Clang に興味があるので、本稿ではCコンパイラに Clang を使ってC言語の学習を進めることにします。Debian 系の OS であれば、次のコマンドで Clang をインストールすることができます。
sudo apt intstall clang
$ clang --version
clang version 6.0.0-1ubuntu2 (tags/RELEASE_600/final)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin
コマンドは gcc のかわりに clang を使います。なお、Clang は Cygwin でも利用することができます。setup-x86_64.exe で簡単にインストールすることができるので、Cygwin ユーザーで興味のある方は試してみてください。
●実行ファイルができるまで
C言語でプログラムを作る場合、エディタを使ってソースファイルを作成します。ソースファイルとは、プログラミング言語で記述された命令書のことです。この命令書をコンピュータが理解できるようにマシン語に変換する必要があります。
コンパイラは、ソースファイルを実行ファイルに変換します。一度変換してしまえば、あとは外部コマンドと同様にそのプログラムを実行することができます。それでは、標準的なC言語を例に実行ファイルができるまでの様子を見てみましょう。
いきなりソースファイルを実行ファイルに変換することはできません。まず、ソースファイルをアセンブラプログラムに変換します。この作業をコンパイルといいます。そして、この作業を行うプログラムをコンパイラといいます。C言語で書かれたプログラムは、Cコンパイラによって変換されます。ほかのプログラミング言語のコンパイラを使うことはできません。
Unix 系 OS で標準的なCコンパイラを使用する場合、ここの処理は cpp と cc1 が担当します。C言語のソースファイルは、拡張子に .c が使われます。ソースファイル abc.c はコンパイラによって abc.s というアセンブラプログラムに変換されます。Unix 系 OS の場合、アセンブルプログラムの拡張子は .s が使用されます。このとき、ソースファイルのほかにも「ヘッダファイル」という複数のファイル ( *.h ) が必要になります。
次に、アセンブラプログラムをオブジェクトファイルに変換します。この作業をアセンブルといい、それを実行するプログラムをアセンブラといいます。Unix 系 OS では as が担当します。
オブジェクトファイルの内容はマシン語なのですが、このままでは実行することができません。オブジェクトファイルを実行ファイルに変換する作業がリンクです。そして、この作業を行うプログラムがリンカと呼ばれます。Unix 系 OS では ld が担当します。オブジェクトファイルの拡張子は .o です。リンク作業は、「ライブラリ」という複数のオブジェクトをまとめたファイルの中から、必要なオブジェクトを取り出し [*1]、abc.o と一緒に結合して abc という実行ファイルを作ります。
このように、実行ファイルに変換するまで、複数のプログラムを使います。いちいち手作業でこれらのプログラムを実行するのでは疲れてしまいますね。そこで、必要なプログラムを順番に呼び出してくれる「コンパイラ・ドライバ」というプログラムが用意されています。これが cc です。GCC であればコマンド gcc を使い、Clang であれば clang を使います。
$ clang -o abc abc.c
上記のように入力するだけで、abc.c は abc という実行ファイルに変換されます。この様子を見ただけでは、アセンブラやリンカが働いていることはわかりません。clang がソースファイルを実行ファイルに変換するように見えますが、今まで説明したように、複数のプログラムが働いているのです。なお、「コンパイルする」というと、一般には、ソースファイルから実行ファイルに変換する作業すべてを指す場合が多いようです。
それでは実際にコンパイルしてみましょう。次のプログラムは画面に hello, world と表示します。
リスト : hello.c
#include <stdio.h>
int main(void)
{
printf("hello, world\n");
return 0;
}
$ clang -o hello hello.c
$ ls
hello hello.c
$ ./hello
hello, world
-o は実行ファイル名を指定するオプションです。-o を省略すると実行ファイル名は a.out になります。
-- note --------
[*1] これは静的ライブラリ (拡張子が .a のファイル) をリンクする場合の話です。Linux では共有ライブラリ (拡張子が .so のファイル) をプログラムの実行時にロードする方法が標準です。
●たらいまわし関数
それでは、お馴染みの「たらいまわし関数」を使って、gcc と clang の実行時間を計測してみましょう。C言語の場合、たらいまわし関数は次のようになります。
リスト : たらいまわし関数
#include <stdio.h>
int tak(int x, int y, int z)
{
if (x <= y) {
return z;
} else {
return tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y));
}
}
int main(void)
{
printf("%d\n", tak(24, 12, 0));
return 0;
}
時間計測はコマンド time を使います。time で時間を計測する場合、プログラムの起動時間も含まれることに注意してください。実行結果は次のようになりました。
$ gcc -O2 -o takg tak.c
$ clang -O2 -o takc tak.c
$ time ./takg
1
real 0m7.639s
user 0m7.641s
sys 0m0.000s
$ time ./takc
1
real 0m7.443s
user 0m7.438s
sys 0m0.000s
- 実行環境 : Ubunts 18.04 (Windows Subsystem for Linux), Intel Core i5-6200U 2.30GHz
最適化のオプションはどちらも -O2 を指定しました。Clang のほうがちょっと少しだけ速いみたいです。興味のある方はいろいろ試してみてください。
参考文献・URL
- B.W.カーニハン, D.M.リッチー (共著), 石田晴久 (訳), 『プログラミング言語C』, 共立出版, 1981
- 平林雅英 (著), 『ANSI C言語辞典』, 技術評論社, 1989
- 奥村晴彦,『C言語による最新アルゴリズム事典』, 技術評論社, 1991
- Patrick Henry Winston (著), 大鋳史男, 鬼頭繁治 (訳), 『ウィンストンのC』, アジソンウェスレイ, 1995
- P.J.プラウガー (著), 福富寛, 門倉明彦, 清水恵介 (訳), 『標準Cライブラリ』, トッパン, 1995
- Ravi Sethi (著), 神林靖 (訳), 『プログラミング言語の概念と構造』, アジソンウェスレイ, 1995
- 近藤嘉雪, 『Cプログラマのためのアルゴリズムとデータ構造』, ソフトバンク, 1998
- C言語 - Wikipedia
- 連載:C言語の最新事情を知る, (花井志生さん, Build Insider)
権利・免責事項など
『お気楽C言語プログラミング超入門』の著作権は筆者「広井誠 (Makoto Hiroi) 」が保持します。無断使用や無断転載は禁止いたします。『お気楽C言語プログラミング超入門』で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は出典を明記してくださるようお願いいたします。
ただし、ドキュメントの内容とプログラムは無保証であり、利用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi) 」 は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。
Copyright (C) 2015-2022 Makoto Hiroi
All rights reserved.