使用 C 和 C++ 的程式語言概念/資料級結構

在本章中，我們將首先定義在程式設計環境中可用的所有資料項的通用屬性，然後根據其結構和型別對資料進行分類。在這樣做的過程中，我們還將嘗試瞭解它們如何在記憶體中佈局。

一般屬性

可變性

不可變資料

常量是在其整個生命週期內保持不變的資料項。常量可以按字面使用，也可以命名。命名的常量有時被稱為符號常量或形象常量。

字面常量和命名常量。
3、'5'、.TRUE.、"String literal" 是字面常量的示例，而 const double pi = 3.141592654; 是 C++ 中將 [對] Π 作為命名常量定義的示例。

一些程式語言區分了在編譯時確定值的常量和在執行時確定值的常量。例如，在 C# 中，前者用關鍵字 const 標記，後者用 readonly 標記。在 Java 中，欄位（或區域性識別符號）的常量性用 final 關鍵字標記，而 static 修飾符的存在或不存在分別將關聯的資料項分類為編譯時常量或執行時常量。

示例：C# 中的編譯時常量。
public class Math { ... public const /* static final in Java */ double pi = 3.141592654; public const double e = 2.718281; ... }

這裡，pi 和 e（尤拉常數）的值甚至可以在程式開始執行之前確定。因此，它們被定義為常量。

請注意，如果存在任何 Math 類例項，則相同的定義對所有例項都有效。也就是說，pi 或 e 的值不會從一個例項更改為另一個例項。事實上，它們獨立於例項作為類欄位存在。換句話說，它們是 [隱式] 靜態的。在 C++ 中，與 C# 的靈感來源相同，顯式使用 static 和 const 就是這種體現。

示例：C# 中的執行時常量。
public class Citizen { ... Citizen (..., long SSNoftheNewCitizen, ...) { ... SSN = SSNoftheNewCitizen; ... } ... private readonly long SSN; /* private final long SSN in Java*/ } // end of class Citizen

這裡，SSN 的值無法在相關 Citizen 物件建立之前確定。一旦物件被建立，其 SSN 欄位在物件的生命週期內永遠不會改變。因此，我們得出結論，初始化的唯一可能位置是建構函式。此值可以作為引數提供給建構函式，也可以使用物件的和其他屬性和/或類計算得出。

觀察到此類欄位的值可能因例項而異。在我們的示例中，這是預期的行為：任何兩個 Citizen 物件必須具有不同的 SSN 值。

可變資料

變數為我們提供了命名的記憶體儲存，我們可以在程式執行過程中寫入、檢索和操作它。

變數有兩個相關聯的值

1. 它的資料值，儲存在某個記憶體地址中。這有時被稱為物件的右值（讀作“are-value”）。你可以將其理解為讀取（或右側）值。常量和變數都可以充當右值。
2. 它的地址值——也就是說，它在記憶體中的地址，其中儲存著它的資料值。這有時被稱為物件的左值（讀作“ell-value”）。你可以將其理解為位置（或左側）值。請注意，常量不能充當左值。（因為它不能出現在賦值語句的左側）。

可以透過三種方式為變數提供值

1. 在建立時進行初始化。這可以由使用者提供，也可以是語言分配的預設值。Java程式語言就是第二種方法的一個例子。
2. 透過輸入操作。
3. 透過賦值語句。

將識別符號（無論是變數、常量還是函式）與其左值相關聯的行為稱為繫結，並且可以透過兩種不同的方式建立。在識別符號和左值之間是一對一關係的情況下，繫結發生在執行時之前，因此被稱為靜態繫結。全域性變數就是一個例子，它只有一個識別符號例項。在其他情況下，當關系是一對多時，繫結發生在執行時，稱為動態繫結。區域性變數就是一個例子，每次呼叫函式時，都會為其重新分配零個或多個例項。

可見性

我們還可以談論識別符號的作用域。作用域可以定義為宣告一個識別符號有效的程式部分。具有有效宣告的識別符號被稱為在作用域內，而不在作用域內的識別符號則被稱為超出作用域。

語言的作用域規則決定了對非區域性識別符號的引用的處理方式。大多數程式語言使用一個稱為詞法或靜態作用域規則的通用規則，透過單獨檢查程式文字來確定適用於識別符號的宣告。另一種規則，稱為動態作用域規則，在執行時透過考慮當前子程式的啟用來確定適用於識別符號的宣告。

識別符號在作用域內並不意味著它是可見的。如果某個上下文中識別符號的使用將繫結到該宣告，則識別符號的宣告在該上下文中是可見的。也就是說，識別符號將與該宣告相關聯。宣告可能在其整個作用域內可見，但它也可能被其他作用域和可見性與第一個宣告重疊的宣告隱藏。

示例：C語言中的作用域和可見性。
... { int i1, i2; ... { double i1; double d; ... } /* 內部塊結束 */ ... } /* 外部塊結束 */ ...

在上面的程式碼片段中，變數（識別符號）的作用域為

i1（外部塊）、i2：從其宣告點到外部塊的末尾

i1（內部塊）、d：從其宣告點到內部塊的末尾

變數的可見性為

i2、i1（內部塊）、d：與其作用域相同

i1（外部塊）：其作用域減去內部塊

可訪問性

可訪問性約束是模組化和麵向物件語言中的一種概念，可以應用於資料。這樣做有兩個目的

1. 為了保持資料的完整性，以及
2. 為了給予實現者更改實現細節的自由。

示例：Java中的訪問約束。
public class Stack { ... private int _top; private Object[] _contents; } // Stack類結束

在上面的類定義中，將實現細節宣告為private，這意味著它們對使用者是不可訪問的，即以下語句是不允許的。

stk._top = 0; stk._contents[7] = new Integer(5);

發出第一個語句可能會導致一個非空的Stack物件看起來為空。類似地，第二個語句可能會透過在_top指示的位置以外的其他位置新增新元素來填充Stack物件，這絕對違反了堆疊的定義。

此外，這樣的定義使Stack類的實現者能夠更改實現細節。例如，她可以選擇使用Vector作為底層資料結構。現在，由於外部世界不知道這一點，因此Stack類的使用者不會受到此決定的影響。

資料類別

資料元素

最基本的資料實體是資料元素。這些資料實體可以組合在一起形成結構。

原始資料元素

原始資料元素是可以由機器語言指令直接操作的元素，主要分為數值型、字元型和邏輯型（布林型）。數值型資料元素可以進一步細分為整數和實數。

