數(shù)據(jù)結構與算法課程學習總結

1、數(shù)據(jù)結構與算法課程學習總結2010年05月20日 班級： 姓名： 學號：一、課程學習內容總結（ 1）第一章知識點及主要知識 ：本章的重點是數(shù)據(jù)結構中的邏輯結構、 存儲結構、數(shù)據(jù)的運算3個方面的概 念及相互關系，難點是算法復雜度的分析方法。 基本概念和術語有數(shù)據(jù)、 數(shù)據(jù)元 素、數(shù)據(jù)項、數(shù)據(jù)結構。特別是數(shù)據(jù)結構的邏輯結構、存儲結構及運算的含義及 其相互關系；數(shù)據(jù)的結構的兩大類邏輯結構和4個常用的存儲表示方法；算法、 算法的時間復雜度和空間復雜度、 最壞的和平均時間復雜度等概念， 算法描述和 算法分析的方法、對一般的算法要能分析出時間復雜度和空間復雜度。本人掌握知識情況及分析：通過對這一章的學習，

2、我理解了數(shù)據(jù)和數(shù)據(jù)結構的有關概念， 熟悉了數(shù)據(jù)結 構的邏輯結構和存儲結構。但對算法的時間、 空間性能分析還不太熟練， 尤其是 空間性能分析需要加強。（ 2）第二章知識點及主要知識 ：本章介紹了順序表、順序串的結構、數(shù)據(jù)類型、基本運算及相關應用。 順序表是一種具有線性邏輯結構、 順序存儲結構的數(shù)據(jù)集合， 它的一些基本 運算包括初始化表、求表長、查找表中元素、插入元素及刪除元素等。其中，實 現(xiàn)順序表的插入與刪除運算時要大量移動元素，算法的時間復雜度為O（n）。順序串是順序表的一個特列。其特別之處在于組成順序串的數(shù)據(jù)元素是一組字符。順序串的運算主要是針對字符串來進行的，其基本運算大多數(shù)都比較簡單，只

3、有“子串定位”（串的模式匹配）運算較為復雜。模式匹配時各種串處理系統(tǒng) 中重要的操作之一，本章介紹了模式匹配的簡單算法思想。本人掌握知識情況及分析 ：通過對這一章的學習， 對于順序表的概念、生成算法理解較為清晰，并且熟 悉簡單順序查找和二分查找，不過對于分塊查找較為含糊；在排序問題中， 因為 冒泡排序在大一C語言課上已經學習過了， 再來學習感覺很輕松。 對于插入排序 和選擇排序理解的不錯， 但是，在實際運用中仍然出現(xiàn)明顯不熟練的現(xiàn)象。 在學 習歸并排序過程中感覺較吃力， 現(xiàn)在對這種排序方法仍然非常模糊， 所以需要花 較多的時間來補習。此外串的模式匹配也是我較難理解的一個內容。（3）第三章知識點及

4、主要知識：本章介紹了幾種鏈表的結構、數(shù)據(jù)類型、基本運算及相關的應用單鏈表是一種簡單、常用的數(shù)據(jù)結構。與順序表相比，其插入、刪除結點不 需要移動元素，且不必事先估計存儲空間的大小。所以， 應用鏈表來完成多項式 相加、有序表的歸并及箱子排序等運算，其時間性能較好。對單鏈表中的每個結點增加一個指向其前驅結點的指針域就構成了雙向鏈 表。雙向鏈表的插入操作有前插和后插之分， 其操作過程較單鏈表的復雜、 靈活。鏈串是鏈接存儲的字符串。 若每個字符占用一個結點空間， 鏈串的存儲空間 浪費較大； 且由于對字符串的操作通常不是針對單個字符進行， 所以鏈串中的每 個結點一般存放多個字符， 稱為塊鏈串。 本章介紹了

