正文

在計(jì)算機(jī)科學(xué)中，資料結(jié)構(gòu)（data structure）是計(jì)算機(jī)中存儲、組織數(shù)據(jù)的方式。通常情況下，精心選擇的資料結(jié)構(gòu)可以帶來最優(yōu)算法效率的演算法。一般而言，資料結(jié)構(gòu)的選擇首先會從抽象數(shù)據(jù)類型的選擇開始。一個(gè)設(shè)計(jì)良好的資料結(jié)構(gòu)，應(yīng)該在盡可能使用較少的時(shí)間與空間資源的前提下，為各種臨界狀態(tài)下的運(yùn)行提供支持。資料結(jié)構(gòu)可通過編程語言所提供的數(shù)據(jù)類型、引用及其他操作加以實(shí)現(xiàn)。

簡介

不同種類的資料結(jié)構(gòu)適合於不同種類的應(yīng)用，而部分甚至專門用于特定的作業(yè)任務(wù)。例如，當(dāng)計(jì)算機(jī)網(wǎng)路依賴於路由表運(yùn)作時(shí)，B樹高度適用於資料庫的封裝。

在許多類型的程序設(shè)計(jì)中，選擇適當(dāng)?shù)馁Y料結(jié)構(gòu)是一個(gè)主要的考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)表明，封裝的困難程度與最終成果的質(zhì)量與表現(xiàn)，都取決於是否選擇了最優(yōu)的資料結(jié)構(gòu)。在許多時(shí)候，確定了資料結(jié)構(gòu)後便能很容易地得到演算法。而有些時(shí)候，方向則會顛倒過來：例如當(dāng)某個(gè)關(guān)鍵作業(yè)需要特定資料結(jié)構(gòu)下的演算法時(shí)，會反過來確定其所使用的資料結(jié)構(gòu)。然而，不管是哪種情況，資料結(jié)構(gòu)的選擇都是至關(guān)重要的。

系統(tǒng)構(gòu)造的關(guān)鍵因素是資料結(jié)構(gòu)而非演算法的這一深入理解，導(dǎo)致了多種形式化的設(shè)計(jì)方法與程式語言的出現(xiàn)。絕大多數(shù)的語言都帶有某種程度上的模塊化思想，通過將資料結(jié)構(gòu)的具體實(shí)現(xiàn)封裝隱藏於受限介面後方的方法，來讓不同的應(yīng)用程序能夠安全地重用這些資料結(jié)構(gòu)。C++、Java等物件導(dǎo)向的程序設(shè)計(jì)語言可使用類來完成這一功能。

因?yàn)橘Y料結(jié)構(gòu)的重要性毋庸置疑，現(xiàn)代程式語言及其運(yùn)行環(huán)境在標(biāo)準(zhǔn)庫中都包含了多種的資料結(jié)構(gòu)，例如C++標(biāo)準(zhǔn)模板庫中的容器、java集合框架以及微軟的.NET Framework。

大多數(shù)資料結(jié)構(gòu)都由數(shù)列、記錄、可辨識聯(lián)合、引用等基本類型構(gòu)成。舉例而言，可空引用（nullable reference，一種可被置空的引用）是引用與可辨識聯(lián)合的結(jié)合體，而最簡單的鏈?zhǔn)浇Y(jié)構(gòu)鏈表則是由記錄與可空引用構(gòu)成。

資料結(jié)構(gòu)意味著：一個(gè)資料結(jié)構(gòu)可被視為兩個(gè)函數(shù)之間的介面，或者是由數(shù)據(jù)類型聯(lián)合組成的存儲內(nèi)容的訪問方法封裝。