第一章概論
1.1基本概念和術語
資料是資訊的載體,能被計算機識別、儲存和加工處理。
資料元素是資料的基本單位，可由若干個資料項組成，資料項是具有獨立含義的最小標識單位。
資料結構包括：1）資料的邏輯結構，從邏輯關係上描述資料，與資料儲存無關，獨立於計算機； 2）資料的儲存結構，是邏輯結構用計算機語言的實現，依賴於計算機語言。 3）資料的運算，定義在邏輯結構上，每種邏輯結構都有乙個運算集合。
常用的：檢索/插入/刪除/更新/排序。
資料型別是乙個值的集合及在值上定義的一組操作的總稱。分為原子型別和結構型別。
抽象資料型別是抽象資料的組織和與之相關的操作。其優點是將資料和操作封裝在一起實現了資訊隱藏。
adt是在概念層上描述問題；類是在實現層上描述問題；在應用層上操作物件（類的例項）解決問題。
資料的邏輯結構有：1）線性結構，若結構是非空集則僅有乙個開始和終端結點，並且所有結點最多只有乙個直接前趨和後繼。
2）非線性結構，乙個結點可能有多個直接前趨和後繼。
資料的儲存結構有：1）順序儲存，把邏輯相鄰的結點儲存在物理上相鄰的儲存單元內。
2）鏈結儲存，結點間的邏輯關係由附加指標字段表示。
3）索引儲存，儲存結點資訊的同時，建立附加索引表，有稠密索引和稀疏索引。
4）雜湊儲存，按結點的關鍵字直接計算出儲存位址。
1.2學習資料結構的意義
程式設計的實質是選擇乙個好的資料結構，設計乙個好的演算法。演算法取決於描述實際問題的資料結構。
1.3演算法的描述和分析
演算法是任意乙個良定義的計算過程，以乙個或多個值輸入，並產生乙個或多個值輸出。是用來解決乙個計算問題的工具。
問題的輸入例項是滿足問題陳述中所給出的限制、為計算該問題的解所需要的所有輸入構成。
評價演算法的好壞是：1）演算法是正確的；2）要考慮演算法所耗的時間、儲存空間（輔助儲存）、易於理解，編碼，除錯。
演算法所耗時間是每條語句執行時間之和，每條語句的執行時間是該語句執行次數與執行時間的乘積。
演算法求解問題的輸入量稱問題的規模。
演算法的時間複雜度t(n)是該演算法的時間耗費，是求解問題規模n的函式。當問題規模趨向無窮大時，把t(n)的數量階稱演算法的漸進時間複雜度，記為o(n)。常見的時間複雜度排列為：
常數階、對數階、線性階、線性對數階、平方階、立方階、k次方階、指數階。
演算法的空間複雜度s(n)是該演算法的空間耗費，是求解問題規模n的函式。演算法的漸進空間複雜度簡稱空間複雜度。
演算法的時間複雜度和空間複雜度合稱演算法的複雜度。
附結二:
第一章概論
資料就是指能夠被計算機識別、儲存和加工處理的資訊的載體。
資料元素是資料的基本單位，可以由若干個資料項組成。資料項是具有獨立含義的最小標識單位。
資料結構的定義：·邏輯結構：從邏輯結構上描述資料，獨立於計算機。·線性結構：一對一關係。
·線性結構：多對多關係。
·儲存結構：是邏輯結構用計算機語言的實現。·順序儲存結構：如陣列。
·鏈式儲存結構：如鍊表。
·索引儲存結構：·稠密索引：每個結點都有索引項。
·稀疏索引：每組結點都有索引項。
·雜湊儲存結構：如雜湊表。
·資料運算。·對資料的操作。定義在邏輯結構上，每種邏輯結構都有乙個運算集合。
·常用的有：檢索、插入、刪除、更新、排序。
資料型別：是乙個值的集合以及在這些值上定義的一組操作的總稱。·原子型別：由語言提供。
·結構型別：由使用者借助於描述機制定義，是匯出型別。
抽象資料型別adt：·是抽象資料的組織和與之的操作。相當於在概念層上描述問題。
·優點是將資料和操作封裝在一起實現了資訊隱藏。
程式設計的實質是對實際問題選擇一種好的資料結構，設計乙個好的演算法。演算法取決於資料結構。
演算法是乙個良定義的計算過程，以乙個或多個值輸入，並以乙個或多個值輸出。
評價演算法的好壞的因素：·演算法是正確的；
·執行演算法的時間；
·執行演算法的儲存空間（主要是輔助儲存空間）；
·演算法易於理解、編碼、除錯。
時間複雜度：是某個演算法的時間耗費，它是該演算法所求解問題規模n的函式。
漸近時間複雜度：是指當問題規模趨向無窮大時，該演算法時間複雜度的數量級。
評價乙個演算法的時間效能時，主要標準就是演算法的漸近時間複雜度。
演算法中語句的頻度不僅與問題規模有關，還與輸入例項中各元素的取值相關。
時間複雜度按數量級遞增排列依次為：常數階o(1)、對數階o(log2n)、線性階o(n)、線性對數階o(nlog2n)、平方階o(n^2)、立方階o(n^3)、……k次方階o(n^k)、指數階o(2^n)。
空間複雜度：是某個演算法的空間耗費，它是該演算法所求解問題規模n的函式。
演算法的時間複雜度和空間複雜度合稱演算法複雜度。
本章的重點是了解資料結構的邏輯結構、儲存結構、資料的運算三方面的概念及相互關係，難點是演算法複雜度的分析方法。
需要達到 《識記》 層次的基本概念和術語有：資料、資料元素、資料項、資料結構。特別是資料結構的邏輯結構、儲存結構及資料運算的含義及其相互關係。
資料結構的兩大類邏輯結構和四種常用的儲存表示方法。
需要達到 《領會》 層次的內容有演算法、演算法的時間複雜度和空間複雜度、最壞的和平均時間複雜度等概念，演算法描述和演算法分析的方法、對一般的演算法要能分析出時間複雜度。
對於基本概念，仔細看書就能夠理解，這裡簡單提一下：
資料就是指能夠被計算機識別、儲存和加工處理的資訊的載體。
資料元素是資料的基本單位，有時乙個資料元素可以由若干個資料項組成。資料項是具有獨立含義的最小標識單位。如整數這個集合中，10這個數就可稱是乙個資料元素.
又比如在乙個資料庫(關係式資料庫)中，乙個記錄可稱為乙個資料元素，而這個元素中的某一欄位就是乙個資料項。
資料結構的定義雖然沒有標準，但是它包括以下三方面內容： 邏輯結構、儲存結構、和對資料的操作 。這一段比較重要，我用自己的語言來說明一下，大家看看是不是這樣。
比如乙個表 ( 資料庫 )，我們就稱它為乙個資料結構，它由很多記錄 ( 資料元素 )組成，每個元素又包括很多字段 ( 資料項 )組成。那麼這張表的邏輯結構是怎麼樣的呢? 我們分析資料結構都是從結點 (其實也就是元素、記錄、頂點，雖然在各種情況下所用名字不同，但說的是同乙個東東)之間的關係來分析的，對於這個表中的任乙個記錄(結點)，它只有乙個直接前趨 ，只有乙個直接後繼 (前趨後繼就是前相鄰後相鄰的意思)，整個表只有乙個開始結點和乙個終端結點 ，那我們知道了這些關係就能明白這個表的邏輯結構了。
而儲存結構則是指用計算機語言如何表示結點之間的這種關係。如上面的表，在計算機語言中描述為連續存放在一片記憶體單元中，還是隨機的存放在記憶體中再用指標把它們鏈結在一起，這兩種表示法就成為兩種不同的儲存結構。( 注意，在本課程裡，我們只在高階語言的層次上討論儲存結構。
)第三個概念就是對資料的運算 ，比如一張**，我們需要進行查詢，增加，修改，刪除記錄等工作，而怎麼樣才能進行這樣的操作呢? 這也就是資料的運算，它不僅僅是加減乘除這些算術運算了，在資料結構中，這些運算常常涉及演算法問題。
弄清了以上三個問題，就可以弄清資料結構這個概念。
通常我們就將資料的邏輯結構簡稱為資料結構 ，資料的邏輯結構分兩大類： 線性結構和非線性結構 (這兩個很容易理解)
資料的儲存方法有四種： 順序儲存方法 、 鏈結儲存方法 、 索引儲存方法和雜湊儲存方法 。
下乙個是難點問題，就是演算法的描述和分析，主要是演算法複雜度的分析方法及其運用。
首先了解一下幾個概念。乙個是時間複雜度 ，乙個是漸近時間複雜度 。前者是某個演算法的時間耗費，它是該演算法所求解問題規模 n的函式，而後者是指當問題規模趨向無窮大時，該演算法時間複雜度的數量級。
當我們評價乙個演算法的時間效能時，主要標準就是演算法的漸近時間複雜度 ，因此， 在演算法分析時，往往對兩者不予區分，經常是將漸近時間複雜度t(n)=o(f(n)簡稱為時間複雜度，其中的f(n)一般是演算法中頻度最大的語句頻度 。
此外，演算法中語句的頻度不僅與問題規模有關，還與輸入例項中各元素的取值相關 。但是我們總是考慮在最壞的情況下的時間複雜度。以保證演算法的執行時間不會比它更長。
常見的時間複雜度，按數量級遞增排列依次為： 常數階o(1) 、 對數階o(log2n) 、 線性階o(n) 、 線性對數階o(nlog2n) 、 平方階o(n^2)、立方階o(n^3) 、 k次方階o(n^k) 、 指數階o(2^n) 。
時間複雜度的分析計算請看書本上的例子，然後我們通過做練習加以領會和鞏固。
資料結構習題一
1.1 簡述下列概念：資料、資料元素、資料型別、資料結構、邏輯結構、儲存結構、線性結構、非線性結構。
◆ 資料 ：指能夠被計算機識別、儲存和加工處理的資訊載體。
◆ 資料元素 ：就是資料的基本單位，在某些情況下，資料元素也稱為元素、結點、頂點、記錄。資料元素有時可以由若干資料項組成。
◆ 資料型別 ：是乙個值的集合以及在這些值上定義的一組操作的總稱。
◆ 資料結構 ：指的是資料之間的相互關係，即資料的組織形式。一般包括三個方面的內容:資料的邏輯結構 、 儲存結構和資料的運算 。
◆ 邏輯結構 ：指各資料元素之間的邏輯關係。
◆ 儲存結構 ：就是資料的邏輯結構用計算機語言的實現。
◆ 線性結構 ：資料邏輯結構中的一類，它的特徵是若結構為非空集，則該結構有且只有乙個開始結點和乙個終端結點 ，並且所有結點都最多只有乙個直接前趨和乙個直接後繼 。線性表就是乙個典型的線性結構。
◆ 非線性結構 ：資料邏輯結構中的另一大類，它的邏輯特徵是乙個結點可能有多個直接前趨和直接後繼。
1.2 試舉乙個資料結構的例子、敘述其邏輯結構、儲存結構、運算三個方面的內容。
◆ 例如有一張學生成績表，記錄了乙個班的學生各門課的成績。按學生的姓名為一行記成的表。這個表就是乙個資料結構。
每個記錄(有姓名，學號，成績等字段)就是乙個結點，對於整個表來說，只有乙個開始結點(它的前面無記錄)和乙個終端結點(它的後面無記錄)，其他的結點則各有乙個也只有乙個直接前趨和直接後繼(它的前面和後面均有且只有乙個記錄)。這幾個關係就確定了這個表的邏輯結構。
那麼我們怎樣把這個表中的資料儲存到計算機裡呢? 用高階語言如何表示各結點之間的關係呢? 是用一片連續的記憶體單元來存放這些記錄(如用陣列表示)還是隨機存放各結點資料再用指標進行鏈結呢?
這就是儲存結構的問題，我們都是從高階語言的層次來討論這個問題的。(所以各位趕快學c語言吧)。
最後，我們有了這個表(資料結構)，肯定要用它，那麼就是要對這張表中的記錄進行查詢，修改，刪除等操作，對這個表可以進行哪些操作以及如何實現這些操作就是資料的運算問題了。
資料結構第一章習題
第一章習題 一 單項選擇題1.資料結構是一門研究非數值計算的程式設計問題中計算機的 以及它們之間的 和運算等的學科。a 操作物件 b 計算方法 c 邏輯儲存 d 資料映象 a 結構 b 關係 c 運算 d 演算法2.演算法分析的目的是 演算法分析的兩個主要方面是 a 找出資料結構的合理性 b 研究演...
資料結構第一章習題
一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的以及它們之間的和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是的有限集合，r是d上的有限集合。3.資料結構包括資料的資料的和資料的這三個方面的內容。4.資料結構按邏輯結構可分為兩大類，它們分別是和 5.線性結構中元素之間...
資料結構第一章練習題
第一章概論自測題 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的以及它們之間的和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是的有限集合，r是d上的有限集合。3.資料結構包括資料的資料的和資料的這三個方面的內容。4.資料結構按邏輯結構可分為兩大類，它們分別是和 5....