人的記憶力會隨著歲月的流逝而衰退,寫作可以彌補記憶的不足,將曾經(jīng)的人生經(jīng)歷和感悟記錄下來,也便于保存一份美好的回憶。相信許多人會覺得范文很難寫?以下是小編為大家收集的優(yōu)秀范文,歡迎大家分享閱讀。
數(shù)據(jù)結(jié)構(gòu)與算法分析推薦書籍篇一
100401200510計本(4)班章興春
本學期所學習的《數(shù)據(jù)結(jié)構(gòu)與算法》課程已經(jīng)告一段落,就其知識點及其掌握情況、學習體會以及對該門課程的教學建議等方面進行學習總結(jié)。以便在所學習知識有更深刻的認識。
一、《數(shù)據(jù)結(jié)構(gòu)與算法》知識點:
學習數(shù)據(jù)結(jié)構(gòu)之前、一直以為數(shù)據(jù)結(jié)構(gòu)是一門新的語言、后來才知道學習數(shù)據(jù)結(jié)構(gòu)是為了更加高效的的組織數(shù)據(jù)、設計出良好的算法,而算法則是一個程序的靈魂。經(jīng)過了一學期的數(shù)據(jù)結(jié)構(gòu)了,在期末之際對其進行總結(jié)。首先,學完數(shù)據(jù)結(jié)構(gòu)我們應該知道數(shù)據(jù)結(jié)構(gòu)講的是什么,數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的研究的程序設計問題中所出現(xiàn)的計算機處理對象以及它們之間關系和操作的學科。
第一章主要介紹了相關概念,如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型以及數(shù)據(jù)結(jié)構(gòu)的定義。其中,數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算集合。邏輯結(jié)構(gòu)分為四類:集合型、線性、樹形和圖形結(jié)構(gòu),數(shù)據(jù)元素的存儲結(jié)構(gòu)分為:順序存儲、鏈接存儲、索引存儲和散列存儲四類。最后著重介紹算法性能分析,包括算法的時間性能分析以及算法的空間性能分析。
第二章具體地介紹了順序表的定義、特點及其主要操作,如查找、插入和刪除的實現(xiàn)。需要掌握對它們的性能估計。包括查找算法的平均查找長度,插入與刪除算法中的對象平均移動次數(shù)。
鏈表中數(shù)據(jù)元素的存儲不一定是連續(xù)的,還可以占用任意的、不連續(xù)的物理存儲區(qū)域。與順序表相比,鏈表的插入、刪除不需要移動元素,給算法的效率帶來較大的提高。鏈表這一章中介紹了鏈表的節(jié)點結(jié)構(gòu)、靜態(tài)與動態(tài)鏈表的概念、鏈表的基本運算(如求表長、插入、查找、刪除等)、單鏈表的建立(頭插法和尾插法)以及雙向循環(huán)鏈表的定義、結(jié)構(gòu)、功能和基本算法。
第三章介紹了堆棧與隊列這兩種運算受限制的線性結(jié)構(gòu)。其基本運算方法與順序表和鏈表運算方法基本相同,不同的是堆棧須遵循“先進后出”的規(guī)則,對堆棧的操作只能在棧頂進行;而隊列要遵循“先進先出”的規(guī)則,教材中列出了兩種結(jié)構(gòu)的相應算法,如入棧、出棧、入隊、出隊等。在介紹隊列時,提出了循環(huán)隊列的概念,以避免“假溢出”的現(xiàn)象。算法上要求掌握進棧、退棧、取棧頂元素、判棧空盒置空棧等五種操作及掌握使用元素個數(shù)計數(shù)器及少用一個元素空間來區(qū)分隊列空、隊列滿的方法。
第四章串和數(shù)組中,我們知道串是一種特殊的線性表,是由零個或多個任意字符組成的字符序列。串的儲存結(jié)構(gòu)分為緊縮模式和非緊縮模式。
基本運算需掌握求串長、串賦值、連接操作、求子串、串比較、串定位、串插入、串刪除、串替換等。
第五章二叉樹的知識是重點內(nèi)容。在介紹有關概念時,提到了二叉樹的性質(zhì)以及兩種特殊的二叉樹:完全二叉樹和滿二叉樹。接著介紹二叉樹的順序存儲和鏈接存儲以及生成算法。重點介紹二叉樹的遍歷算法(遞歸算法、先序、中序和后序遍歷非遞歸算法)和線索二叉樹。二叉樹的應用:基本算法、哈弗曼樹、二叉排序樹和堆排序。
樹與二叉樹是不同的概念。教材介紹了樹和森林的概念、遍歷和存儲結(jié)構(gòu),還有樹、森林和二叉樹的相互關系,樹或森林怎樣轉(zhuǎn)化成二叉樹,二叉樹又如何轉(zhuǎn)換為樹和森林等算法。
第六章介紹了圖的概念及其應用,圖的存儲結(jié)構(gòu)的知識點有:鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識點有:有向圖、連通圖、生成樹和森林、最短路徑問題和有向無環(huán)圖及其應用。有向無環(huán)圖重點理解aov網(wǎng)和拓撲排序及其算法。
最后兩章集體說明了查找和排序算法,查找教材上介紹了靜態(tài)查找表和哈希查找表,靜態(tài)查找表中介紹了順序查找、折半查找以及分塊查找。哈希法中,學習要點包括哈希函數(shù)的比較;解決地址沖突的線性探查法的運用,平均探查次數(shù);解決地址沖突的二次哈希法的運用。
排序是使用最頻繁的一類算法,可分為內(nèi)部排序和外部排序。主要需要理解排序的基本概念,在算法上、需要掌握插入排序(包括直接插入排序算法、折半插入排序算法),交換排序(包括冒泡排序算法、快速排序遞歸算法),選擇排序(包括直接選擇排序算法、堆排序算法)等。
二、對各知識點的掌握情況
總體來看,對教材中的知識點理解較為完善,但各個章節(jié)均出現(xiàn)有個別知識點較為陌生的現(xiàn)象。現(xiàn)將各個章節(jié)出現(xiàn)的知識點理解情況列舉如下。
第一章中我對數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)的概念理解較為透徹,熟悉數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。而對算法的時間、空間性能分析較為模糊,尤其是空間性能分析需要加強。
第二章,順序表的概念、生成算法理解較為清晰,并且熟悉簡單順序查找和二分查找,對分塊查找較為含糊;排序問題中,由于冒泡排序在大一c語言課上已經(jīng)學習過,再來學習感覺很輕松。對插入排序和選擇排序理解良好,但是,在實際運用中仍然出現(xiàn)明顯不熟練的現(xiàn)象。由于在歸并排序?qū)W習中感覺較吃力,現(xiàn)在對這種排序方法仍然非常模糊,所以需要花較多的時間來補習。此外串的模式匹配也是較難理解的一個地方。
鏈表這一章中,除對雙向循環(huán)鏈表這一知識點理解困難之外,其他的知識點像單鏈表的建立和基本算法等都較為熟悉。
接下來的有關堆棧以及隊列的知識點比較少,除有關算法較為特殊以外,其余算法都是先前學過的順序表和鏈表的知識,加上思想上較為重視,因此這部分內(nèi)容是我對全書掌握最好的一部分。不足之處仍然表現(xiàn)在算法的性能分析上。
在學習第六章時感覺較為吃力的部分在于矩陣的應用上,尤其對矩陣轉(zhuǎn)置算法的c語言描述不太理解。稀疏矩陣相加算法中,用三元組表實現(xiàn)比較容易理解,對十字鏈表進行矩陣相加的方法較為陌生。
第七章是全書的重點,卻也有一些內(nèi)容沒有完全理解。在第一節(jié)基本概念中,二叉樹的性質(zhì)容易懂卻很難記憶。對二叉樹的存儲結(jié)構(gòu)和遍歷算法這部分內(nèi)容掌握較好,能夠熟練運用,而對于二叉樹應用中的哈弗曼樹卻比較陌生。
第八章內(nèi)容較少,牽涉到所學的隊列的有關內(nèi)容,總體來說理解上沒有什么困難,問題依舊出現(xiàn)在算法的性能分析上。
散列結(jié)構(gòu)這一章理解比較完善的知識點有:基本概念和存儲結(jié)構(gòu)。散列函數(shù)中直接定址法和除留余數(shù)法學得比較扎實,對數(shù)字分析法等方法則感覺較為陌生。對兩種沖突處理的算法思想的理解良好,問題在于用c語言描述上。
最后一章,圖及其應用中,圖的定義、基本運算如圖的生成等起初理解有困難,但隨著學習深入,對它的概念也逐步明朗起來。鄰接矩陣、鄰接表和逆鄰接表掌握較好,而對十字鏈表和鄰接多重表則較為陌生。感覺理解較為吃力的內(nèi)容還有圖的遍歷(包括深度和廣度優(yōu)先遍歷),最小生成樹問題也是比較陌生的知識點。最短路徑和aov網(wǎng)學習起來感覺比較輕松,而對于c語言描述卻又不大明白。
由于平時上機練習的少,對于教材中很多算法都掌握的不是很熟悉、不過這些都是可以彌補的,我會在剩下的時間中不斷練習書上給出的算法和練習,正如教材上說的,學習數(shù)據(jù)結(jié)構(gòu),僅從書本上學習是不夠的,必須經(jīng)過大量的程序設計實踐,在實踐中體會構(gòu)造性思維方法,掌握數(shù)據(jù)組織與程序設計技術(shù)。
三、學習體會:
多做實驗!這個就沒有太多理由了,我一直覺得編程是一門熟練科學,多編程,水平肯定會提高,最重要的是能夠養(yǎng)成一種感覺,就是對程序?qū)λ惴ǖ拿舾校瑸槭裁茨切┡H丝匆粋€算法一下子就看懂了?而自己要看很久才能弄懂,而且弄懂了過了一陣子又忘記了?其實這個是因為牛人們以前看的程序很多,編得也很多,所以他們有了那種感覺,所以我覺得大家應該多看程序,多寫程序,培養(yǎng)自己的感覺。
復習和考試的技巧,我想大家應該都有這樣的感覺,就是覺得自己什么都掌握了,但是在考試的時候就是會犯暈,有時候一出考場就知道錯在哪個了,然后考完以后一對答案,發(fā)現(xiàn)其實考得很簡單,應該都是自己會做的,這個就是與自己的復習和考試的技巧有關系了。
首先就是復習,前面已經(jīng)說過其實我們學的算法也就是幾十個,那么我們的任務也就是理解這幾十個算法,復習也就是要加深你的理解。如何理解算法,然后理解到什么程度呢? 是能默出整個算法嗎?其實不是這樣的,數(shù)據(jù)結(jié)構(gòu)的考試有它的特點,考過程考試了,大家應該都發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)其實不要求你把整個算法背出來,它注重考察你的理解,那么怎么考察呢?其實也就是兩種方式吧,一種就是用實例,就是給你一個例子,要你用某個算法運行出結(jié)果,我想這個期末考試的時候仍然會有很多這樣的題目,比如排序那塊就很好出這樣的題目,要復習這種題目我覺得很簡單,就是每個算法都自己用例子去實踐一下,以不變應萬變,我期中復習的時候就是這樣去做的,而且考試之前我就覺得那個并查集的題目就很有可能會考,于是就自己出了幾個例子,做了一下。另外一種考察方式就是算法填空和算法改錯,可能有一些同學覺得這種題目很難,其實我們首先可以確定這兩種題目肯定是與書上算法有關系的,只要理解了書上的算法就可以了,有人覺得看完書以后什么都懂了,而且要默也默得出來,其實不是這樣的,算法改錯和填空主要是考察的細微處,雖然你覺得你默得出來,那是能夠默出算法的主體部分,很多細微的地方你就會很容易忽略。我想大家考過期中考以后應該都有這種感覺吧?那要怎樣解決這種問題呢? 我覺得有兩種方法,一種就是自己去編程實現(xiàn),這種方法比較有意義,還能夠提高編程水平,另外一種就是用實例分析算法的每句話,我認為這種方法是最有效的。
然后還有一種題目,就是最后的寫算法的題目,我覺得這種題目還是很好解決的,只要是能夠自己做出作業(yè)的,基本上都會很容易做出來,這也是為什么我前面覺得平時做作業(yè)應該自己獨立思考的原因,同時做這種題目千萬要小心,尤其是題目簡單的時候,那肯定會有一些小地方要考慮清楚,一不小心就會被扣掉很多分,這樣很不值。
我覺得考試的時候沒有太多要講的,只要復習好了,考試的時候細心一點就可以了,然后就是做一個題目開始就要盡量保證正確,如果覺得留在那里等后面做完了再來檢查,這樣錯誤還是很有可能檢查不出來,我期中考試的時候就基本上沒有檢查,因為我做每個題目都是確保正確,用的時間也挺多的,然后也覺得沒有檢查的必要了。
三、對《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學的建議
1、建議在上課過程中加大隨堂練習的分量,以便學生能當堂消化課堂上學習的知識,也便于及時了解學生對知識點的掌握情況,同時有助于學生保持良好的精神狀態(tài)。
2、建議在課時允許的情況下,增加習題課的分量,通過課堂的習題講解,加深對知識點的掌握,同時對各知識點的運用有一個更為直觀和具體的認識。
3、要更加重視實驗的重要性。
以上便是我對《數(shù)據(jù)結(jié)構(gòu)與算法》這門課的學習總結(jié),我會抓緊時間將沒有吃透的知識點補齊。今后我仍然會繼續(xù)學習,克服學習中遇到的難關,在打牢基礎的前提下向更深入的層面邁進!
數(shù)據(jù)結(jié)構(gòu)與算法分析推薦書籍篇二
《數(shù)據(jù)結(jié)構(gòu)與算法》推薦信
美國uiuc大學博士生梅俏竹
數(shù)據(jù)結(jié)構(gòu)是美國所有一流計算機系的本科核心課程之一,上承計算引論與初級程序設計,下啟高級算法和計算理論,向來是計算機本科教學的重中之重。我在北大上過的諸多本科基礎課中,無論從課程內(nèi)容和老師教學下的功夫來看,張銘老師的”數(shù)據(jù)結(jié)構(gòu)與算法”課程都是首屈一指的。可以說,將北大的數(shù)據(jù)結(jié)構(gòu)與算法課程,無論其內(nèi)容覆蓋面,前瞻性,難易程度,以及學生的工作量,都并不遜色于國外一流計算機系的同名課程。
舉個例子,記得當年數(shù)據(jù)結(jié)構(gòu)的大實習作業(yè)是設計并實現(xiàn)一個簡單的搜索引擎。這并不容易。從頭到尾所有的模塊,包括網(wǎng)頁抓取,內(nèi)容提取,索引和信息檢索都需要自己設計和完成,幾乎沒有現(xiàn)成的工具可以利用。用業(yè)內(nèi)的俗語說就是”build a search engine from the scratch”,這換成uiuc計算機系的學生來講也是很值得驕傲的事情。按計算機行業(yè)的慣例來說,業(yè)界最熱門最前沿的問題出現(xiàn)在課堂上是有一個明顯滯后的。而當時只不過是2000年,現(xiàn)在搜索引擎的巨頭google遠未上市,百度則剛剛成立,微軟和雅虎甚至還沒開始研發(fā)自己的搜索引擎。北大的本科生課程實習就能有這樣的前瞻性的問題絕對是值得稱道的。我在uiuc的所有師兄師弟,沒有別人在本科課程中有同樣的經(jīng)歷。我自己的研究工作也從這個經(jīng)歷中受益良多。
和我合作這個實習題目的同學,現(xiàn)在在yahoo公司santa clara的搜索組做工程師。我們同班的同學們,有不少去了google, yahoo和microsoft從事搜索和數(shù)據(jù)挖掘相關的研究與開發(fā)工作。和他們交談中,大家都不約而同地提到數(shù)據(jù)結(jié)構(gòu)這門課程對自己的影響。歸結(jié)起來,大家都認為張銘老師的“數(shù)據(jù)結(jié)構(gòu)與算法課程”內(nèi)容細致實用,講授深入淺出,課程實習精巧而具前瞻性,對培養(yǎng)學生分析和解決問題,創(chuàng)造性思考,和團隊合作的能力都有很好的作用。祝張老師的《數(shù)據(jù)結(jié)構(gòu)與算法》成功當選北京市精品課程。
推薦人梅俏竹
2008年4月15日
推薦人簡介:
梅俏竹,1999-2003就讀于北京大學計算機系,獲學士學位。
2004至今就讀于全美專業(yè)排名第5的uiuc計算機系,師從著名的信息檢索專家翟成祥(chengxiang zhai)教授,作為第一作者已發(fā)表論文十多篇,都發(fā)表sigkdd、sigir、www等一流國際會議和acm transactions on knowledge discovery from data期刊。梅俏竹是首屆yahoo!fellowship全美五名獲得者之一,曾獲kdd 2006,2007 最佳學生論文獎第二名。
數(shù)據(jù)結(jié)構(gòu)與算法分析推薦書籍篇三
金陵科技學院實驗報告
學 生 實 驗 報 告 冊
課程名稱:
學生學號:
所屬院部:計算機工程學院
(理工類)
算法與數(shù)據(jù)結(jié)構(gòu) 專業(yè)班級: 計算機統(tǒng)招(1)班
1413101006 學生姓名: 邢亦波
指導教師: 徐永華 15 ——20 16 學年 第 2 學期
金陵科技學院教務處制
金陵科技學院實驗報告
實驗報告書寫要求
實驗報告原則上要求學生手寫,要求書寫工整。若因課程特點需打印的,要遵照以下字體、字號、間距等的具體要求。紙張一律采用a4的紙張。
實驗報告書寫說明
實驗報告中一至四項內(nèi)容為必填項,包括實驗目的和要求;實驗儀器和設備;實驗內(nèi)容與過程;實驗結(jié)果與分析。各院部可根據(jù)學科特點和實驗具體要求增加項目。
填寫注意事項
(1)細致觀察,及時、準確、如實記錄。(2)準確說明,層次清晰。
(3)盡量采用專用術(shù)語來說明事物。
(4)外文、符號、公式要準確,應使用統(tǒng)一規(guī)定的名詞和符號。(5)應獨立完成實驗報告的書寫,嚴禁抄襲、復印,一經(jīng)發(fā)現(xiàn),以零分論處。
實驗報告批改說明
實驗報告的批改要及時、認真、仔細,一律用紅色筆批改。實驗報告的批改成績采用百分制,具體評分標準由各院部自行制定。
實驗報告裝訂要求
實驗批改完畢后,任課老師將每門課程的每個實驗項目的實驗報告以自然班為單位、按學號升序排列,裝訂成冊,并附上一份該門課程的實驗大綱。
金陵科技學院實驗報告
實驗項目名稱: 順序表 實驗學時: 2 同組學生姓名: 無 實驗地點: 實驗日期: 04.05 實驗成績: 批改教師: 徐永華 批改時間:
金陵科技學院實驗報告
實驗1 順序表
一、實驗目的和要求
掌握順序表的定位、插入、刪除等操作。
二、實驗儀器和設備
turbo c 2.0
三、實驗內(nèi)容與過程(含程序清單及流程圖)
1、必做題
(1)編寫程序建立一個順序表,并逐個輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測試結(jié)果。
(2)編寫順序表定位操作子函數(shù),在順序表中查找是否存在數(shù)據(jù)元素x。如果存在,返回順序表中和x值相等的第1個數(shù)據(jù)元素的序號(序號從0開始編號);如果不存在,返回-1。編寫主函數(shù)測試結(jié)果。(3)在遞增有序的順序表中插入一個新結(jié)點x,保持順序表的有序性。
解題思路:首先查找插入的位置,再移位,最后進行插入操作;從第一個元素開始找到第一個大于該新結(jié)點值x的元素位置i即為插入位置;然后將從表尾開始依次將元素后移一個位置直至元素i;最后將新結(jié)點x插入到i位置。
(4)刪除順序表中所有等于x的數(shù)據(jù)元素。
2、選做題
(5)已知兩個順序表a和b按元素值遞增有序排列,要求寫一算法實現(xiàn)將a和b歸并成一個按元素值遞減有序排列的順序表(允許表中含有值相同的元素)。
金陵科技學院實驗報告
程序清單: 1.(1)
#include
#define maxsize 100 #define datatype int typedef struct shun { datatype a[maxsize];int length;}shun;shun s;void init(shun *s){ } void setup(shun *s){
} void display(shun *s){} main()int i;if(s->length==0)printf(“沒有數(shù)據(jù)n”);else for(i=0;i
length;i++){ } printf(“%-5d”,s->a[i]);int i,j;printf(“需要幾個數(shù)n”);scanf(“%d”,&s->length);while(s->length>=maxsize){ printf(“需要幾個數(shù)n”);scanf(“%d”,&s->length);} for(i=0;i
length;i++){ } scanf(“%d”,&s->a[i]);s->length=0;printf(“溢出n”);
金陵科技學院實驗報告{
} init(&s);setup(&s);display(&s);
1.(2)
#include
#define maxsize 100 #define datatype int typedef struct shun { datatype a[maxsize];int length;}shun;shun s;void init(shun *s){ } void setup(shun *s){
} int find(shun *s,int x){ int i;for(i=0;ilength;i++){ int i,j;printf(“需要幾個數(shù)n”);scanf(“%d”,&s->length);while(s->length>=maxsize){ printf(“需要幾個數(shù)n”);scanf(“%d”,&s->length);} for(i=0;i
length;i++){ } scanf(“%d”,&s->a[i]);s->length=0;printf(“溢出n”);
金陵科技學院實驗報告if(s->a[i]==x)return i;} return 0;} void display(shun *s){
} main(){
} int x;init(&s);setup(&s);display(&s);printf(“輸入xn”);scanf(“%d”,&x);if(find(&s,x))printf(“找到位置是%dn”, find(&s,x));printf(“-1n”);else int i;if(s->length==0)printf(“沒有數(shù)據(jù)n”);else for(i=0;i
length;i++){ } printf(“%-5d”,s->a[i]);
1.(3)#include#define maxsize 100 #define datatype int typedef struct shun { datatype a[maxsize];int length;}shun;shun s;void init(shun *s){ s->length=0;
金陵科技學院實驗報告} void setup(shun *s){
} void insert(shun *s,int x){ int i,j;if((s->length+1)>=maxsize){ printf(“溢出n”);exit(0);int i,j;printf(“需要幾個數(shù)n”);scanf(“%d”,&s->length);while(s->length>=maxsize){ printf(“需要幾個數(shù)n”);scanf(“%d”,&s->length);} for(i=0;i
length;i++){ } scanf(“%d”,&s->a[i]);printf(“溢出n”);} for(i=0;i
length;i++){ if(s->a[i]>=x)break;} for(j=s->length-1;j>=i;j--){ s->a[j+1]=s->a[j];} s->a[i]=x;s->length++;} void display(shun *s){
int i;if(s->length==0)printf(“沒有數(shù)據(jù)n”);else for(i=0;ilength;i++)
金陵科技學院實驗報告} main(){
} int x;init(&s);setup(&s);printf(“輸入xn”);scanf(“%d”,&x);insert(&s,x);display(&s);{ } printf(“%-5d”,s->a[i]);
1.(4)#include
#define maxsize 100 #define datatype int typedef struct shun { datatype a[maxsize];int length;}shun;shun s;void init(shun *s){ } void setup(shun *s){
int i,j;printf(“需要幾個數(shù)n”);scanf(“%d”,&s->length);while(s->length>=maxsize){ printf(“需要幾個數(shù)n”);scanf(“%d”,&s->length);s->length=0;printf(“溢出n”);金陵科技學院實驗報告
} void delet(shun *s,int x){ int i,j;for(i=0;i
length;i++){
} void display(shun *s){} main(){
} int x;init(&s);setup(&s);printf(“輸入xn”);scanf(“%d”,&x);delet(&s,x);display(&s);int i;if(s->length==0)printf(“沒有數(shù)據(jù)n”);else for(i=0;i
length;i++){ } printf(“%-5d”,s->a[i]);if(s->a[i]==x){
for(j=i;jlength;j++){ s->a[j]=s->a[j+1];} s->length--;i--;} for(i=0;i
length;i++){ } scanf(“%d”,&s->a[i]);} }
金陵科技學院實驗報告2.#include
#define maxsize 100 #define datatype int typedef struct shun { datatype a[maxsize];int length;}shun;shun a,b,c;void init(shun *s){ } void setup(shun *s){
} } int i,j,t;printf(“需要幾個數(shù)n”);scanf(“%d”,&s->length);while(s->length>=maxsize){ printf(“需要幾個數(shù)n”);scanf(“%d”,&s->length);} for(i=0;ilength;i++){ } for(i=0;i
length;i++){
for(j=i+1;jlength;j++){
} if(s->a[i]a[j]){
} t=s->a[i];s->a[j]=t;s->a[i]=s->a[j];scanf(“%d”,&s->a[i]);s->length=0;printf(“溢出n”);金陵科技學院實驗報告
void cat(shun *a,shun *b){ int i,j=0,t;if((a->length+b->length)>=maxsize){
} for(i=0;ilength;i++){ } for(j=0;j
length;j++){
} =a->length+b->length;} void display(shun *s){
} int i;if(s->length==0)printf(“沒有數(shù)據(jù)n”);else for(i=0;i
length;i++){ } printf(“%-5d”,s->a[i]);} for(i=0;i
for(j=i+1;j
} if(c.a[i]
} t=c.a[i];c.a[j]=t;c.a[i]=c.a[j];c.a[i]=b->a[j];i++;c.a[i]=a->a[i];printf(“溢出n”);exit(0);
金陵科技學院實驗報告
main(){
} init(&a);printf(“a初始化n”);setup(&a);init(&b);setup(&b);cat(&a,&b);display(&c);printf(“b初始化n”);
金陵科技學院實驗報告
四、實驗結(jié)果與分析(程序運行結(jié)果及其分析)1.(1)
1.(2)
金陵科技學院實驗報告
1.(3)
1.(4)
金陵科技學院實驗報告
2.金陵科技學院實驗報告
五、實驗體會(遇到問題及解決辦法,編程后的心得體會)
我覺得編程不能只要完成其主要功能就行了,還要考慮到邊界值,考慮是否會出錯等等。有時候一種方法編不通,不如換種方法編。我覺得編程挺考慮耐心的,恩,就這么多感悟了。
金陵科技學院實驗報告
實驗項目名稱: 單鏈表 實驗學時: 2 同組學生姓名: 實驗地點: 實驗日期: 實驗成績: 批改教師: 批改時間:
金陵科技學院實驗報告
實驗2 單鏈表
一、實驗目的和要求
1、實驗目的
掌握單鏈表的定位、插入、刪除等操作。
2、實驗要求
(1)注意鏈表的空間是動態(tài)分配的,某結(jié)點不用之后要及時進行物理刪除,以便釋放其內(nèi)存空間。
(2)鏈表不能實現(xiàn)直接定位,一定注意指針的保存,防止丟失。
二、實驗儀器和設備
turbo c 2.0
三、實驗內(nèi)容與過程(含程序清單及流程圖)
1、必做題
(1)編寫程序建立一個單鏈表,并逐個輸出單鏈表中所有數(shù)據(jù)元素。(2)在遞增有序的單鏈表中插入一個新結(jié)點x,保持單鏈表的有序性。
解題思路:首先查找插入的位置然后進行插入操作;從第一個結(jié)點開始找到第一個大于該新結(jié)點值的結(jié)點即為插入位置;然后在找到的此結(jié)點之前插入新結(jié)點;注意保留插入位置之前結(jié)點的指針才能完成插入操作。
(3)編寫實現(xiàn)帶頭結(jié)點單鏈表就地逆置的子函數(shù),并編寫主函數(shù)測試結(jié)果。
2、選做題
已知指針la和lb分別指向兩個無頭結(jié)點單鏈表的首元結(jié)點。要求編一算法實現(xiàn),從表la中刪除自第i個元素起共len個元素后,將它們插入到表lb中第j個元素之前。程序清單:
1.(1)
#include
#define datatype char typedef struct lnklist { datatype a;struct lnklist *next;}list;list *s;list *setup(list *s)
金陵科技學院實驗報告{
} void display(list *head){ list *rear;if(head==null){
} } main(){
list *head;head=setup(s);display(head);free(s);rear=head;printf(“%c”,rear->a);while(rear->next!=null){
} rear=rear->next;printf(“%c”,rear->a);printf(“沒有數(shù)據(jù)n”);else list *head=null;list *rear=null;
char c;printf(“請輸入c直到$n”);c=getchar();while(c!='$'){
} if(rear!=null)rear->next=null;return head;s=malloc(sizeof(list));s->a=c;if(head==null){ } else rear->next=s;rear=s;c=getchar();head=s;
金陵科技學院實驗報告
} free(head);1.(2)#include
#define datatype char typedef struct lnklist { datatype a;struct lnklist *next;}list;list *s;list *setup(list *s){
} void paixu(list *head){list *rear;list *p;datatype min;if(head==null){ list *head=null;list *rear=null;
char c;printf(“請輸入c直到$n”);c=getchar();while(c!='$'){
} if(rear!=null)rear->next=null;return head;s=malloc(sizeof(list));s->a=c;if(head==null){ } else rear->next=s;rear=s;c=getchar();head=s;
金陵科技學院實驗報告
} void insert(list *head,datatype x){
list *p;list *q;list *r;if(head==null)printf(“空表n”);p=head;q=head;r=malloc(sizeof(list));r->a=x;while(p->next!=null){
} while(q->next!=p)q=q->next;r->next=p;q->next=r;if(p->next==null)if(x
a){ } p=p->next;break;} p=head;
while(p->next!=null){
do {
rear=rear->next;if(min>rear->a){
} min=rear->a;rear->a=p->a;p->a=min;
min=p->a;rear=p;printf(“空表!n”);exit(0);} while(rear->next!=null);p=p->next;}
金陵科技學院實驗報告
} void display(list *head){ list *rear;if(head==null){
} } main(){
} datatype x,c;list *head;head=setup(s);paixu(head);printf(“請輸入xn”);c=getchar();x=getchar();insert(head,x);display(head);free(s);free(head);rear=head;printf(“%c”,rear->a);while(rear->next!=null){
} rear=rear->next;printf(“%c”,rear->a);printf(“沒有數(shù)據(jù)n”);else p->next=r;1.(3)#include
#define datatype char typedef struct lnklist { datatype a;struct lnklist *next;}list;list *s;
金陵科技學院實驗報告list *setup(list *s){
} list *nizhi(list *head){
list *h;list *rear;int i=0;char b[100];h=malloc(sizeof(list));h->next=head;rear=head;do {
b[i]=rear->a;rear=rear->next;i++;list *head=null;list *rear=null;
char c;printf(“請輸入c直到$n”);c=getchar();while(c!='$'){
} if(rear!=null)rear->next=null;return head;s=malloc(sizeof(list));s->a=c;if(head==null){ } else rear->next=s;rear=s;c=getchar();head=s;}while(rear->next!=null);b[i]=rear->a;rear=head;for(;i>=0;i--){
} rear->a=b[i];rear=rear->next;
金陵科技學院實驗報告
} void display(list *head){ list *rear;if(head==null){
} } main(){
} list *head;head=setup(s);head=nizhi(head);display(head);free(s);free(head);rear=head;printf(“%c”,rear->a);while(rear->next!=null){
} rear=rear->next;printf(“%c”,rear->a);printf(“沒有數(shù)據(jù)n”);else return head;2.#include
#define datatype char typedef struct lnklist { datatype a;struct lnklist *next;}list;list *s1;list *s2;list *setup(list *s){
list *head=null;list *rear=null;char c;printf(“請輸入c直到$n”);c=getchar();while(c!='$')
金陵科技學院實驗報告
} void dein(list *la,list *lb,int i,int len,int j){
int k;list *rear;list *t;list *h;list *r;list *q;h=null;rear=la;q=la;for(k=1;k!=i;k++){
} while(q->next!=rear){
t=malloc(sizeof(list));t->a=rear->a;if(h==null)h=t;q=q->next;for(k=1;k<=len;k++)rear=rear->next;if(rear->next==null&&k!=i){
} printf(“沒找到i的位置n”);exit(0);
{
} if(rear!=null)rear->next=null;return head;s=malloc(sizeof(list));s->a=c;if(head==null){ } else rear->next=s;rear=s;c=getchar();head=s;
金陵科技學院實驗報告
} void display(list *head){ list *rear;if(head==null){
rear=head;printf(“%c”,rear->a);while(rear->next!=null){
} printf(“n”);rear=rear->next;printf(“%c”,rear->a);printf(“沒有數(shù)據(jù)n”);else
} q->next=rear;if(r!=null)r->next=null;rear=lb;for(k=1;k!=j;k++){
} q=lb;while(q->next!=rear)q=q->next;r->next=rear;q->next=h;rear=rear->next;if(rear->next==null&&k!=j){
} printf(“沒找到j的位置n”);exit(0);else r->next=t;r=t;rear=rear->next;if(rear->next==null&&k
} printf(“l(fā)en太長n”);exit(0);
金陵科技學院實驗報告
} } main(){ char c;
} list *la;list *lb;int i,len,j;printf(“建立單鏈表lan”);la=setup(s1);printf(“建立單鏈表lbn”);lb=setup(s2);printf(“請輸入要刪的位置in”);scanf(“%d”,&i);printf(“請輸入要刪減的數(shù)據(jù)長度lenn”);scanf(“%d”,&len);printf(“請輸入要插入的位置jn”);scanf(“%d”,&j);dein(la,lb,i,len,j);printf(“顯示lan”);display(la);printf(“顯示lbn”);display(lb);free(la);free(lb);c=getchar();
金陵科技學院實驗報告
四、實驗結(jié)果與分析(程序運行結(jié)果及其分析)1.(1)
金陵科技學院實驗報告
1.(2)
1.(3)
金陵科技學院實驗報告
2.金陵科技學院實驗報告
五、實驗體會(遇到問題及解決辦法,編程后的心得體會)
單鏈表以前沒怎么編過,所以現(xiàn)在編有點陌生,要編譯好幾次才能運行。我覺得還是不能光看書,還要多編幾道題比較有手感。
金陵科技學院實驗報告
實驗項目名稱: 堆棧和隊列 實驗學時: 2 同組學生姓名: 實驗地點: 實驗日期: 實驗成績: 批改教師: 批改時間:
金陵科技學院實驗報告
實驗3 堆棧和隊列
一、實驗目的和要求
(1)掌握應用棧解決問題的方法。(2)掌握利用棧進行表達式求和的算法。
(3)掌握隊列的存儲結(jié)構(gòu)及基本操作實現(xiàn),并能在相應的應用問題中正確選用它們。
二、實驗儀器和設備
turbo c 2.0
三、實驗內(nèi)容與過程(含程序清單及流程圖)
1、必做題
(1)判斷一個算術(shù)表達式中開括號和閉括號是否配對。(2)測試“漢諾塔”問題。
(3)假設稱正讀和反讀都相同的字符序列為”回文”,試寫一個算法判別讀入的一個以’@’為結(jié)束符的字符序列是否是“回文”。
2、選做題
在順序存儲結(jié)構(gòu)上實現(xiàn)輸出受限的雙端循環(huán)隊列的入列和出列算法。設每個元素表示一個待處理的作業(yè),元素值表示作業(yè)的預計時間。入隊列采取簡化的短作業(yè)優(yōu)先原則,若一個新提交的作業(yè)的預計執(zhí)行時間小于隊頭和隊尾作業(yè)的平均時間,則插入在隊頭,否則插入在隊尾。程序清單:
1.(1)
#include
#include
char a[100];int panduan(char *a){
int i,k,count1=0,count2=0;for(i=0;a[i]!='';i++){ {count1++;for(k=i+1;a[k]!='';k++){ if(a[k]==')')if(a[i]=='(')
金陵科技學院實驗報告
} main(){
} printf(“請輸入算式n”);gets(a);if(panduan(a)==1){ } else printf(“算式()不配對n”);printf(“算式()配對n”);
break;} if(a[k]=='')return 0;} if(a[i]==')')} if(count1!=count2)return 0;return 1;count2++;1.(2)
#include
int i;void move(int n,char a,char c){ printf(“第%d步:將%d號盤子%c--->%cn”,i++,n,a,c);} void hanno(int n,char a,char b,char c){
} main(){ if(n==1){} hanno(n-1,a,c,b);move(n,a,c);hanno(n-1,b,a,c);move(1,a,c);else
金陵科技學院實驗報告
} int n;char a,b,c;printf(“請輸入要移動的盤子數(shù)n”);scanf(“%d”,&n);a='a';b='b';c='c';hanno(n,a,b,c);1.(3)
#include
#include
char s[100];int huiwen(char s[]){
} main(){while(1){ printf(“請輸入字符直到@n”);gets(s);if(huiwen(s))
} printf(“是回文n”);printf(“不是回文n”);else int i,j=0;char b[100];for(i=0;s[i]!='@';i++);for(i=i-1;i>=0;i--){
} j=0;for(i=0;s[i]!='@';i++){ } return 1;return 0;b[j]=s[i];j++;if(s[i]!=b[j])j++;
金陵科技學院實驗報告
}
2.#include
#define maxsize 100 typedef struct duilie {
int a[maxsize];int head;int rear;}dui;dui *s;void init(dui *s){} void setup(dui *s,int x){
if(x<((s->a[s->head]+s->a[s->rear])/2)){
} else { s->rear=(s->rear++)%maxsize;s->head=(s->head--)%maxsize;s->a[s->head]=x;s->head=maxsize-1;s->rear=maxsize-1;s->a[s->head]=0;s->a[s->rear]=0;
金陵科技學院實驗報告
} } s->a[s->rear]=x;void display(dui *s){
printf(“s隊為:”);while(s->head==s->rear){ printf(“%-3d”,s->a[s->head]);
} main(){
} int x;while(1){ printf(“請輸入x直到0n”);scanf(“%d”,&x);setup(s,x);if(x==0)} if(s->head!=(s->rear+1)%maxsize)printf(“隊滿n”);display(s);break;} s->head=(s->head++)%maxsize;
金陵科技學院實驗報告
四、實驗結(jié)果與分析(程序運行結(jié)果及其分析)1.(1)
金陵科技學院實驗報告
1.(2)
1.(3)
金陵科技學院實驗報告
五、實驗體會(遇到問題及解決辦法,編程后的心得體會)
金陵科技學院實驗報告
實驗項目名稱: 串 實驗學時: 2 同組學生姓名: 實驗地點: 實驗日期: 實驗成績: 批改教師: 批改時間:
金陵科技學院實驗報告
實驗4 串
一、實驗目的和要求
掌握串的存儲及應用。
二、實驗儀器和設備
turbo c 2.0
三、實驗內(nèi)容與過程(含程序清單及流程圖)
1、必做題
(1)編寫輸出字符串s中值等于字符ch的第一個字符的函數(shù),并用主函數(shù)測試結(jié)果。
(2)編寫輸出字符串s中值等于字符ch的所有字符的函數(shù),并用主函數(shù)測試結(jié)果。
解題思路:可以將第一題程序改進成一個子函數(shù),在本題中循環(huán)調(diào)用。(3)設字符串采用單字符的鏈式存儲結(jié)構(gòu),編程刪除串s從位置i開始長度為k的子串。
2、選做題
假設以鏈結(jié)構(gòu)表示串,編寫算法實現(xiàn)將串s插入到串t中某個字符之后,若串t中不存在這個字符,則將串s聯(lián)接在串t的末尾。
提示:為提高程序的通用性,插入位置字符應設計為從鍵盤輸入。程序清單:
1.(1)
#include
#include
void fun(char s[],char ch){
int i;for(i=0;s[i]!='';i++){} printf(“沒找到n”);if(ch==s[i]){
} printf(“找到字符%c在位置%dn”,s[i],i+1);exit(0);
金陵科技學院實驗報告
} main(){
} char s[100],ch;printf(“請輸入字符串sn”);gets(s);printf(“請輸入要查找的字符chn”);scanf(“%c”,&ch);fun(s,ch);1.(2)
#include
#include
char s[100];void fun(char s[],char ch){ int i;if(strcmp(s,“")==0){ printf(”字符串s為空n“);exit(0);} for(i=0;s[i]!='';i++){
} main(){ char ch;printf(”請輸入字符串sn“);gets(s);printf(”請輸入要查找的chn“);scanf(”%c“,&ch);fun(s,ch);} if(ch==s[i])printf(” %c“,s[i]);} 1.(3)金陵科技學院實驗報告
#include
#include
typedef struct chuanlian { char c;struct chuanlian *next;}chuan;chuan *s;chuan *setup(chuan *s){
} void delet(chuan *chu,int i,int k){int j;chuan *p;chuan *t;if(chu==null){
} p=chu;for(j=1;j
c=ch;if(head==null){ } else
} if(rear!=null)rear->next=null;return head;rear->next=s;rear=s;head=s;s=malloc(sizeof(chuan));ch=getchar();金陵科技學院實驗報告
}
void display(chuan *chu){ chuan *p;
} main(){
int i,k;chuan *head;head=setup(s);printf(”請輸入要刪除字符的位置in“);scanf(”%d“,&i);p=chu;if(chu==null){
} printf(”%c“,p->c);while(p->next!=null){
} p=p->next;printf(”%c“,p->c);printf(”空串n“);exit(0);{
} t=p->next;for(j=1;j
} p->next=t;if(p->next==null&&j
} t=t->next;printf(”串長度太小,無法刪除%d個元素n“,k);exit(0);if(p->next==null&&j
} p=p->next;printf(”無法找到第%d位置n“,i);exit(0);
金陵科技學院實驗報告
printf(”請輸入要刪除字符的個數(shù)kn“);scanf(”%d“,&k);delet(head,i,k);display(head);free(head);free(s);} 2.#include
#include
typedef struct chuanlian { char c;struct chuanlian *next;}chuan;chuan *s,*t;chuan *setup(chuan *chu){
chuan *head=null;chuan *rear=null;char ch;printf(”請輸入字符ch直到$n“);ch=getchar();while(ch!='$'){ chu=malloc(sizeof(chuan));chu->c=ch;if(head==null){ head=chu;
金陵科技學院實驗報告
} } else rear->next=chu;rear=chu;ch=getchar();} if(rear!=null)rear->next=null;return head;
void insert(chuan *s1,chuan *s2,char x){
chuan *p;chuan *q;p=s1;if(s1==null){
} {
} while(p->next!=null){ if(p->c==x)break;printf(”s是空串n“);exit(0);if(s2==null)printf(”t是空串n“);exit(0);
金陵科技學院實驗報告
} } p=p->next;if(p->next==null)p->next=s2;else {
} q=s2;while(q->next!=null)q=q->next;q->next=p->next;p->next=s2;void display(chuan *chu){ chuan *p;
} p=chu;if(chu==null){
} printf(”%c“,p->c);while(p->next!=null){
} p=p->next;printf(”%c“,p->c);printf(”空串n“);exit(0);
金陵科技學院實驗報告
main(){
char x,c;printf(”建立單鏈串tn“);t=setup(t);c=getchar();printf(”建立單鏈串sn“);s=setup(s);c=getchar();printf(”請輸入要在什么字符后插入n");x=getchar();
}
insert(t,s,x);display(t);
數(shù)據(jù)結(jié)構(gòu)與算法分析推薦書籍篇四
《數(shù)據(jù)結(jié)構(gòu)》教學大綱
一、課程基本信息
課程名稱:數(shù)據(jù)結(jié)構(gòu)
總學時:64(理論課內(nèi)學時48,上機課內(nèi)學時16)課程設計:24 課程類型:必修課
考試形式:半開卷考試 講課對象:計算機本科
建議教材:《數(shù)據(jù)結(jié)構(gòu)》(c語言版)陳明 編著 清華大學出版社
課程簡介:數(shù)據(jù)結(jié)構(gòu)課程介紹如何組織各種數(shù)據(jù)在計算機中的存儲、傳遞和轉(zhuǎn)換。內(nèi)容包括:數(shù)組、鏈接表、棧和隊列、串、樹與森林、圖、排序、查找、索引與散列結(jié)構(gòu)等。課程以結(jié)構(gòu)化程序設計語言c語言作為算法的描述工具,強化數(shù)據(jù)結(jié)構(gòu)基本知識和結(jié)構(gòu)化程序設計基本能力的雙基訓練。為后續(xù)計算機專業(yè)課程的學習打下堅實的基礎。
二、課程的教學目標
“數(shù)據(jù)結(jié)構(gòu)”是計算機相關專業(yè)的一門重要專業(yè)基礎課,是計算機學科的公認主干課。課程內(nèi)容由數(shù)據(jù)結(jié)構(gòu)和算法分析初步兩部分組成。
數(shù)據(jù)結(jié)構(gòu)是針對處理大量非數(shù)值性程序問題而形成的一門學科,內(nèi)涵豐富、應用范圍廣。它既有完整的學科體系和學科深度,又有較強的實踐性。通過課程的學習,應使學生理解和掌握各種數(shù)據(jù)結(jié)構(gòu)(物理結(jié)構(gòu)和邏輯結(jié)構(gòu))的概念及其有關的算法;熟悉并了解目前常用數(shù)據(jù)結(jié)構(gòu)在計算機諸多領域中的基本應用。
算法分析強調(diào)最基本的算法設計技術(shù)和分析方法。要求學生從算法和數(shù)據(jù)結(jié)構(gòu)的相互依存關系中把握應用算法設計的藝術(shù)和技能。
經(jīng)過上機實習和課程設計的訓練,使學生能夠編制、調(diào)試具有一定難度的中型程序;以培養(yǎng)良好的軟件工程習慣和面向?qū)ο蟮能浖季S方法。
“數(shù)據(jù)結(jié)構(gòu)”的前序課是《離散數(shù)學》、《c語言程序設計與算法初步》。
三、理論教學內(nèi)容的基本要求及學時分配
1、序論(2學時)學習目標:熟悉各類文件的特點,構(gòu)造方法以及如何實現(xiàn)檢索,插入和刪除等操作。
重點與難點:本章無。
知識點:數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型、算法及其設計原則、時間復雜度、空間復雜度。
2、線性表(4學時)
學習目標:
(1)了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關系,在計算機中表示這種關系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。用前者表示的線性表簡稱為順序表,用后者表示的線性表簡稱為鏈表;
(2)熟練掌握這兩類存儲結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲結(jié)構(gòu)上的實現(xiàn);
(3)能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合;
(4)結(jié)合線性表類型的定義增強對抽象數(shù)據(jù)類型的理解。
重點與難點:鏈表是本章的重點和難點。扎實的指針操作和內(nèi)存動態(tài)分配的編程技術(shù)是學好本章的基本要求,分清鏈表中指針 p 和結(jié)點 *p 之間的對應關系,區(qū)分鏈表中的頭結(jié)點、頭指針和首元結(jié)點的不同所指以及循環(huán)鏈表、雙向鏈表的特點等。
知識點:線性表、順序表、鏈表、有序表。
3、棧和隊列(4學時)
學習目標:
(1)掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點,并能在相應的應用問題中正確選用它們;
(2)熟練掌握棧類型的兩種實現(xiàn)方法;
(3)熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法;(4)理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。
重點與難點:棧和隊列是在程序設計中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu),因此本章的學習重點在于掌握這兩種結(jié)構(gòu)的特點,以便能在應用問題中正確使用。
知識點:順序棧、鏈棧、循環(huán)隊列、鏈隊列。
4、串(2學時)
學習目標:(1)理解串類型定義中各基本操作的特點,并能正確利用它們進行串的其它操作;
(2)理解串類型的各種存儲表示方法;(3)理解串匹配的各種算法。
重點和難點:相對于其它各個知識點而言,本章非整個課程的重點,鑒于串已是多數(shù)高級語言中已經(jīng)實現(xiàn)的數(shù)據(jù)類型,因此本章重點僅在于了解串類型定義中各基本操作的定義以及串的實現(xiàn)方法,并學會利用這些基本操作來實現(xiàn)串的其它操作。本章的難點是理解實現(xiàn)串匹配的kmp算法的思想。
知識點:串的類型定義、串的存儲表示、串匹配、kmp算法。
5、數(shù)組和廣義表(4學時)
學習目標:
(1)理解數(shù)組類型的特點及其在高級編程語言中的存儲表示和實現(xiàn)方法,并掌握數(shù)組在“以行為主”的存儲表示中的地址計算方法;
(2)掌握特殊矩陣的存儲壓縮表示方法;
(3)理解稀疏矩陣的兩類存儲壓縮方法的特點及其適用范圍,領會以三元組表示稀疏矩陣時進行矩陣運算所采用的處理方法。
重點和難點:本章重點是學習數(shù)組類型的定義及其存儲表示。
知識點:數(shù)組的類型定義、數(shù)組的存儲表示、特殊矩陣的壓縮存儲表示方法、隨機稀疏矩陣的壓縮存儲表示方法。
6、樹和二叉樹(8學時)
學習目標:
(1)領會樹和二叉樹的類型定義,理解樹和二叉樹的結(jié)構(gòu)差別;(2)熟記二叉樹的主要特性,并掌握它們的證明方法;
(3)熟練掌握二叉樹的各種遍歷算法,并能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作;
(4)理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法;
(5)熟練掌握二叉樹和樹的各種存儲結(jié)構(gòu)及其建立的算法;(6)學會編寫實現(xiàn)樹的各種操作的算法;
(7)了解最優(yōu)樹的特性,掌握建立最優(yōu)樹和赫夫曼編碼的方法。
重點和難點:二叉樹和樹的遍歷及其應用是本章的學習重點,而編寫實現(xiàn)二叉樹和樹的各種操作的遞歸算法也恰是本章的難點所在。
知識點:樹的類型定義、二叉樹的類型定義、二叉樹的存儲表示、二叉樹的遍歷以及其它操作的實現(xiàn)、線索二叉樹、樹和森林的存儲表示、樹和森林的遍歷以及其它操作的實現(xiàn)、最優(yōu)樹和赫夫曼編碼。
7、圖(8學時)
學習目標:
(1)領會圖的類型定義;
(2)熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法,了解各種存儲結(jié)構(gòu)的特點及其選用原則;
(3)熟練掌握圖的兩種遍歷算法;(4)理解各種圖的應用問題的算法。
重點和難點:圖的應用極為廣泛,而且圖的各種應用問題的算法都比較經(jīng)典,因此本章重點在于理解各種圖的算法及其應用場合。
知識點:圖的類型定義、圖的存儲表示、圖的深度優(yōu)先搜索遍歷和圖的廣度優(yōu)先搜索遍歷、無向網(wǎng)的最小生成樹、最短路徑、拓撲排序、關鍵路徑。
8、查找(6學時)
學習目標:
(1)理解“查找表”的結(jié)構(gòu)特點以及各種表示方法的適用性;(2)熟練掌握以順序表或有序表表示靜態(tài)查找表時的查找方法;
(3)熟悉靜態(tài)查找樹的構(gòu)造方法和查找算法,理解靜態(tài)查找樹和折半查找的關系;
(4)熟練掌握二叉查找樹的構(gòu)造和查找方法;(5)理解二叉平衡樹的構(gòu)造過程;
(6)熟練掌握哈希表的構(gòu)造方法,深刻理解哈希表與其它結(jié)構(gòu)的表的實質(zhì)性的差別;
(7)掌握描述查找過程的判定樹的構(gòu)造方法,以及按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。
重點和難點:本章重點在于理解查找表的結(jié)構(gòu)特點及其各種表示方法的特點和適用場合。
知識點:順序表、有序表、索引順序表、靜態(tài)查找樹、二叉查找樹、二叉平衡樹、哈希表。
9、內(nèi)部排序(6學時)
學習目標:
(1)理解排序的定義和各種排序方法的特點,并能加以靈活應用。排序方法有不同的分類方法,基于“關鍵字間的比較”進行排序的方法可以按排序過程所依據(jù)的不同原則分為插入排序、交換排序、選擇排序、歸并排序和計數(shù)排序等五類;
(2)掌握各種排序方法的時間復雜度的分析方法。能從“關鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時間性能。按平均時間復雜度劃分,內(nèi)部排序可分為三類:o(n2)的簡單排序方法,o(n*logn)的高效排序方法和o(d*n)的基數(shù)排序方法;
(3)理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義,弄清楚在什么情況下要求應用的排序方法必須是穩(wěn)定的。
重點和難點:希爾排序、快速排序、堆排序和歸并排序等高效方法是本章的學習重點和難點。
知識點:排序、直接插入排序、折半插入排序、表插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序、堆排序、2-路歸并排序、基數(shù)排序、排序方法的綜合比較。
10、文件(4學時)
學習目標:熟悉各類文件的特點,構(gòu)造方法以及如何實現(xiàn)檢索,插入和刪除等操作。
重點和難點:本章重點在于了解各種文件的結(jié)構(gòu)特點及其適用場合。知識點:順序文件、索引文件、b-樹、b+樹、索引順序文件、vsam文件、散列文件、多關鍵字文件。
四、實驗教學內(nèi)容的基本要求及學時分配
1、線性表(1學時)實驗一 順序表的應用 實驗二 鏈表的應用
要求:理解線性表的定義及其運算;理解順序表和鏈表的定義,組織形式,結(jié)構(gòu)特征和類型說明;掌握在這兩種表上實現(xiàn)的插入,刪除和按值查找的算法;了解循環(huán)鏈表,雙(循環(huán))鏈表的結(jié)構(gòu)特點和在其上施加的插入,刪除等操作。
2、棧(0.5學時)實驗三 棧的應用
要求:理解棧的定義,特征及在其上所定義的基本運算;掌握在兩種存儲結(jié)構(gòu)上對棧所施加的基本運算的實現(xiàn)。
3、隊列(0.5學時)實驗四 隊列的應用
要求:理解隊列的定義,特征及在其上所定義的基本運算;掌握在兩種存儲結(jié)構(gòu)上對隊列所施加的基本運算的實現(xiàn)。
4、串(0.5學時)實驗五 串的應用
要求:了解串的定義;理解和領會串的存儲方式;掌握常用的串運算。
5、數(shù)組和廣義表(0.5學時)實驗六 稀疏矩陣的應用
要求:理解多維數(shù)組的結(jié)構(gòu)特點和在內(nèi)存中的兩種順序存儲方式;理解并掌握矩陣和特殊矩陣元素在存儲區(qū)中地址的計算;領會稀疏矩陣的壓縮方式和簡單運算;了解廣義表的定義和基本運算。
6、樹與二叉樹(4學時)實驗七 樹與二叉樹的應用
要求:理解樹的定義,術(shù)語;領會并掌握樹的各種存儲結(jié)構(gòu);熟練掌握森林與二叉樹間的相互轉(zhuǎn)換;領會樹和森林的遍歷;了解樹的簡單應用。深刻理解二叉樹的定義,性質(zhì)及其存儲方法;熟練掌握二叉樹的二叉鏈表存儲方式,結(jié)點結(jié)構(gòu)和類型定義;理解并掌握二叉樹的三種遍歷算法;掌握二叉樹的線索化方法;靈活運用二叉樹的遍歷方法解決相關的應用問題。
7、圖(3學時)實驗八 圖的應用
要求:理解圖的基本概念及術(shù)語;掌握圖的兩種存儲結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法;熟練掌握圖的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想,步驟,并能列出在兩種存儲結(jié)構(gòu)上按上述兩種遍歷算法得到的序列;理解最小生成樹的概念,能按prim算法構(gòu)造最小生成樹;領會并掌握拓撲排序,關鍵路徑,最短路徑的算法思想。
8、查找(3學時)實驗九 順序查找 實驗十 折半查找 實驗十一 哈希表的應用 實驗十二 二叉排序樹的綜合練習要求:了解查找的基本思想及查找成功和不成功的概念;掌握在順序表,有序表,索引表,散列表等上的查找方法和算法,并能求出相應的平均查找長度;理解并掌握二叉排序樹,平衡二叉樹b-樹的各種算法。
9、排序(3學時)實驗十三 插入排序 實驗十四 選擇排序 實驗十五 排序綜合練習
要求:領會排序的基本思想和基本概念;理解并掌握插入排序,冒泡排序,快速排序,直接選擇排序,堆排序,歸并排序和基數(shù)排序的基本思想,步驟,算法及時空效率分析;了解外排序的定義和基本方法。
五、大綱說明
1、課堂講述的論題只是核心或有特色的知識內(nèi)容,還有相當數(shù)量的篇章內(nèi)容留給學生自學,所確定的自學部分內(nèi)容亦屬考查范圍。
2、“數(shù)據(jù)結(jié)構(gòu)”課注重上機訓練,所有作業(yè)都必須配有規(guī)范的文檔。上機訓練由平時的上機訓練和小學期的實訓課程設計兩部分組成。
3、課內(nèi)學時安排說明:前8周每周4學時全為理論課,從第9周開始理論和上機為1:1,也即2學時理論,2學時上機訓練。
4、本課強調(diào)能力的培養(yǎng),期末采用半開卷考試(允許同學攜帶一頁a4紙的總結(jié)資料)。本課成績由平時作業(yè)、上機成績(30%)和期末考試(70%)合成得到,有獨到見解的作業(yè)予以適當加分。
5、主要參考書:
[1]《數(shù)據(jù)結(jié)構(gòu)與算法教程》鄒永林 周蓓 唐曉陽 楊劍勇 編著 機械工業(yè)出版社
[2]《數(shù)據(jù)結(jié)構(gòu)(c語言版)》(含cd)嚴蔚敏 吳為民 編著 清華大學出版社
[3]《數(shù)據(jù)結(jié)構(gòu)習題集(c語言版)》嚴蔚敏 編著 清華大學出版社
[4]《數(shù)據(jù)結(jié)構(gòu)習題解析與實訓》張世和 編著 清華大學出版社
數(shù)據(jù)結(jié)構(gòu)與算法分析推薦書籍篇五
《數(shù)據(jù)結(jié)構(gòu)與算法》課程學習總結(jié)報告
070401301507計本(3)班張浩
本學期開設的《數(shù)據(jù)結(jié)構(gòu)與算法》課程已經(jīng)告一段落,現(xiàn)就其知識點及其掌握情況、學習體會以及對該門課程的教學建議等方面進行學習總結(jié)。
一、《數(shù)據(jù)結(jié)構(gòu)與算法》知識點
在課本的第一章便交代了該學科的相關概念,如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型以及數(shù)據(jù)結(jié)構(gòu)的定義。其中,數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算集合。邏輯結(jié)構(gòu)分為四類:集合型、線性、樹形和圖形結(jié)構(gòu),數(shù)據(jù)元素的存儲結(jié)構(gòu)分為:順序存儲、鏈接存儲、索引存儲和散列存儲四類。緊接著介紹了一些常用的數(shù)據(jù)運算。最后著重介紹算法性能分析,包括算法的時間性能分析以及算法的空間性能分析。
第二章具體地介紹了順序表的概念、基本運算及其應用。基本運算有:初始化表、求表長、排序、元素的查找、插入及刪除等。元素查找方法有:簡單順序查找、二分查找和分塊查找。排序方法有:直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序及歸并排序等。最后介紹了順序串的概念,重點在于串的模式匹配。
鏈表中數(shù)據(jù)元素的存儲不一定是連續(xù)的,還可以占用任意的、不連續(xù)的物理存儲區(qū)域。與順序表相比,鏈表的插入、刪除不需要移動元素,給算法的效率帶來較大的提高。鏈表這一章中介紹了鏈表的節(jié)點結(jié)構(gòu)、靜態(tài)與動態(tài)鏈表的概念、鏈表的基本運算(如求表長、插入、查找、刪除等)、單鏈表的建立(頭插法和尾插法)以及雙向循環(huán)鏈表的定義、結(jié)構(gòu)、功能和基本算法。
堆棧與隊列是兩種運算受限制的線性結(jié)構(gòu)。其基本運算方法與順序表和鏈表運算方法基本相同,不同的是堆棧須遵循“先進后出”的規(guī)則,對堆棧的操作只能在棧頂進行;而隊列要遵循“先進先出”的規(guī)則,教材中列出了兩種結(jié)構(gòu)的相應算法,如入棧、出棧、入隊、出隊等。在介紹隊列時,提出了循環(huán)隊列的概念,以避免“假溢出”的現(xiàn)象。
第六章介紹了特殊矩陣和廣義表的概念與應用。其中,特殊矩陣包括對稱矩陣、三角矩陣、對角矩陣和稀疏矩陣,書中分別詳細介紹了它們的存儲結(jié)構(gòu)。稀疏矩陣的應用包括轉(zhuǎn)置和加法運算等。最后介紹了廣義表的相關概念及存儲結(jié)構(gòu),關于它的應用,課本中舉了m元多項式的表示問題。
第七章二叉樹的知識是重點內(nèi)容。在介紹有關概念時,提到了二叉樹的性質(zhì)以及兩種特殊的二叉樹:完全二叉樹和滿二叉樹。接著介紹二叉樹的順序存儲和鏈接存儲以及生成算法。重點介紹二叉樹的遍歷算法(遞歸算法、先序、中序和后序遍歷非遞歸算法)和線索二叉樹。二叉樹的應用:基本算法、哈弗曼樹、二叉排序樹和堆排序。
樹與二叉樹是不同的概念。教材介紹了樹和森林的概念、遍歷和存儲結(jié)構(gòu),還有樹、森林和二叉樹的相互關系,樹或森林怎樣轉(zhuǎn)化成二叉樹,二叉樹又如何轉(zhuǎn)換為樹和森林等算法。散列結(jié)構(gòu)是一種查找效率很高的一種數(shù)據(jù)結(jié)構(gòu)。本章的主要知識點有:散列結(jié)構(gòu)的概念及其存儲結(jié)構(gòu)、散列函數(shù)、兩種沖突處理方法、線性探測散列和鏈地址散列的基本算法以及散列結(jié)構(gòu)的查找性能分析。
最后一章介紹了圖的概念及其應用,是本書的難點。圖的存儲結(jié)構(gòu)的知識點有:鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識點有:有向圖、連通圖、生成樹和森林、最短路徑問題和有向無環(huán)圖及其應用。有向無環(huán)圖重點理解aov網(wǎng)和拓撲排序及其算法。
二、對各知識點的掌握情況
總體來看,對教材中的知識點理解較為完善,但各個章節(jié)均出現(xiàn)有個別知識點較為陌生的現(xiàn)象。現(xiàn)將各個章節(jié)出現(xiàn)的知識點理解情況列舉如下。
第一章中我對數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)的概念理解較為透徹,熟悉數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。而對算法的時間、空間性能分析較為模糊,尤其是空間性能分析需要加強。
第二章,順序表的概念、生成算法理解較為清晰,并且熟悉簡單順序查找和二分查找,對分塊查找較為含糊;排序問題中,由于冒泡排序在大一c語言課上已經(jīng)學習過,再來學習感覺很輕松。對插入排序和選擇排序理解良好,但是,在實際運用中仍然出現(xiàn)明顯不熟練的現(xiàn)象。由于在歸并排序?qū)W習中感覺較吃力,現(xiàn)在對這種排序方法仍然非常模糊,所以需要花較多的時間來補習。此外串的模式匹配也是較難理解的一個地方。
鏈表這一章中,除對雙向循環(huán)鏈表這一知識點理解困難之外,其他的知識點像單鏈表的建立和基本算法等都較為熟悉。
接下來的有關堆棧以及隊列的知識點比較少,除有關算法較為特殊以外,其余算法都是先前學過的順序表和鏈表的知識,加上思想上較為重視,因此這部分內(nèi)容是我對全書掌握最好的一部分。不足之處仍然表現(xiàn)在算法的性能分析上。
在學習第六章時感覺較為吃力的部分在于矩陣的應用上,尤其對矩陣轉(zhuǎn)置算法的c語言描述不太理解。稀疏矩陣相加算法中,用三元組表實現(xiàn)比較容易理解,對十字鏈表進行矩陣相加的方法較為陌生。
第七章是全書的重點,卻也有一些內(nèi)容沒有完全理解。在第一節(jié)基本概念中,二叉樹的性質(zhì)容易懂卻很難記憶。對二叉樹的存儲結(jié)構(gòu)和遍歷算法這部分內(nèi)容掌握較好,能夠熟練運用,而對于二叉樹應用中的哈弗曼樹卻比較陌生。
第八章內(nèi)容較少,牽涉到所學的隊列的有關內(nèi)容,總體來說理解上沒有什么困難,問題依舊出現(xiàn)在算法的性能分析上。
散列結(jié)構(gòu)這一章理解比較完善的知識點有:基本概念和存儲結(jié)構(gòu)。散列函數(shù)中直接定址法和除留余數(shù)法學得比較扎實,對數(shù)字分析法等方法則感覺較為陌生。對兩種沖突處理的算法思想的理解良好,問題在于用c語言描述上。
最后一章,圖及其應用中,圖的定義、基本運算如圖的生成等起初理解有困難,但隨著學習深入,對它的概念也逐步明朗起來。鄰接矩陣、鄰接表和逆鄰接表掌握較好,而對十字鏈表和鄰接多重表則較為陌生。感覺理解較為吃力的內(nèi)容還有圖的遍歷(包括深度和廣度優(yōu)先遍歷),最小生成樹問題也是比較陌生的知識點。最短路徑和aov網(wǎng)學習起來感覺比較輕松,而對于c語言描述卻又不大明白。
三、學習體會
接觸這門課程以前,我對該課程所學的內(nèi)容有許多疑點,例如:這門課是否是在介紹一種新的計算機語言?如果不是,那么學習這門課程的用途是什么?為什么市面上各種介紹數(shù)據(jù)結(jié)構(gòu)的資料采用了不同的計算機語言,如c、c++還有java?我的c語言學得不好,對學習這門課是否有影響??
在學習伊始,老師就明確提出它不是一種計算機語言,不會介紹新的關鍵詞,而是通過學習可以設計出良好的算法,高效地組織數(shù)據(jù)。一個程序無論采用何種語言,其基本算法思想不會改變。聯(lián)系到在大一和大二上學期學習的c和c++語言,我深刻認識到了這一點。“軟件開發(fā)好比寫作文,計算機語言提供了許多華麗的辭藻,而數(shù)據(jù)結(jié)構(gòu)則考慮如何將這些辭藻組織成一篇優(yōu)秀的文章來。”在學習這門課中,要熟悉對算法思想的一些描述手段,包括文字描述、圖形描述和計算機語言描述等。因此,計算機語言基礎是必須的,因為它提供了一種重要的算法思想描述手段——機器可識別的描述。
這門課結(jié)束之后,我總結(jié)了學習中遇到的一些問題,最為突出的,書本上的知識與老師的講解都比較容易理解,但是當自己采用剛學的知識點編寫程序時卻感到十分棘手,有時表現(xiàn)在想不到適合題意的算法,有時表現(xiàn)在算法想出來后,只能將書本上原有的程序段謄寫到
自己的程序中再加以必要的連接以完成程序的編寫。針對這一情況,我會嚴格要求自己,熟練掌握算法思想,盡量獨立完成程序的編寫與修改工作,只有這樣,才能夠提高運用知識,解決問題的能力。
四、對《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學的建議
1、建議在上課過程中加大隨堂練習的分量,以便學生能當堂消化課堂上學習的知識,也便于及時了解學生對知識點的掌握情況,同時有助于學生保持良好的精神狀態(tài)。
2、建議在課時允許的情況下,增加習題課的分量,通過課堂的習題講解,加深對知識點的掌握,同時對各知識點的運用有一個更為直觀和具體的認識。
以上便是我對《數(shù)據(jù)結(jié)構(gòu)與算法》這門課的學習總結(jié),我會抓緊時間將沒有吃透的知識點補齊。今后我仍然會繼續(xù)學習,克服學習中遇到的難關,在打牢基礎的前提下向更深入的層面邁進!