記錄

數據結構

電腦科學中,記錄(英語:record)也稱為結構體struct)或複合資料compound data)是基本的資料結構,記錄是一些相關欄位的聚集,它們可由不同的資料類型組成,通常是固定的數量和序列。記錄中的每個欄位或稱為元素,但可能與集合的元素概念混淆不清。在物件導向編程中,記錄的欄位也另外被稱為成員;依照慣例和具體的程式語言,多元組有可能會被認為是一個記錄,反之亦然。

譬如將日期儲存為一個記錄,則其中包含了數字的年份,以字串表示的月份和數字的日期等欄位。而人事記錄可包含姓名,薪水和職級等欄位。一個圓形的記錄可包含圓中心點和它的半徑-在這種情況下,圓中心點本身可能表示為x和y座標的點記錄。

記錄與陣列的區別在於,它們的欄位數通常是固定的,每個欄位都有一個名稱,而且每個欄位可能有不同的類型。

一個記錄型別是描述其中欄位所具有值和變數的資料類型。大多數現代計算機語言允許開發人員自由定義新的記錄型別。記錄型別的定義將會指定每個欄位的資料類型和存取它的識別碼(名稱或標籤)。

記錄可以存在於任何儲存介質中,包括主記憶體和大容量儲存裝置,如磁帶或硬碟。記錄是大多數資料結構的基本組成部分,特別是鏈結的資料結構。

許多計算機檔案是以邏輯記錄的陣列組成的,通常被分組成更大的實體記錄或區塊以提高存取效率。

函式或程式的參數通常當作是一個記錄變數其中的欄位;而在呼叫該函式時,傳遞給它的參數可被視為將欄位的值指派給該記錄變數。此外,通常用於實現程式調用的呼叫堆疊中,每個登錄即是一條啟動記錄或呼叫框頁,包含了程式參數和局部變數,返回位址和其它內部欄位。

物件導向語言中的物件本質上是一個記錄,有如何處理該記錄的專用程式;而物件型別是對記錄類型的詳細描述。實際上在大多數物件導向語言中,記錄只是物件的特殊情況,並且被稱為普通舊資料結構(plain old data structures, PODS),與使用OO特徵的物件形成對比。

計算機的記錄可類比為數學的元組。相同地,記錄型別可看作是兩個或多個數學集合的笛卡爾積,或是以特定語言實作的抽象乘積型別。

在許多電腦語言中,都對結構有所定義:

關聯鍵

一條記錄可能有零個或多個關聯鍵。關聯鍵是以記錄其中一個或多個欄位的集合,來作為識別碼。唯一的鍵通常被稱為主鍵,或簡稱為記錄鍵。例如,員工檔案可能包含了員工編號,姓名,部門代碼和薪資,那麼員工編號在組織中應該是唯一的,並且為主鍵。依據儲存媒介和檔案結構,員工編號可被編入索引檔,另外個別地儲存能使查詢過程加速。部門代碼或許不是唯一的,它也可能被編成索引;這樣子它會被當作是次要鍵或備用鍵。如果沒有索引,則必須依序掃描整個員工檔案,以產生特定部門的所屬員工列表。薪資領域通常不被視為可用的關鍵。索引是設計資料檔時需考量的一個因素。

歷史

 
Journal sheet from 1880 United States Census, showing tabular data with rows of data, each a record corresponding to a single person.

記錄的概念可從久遠的會計使用中回溯到各種類型的表格和分類帳。現代電腦科學中的記錄形式,具有明確的類型和大小的欄位,已經隱含在19世紀機械的計算器,如巴貝奇分析機中。

 
Hollerith punched card (1895)

最初用於處理資料(與控制相反)的機器可讀媒介,是在1890年美國人口普查中用於記錄的打孔卡:每張打孔卡是單個記錄。若將1895年的打孔卡與1880年的日記帳兩相比較,記錄在20世紀上半葉成熟,大多數資料處理是用打孔卡片完成的。通常資料檔的每條記錄會記錄在一張打孔卡中,特定欄分配給特定欄位。一般地,記錄是可從外部儲存裝置(例如讀卡機,磁帶或磁碟)讀取的最小單元。

大多數機器語言實現和早期組合語言沒有記錄的特殊語法,但藉由使用索引暫存器,間接定址和自修改代碼,這個概念是可用的(並廣泛被使用)。一些早期的計算機如IBM 1620,具備了對分隔記錄和欄位的硬體支援,以及複製這些記錄的特殊指令。

一些早期的檔案排序和製表工具如IBM的報告程式生成器(Report Program Generator, RPG)中,記錄和欄位是其核心概念。

COBOL是第一個支援記錄類型並廣泛使用的程式語言,其記錄定義在當時已相當複雜。它允許以任意大小和精度的英數字、整數和小數欄位,來定義巢狀記錄,並自動格式化將值指定給紀錄的欄位(例如,插入貨幣符號,小數點和數字組分隔符)。每個檔案與讀取或寫入的資料一併關聯到一個記錄變數。 COBOL 還提供了一個MOVECORRESPONDING陳述語句,根據名稱來指派兩個記錄的相對應欄位。

早期開發用於數值計算的計算機語言,如FORTRAN(到FORTRAN IV)和Algol 60,並不支援記錄類型;但這些語言的更新版本,如Fortran 77和Algol 68增加了記錄類型。最初的Lisp程式語言也缺乏記錄(除了內建的cons單元),但它的S表達式能滿足對紀錄的需求。將記錄類型與其它基本類型完全整合邏輯上一致性的型別系統,則是Pascal程式語言。

