劉華煜
摘要:排序是一個常見的操作。在Lazarus中,經(jīng)常選擇使用TFPSList和TFPGList來進行排序。
關(guān)鍵詞:Lazarus;排序;TFPSList;TFPGList
中圖分類號:TP311 ? ? ?文獻標(biāo)識碼:A
文章編號:1009-3044(2020)28-0083-03
Abstract: Sorting is a common operation. In Lazarus, TFPSList and TFPGList are often used for sorting.
Key words: Lazarus;sort; TFPSList; TFPGList
1 背景
在編程中經(jīng)常會用到排序,由于排序涉及語言層面本身,所以每種語言實現(xiàn)排序的方法各不相同。在Lazarus中,通常用TFPSList和TFPGList實現(xiàn)排序功能。
2 TFPSList和TFPGList
TFPSList實現(xiàn)的是線性表,線性表每個元素都只能以Pointer形式訪問,這樣就需要在使用元素的時候先強制類型轉(zhuǎn)換。假設(shè)要在一個TFPSList中存儲整數(shù),那么就得這樣寫代碼:
var
list: TFPSList;
k: Integer;
begin
list:=TFPSList.Create(sizeof(Integer));
k:=3;
list.Add(@k);
k:=-7;
list.Add(@k);
writeln(PInteger(list[0])^);
writeln(PInteger(list[1])^);
end;
在創(chuàng)建TFPSList時要指定元素所占字節(jié)數(shù),這樣的話才可以根據(jù)傳入的指針把元素復(fù)制到TFPSList中。加入元素的方法是調(diào)用TFPSList的Add方法,取出元素則通過下標(biāo)取出,由于通過下標(biāo)得到的是Pointer,所以需要強制轉(zhuǎn)換成指向整數(shù)的指針PInteger再進行操作。
TFPGList實現(xiàn)的也是線性表,它的元素是通過模板指定的。下面的代碼展示了如何在一個TFPGList中存儲整數(shù):
type
LI = specialize TFPGList
var
list: LI;
k: Integer;
begin
list:=LI.Create;
k:=3;
list.Add(k);
k:=-7;
list.Add(k);
writeln(list[0]);
writeln(list[1]);
end;
首先要創(chuàng)建一個數(shù)據(jù)類型,以模板形式指定TFPGList元素類型,然后通過Add方法加入元素,通過下標(biāo)取出元素。
3 用TFPSList排序
為敘述方便,假設(shè)每個數(shù)據(jù)項都由兩個整數(shù)組成:key和index,依據(jù)key來排序。
首先需要定義表達數(shù)據(jù)項的記錄以及指向它的指針:
type
KI = record
key, index: Integer;
end;
PKI = ^KI;
然后定義比較函數(shù),排序需要比較函數(shù)來確定兩個記錄哪個比較大,需要注意的是TFPSList要求比較函數(shù)是成員函數(shù),那么就需要單獨定義一個類:
coo = class
function CompFunc(k1, k2: Pointer): Integer;
end;
function coo.CompFunc(k1, k2: Pointer): Integer;
begin
Result := PKI(k1)^.key - PKI(k2)^.key;
end;
比較函數(shù)的參數(shù)是兩個指針,所以需要強制轉(zhuǎn)換成PKI再比較二者的key,函數(shù)返回值大于0,表示第一個數(shù)據(jù)大于第二個數(shù)據(jù),返回值等于0,表示兩個數(shù)據(jù)相等,返回值小于0,表示第一個數(shù)據(jù)小于第二個數(shù)據(jù)。
然后進行排序:
procedure foo;
var
list: TFPSList;
k: KI;
c: coo;
begin
list:=TFPSList.Create(sizeof(KI));
k.key := …
k.index := …
list.Add(@k);
…
list.Sort(@c.CompFunc);
Writeln(PKI(list[0])^.index);
end;
list.Sort(@c.CompFunc)執(zhí)行排序,由于用不到c的成員變量,所以用不著創(chuàng)建c對象直接調(diào)用其成員函數(shù)CompFunc。排序后PKI(list[0])^.index就是最小的數(shù)據(jù)項的index成員值。
單獨給比較函數(shù)創(chuàng)建一個類顯得不夠優(yōu)雅,如果排序本身就在一個類的成員函數(shù)里,那么可以把比較函數(shù)放入這個類中:
function TForm1.CompFunc(k1, k2: Pointer): Integer;
begin
Result := PKI(k1)^.key - PKI(k2)^.key;
end;
如果在Form1窗體里排序,那么就用不著為了排序函數(shù)單獨創(chuàng)建一個類,把比較函數(shù)作為TForm1的成員函數(shù)即可。
相應(yīng)的排序修改成:
procedure TForm1.foo;
var
list: TFPSList;
k: KI;
begin
list:=TFPSList.Create(sizeof(KI));
k.key := …
k.index := …
list.Add(@k);
…
list.Sort(@CompFunc);
Writeln(PKI(list[0])^.index);
end;
注意排序函數(shù)foo從頂層函數(shù)變成TForm1的成員函數(shù),list.Sort的參數(shù)也變成了@CompFunc。
4 用TFPGList排序
TFPGList也需要比較函數(shù),但和TFPSList不同的是,TFPGList的比較函數(shù)是頂層函數(shù):
function CompFunc(const k1, k2: KI): Integer;
begin
Result := k1.key - k2.key;
end;
TFPSList的比較函數(shù)的參數(shù)類型是指針,需要強制轉(zhuǎn)換,而TFPGList的比較函數(shù)的參數(shù)類型是數(shù)據(jù)項本身,無須強制轉(zhuǎn)換。
在TFPGList的元素是記錄的情況下,需要重載記錄的相等操作符:
type
KI = record
key, index: Integer;
class operator Equal(k1, k2: KI): Boolean;
end;
class operator KI.Equal (k1, k2: KI): Boolean;
begin
Result := k1=k2;
end;
然后進行排序:
procedure foo;
type
LKI = specialize TFPGList
var
list: LKI;
k: KI;
begin
list := LKI.Create;
k.key := …
k.index := …
list.Add(k);
…
list.Sort(@CompFunc);
Writeln(list[i].index);
end;
需要注意的是,class operator Equal函數(shù)需要預(yù)編譯指令{$mode delphi},TFPGList需要預(yù)編譯指令{$mode objfpc},而這兩個預(yù)編譯指令是互斥的,這就是說KI的定義和LKI的定義必須分別在兩個文件中,這就造成了麻煩。
如果TFPGList的元素不是記錄,而是對象,那么就無須重載相等操作符,也就不需要預(yù)編譯指令{$mode delphi},那么KI的定義和LKI的定義也就可以在一個文件中了:
type
KI = class
key, index: Integer;
end;
LKI = specialize TFPGList
比較函數(shù)不變,排序則變成下面這樣:
procedure foo;
var
list: LKI;
k: KI;
begin
list := LKI.Create;
k := KI.Create;
k.key := …
k.index := …
list.Add(k);
…
list.Sort(@CompFunc);
Writeln(list[i].index);
list[0].Free;
…
end;
既然KI的定義從記錄變成類,那么也就需要創(chuàng)建對象和銷毀對象。
同樣,如果TFPGList的元素不是記錄,而是指向記錄的指針,那么也無須重載相等操作符,KI的定義和LKI的定義也可以在一個文件中:
type
KI = record
key, index: Integer;
end;
PKI = ^KI;
LKI = specialize TFPGList
比較函數(shù)需要改一下:
function CompFunc(const k1, k2: PKI): Integer;
begin
Result := k1^.key - k2^.key;
end;
排序也要改:
procedure foo;
var
list: LKI;
i,n: Integer;
begin
list := LKI.Create;
list.Add(…);
…
list.Sort(@CompFunc);
Writeln(list[0]^.index);
end;
5 結(jié)束語
TFPSList和TFPGList都可以實現(xiàn)排序功能,從直觀性上來說,TFPGList直接用數(shù)據(jù)項作為元素最為直觀,但可惜的是如果元素是記錄類型,則需要單獨一個文件放記錄定義,在多一個文件也無所謂的情況下,這是最好的選擇,另外如果數(shù)據(jù)項只有一項數(shù)據(jù),根本無須記錄類型,那么TFPGList直接用數(shù)據(jù)項也是最好的選擇。TFPSList的最大缺點是它的元素被泛化成通用指針Pointer,必須進行強制轉(zhuǎn)換才能訪問其元素,這樣就帶來很多麻煩。TFPGList的元素是指向記錄的指針這種方法的一個缺點是必須解引用,但這還不是最大的缺點,最大的缺點是記錄本身不保存于TFPGList中,還需要讓記錄本身不要因為超出作用域而失效,在記錄本身無須維護的情況下,是一個好的選擇。TFPGList的元素是對象這種方法比較均衡,在直觀性上和TFPGList直接用數(shù)據(jù)項作為元素一樣直觀,并且因為對象保存在堆里,即使對象引用超出作用域,對象內(nèi)容也不會失效,只是可能需要排序前創(chuàng)建對象,排序后釋放對象,不過這并不麻煩,另外在對象的創(chuàng)建和釋放都無須排序本身處理的情況下,這種方法和TFPGList直接用數(shù)據(jù)項作為元素并無區(qū)別。
參考文獻:
[1] Booth J.Lazarus & Object Pascal Notebook[M].北京:機械工業(yè)出版社,2014.
[2] 徐新華.IDE和Object Pascal語言[M].北京:人民郵電出版社,1998.
[3] Knuth D E.計算機程序設(shè)計藝術(shù)(卷3):排序與查找[M].北京:機械工業(yè)出版社,2010.
【通聯(lián)編輯:謝媛媛】