Lazarus中用TFPSList和TFPGList排序

劉華煜

摘要：排序是一個常見的操作。在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)編輯：謝媛媛】