PL/I程式語言提供了COBOL格式的記錄。C程式語言最初將記錄類型(struct)當作是置於儲存區塊之上的模板概念,而並不是真實的記錄資料類型。後來C語言提供了(以typedef宣告),但這兩個概念在語言上仍然是不同的。在Pascal之後設計的大多數語言(如 Ada,Modula 和 Java)也都支援了記錄。

記錄的操作

  • 新記錄類型的宣告,包括每個欄位的位置,型別和(可能)名稱;
  • 將變數和值聲明為已定義的記錄類型;
  • 從給定的欄位值和(有時)欄位名稱來建構一條記錄;
  • 以明確名稱來選取一條記錄的欄位;
  • 將值指定給記錄變數;
  • 比較兩條記錄的等同性;
  • 計算記錄的標準雜湊值

從記錄中選取一個欄位會產生一個值。

有些語言提供列舉記錄所有欄位的功能,或至少是參照的欄位。該功能需要實現某些服務,像是除錯器垃圾收集器序列化。它需要具備一定程度的多型

在具有記錄子類型的系統中,記錄類型的值操作還可以包括:

  • 增添新欄位到記錄,設定新欄位的值。
  • 從記錄中刪除一個欄位。

在這樣的設定中,特定的記錄類型表示目前有特定的一組欄位,但是該類型的值可能包含其它欄位。因此,具有xyz欄位的記錄將屬於具有xy欄位的記錄類型,以及具有xyr欄位的記錄。理由是將(x,y,z)記錄傳遞給某個函式,若該函式預設使用(x,y)記錄作為參數,因為該函式將在記錄中找到所需的全部欄位。實際上在程式語言中實作記錄的許多方法,若允許這樣的型別轉換會遇到麻煩,然而在理論中這個事實是記錄類型的核心特徵。

賦值與比較

大多數語言允許在完全相同類型的記錄之間進行指派(包括相同的欄位類型和名稱,以相同的順序)。
然而,依照語言的不同,兩個單獨定義的記錄類型,即使它們具有完全相同的欄位,也可能被視為不同類型。

在記錄之間,有些語言也允許對其中不同名稱的欄位進行指派,按照欄位在其記錄中的位置,將每個欄位值與相應的欄位變數進行對應;所以譬如有一複數的紀錄,其中有realimag兩個欄位,則可將兩欄位值指派給有XY欄位,表示平面上一點的記錄變數。在這種方案中,兩個操作數仍舊要求相同的欄位類型序列。

某些語言可能也要求相對應的類型,應該具有相同的大小和編碼,以便整個記錄能被指派成不解譯的位元字串。而其它語言可能在這方面更有彈性,僅要求每個值欄位可合法地指派給相應的變數欄位;所以譬如可將短整數欄位分配給長整數欄位,反之亦然。

另外的語言(例如COBOL)可藉由名稱來匹配欄位與值,而不用位置。

以上所述的功能性質同理應用在比較兩個記錄值的等同性。某些語言也允許使用根據單一欄位的字典序來進行次序的比較('<'和'>')。

PL/I允許以上兩種類型的賦值,也允許結構表達式,如a = a + 1;其中「a」是一條記錄,或是在PL/I術語中所指的結構。

ALGOL 68的欄位選取

在Algol 68中,如果Pts是一組記錄,每個都有整數欄位XY,可以寫入Pts.Y來獲得一個整數數組, 由Pts的所有元素的Y欄位組成。結果,語句Pts[3].Y:=7Pts.Y[3]:= 7將具有相同的效果。

PASCAL中的WITH陳述句

在Pascal程式語言中,使用with R do S的陳述將執行指令序列S,就像記錄R的所有欄位都被聲明 為變數一樣。 所以不必全部寫出Pt.X := 5; Pt.Y := Pt.X +3,而可以縮寫為 with Pt do begin X := 5; Y := X +3 end

在記憶體中的表現

記錄在記憶體中的表現取決於程式語言。通常,這些欄位會依照在記錄類型中宣告的相同順序,連續地儲存於記憶體中。這可能導致兩個或多個欄位儲存在相同的記憶體字組中;實際上,此功能經常用於系統編程以存取字組的特定位元。另一方面,大多數編譯器會添加開發人員看不見的填補欄位,以符合硬體要求的對齊限制 -比如浮點欄位必須補滿整個字組。

有些語言將記錄實作為位址指向欄位(可能的名稱和/或類型)的陣列。物件導向語言中的物件通常以相對複雜的方式實現,特別是在允許多重類別繼承的語言中。

自訂記錄

自訂記錄是一種類型,其中包含辨別記錄類型和記錄內定位的相關資訊。它可能包含了元素的偏移量;因此,元素可用任何次序儲存或者可省略掉次序。另外在這樣類型的記錄中,具有識別碼的各種元素可簡單地依任何次序,跟隨彼此。

範例

以下顯示記錄定義的範例:

  • PL/I:
      declare 1 date,
                2 year  picture '9999',
                2 month picture '99',
                2 day   picture '99';
    
  • C:
    struct date {
       int year;
       int month;
       int day;
    };
    
  • Rust:
    struct Date {
       year: u32,
       month: u32,
       day: u32,
    }
    

外部連結

參考