課題 12-1

——————————————–

1. １．まず，レジュメの通り　struct node の宣言をする．
2. ２．次に new_node 関数を作る．
• 関数内でメモリ確保(malloc)をする．
• 要素の値はkey を入れる．
• そのメモリ領域を指すポインタをreturnで返す．
3. ３．必要な数の構造体ポインタを宣言し，それぞれにnew_nodeで値を割り当てて，その後に，parent, right, leftなどのポインタに代入することで，繋げていく．
4. ４．最後にprint_treeする．

———————————————

まず，書かれている通りの宣言を書いてしまおう．

#include <stdio.h>
#include <stdlib.h>

//nodeの構造体を宣言する（レジュメの通り）
struct node {
    int key;
    struct node *parent, *left, *right;
};

// 問題は↓を作れと言われている．ことと殆ど同義
struct node *new_node(int key)
{

  //関数内で新たなノードに相当するメモリ領域を確保する．
  struct node *p = malloc(sizeof(struct node));　　//mallocで

  /* あとこの関数の中でやることは   

  node *p の値 key に 引数の値 key を代入して

　parent, left, right にをリセットすること．　

　つまり，NULL値を放り込むことだ．

　最終的に関数の戻り値の型は struct node *  (node構造体型のポインタ)　なので

　p を返してあげればいいのです． */

}

main()
{
    struct node *root, *n[10];

    n[0] = new_node(4);
   //という感じで10個のnodeを作って

   /*

    ここにいろいろコードを書く

   */

   //まず　root の値を何かに設定．たとえば，　root = n[5]; のように．

　　//下のように，ノードをつないで行けばできあがり．

    n[0]->left = new_node(0);
    n[0]->right = n[1];
    n[0]->parent = n[2];

    /*

続きをいろいろ書く．

    */   

  // 最後に全体を出力．
  print_tree(root);
}

課題12-2

この問題は木構造というか二分探索木の問題です．

insert関数を作りましょうと言う問題です．

以下，データ構造とアルゴリズムの資料より

insertでは，ノードの値と比較していき，ノードの値より大きければ右，小さければ左というふうに，動いていく．

——————————————-

実装

