Pascal 程式設計/集合

本章介紹了一種新的自定義資料型別。集合是基本結構化資料型別之一。在程式設計中，您會經常發現某些邏輯可以用集合來建模。學習和掌握集合的使用是一項關鍵技能，因為您將在 Pascal 中經常遇到它們。

基礎

概念

集合是（可能為空的）可區分物件的聚合。集合要麼包含某個物件，要麼不包含。物件作為集合的一部分也被稱為該集合的元素。

假設我們知道物件“蘋果”、“香蕉”和“鉛筆”。集合 Fruit ≔ {“蘋果”, “香蕉”} 包含物件“蘋果”和“香蕉”。“鉛筆”不是 Fruit 集合的成員。

數字化

當計算機需要儲存和處理集合時，它實際上處理的是一系列Boolean值。 每一個Boolean值告訴我們某個元素是否屬於集合。

計算機也儲存一個Boolean值，用於每個不屬於特定集合的物件。

Pascal 中的集合

計算機需要知道它需要保留多少個Boolean值。為了實現這一點，Pascal 中的集合需要一個序數型別作為集合的基型別。序數型別始終具有有限的允許離散值的範圍，因此計算機預先知道要保留多少個Boolean值，我們最多可以期望一個集合包含多少個元素。因此，有效的集合type宣告是

type
	characters = set of char;

資料型別characters的變數只能包含char值。例如，這個集合不能包含42，它是一個integer值，這些資訊也不會以任何方式儲存。

集合在與列舉資料型別結合使用時特別有用，您剛在上一章中學習了列舉資料型別。讓我們考慮一個 Pascal 中的例子

program setDemo;

type
	skill = (cooking, cleaning, driving, videogames, eating);
	skills = set of skill;

var
	slob: skills;
begin
	slob := [videogames, eating];
end.

在這裡，我們聲明瞭一個變數slob，它表示skill列舉資料型別值的集合。在倒數第二行，我們用兩個物件videogames和eating填充了我們的集合slob。方括號表示集合字面量。 [videogames, eating] 是一個集合表示式，我們將其賦值給slob變數。

集合變數slob不包含其他物件。但是，計算機仍然為該集合的每個潛在成員儲存五個Boolean值。數字五是skill（集合的基型別）中的元素數量。資訊cooking、cleaning和driving不屬於集合slob，是顯式儲存的（透過適當的Boolean值false）。

檢查集合

如果我們想了解某個物件是否屬於集合，集合運算子in將產生計算機用來儲存該資訊的相應Boolean值。

program setInspection(output);
type
	skill = (cooking, cleaning, driving, videogames, eating);
	skills = set of skill;
var
	slob: skills;
begin
	slob := [videogames, eating];
	
	if videogames in slob then
	begin
		writeLn('Is she a level 45 dungeon master?');
	end;
end.

in運算子是 Pascal 的非交換運算子之一。這意味著您不能交換運算元。在RHS上，您始終需要編寫一個計算為set值的表示式，而LHS必須是一個計算為該集合基型別的表示式。

儘管我們作為人類可以說42 in slob是錯誤的，即false，但這種比較是非法的。根據定義，slob集合只能包含skill值。

操作

到目前為止，集合可能看起來像是使用Boolean值的非常複雜的方式。集合的真正強大之處在於它的一系列不同操作，使集合成為處理兩個或多個單獨（但相關）Boolean值的更簡單，因此更好的替代方案。

組合

在 Pascal 中，兩個相同型別（相同資料型別）的集合可以組合形成一個新的相同型別集合。以下運算子可用

Pascal 中的集合運算子

名稱	數學符號	原始碼符號
並集	∪	+
差集	∖	-
交集	∩	*
對稱差集	△	><†

_{^† 對稱差集運算子僅在 EP 中定義。}

並集

在韋恩圖中，兩個圓圈分別代表屬於任一集合或兩個集合的（正）物件數量。紅色區域表示並集的結果。

將兩個集合合併成一個集合的結果稱為並集。例如，最近我們的懶人學會了開車，現在也開車了。這可以寫成

slob := slob + [driving];

現在，slob 包含它之前包含的所有物件，加上另一個集合中的所有物件，[driving]。

差集

差集作為韋恩圖：右圓“減去”左圓

當然，可以使用差集運算子從集合中刪除一組元素，在原始碼中，寫成 -。

slob := slob - [];