5、在結點大小為1的的鏈塊串 上實現(xiàn)的串匹配算法，算法的時間復雜度與順序串上的串匹配算法相同。本人掌握知識情況及分析：通過對這一章的學習， 對于單鏈表的概念理解的不錯了， 并且學會了有關單 鏈表的基本算法，但在雙向循環(huán)鏈表這一塊知識點上，感覺理解有點困難， 在這 一方面還需加強（4）第四章知識點及主要知識：本章介紹了棧及其相關應用。 棧是一種運算受限制的線性結構，遵守“先進后出”的規(guī)則，其插入與刪除 操作都在棧頂進行。 順序存儲和鏈接存儲的棧分別被稱為順序棧和鏈棧。 不同的 存儲結構決定了各種運算實現(xiàn)方法的不同。在對棧的邏輯結構、 存儲結構及基本運算介紹的基礎上， 本章重點介紹了棧 的一些基本應用

6、。棧作為一類重要的數(shù)據(jù)類型， 被廣泛應用各種程序設計中。 本 章選取了一些典型的應用問題。分別進行了問題分析，提出了算法思想， 并給出 了解決問題的算法實現(xiàn)過程，供讀者在學習和工作中借鑒使用。本人掌握知識情況及分析：通過這一章學習，認識了一種新的線性結構-堆棧，有關堆棧的知識，除 有關算法較為特殊以外， 新的知識點比較少， 因為其余算法都在先前學過的順序 表和鏈表中遇到過， 并且學這一新知識點時比較重視， 所以對這部分內容學的還是很不錯的，只是仍然在算法的性能分析上有所不足。（5）第五章知識點及主要知識：本章介紹了隊列及其相關應用。隊列是一種運算受限制的線性結構， 遵守“先進先出”的規(guī)則，其插

7、入在隊 尾、刪除在對頭。 順序存儲和鏈接存儲的隊列分別被稱為順序隊列和鏈隊列。 由 于不斷有出隊運算， 使得順序隊列出現(xiàn) “假溢出” 現(xiàn)象，為了避免這種現(xiàn)象發(fā)生， 同時也為了節(jié)省存儲空間， 我們提出了循環(huán)隊列的概念。 隊列的不同存儲結構決 定了各種運算的實現(xiàn)方法的不同。在對隊列的邏輯結構、 存儲結構及基本運算介紹的基礎上， 本章介紹了隊列 的一些基本應用。隊列作為一類重要的數(shù)據(jù)結構，被廣泛應用于各種實際問題解 決及程序設計中。本人掌握知識情況及分析：通過這一章的學習，又認識了一個新的線性結構-隊列，并且隊列與堆棧 一樣，都是運算受限制的線性結構，新的知識點也不多， ，與堆?；舅惴ㄔ谒?想上大

8、同小異， 只要注意它的出對和入隊就行。 但對于循環(huán)隊列還有一些小模糊， 騰出時間來把書好好看一看，應該會有所好轉。（6）第六章知識點及主要知識：本章在介紹數(shù)組的概念和存儲的方法的基礎上， 重點介紹了矩陣的存儲及應 用，以及廣義表的相關概念。矩陣廣泛應用于科學與工程計算問題中， 通常采用二維數(shù)組來存儲矩陣。 在 數(shù)值計算過程中， 經常出現(xiàn)一些階數(shù)很高、 但其數(shù)據(jù)元素分布具有一點規(guī)律的矩 陣，我們稱這樣的矩陣為特殊矩陣，包括對稱矩陣、三角矩陣、對角矩陣和稀疏 矩陣。本章介紹了這些特殊矩陣的存儲方法， 并重點介紹了稀疏矩陣的存儲及應 用。盡管廣義表是線性表的一種推廣， 但它并不是線性表。 本章在介紹

9、了廣義表 的相關概念的基礎上，介紹了廣義表的存儲結構。廣義表濃縮了線性表、 數(shù)組等 常見數(shù)據(jù)結構的特點，在有效利用存儲空間方面更勝一籌，目前在文本處理、 人 工智能、代數(shù)操作和計算機圖形等各領域都具有應用價值。本人掌握知識情況及分析：通過這一章的學習， 對于矩陣的存儲理解的比較好， 但對于矩陣的應用確感 覺有點吃力，對于書本上的關于矩陣轉置算法的C語言描述也不太理解。在稀疏 矩陣相加算法中，用三元組表實現(xiàn)時比較容易理解， 但對于十字鏈表進行矩陣相 加的方法還是感覺有點吃力的。（7）第七章知識點及主要知識：本章主要內容有二叉樹的概念， 二叉樹的有關性質，兩種特殊的二叉樹（完 全二叉樹和滿二叉樹）

