算法可以理解為壹個完整的解題步驟,由基本運算和指定的運算順序組成。或者是根據需求設計的有限精確的計算序列,這樣的步驟和序列可以解決壹類問題。
壹個算法應該具有以下五個重要特征:
1,有限性:壹個算法必須保證在有限步數後結束;
2.精確:算法的每壹步都必須有精確的定義;
3.輸入:壹個算法有0個或多個輸入來描述操作對象的初始情況。所謂0輸入是指算法本身排除了初始條件;
4.輸出:壹個算法有壹個或多個輸出來反映處理輸入數據的結果。壹個沒有輸出的算法是沒有意義的;
5.可行性:原則上算法能準確運行,人用紙筆做有限次數的運算後就能完成。
計算機科學家郭瑞華·沃斯曾經寫過壹本名著《數據結構十大算法=程序》,可見算法在計算機科學和計算機應用中的地位。
數據結構是計算機存儲和組織數據的方式。數據結構是指相互之間具有壹種或多種特定關系的數據元素的集合。通常,精心選擇的數據結構可以帶來更高的操作或存儲效率。數據結構通常與有效的檢索算法和索引技術有關。
壹般認為,數據結構是由數據元素按照某種邏輯聯系組織起來的。數據元素之間邏輯關系的描述稱為數據的邏輯結構;數據必須存儲在計算機中,數據的存儲結構就是數據結構及其在計算機中的表現形式;此外,同時討論數據結構和對這種數據執行的操作是有意義的。
在許多類型的程序設計中,數據結構的選擇是壹個基本的設計考慮。許多大型系統的建設經驗表明,系統實現的難度和系統建設的質量很大程度上取決於是否選擇了最優的數據結構。很多時候,數據結構確定之後,算法就很容易得到了。有時候事情會反過來,我們根據特定的算法選擇數據結構來適應。無論是哪種情況,選擇合適的數據結構都是非常重要的。
當數據結構選定後,算法也就確定了。系統構建的關鍵因素是數據而不是算法。這種洞察力導致了許多軟件設計方法和編程語言的出現,面向對象編程語言就是其中之壹。
在計算機科學中,數據結構是研究計算機的操作對象(數據元素)及其在非數值計算編程問題中的關系和操作,並保證這些操作後得到的新結構仍然是原來的結構類型的壹門學科。
“數據結構”作為壹門獨立的課程,在國外是從1968才建立起來的。1968年,美國的Don O 'Knut教授開創了數據結構的最初體系。《計算機編程技巧》第壹卷《基本算法》是第壹本系統闡述數據的邏輯結構、存儲結構和運算的書籍。《數據結構》是計算機專業的壹門綜合性專業基礎課。數據結構是數學、計算機硬件和計算機軟件之間的壹門核心課程。數據結構的內容不僅是壹般編程(尤其是非數值編程)的基礎,也是設計和實現編譯器、操作系統、數據庫系統等系統程序的重要基礎。
計算機是壹門用計算機研究信息表示和處理的科學。這裏涉及兩個問題:
信息的表示
信息處理
信息的表示和分組與處理信息的程序的效率直接相關。隨著計算機的普及,信息量的增加和信息範圍的擴大,許多系統程序和應用程序規模龐大,結構相當復雜。因此,要想寫出壹個“好”的程序,就必須分析要處理的對象的特點以及它們之間的關系,這是數據結構課程要研究的問題。眾所周知,計算機程序是處理信息的。大多數情況下,這些信息並不是無組織的,信息(數據)之間往往存在著重要的結構關系,這就是數據結構的內容。數據的結構直接影響算法的選擇和效率。
計算機在解決壹個具體問題時,壹般需要經過以下幾個步驟:首先從具體問題中抽象出壹個合適的數學模型,然後設計求解這個數學模型的算法,最後編寫程序,進行測試和調整,直到得到最終的解。求數學模型的本質是分析問題,從中提取運算對象,找出這些運算對象之間的關系,然後用數學語言描述出來。計算機算法與數據的結構密切相關,所有的算法都依附於特定的數據結構,而數據結構直接關系到算法的選擇和效率。操作由計算機完成,需要設計相應的插入、刪除和修改算法。換句話說,數據結構還需要給出每個結構類型定義的各種運算的算法。
數據是客觀事物的符號化表示。在計算機科學中,它是指可以輸入計算機並由計算機程序處理的所有符號。
數據元素是數據的基本單位,在計算機程序中通常被認為是壹個整體。壹個數據元素由幾個數據項組成。數據項是最小的不可分割的數據單位。數據元素有兩種:壹種是不可分的原子數據元素,如整數“5”和字符“n”;另壹種是由多個基金組成的數據元素,每個基金稱為壹個數據項。例如,描述學生信息的數據元素可以由以下六個數據項組成。出生日期可以由“年”、“月”、“日”三個數據項組成,作為組合項稱為“出生日期”,其他不可分的數據項為原子項。
關鍵字是指可以識別壹個或多個數據元素的數據項。如果能起到獨特的識別作用,則稱為“壹級”關鍵詞,否則稱為“二級”關鍵詞。
數據對象是具有相同性質的數據元素和數據子集的集合。數據對象可以是有限的,也可以是無限的。
數據處理是指對數據進行查找、插入、刪除、合並、排序、計數和簡單計算的操作過程。在早期,計算機主要用於科學和工程計算。80年代以後,計算機主要用於數據處理。據有關統計,現在計算機用於數據處理的時間比例達到80%以上。隨著時間的推移和計算機應用的進壹步普及,計算機用於數據處理的時間比例必將進壹步增加。
數據結構是指同壹數據元素類中數據元素之間的關系。數據結構是邏輯結構、存儲結構(物理結構)和數據操作。數據的邏輯結構是對數據之間關系的描述,有時邏輯結構簡稱為數據結構。邏輯結構在形式上定義為(k,r)(或(d,s)),其中k是數據元素的有限集,r是k上的關系的有限集。
數據元素之間的關系稱為結構。有四種基本結構:集合、線性結構、樹型結構和圖型結構(網絡結構)。樹形結構和圖形結構都稱為非線性結構。集合結構中的數據元素除了屬於同壹類型之外,沒有其他關系。線性結構中元素之間是壹對壹的關系,樹形結構中元素之間是壹對多的關系,圖形結構中元素之間是多對多的關系。在圖形結構中,每個節點的前任節點和後續節點的數量可以是任意倍數。
數據結構在計算機中的表示(圖像)稱為數據的物理(存儲)結構。它包括數據元素的表示和關系的表示。數據元素之間的關系有兩種不同的表示:順序映射和非順序映射,從而得到兩種不同的存儲結構:順序存儲結構和鏈式存儲結構。順序存儲法:將邏輯上相鄰的節點存儲在物理上相鄰的存儲單元中,節點之間的邏輯關系由存儲單元的相鄰關系來反映,由此產生的存儲表示稱為順序存儲結構。順序存儲結構是壹種基本的存儲表示方法,在編程語言中通常是通過數組來實現的。鏈接存儲法:不要求邏輯相鄰的節點物理相鄰,節點之間的邏輯關系用附加的指針字段來表示。由此產生的存儲表示稱為鏈式存儲結構,在編程語言中通常通過指針類型來實現。索引存儲方式:除了存儲節點信息外,還建立了壹個額外的索引表來標識節點的地址。哈希存儲方式:根據節點的關鍵字直接計算節點的存儲地址。
在數據結構中,邏輯上(邏輯結構:數據元素之間的邏輯關系),數據結構可分為線性結構和非線性結構。線性表的順序存儲結構是隨機存取存儲結構,線性表的鏈式存儲結構是順序存取存儲結構。如果線性表用鏈式存儲表示,那麽所有節點之間的存儲單元地址可以是連續的,也可以是不連續的。邏輯結構與數據元素本身包含的形式、內容、相對位置和節點數量無關。
算法的設計取決於數據(邏輯)結構,而算法的實現取決於采用的存儲結構。數據的操作是定義在數據邏輯結構上的操作算法,如檢索、插入、刪除、更新等。