這將從第一個集合中刪除第二個集合中存在的所有物件。這裡，空集 ([]) 不包含任何物件，因此刪除沒有物件實際上對 slob 沒有影響。

交集

交集作為韋恩圖：重疊區域（如果有）用紅色表示，代表交集

此外，您可以對集合進行交集運算。兩個集合的交集定義為這兩個運算元都包含的元素的集合。

program intersectionDemo;
type
	skill = (cooking, cleaning, driving, videogames, eating);
	skills = set of skill;
var
	slob, blueCollar, common: skills;
begin
	blueCollar := [cooking, cleaning, driving, eating];
	slob := [driving, videogames, eating];
	
	common := blueCollar * slob;
end.

集合 common 現在（僅）包含 driving 和 eating，因為這些是兩個運算元、兩個給定集合中成員的物件。

對稱差集

對稱差集作為韋恩圖

與交集結果相反的是對稱差集。它是運算元的並集，不包括兩個集合中都包含的元素。

unique := blueCollar >< slob;

現在 unique 是 [cooking, cleaning, videogames]，因為這些是任一集合中的值，但不是兩個集合中都包含的值。

比較

可以透過檢視兩個集合中的每個元素來比較兩個相同型別的集合（相同的資料型別）。

Pascal 中集合的比較運算子

名稱	數學符號	原始碼符號
相等	=	=
不相等	≠	<>
包含	⊆	<=
包含	⊇	>=
元素	∈	in

與以前一樣，所有比較運算子都計算為 Boolean 表示式。

包含

兩個集合的包含意味著一個集合包含的所有物件都存在於另一個集合中。如果表示式 A <= B 計算結果為 true，則集合 A 中存在的所有物件也存在於 B 中。在韋恩圖中，您會注意到一個圓圈的面積完全被另一個圓圈包圍，如果不是與另一個圓圈相同的話。

關於空集的表示式始終為真，儘管沒有物件需要檢查。表示式 [] <= someSet 始終計算結果為 true，無論 someSet 的值是什麼（它甚至可能是另一個空集）。

相等和不相等

兩個集合的相等定義為 A <= B and B <= A。左邊的集合中包含的所有物件都存在於右邊的集合中，反之亦然。換句話說，不存在只存在於一個集合中的單個物件。不相等只是其否定。

元素

in 運算子是唯一一個不作用於兩個集合而是作用於一個潛在的集合成員候選者和一個集合的集合運算子。它已在上面介紹。關於韋恩圖，您可以說 in 運算子“就像”用食指指向圓圈內或圓圈外的某個點。

預定義的集合例程

基數

（在初始化之後）任何時候，集合都包含一定數量的元素。在數學中，作為集合一部分的物件的數量稱為基數。可以使用函式 card（一個 EP 擴充套件）檢索集合的基數。

emptySet := [];
writeLn(card(emptySet));

這將列印 0，因為空集中沒有元素。

不幸的是，並非所有編譯器都實現了 card 函式。 FPC 沒有。 GPC 確實提供了一個。

全集

最初，Wirth 提出了一個函式 all

all(T)

是型別 T 的所有值的集合

例如

superwoman := all(skill);

集合 superwoman 將包含所有可用的 skill 值，cooking，cleaning，driving，videogames，eating。

不幸的是，這個提議從未進入 ISO 標準，FPC 或 GPC 也不支援該功能，或提供等效功能。唯一的替代方法是使用適當的集合建構函式（EP 擴充套件）：[cooking..eating] 等效於 all(skill)，前提是 cooking 是第一個 skill，而 eating 是最後一個 skill 值（指的是這些專案在 skill 資料型別宣告期間的列出順序）。

包含和排除

雖然沒有標準化，但很方便的是 BP 對 include 和 exclude 過程的定義。這些是針對非常頻繁的集合操作的簡寫。

這些過程允許您快速從一個集合中新增或刪除一個物件。

include(recognizedLetters, 'Z');

與以下相同

recognizedLetters := recognizedLetters + ['Z'];

但您不需要兩次鍵入集合名稱以及其他所有內容，從而減少了鍵入錯誤的可能性。同樣地，

exclude(primeSieve, 4);

將執行與以下相同的操作

primeSieve := primeSieve - [4];

FPC 和 GPC 都支援這些方便的例程，這些例程實際上在所有情況下都作為編譯器內在函式實現，而不是實際的 procedure。

中間用法

集合文字