10、 ，二叉樹的兩種存儲結構 （順序存儲結構、鏈式存儲結構）， 二叉樹的遍歷的遞歸算法和非遞歸算法， 線索化二叉樹算法， 二叉樹中葉子個數(shù) 的統(tǒng)計， 二叉樹的深度計算等。 這些基本問題和基本算法是學習的要點。 在此基 礎上，本章列出的二叉樹應用問題， 如表達式求值、 哈夫曼樹和哈夫曼編碼問題、 二叉排序樹、堆和堆排序等問題。本人掌握知識情況及分析：通過對本章的學習，接觸到了本書的一個重點內容-二叉樹，由于老師上 這章之前說過這部分內容的重要性， 所以引起了足夠的重視， 但卻也有一些內容 沒有完全理解。 比如在第一節(jié)基本概念中，二叉樹的性質4就沒有完全理解， 還 有一些其他的小內容也是如此。 但對二

11、叉樹的存儲結構和遍歷算法這部分內容掌 握較好，能夠熟練運用，并且對于二叉樹應用中的哈弗曼樹也比較熟練。8）第八章知識點及主要知識：樹在二叉樹的基礎上做了更為一般化的擴展，而森林是樹的集合。樹或森林與二叉樹之間有一個自然的一一對應關系。 任何一個森林或一顆樹 可以唯一地對應到一顆二叉樹； 反之，任何一顆二叉樹也能唯一對應到一個森林 或一棵樹。數(shù)的常用存儲結構包括雙親表示法、孩子表示法和孩子兄弟表示法3種。 對一棵樹，按某種次序訪問其中每一個結點一次且僅一次的過程稱為樹的遍 歷。樹有兩種遍歷方法：先序遍歷和后序遍歷。同樣的森林也有兩種遍歷方法： 先序遍歷和中序遍歷。本章還介紹了樹的一種典型應用B樹

12、。它是一種平衡的多路查找樹。本 書給出了在B樹中查找、插入和刪除關鍵字的算法。本人掌握知識情況及分析：通過對該章的學習，學到了樹和森林相關知識， 其實本章也是第七章的擴展， 因為樹是在二叉樹的基礎上做了更為一般化的擴展， 而森林是樹的集合。 但也有 些特殊的地方。在第一節(jié)基本概念中，樹和森林的性質很容易懂。 對于樹和森林 的存儲結構和遍歷算法這部分內容掌握也較好， 其中對于遞歸思想的運用比較 多。 對于孩子兄弟表示法也理解的不錯，只是在運用時有時會出現(xiàn)一些錯誤。 對 于B樹的掌握還不太熟練，有待進一步加強。（9）第九章知識點及主要知識：散列結構是一種查找效率很高的一種數(shù)據(jù)結構。它是一種特殊的數(shù)

13、據(jù)結構， 表中各元素之間沒有直接的關系。散列和沖突處理是散列法中最重要的兩個概念。 常用的散列函數(shù)有直接定址法、 除留余數(shù)法、數(shù)字分析法、平方取中法和折 疊法等。一個好的散列函數(shù)應該是一個均勻的散列函數(shù)。由于散列法的自身特點， 沖突的發(fā)生時不可避免的。 當不同關鍵字的結點映 射到相同的存儲地址時， 必須采用某種措施進行處理， 才能保證散列法德正常執(zhí) 行。常用的沖突處理方法分為開放定址法和鏈地址法兩大類， 其中開放定址法還 可以分為線性探測再散列、二次探測再散列和偽隨機探測再散列3中方式。開放 定址法操作簡單，節(jié)約空間，但容易引起“二次聚集” 。鏈地址法可以從根本上 杜絕二次聚集，但操作繁瑣，空