示例：C/C++中的原始資料元素。
在C/C++中，char、int、short、long和long long用於表示整數。char也可以解釋為儲存單個位元組的字元。float、double和long double表示單精度、雙精度和擴充套件精度的浮點數。bool用於表示布林值。

作為地址的資料元素

地址是一個值，它指示執行程式後建立的程序映像中的一個位置。根據它指向的程式段，地址屬於以下兩組之一。

1. 標籤實際上是程式語句的地址，是程式程式碼段中的一個地址。它也可以被認為是一個數據元素，可以透過goto操作進行操作。

2. 指標引用或指向程式碼和資料段中的其他元素。在前一種情況下，指示子程式開始的指標可用於動態呼叫子程式，從而能夠透過回撥實現多型子程式。指向資料段的指標通常引用未命名的資料元素。它們在構建動態資料結構和遞迴演算法中被大量使用。控制代碼可以被視為智慧指標，它們具有相同的用途。

複合資料元素

字元字串，通常簡稱為字串，是字元的線性序列。它們有時被認為是原始資料元素，因為它們由機器語言指令直接操作，有時被歸類為資料結構。

結構體

資料結構

資料結構是經過組織的資料元素集合，這些元素受某些允許的操作約束。資料結構在邏輯上是實體，因為它們是由程式設計師建立的，並由高階程式操作。這些可能與物理實體（即機器語言程式碼操作的儲存結構）幾乎沒有關係。

資料結構可以分類為

• 線性與非線性：線性資料結構與非線性資料結構相反，是指各個元件是有序序列的資料結構。線性資料結構的示例包括字串、陣列和列表。非線性資料結構的示例包括樹、圖和集合。
• 靜態與動態：靜態結構是指在執行過程中其大小無法改變的結構。陣列和記錄是靜態資料結構的示例。動態資料結構的示例是列表。

儲存（記憶體）結構

儲存結構是在資料結構對映到記憶體之後的資料結構。資料結構是資料的邏輯組織，而儲存結構表示在程式執行期間資料在記憶體中的物理儲存方式。

多維陣列可能的佈局。
假設您正在使用二維陣列。您的陣列，例如n乘以m，實際上並沒有在記憶體中以二維方式儲存，而是作為元素的線性序列儲存。在行主序中，陣列按以下方式儲存 A(1, 1), A(1, 2), ..., A(1, m), A(2, 1), ..., A(n, 1), A(n, 2), ..., A(n, m) 在列主序中，相同陣列在記憶體中的佈局如下 A(1, 1), A(2, 1), ..., A(n, 1), A(1, 2), ..., A(1, m), A(2, m), ..., A(n, m)

儲存可以透過兩種方式分配

• 順序：以這種方式分配的結構也可以稱為靜態結構，因為它在其整個生命週期中都無法更改。此類結構使用隱式排序：元件透過其在結構中的順序排序（索引）來排序。
• 連結：以這種方式分配的結構也可以稱為動態結構，因為資料結構可以在其生命週期中增長和縮小。它們使用顯式排序：每個元件在其自身內部包含下一個專案的地址，因此它實際上“指向”其自己的後繼。

至於每種方法的優缺點

• 在靜態結構中，整個儲存在結構的整個生命週期內都保持分配狀態。此外，為了避免溢位，在結構的宣告中使用最大理論大小。由於這些原因，靜態結構不是記憶體高效的。在動態結構中，由於指標欄位的存在，存在空間開銷。
• 由於可能發生移位（可以透過犧牲一些額外的記憶體來避免），因此除了靜態結構末尾之外，從任何位置插入和刪除都是代價高昂的。動態結構並非如此。
• 在靜態結構中可以使用索引值進行直接訪問，這意味著訪問結構中的任何項都花費恆定時間。但是，這對於動態結構無效。但是，可以透過對資料強加分層結構來緩解此弱點。

檔案結構

檔案結構指的是駐留在輔助儲存器中的資料。當程式執行終止時，檔案結構是唯一在程式終止後仍然存在的結構。

資料層次結構指的是資料的邏輯組織，這些資料可能儲存在輔助儲存或外部儲存介質（如磁帶）上。

檔案是與特定應用程式相關的相關記錄的集合。記錄是與單個處理物件相關的一組相關資料項或欄位。欄位是資料項，是包含在記錄中的資訊（資料元素或結構化資料項）。

可以訪問檔案以進行輸入、輸出、輸入/輸出和追加。它可以以兩種不同的模式處理：批處理模式、查詢模式。在批處理模式下，檔案的元件記錄按順序操作。生成班級測試結果的報告是此類處理的示例。在查詢模式下，透過直接訪問來操作單個記錄。檢索單個學生的記錄屬於此類別。

另一個重要問題是檔案在輔助儲存器上的組織方式。記錄的這種（物理）排序可以透過三種方式完成

• 順序：檔案被視為記錄的線性序列。此類檔案無法在輸入/輸出訪問模式下訪問。文字檔案是順序檔案的典型示例。
• 相對：檔案中的每個記錄都可以透過位置直接訪問。當然，只有當檔案儲存在直接訪問儲存裝置 (DASD) 上時，這種組織才成為可能。記錄中的鍵欄位與磁碟上的位置之間的對映可以透過兩種方式完成：直接對映和雜湊。
• 索引順序：這是前兩種方法之間的折衷方案。檔案按順序儲存在 DASD 上，但還有一個索引檔案，允許透過索引搜尋進行最佳的直接訪問。

必須根據以下方面評估每種檔案組織技術

• 訪問時間：查詢特定資料項所需的時間。
• 插入時間：插入新資料項所需的時間。這包括查詢插入新資料項的正確位置所需的時間以及更新索引結構所需的時間。
• 刪除時間：刪除資料項所需的時間。這包括查詢要刪除的項所需的時間以及更新索引結構所需的時間。
• 空間開銷：索引結構佔用的額外空間。

這些反過來又受三個因素的影響。系統必須首先將磁頭移動到相應的磁軌或柱面。這種磁頭移動稱為尋道，完成所需的時間為尋道時間。磁頭到達正確的磁軌後，必須等到所需的塊旋轉到讀寫磁頭下方。此延遲稱為延遲時間。最後，可以進行磁碟和主記憶體之間資料的實際傳輸。這最後部分是傳輸時間。

