數據結構

什麼是數據結構

數據結構是一種具有一定邏輯關係,在電腦中應用某種存儲結構,並且封裝了相應操作的數據元素的集合。它包含三方面的內容,邏輯關係、存儲關係以及操作。

數據結構的內容

一般而言,數據結構的選擇首先會從抽象數據類型的選擇開始。一個設計良好的數據結構,應該在儘可能使用較少的時間與空間資源的前提下,為各種臨界狀態下的運行提供支持。數據結構可通過編程語言所提供的數據類型、引用及其他操作加以實現。

不同種類的數據結構適合於不同種類的應用,而部分甚至專門用於特定的作業任務。例如,當電腦網路依賴於路由表運作時,B樹高度適用於資料庫的封裝。

在許多類型的程式設計中,選擇適當的數據結構是一個主要的考慮因素。許多大型系統的構造經驗表明,封裝的困難程度與最終成果的質量與表現,都取決於是否選擇了最優的數據結構。在許多時候,確定了數據結構後便能很容易地得到演算法。而有些時候,思路則會顛倒過來:例如當某個關鍵作業需要特定數據結構下的演算法時,會反過來確定其所使用的數據結構。然而,不管是哪種情況,數據結構的選擇都是至關重要的。

系統構造的關鍵因素是數據結構而非演算法的這一深入理解,導致了多種形式化的設計方法與編程語言的出現。絕大多數的語言都帶有某種程度上的模塊化思想,通過將數據結構的具體實現封裝隱藏於受限介面之後的方法,來讓不同的應用程式能夠安全地重用這些數據結構。C++、Java、Python等面向對象的編程語言可使用類來完成這一功能。

因為數據結構的重要性毋庸置疑,現代編程語言及其運行環境在標準庫中都包含了多種數據結構,例如C++標準模板庫中的容器、Java集合框架以及微軟的.NETFramework。

大多數數據結構都由數列、記錄、可辨識聯合、引用等基本類型構成。舉例而言,可空引用(nullablereference,一種可被置空的引用)是引用與可辨識聯合的結合體,而最簡單的鏈式結構鏈表則是由記錄與可空引用構成。

數據結構意味著介面或封裝:一個數據結構可被視為兩個函數之間的介面,或者是由數據類型聯合組成的存儲內容的訪問方法封裝。

數據結構的設計

應用數據結構解決生活中的問題的首要前提是研究應用什麼數據結構解決生活中的問題。其分析步驟為:首先分析任務中的操作對象,即找出任務中涉及到的數據,從中總結和抽象出操作對象,並且分析操作對象之間的邏輯關係;其次根據任務中對操作對象的操作,研究應用何種存儲方式來存儲數據才能高效的執行程式並且占用較小的存儲空間。選擇數據結構的介面要最接近軟體的需求。通常當有多個滿足需要的介面數據結構實現時,可以根據比較他們的介面操作的運行時間以及數據結構消耗的空間來進行選擇,有的時候時間和空間可以相互轉換,比如可以用空間來交換操作的效率;最後在物理存儲方式的基礎上設計正確的演算法實現操作,完成任務。

生活中所要處理的數據之間可以抽象出來不同的邏輯關係,建立不同的數據結構,但是針對實際問題要從中選取能夠準確描述問題的基本特性並且易於實現的邏輯結構。例如八枚硬幣中其中有一枚硬幣是較為輕的,要求用一個天平將這枚輕的硬幣判斷出來,判斷的過程採用將硬幣分析兩組或者三組,分別使用天平比較的方式來判斷。這一判斷過程可以用一個樹形圖來表示,所以可以將該問題抽象為判定樹,構建樹形結構。

根據選定的數據結構可以用不同的存儲結構來實現。不同類型的數據結構常用的存儲結構為順序存儲結構、鏈式存儲結構、散列存儲結構及索引存儲結構。不同的存儲結構具有不同的特點,大致上存在的差異在存儲空間和運算效率兩個方面。例如線性表的順序存儲結構與鏈式存儲結構在存儲空間上來對比,鏈式存儲結構顯然要多占用一部分存儲空間。從運算效率上來對比,如果線性表需要進行大量的插入和刪除操作的話,那麼鏈式存儲結構從執行效率上來講要占有優勢。而如果線性表要反覆進行查詢操作的話,順序存儲結構具備隨機讀寫的特點,就比較適合這種情況。

確定數據的邏輯關係與存儲結構的情況下,可以設計出不同的演算法來實現應用。設計的演算法應該是正確的演算法。正確的演算法的含義是:能夠解決實際問題,輸入的所有可能的合法的輸入都能產生預期的正確的結果;能夠在有窮的步驟內執行完程式;能夠用最簡短的語句最高效的完成任務。

Close Menu
Translate »

×

 立即聯繫 0800-070-131 全台服務

Malcare WordPress Security