《“數據結構與算法”課程學習總結報告.doc》由會員分享，可在線閱讀，更多相關《“數據結構與算法”課程學習總結報告.doc（4頁珍藏版）》請在裝配圖網上搜索。

數據結構課程總結 孫博 1104011045 11 計本3班 如何合理的組織數據、高效的處理數據是擴大計算機應用領域、提高軟件效率的關鍵。而在軟件開發(fā)過程中人們會要求軟件工程師們使程序有更高的運行效率。因此要成為一名合格的軟件編程員，必須具備數據結構領域和算法設計領域的專門知識。 本學期我們在李紅老師的帶領下學習了《數據結構結構與算法》一書。這本書安排十分合理，在第一章對全書進行導引和學習的基礎知識、預備知識。在2—6章中使邏輯結構為“線性”的數據結構及其應用知識內容。在7、8章中使邏輯結構中的為“樹形”的數據結構及應喲就能夠只是內容。在第九章中使邏輯結構為“集合性”的數據元素在三列存儲下的數據結構及其應用知識內容。在第十章使邏輯結構為“圖形”的數據數據結構及其應用知識內容。下面將對各章的內容驚醒總結： 第一章：首先介紹了數據的相關知識，講述了數據的概、構成等，數據的最小組成單位。然后講述了數據類型與數據結構。 數據類型包括概念及定義，數據類型包括簡單數據類型和復雜數據。簡單數據類型有：整數，實屬，字符，指針，枚舉量等。而復雜數據類型包括：數組，結構圖，共用體。 而數據結構主要使討論元素之間的關系，數據結構包括三方面內容，及邏輯結構，存儲結構以及一組運算集合。數據的邏輯結構有四種基本結構：集合性結構，線性結構，樹形結構，圖形結構。數據的存儲結構是指數據嚴肅在存儲器中的存儲方式包括順序存儲，鏈表存儲，索引存儲，散列存儲。 然后介紹以前學習的C語言（及本教材的使用的算法描述工具）知識錦興路回顧包括指針、結構比阿亮、函數、遞歸、動態(tài)存儲分配、文件操作等內容。 第二章：順序表及其應用主要介紹的是線性邏輯結構的呼聲幾乎在順序存儲方法下的數據結構順序標的概念、數據類型 、數據結構、基本運算及相關應用問題。 應用一：查找—介紹了兩種方法：簡單順序查找（從書序標的一端來時掃描，將待查找元素與數據節(jié)點中的個元素比較。若相等，則查找成功，否則失?。┖投植檎遥▽⒈碇虚g的記錄的關鍵字與給定的值比較，若相等，則成功。否則，將順序表風味左右兩個字表，然后在子表中進一步查找。） 應用二：排序問題—介紹了交換排序，選擇排序，插入排序，歸并排序。 1、 插入排序 包括直接插入排序(將順序表分為左右兩個子表，左子表為有序表，右子表為無序表，將右子表中的元素插入左子表中)和希爾排序法（將整個待排序的元素序列分割成若干子序列，對每個子序列分別進行直接插入排序，當整個帶排序元素序列“基本有序時”，在進行直接插入排序） 2、 交換排序 a) 冒泡排序：兩輛比較待排序元素的關鍵字，發(fā)現相反時即進行交換，知道沒有逆序的元素為止。 b) 快速排序算法：在待排序的元素中選定一個“中間數”，將其他數據元素與該數比較，將比其小的數據放道左子表中，比起大的放入右子表中。 3、 選擇排序 a) 直接選擇排序：將數據進行多談排序，每趟選出其中的最大數或最小數放在最終位置上，每趟中已排好的數不再參加下一輪的排序。 b) 堆排序：輸出堆頂元素將剩余元素按關鍵字大小重誠信排列成一個堆重復上述2個步驟 4、 歸并排序 將兩個或兩個以上的有序表合并成一個新的有序表。 應用三：字符處理問題 介紹了串和順序串的定義及相關概念，還有順序串的基本算法。 第三章：介紹鏈表。鏈表中數據元素的存儲不一定是連續(xù)的，還可以占用任意的、不連續(xù)的物理存儲區(qū)域。與順序表相比，鏈表的插入、刪除不需要移動元素，給算法的效率帶來較大的提高，且在存儲空間上有動態(tài)申請的優(yōu)點。這一章中介紹了鏈表的節(jié)點結構、靜態(tài)與動態(tài)鏈表的概念、鏈表的基本運算（如求表長、插入、查找、刪除等）、單鏈表的建立（頭插法和尾插法）以及雙向循環(huán)鏈表的定義、結構、功能和基本算法。弄清其個運算的算法思想及其時間復雜度和空間性能。最后介紹了鏈表之中存儲結構在實際中的相關應用。 a) 單循環(huán)鏈表是一種首尾相接的單鏈表，終端結點的指針域指向開始結點或頭結點。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點是查找頭指針和尾指針的時間都是O(n)，不用遍歷整個鏈表。 b) 雙鏈表就是雙向鏈表，就是在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior，形成兩條不同方向的鏈。由頭指針head惟一確定。雙鏈表也可以頭尾相構成雙循環(huán)鏈表。雙鏈表上的插入和刪除時間復雜度均為O(1)。 順序表和鏈表的比較 a） 基本空間的考慮 存儲密度是指節(jié)點數據本身所占的存儲量除以結點構所占的存儲總量所得的值。值越大存儲空間利用率越高。 順序表是靜態(tài)分配的，存儲密度為1,鏈表是動態(tài)分配的，存儲密度小于1。 b) 順序表適用于靜態(tài)查找，要進行刪除和插入操作時，需移動大量結點。 鏈表適用于做動態(tài)的插入和刪除。 第四章：堆棧是運算受限制的線性結構。其基本運算方法與順序表和鏈表運算方法基本相同，不同的是堆棧須遵循“先進后出”的規(guī)則，對堆棧的操作只能在棧頂進行；堆棧在文字處理，匹配問題和算術表達式的求值問題方面的應用。 a) 棧的基本運算有六種：構造空棧：InitStack，判棧空：StackEmpty，判棧滿：StackFull，進棧：Push，退棧：Pop，取棧頂元素：StackTop b) 在順序棧中有“上溢”和“下溢”的現象?！吧弦纭笔菞ｍ斨羔樦赋鰲５耐饷媸浅鲥e狀態(tài)?！跋乱纭笨梢员硎緱榭諚＃虼擞脕碜鳛榭刂妻D移的條件。 c) 順序棧中的基本操作有六種：構造空棧，判?？眨袟M，進棧，退棧，取棧頂元素 d) 鏈棧則沒有上溢的限制，因此進棧不要判棧滿。鏈棧不需要在頭部附加頭結點，只要有鏈表的頭指針就可以了。 e) 鏈棧中的基本操作有五種：構造空棧，判棧空，進棧，退棧，取棧頂元素 第五章：隊列及其應用，我們知道隊列是一種特殊的線性表，是一種具有線性邏輯結構的數據元素的集合。而隊列的運算遵循“先進后出”的原則，因此，隊列也是一個運算受限制的線性表。 a) 隊列的基本運算有六種：置空隊：InitQueue，判隊空：QueueEmpty，判隊滿：QueueFull，入隊：EnQueue，出隊：DeQueue，取隊頭元素：QueueFront b) 順序隊列的“假上溢”現象：由于頭尾指針不斷前移，超出向量空間。這時整個向量空間及隊列是空的卻產生了“上溢”現象。為了克服“假上溢”現象引入循環(huán)向量的概念，是把向量空間形成一個頭尾相接的環(huán)形，這時隊列稱循環(huán)隊列。 c) 判定循環(huán)隊列是空還是滿，方法有2種：一種是另設一個標志變量來判斷;第二種是少用一個元素空間，入隊時先測試(q->rear%m=q->front? )滿：空。 d) 隊列的鏈式存儲結構稱為鏈隊列，一個鏈隊列就是一個操作受限的單鏈表。為了便于在表尾進行插入的操作，在表尾增加一個尾指針，一個鏈隊列就由一個頭指針和一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。在鏈隊列的出隊算法中，要注意當原隊中只有一個結點時，出隊后要同進修改頭尾指針并使隊列變空。 第六章：介紹了特殊矩陣和廣義表的概念與應用。其中，特殊矩陣包括對稱矩陣、三角矩陣、對角矩陣和稀疏矩陣，書中分別詳細介紹了它們的存儲結構。其中三元組和十字鏈表這兩種結構尤為重要；對著兩種結構的建立了應用要掌握。稀疏矩陣的應用包括轉置和加法運算等。最后介紹了廣義表的相關概念及存儲結構，關于它的應用，課本中舉了m元多項式的表示問題。 第七章：二叉樹的知識是重點內容。在介紹有關概念時，提到了二叉樹的性質以及兩種特殊的二叉樹：完全二叉樹和滿二叉樹。接著介紹二叉樹的順序存儲和鏈接存儲以及生成算法。重點介紹二叉樹的遍歷算法（遞歸算法、先序、中序和后序遍歷非遞歸算法）和線索二叉樹。二叉樹的應用：基本算法、哈夫曼樹、二叉排序樹和堆排序，其中關于二叉排序樹和哈弗曼書的構建是重點。 a) 兩種特殊的二叉樹：完全二叉樹（非葉子節(jié)點均有兩個孩子節(jié)點并且對于仍一層某一節(jié)點有孩子節(jié)點，該層所有節(jié)點均有孩子節(jié)點）和滿二叉樹（在完全二叉樹上的基礎上最下層從左到右刪除若干個節(jié)點。） b) 二叉樹的5個重要性質 c) 根據結點的次序不同可得三種遍歷：先序遍歷，中序遍歷、后序遍歷。 d) 二叉樹的應用：基本算法、哈弗曼樹、二叉排序樹和堆排序 第八章：介紹了樹和森林。樹與二叉樹是不同的概念。教材介紹了樹和森林的概念、遍歷和存儲結構，還有樹、森林和二叉樹的相互關系，樹或森林怎樣轉化成二叉樹，二叉樹又如何轉換為樹和森林等算法。 第九章：散列結構是一種查找效率很高的一種數據結構。本章的主要知識點有：散列結構的概念及其存儲結構、散列函數、兩種沖突處理方法、線性探測散列和鏈地址散列的基本算法以及散列結構的查找性能分析。 第十章：介紹了圖的概念及其應用，是本書的難點。圖的存儲結構的知識點有：鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識點有：有向圖、連通圖、生成樹和森林、最短路徑問題和有向無環(huán)圖及其應用。有向無環(huán)圖重點理解AOV網和拓撲排序及其算法。 心得體會以及建議：通過學習《數據結構與算法》我們可以設計出更好的算法，高效地組織數據。一個程序無論采用何種語言，其基本算法思想不會改變。 “軟件開發(fā)好比寫作文，計算機語言提供了許多華麗的辭藻，而數據結構則考慮如何將這些辭藻組織成一篇優(yōu)秀的文章來?！痹趯W習這門課中，要熟悉對算法思想的一些描述手段，包括文字描述、圖形描述和計算機語言描述等。因此，計算機語言基礎是必須的，因為它提供了一種重要的算法思想描述手段——機器可識別的描述。 這門課結束之后，我總結了學習中遇到的一些問題，最為突出的，書本上的知識與老師的講解都比較容易理解，但是當自己采用剛學的知識點編寫程序時卻感到十分棘手，有時表現在想不到適合題意的算法，有時表現在算法想出來后，只能將書本上原有的程序段謄寫到自己的程序中再加以必要的連接以完成程序的編寫。針對這一情況，我會嚴格要求自己，熟練掌握算法思想，盡量獨立完成程序的編寫與修改工作，只有這樣，才能夠提高運用知識，解決問題的能力。 教學的建議 1、建議在上課過程中加大隨堂練習的分量，以便學生能當堂消化課堂上學習的知識，也便于及時了解學生對知識點的掌握情況，同時有助于學生保持良好的精神狀態(tài)。 2、建議在課時允許的情況下，增加習題課的分量，通過課堂的習題講解，加深對知識點的掌握，同時對各知識點的運用有一個更為直觀和具體的認識。 以上便是我對《數據結構與算法》這門課的學習總結，我會抓緊時間將沒有吃透的知識點補齊。今后我仍然會繼續(xù)學習，克服學習中遇到的難關，在打牢基礎的前提下向更深入的層面邁進！