あわわ。〆切明日だ

というかほとんど今日だ。
成人式やら同窓会やらと、情報特別演習とかいう授業のレポートが終わらなくてカツカツでついぞさっきやっと終わらせた。

〆切が朝10時な課題。
むしろ前日〆切、って言ってくれた方が助かるというね。
10時とか気づいたらオーバーしてるべ。

ということで、今回も課題をといてみてみた。

とりあえず課題を確認。

メモした記憶があるのに残ってなかった。何故。
友人に尋ねてどうにか判明。

課題31 : 引数を重複を削除して表示する。
%./a.out a ab abc ab abc
a
ab
abc
と言った感じカナ。出力の順番は問わない。

課題32 : 引数を多い順から5個表示する。
%./a.out a b c d e f b c d e f c d e f d e f e f
f
e
d
c
b
と言った感じカナ。

課題33 : 引数を(バケットソートを使って)多い順に表示する。
%./a.out a b c d e f b c d e f c d e f d e f e f
f
e
d
c
b
a
と言った感じカナ。各引数の出現数は16回を上限とする。

ではではGoGo!!

リストを使った課題でございます。
こんな(↓)構造体を使います。

struct node {
	char* data;
	struct node* next;
};

まぁ、細かいとこは別に一緒でなくてもいいけど。
これだと毎回毎回"struct node"って書かないといけんのでめんどい。
ので

typedef struct node {
	char* data;
	struct node* next;
} node;

とかやっておけば"node"だけでおっけ。

で、リストを使う基本をいくつか。

まず、リストは頭付きリスト*1が便利。
リストだけを単純に使うより、先頭に「無意味な」アイテムを一個作るだけで実装が数段らくになる。
で、まぁ、先頭をfirstとか名前にしておいて、最初はnextをNULLにしておく。

node first;
first.next = NULL

みたいな感じで。(firstをポインタで宣言した場合は"first->next"を使うべし。

で、ループは基本こんな感じで。

node* p;
for( p = first.next; p != NULL; p ) {
	/* pに対してなにか処理 */
}

とか、

あと挿入。

p = (node*)malloc( sizeof( node ) );
p->next = first.next;
p->data = hoge;
first.next = p;

みたいな感じで。
順番とか気にしなくていい場合はfirst使って先頭に打ち込むと便利。
末尾に挿入は走査しないといけんし、直前の要素を記憶させとかなあかんし(順方向の場合は)、色々面倒。
ちなみにfirstとか用意しないと、最初の一個は特別に処理しないといけなかったりとかする。

で、各課題毎のアプローチ。

課題31

簡単な実装は多分

• for( i = 1; i < argc; i++ )でargvをみていく。
• argv[i]に対して、リストにあるかどうかをチェック!!
  • あったらスルー(リストに追加しない
  • なかったらリストに追加(リストのnodeを新しく作る。

という感じカナ。

多分20行ちょい。

リストにある/ないの判断はフラグ一個用意してもいいけど、ループを終えた後のpをチェックすると便利。

for( p = first.next; p != NULL; p ) {
	if( strcmp( ... ) == 0 ) {
		break;
	}
}

の様な場合、ループを向けた直後のpは
探したいデータが見つかった場合には、そのnodeへのポイントが、
見つからなかったらNULLが、
入っていることになるので、リストにある/ないは"p == NULL"が使える。

課題32

多い順に5個をもってこなならんのでやや面倒。
さきの31の課題をちょいちょいと変更していくといいカモ。

とりあえず多い順に、ってことなので出現数をしらべないといけない。
ということで、構造体に"count"とか加えるといい感じ。

typedef struct node {
	char* data;
	struct node* next;
	int count;
} node;

で、変数増やしても数えなきゃ意味が無いので、↑の「あったらスルー」の部分でカウントアップするようにする。
ループ抜けた直後のpがちょうど探してる要素へのポインタなので利用するとよし。
あとうっかり間違いが多いのは、nodeを作成する際に"p->count = 0;"としてしまうこと。
countは1で初期化しましょう。

で、数えられたら↑から5個もってくるだけ。
一番安直で簡単なのは、

• "for( p = first.next; p != NULL; p = p->next )"でリスト全体を眺めて最大値を持ってくる
• 最大のやつのcountを0で上書きしてしまう。

を5回繰り返す方法。
効率は悪いかもしれんが楽だし、とくに問題があるわけでもないのでよいとしましょう。

課題33

ソート。
それもバケットソート。
オーダーがO(N)という夢のソートバケットソート。
「クイック」ソートなんかよりもよっぽど速いのさ。爆速。爆速。

ということで、前半は↑の課題32と同じでおっけー。
数を数えます。
で、全部の出現個数が別ったところでバケットソート。

出現回数の上限が16と決められてるので16個のバケツを用意すればおっけーです(正確には15個。「0回出現」は「無い」ので
ただ、数字のバケットソートと違ってそう安易に実装できないのが難点。
リスト用に用意したnodeをそのまま使うと良い感じ。(というかバケツの中もリストになるので。

node buckets[ 16 ];	//16個の頭
/* 頭の初期化をこの辺に書く。 */
for( p = first.next; p != NUL; p = p->next ) {
	node* pp = (node*)malloc( sizeof( node ) );	//新しいノードを作って
	pp->data = p->data;
	pp->count = p->count;
	pp->next = buckets[ pp->count ].next;		//バケツに打ち込む。
	buckets[ p->count ].next = pp;
}

みたいな感じでやっていけばいいのカナ?
実際に提出したのとは別の方法で書いてるんで、正しいかどうかわからんというね(ぉぃ
コンパイラにも通してないし。まぁ、こんな雰囲気で。

まぁ、毎度のごとく、これ意味アンのか?てきなエントリですが...ではでは

*1:頭付きリスト : ググっても「そんな単語はねぇ」みたいなこと言われる...正式名称は何?