檔案上的典型操作包括：開啟、關閉、讀取、寫入、EOF 和維護操作，例如排序、合併、更新和備份。

資料型別

資料型別，通常簡稱為型別，由資料元素的域和作用於這些元素的操作集組成——這些操作可以構造、銷燬或修改這些資料元素的例項。

除了可以結構化為原始資料型別的內建型別外，大多數語言還具有使用者定義新資料型別的功能。[ALGOL68 和 Pascal 是首批提供此功能的程式語言。]

型別系統是定義新型別以及宣告變數為這些型別的工具。型別系統還可以具有型別檢查功能，該功能可以是靜態的或動態的，具體取決於此檢查是在編譯時還是在執行期間完成。

示例：C 的（受限）型別系統。
基本型別：char、short、int、long、float、double 型別構造器：*、[]、()、struct、union typedef char Performance[2]; typedef char* String; typedef struct { String first_name; String last_name; Performance grades; } Student; typedef void (*EVAL_PERF) (Student* Class); ...

強型別程式語言是指所有變數的型別在編譯時都確定的語言。用這種語言編寫的程式（被稱為具有靜態型別）必須顯式宣告所有程式設計師定義的詞。全域性變數和區域性變數的儲存需求在編譯期間完全確定。強型別程式語言可能包含用於定義新型別的型別機制。

在動態型別中，變數在編譯時不與型別繫結。允許變數動態型別的語言（也歸類為弱型別）可以使用動態型別檢查，這需要存在執行時例程來檢查型別並執行正確的操作，例如涉及儲存對映和程式碼選擇的那些操作。也可以說型別與值相關聯，而不是與變數相關聯。

示例：Scheme中的動態型別。
> (define x 3)↵ ; x表示型別為數字的值 > (+ x 1)↵ 4 > (number? x)↵ ; x是數字嗎？-是的。 #t > (set! x "Nermin")↵ ; x現在表示型別為字串的值 > (string-length x)↵ 6 > (number? x)↵ ; x是數字嗎？-不再是了！ #f > (string? x)↵ ; x是字串嗎？-是的。 #t >_

資料型別之間的關係

等價性

在賦值語句（以及許多其他程式設計結構）中，編譯器不僅檢查語法正確性，還測試語義有效性。例如，不允許將字串值賦給整型變數；編譯器會強制執行某種賦值相容性規則。此過程的一個重要組成部分是找出表示式和變數的型別是否等價。

這可以透過兩種不同的方式完成：結構等價和名稱等價。在前者中，如果兩種型別由相同的底層資料型別組成，則它們是等價的。

示例：偽C中的結構等價。
struct S1 { int i; double d; char c; }; struct S2 { int f1; double f2; char f3; }; S1和S2被認為是等價的。

在名稱等價中，只有當兩個型別的名稱相同時，它們才相等。這是大多數基於Algol的語言採用的方法。

示例：Pascal中的名稱等價。
type arrtype1: array [1..10] of integer; arrtype2: array [1..10] of integer; var v1, v2: arrtype1; v3: arrtype2; 在以上片段中，v1和v2具有等價的型別，而v3的型別與這些變數的型別不同。

擴充套件

如果某個型別的全部例項都可以被視為其擴充套件型別的例項，則稱該型別擴充套件另一個型別。基型別（被擴充套件的型別）被稱為擴充套件型別的泛化，而擴充套件型別被稱為其基型別的特化。

由於關係的性質，擴充套件型別的表示式與基型別變數是賦值相容的。

提供這種關係最常用的技術是繼承，它在大多數面向物件程式語言中都很常見。

實現

如果某個型別為已實現型別介面中列出的所有操作提供了實現，則稱該型別實現了另一個型別。

實現可以被視為擴充套件的一種特例，其中基型別不提供其任何操作的實現。

在許多面向物件程式語言中，這種關係存在於介面與其實現類之間。

宣告

在具有靜態型別檢查的語言中，程式必須以某種方式傳達其使用的識別符號的型別。編譯時對識別符號型別的完整了解可以提高程式效率，原因如下。

更有效的儲存分配。例如，所有整型都可以使用最大的整型型別進行類似儲存。但是，如果知道確切的型別，則不必分配最大的大小。執行時更有效的例程。A + B 的處理方式不同，具體取決於 A 和 B 是整數還是實數。編譯時檢查。在程式開始執行之前，就會發現許多程式設計結構的無效用法。

另一方面，以確保型別安全為代價，編譯器有時可能會拒絕有效的程式。

識別符號型別可以透過兩種方式傳達。

顯式型別宣告

與其他方法相比，程式設計師更傾向於使用宣告語句來告知變數、函式等的型別。一些程式語言，例如 ML 和 Haskell，不要求程式設計師為所有識別符號提供型別宣告。透過一個稱為型別推斷的過程，編譯器盡力推斷出表示式的型別。

隱式型別宣告

在（某些版本的）Fortran 和 BASIC 等語言中，變數的命名方式揭示了它的型別。

Fortran 中的隱式型別宣告。
在 FORTRAN 90 之前的 FORTRAN 版本中，以 I-N 開頭的識別符號被視為整數，而以其他任何字母開頭的識別符號被視為實數。

標量資料型別

標量資料型別的域僅由單個基本資料元素組成。

數值型別

數值型別與外部世界中的數量相關或表示數量。但是，儘管在現實生活中這些型別的域可能是無限的，但在計算機的世界中，它們的域是有限的。

數值型別。
整數、浮點數、定點數和複數。

邏輯（布林）型別

此類型別的變數只能取兩個值，true 或 false，它們可以在機器中表示為 0 和 1、零和非零。布林值上的典型運算包括and、or、not。

指標型別

指標是對物件或資料元素的引用。指標變數是一個識別符號，其值為對物件的引用。

指標對於動態分配先前未確定數量的資料非常重要。此外，它們允許相同的資料同時駐留在不同的結構中。換句話說，它們使資料共享成為可能。

指標變數指向並提供訪問未命名或匿名變數的方法。因此，指標上的操作必須區分對指標變數本身的操作和對指標指向的數量的操作。

示例：C/C++ 中的指標
int num1, num2, *pnum; ... ... pnum = &num1; num1 = 15; num2 = *pnum; ...
	第 6 行之後的記憶體佈局

