“數(shù)據(jù)結(jié)構(gòu)與算法”課程學(xué)習(xí)總結(jié)報告
數(shù)據(jù)結(jié)構(gòu)課程總結(jié)
孫博110401104511計本3班
如何合理的組織數(shù)據(jù)、高效的處理數(shù)據(jù)是擴(kuò)大計算機(jī)應(yīng)用領(lǐng)域、提高軟件效率的關(guān)鍵。
而在軟件開發(fā)過程中人們會要求軟件工程師們使程序有更高的運行效率。因此要成為一名合格的軟件編程員,必須具備數(shù)據(jù)結(jié)構(gòu)領(lǐng)域和算法設(shè)計領(lǐng)域的專門知識。
本學(xué)期我們在李紅老師的帶領(lǐng)下學(xué)習(xí)了《數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)與算法》一書。這本書安排十分合理,在第一章對全書進(jìn)行導(dǎo)引和學(xué)習(xí)的基礎(chǔ)知識、預(yù)備知識。在26章中使邏輯結(jié)構(gòu)為“線性”的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用知識內(nèi)容。在7、8章中使邏輯結(jié)構(gòu)中的為“樹形”的數(shù)據(jù)結(jié)構(gòu)及應(yīng)喲就能夠只是內(nèi)容。在第九章中使邏輯結(jié)構(gòu)為“集合性”的數(shù)據(jù)元素在三列存儲下的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用知識內(nèi)容。在第十章使邏輯結(jié)構(gòu)為“圖形”的數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用知識內(nèi)容。下面將對各章的內(nèi)容驚醒總結(jié):
第一章:首先介紹了數(shù)據(jù)的相關(guān)知識,講述了數(shù)據(jù)的概、構(gòu)成等,數(shù)據(jù)的最小組成單位。然后講述了數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)類型包括概念及定義,數(shù)據(jù)類型包括簡單數(shù)據(jù)類型和復(fù)雜數(shù)據(jù)。簡單數(shù)據(jù)類型有:整數(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),存儲結(jié)構(gòu)以及一組運算集合。數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本結(jié)構(gòu):集合性結(jié)構(gòu),線性結(jié)構(gòu),樹形結(jié)構(gòu),圖形結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)嚴(yán)肅在存儲器中的存儲方式包括順序存儲,鏈表存儲,索引存儲,散列存儲。然后介紹以前學(xué)習(xí)的C語言(及本教材的使用的算法描述工具)知識錦興路回顧包括指針、結(jié)構(gòu)比阿亮、函數(shù)、遞歸、動態(tài)存儲分配、文件操作等內(nèi)容。
第二章:順序表及其應(yīng)用主要介紹的是線性邏輯結(jié)構(gòu)的呼聲幾乎在順序存儲方法下的數(shù)據(jù)結(jié)構(gòu)順序標(biāo)的概念、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、基本運算及相關(guān)應(yīng)用問題。應(yīng)用一:查找介紹了兩種方法:簡單順序查找(從書序標(biāo)的一端來時掃描,將待查找元素與數(shù)據(jù)節(jié)點中的個元素比較。若相等,則查找成功,否則失。┖投植檎遥▽⒈碇虚g的記錄的關(guān)鍵字與給定的值比較,若相等,則成功。否則,將順序表風(fēng)味左右兩個字表,然后在子表中進(jìn)一步查找。)
應(yīng)用二:排序問題介紹了交換排序,選擇排序,插入排序,歸并排序。
1、插入排序
包括直接插入排序(將順序表分為左右兩個子表,左子表為有序表,右子表為無序表,將右子表中的元素插入左子表中)和希爾排序法(將整個待排序的元素序列分割成若干子序列,對每個子序列分別進(jìn)行直接插入排序,當(dāng)整個帶排序元素序列“基本有序時”,在進(jìn)行直接插入排序)2、交換排序
a)冒泡排序:兩輛比較待排序元素的關(guān)鍵字,發(fā)現(xiàn)相反時即進(jìn)行交換,知道沒有
逆序的元素為止。b)快速排序算法:在待排序的元素中選定一個“中間數(shù)”,將其他數(shù)據(jù)元素與該
數(shù)比較,將比其小的數(shù)據(jù)放道左子表中,比起大的放入右子表中。
3、選擇排序a)直接選擇排序:將數(shù)據(jù)進(jìn)行多談排序,每趟選出其中的最大數(shù)或最小數(shù)放在最終位置上,每趟中已排好的數(shù)不再參加下一輪的排序。b)堆排序:輸出堆頂元素將剩余元素按關(guān)鍵字大小重誠信排列成一個堆重復(fù)
上述2個步驟
4、歸并排序
將兩個或兩個以上的有序表合并成一個新的有序表。應(yīng)用三:字符處理問題
介紹了串和順序串的定義及相關(guān)概念,還有順序串的基本算法。
第三章:介紹鏈表。鏈表中數(shù)據(jù)元素的存儲不一定是連續(xù)的,還可以占用任意的、不連續(xù)的物理存儲區(qū)域。與順序表相比,鏈表的插入、刪除不需要移動元素,給算法的效率帶來較大的提高,且在存儲空間上有動態(tài)申請的優(yōu)點。這一章中介紹了鏈表的節(jié)點結(jié)構(gòu)、靜態(tài)與動態(tài)鏈表的概念、鏈表的基本運算(如求表長、插入、查找、刪除等)、單鏈表的建立(頭插法和尾插法)以及雙向循環(huán)鏈表的定義、結(jié)構(gòu)、功能和基本算法。弄清其個運算的算法思想及其時間復(fù)雜度和空間性能。最后介紹了鏈表之中存儲結(jié)構(gòu)在實際中的相關(guān)應(yīng)用。
a)單循環(huán)鏈表是一種首尾相接的單鏈表,終端結(jié)點的指針域指向開始結(jié)點或頭結(jié)點。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點是查找頭指針和尾指針的時間都是O(n),不用遍歷整個鏈表。
b)雙鏈表就是雙向鏈表,就是在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior,形成兩條不同方向的鏈。由頭指針head惟一確定。雙鏈表也可以頭尾相構(gòu)成雙循環(huán)鏈表。雙鏈表上的插入和刪除時間復(fù)雜度均為O(1)。
順序表和鏈表的比較
a)基本空間的考慮存儲密度是指節(jié)點數(shù)據(jù)本身所占的存儲量除以結(jié)點構(gòu)所占的存儲總
量所得的值。值越大存儲空間利用率越高。
順序表是靜態(tài)分配的,存儲密度為1,鏈表是動態(tài)分配的,存儲密度小于1。b)順序表適用于靜態(tài)查找,要進(jìn)行刪除和插入操作時,需移動大量結(jié)點。鏈表適用于做動態(tài)的插入和刪除。第四章:堆棧是運算受限制的線性結(jié)構(gòu)。其基本運算方法與順序表和鏈表運算方法基本相同,不同的是堆棧須遵循“先進(jìn)后出”的規(guī)則,對堆棧的操作只能在棧頂進(jìn)行;堆棧在文字處理,匹配問題和算術(shù)表達(dá)式的求值問題方面的應(yīng)用。
a)棧的基本運算有六種:構(gòu)造空棧:InitStack,判?眨篠tackEmpty,判棧滿:
StackFull,進(jìn)棧:Push,退棧:Pop,取棧頂元素:StackTopb)在順序棧中有“上溢”和“下溢”的現(xiàn)象!吧弦纭笔菞m斨羔樦赋鰲5耐饷媸浅鲥e狀態(tài)!跋乱纭笨梢员硎緱榭諚,因此用來作為控制轉(zhuǎn)移的條件。
c)順序棧中的基本操作有六種:構(gòu)造空棧,判棧空,判棧滿,進(jìn)棧,退棧,取棧頂元
素d)鏈棧則沒有上溢的限制,因此進(jìn)棧不要判棧滿。鏈棧不需要在頭部附加頭結(jié)點,只
要有鏈表的頭指針就可以了。e)鏈棧中的基本操作有五種:構(gòu)造空棧,判棧空,進(jìn)棧,退棧,取棧頂元素
第五章:隊列及其應(yīng)用,我們知道隊列是一種特殊的線性表,是一種具有線性邏輯結(jié)構(gòu)的數(shù)據(jù)元素的集合。而隊列的運算遵循“先進(jìn)后出”的原則,因此,隊列也是一個運算受限制的線性表。a)隊列的基本運算有六種:置空隊:InitQueue,判隊空:QueueEmpty,判隊滿:QueueFull,入隊:EnQueue,出隊:DeQueue,取隊頭元素:QueueFront
b)順序隊列的“假上溢”現(xiàn)象:由于頭尾指針不斷前移,超出向量空間。這時整個向
量空間及隊列是空的卻產(chǎn)生了“上溢”現(xiàn)象。為了克服“假上溢”現(xiàn)象引入循環(huán)向量的概念,是把向量空間形成一個頭尾相接的環(huán)形,這時隊列稱循環(huán)隊列。c)判定循環(huán)隊列是空還是滿,方法有2種:一種是另設(shè)一個標(biāo)志變量來判斷;第二種
是少用一個元素空間,入隊時先測試(q->rear%m=q->front?)滿:空。d)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列,一個鏈隊列就是一個操作受限的單鏈表。為了便
于在表尾進(jìn)行插入的操作,在表尾增加一個尾指針,一個鏈隊列就由一個頭指針和
一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。在鏈隊列的出隊算法中,要注意當(dāng)原隊中只有一個結(jié)點時,出隊后要同進(jìn)修改頭尾指針并使隊列變空。
第六章:介紹了特殊矩陣和廣義表的概念與應(yīng)用。其中,特殊矩陣包括對稱矩陣、三角矩陣、對角矩陣和稀疏矩陣,書中分別詳細(xì)介紹了它們的存儲結(jié)構(gòu)。其中三元組和十字鏈表這兩種
結(jié)構(gòu)尤為重要;對著兩種結(jié)構(gòu)的建立了應(yīng)用要掌握。稀疏矩陣的應(yīng)用包括轉(zhuǎn)置和加法運算等。最后介紹了廣義表的相關(guān)概念及存儲結(jié)構(gòu),關(guān)于它的應(yīng)用,課本中舉了m元多項式的表示問題。
第七章:二叉樹的知識是重點內(nèi)容。在介紹有關(guān)概念時,提到了二叉樹的性質(zhì)以及兩種特殊的二叉樹:完全二叉樹和滿二叉樹。接著介紹二叉樹的順序存儲和鏈接存儲以及生成算法。重點介紹二叉樹的遍歷算法(遞歸算法、先序、中序和后序遍歷非遞歸算法)和線索二叉樹。二叉樹的應(yīng)用:基本算法、哈夫曼樹、二叉排序樹和堆排序,其中關(guān)于二叉排序樹和哈弗曼書的構(gòu)建是重點。
a)兩種特殊的二叉樹:完全二叉樹(非葉子節(jié)點均有兩個孩子節(jié)點并且對于仍一層某
一節(jié)點有孩子節(jié)點,該層所有節(jié)點均有孩子節(jié)點)和滿二叉樹(在完全二叉樹上的基礎(chǔ)上最下層從左到右刪除若干個節(jié)點。)
b)二叉樹的5個重要性質(zhì)
c)根據(jù)結(jié)點的次序不同可得三種遍歷:先序遍歷,中序遍歷、后序遍歷。
d)二叉樹的應(yīng)用:基本算法、哈弗曼樹、二叉排序樹和堆排序
第八章:介紹了樹和森林。樹與二叉樹是不同的概念。教材介紹了樹和森林的概念、遍歷和存儲結(jié)構(gòu),還有樹、森林和二叉樹的相互關(guān)系,樹或森林怎樣轉(zhuǎn)化成二叉樹,二叉樹又如何轉(zhuǎn)換為樹和森林等算法。
第九章:散列結(jié)構(gòu)是一種查找效率很高的一種數(shù)據(jù)結(jié)構(gòu)。本章的主要知識點有:散列結(jié)構(gòu)的概念及其存儲結(jié)構(gòu)、散列函數(shù)、兩種沖突處理方法、線性探測散列和鏈地址散列的基本算法以及散列結(jié)構(gòu)的查找性能分析。
第十章:介紹了圖的概念及其應(yīng)用,是本書的難點。圖的存儲結(jié)構(gòu)的知識點有:鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識點有:有向圖、連通圖、生成樹和森林、最短路徑問題和有向無環(huán)圖及其應(yīng)用。有向無環(huán)圖重點理解AOV網(wǎng)和拓?fù)渑判蚣捌渌惴ā?/p>
心得體會以及建議:通過學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)與算法》我們可以設(shè)計出更好的算法,高效地組織數(shù)據(jù)。一個程序無論采用何種語言,其基本算法思想不會改變!败浖_發(fā)好比寫作文,計算機(jī)語言提供了許多華麗的辭藻,而數(shù)據(jù)結(jié)構(gòu)則考慮如何將這些辭藻組織成一篇優(yōu)秀的文章來!痹趯W(xué)習(xí)這門課中,要熟悉對算法思想的一些描述手段,包括文字描述、圖形描述和計算機(jī)語言描述等。因此,計算機(jī)語言基礎(chǔ)是必須的,因為它提供了一種重要的算法思想描述手段機(jī)器可識別的描述。
這門課結(jié)束之后,我總結(jié)了學(xué)習(xí)中遇到的一些問題,最為突出的,書本上的知識與老師的講解都比較容易理解,但是當(dāng)自己采用剛學(xué)的知識點編寫程序時卻感到十分棘手,有時表現(xiàn)在想不到適合題意的算法,有時表現(xiàn)在算法想出來后,只能將書本上原有的程序段謄寫到自己的程序中再加以必要的連接以完成程序的編寫。針對這一情況,我會嚴(yán)格要求自己,熟練掌握算法思想,盡量獨立完成程序的編寫與修改工作,只有這樣,才能夠提高運用知識,解決問題的能力。
教學(xué)的建議
1、建議在上課過程中加大隨堂練習(xí)的分量,以便學(xué)生能當(dāng)堂消化課堂上學(xué)習(xí)的知識,也便于及時了解學(xué)生對知識點的掌握情況,同時有助于學(xué)生保持良好的精神狀態(tài)。2、建議在課時允許的情況下,增加習(xí)題課的分量,通過課堂的習(xí)題講解,加深對知識點的掌握,同時對各知識點的運用有一個更為直觀和具體的認(rèn)識。
以上便是我對《數(shù)據(jù)結(jié)構(gòu)與算法》這門課的學(xué)習(xí)總結(jié),我會抓緊時間將沒有吃透的知識點補(bǔ)齊。今后我仍然會繼續(xù)學(xué)習(xí),克服學(xué)習(xí)中遇到的難關(guān),在打牢基礎(chǔ)的前提下向更深入的層面邁進(jìn)!
擴(kuò)展閱讀:數(shù)據(jù)結(jié)構(gòu)與算法課程學(xué)習(xí)總結(jié)報告
數(shù)據(jù)結(jié)構(gòu)與算法課程學(xué)習(xí)總結(jié)報告
計科系10級計本
一、數(shù)據(jù)結(jié)構(gòu)與算法知識點
《數(shù)據(jù)結(jié)構(gòu)與算法》這本書共有十一個章節(jié)。從第一章的數(shù)據(jù)結(jié)構(gòu)和算法的引入,介紹了數(shù)據(jù)和數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、算法描述工具、算法和算法評價四個方面的知識。第二章則介紹了順序表及其應(yīng)用的相關(guān)知識。從順序表的基本概念開始,分別介紹了順序表基本算法、順序表基本算法性能分析、順序表的應(yīng)用。順序表應(yīng)用又涉及多方面,有查找問題、排序問題、字符處理問題。其中查找分簡單順序查找,有序表的二分查找,分塊查找三種。排序中分插入排序(直接插入排序、希爾排序)、交換排序(冒泡排序、快速排序)、選擇排序(直接選擇排序)、歸并排序。第三章鏈表及其應(yīng)用,分為鏈表的基本概念、單鏈表的數(shù)據(jù)結(jié)構(gòu)、單鏈表的基本算法、循環(huán)鏈表、鏈表的應(yīng)用。第四章堆棧及其應(yīng)用,分為堆棧堆的基本概念、順序棧及其基本算法、鏈棧及其基本算法、堆棧的應(yīng)用。第五章隊列及其應(yīng)用,分為隊列的基本概念、順序隊列及其基本算法、鏈隊列及其基本算法、基數(shù)排序問題。第六章特殊矩陣和廣義表及其應(yīng)用,分為數(shù)組與矩陣,特殊矩陣的壓縮存儲、矩陣的應(yīng)用實例、廣義表。第七章二叉樹及其應(yīng)用。分為二叉樹的基本概念、二叉樹存儲結(jié)構(gòu)、二叉樹的遍歷算法、線索二叉樹、二叉樹的應(yīng)用(基本算法、哈夫曼樹、二叉排序樹、堆和堆排序)。第八章樹和森林及其應(yīng)用。分為樹和森林的基本概念,樹的存儲結(jié)構(gòu)、樹的基本算法及性能分析、樹的應(yīng)用(B樹)。第九章散列結(jié)構(gòu)及其應(yīng)用。分為散列結(jié)構(gòu)的概念等。著重學(xué)習(xí)了散列表、散列函數(shù)、沖突處理方法(開放定址法和鏈地址法)。第九章圖及其應(yīng)用。分為圖的概念、圖的存儲結(jié)構(gòu)及其基本算法、圖的遍歷及算法、有向圖的連通性和最小生成樹、圖的最小生成樹、非連通圖的生成森林算法、最短路徑、有向無環(huán)圖及其應(yīng)用。第十一章算法性能分析和算法設(shè)計方法簡介。
二、對各知識點的掌握情況
綜合以上知識點,我對自我學(xué)習(xí)成果作如下總結(jié):對于第一章對數(shù)據(jù)結(jié)構(gòu)的概念理解頗深,大概是每次都要談?wù)摰桨伞λ惴ǖ臅r間性能,空間性能基本了解。這些在后面的章節(jié)都會有運用。第二章順序表較為清晰。如何去建一個順序表,順序表的一些基本算法都可以很好運用。在順序表應(yīng)用中對二分查找映象深刻。對于排序能了解其算法思想。對字符串的處理應(yīng)用的較少,沒有深入了解。第三章鏈表的知識,由于鏈表在上學(xué)期就有所接觸,老師也強(qiáng)調(diào)其作用,對鏈表掌握還好,但在第三章中又學(xué)習(xí)到了新的內(nèi)容,對其數(shù)據(jù)結(jié)構(gòu)進(jìn)行了分析,增加了循環(huán)鏈表,對知識進(jìn)行補(bǔ)充。第四章堆棧,堆棧是一個運算受限的線性表,可對比順序表的學(xué)習(xí),不同的是還有鏈棧,這部分感覺是全書最容易的部分了。第五章隊列是接著堆棧之后的又一個運算受限制的線性表,感覺和堆棧一樣簡單。第六章矩陣和廣義表是我的弱項,在這部分的學(xué)習(xí)過程中沒有用心學(xué),現(xiàn)在正在深入研究。接下來的第七章第八章是全書的重點,特別是第七章二叉樹,所以學(xué)習(xí)的重心也偏向這兩章。對二叉樹掌握較好,其概念,存儲,遍歷有很好的掌握。就是對二叉排序樹有點生疏,它的生成算法不是很會。第八章樹和森林,樹與二叉樹之間的轉(zhuǎn)換,森林與二叉樹的轉(zhuǎn)換算法思想基本掌握。第九章散列的一些知識,沒有深入學(xué)習(xí),大概了解了散列存儲結(jié)構(gòu)散列表,散列函數(shù),沖突的處理方法。第十章感覺是很難的一章,知識點多,能夠畫有向圖和無向圖的鄰接矩陣,鄰接表。圖的深度遍歷和廣度遍歷,但是其算法只是能讀懂。三、學(xué)習(xí)體會
開學(xué)伊始,聽說要學(xué)數(shù)據(jù)結(jié)構(gòu)與算法,而且考試通過率極低,就帶著這樣恐懼的心理開始學(xué)習(xí)了。通過學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法讓我對程序有了新的認(rèn)識。“數(shù)據(jù)結(jié)構(gòu)和算法”課程主要學(xué)習(xí)在軟件開發(fā)中涉及到的各種常用數(shù)據(jù)結(jié)構(gòu)及其常用算法,在此基礎(chǔ)上,學(xué)習(xí)如何利用數(shù)據(jù)結(jié)構(gòu)和算法解決一些基本的應(yīng)用問題,通過學(xué)習(xí)我了解了相關(guān)領(lǐng)域的基礎(chǔ)知識和基本應(yīng)用。知道了學(xué)習(xí)一種數(shù)據(jù)結(jié)構(gòu)必須掌握該數(shù)據(jù)結(jié)構(gòu)的定義,其包括邏輯結(jié)構(gòu),存儲結(jié)構(gòu)和基本算法還有基本應(yīng)用知識。對于一個應(yīng)用程序,不是它能運行,能顯示結(jié)果就行了,還要考慮它的各方面的性能,時間性能,空間性能。以此節(jié)約空間和時間。給定一個程序首先要分析其應(yīng)有的數(shù)據(jù)結(jié)構(gòu)。怎么存儲,怎么性能會比較好!皵(shù)據(jù)結(jié)構(gòu)與算法”是一門很有用的科目,可是也是很令人頭疼的學(xué)科,這也鍛煉了我們迎難而上的毅力。當(dāng)然學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法是建立在學(xué)習(xí)好計算機(jī)語言的基礎(chǔ)上的,學(xué)習(xí)編程是枯燥無味的,學(xué)據(jù)結(jié)構(gòu)給我?guī)砀嗟氖撬伎嫉臇|西。
課程結(jié)束我總結(jié)了學(xué)習(xí)過程中遇到的困難,有時寫不出合條件的算法,在寫實驗報告時,有時就是將書上的源程序搬上去,對程序進(jìn)行一些修改。針對這一情況我會慢慢改正。多加思考。
四、對課程教學(xué)的建議
1、課程課時較緊,課堂上的練習(xí)時間較少,講解的東西越多,頭腦有時就很混亂。2、長期的ppt教學(xué),會使產(chǎn)生疲勞,稍不留神,思維開了小差,就跟不上了。可以適當(dāng)結(jié)合ppt和例題講解。。通過課堂的習(xí)題講解,加深對知識點的掌握,同時對各知識點的運用有一個更為直觀和具體的認(rèn)識。
友情提示:本文中關(guān)于《“數(shù)據(jù)結(jié)構(gòu)與算法”課程學(xué)習(xí)總結(jié)報告》給出的范例僅供您參考拓展思維使用,“數(shù)據(jù)結(jié)構(gòu)與算法”課程學(xué)習(xí)總結(jié)報告:該篇文章建議您自主創(chuàng)作。
來源:網(wǎng)絡(luò)整理 免責(zé)聲明:本文僅限學(xué)習(xí)分享,如產(chǎn)生版權(quán)問題,請聯(lián)系我們及時刪除。