int insert(int x, struct node *p)
{
    /* 引数のnode *p から始めて，そのノードの値と x の値を比べて

　　大きければ p を p->ritght に進め，

　　小さければ p を p->left に進めます．

　　もし同じ値があれば， return 0 で，同じ値があったので挿入しなかったと返し，

　　key が 0　のノード（外点）を見つけたら，そこに値 x を入れましょう．

    新たなノードには外点が無くなるので，　その左右には new_node(0) をしておきます．

　　挿入に成功したら， return 1; をしておきましょう．

    /*

}

main()

の中はよしなにつくってください．

以下の三段階で解けばいいでしょう．

決して一気に解こうとせずに，各段階で出来ているか確認して下さい．

（１）　データ構造として　構造体の配列を用意する．

（２）　ファイルから文字を数え上げる．

（３）　配列の二つの要素を入れ替える関数を作る．

（４）　ヒープソートを作成する．

（１）　データ構造として　構造体の配列を用意する．

標準的には

#define MAX_CHAR 1000

typedef struct _chdata {
    int        count;
    char    name;
} CHDATA;

CHDATA chdata[MAX_CHAR]; //構造体の配列で作る場合。

int     n_char;    /* 文字の種類 */
int     total_char;    /* 総文字数 */

のように確保すればよいでしょう．

（２）　ファイルから文字を数え上げる．

新しい文字が出てくる旅に，使っていない配列の要素 chdata[n_char]　のnameに

新しい文字を割り当て，count を1にします．

その後，同じ文字が出てくる度に count を１増やして行きましょう．

この時，大文字を小文字に替えることや　改行(\n)，tab(\t)などをスペースに

替えるコトなどをわすれずに

（３）　配列の二つの要素を入れ替える関数を作る．

chdata[i]　と　chdata[k] を入れ替える swap関数を作りましょう．

（４）　ヒープソートを作成する．

データ構造とアルゴリズムでのヒープの復習をした上で，

ヒープの一次元配列による表現　を理解しましょう （教科書p.136など）

その上でヒープソートの動きを理解し　（こちらのページも参照）

その上で，教科書 p.137 のソースコードをホボ写しましょう．

このソースコードを一生懸命読解する！！　←ここ山場！！

これが何をやっているか理解出来れば，

それを今回のプログラムに合うように，修正してあげれば，

8-4が達成されます．

追記：

プログラムを進めるうえで，　配列の状況を常にチェックするようにした方が良いので

現在のデータを出力する関数

void print_all_data(){
    for(i=0;i<n_char;i++){
        printf(”%c  %d\n”,chdata[i].name,chdata[i].count);
    }
}

のようなものを先に作っておくとよいでしょう．

【H20前期】

• プログラミング演習１
• 知能情報学実験１　（信号処理）

【H20 後期】

• プログラミング演習２
  • 第１週
  • 第2週
  • 第３週
  • 第４週
  • 第５週から第７週まで
  • 第8週から第11週まで
  • 第１２週～第１４週　講義補助資料（木構造）
• 留学生数学
• 知能システム創成Ⅱ
• 日本の科学技術（初回，最終回のみ）

2009/07/02 の時間中にホワイトボードで教員・TA/ESでブレストした

アイデア集です．

参考までに・・・・

ゲーム
トランプ
大富豪
７並べ
ばば抜き
ポーカー
麻雀
どんじゃら
ＲＰＧ
ダンジョン
絵のないドラクエ
ゲームブック
迷路自動生成
アスキーアートで絵を描く
バトルシーンのみ
マインスイーパ
シミュレーション
戦国もの？
シムシティ
シムアント
コンビニ経営
ＡＯＥ
人工生命
子育てシミュレーション
すごろく
人生ゲーム
じゃんけん
あっちむいてホイ
ＯＸゲーム
丁半
五目並べ
四目並べ
オセロ
戦略を学習するＡＩ
機械学習
知能情報っぽい話
ＧＡ
強化学習
ニューラルネットワーク
ＳＯＭ
フラクタル生成
フーリエ展開

ユーティリティソフト
メーラー
電卓
TODO管理
スケジュール帳
レシピ自動生成
カレンダー
リモコン
小遣い帳

ＷＥＢ掲示板
アクセスカウンター
数字の３の倍数をアホに変換するソフト
数値計算
数値積分
ボールの軌道をシミュレーション
方程式を解く

シューティング

知能情報学実験「信号処理」受講者へ

皆さんの中には昨年度のプログラミング演習１で習われた事を「サッパリ」お忘れの方もおられるでしょう．

もちろんそれは「よろしくない」事ですが．ファイル入出力については大体期末にならい，バタバタとして身につきにくい単元でもありますので，サンプルソースを提示しておきます．課題１で「ファイル出力」，課題２以降で「ファイル入力」を用います．

講義の内容については何はともあれ北野先生の講義情報ページをご覧下さい．

１．ファイル出力サンプルコード

たとえば，新しくdata.txtという名前のファイルを作って，そこ0～9という数字をはき出すプログラムを考えましょう．

#include <stdio.h> 
 
int main(){
 
	int i=0;
	//	①FILEでファイルポインタを宣言する．
	FILE *fp;
	//	②fopenで"w"か"r"か"a"か開くモードを指定し，ファイルを開く．
	fp =fopen("data.txt","w");//"w"はwrite：書き込みの意味です．
	for(i=0;i<10;i++){
		//③fprintfでファイルポインタ（開いたファイル）に書き込む
		fprintf(fp,"%d\n",i);
	}
	//④ファイルを閉じる．
	fclose(fp);
 
	return 0;
}
 
 
/*
	コードの実行結果
 
	プログラムのあるフォルダに"data.txt"ができ以下の
	データが出力されます．
 
	0
	1
	2
	3
	4
	5
	6
	7
	8
	9
 
*/

２．ファイル入力サンプルコード

つぎに上でつくったデータを読み込んで画面に表示するプログラムを作りましょう

#include <stdio.h>
 
int main(){
 
	int i=0;
	int a=0;
	//	①FILEでファイルポインタを宣言する．
	FILE *fp;
	//	②fopenで"r"と開くモードを指定し，ファイルを開く．
	//	このときちゃんと開くファイル（例えば）"data.txt"があることを確認
	fp =fopen("data.txt","r");//"r"はread書き込みの意味です．
	for(i=0;i<10;i++){
		//③fprintfでファイルポインタ（開いたファイル）に書き込む
		fscanf(fp,"%d",&a);//scanfとほとんど同じ文法なので"&"を忘れない．
		printf("%d,",a);
	}
	//④ファイルを閉じる．
	fclose(fp);
 
	return 0;
}
 
 
/*
	コードの実行結果
 
	プログラムのあるフォルダにある"data.txt"から整数aに
	データが読み込まれ，以下のデータがprintfによって出力されます．
	0,1,2,3,4,5,6,7,8,9,
 
*/

sin, cos, フーリエ変換使用時コンパイル時の注意

コンパイル時に -lm をつける必要があります．(math（数学）ライブラリーを使うと言う意味)

たとえば

> gcc test.c -o test -lm

のようにしないとエラーがでます．

プログラミング演習２　～第12週から第14週まで～

※ 課題１２－１の実行例では、外点が０（ゼロ）として表示されています。

本課題では、 「外点のキーは０（ゼロ）とする。」 との記述が抜けています。

つまり、外点を作成する場合、

struct node *n[10]; n[i] = new_node(0);

とする必要があります。 12-1

・print_treeの使い方

根（root）のstruct nodeのポインタをrootとすると

print_tree(root);

という形で利用する．

・とりあえず

とりあえず，教科書p.155ページを見てください．

・structの宣言

プリントにもありますが，以下の宣言がまずはじめ．

struct node{
	int key;
	structnode *parent,*left,*right;
}

・とりあえず２

構造体node型の領域を確保し，要素を代入するnew_node関数を作りましょう．．

struct node *new_node(int val)
{
    [struct node のポインタpを宣言，struct node相当のメモリ領域をmallocでわりあてる．]
 
    [pのメンバ変数keyに値valを割り当てる]
 
    [pのメンバ変数parent，left，rightにNULLを割り当てる]
 
    [strut node のポインタpを返す．]
}

といった作業をします．

これを作った後に

struct node *n; n = new_node(4);

のようにすれば値が4のノードを作れるわけです．

あとはこれと同様に配列なりで必要な数nodeのポインタ＆メモリ領域を用意し， このparent, left, rightに適切なポインタを代入していくことで木構造を作ります．