pnum 在上述示例中用於訪問儲存 int 值的位置。事實上，它只能儲存對 int 的引用。這是指標和普通地址之間最重要的區別：雖然地址可用於引用任何型別的值，但指標儲存對特定資料型別的引用。然而，作為在 C 中實現泛型集合的寶貴工具，可以透過規範使用 void * 來恢復地址的型別不可知性。

在 C 中，指標被大量使用，優點可能會變成維護噩夢。以下程式就是一個例子。

示例：C 中的指標陷阱。
#include <stdio.h> int main(void) { int ch = 65; int* p2i; const int *p2ci = &ch; p2i = p2ci; /* !!! */ printf("p2ci: %i\tp2i: %i\n", *p2ci, *p2i); *p2i = ch++; /* !!! */ printf("p2ci: %i\tp2i: %i\n", *p2ci, *p2i); exit(0); } /* end of int main(void) */

當我們編譯並執行此程式時，它將產生以下輸出。

p2ci: 65 p2i: 65 p2ci: 66 p2i: 66

這違反了我們所做的約定。在第 6 行，我們保證由 p2ci 指向的位置的內容不會改變。在第 8 行，我們將 p2ci 分配給 p2i，後者是另一個允許自身更新的指標。我們隨後繼續透過非常量指標 p2i 更改該位置處的值，這意味著由 p2ci 指向的值也發生了更改。

編譯器可能會針對此錯誤發出警告，這在 GNU C 編譯器中就是這種情況。但你不能依賴這一點：並非所有編譯器都會發出警告。有時，程式設計師會關閉警告以避免閱讀煩人的訊息，並且該訊息會被忽略。

結構化資料型別

結構化資料型別的域元素本身由其他標量或結構化型別元素組成。

字串

字串是動態變化大小的資料元素的有序集合。

可以將兩個屬性與字串關聯：型別和長度。型別指的是各個元素的域，而長度指的是元素的數量。（請注意，長度和大小是兩個不同的概念。）

型別屬性通常是字元，儘管位字串也常用於實現集合。

示例：C/C++ 中的字元字串。
char *name = "Atilla";

在其他語言中，同一個字串的另一種可能的表示形式為

請注意，為長度字首保留的位元組數在不同的實現中可能會有所不同。還需要記住的一點是：ASCII 並非沒有競爭對手。替代方案包括 Unicode 和基於 ASCII 的 ISO/IEC-8859 系列編碼。在 Unicode 的情況下，每個字元在記憶體中佔用兩個位元組。

示例：在 [OLE] 自動化中使用的 BSTR 型別。
CString name = _T("Atilla"); BSTR bstrName = name.AllocSysString();

如上圖所示，BSTR 用於在可能使用不同語言編寫的元件之間交換字元字串資料。事實上，長度字首繼承自 Visual Basic，而終止空字元則來自 C。

請注意，長度字首儲存字元字串本身所佔用的位元組數，而 bstrName 識別符號實際上是指向第一個字元的指標。

字串的典型操作包括

• 連線 從較小的字串建立一個字串。
• 子字串 從另一個字串的子序列建立一個字串。
• 索引測試 用於檢查較小字串是否包含在較大字串中。它返回包含較小字串的子序列開始的索引值。
• 長度 返回字串中的元件數。
• 插入、刪除、替換 等。

陣列

陣列可以定義為一個固定大小、有序的同構資料集合。它儲存在連續的記憶體位置，這使得可以直接訪問。其固定大小使得陣列成為一個靜態結構。

在某些程式語言（如標準 Pascal）中，大小必須在編譯時已知，而在許多語言中，此大小也可以在執行時給出。但是，即使在後一種情況下，陣列的大小在其生命週期內也不會改變。

示例：標準 Pascal 中陣列的靜態特性。
program primes(input, output); const N = 1000; var a: array [1..N] of boolean; ... begin ... end
對於 N 的不同值，此 Pascal 程式碼片段必須重新編譯並執行。

示例：Oberon 中的開放陣列。
PROCEDURE SetZero (VAR v: ARRAY OF REAL); VAR j: INTEGER; BEGIN j := 0; WHILE j < LEN(v) DO v[j] := 0; INC(j) END END SetZero;

在上面的 Oberon 程式碼片段中，任何元素型別為 REAL 的實際（一維）陣列引數都與 v 相容。可以使用任何大小的一維陣列呼叫子程式。但是，一旦陣列作為引數傳遞，其大小就不能更改。

陣列的重要屬性包括元件型別、陣列的維數以及每個維度的尺寸。

陣列可以在記憶體中以兩種不同的方式表示

1. 行主序（幾乎所有主要的程式語言）
2. 列主序（FORTRAN）

為了最大程度地減少對單個數組元件的訪問時間，我們應該確保程式中變化最快的索引（即最內層迴圈變數）對應於記憶體佈局中變化最快的索引。如果忽略迴圈順序，對於大型多維陣列，虛擬記憶體效能可能會嚴重下降。

示例：Pascal 中多維陣列的使用。
var a: array [3..5, 1..2, 1..4] of integer; ... for i := 3 to 5 do for j := 1 to 2 do for k := 1 to 4 do {some processing done using a[i, j, k]}

此程式片段顯示了使用行主序表示陣列的語言的正確迴圈順序。請注意，片段中最內層迴圈變數（變化最快的變數）對應於記憶體佈局中變化最快的索引。此對應關係必須擴充套件到其他迴圈變數和索引，即第二內層迴圈變數必須對應於記憶體中變化速度第二快的索引，依此類推。

示例：Fortran 中多維陣列的使用。
DO k = 1, 4 DO j = 1, 2 DO i = 3, 5 {some processing done using a(i, j, k)} END DO END DO END DO

第二個片段給出了使用列主序表示的語言的正確迴圈順序。

需要注意的是，包含在陣列表示中的頭資訊不是標準的，並且在某些程式語言中可能會有所不同甚至消失。最顯著的例子是 Java，其中陣列的大小不用於型別檢查。這意味著可以使用陣列控制代碼來操作不同大小的陣列。

示例：Java 中陣列的型別相容性。
int[] intArray = new int[10]; ... // use intArray as an array of 10 ints intArray = new int[20]; // OK! ... // use intArray as an array of 20 ints

這起初似乎與陣列的靜態特性相矛盾。畢竟，intArray 的大小已從 10 更改為 20。並非如此！我們在前面的程式碼片段中所做的是使 intArray 指示堆中的兩個不同的陣列物件。換句話說，我們更改了陣列控制代碼，而不是陣列物件本身。

