プログラミングⅠ

プログラミングⅠ
Report #8
提 出 日 : 2008 年 7 月 17 日(木)
所
属
:工 学 部 情 報 工 学 科
学籍 番 号 : 0
氏
名
:嘉
8
5
陽
7
1
宗
5
H
史
プログラミングⅠ
基数変換と SORT
1
入力した正の整数を降順に並べ換えて出力するプログラムを作成せよ。プログラムは個別にコンパ
イルし、 make コマンドで実行すること。
ソース
cardinal.c
ソース
conv10.c
ソース
select_sort.c
ソース
print_num.c
ソース
msg.c
7
ソース
Makefile
7
出力結果
考察
……………………………………………………………1
1
2
5
6
8
8
リスト構造のプログラムの動作を解析しなさい
ソース
考察
感想
9
9
10
10
基数変換と SORT
入力した正の整数を降順に並べ換えて出力するプログラムを作成せよ。プログラム
は個別にコンパイルし、 make コマンドで実行すること。
入力データは 50 以下とし、以下の数が混在しているとする。
16 進数:先頭 1 文字が x または X(エックスの小文字か大文字)
8 進数:先頭 1 文字が 0(零)
10 進数:先頭 1 文字が 0(零)以外の数字
ソース cardinal.c
/*
Program
: cardinal.c
Comment
: 基数変換と整列処理
*/
#include <stdio.h>
#include <string.h>
#define MAX 256
void conv10(char **x, int *k, int n);
void select_sort(int x[], int m[], int n);
void print_num(char *x[], int m[], int n);
①
void msg();
int main(){
char *dt[50], num[10], buf[MAX], *p=buf;
②
int n=0, len, i10[50], move[50];
puts("-------- Input");
while(gets(num) != NULL) {
len = strlen(num);
if(p > ?_?_?_?_? ) break;/*(1)*/
strcpy(p, num);
③
dt[n] = p;
p += ?_?_?_?_?;/*(2)*/
n++;
}
puts("-------- Result");
-1-
conv10(?_?_?_?_?);
select_sort(?_?_?_?_?);/*(3)*/
print_num(?_?_?_?_?);/*(4)*/
④
msg();
return(0);
}
穴埋め・考察
8行目の「#define MAX 256 」で MAX=256 を定義する。
①の部分で関数のプロトタイプを宣言する。
②の部分でアドレスの設定をする「*dt[50]」で文字列の先頭アドレスを指す。「num[10]」で入
力した文字列を格納する。「buf[50]」でnum の文字列をコピーして格納する。「*p=buf」でbuf
の先頭アドレスを格納する。while 文 配列num がNULL になるまでループ。{ strlen(num)で
num の長さをlen に代入。(1)strcpy(p, num)でp が示す先(buf)にnum の文字列コピー。dt
[n]にp を代入する(アドレス)。
③の部分で文字列(数字)を入力させる。ここで(1)には「buf +MAX -(len+1)」が入る。これは
もしp がbuf の容量を超えてしまうとループから抜けるということ。buf+MAX =buf[MAX]と同じ
である。-(len+1)をしているのは、buf[MAX](=256)を超えると超過分が入っていたものを上きし
てしまう恐れがあるためである。
(2)には「len+1」が入る。buf にうまく数値を入れていくため +len。さらに¥0 のため +1。
する。n++でn を更新。NULLが入力された時点で}while 文を抜ける。
たとえば数値 3 、 18 、 34 、 xa4 、 x5d 、 067 、 054 を順に入力したとするとdt[0] には3
の先頭アドレス、dt[1]には18 の先頭アドレス、・・・となり、*p =buf となってるのでbuf に下
の図のように格納される。
3
¥0
1
8
¥0
3
4
¥n
④ではそれぞれ使う引数を各々の関数に引き継ぐ。
ソース conv10.c
/*
Program
: conv10.c
*/
void conv10(char **x, int *k, int n){
while(n-- > 0){
switch(**x){
case '0' :
-2-
①
x
a
4
¥n
・・・・
sscanf(?_?_?_?_?, "%o", k);/*(6)*/
break;
②
case 'x' :
case 'X' :
sscanf(?_?_?_?_?, "%x", k);/*(7)*/
break;
default :
sscanf(?_?_?_?_?, "%u", k);/*(8)*/
break;
}
?_?_?_?_?;/*(9)*/
?_?_?_?_?;/*(10)*/
}
}
穴埋め・解説
①で cardinal.c から引数の引き渡しを行う。 main 関数の「 dt 」は「 **x 」に、 main 関
数の「 i10 」は「*k 」に、 main 関数の「 n 」は「 n 」にそれぞれ引き継がれる。
②は while 文である。 n >0 を検証し、 n >0 なら while 文を実行。その後、 n-- (=n-1)
をする。ここでは16進数、8進数、それ以外(10進数)を分けている。 switch 文を用いて分
ける。次のページの図のように動きフィルタに途中で引っかかったら sscanf()で文字列から
数値に変換され読み取られ、 k に格納して break する。
(6) は「*x+1 」が。 (7)は「 *x+1 」が。 (8)は「 *x 」がそれぞれはいる。(6)(7)は「 x , X 」、
「 0 」 を読み込まない様に、+1 してから。(8)は 10 進数の場合なので OK 。
(9)は「 x++」が。 (10)は「 k++」が入る。(9)(10)は、次に変換された文字列などを処理してい
かないといけないので文字列の先頭アドレス x と変換された数値を格納する k を更新させる。
-3-
**x
先頭が0なら
8進数として読み込む
8進数として
読み込む
16進数として読み込む
先頭が xX なら
16 進数として
読み込む
通常は
この読み込み
break
-4-
ソース select_sort.c
/*
Program : select_sort.c
*/
void select_sort(int x[], int m[], int n){
①
int i, j, k, w;
for(i=0; i<n; i++) m[i]=i;
for(i=0; i<n-1; i++){
k=i;
for(j=i+1; j<n; j++)
if( ?_?_?_?_? ) k=j; /* (11) */
w
= x[i];
②
x[i] = x[k];
x[k] = w;
w
= m[i];
m[i] = m[k];
m[k] = w;
}
}
穴埋め・考察
①で cardinal.c から引数の引き渡しを行う。 main 関数の「 i10 は「 x[]」に。 main 関
数の「 move 」は「 m[]」に。 main 関数の「 n 」は「 n 」に引き継がれる。また変数宣言 int
型 i,j,k,w.をする。
②で入力した数を降順に並び替える。(11)には「 x[j] >x[k]」が入る。
conv10 よりつづく i10 が数値に変換され x[]に順番よく並んで入る。 move が「 select_s
ort()」で並び替えられた順番を m[]に記憶する。
x[] = i10
conb10 の例で使った数値をそのまま使う。10進数に変換されている。
3
18
34
164
先頭の3に注目してほかの数
値と 比 べ て そ の 中の 最 大 の 数
(164)と入れ替える
164
18
34
-5-
3
164
18
34
3
次に2番目の先 18 に注目し
て先頭の 164 以外のほかの数値
と比べてその中の最大の数( 34)
と入れ替える。
164
34
18
3
以下、すべての数が孝順になる
まで続ける。
これが
x[0]
x[1]
x[2]
x[3]
となる。
m[]= move は x[]と連動する形で、順番を記憶する。
これが
0
1
2
3
3
1
2
0
3
2
1
0
m[1]
m[2]
m[3]
m[0]
となる。
すべての数の並び替えが終わったらこの関数は終了
ソース print_num.c
/*
Program
: print_num.c
*/
void print_num(char *x[], int m[], int n){
①
int i;
for(i=0; i<n; i++){
②
puts(?_?_?_?_?);/*(12)*/
}
}
-6-
穴埋め・考察
①で引数の引き渡しを行う。 main 関数の「 dt 」は「*x[]」に。 main 関数の「 move 」は「 m
[]」に。 main 関数の「 n 」は「 n 」にそれぞれ引き継がれる。
int 型 i の変数宣言を行う。
②で for 文の中の puts()で並び替えられたものを表示。(12)には「 x[m[i]]」が入る。「 sel
ect_sort()で並べられた順番の記憶が m[]に入っているのでその順で、「*x(dt)」が指す
アドレスにある文字列を表示させる。
ソース msg.c
/*
Program
: msg.c
*/
int msg(){
printf("#### Message from C #### By Taniguchi¥n");
return(0);
}
考察
最後にメッセージを出力させるためのプログラムである
ソース Makefile
enc: cardinal.o conv10.o select_sort.o print_num.o msg.o
gcc -o enc cardinal.o conv10.o select_sort.o print_num.o
msg.o
cardinal.c: cardinal.c
gcc -c cardinal.c
conv10.c: conv10.c
gcc -c conv10.c
select_sort.c: select_sort.c
gcc -c select_sort.c
print_num.c: print_num.c
gcc -c print_num.c
msg.c: msg.c
-7-
gcc -c msg.c
出力結果
-------- Input
warning: this program uses gets(), which is unsafe.
3
18
34
xa4
x5d
067
054^D
-------- Result
xa4
x5d
067
054
34
18
3
#### Message from C #### By Taniguchi
考察
ワーニングメッセージが出たが問題なく実行できた。
このプログラムは複数の小さなプログラムの集まりである。実際の開発現場でもこのような方法
をとっていると聞く。
たくさんの小さなプログラムが集まって一つのプログラムとして完成したときは、結構うれしい。
-8-
リスト構造のプログラムの動作を解析しなさい
ソース
/*
Program : list.c
Comment : リスト構造
*/
#include <stdio.h>
#include <stdlib.h>
/*FALSE と TRUE の定義*/
#define FALSE 0
#define TRUE !FALSE
/*構造体の型枠の宣言(その関数を node と名付ける)*/
typedef struct Node{
int num;
struct Node *next_ptr;
}node;
/*node の中身が NULL と定義*/
node *start_ptr = NULL;
/*関数のプロトタイプ宣言*/
void ins(int idata){
node *p = start_ptr;
/*start_ptr は node の中身のサイズを置換*/
start_ptr = (node *)malloc(sizeof(node));
/*if 文(もし start_ptr ならば puts の中身を表示)*/
if (start_ptr == NULL) puts("Not enough memory!"), exit(0);
/*(1)絶対的なポインタの参照*/
start_ptr->num = idata;
start_ptr->next_ptr = p;
}
int main(){
-9-
/*(1)で参照したものに型を宣言*/
int idata;
node *p;
/*整数を入力するように文を表示*/
puts("Enter a sequence of integers:");
/*while 文(整数が入力されたら、その整数を ins(idata)とおく)*/
while(scanf("%d", &idata) == TRUE) ins(idata);
/*入力が反転する旨の文を表示*/
puts("In reverse order:");
/*p(start_ptr)が!NULL の時、再度 next_ptr を参照してそれを p に代入*/
for(p = start_ptr; p != NULL; p = p->next_ptr){
printf("%5d-", p->num);
}
/*^D で for 文を脱出*/
puts("/end/");
return(0);
}
考察
解説はソースファイルの中でその都度説明している。
「 struct 」と「 typedef struct 」は同じで構造体の型枠を宣言する際の関数だが、その
違いは名前を付けるか付けないかである。
このソースファイルの例では、この構造体に「 node 」と名付けている。
(1)部分の「->」は「アロー演算子」と呼ばれ左辺ものの中身をみてそれを右辺代入する働きが
ある。 start_ptr->num = idata;は start_ptr が num の中身を見てそれを idata
に代入、 start_ptr->next_ptr = p;は start_ptr が next_ptr の中身を見てそれ
を p に代入するという意味である。
そして代入された物をそのままプログラムの流れで使用する。
感想
今回の最初のソートするプログラムは複数の小さなプログラムをまとめると言うことでできあがっ
たときの感激は大きかった。
リスト構造のプログラムはいまいちよくわからずぐだぐだな考察になってしまった。
プログラミングを学び始めて半年になるが、まだまだ知らないことが多いのでもっともっとがんば
っていきたい。
- 10 -