星期六, 1月 19, 2008

錯覺


剛剛把書架上的書都拿下來,才發現,原來學校的書架也蠻大的XD

---
為什麼以前一直覺得很小XD

HashTable - 以簡單的STL實作之

嗯,我還是覺得用template比較好,畢竟可以完全把事情抽象化是一件很有趣的事,在這一次的程式中簡單的使用到functor和template partial specialization(用在產生hash value)上,參考了不少書只能寫出這樣子的程式,甚感慚愧,事實上寫這個程式我只是想回復使用template的手感,不過感到的最可惜的是下面這個程式碼

template<class T, class EV>
ostream& operator<< (ostream& out, HashTable<T, EV> rhs){
for(unsigned int i=0; i<rhs.u.size(); ++i){
copy(rhs.u[i].begin(), rhs.u[i].end(), ostream_iterator(out, " "));
out << endl;
}
return out;
}


code

應該有辦法避開這個for loop,使用STL應該有辦法的才是,只能說自己能力不足,這個寒假可以好好玩一下

---
我還是玩心很重XD

hashtable的簡單實作

讓我們談談如何實作一個簡單的hashtable

嗯,剛好我最近在複習怎麼玩C++的STL,也有學弟問,我想可以討論一下hashtable怎麼使用C++實作。由於學弟妹皆沒有template的概念(這是很可惜的一點),所以我們就不用template啦。

首先,我們大概說明一下hashtable,大概需要怎麼樣的資料結構

  • hashtable(廢話XD)
  • linked-list
  • dynamic array
以這一次學弟妹問到的bookmark為例,如果我們要做一個hashTable,那麼我們會希望有一個array,來儲存整個hashTable,所以我們會寫如下的程式碼
class bookmark_hashtable{
public:
bookmark_hashtable(int s);
/* ... */
private:
int _size;
bookmark_linklist* u;
};

bookmark_hashtable::bookmark_hashtable(int s=57){
/*
* 當決定整個array的size之後,隨之動態分配一個新的linkedlist array
* 每一個array element 皆為 linkedlist,而array index即是自己需
* 產生的hash value。
*/
_size = make_next_prime(s); // int make_next_prime(int num)並未定義,自行撰寫XD
u = new bookmark_linklist[_size];
}

bookmark_hashtable::~bookmark_hashTable(){
/*
* 當object life time end,記得delete dynamic array
*/
delete [] u;
}


這時候就興起一個疑問了,bookmark_linklist從那裡來,呃,基本上第一份作業有關url的實作,稍做改變即可,不過基本架構如下。
struct bookmark{
/* ... */
};

struct bookmark_node{
bookmark data;
bookmark_node* prev, next;
};

class bookmark_linklist{
public:
/* ... */
private:
/* ... */
bookmark_node* start;
};


那麼我們還需要做什麼? hashTable的架構已經完成了,接下來就只有增加功能,如果bookmark_linklist的功能寫的足夠,bookmark_hashtable應該都能直接支援。例如說

void bookmark_linklist::add_data(bookmark data){
/* ... */
}

/* 如果bookmark_linklist::add_data已實作之則我們可以寫 */
void bookmakr_hashtable::add_data(bookmark data){
int index = hash_value(data);
u[index].add_data(data);
}


匆促之下臨時寫成,有問題歡迎多多討論XD

---
還是有template比較好玩XD
08/01/19 05:58PM 聽說很多學弟妹對linked-list不熟,我想起來我以前寫過XD

星期五, 1月 18, 2008

計畫

寒假計畫好像很簡單,就三本書吧XD

  • Introduction to Algorithm 2/e
  • Computer Orgranization and Design: the hardware and software interface 3/e
  • C++ Primer 4/e 中文版(基本上是當故事書看,如果寒假拿的到的話XD)


就這樣,希望能開一連串的連載嘍XD

---
希望不要跳票 XD

星期四, 1月 17, 2008

寒假

開始啦,不過很多事情尚未確定,預計的計畫都是讀書,所以暫緩po出XD

星期二, 1月 15, 2008

以後再說

看到學弟妹的版上說一個學期五次作業很多...? 我自己試程式的次都遠遠超過

---
算了,考完再說...Orz

星期一, 1月 14, 2008

早晨

其實現在也不算早了,只是剛好這是期末考前的空檔XD 天氣轉冷的當下,其實很怕自己睡過頭XD

有時候仔細想想,每個人總是會有想把自己的事做好的時候,有人做好了,有人做不好,心有餘力而不足的事其實常發生,對我而言,其實這算不了什麼,我有些科目可以high pass,有些科目可以被當掉,我可以玩VHDL玩到整夜沒睡,我也有翻到書就掛點的記錄。

學生的最大好處就是,學校允許學生犯錯,但是不代表可以一直犯錯XD,應該是說,當我們在做多種嘗試時,可以由於很多因素犯了錯誤,進而學習,到了社會,可能就沒這個好處了。所以在我們當學生時,記得多嘗試,多學習,多接觸不同的人群,我覺得這樣子還蠻有趣的。

事實上PageRank升到1我還蠻高興的(看清楚,我沒有廣告XD),因為總覺得很平凡的自己,可以因為這個blog認識更多的朋友,從以前到現在,我還蠻喜歡抽學伴的(交了女朋友之後也是XD),因為我從他人身上,看到不同的人生(我只是愛聊天XD),不然我怎麼可能知道,政大無熱水XDDD。

有時候常常在想,我做的跟資工無關耶,我要不要改行當張老師算了XD DJ也不錯,還是,無業遊民每天嘴炮 XD

就算閒聊一下嘍XD

---
早起會讓心情好一點~