有效地宣告集合是在處理集合時一項必備技能。重要的是要理解，集合僅儲存一個物件是否屬於一個集合的資訊。集合 ['A', 'A', 'A'] 與 ['A'] 相同。多次指定 'A' 不會使其“更多”地成為該集合的一部分。

此外，沒有必要以任何特定順序列出所有成員。['X', 'Z', 'Y'] 與 ['X', 'Y', 'Z'] 一樣是可以接受的。從數學角度講，集合是無序的。 Pascal 的要求 是集合的基本資料型別必須是序數型別，這純粹是一個技術要求。但是，出於可讀性的原因，通常將元素按升序排列是有意義的。

EP 標準為您提供了 set 文字的簡潔表示法，其中包含一系列連續的值。與其編寫 [7, 8, 9, 11, 12, 13]，您也可以編寫範圍，例如 [7..9, 11..13]，其計算結果與上述值相同。當然，所有數字也可以是變數，或者更一般地說是表示式。

集合文字始終是關於哪些物件存在於集合中的肯定陳述。如果我們想要一個集合，其中包含 integer 值，範圍為 0 到 10，不包括 3，5 和 7，但不想完全寫出這個集合（即，作為 [0, 1, 2, 4, 6, 8, 9, 10]），您可以編寫 [0..2, 4, 6, 8..10] 或表示式 [0..10] - [3, 5, 7]。後者可能更容易理解哪些物件存在於最終集合中，而哪些物件不存在。

記憶體限制

雖然 set of integer 是合法的，並且符合所有 Pascal 標準，但許多編譯器不支援這種大型集合。根據定義，一個 set of integer 可以包含（最多）範圍內所有值 -maxInt..maxInt。這是一個很大的數字（嘗試 writeLn(maxInt) 或閱讀您的編譯器文件以瞭解該值）。在 64 位平臺上，該值（通常）為 2⁶³−1，即 9,223,372,036,854,775,808。截至 2020 年，許多計算機如果嘗試儲存這麼多 Boolean 值，將很快耗盡主記憶體。

因此，BP 限制了允許的集合基本型別。在 BP 中，基本型別最大和最小值的序數值必須在範圍內 0..255。值 255 是 2⁸−1。截至 3.2.0 版，FPC 設定了相同的限制。

GPC 允許定義超過 2⁸ 個元素的 set，儘管需要進行一些配置：您需要指定 ‑‑setlimit 命令列引數或在原始碼中使用經過專門設計的註釋

program largeSetDemo;
{$setLimit=2147483647} // this is 2³¹ − 1
type
	// 1073741823 is 2³⁰ − 1
	characteristicInteger = -1073741823..1073741823;
	integers = set of characteristicInteger;
var
	manyManyIntegers: integers;
begin
	manyManyIntegers := [];
	include(manyManyIntegers, 1073741823);
end.

這將指示 GPC set of characteristicInteger 只能儲存最多這麼多 characteristicInteger 值。

迴圈

既然您已經瞭解了列舉資料型別和集合，您將面臨著處理越來越多的資料。Pascal 與許多其他程式語言一樣，支援一種稱為*迴圈*的語言結構。

特徵

迴圈是（可能為空的）語句序列，根據Boolean值，一遍又一遍地重複，甚至從未執行。語句序列稱為*迴圈體*。*迴圈頭*包含（可能隱式）一個Boolean表示式，用於確定是否執行迴圈體。每次執行迴圈體時，都進行一次*迭代*。

*迴圈*一詞起源於早期的計算機模型，這些模型需要透過穿孔紙帶輸入（“載入”）程式。如果該紙帶的一部分需要多次處理，則將該部分紙帶剪斷、彎曲並暫時固定，形成一個*物理迴圈*。值得慶幸的是，計算機技術的進步使處理重複程式碼變得更加方便。

Pascal（以及許多其他程式語言）區分兩種迴圈組

• 計數迴圈，此處介紹，以及
• 條件迴圈，將在後面的章節中介紹。

計數迴圈的共同點是，在執行第一次迭代之前，只需評估迴圈頭，就可以確定迴圈體將執行*多少次*。另一方面，條件迴圈是基於中止條件，即一個Boolean表示式。除了無限迴圈之外，沒有辦法提前確定條件迴圈將執行多少次（多少次迭代），除非徹底（數學地）分析迴圈體和迴圈頭，甚至可能考慮迴圈之外的情況。

