アルゴリズムとデータ構造ＩWebテキスト
Ａｐｒ2008
担当coskx
この文書はC言語文法をマスターした後にアルゴリズムとデータ構造を学ぶためののＷｅｂテキストである。
アルゴリズムとは，コンピュータに作業をさせる手順のことである。アルゴリズムを特定のプログラミング言語で記述したものがプログラムである。
データ格納容器を考える。データは2つ以上あり，格納したり取り出したりするができる。データを格納する順番と，取り出す順番には関係があり，取り
出そうとすると一番最後に格納したものが取り出される。たとえば，Ａ，Ｂ，Ｃ，Ｄの順で格納すると，取り出す時にはＤ，Ｃ，Ｂ，Ａの順で取り出される。こ
のようなデータ格納容器を「スタック」と呼ぶ。
→小坂説明 Ｃプログラミング入門 「Ｆ．補足 マルチソースファイル・ポインタ補足・動的二次配列・リスト構造」中の「キューとスタック」
スタックは変数の配列とスタックポインタと呼ばれる変数によって形成される。
int型データを格納するにはint型配列，double型データを格納するにはdouble型配列を用いる。
構造体でデータを格納するのなら構造体の配列が用いられる。
スタックポインタはポインタ変数である必要はなく，配列の要素番号を指すことにすると通常のint型変数でよい。
初期状態ではポインタは配列の先頭を指すようにする。ポインタは常にデータを次に格納する場所を指すように動作する。
データを格納することをpush，データを取り出すことをpopと呼ぶ。図２．１と図２．２にpushの時とpopの時の配列状態とスタックポインタの位置を示す。
|
初期状態 |
→
push 123 |
123がpushされた状態 |
→
push 456 |
|
|
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 456 |
| 123 | |
| 456がpushされた状態 |
→
push 789 |
|
|
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 789 |
| 456 |
| 123 | |
| 789がpushされた状態 |
図２．１ スタックに３つの値が次々とpushされる様子
配列を下から順に0,1,2,..,7のように示している。
「←」はスタックポインタが指している場所を示す。
各段階でデータが格納された状態では，スタックポインタは常に「次に格納すべき場所」を指している。 |
|
|
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 789 |
| 456 |
| 123 | |
| 3つの値が格納された状態 |
→
pop
↓
789が
取り
出さ
れる |
|
|
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 789 |
| 456 |
| 123 | |
| 789が取り出された状態 |
→
pop
↓
456が
取り
出さ
れる |
|
|
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 789 |
| 456 |
| 123 | |
| 456が取り出された状態 |
→
pop
↓
123が
取り
出さ
れる |
|
|
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 未定 |
| 789 |
| 456 |
| 123 | |
| 123が取り出された状態 |
図２．２ ３つの値が格納されているスタックから３つの値が次々とpopされる様子
値を取り出しても，配列の中ではその値は消えるわけではなく，スタックポインタが指さなくなって，無効状態になる。
ここでも各段階で，スタックポインタは常に「次に格納すべき場所」を指している。（popする時，取り出すデータを指しているわけではないことに注意） |
まとめ
スタックポインタは常に次のデータを格納すべき場所を指す（初期状態で0）
関数pushの作業の実際
（push１）スタックポインタの指す位置にpushされた値を格納
（push２）スタックポインタの値を１つ進める
関数popの作業の実際
（pop１）スタックポインタの値を１つ戻す
（pop２）スタックポインタの指す位置の値を取り出して関数の値として戻す
未完成となっている関数int pop(void)をつくりなさい。レポートはプログラム全容および実行結果を提出のこと。
（x01ex01.c）
|
#include <stdio.h>
/********************stack構造の記述のはじまり***************/
#define
SIZE 8
int stack_buffer[SIZE]; /*格納のための配列*/
int
stack_pointer=0; /*次に格納する場所を示す*/
void push(int var)
/*格納関数*/
{
stack_buffer[stack_pointer]=var;
/*(push1)*/
stack_pointer++;
/*(push2)*/
}
int pop(void)
/*取り出し関数*/
{
★ここの中身を作りなさいpop1とpop2の作業を記述すればよい★
}
/********************stack構造の記述のおわり*****************/
int main()
{
push(31);
push(32);
push(33);
push(34);
push(35);
printf("%d\n",pop());
printf("%d\n",pop());
printf("%d\n",pop());
printf("%d\n",pop());
printf("%d\n",pop());
push(36);
push(37);
push(38);
push(39);
push(40);
printf("%d\n",pop());
printf("%d\n",pop());
printf("%d\n",pop());
printf("%d\n",pop());
printf("%d\n",pop());
return
0;
} |
|
次のような実行結果になれば正解です。
35
34
33
32
31
40
39
38
37
36 |
注意
ここまでの説明とは異なり，次のような方針でスタックを作ることもできる
スタックポインタは常に現在の最終登録データ格納場所を指す（初期状態で-1）
pushの作業の実際
（１）スタックポインタの値を１つ進める
（２）スタックポインタの指す位置にpushされた値を格納
popの作業の実際
（１）スタックポインタの指す位置の値を取り出す
（２）スタックポインタの値を１つ戻す
（３）「（１）」で取り出した値を，関数の値として戻す
逆ポーランド記法とは，演算子（+-*/）の演算対象が直前の２つの値になる記法である。通常数学の記法では演算子（+-*/）の演算対象は演算子の前後の2つの値である。
逆ポーランド記法の演算式の例を次に示す。（「=」がない場合）
gets()またはgetchar()でキーボードから式をもらって，計算する逆ポーランド記法電卓を作りなさい。
ここに示した例をすべて実行して検証しなさい。
（x01ex02.c）
| 通常の表記 |
逆ポーランド記法 |
|
| 23+45 |
23,45+ |
68 |
| 43-13 |
43,13- |
30 |
| 3.5*2.5 |
3.5,2.5* |
8.75 |
| 16/8 |
16,8/ |
2.0 |
| (3-2)/5 |
3,2-5/ |
0.2 |
| (2+3)*4 |
2,3+4* |
20 |
| 2*(3+4) |
2,3,4+* |
14 |
| 12.4*(3-(4+5)) |
12.4,3,4,5+-* |
-74.4 |
ヒント 数字と「．」が連なっている間は数値文字列として文字型変数配列にしまう。
「，」のところで数値文字列から数値として読み出し，double型変数バッファをPUSH。
演算子「+-*/」なら，数値文字列から数値として読み出し，double型変数バッファをPUSH。
2回POPして，得られた２つの値を演算して，答えをPUSH。
式の終わりになったら，POPして答えを画面に表示
関数sscanf()は文字列から読み出すscanf()である。
補足説明
さらに34の補数（すなわち-34）を作る時には「34C」と書くことにする。
（「-」は２項演算子であり，単項演算子のマイナス（たとえば-12のマイナス）は後ろ付のCとする）
| 通常の表記 |
逆ポーランド記法 |
|
| 23+(-45) |
23,45C+ |
-22 |
| (-3)-(-13) |
3C,13C- |
10 |
| 3*(-5) |
3,5C* |
-15 |
| 未完成プログラムの一部 |
|
double RPcalculation(char*
expression)
{
char numericalString[256];
/*数値を表わす文字列*/
int i;
/*expression中のポインタ*/
int j;
/*numericalString中のポインタ*/
double
value;
i=j=0;
initStack();
/*スタックの初期化*/
while (expression[i]) { /* while
(expression[i]!='\0')
{ と同じ意味 */
if
(isdigit(expression[i]) || expression[i]=='.')
{
numericalString[j++]=expression[i++];
} else if (expression[i]==',')
{
if
(j)
{
numericalString[j]='\0';
sscanf(numericalString,"%lf",&value);
pushData(value);
j=0;
}
i++;
} else if
(expression[i]=='C' || expression[i]=='c')
{
if
(j)
{
numericalString[j]='\0';
sscanf(numericalString,"%lf",&value);
pushData(-value);
j=0;
}
i++;
} else if
(expression[i]=='+')
{
if
(j)
{
numericalString[j]='\0';
sscanf(numericalString,"%lf",&value);
pushData(value);
j=0;
}
pushData(popData()+popData());
i++;
} else if
(expression[i]=='-')
{
if
(j)
{
numericalString[j]='\0';
sscanf(numericalString,"%lf",&value);
pushData(value);
j=0;
}
pushData(-popData()+popData());
i++;
} else if
(expression[i]=='*') {
途中省略
}
return
popData();
}
int main()
{
char
expression[512]; /*数式表現を入力する文字列容器*/
double
value;
printf(">");
gets(expression);
while(expression[0]) { /* while
(expression[0]!='\0')
{ と同じ意味 */
value=RPcalculation(expression);
printf("%lf\n",value);
printf(">");
gets(expression);
}
return
0;
}
|
| 実行結果 薄い色のところはデバッグのためのスナップショット |
>23,45+
push
[23.000000] 23.000000
push [45.000000] 45.000000 23.000000
pop
[45.000000] 23.000000
pop [23.000000]
push [68.000000]
68.000000
pop
[68.000000]
68.000000
>43,13-
push [43.000000] 43.000000
push [13.000000] 13.000000
43.000000
pop [13.000000] 43.000000
pop
[43.000000]
push [30.000000] 30.000000
pop
[30.000000]
30.000000
>3.5,2.5*
push [3.500000] 3.500000
push [2.500000] 2.500000
3.500000
pop [2.500000] 3.500000
pop [3.500000]
push
[8.750000] 8.750000
pop
[8.750000]
8.750000
>16,8/
push
[16.000000] 16.000000
push [8.000000] 8.000000 16.000000
pop
[8.000000] 16.000000
pop [16.000000]
push [2.000000]
2.000000
pop [2.000000]
2.000000
>3,2-5/
push [3.000000] 3.000000
push [2.000000] 2.000000
3.000000
pop [2.000000] 3.000000
pop [3.000000]
push
[1.000000] 1.000000
push [5.000000] 5.000000 1.000000
pop
[5.000000] 1.000000
pop [1.000000]
push [0.200000]
0.200000
pop [0.200000]
0.200000
>2,3+4*
push [2.000000] 2.000000
push [3.000000] 3.000000
2.000000
pop [3.000000] 2.000000
pop [2.000000]
push
[5.000000] 5.000000
push [4.000000] 4.000000 5.000000
pop
[4.000000] 5.000000
pop [5.000000]
push [20.000000]
20.000000
pop
[20.000000]
20.000000
>2,3,4+*
push [2.000000] 2.000000
push [3.000000] 3.000000
2.000000
push [4.000000] 4.000000 3.000000 2.000000
pop
[4.000000] 3.000000 2.000000
pop [3.000000]
2.000000
push [7.000000] 7.000000 2.000000
pop [7.000000]
2.000000
pop [2.000000]
push [14.000000]
14.000000
pop
[14.000000]
14.000000
>12.4,3,4,5+-*
push [12.400000] 12.400000
push [3.000000] 3.000000
12.400000
push [4.000000] 4.000000 3.000000 12.400000
push
[5.000000] 5.000000 4.000000 3.000000 12.400000
pop [5.000000]
4.000000 3.000000 12.400000
pop [4.000000] 3.000000
12.400000
push [9.000000] 9.000000 3.000000 12.400000
pop
[9.000000] 3.000000 12.400000
pop [3.000000] 12.400000
push
[-6.000000] -6.000000 12.400000
pop [-6.000000] 12.400000
pop
[12.400000]
push [-74.400000] -74.400000
pop
[-74.400000]
-74.400000 |
ファミりーレストランの待合室には，先着順に名前を書く表が置かれていて，到着したらお客の氏名を書きます。案内されたらそのお客の名前には「済」を表すしるしがつけられます。
このように，先着順に登録して，先に書かれたものから順に取り除かれていく，一次保存場所を「キュー」といいます。→小坂説明 Ｃプログラミング入門 「Ｆ．補足 マルチソースファイル・ポインタ補足・動的二次配列・リスト構造」中の「キューとスタック」
以下のプログラムを完成させ，動作チェックを行ないなさい。ただし，保存できるデータの数は8個までである。
「次
に格納する場所を示すポインタ」は「次に取り出す場所を示すポインタ」に１周まわって追い付いてはいけない。また「次に取り出す場所を示すポインタ」は
「次に格納する場所を示すポインタ」に追い付いてはいけない。追いついてしまった場合の動作不良を観察し，考察しなさい。
if (queue_putpointer==SIZE)
queue_putpointer=0;
の代わりに
queue_putpointer&=7;
にすることができる。どうしてこのようなことができるのか，実行結果の後半に考察を書きなさい。
SIZEが６の時に
queue_putpointer&=5;
としたらうまく動作しない。どうしてか考察しなさい。
（x01ex03.c）
| 未完成メインを持つキューの例 |
|
#include <stdio.h>
/********************queue構造の記述のはじまり***************/
#define
SIZE 8
int queue_buffer[SIZE]; /*格納のための配列*/
int queue_putpointer=0;
/*次に格納する場所を示す*/
int queue_getpointer=0; /*次に取り出す場所を示す*/
void enqueue(int var)
/*格納関数*/
{
queue_buffer[queue_putpointer++]=var;
if
(queue_putpointer==SIZE) queue_putpointer=0;
}
int dequeue(void)
/*取り出し関数*/
{
int var;
var=queue_buffer[queue_getpointer++];
if
(queue_getpointer==SIZE) queue_getpointer=0;
return
var;
}
/********************queue構造の記述のおわり*****************/
int main()
{
★ここの中身を作りなさい★
return
0;
} |
実行ファイル例と実行例
Windows実行ファイル
| 実行例QueueTest.exe |
|
============== Queue サンプルプログラム
==============
使い方: >>command
value[enter]
-----------------------------------------
コマンド | put
| get
| quit
コマンドの意味 | 格納 | 取出 | 終了
-----------------------------------------
>>put
value
（putの後ろに格納したい値（整数）を書く)
>>get
(getの後ろには何も書かない)
>>quit
(quitの後ろには何も書かない)
======================================================
>>put 123
>>put
234
>>get
123
>>get
234
>>put
-123
>>put 444
>>put
555
>>get
-123
>>get
444
>>get
555
>>put
111
>>put 222
>>put 333
>>put
444
>>put 555
>>put 666
>>put
777
>>put 888
>>put
999
>>get
999
>>get
222
>>get
333
>>get
444
>>get
555
>>get
666
>>get
777
>>get
888
>>get
999
>>quit
Pushing any key leads the exit. |
123を先に，その後234を格納
取り出すと，先に123が出てきて
その後，234が出てくる
-123，444，555を順に格納
取り出すと，-123，444，555の
順に出てくる
111，222，．．．，888，999を
順に格納する
取り出すと，111の代わりに999
が取り出されている。
その後は222，333，．．．，
888，999が取り出されている。
どうして111が取り出されずに
999が取り出されたのか
考察しなさい。 |
複数のデータがつながりを持っていて，そのつながりがあることを示しながら保存するデータ構造をリスト構造という。
リスト構造の変形されたものとして木構造がある。特に単純な一方向に連結されたリスト構造を線形リスト構造という。
線形リスト構造は，大きさが伸び縮みする配列としても用いられることがある。
→小坂説明 Ｃプログラミング入門 「Ｆ．補足 マルチソースファイル・ポインタ補足・動的二次配列・リスト構造」中の
「typedefを用いた構造体定義」，「リスト構造入門」
および
「リスト構造」
（この説明はデータを登録するごとにメモリ管理をしている例であり，メモリ・アドレスの概念が
しっかり出来ていないと読むのに苦労する。ポインタのポインタが出てくる。）
1つのデータは，「国の名前，首都」よりできている。
リスト構造にデータを保存し，表示し，消去しなさい。
作るべき関数は，
（１）リストの先頭からｎ番目に，ある国のデータを保存
（現在存在しているデータ数はｍとして，ｎ＜＝ｍなら現在のｎ番目のデータはｎ＋１にずれる。
そうでなかったらリストの最後にデータが付け加えられるものとする）
（２）先頭からｎ番目のデータを表示（現在存在しているデータ数はｍとして，ｍ＜ｎの場合はなにもしない）
（３）先頭からｎ番目のデータを消去（現在存在しているデータ数はｍとして，ｍ＜ｎの場合はなにもしない）
とする。
３つの関数の動作検証を行ないなさい。
使用するデータは
日本 東京
イギリス ロンドン
フランス パリ
イタリア ローマ
中国 北京
として，すべてを登録しなさい。
（x01ex04.c）
実行ファイル例と実行例
Windows実行ファイル
| 実行例QueueTest.exe |
|
>ListTest.exe
====================List サンプルプログラム
使い方====================
使い方: >>command number Country
Capital[enter]
-----------------------------------------------------------------
コマンド
| register | read | delete | survey | number
| quit
意味 | 登録 | 読出 | 消去 | 中を見る | データ数 |
終了
-----------------------------------------------------------------
>>register
position Country Capital (registerの後に登録位置，国名，首都を書く)
>>read
position
(readの後に読み出し位置を書く)
>>delete
position
(deleteの後に消去位置を書く)
>>survey
(surveyの後には何も書かない)
>>number
(numberの後には何も書かない)
>>quit
(quitの後には何も書かない)
注意1 位置positionは０から数え始める 0,1,2,3,...
注意2
コマンドの文字列区切りは半角スペースを使う。全角スペースは使わない
使用例
>>register 1 インドネシア
ジャカルタ
>>read 0
>>delete
0
>>survey
======================================================================
>>register 0 日本
東京
>>survey
**
printListStructure (debug 1)
**
&namelist(root)=0040F640
namelist(root)
=00373148
&node = 00373148
node.country =
[日本]
node.capital = [東京]
node.next =
[00000000]
>>register 1 イギリス
ロンドン
>>register 1 フランス
パリ
>>register 1 イタリア
ローマ
>>register 1 中国
北京
>>survey
**
printListStructure (debug 2)
**
&namelist(root)=0040F640
namelist(root)
=00373148
&node = 00373148
node.country =
[日本]
node.capital = [東京]
node.next =
[00373288]
&node = 00373288
node.country =
[中国]
node.capital = [北京]
node.next =
[00373238]
&node = 00373238
node.country =
[イタリア]
node.capital = [ローマ]
node.next =
[003731E8]
&node = 003731E8
node.country =
[フランス]
node.capital = [パリ]
node.next =
[00373198]
&node = 00373198
node.country =
[イギリス]
node.capital = [ロンドン]
node.next =
[00000000]
>>read 2
2
イタリア ローマ
>>read 3
3 フランス
パリ
>>read 4
4 イギリス
ロンドン
>>read 5
5 NotAvailable
NotAvailable
>>delete
1
>>delete 1
>>delete 1
>>survey
** printListStructure (debug 3)
**
&namelist(root)=0040F640
namelist(root)
=00373148
&node = 00373148
node.country =
[日本]
node.capital = [東京]
node.next =
[00373198]
&node = 00373198
node.country =
[イギリス]
node.capital = [ロンドン]
node.next =
[00000000]
>>delete
0
>>survey
**
printListStructure (debug 4)
**
&namelist(root)=0040F640
namelist(root)
=00373198
&node = 00373198
node.country =
[イギリス]
node.capital = [ロンドン]
node.next =
[00000000]
>>number
number of Datas = 1
>>delete 0
>>survey
** printListStructure (debug 5)
**
&namelist(root)=0040F640
namelist(root) =00000000
>>register 0 日本
東京
>>survey
**
printListStructure (debug 6)
**
&namelist(root)=0040F640
namelist(root)
=00373148
&node = 00373148
node.country =
[日本]
node.capital = [東京]
node.next =
[00000000]
>>delete
0
>>survey
**
printListStructure (debug 7)
**
&namelist(root)=0040F640
namelist(root) =00000000
>>quit
0
Pushing any key leads the
exit. |
参考 キーワードと値を取り込む方法
関数 char *strstr(char *str1,char
*str2)
文字列str1中に，文字列str2を見つけ，見つけたらそのアドレスを返す。見つからなかったらNULLを返す。
関数 int
sscanf(char *buff, char *format,
変数ポインタの羅列)
scanfがキーボード文字列から値を読むのに対し，sscanfは文字列buffから値を読む
似た関数にfscanfがあり，これはファイルから値を読んでいた。
| 2乗，3乗あるいは積を対話で求めるプログラム（キーワードと値を取り込む方法） |
|
#include <stdio.h>
#include
<string.h>
#include <math.h>
char
*usage=
"与えられた数の2乗，3乗を求めます。\n"
"また与えられた2数の積を求めます\n"
"コマンドは「square」「cube」「multiply」「quit」の４つだけです\n"
"起動後の使い方\n"
">square
12\n"
" 12の2乗を求めます\n"
">cube
20\n"
" 20の3乗を求めます\n"
">multiply 20
15\n"
" 20×15を求めます\n"
">quit\n"
" 終了します\n";
int main()
{
double
x,x1,x2;
char
tmp[128],dummy[128];
puts(usage);
printf(">");
gets(tmp);
while (strstr(tmp,"quit")!=tmp)
{
/*入力文字列が"quit"でない*/
if
(strstr(tmp,"square")==tmp)
{
/*入力文字列が"square"だったら*/
sscanf(tmp,"%s
%lf",dummy,&x);
printf("%lf\n",x*x);
}
else if (strstr(tmp,"cube")==tmp) {
/*入力文字列が"cube"だったら*/
sscanf(tmp,"%s
%lf",dummy,&x);
printf("%lf\n",x*x*x);
}
else if (strstr(tmp,"multiply")==tmp) {
/*入力文字列が"multiply"だったら*/
sscanf(tmp,"%s %lf %lf", dummy, &x1,
&x2);
printf("%lf\n",x1*x2);
}
printf(">");
gets(tmp);
}
return
0;
} |
| 実行結果 |
|
与えられた数の2乗，3乗を求めます。
また与えられた2数の積を求めます
コマンドは「square」「cube」「multiply」「quit」の４つだけです
起動後の使い方
>square
12
12の2乗を求めます
>cube 20
20の3乗を求めます
>multiply 20
15
20×15を求めます
>quit
終了します
>square
12
144.000000
>cube
20
8000.000000
>multiply 20
15
300.000000
>quit
|
ソートは，数値データを大きい順や小さい順に並べたり，文字列データを辞書順に並べ替える作業のことです。
→小坂説明 Ｃプログラミング入門 「４．配列と文字・文字列」中の 「４．２ ソート（並び替え）」
選択ソート
： List 4.2.1〜List 4.2.4
バブルソート：List 4.2.5
「５．４ 引数が配列の関数」
→小坂 ソートデモ
デモ用アプリケーション（ダウンロードしてから実行のこと）
課題 整数値データの選択ソート関数をつくりなさい。
ソートは整数値を小さい順に並べ替えるものとし，ソート結果を検査する関数で検査しなさい。
ソート対象整数値データの数は１００，１０００，１００００，１０００００とし，それぞれソートに要した時間を調べなさい。
ソート対象のデータは乱数発生関数rand()を用いなさい。また既に小さい順や大きい順に並んでいるデータも使いなさい。
はやく終わりすぎて測定できない時は，1000回連続して実行して全時間を１０００で割って1回あたりの作業時間を求めなさい。（乱数データ作成から，ソート検証まで含めてよい。）
10分以上かかるような場合は，測定不能としてよい。
結果は1回の作業の時間（単位msec）を使って，次のような表にまとめなさい。
なお，PCでは，バックグラウンドで複数の作業が行われているため，それに時間を乱される可能性があります。
矛盾した結果が出てきた場合は，再度やり直してください。
（x02ex01.c）
選択ソート
| データ種類 ＼ データ数 |
100 |
300 |
1000 |
3000 |
10000 |
30000 |
100000 |
| 乱数データ |
|
|
|
|
|
|
|
| 小さい順データ |
|
|
|
|
|
|
|
| 大きい順データ |
|
|
|
|
|
|
|
使用したCPU情報 例えばPentium4-M
1.80GHz（マイコンピュータ右クリックープロパティ参照）
ヒント１
| このままでは不完全です。自分で作るためのヒントです |
|
/*乱数データ*/
void makedata(int x[], int
num)
{
int i;
for (i=0;
i<num; i++)
x[i]=rand();
}
/*最初から小さい順に並んでいるデータ*/
void makedata1(int x[], int num)
{
int i;
for (i=0; i<num; i++)
x[i]=i;
}
/*最初から大きい順に並んでいるデータ*/
void makedata2(int x[], int
num)
{
int i;
for (i=0;
i<num; i++) x[i]=num-i-1;
}
void
printdata(int x[], int num)
{
int
i;
for (i=0; i<num; i++) printf("%2d
",x[i]);
printf("\n");
}
/*小さい順ソート済みデータのチェック
戻り値０：正常
１：異常あり
*/
int
checkSortedData(int x[], int num)
{
int
i;
int ng=0;
for (i=0;
i<num-1; i++) {
if
(x[i+1]<x[i])
{
printf("%2d
%2d\n",x[i],x[i+1]);
ng=1;
}
}
return
ng;
}
/*選択ソート*/
void
SelectionSort(int x[], int num)
{
ここを作る
}
int main()
{
int x[SIZE];
/*大きな配列はスタティック変数とする*/
int
nogood;
makedata(x,SIZE);
printdata(x,SIZE); /*SIZEが大きい場合は使わない*/
SelectionSort(x,SIZE);
printdata(x,SIZE);
/*SIZEが大きい場合は使わない*/
nogood=checkSortedData(x,SIZE);
if (nogood)
printf("no good\n");
printf("\n");
return
0;
} |
ヒント２ windowsのOS依存でPC起動時からの時間を得る関数がある。
これを作業前と作業後に使えば，作業にかかった時間がわかる。
#include
"windows.h"のもとで関数GetTickCount()を使う。
| 関数GetTickCount()使用例 |
|
#include "stdio.h"
#include "windows.h"
/*関数GetTickCount()を使うため*/
void doNothing()
{
printf("working
working working\r");
}
int
main()
{
int time1,time2;
time1=GetTickCount();
/*msec単位でPC起動からの経過時間*/
printf("started at %d
[msec]\n",time1);
for (i=0; i<100000; i++)
doNothing();
time2=GetTickCount();
/*msec単位でPC起動からの経過時間*/
printf("terminated at %d
[msec]\n",time2);
printf("process time %d
[msec]\n",time2-time1);
return
0;
} |
| 実行結果 |
|
started at 1148641 [msec]
terminated at 1153829
[msec]
process time 5188 [msec] |
| 関数GetTickCount()によるソートの時間測定（１） |
|
int main()
{
int
x[SIZE]; /*大きな配列はスタティック変数とする*/
int
nogood;
int time1,time2;
makedata(x,SIZE);
printdata(x,SIZE);
/*SIZEが大きい場合は使わない*/
time1=GetTickCount();
/*msec単位でPC起動からの経過時間*/
SelectionSort(x,SIZE);
time2=GetTickCount();
/*msec単位でPC起動からの経過時間*/
printdata(x,SIZE);
/*SIZEが大きい場合は使わない*/
nogood=checkSortedData(x,SIZE);
if (nogood)
printf("no good\n");
/*else
printf("good\n");*/
printf("process time %d
[msec]\n",time2-time1);
return
0;
} |
|
関数GetTickCount()によるソートの時間測定（２）
はやすぎて測定不能な場合100回とか1000回ほど実行して測定する
makedata()やcheckSortedData()などの処理時間は無視する |
|
int main()
{
int
x[SIZE]; /*大きな配列はスタティック変数とする*/
int
nogood;
int time1,time2;
int
i;
time1=GetTickCount();
/*msec単位でPC起動からの経過時間*/
for (i=0; i<1000; i++)
{
makedata(x,SIZE);
SelectionSort(x,SIZE);
nogood=checkSortedData(x,SIZE);
if (nogood) printf("no
good\n");
/*else
printf("good\n");*/
}
time2=GetTickCount();
/*msec単位でPC起動からの経過時間*/
printf("process time %d
[msec]\n",time2-time1);
return
0;
} |
整数値データのバブルソート関数をつくりなさい。
ソートは整数値を小さい順に並べ替えるものとし，ソート結果を検査する関数で検査しなさい。
ソート対象整数値データの数は１００，１０００，１００００，１０００００とし，それぞれソートに要した時間を調べなさい。
ソート対象のデータは乱数発生関数rand()を用いなさい。また既に小さい順や大きい順に並んでいるデータも使いなさい。
10分以上かかるような場合は，測定不能としてよい。
結果は1回の作業の時間（単位msec）を使って，次のような表にまとめなさい。
なお，PCでは，バックグラウンドで複数の作業が行われているため，それに時間を乱される可能性があります。
矛盾した結果が出てきた場合は，再度やり直してください。
（x02ex02.c）
バブルソート
| データ種類 ＼ データ数 |
100 |
300 |
1000 |
3000 |
10000 |
30000 |
100000 |
| 乱数データ |
|
|
|
|
|
|
|
| 小さい順データ |
|
|
|
|
|
|
|
| 大きい順データ |
|
|
|
|
|
|
|
使用したCPU情報
提出するプログラムおよび実行結果（ソート結果，ソート検査結果を含む）はデータ数２０のものとする。
また実行時間分布も実行結果の後ろにわかるように記述しなさい。
→小坂説明 Ｃプログラミング入門 「Ｆ．補足 マルチソースファイル・ポインタ補足・動的二次配列・リスト構造」中の「挿入ソート」
整数値データの挿入ソート関数をつくりなさい。
ソートは整数値を小さい順に並べ替えるものとし，ソート結果を検査する関数で検査しなさい。
ソート対象整数値データの数は１００，１０００，１００００，１０００００とし，それぞれソートに要した時間を調べなさい。
ソート対象のデータは乱数発生関数rand()を用いなさい。また既に小さい順や大きい順に並んでいるデータも使いなさい。
はやく終わりすぎて測定できない時は，1000回連続して実行して全時間を１０００で割って1回あたりの作業時間を求めなさい。（乱数データ作成から，ソート検証まで含めてよい。）
10分以上かかるような場合は，測定不能としてよい。
結果は1回の作業の時間（単位msec）を使って，次のような表にまとめなさい。
なお，PCでは，バックグラウンドで複数の作業が行われているため，それに時間を乱される可能性があります。
矛盾した結果が出てきた場合は，再度やり直してください。
（x02ex03.c）
挿入ソート
| データ種類 ＼ データ数 |
100 |
300 |
1000 |
3000 |
10000 |
30000 |
100000 |
| 乱数データ |
|
|
|
|
|
|
|
| 小さい順データ |
|
|
|
|
|
|
|
| 大きい順データ |
|
|
|
|
|
|
|
使用したCPU情報
提出するプログラムおよび実行結果（ソート結果，ソート検査結果を含む）はデータ数２０のものとする。
また実行時間分布も実行結果の後ろにわかるように記述しなさい。
→小坂説明 Ｃプログラミング入門 「Ｆ．補足 マルチソースファイル・ポインタ補足・動的二次配列・リスト構造」中の「シェルソート」
整数値データのシェルソート関数をつくりなさい。
ソートは整数値を小さい順に並べ替えるものとし，ソート結果を検査する関数で検査しなさい。
ソート対象整数値データの数は１００，１０００，１００００，１０００００とし，それぞれソートに要した時間を調べなさい。
ソート対象のデータは乱数発生関数rand()を用いなさい。また既に小さい順や大きい順に並んでいるデータも使いなさい。
はやく終わりすぎて測定できない時は，1000回連続して実行して全時間を１０００で割って1回あたりの作業時間を求めなさい。（乱数データ作成から，ソート検証まで含めてよい。）
10分以上かかるような場合は，測定不能としてよい。
結果は1回の作業の時間（単位msec）を使って，次のような表にまとめなさい。
なお，PCでは，バックグラウンドで複数の作業が行われているため，それに時間を乱される可能性があります。
矛盾した結果が出てきた場合は，再度やり直してください。
（x02ex04.c）
シェルソート
| データ種類 ＼ データ数 |
100 |
300 |
1000 |
3000 |
10000 |
30000 |
100000 |
| 乱数データ |
|
|
|
|
|
|
|
| 小さい順データ |
|
|
|
|
|
|
|
| 大きい順データ |
|
|
|
|
|
|
|
使用したCPU情報
提出するプログラムおよび実行結果（ソート結果，ソート検査結果を含む）はデータ数２０のものとする。
また実行時間分布も実行結果の後ろにわかるように記述しなさい。
→小坂説明 Ｃプログラミング入門 「Ｆ．補足 マルチソースファイル・ポインタ補足・動的二次配列・リスト構造」中の「クイックソート」
→小坂 ソートデモ
デモ用アプリケーション（ダウンロードしてから実行のこと）
整数値データのクイックソート関数をつくりなさい。
ソートは整数値を小さい順に並べ替えるものとし，ソート結果を検査する関数で検査しなさい。
ソート対象整数値データの数は１００，１０００，１００００，１０００００とし，それぞれソートに要した時間を調べなさい。
ソート対象のデータは乱数発生関数rand()を用いなさい。また既に小さい順や大きい順に並んでいるデータも使いなさい。
はやく終わりすぎて測定できない時は，1000回連続して実行して全時間を１０００で割って1回あたりの作業時間を求めなさい。（乱数データ作成から，ソート検証まで含めてよい。）
10分以上かかるような場合は，測定不能としてよい。
結果は1回の作業の時間（単位msec）を使って，次のような表にまとめなさい。
なお，PCでは，バックグラウンドで複数の作業が行われているため，それに時間を乱される可能性があります。
矛盾した結果が出てきた場合は，再度やり直してください。
（x02ex05.c）
クイックソート
| データ種類 ＼ データ数 |
100 |
300 |
1000 |
3000 |
10000 |
30000 |
100000 |
| 乱数データ |
|
|
|
|
|
|
|
| 小さい順データ |
|
|
|
|
|
|
|
| 大きい順データ |
|
|
|
|
|
|
|
使用したCPU情報
提出するプログラムおよび実行結果（ソート結果，ソート検査結果を含む）はデータ数２０のものとする。
また実行時間分布も実行結果の後ろにわかるように記述しなさい。
→小坂説明 Ｃプログラミング入門 「Ｆ．補足 マルチソースファイル・ポインタ補足・動的二次配列・リスト構造」中の「マージソート」
整数値データのマージソート関数をつくりなさい。
ソートは整数値を小さい順に並べ替えるものとし，ソート結果を検査する関数で検査しなさい。
ソート対象整数値データの数は１００，１０００，１００００，１０００００とし，それぞれソートに要した時間を調べなさい。
ソート対象のデータは乱数発生関数rand()を用いなさい。また既に小さい順や大きい順に並んでいるデータも使いなさい。
はやく終わりすぎて測定できない時は，1000回連続して実行して全時間を１０００で割って1回あたりの作業時間を求めなさい。（乱数データ作成から，ソート検証まで含めてよい。）
10分以上かかるような場合は，測定不能としてよい。
結果は1回の作業の時間（単位msec）を使って，次のような表にまとめなさい。
なお，PCでは，バックグラウンドで複数の作業が行われているため，それに時間を乱される可能性があります。
矛盾した結果が出てきた場合は，再度やり直してください。
（x02ex06.c）
マージソート
| データ種類 ＼ データ数 |
100 |
300 |
1000 |
3000 |
10000 |
30000 |
100000 |
| 乱数データ |
|
|
|
|
|
|
|
| 小さい順データ |
|
|
|
|
|
|
|
| 大きい順データ |
|
|
|
|
|
|
|
使用したCPU情報
提出するプログラムおよび実行結果（ソート結果，ソート検査結果を含む）はデータ数２０のものとする。
また実行時間分布も実行結果の後ろにわかるように記述しなさい。
→小坂説明 Ｃプログラミング入門 「Ｆ．補足 マルチソースファイル・ポインタ補足・動的二次配列・リスト構造」中の「ヒープソート」
→小坂 ソートデモ
デモ用アプリケーション（ダウンロードしてから実行のこと）
整数値データのヒープソート関数をつくりなさい。
ソートは整数値を小さい順に並べ替えるものとし，ソート結果を検査する関数で検査しなさい。
ソート対象整数値データの数は１００，１０００，１００００，１０００００とし，それぞれソートに要した時間を調べなさい。
ソート対象のデータは乱数発生関数rand()を用いなさい。また既に小さい順や大きい順に並んでいるデータも使いなさい。
はやく終わりすぎて測定できない時は，1000回連続して実行して全時間を１０００で割って1回あたりの作業時間を求めなさい。（乱数データ作成から，ソート検証まで含めてよい。）
10分以上かかるような場合は，測定不能としてよい。
結果は1回の作業の時間（単位msec）を使って，次のような表にまとめなさい。
なお，PCでは，バックグラウンドで複数の作業が行われているため，それに時間を乱される可能性があります。
矛盾した結果が出てきた場合は，再度やり直してください。
（0x2ex07.c）
ヒープソート
| データ種類 ＼ データ数 |
100 |
300 |
1000 |
3000 |
10000 |
30000 |
100000 |
| 乱数データ |
|
|
|
|
|
|
|
| 小さい順データ |
|
|
|
|
|
|
|
| 大きい順データ |
|
|
|
|
|
|
|
使用したCPU情報
提出するプログラムおよび実行結果（ソート結果，ソート検査結果を含む）はデータ数２０のものとする。
また実行時間分布も実行結果の後ろにわかるように記述しなさい。