TAG

首都機能移轉 (2) 歌詞 (2) 靠北文 (40) 戲言 (30) 糟糕 (7) ACG (23) Assembly (2) Boost (2) C (31) C++ (69) CMake (4) CSIE (67) Debian (34) Design_Pattern (2) Django (1) Eclipse (1) en_US (13) FFmpeg (3) FoolproofProject (26) FreeBSD (2) Git (4) GNU_Linux (65) IDE (5) Java (11) JavaScript (19) KDE (15) Khopper (16) KomiX (3) Kubuntu (18) Life (1) Lighttpd (2) Mac_OS_X (2) Opera (1) PHP (2) PicKing (2) Programing (21) Prolog (1) Python (7) QSnapshot (2) Qt (30) Qt_Jambi (1) Regular_Expression (1) Shell_Script (7) Talk (98) VirtualBox (7) Visual_Studio (13) Windows (18) zh_TW (36)

2007年7月22日 星期日

Sorting

這篇的主題主要是針對多筆資料的同時排序。
這樣說也許不太確切吧,比方說,現在有五十個人分別從1編到50號,並給每個人的身長,求以高矮順序排列的座號。
這時候該怎麼寫?
由於C的qsort和C++的sort都只能排一個一維陣列,像這種排序的同時要保留其他資訊的位置時[?],也許有人的做法是建立兩個陣列,一個放身高,另一個放座號,然後自己寫一個sorting function。
不過這樣好像有點麻煩,因為quick sort實在是很煩,bubble有夠慢,而且又有現成的函式可用,像這種問題要怎麼解決?
其實用簡單的資料結構就可以漂亮地解決。
以上述問題為例:
// C version:
typedef struct Prop
{
 double height;
 unsigned int index;
}Prop;
typedef struct Array
{
 Prop *content;
 unsigned int size;
}Array;
// C++ version:
struct Prop
{
 double height;
 unsigned int index;
};
struct Array
{
 Prop *content;
 unsigned int size;
};
先建立一個結構,內容是每個人的資料,也就是double的height[?]和unsigned int的index[?]。然後再建立一個Array的結構把它包起來。
我為什麼不直接就用Prop這個結構去建立陣列呢?其實只是我個人的喜好而已,因為與其另外再宣告一個變數放陣列目前長度,不如直接用結構把它跟陣列本身綁起來,對我來說比較好懂。
使用動態陣列存也只是我個人的喜好,各位高興也可以換成固定陣列。
由於是動態陣列,所以要先建立出陣列空間[?]
Array people;
// C version:
people.content = (Prop*)malloc( sizeof( Prop ) * people.size );
// C++ version:
people.content = new Prop[people.size];
到了這步,我假設你已把資料全部正確的放進陣列裡了。
好了,問題來了,qsort和sort都不認得這個結構的大小判斷,compiler會很直接的發給你一張好人卡,那接下來要怎麼辦?
注意到,sort其實可以放第三個argument,也就是compare function的address,而qsort則是一定要放入compare function。要動手腳的地方就在這裡。
// C version:
int compare( const void *a, const void *b )
{
 return ( ( Prop* )a )->height > ( ( Prop* )b )->height;
}
qsort( people.content, people.size, sizeof( Prop ), compare );
// C++ version:
bool compare( Prop a, Prop b )
{
 return a.height < b.height;
}
sort( people.content, people.content + people.size, compare );
也就是說,其實可以藉由自訂compare function的方式來自訂要用哪個元素排序。
注意,C的qsort和C++的sort排序的條件不同,qsort是當compare為true時做swap,sort則是當compare為false時做swap,當發現sort出來的結果怪怪的時候,請檢查compare function。
最後請記得,有多少個malloc就要有多少個free,有多少個new就要有多少個delete,有借有還,再借不難唄:P
// C version:
free( ( void* )people.content );
// C++ version:
delete[] people.content;

沒有留言:

張貼留言