確定 Pascal 樣式陣列中元素的地址。

給定偽 Pascal 宣告 var a: array [5..10, 0..3, -2..2] of integer; 假設 a) 列主序表示和 b) 行主序表示，計算 a[7, 2, 1] 的地址。對於這兩種情況，假設 a 的基地址為 200，一個整數以四個位元組表示。 a) (10 – 5 + 1) * (3 – 0 + 1) * (1 – (-2 )) + 1 給我們 [5, 0, 1] 處的元件的順序。我們需要 (10 – 5 + 1) * (2 – 0) 來到達 [5, 2, 1]。再加 (7 – 5)，我們就到達了 [7, 2, 1]。因此，[7, 2, 1] 是第 (6 * 4 * 3 + 1) + (6 * 2) + 2 = 87 個元件。它可以在地址 200 + (87 – 1) * 4 = 544 處找到。 上述計算可以推廣如下 $order(n_{1},n_{2},n_{3},...,n_{m})=1+(n_{1}-l_{1})\sum _{i=m}^{2}{(n_{i}-l_{i})\prod _{j=1}^{i-1}{(u_{j}-l_{j}+1)}}\!$ 在基於 C 的程式語言中，下界始終取為 0，因此該公式可以簡化為 $order(n_{1},n_{2},n_{3},...,n_{m})=1+n_{1}\sum _{i=m}^{2}{n_{i}\prod _{j=1}^{i-1}{u_{j}}}\!$ 某個元件的記憶體地址如下給出： $address(n_{1},n_{2},n_{3},...,n_{m})=base+componentSizex(order(n_{1},n_{2},n_{3},...,n_{m})-1)$ b) (2 – (-2) + 1) * (3 – 0 + 1) * (7 – 5) + 1 給我們 [7, 0, -2] 處元件的順序。(2 – (-2) + 1) * (2 – 0) 更多，我們就到了 (7, 2, -2)。[7, 2, 1] 是 [7, 2, -2] 之後 (1 – (-2)) 個位置。所以，[7, 2, 1] 是第 (5 * 4 * 2 + 1) + (5 * 2) + 3 = 54 個元件。它的地址是 200 + (54 – 1) * 4 = 412。 經過推廣，我們得到 $order(n_{1},n_{2},n_{3},...,n_{m})=1+(n_{m}-l_{m})+\sum _{i=1}^{m-1}{(n_{i}-l_{i})\prod _{j=i+1}^{m}{(u_{j}-l_{j}+1)}}\!$ 對於基於 C 的程式語言，這簡化為 $order(n_{1},n_{2},n_{3},...,n_{m})=1+n_{m}+\sum _{i=1}^{m-1}{n_{i}}\prod _{j=i+1}^{m}{u_{j}}\!$

確定 C 樣式陣列中元素的地址。

給定偽 C 宣告 double a[13][10][9]; 計算 a[7][6][8] 的地址，假設 a) 列主序表示和 b) 行主序表示。對於這兩種情況，假設 a 的基地址為 200，並且 double 用 8 個位元組表示。 a) $order(n_{1},n_{2},n_{3},...,n_{m})=1+n_{1}\sum _{i=m}^{2}{n_{i}\prod _{j=1}^{i-1}{u_{j}}}\!$ $order(7,6,8)=1+7+8(13x10)+6x13=8+1040+78=1126\!$ $address(7,6,8)=200+8x(1126-1)=9200\!$ b) $order(n_{1},n_{2},n_{3},...,n_{m})=1+n_{m}\sum _{i=1}^{m-1}{n_{i}\prod _{j=i+1}^{m}{u_{j}}}\!$ $order(7,6,8)=1+8+7(10x9)+6x9=9+630+54=693\!$ $address(7,6,8)=200+8x(693-1)=5736\!$

多維陣列

對多維陣列的支援可以透過兩種方式提供：鋸齒陣列（有時稱為不規則陣列）和矩形陣列。

示例：Java 中的鋸齒陣列。
int[][] numArr = { {1, 2, 3}, {4, 5, 6, 7}, {8, 9} };

這裡我們實際上得到的是一個陣列的陣列。由於不同的陣列可能具有不同的元件數量，因此我們示例中的子陣列可以並且確實具有不同的長度。可以使用以下程式碼形成相同的陣列，該程式碼反映了 Java 中陣列的處理方式。

int[][] numArr = new int[3][]; numArr[0] = new int[3]; for (int i = 0; i < numArr[0].length; i++) numArr[0][i] = i + 1; numArr[2] = new int[2]; for (int i = 0; i < numArr[2].length; i++) numArr[2][i] = i + 8; numArr[1] = new int[4]; for (int i = 0; i < numArr[1].length; i++) numArr[1][i] = i + 4;

觀察到涉及四次陣列分配：numArr、numArr[0]、numArr[1]和numArr[2]。這些分配不需要以特定的順序進行，可以在程式碼中交錯出現。唯一的限制是子陣列不能在包含陣列之前分配。也就是說，必須先分配numArr，然後才能分配其他陣列。這使我們得出了結論，這也反映在前面給出的佈局中，即 Java 樣式的多維陣列不一定在連續的記憶體位置分配。

示例：C# 中的矩形陣列。
int[,]4 numMatrix = { {1, 2}, {3, 4}, {5, 6} };
這裡，我們有一個 3×2 的矩陣。它也保證整個矩陣在連續的記憶體位置分配。

關聯陣列

陣列索引通常是標量型別，儘管像 Perl 和 Tcl 這樣的語言透過使用雜湊提供了非標量索引。5 這種陣列稱為關聯陣列。

示例：Perl 中的關聯陣列。
$dictionary{'word'} = 'sözcük, kelime'; $grade{'Emrah'} = 90; $dictionary{'sentence'} = 'tümce, cümle';
由於運算子名稱過載功能，像 C++ 和 C# 這樣的語言透過過載下標運算子（[]）的類來合併此類功能。

示例：C# 中的關聯陣列。
HashTable dictionary = new HashTable(); ... dictionary["word"] = "sözcük, kelime"; dictionary["sentence"] = "tümce, cümle"; ... Console.Write("sentence in Turkish is {0}", dictionary["sentence"]); // 將在標準輸出上列印“sentence in Turkish is tümce, cümle”

在缺少運算子名稱過載的語言（如 Java）中，必須使用其訊息的相關類。

