一、資料結構
1、概念：資料結構是指相互之間存在一種或多種特定關系的資料元素的集合。它主要描述的是用計算機存盤和組織資料的方式。資料結構又分為邏輯結構、（存盤）物理結構和資料的運算三個部分。
2、瑞士著名計算機科學家尼古拉斯.沃思（Niklaus.Wirth）提出了“演算法+資料結構=程式”的觀點，說明了資料結構的重要性。而是否能夠熟練地選擇和設計各種業務邏輯的資料結構和演算法是區分程式設計人員水平高低的一個重要標志。因此，學好資料結構的目的是能使學生更快地撰寫出更高效的程式。
3、資料結構中的邏輯結構包括了以下四種結構：
（1）線性結構：資料元素之間存在著一對一的線性關系；除了第一個和最后一個資料元素之外，其余每個資料元素都只有一個前驅和一個后繼資料元素。
（2）樹形結構：資料元素之間存在著一對多的層次關系；除了根結點外，其余每個資料元素都只有一個前驅資料元素，以及零個或若干個后繼資料元素。
（3）圖（網）狀結構：資料元素之間存在著多對多的任意關系；每個資料元素可有零個或若干個前驅資料元素和零個或若干個后繼資料元素。
（4）集合：資料元素之間除了“同屬于一個集合”的相互關系外，就沒有其他關系了。
4、資料結構中的（存盤）物理結構指的是資料的邏輯結構在計算機中的存盤形式。它分為
（1）順序存盤結構：是把資料元素按順序存放在一組存盤地址連續的存盤單元里，它的資料元素之間的邏輯關系和物理關系是一致的。
（2）鏈式存盤結構：是把資料元素存放在任意的存盤單元里，它的存盤地址可為連續，也可以是不連續的；它的資料元素之間的物理關系不能夠反映邏輯關系，所以要用指標來表示資料元素之間的邏輯關系。
5、資料結構中的邏輯結構和（存盤）物理結構是密切相關的，任何一個演算法的設計都是取決于選定的資料邏輯結構的，而演算法的實作卻是依賴于所采用的存盤結構的。
二、演算法
1、演算法是解決問題的方法，是程式設計的精髓，程式設計的實質就是構造解決問題的演算法。演算法的設計取決于資料的邏輯結構，演算法的實作取決于資料的物理存盤結構。
2、概念：演算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。
3、演算法具有以下五個重要特性：
（1）有窮性：是指一個演算法應包含有限個操作步驟，而且這個演算法在執行若干個步驟之后還能夠自動結束而不是出現無限回圈，并且每一步都在有限時間內完成。
（2）確定性：是指演算法中的每一步都必須有確切的含義，不能產生二義性。
（3）可行性：是指演算法中的每一個步驟都應該是能有效地執行，并得到確定的結果。
（4）輸入：是指在演算法執行時，從外界取得必要的資料。計算機運行程式的目的是為了進行資料處理，在大多數情況下，這些資料需要通過輸入得到。有些情況下，資料已經包含在演算法中，演算法執行時不需要任何資料，所以一個演算法可以有零個或多個輸入。
（5）輸出：是指一個演算法至少有一個或多個輸出，這是演算法進行資料處理后的結果。沒有輸出的演算法是毫無意義的。
正是演算法的這些特性，約束了程式設計人員正確地書寫演算法，并使之能夠正確無誤地執行，從而達到了求解問題的預期效果。
4、演算法設計的好壞關乎程式的執行效率，演算法的設計必須滿足下列四個要求：
（1）正確性。正確性的含義是演算法對于一切合法的輸入資料都能夠得出滿足要求的結果。但事實上要驗證演算法的正確性是極為困難的，因為通常情況下合法的輸入資料量太大，用窮舉法逐一驗證是不現實的。所謂的演算法正確性是指演算法達到了測驗要求。
（2）可讀性。演算法的可讀性是指人對演算法閱讀理解的難易程度。可讀性高的演算法便于交流，有利于演算法的除錯和修改。通常增加演算法的可讀性是在書寫演算法時采用按縮進格式書寫、分模塊書寫等方法。
（3）健壯性。對于非法的輸入資料，演算法能給出相應的回應，而不是產生不可預料的后果。
（4）效率與低存盤量需求。效率指的是演算法的執行時間；對于解決同一問題的多個演算法，執行時間短的演算法效率高。存盤量需求指演算法執行程序中所需要的最大存盤空間；存盤量需求越小的演算法效率越高。
5、演算法的效率包括時間與空間兩個方面，分別稱為時間復雜度和空間復雜度。
6、演算法的時間復雜度就是演算法的時間度量，隨問題規模n的增大，演算法的執行時間的增長率和f（n）的增長率相同，稱作演算法的漸進時間復雜度，簡稱為時間復雜度，記作T(n)=O(f(n))。其中，執行次數 T(n) 是關于問題規模 n 的函式，f（n）是問題規模n的某個函式。
7、可用演算法中陳述句的執行次數來度量一個演算法的效率。
8、陳述句頻度是指陳述句在一個演算法中重復執行的次數。
9、演算法的時間復雜度越低，效率越高。演算法的時間復雜度從小到大依次排序為：O(1)常數階、O(log2n)對數階、O(n)線性階、O(nlog2n)、O(n2)平方階、O(n3)立方階、O(2n)指數階。
10、演算法的空間復雜度是作為演算法所需存盤空間的量度，記做S(n) = O (f(n))。其中，n為問題的規模；f（n）為陳述句關于n的所占存盤空間的函式。注意：
（1）一般情況下，一個程式在機器上運行時，除了需要存盤程式本身的指令、常數、變數和輸入資料以外，還需要存盤一些對資料進行操作的輔助存盤空間。
（2）其中對于輸入資料所占的具體存盤量只取決于問題本身，和演算法無關，這樣只需要分析該演算法在實作時所需的輔助空間單元數即可。
（3）若演算法執行時所需的輔助空間相對于輸入資料量而言是個常量，則稱此演算法為原地作業，空間復雜度為O(1)。
（4）因為演算法的執行時間和存盤空間的耗費是一對矛盾體，即演算法執行的高效通常是以增加存盤空間為代價的，反之亦然。
（5）就一般情況而言，常常是以演算法執行時間做為演算法優劣的主要衡量指標的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/62262.html
標籤：非技術區