14、間占用大。本人掌握知識情況及分析：通過本章的學習，接觸到了一個新的數(shù)據(jù)結構-散列結構，在這一章內容 中，理解比較完善的知識點有：基本概念和存儲結構。散列函數(shù)中直接定址法和 除留余數(shù)法學得還不錯， 但對于數(shù)字分析法等方法則感覺比較棘手。 能夠理解兩 種沖突處理的算法思想，但在用C語言描述時會有點吃力。10）第十章知識點及主要知識：本章介紹了圖的概念及其應用，是本書的重點。 圖是一種較線性表和樹更為復雜的數(shù)據(jù)結構。 一個圖中任意兩個元素都可以 是相關，即每個元素可以有多個前驅和多個后繼。圖可以分為有向圖和無向圖。 圖中的數(shù)據(jù)元素稱為頂點。 有向圖中頂點之間 的關系稱為弧，無向圖中頂點的關系稱為邊。

15、圖的存儲結構的知識點有：鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接 多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。 深度優(yōu)先搜索類 似樹的先序遍歷，廣度搜索類似樹的層次遍歷的過程。通過遍歷算法可以檢測樹的連通性。 對于連通圖可以相應的生成深度優(yōu)先生 成樹和廣度優(yōu)先生成樹。其余知識點有：生成樹和森林、最短路徑問題和有向無環(huán)圖及其應用。 有向 無環(huán)圖重點理解AOV網和拓撲排序及其算法。本人掌握知識情況及分析：通過對這一章的學習， 對于圖的定義理解的比較好， 因為之前的離散數(shù)學中 學習過，現(xiàn)在學習起來就非常輕松了， 但對于基本運算如圖的生成等起初理解有 困難，但隨著學習深入，對它的概念

16、也逐步明朗起來。鄰接矩陣、鄰接表和逆鄰 接表掌握較好，而對十字鏈表和鄰接多重表則較難理解。起初對于圖的遍歷 （包 括深度和廣度優(yōu)先遍歷）有些概念上的模糊，但拿了幾個題目練習之后， 也理解 的不錯了，但對于最小生成樹問題還是比較難理解的。 最短路徑和AOV網學習起 來感覺比較輕松，但用C語言描述的話卻又感覺不怎么輕松了。這門課程的教材非常好，由于是老師自己編寫的教材，對教材有著深刻的理 解，上課時能夠將問題講述得非常清晰，還能夠聯(lián)系實際應用， 而不是簡單的局 限于課本。 課堂的學習氛圍很濃郁，老師講解的很透徹，同學們聽的也很認真。另外，這門課還有一個配套的數(shù)據(jù)結構與算法的實驗課程，主要的目的是鍛

17、 煉我們數(shù)據(jù)結構的實踐能力， 課前同學積極的預習， 并根據(jù)題目要求設計各種算 法，課堂上把自己不懂和迷惑的地方向老師請教，老師細心的給同學們講解，在 這種良好的氛圍中我們的能力得到了很大的提高。在上過這門課之后，我感覺我的能力有了不小的進步，對計算機的學習有了 很大的興趣。學習這門課程時， 首先從根本上就要認識到數(shù)據(jù)結構的本質， 數(shù)據(jù)結構和算 法之間的密切關系， 以及數(shù)據(jù)結構的應用方法。 不然我們很可能陷入各種數(shù)據(jù)結 構的復雜特性中卻還根本不知道到底什么才是數(shù)據(jù)結構的本質， 學了很多很久卻 其實什么都沒有弄明白。開始學習的時候一定要靜下心來。 從最簡單的理論知識開始， 在熟悉了各種 理論知識之后， 比如從最簡單的順序表開始， 首先，要了解這種數(shù)據(jù)結構的特點， 包括內涵和外延。理論知識掌握好之后， 就要學會靈活運用了。 開始時寫一寫所有基本數(shù)據(jù)結 構的基本算法，然后是反思， 根據(jù)這種結構的具體特點， 看看是線性結構還是鏈 式結構， 然后來思考應該有哪些操作。 要不斷的對比總結， 把所有的數(shù)據(jù)結構的 線性結構的實現(xiàn)進行