《“數(shù)據(jù)結(jié)構(gòu)與算法”課程學(xué)習(xí)總結(jié)報(bào)告.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《“數(shù)據(jù)結(jié)構(gòu)與算法”課程學(xué)習(xí)總結(jié)報(bào)告.doc（4頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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