示例：Java 中的關聯陣列。
Map dictionary = new HashMap(); ... dictionary.put("word", "sözcük, kelime"); dictionary.put("sentence", "tümce, cümle"); ... System.out.print("Sentence in Turkish " + dictionary.get("sentence")); // 將在標準輸出上列印“sentence in Turkish is tümce, cümle”

列表

列表是廣義的、動態的、線性資料結構。列表（連結列表）是一組按順序組織的專案，就像陣列一樣。在陣列中，順序組織是隱式提供的（透過陣列中的位置）；在列表中，我們使用顯式安排，其中每個專案都是節點的一部分，該節點還包含指向下一個節點的連結。

示例：Pascal 中的連結列表。
type link = ^node; node = record key : integer; next : link end; var head : link; ...

根據連結的提供方式，我們有

• 單向連結串列：這些只為我們提供了一個前向指標，指向列表中的下一個節點。
• 雙向連結串列：這些為我們提供了兩個指標，一個指向下一個節點，一個指向列表中的前一個節點。

另一種分類是根據列表中第一個和最後一個節點的關係

• 迴圈列表：在迴圈列表中，列表中的第一個和最後一個節點透過連結連線起來。在迴圈雙向連結串列中，最後一個節點的 next 連結指向第一個節點，第一個節點的 previous 連結指向列表的最後一個節點。在迴圈單向連結串列的情況下，從第一個節點到最後一個節點沒有指標。
• 線性列表：線上性列表中，第一個和最後一個節點之間沒有連結。最後一個節點的 next 欄位和第一個節點的 previous 欄位不指向任何地方，即它們為 null。

在列表的實現中，可以使用頭節點和/或虛擬尾節點。

列表上的操作是

• 建立/銷燬操作。
• 插入：在具有特定鍵值的節點之前/之後；插入到末尾，在開頭。
• 刪除：具有特定鍵值的元件；第一個、最後一個元件。
• 搜尋：具有特定鍵值的元件。
• 空：測試列表是否為空。

一些常用的、專門的（受限的）列表形式是棧（LIFO）、佇列（FIFO）、雙端佇列（Deque）、輸出受限雙端佇列和輸入受限雙端佇列。

多列表

多列表類似於列表。唯一的區別是節點同時駐留在多個列表上。

示例：使用多列表表示稀疏矩陣的 Pascal 表示形式。
type link = ^node; node = record row_no, column_no : integer; key : integer; next_row, next_column : link end;

動態陣列

動態陣列是陣列和列表的混合體，可以在執行時增長或縮小其大小。Java 世界中稱為 Vector，C# 世界中稱為 ArrayList，動態陣列維護一個內部的、堆分配的陣列，並根據需要用更大（更小）的陣列替換它。

記錄

作為邏輯資料結構的記錄是固定大小的、有序的、可能異構的元件集合，這些元件本身可能是有結構的。它也可以稱為分層或結構化型別。記錄元件，通常稱為欄位，透過名稱而不是下標訪問。

示例：COBOL 中的記錄型別定義。
01 STUDENT-RECORD. 02 NAME. 03 FIRST-NAME PIC X(15). 03 MIDDLE-INITIAL PIC X. 03 LAST-NAME PIC X(15). 02 STUDENT-NO PIC 9(9). 02 TEST-SCORES. 03 MIDTERM PIC 9(3).99. 03 FINAL PIC 999.99. 02 ASSIGNMENTS OCCURS 5 TIMES PICTURE IS 9(3).9(2).

變體記錄

一些語言允許我們擁有記錄的不同變體。這種帶有變體的記錄稱為變體記錄。這意味著某些欄位對所有變體都是通用的，而某些欄位對每個變體都是唯一的。

示例：C語言中的變體記錄。

enum shape_tag {Circle, Square}; struct SHAPE { float area; enum shape_tag tag; union { float radius; float edge_length; }; }; typedef struct SHAPE shape; shape s; ... ... s.tag = Square; or s.tag = Circle; s.edge_length = 3.5; s.radius = 5; ... ... void print_areas(shape s) { switch (s.tag) { case Circle: printf("圓的面積：%f\n", PI * s.radius * s.radius); break; case Square: printf("正方形的面積：%f\n", s.edge_length * s.edge_length); } /* switch語句結束 */ } /* void print_areas(shape)結束 */

請注意，隨著型別擴充套件功能的引入，變體記錄現在已成為一項過時的特性。除了像C++這樣的為了與C相容而保留它的語言外，面向物件的程式語言在其工具庫中都不包含變體記錄。

變長記錄

變長記錄類似於變體記錄。在這種情況下，變體涉及重複欄位的數量。

示例：COBOL中的變長記錄。
01 CLASS. 03 NO-OF-STUDENTS PIC 99. 03 STUDENTS OCCURS 70 TIMES DEPENDING ON NO-OF-STUDENTS. 05 FIRST-NAME PIC X(15). 05 MIDDLE-INITIAL PIC X. 05 LAST-NAME PIC X(15). 05 TEST-SCORE PIC 999.99 OCCURS 3 TIMES.

一些程式語言提供元組，它們實際上是其欄位由其位置隱式命名的記錄。

示例：ML中的元組。
val t = (4, 5.0, "six");↵ val t = (4, 5.0, "six") : int * real * string #1(t);↵ val it = 4 : int #2(t);↵ val it = 5.0 : real #3(t);↵ val it = "six" : string

在檢視記錄如何在記憶體中佈局的示例之前，讓我們先看看一個相當重要的影響因素：對齊要求。

對齊要求

出於效率的原因，某些體系結構不允許資料元素從不是資料元素大小倍數的地址開始。由於這種對齊，獲取程式所需資料需要更少的記憶體訪問次數。然而，這種執行速度的提高是以佔用更多記憶體為代價的。

需要注意的是，以下示例中提供的對齊方案並非唯一方案。程式設計環境可能會以某種方式讓您更改資料對齊的方式。事實上，構建在英特爾架構之上的程式設計環境甚至可能允許您開啟和關閉對齊。

double 的對齊要求
IEEE754雙精度浮點數可以用8個位元組表示。與該規範相容並在具有如上所述對齊要求的體系結構上實現的資料型別不能從記憶體位置（例如4或6）開始。它應該從地址可被8整除的位置開始。因此，它可以從0、8、...、33272、...等位置開始。

記錄型別的對齊要求至少與具有最嚴格要求的元件一樣嚴格。記錄必須在其開始的對齊邊界上結束。