計數迴圈

計數迴圈並不一定*計數*一個數量。它們之所以得名，是因為它們使用一個變數，一個*計數變數*。這個任何序數資料型別的變數（實際上）為每次迭代分配一個數字。

計數迴圈由保留字for引入。

program forLoopDemo(output);
var
	i: integer;
begin
	for i := 1 to 10 do // loop head
	begin               // ┐
		writeLn(i:3);   // ┝ loop body
	end;                // ┘
end.

在for之後，緊跟一個專門設計的對計數變數的賦值。

計數變數的範圍

1 to 10（使用輔助保留字to）表示計數變數i在執行迴圈體時將採用的值的*範圍*。 1 和 10 都是具有計數變數資料型別的*表示式*，這意味著也可能出現變數或更復雜的表示式，而不僅僅是如所示的常量文字。

此範圍*類似於*一個set。它可能為空：範圍5 to 4是一個*空*範圍，因為在 5*到*幷包括 4之間沒有值。因此，計數變數不會從該空範圍分配任何值，因為根本沒有可用的值，並且迴圈體*永遠不會*執行。但是，範圍8 to 8恰好包含一個值，即 8。

在第一次迭代期間，相應的計數變數（此處為 i）將具有給定範圍內的第一個值，即*起始值*，在上面的示例中，這是值 1。在隨後的迭代中，變數 i 的值為 2，依此類推，直到幷包括給定範圍內的*最終值*，此處為 10。

計數變數的不可變性

在迴圈體內部不需要實際使用計數變數，但如果您*僅*獲取其當前值，則可以*使用*它：在for迴圈的迴圈體內部，禁止對計數變數賦值。禁止的賦值包括但不限於將計數變數置於:=的LHS，還包括read/readLn，它們不能使用計數變數。篡改計數變數是被禁止的，因為迴圈頭將有效地使用succ(i) 來獲取下一次迭代的值。迴圈頭*隱式*包含Boolean表示式 計數變數 ≠ 最終值。如果計數變數 被操縱，則此條件*可能*永遠不會滿足，從而破壞了for迴圈的特性。透過阻止程式設計師進行任何賦值，可以預先確保不會意外或故意建立這樣的無限迴圈。

反向

Pascal 還允許使用保留字downto（而不是to）以反向方向使用for迴圈。

program downtoDemo(output);
var
	c: char;
begin
	for c := 'Z' downto 'B' do
	begin
		write(c, ' ');
	end;
	writeLn('A');
end.

此處，範圍是'Z'*向下*幷包括到 'B'。迴圈的終止條件仍然是 計數變數 ≠ 最終值，但在這種情況下，計數變數 c 在每次迭代結束時（迴圈體執行完畢後）變為 pred(c)（而不是 succ）。

集合上的迴圈

EP 允許迭代離散聚合，例如集合。如果您有一個需要應用於聚合的每個值的例程，這將特別有用。以下是一個示例，用於演示該原理。

program forInDemo(output);
var
	c: char;
	vowels: set of char;
begin
	vowels := ['A', 'E', 'I', 'O', 'U'];
	
	for c in vowels do
	begin
		writeLn(c);
	end;
end.

現在您又看到了單詞in，但在這種情況下，c in vowels 不是一個表示式。in 的資料型別限制仍然有效：在RHS 上，給出了一個聚合表示式，而在LHS 上，在這種情況下，是一個*變數*，它具有聚合的資料型別。這個變數將在每次處理迭代時被分配從給定聚合中得到的每個值。

由於RHS 只需要一個*表示式*，而不是一個變數，因此您可以進一步縮短示例。

    for c in ['A', 'E', 'I', 'O', 'U'] do

請注意，與上面的計數迴圈不同，您不應該對迴圈變數被分配值的順序做出任何假設。它可能是按升序、降序或完全混合的“順序”，但具體順序是“實現定義的”，即它取決於使用的編譯器。編譯器的附帶文件解釋了for … in 迴圈 的處理順序。

任務

集合表示式fruit - fruit 計算結果是什麼值？

此表示式將評估為一個空集，因為差運算子會從前一個集合中“移除”後一個集合包含的所有物件。這裡，我們兩次引用同一個集合，所以兩個運算元相等，實際上將表示式簡化為“移除同一個集合中的所有物件”。不用說，寫出這樣的表示式毫無意義，因為我們已經知道它的結果，但它仍然是允許的。

來源

備註