明けましておめでとうございます。
今年は技術は二の次にして英語力の向上を目指したい、・・・と思っている。
今日は正月なので珍しく朝から呑んでいた。
年賀状を買いに行こうと思ったときに、飲酒運転する奴がいるかもしれないから気を付けないとな、と言ったのがよかった。
妻のつっこみがなければ危うく飲酒運転するところだった。
冬休みは子どもと遊んで、子どもが昼寝の時間に横で一緒に昼寝したり技術書読んだり。
おいしいもの食べたり。散歩したり。
昨年は慌ただしかったこともあり、こういうゆったりした時間が大変幸せである。
明日は北海道から取り寄せたカニだ!
/////////////////////////////////
データ構造とアルゴリズムを勉強中。
僕は物理学科出身で情報工学について学校で体系的に学んだことがない。
独学だとありがちなことだが、ところどころ基礎がごっそり抜け落ちていたりする。
そのひとつがデータ構造とアルゴリズム。
競技プログラミングの問題解いてみて、自分の知識不足を実感したので勉強を始めた。
押入れにいい本がなかったかなーと探してみると発見。
「Cをさらに理解しながら学ぶデータ構造とアルゴリズム」。
記憶に残っていないが、古本屋で買い込んできたものらしい。
一度も開いた憶えがない。妻に叱られるな。
学部2年生程度に向けて書かれたもので読みやすい。
C言語の復習の部分も多いのでその部分は飛ばす。
具体的には1〜4章はCを知っている人には退屈なので飛ばす。
第5章は配列要素の探索。線形探索と二分探索が紹介されているがこれは知っていたので飛ばす。
p28コラムの番兵はどこかで見た覚えがあるが一応抑えておく。
6〜8章は再び退屈な部分なので飛ばす。
9章はスタック。これも知っているので飛ばす。
10章はソート。全てを知っているわけではないが基本的には自分で実装することはないと思うのでとりあえず飛ばす。
11章はリスト構造とキュー。
リスト構造についてはあまり詳しく知らないので少し真面目に読む。
リスト構造はポインタで構造体(オブジェクト)を鎖状につないだものだ。オブジェクトは次のような感じ。
template <class Value_t> class Data
{
public:
Value_t v;
Data *next;
};
nextに次のデータのアドレスを代入する。
容易に想像がつくことだが、データの挿入や削除が効率よく出来そうだ。
挿入や削除したいところの周りのData *nextをいじればいいだけだから。
配列で同じことをしようとするとデータを全て少しずつずらさなければならない。
ただ、配列と違って添字番号でデータにアクセスすることが出来ない。
ポインタを辿って目的のデータを探すしかない。
練習としてリスト構造でキューを実装してみた。
あくまでリスト構造の雰囲気を知るためなので完成度は低い。バグもあるかも。
#include <iostream>
template <class data_t> class queue_data
{
public:
queue_data(data_t data)
{
this->next = NULL;
this->data = data;
}
data_t data;
queue_data *next;
};
template <class data_t> class queue
{
private:
queue_data<data_t> *root;
public:
queue();
void push(queue_data<data_t> *p);
queue_data<data_t>* pop();
};
template <class data_t> queue<data_t>::queue()
{
this->root = NULL;
}
template <class data_t> void queue<data_t>::push(queue_data<data_t> *p)
{
if(root==NULL)
{
root = p;
root->next = NULL;
}
else
{
queue_data<data_t> *tmp = root;
while(tmp->next!=NULL)
{
tmp = tmp->next;
}
tmp->next = p;
}
}
template <class data_t> queue_data<data_t>* queue<data_t>::pop()
{
if(root!=NULL)
{
queue_data<data_t> *ret = root;
this->root = root->next;
return ret;
}
else
{
return NULL;
}
}
int main()
{
queue<int> Q;
queue_data<int> qd(0);
queue_data<int> qd2(1);
queue_data<int> qd3(2);
Q.push(&qd);
Q.push(&qd2);
Q.push(&qd3);
for(int i=0;i<3;i++)
{
std::cout << Q.pop()->data << std::endl;
}
return 0;
}
次はこれをちょっと改造してプライオリティキューを実装したい。