數據結構復習總結第一章概論

　　第一章概論

　　基本概念和術語

　　數據是信息的載體能被計算機識別存儲和加工處理

　　數據元素是數據的基本單位可由若干個數據項組成數據項是具有獨立含義的最小標識單位

　　數據結構包括)數據的邏輯結構從邏輯關系上描述數據與數據存儲無關獨立於計算機;

　　)數據的存儲結構是邏輯結構用計算機語言的實現依賴於計算機語言

　　)數據的運算定義在邏輯結構上每種邏輯結構都有一個運算集合常用的檢索/插入/刪除/更新/排序

　　數據類型是一個值的集合及在值上定義的一組操作的總稱分為原子類型和結構類型

　　抽象數據類型是抽象數據的組織和與之相關的操作其優點是將數據和操作封裝在一起實現了信息隱藏

　　ADT是在概念層上描述問題;類是在實現層上描述問題;在應用層上操作對象(類的實例)解決問題

　　數據的邏輯結構有)線性結構若結構是非空集則僅有一個開始和終端結點並且所有結點最多只有一個直接前趨和後繼

　　)非線性結構一個結點可能有多個直接前趨和後繼

　　數據的存儲結構有)順序存儲把邏輯相鄰的結點存儲在物理上相鄰的存儲單元內

　　)鏈接存儲結點間的邏輯關系由附加指針字段表示

　　)索引存儲存儲結點信息的同時建立附加索引表有稠密索引和稀疏索引

　　)散列存儲按結點的關鍵字直接計算出存儲地址

　　學習數據結構的意義

　　程序設計的實質是選擇一個好的數據結構設計一個好的算法算法取決於描述實際問題的數據結構

　　算法的描述和分析

　　算法是任意一個良定義的計算過程以一個或多個值輸入並產生一個或多個值輸出是用來解決一個計算問題的工具

　　問題的輸入實例是滿足問題陳述中所給出的限制為計算該問題的解所需要的所有輸入構成

　　評價算法的好壞是)算法是正確的;)要考慮算法所耗的時間存儲空間(輔助存儲)易於理解編碼調試

　　算法所耗時間是每條語句執行時間之和每條語句的執行時間是該語句執行次數與執行時間的乘積

　　算法求解問題的輸入量稱問題的規模算法的時間復雜度T(n)是該算法的時間耗費是求解問題規模n的函數當問題規模趨向無窮大時把T(n)的數量階稱算法的漸進時間復雜度記為O(n)

　　常見的時間復雜度排列為常數階對數階線性階線性對數階平方階立方階K次方階指數階

　　算法的空間復雜度S(n)是該算法的空間耗費是求解問題規模n的函數算法的漸進空間復雜度簡稱空間復雜度

　　算法的時間復雜度和空間復雜度合稱算法的復雜度

　　附結二:

　　第一章 概 論

　　*************************************************************************************

　　數據就是指能夠被計算機識別存儲和加工處理的信息的載體

　　數據元素是數據的基本單位可以由若干個數據項組成數據項是具有獨立含義的最小標識單位

　　*************************************************************************************

　　數據結構的定義·邏輯結構從邏輯結構上描述數據獨立於計算機·線性結構一對一關系

　　·線性結構多對多關系

　　·存儲結構是邏輯結構用計算機語言的實現·順序存儲結構如數組

　　·鏈式存儲結構如鏈表

　　·索引存儲結構·稠密索引每個結點都有索引項

　　·稀疏索引每組結點都有索引項

　　·散列存儲結構如散列表

　　·數據運算·對數據的操作定義在邏輯結構上每種邏輯結構都有一個運算集合

　　·常用的有檢索插入刪除更新排序

　　*************************************************************************************

　　數據類型是一個值的集合以及在這些值上定義的一組操作的總稱·原子類型由語言提供

　　·結構類型由用戶借助於描述機制定義是導出類型

　　抽象數據類型ADT·是抽象數據的組織和與之的操作相當於在概念層上描述問題

　　·優點是將數據和操作封裝在一起實現了信息隱藏

　　*************************************************************************************

　　程序設計的實質是對實際問題選擇一種好的數據結構設計一個好的算法算法取決於數據結構

　　*************************************************************************************

　　算法是一個良定義的計算過程以一個或多個值輸入並以一個或多個值輸出

　　評價算法的好壞的因素·算法是正確的;

　　·執行算法的時間;

　　·執行算法的存儲空間(主要是輔助存儲空間);

　　·算法易於理解編碼調試

　　*************************************************************************************

　　時間復雜度是某個算法的時間耗費它是該算法所求解問題規模n的函數

　　漸近時間復雜度是指當問題規模趨向無窮大時該算法時間復雜度的數量級

　　評價一個算法的時間性能時主要標准就是算法的漸近時間復雜度

　　算法中語句的頻度不僅與問題規模有關還與輸入實例中各元素的取值相關

　　時間復雜度按數量級遞增排列依次為常數階O()對數階O(logn)線性階O(n)線性對數階O(nlogn)平方階O(n^)立方階O(n^)……k次方階O(n^k)指數階O(^n)

　　空間復雜度是某個算法的空間耗費它是該算法所求解問題規模n的函數

　　算法的時間復雜度和空間復雜度合稱算法復雜度

From:http://tw.wingwit.com/Article/program/sjjg/201311/23758.html