示例：記錄中的對齊。
struct S { double value; char name[10]; };
struct S { char name[10]; double value; };

請意識到陣列的對齊要求等於其元件的對齊要求。無論陣列大小是1還是一百萬位元組，其對齊要求始終相同。這是因為陣列宣告是定義多個變數的簡寫。上述程式碼段實際上應該被認為如下所示

struct S { double value; char name0, name1, name2, ..., name9; };

因此，我們結構定義的對齊要求等於value的對齊要求：8。

示例：變體記錄中的對齊要求。
type tagtype = (first, second); vtype = record f1 : integer; f2 : real; case c : tagtype of first : (f3, f4 : integer); second : (f5, f6 : real) end; var v : vtype;

如果我們將變體部分的選擇器更改為case tagtype of，我們將得到

根據體系結構的不同，這可以為每個記錄節省 4 到 8 個位元組。但它讓我們失去了型別安全。

集合

集合是一種非線性結構，包含一組無序的不同值的集合。集合上的典型操作包括插入單個元件、刪除單個元件、並集、交集、差集和成員資格。

示例：Pascal 中的集合。
type days = (sun, mon, tues, wed, thur, fri, sat); dayset = set of days var weekdays, weekend: dayset; ... begin weekdays := [mon, tues, wed, thur, fri]; weekend := [sun, sat]; ... ... end.

集合中的基本型別限制為標量型別，並且由於儲存要求；潛在成員的數量受到嚴格限制。

樹

樹是非空節點和邊的集合，滿足某些要求。節點是一個簡單的物件，包含指向其他節點的連結以及一些值；指向另一個節點的連結稱為邊。

在一棵樹中，

• 節點的前驅稱為其父節點。
• 節點的後繼稱為其子節點。
• 沒有後繼的節點稱為葉子節點。
• 沒有前驅的節點稱為根節點。
• 從根節點出發，沒有不可到達的節點。
• 根節點和某個節點之間只有一條路徑。

樹在日常生活中經常遇到。例如，許多人用家譜來追蹤他們的祖先和/或後代。事實上，許多術語都源於這種用法。另一個例子是在體育比賽的組織中。

示例：在 Pascal 中表示二叉樹。
type link = ^node; node = record info: char; left_child, right_child: link end;

圖

與樹類似，圖是節點和邊的集合。與樹不同，圖沒有根、葉、父或子的概念。節點，也稱為頂點，可以獨立存在；也就是說，它可能是不可到達的。對於某些頂點對，可能存在多條路徑將它們相互連線。

許多問題都可以用圖來自然地表達。例如，給定歐洲的航空路線圖，我們可能會對以下問題感興趣：“從伊茲密爾到聖彼得堡最快的方法是什麼？”很可能許多城市對之間有多條路徑將它們連線起來。另一個例子可以在有限狀態機中找到。

圖可以用兩種方式表示

1. 鄰接矩陣表示

一個 V×V 的布林值陣列，其中 V 是頂點的數量，如果從頂點 x 到頂點 y 存在一條邊，則 a[x, y] 設定為 true，否則設定為 false。

示例：Pascal 中的鄰接矩陣表示。
program adjmatrix (input, output); const max_no_of_vertices = 50; type matrix_type = array [1..max_no_of_vertices, 1..max_no_of_vertices] of boolean; var a: matrix_type; ... ...

2. 鄰接結構表示

在這種表示中，連線到每個頂點的所有頂點都列在該頂點的鄰接列表中。

示例：Pascal 中的鄰接結構表示，
program adjlist (input, output); const max_no_of_vertices = 100; type link = ^node; node = record v: integer; next: link end; bucket_array = array [1..max_no_of_vertices] of link; var adj: bucket_array; ... ...

雖然鄰接矩陣對於稠密圖是更好的選擇，但對於稀疏圖，鄰接結構表示法成為更可行的解決方案。

使用者定義型別

除了增強程式文字的可讀性和清晰度之外，定義使用者定義型別還可以使我們能夠一次構建複雜的資料結構，然後根據需要建立任意多個該型別的例項（變數），其次，還可以利用語言自身的型別檢查功能進行輸入資料驗證，例如範圍或一致性檢查。

使用者定義型別有兩種形式

1. 列舉型別

列舉型別允許程式設計師列舉型別的域。域值在一個宣告語句中列出。

示例：C++ 中的列舉型別
在 C++ 中，我們可以使用以下方式：
const int input = 1; const int output = 2; const int append = 3; ... bool open_file(string file_name, int open_mode); ... if (open_file("SalesReport", append)) ...
我們也可以使用以下方式：
enum open_modes {input = 1, output, append}; ... bool open_file(string file_name, open_modes om); ... if (open_file("SalesReport", input)) ...

2. 子型別

子型別是將域指定為另一個已存在型別的子範圍。

示例：Pascal 中的子型別。
type ShoeSizeType = 35..46; var ShoeSize : ShoeSizeType;
有了這些宣告，我們就不能將任何超出範圍的值賦給ShoeSize變數。任何此類嘗試都將被型別系統捕獲，並導致程式因錯誤而終止。[在支援異常的程式語言中，這可以透過不終止程式的方式更優雅地處理。]

請注意，列舉和子型別定義不允許程式設計師為新定義的資料型別指定操作。

抽象資料型別

抽象資料型別 (ADT) 的定義特徵是，資料結構和在其上操作的演算法的定義之外的任何內容都不應該引用內部的任何內容，除非透過函式和過程呼叫來執行基本操作。

示例：Pascal 中的棧實現，

type link = ^node; node = record key: integer; next: link end; var head, z: link; procedure stackinit; begin new(head); new(z); head^.next := z; z^.next := z end; procedure push(v: integer); var t: link; begin new(t); t^.key := v; t^.next := head^.next; head^.next : = t end; function pop: integer; var t: link; begin t := head^.next; pop := t^.key; head^.next := t^.next; dispose(t) end; function peek: integer; begin peek := t^.key; end function stackempty: boolean; begin stackempty := (head^.next = z) end;

上面這段 Pascal 程式碼片段不幸不是 ADT 的理想實現。記錄定義的欄位可以被隨意操作；沒有語言結構可以禁止透過更改其元件來直接更改底層結構。程式設計師也可以使用任何子程式，無論是用於匯出的子程式還是用於實現某些輔助功能的子程式。缺少一種機制來提供對子程式和記錄欄位的受控訪問，例如面向物件程式語言中提供的訪問說明符。

