劉華煜

摘要：排序是一個(gè)常見(jiàn)的操作。在Lazarus中，經(jīng)常選擇使用TFPSList和TFPGList來(lái)進(jìn)行排序。

關(guān)鍵詞：Lazarus;排序;TFPSList;TFPGList

中圖分類號(hào)：TP311 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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)常會(huì)用到排序，由于排序涉及語(yǔ)言層面本身，所以每種語(yǔ)言實(shí)現(xiàn)排序的方法各不相同。在Lazarus中，通常用TFPSList和TFPGList實(shí)現(xiàn)排序功能。

2 TFPSList和TFPGList

TFPSList實(shí)現(xiàn)的是線性表，線性表每個(gè)元素都只能以Pointer形式訪問(wèn)，這樣就需要在使用元素的時(shí)候先強(qiáng)制類型轉(zhuǎn)換。假設(shè)要在一個(gè)TFPSList中存儲(chǔ)整數(shù)，那么就得這樣寫(xiě)代碼：

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時(shí)要指定元素所占字節(jié)數(shù)，這樣的話才可以根據(jù)傳入的指針把元素復(fù)制到TFPSList中。加入元素的方法是調(diào)用TFPSList的Add方法，取出元素則通過(guò)下標(biāo)取出，由于通過(guò)下標(biāo)得到的是Pointer，所以需要強(qiáng)制轉(zhuǎn)換成指向整數(shù)的指針PInteger再進(jìn)行操作。

TFPGList實(shí)現(xiàn)的也是線性表，它的元素是通過(guò)模板指定的。下面的代碼展示了如何在一個(gè)TFPGList中存儲(chǔ)整數(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;

首先要?jiǎng)?chuàng)建一個(gè)數(shù)據(jù)類型，以模板形式指定TFPGList元素類型，然后通過(guò)Add方法加入元素，通過(guò)下標(biāo)取出元素。

3 用TFPSList排序

為敘述方便，假設(shè)每個(gè)數(shù)據(jù)項(xiàng)都由兩個(gè)整數(shù)組成：key和index，依據(jù)key來(lái)排序。

首先需要定義表達(dá)數(shù)據(jù)項(xiàng)的記錄以及指向它的指針：

type

KI = record

key， index： Integer;

end;

PKI = ^KI;

然后定義比較函數(shù)，排序需要比較函數(shù)來(lái)確定兩個(gè)記錄哪個(gè)比較大，需要注意的是TFPSList要求比較函數(shù)是成員函數(shù)，那么就需要單獨(dú)定義一個(gè)類：

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ù)是兩個(gè)指針，所以需要強(qiáng)制轉(zhuǎn)換成PKI再比較二者的key，函數(shù)返回值大于0，表示第一個(gè)數(shù)據(jù)大于第二個(gè)數(shù)據(jù)，返回值等于0，表示兩個(gè)數(shù)據(jù)相等，返回值小于0，表示第一個(gè)數(shù)據(jù)小于第二個(gè)數(shù)據(jù)。

然后進(jìn)行排序：

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對(duì)象直接調(diào)用其成員函數(shù)CompFunc。排序后PKI（list[0]）^.index就是最小的數(shù)據(jù)項(xiàng)的index成員值。

單獨(dú)給比較函數(shù)創(chuàng)建一個(gè)類顯得不夠優(yōu)雅，如果排序本身就在一個(gè)類的成員函數(shù)里，那么可以把比較函數(shù)放入這個(gè)類中：

function TForm1.CompFunc（k1， k2： Pointer）： Integer;

begin

Result ：= PKI（k1）^.key - PKI（k2）^.key;

end;

如果在Form1窗體里排序，那么就用不著為了排序函數(shù)單獨(dú)創(chuàng)建一個(gè)類，把比較函數(shù)作為T(mén)Form1的成員函數(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ù)類型是指針，需要強(qiáng)制轉(zhuǎn)換，而TFPGList的比較函數(shù)的參數(shù)類型是數(shù)據(jù)項(xiàng)本身，無(wú)須強(qiáng)制轉(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;

然后進(jìn)行排序：

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}，而這兩個(gè)預(yù)編譯指令是互斥的，這就是說(shuō)KI的定義和LKI的定義必須分別在兩個(gè)文件中，這就造成了麻煩。

如果TFPGList的元素不是記錄，而是對(duì)象，那么就無(wú)須重載相等操作符，也就不需要預(yù)編譯指令{$mode delphi}，那么KI的定義和LKI的定義也就可以在一個(gè)文件中了：

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的定義從記錄變成類，那么也就需要?jiǎng)?chuàng)建對(duì)象和銷毀對(duì)象。

同樣，如果TFPGList的元素不是記錄，而是指向記錄的指針，那么也無(wú)須重載相等操作符，KI的定義和LKI的定義也可以在一個(gè)文件中：

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é)束語(yǔ)

TFPSList和TFPGList都可以實(shí)現(xiàn)排序功能，從直觀性上來(lái)說(shuō)，TFPGList直接用數(shù)據(jù)項(xiàng)作為元素最為直觀，但可惜的是如果元素是記錄類型，則需要單獨(dú)一個(gè)文件放記錄定義，在多一個(gè)文件也無(wú)所謂的情況下，這是最好的選擇，另外如果數(shù)據(jù)項(xiàng)只有一項(xiàng)數(shù)據(jù)，根本無(wú)須記錄類型，那么TFPGList直接用數(shù)據(jù)項(xiàng)也是最好的選擇。TFPSList的最大缺點(diǎn)是它的元素被泛化成通用指針Pointer，必須進(jìn)行強(qiáng)制轉(zhuǎn)換才能訪問(wèn)其元素，這樣就帶來(lái)很多麻煩。TFPGList的元素是指向記錄的指針這種方法的一個(gè)缺點(diǎn)是必須解引用，但這還不是最大的缺點(diǎn)，最大的缺點(diǎn)是記錄本身不保存于TFPGList中，還需要讓記錄本身不要因?yàn)槌鲎饔糜蚨?，在記錄本身無(wú)須維護(hù)的情況下，是一個(gè)好的選擇。TFPGList的元素是對(duì)象這種方法比較均衡，在直觀性上和TFPGList直接用數(shù)據(jù)項(xiàng)作為元素一樣直觀，并且因?yàn)閷?duì)象保存在堆里，即使對(duì)象引用超出作用域，對(duì)象內(nèi)容也不會(huì)失效，只是可能需要排序前創(chuàng)建對(duì)象，排序后釋放對(duì)象，不過(guò)這并不麻煩，另外在對(duì)象的創(chuàng)建和釋放都無(wú)須排序本身處理的情況下，這種方法和TFPGList直接用數(shù)據(jù)項(xiàng)作為元素并無(wú)區(qū)別。

參考文獻(xiàn)：

[1] Booth J.Lazarus & Object Pascal Notebook[M].北京：機(jī)械工業(yè)出版社，2014.

[2] 徐新華.IDE和Object Pascal語(yǔ)言[M].北京：人民郵電出版社，1998.

[3] Knuth D E.計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)（卷3）：排序與查找[M].北京：機(jī)械工業(yè)出版社，2010.

【通聯(lián)編輯：謝媛媛】