將相關的子程式組織到一個編譯單元中不是由語言強制執行的。可以新增與正在實現的 ADT 無關的子程式。沒有編譯器強制的規則將預先存在的和/或新新增的子程式與相關的 ADT 聯絡起來。我們能做的最好的事情就是堅持約定，以便更好地組織我們的程式。

另一個缺點，一個可以很容易解決的缺點，是前面的程式碼片段無法建立多個棧。

我們需要的是類似於模組化程式語言中的模組構造或面向物件程式語言中的類構造的東西。

示例：Ada83 中的棧實現。
程式包 Stack_Package 是 型別 Stack_Type 是 私有; 過程 Init(Stack: 輸入輸出 Stack_Type); 過程 Push (Stack: 輸入輸出 Stack_Type; Item: 輸入 整數); 函式 Pop (Stack: 輸入輸出 Stack_Type) 返回 整數; 函式 Peek (Stack: 輸入 Stack_Type) 返回 整數; 函式 Empty (Stack: 輸入 Stack_Type) 返回 布林; 私有 Stack_Size: 常量 整數 := 10; 型別 Integer_List_Type 是 陣列 (1..Stack_Size) 的 整數; 型別 Stack_Type 是 記錄 Top: 整數 範圍 0..Stack_Size; Elements: Integer_List_Type; 結束記錄; 結束 Stack_Package; 程式包 主體 Stack_Package 是 過程 Init (Stack: 輸入輸出 Stack_Type) 是 開始 Stack.Top := 0; 結束 Init; 過程 Push (Stack: 輸入輸出 Stack_Type; Item: 輸入 整數) 是 開始 Stack.Top := Stack.Top + 1; Stack.Elements (Stack.Top) := Item; 結束 Push; 函式 Pop (Stack: 輸入輸出 Stack_Type) 返回 整數 是 Item: 整數 := Stack.Elements (Stack.Top); 開始 Stack.Top := Stack.Top – 1; 返回 Item; 結束 Pop; 函式 Peek (Stack: 輸入 Stack_Type) 返回 整數 是 開始 返回 Stack.Elements(Stack.Top); 結束 Peek; 函式 Empty (Stack: 輸入 Stack_Type) 返回 布林 是 開始 如果 Stack.Top = 0 那麼 返回 真; 否則 返回 假; 結束 Empty; 結束 Stack_Package;
使用此實現，讀取十個整數並以相反順序列印它們的程式可以如下實現。
使用 Basic_IO, Stack_Package; 過程 Reverse_Integers 是 x: 整數; St: Stack_Package.Stack_Type; 開始 Stack_Package.Init(St); 為了 i 在 1..10 迴圈 Basic_IO.Get(x); Stack_Package.Push(St, x); 結束 迴圈; 為了 i 在 1..10 迴圈 x := Stack_Package.Pop(St); Basic_IO.Put(x); Basic_IO.New_Line; 結束 迴圈; 結束 Reverse_Integers;

以上實現比之前的實現好得多：操作堆疊的唯一方法是透過在其上定義的操作。ADT 的表示被宣告為屬於包的私有部分。這當然是對第一個示例的一個重大改進。但是，它仍然要求使用者在兩個單獨的步驟中執行建立和初始化，這是一個相當容易出錯的過程。如果我們忘記呼叫初始化例程會怎樣？

這種方法的另一個問題是缺乏適應性。一旦定義，使用者無法更改其行為，除非修改其定義。這有時可能非常限制。考慮在圖形系統中定義形狀型別。儘管形狀在許多方面可能有所不同，但某些操作可以應用於所有形狀，例如繪製、旋轉、平移等。起初，我們可能會想出一箇中心例程，在其中呼叫特定形狀型別的相應繪製例程。非面向物件程式語言的典型實現如下所示

enum kind { circle, triangle, rectangle }; class Shape { // 所有形狀的共有屬性 kind k; ... public: // 所有形狀的共有介面 void draw(void); void rotate(int degree); ... }; void Shape::draw(void) { switch(k) { case circle: // 繪製圓形 break; case triangle: // 繪製三角形 break; case rectangle: // 繪製矩形 break; default: error(...); } // switch(k) 結束 } // void Shape::draw(void) 結束 void Shape::rotate(int howManyDegrees) { switch(k) { case circle: // 旋轉圓形 break; case triangle: // 旋轉三角形 break; case rectangle: // 旋轉矩形 break; default: error(…); } // switch(k) 結束 } // void Shape::rotate(int) 結束

前面解決方案的一個弱點是，核心函式draw和rotate必須瞭解所有不同型別的形狀。如果定義了一個新的形狀，則必須檢查對形狀的每個操作並可能進行修改。事實上，除非你擁有原始碼，否則你甚至無法向系統新增新的形狀。而通常情況下，當你只是一個類的使用者時，你並不具備這樣的許可權。因此，實現者面臨著一個兩難境地：要麼釋出缺少形狀的實現，要麼無限期地推遲釋出，直到你確保擁有所有可能形狀的詳盡列表。理想情況下，你希望儘早釋出你的軟體，並使其儘可能地功能完善。這被稱為開閉原則。但是，當你的時間有限，並且對備選方案瞭解不多時，你如何才能提供詳盡的功能呢？答案是讓使用者擴充套件你的軟體，關鍵詞是繼承。在C++中，你會提供以下解決方案

class Shape { // 所有形狀的共有屬性。沒有用於儲存型別的屬性！ ... public: // 所有形狀的共有介面 virtual void draw(void); virtual void rotate(int degree); ... } // class Shape 結束 class Circle : public Shape { // Circle 的特有屬性。 ... public: void draw(void) { /* draw 的圓形特有實現 */ } void rotate(int degree) { /* rotate 的圓形特有實現 */ } ... } // class Circle 結束 class Triangle : public Shape { // Triangle 的特有屬性。 ... public: void draw(void) { /* draw 的三角形特有實現 */ } void rotate(int degree) { /* rotate 的三角形特有實現 */ } ... } // class Triangle 結束 class NewShape : public Shape { // 新形狀的特有屬性。 ... public: void draw(void) { /* draw 的新形狀特有實現 */ } void rotate(int degree) { /* rotate 的新形狀特有實現 */ } ... } // class NewShape 結束

除了上述優點外，編譯器控制整個過程，而在之前的情況下，是使用者在做所有簿記工作。