第一篇：“數(shù)據(jù)結(jié)構(gòu)”課程總結(jié)

“數(shù)據(jù)結(jié)構(gòu)”課程總結(jié)

計算機(jī)科學(xué)與技術(shù)專業(yè)從1994年開始為我校專科生開設(shè)“數(shù)據(jù)結(jié)構(gòu)”課程，2004年開始為本科生開設(shè)這門課程。由于本門課程的教學(xué)從教材、講授、實(shí)驗指導(dǎo)都體現(xiàn)了先進(jìn)的教育理念，該課程的教學(xué)體系科學(xué)、完整，教學(xué)手段與方法先進(jìn)，課程特色鮮明，2006年被評為赤峰學(xué)院本科層次精品課。幾年來，數(shù)據(jù)結(jié)構(gòu)課題組成員從以下幾個方面對本門課程進(jìn)行了建設(shè)和改革。

一、課程建設(shè)指導(dǎo)思想、定位和特色 1．學(xué)科地位

“數(shù)據(jù)結(jié)構(gòu)”是計算機(jī)科學(xué)與技術(shù)專業(yè)的一門學(xué)科基礎(chǔ)課，是本專業(yè)和相關(guān)專業(yè)必修課。本課程的教學(xué)目標(biāo)是培養(yǎng)學(xué)生通過理解、分析和研究計算機(jī)處理的數(shù)據(jù)對象的特性，從而選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和相應(yīng)的算法，并熟練掌握算法的時間分析和空間分析技巧。“數(shù)據(jù)結(jié)構(gòu)”還是計算機(jī)科學(xué)與技術(shù)專業(yè)部分專業(yè)課的先導(dǎo)課，如“數(shù)據(jù)庫原理與應(yīng)用”、“計算機(jī)操作系統(tǒng)”、“計算機(jī)編譯原理”和“面向?qū)ο蟮某绦蛟O(shè)計”等。所以本課程的教學(xué)效果將直接影響到學(xué)生對其它后續(xù)專業(yè)課的學(xué)習(xí)，因此，該課程在專業(yè)建設(shè)的地位十分重要。

“數(shù)據(jù)結(jié)構(gòu)”是一門應(yīng)用性很強(qiáng)的課程，本課程要求學(xué)生在掌握各種數(shù)據(jù)結(jié)構(gòu)，特別是存儲結(jié)構(gòu)和有關(guān)算法的基礎(chǔ)上，通過大量的上機(jī)實(shí)例把難以理解的、抽象的概念轉(zhuǎn)化為計算機(jī)能夠正確運(yùn)行的程序，從而提高學(xué)生運(yùn)用所學(xué)知識解決實(shí)際問題的能力。2．課程特色

根據(jù)課程建設(shè)的規(guī)劃和我系實(shí)際，我們針對《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)開展討論，并就實(shí)驗、圖書資料等方面進(jìn)行建設(shè)。在不斷的教學(xué)實(shí)踐中，我們按照精品課建設(shè)要求，積極探索，積累了豐富的教學(xué)經(jīng)驗。

采用國內(nèi)經(jīng)典教材，結(jié)合前沿的研究領(lǐng)域和最新科研動態(tài)，豐富教學(xué)內(nèi)容，讓學(xué)生了解數(shù)據(jù)結(jié)構(gòu)的實(shí)際應(yīng)用價值。

采用課堂教學(xué)與大作業(yè)相結(jié)合，上機(jī)實(shí)踐為補(bǔ)充的教學(xué)模式，培養(yǎng)學(xué)生的創(chuàng)業(yè)創(chuàng)新素質(zhì)和團(tuán)隊協(xié)作精神。

二、教師隊伍建設(shè)

1．良好的學(xué)緣結(jié)構(gòu)

任課教師的業(yè)務(wù)水平和教學(xué)水平是影響課程建設(shè)質(zhì)量的重要因素。為此，我們不斷加強(qiáng)師資隊伍建設(shè)，特別注重青年教師和實(shí)驗指導(dǎo)教師的培養(yǎng)。在擔(dān)任該課程教學(xué)任務(wù)的5名教師中，教授1名、副教授2名、講師2名，學(xué)歷結(jié)構(gòu)為碩士4人、學(xué)士1人，45歲以下3人，35歲以下2人。本教師梯隊學(xué)歷層次較高，職稱、年齡結(jié)構(gòu)合理，便于本門課程的建設(shè)和發(fā)展。

2．加強(qiáng)學(xué)術(shù)交流，不斷提高團(tuán)隊整體教學(xué)和科研水平

在教學(xué)過程中，我們采取了互相聽課，舉行公開課、觀摩課等方式，經(jīng)常交流教書育人和教學(xué)改革方面的經(jīng)驗，不斷提高任課教師的教學(xué)水平和學(xué)術(shù)水平。

以范體貴教授為學(xué)科帶頭人的教學(xué)研究梯隊，具有豐富的教學(xué)經(jīng)驗和高昂的教學(xué)熱情，同時具備較高的教學(xué)研究和科學(xué)研究水平。教學(xué)梯隊成員在搞好教學(xué)的同時，積極申報承擔(dān)各級各類教學(xué)研究和科學(xué)研究課題，并參加國內(nèi)外相關(guān)學(xué)科的科研、教學(xué)等方面的學(xué)術(shù)交流活動。選派范體貴、門愛華兩位老師參加全國計算機(jī)年會和全國數(shù)據(jù)庫學(xué)術(shù)會議，與國內(nèi)其他高校著名學(xué)者進(jìn)行了教學(xué)、科研等方面的交流，學(xué)到許多寶貴的經(jīng)驗和方法。

注重與其他高校的合作和交流，學(xué)習(xí)其他院校好的教學(xué)經(jīng)驗和方法。選派主講教師門愛華老師到清華大學(xué)計算機(jī)系做訪問學(xué)者，訪學(xué)期間門老師聽取了本課程的講授，經(jīng)常與講授本門課程的資深教授嚴(yán)蔚敏老師、殷仁昆老師進(jìn)行交流、學(xué)習(xí)。二位老師都給予了具體的指導(dǎo)和建議，為我校本門課程的改革和發(fā)展提供了有利的幫助。請國內(nèi)著名高校學(xué)者來我系講學(xué)傳授經(jīng)驗，在教學(xué)、科研等方面給予具體的指導(dǎo)。2008年10月清華大學(xué)著名數(shù)據(jù)庫專家馮建華教授來我系講學(xué)，課題組成員與馮教授進(jìn)行了深入的交流，在教學(xué)和科研方面都有很大的收獲。

3．開展科學(xué)研究，積極申請科研立項

數(shù)據(jù)結(jié)構(gòu)課題小組成員積極進(jìn)行相關(guān)領(lǐng)域的科學(xué)研究，幾年來發(fā)表相關(guān)論文30余篇，承擔(dān)自治區(qū)級科研項目四個，赤峰市科技局科研項目一個，院級項目一個，其中3個項目已經(jīng)完成并通過驗收。目前在研的一個科研項目是與清華大學(xué)合作申請的計算機(jī)前沿領(lǐng)域研究課題，相信通過該項目的研究和合作，對我系的科研工作會起到極大的促進(jìn)作用，同時能夠使我系科研水平上一個新的臺階。課題組成員經(jīng)過幾年的努力，在各方面都取得了一些成績。范體貴、門愛華、張國祥、王玉紅四位教師分別獲得“赤峰學(xué)院課堂教學(xué)質(zhì)量優(yōu)秀獎”，范體貴、門愛華兩位教師多次獲得“赤峰學(xué)院科研成果優(yōu)秀獎”的獎勵。王玉紅老師獲得“畢業(yè)實(shí)習(xí)優(yōu)秀指導(dǎo)教師“稱號，門愛華老師2007年、2008年連續(xù)獲得“畢業(yè)論文優(yōu)秀指導(dǎo)教師”獎勵。

建立了良好的人才培養(yǎng)制度，在學(xué)校和系里的大力支持下，鼓勵現(xiàn)有教師提高學(xué)歷與引進(jìn)高學(xué)歷教師相結(jié)合，經(jīng)過幾年的建設(shè)，已經(jīng)形成了一支以中青年為主的學(xué)科梯隊。積極鼓勵中青年教師到國內(nèi)名校進(jìn)修或攻讀碩士、博士學(xué)位，門愛華、董潔、王玉紅分別考取了東北大學(xué)和遼寧工程技術(shù)大學(xué)的碩士研究生，已圓滿完成學(xué)業(yè)并獲得碩士學(xué)位。

三、教學(xué)內(nèi)容、教材建設(shè)

1．理論環(huán)節(jié)教學(xué)內(nèi)容及學(xué)時分配

“數(shù)據(jù)結(jié)構(gòu)”是計算機(jī)科學(xué)課程體系中核心課程之首，作為學(xué)科的專業(yè)基礎(chǔ)課，具有承上啟下的重要作用。對應(yīng)于學(xué)科中問題求解的理論、抽象和設(shè)計的方法論，本課程內(nèi)容體系結(jié)構(gòu)分為概念表述、構(gòu)建數(shù)據(jù)模型、設(shè)計算法三個層面，突出數(shù)據(jù)組織方法與處理技術(shù)，貫穿程序設(shè)計和軟件工程新思想和新觀點(diǎn)。理論學(xué)時設(shè)置為72學(xué)時。

2.實(shí)踐環(huán)節(jié)教學(xué)內(nèi)容及學(xué)時分配

上機(jī)實(shí)踐和課程設(shè)計重在培養(yǎng)學(xué)生軟件設(shè)計的綜合能力。在基本的課程實(shí)習(xí)基礎(chǔ)上,自2001年起開設(shè)了數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，使課程的實(shí)踐環(huán)節(jié)總學(xué)時數(shù)增加到60學(xué)時。提出了課程設(shè)計的規(guī)范要求，突出關(guān)鍵技術(shù)要點(diǎn)，貫穿基本技能訓(xùn)練主線，加強(qiáng)實(shí)踐能力培養(yǎng)。

通過課程設(shè)計的訓(xùn)練，突出構(gòu)造性思維訓(xùn)練的特征，提高了學(xué)生組織數(shù)據(jù)與進(jìn)行編寫大型程序能力，使學(xué)生更好地理解和掌握了算法設(shè)計所需的技術(shù)，為專業(yè)學(xué)習(xí)打下良好的基礎(chǔ)。課程設(shè)計題目（動態(tài)更新、完善）：航空客運(yùn)訂票系統(tǒng)；電梯模擬；簡單行編輯程序；工資管理系統(tǒng)；醫(yī)院排隊看病活動的模擬；學(xué)籍管理系統(tǒng)；圖書管理系統(tǒng)等。3．教材建設(shè)

教材建設(shè)是課程建設(shè)的重要環(huán)節(jié)。為此，根據(jù)教學(xué)大綱和本課程的發(fā)展需要，在本課程教材的選用上注重教材的先進(jìn)性和科學(xué)性，我們選用了清華大學(xué)出版社嚴(yán)蔚敏教授等編寫的《數(shù)據(jù)結(jié)構(gòu)》（C語言版）作為教材，本書內(nèi)容豐富、體系結(jié)構(gòu)嚴(yán)謹(jǐn)、概念清晰、易學(xué)易懂，也是多所院校指定的考研參考教材，完全適合我系計算機(jī)科學(xué)與技術(shù)、信息與計算科學(xué)專業(yè)學(xué)生的需要。任課教師則多方面參考相關(guān)教材，選擇部分編寫精彩的內(nèi)容充實(shí)到教案中。任課教師們廣泛閱讀相關(guān)文獻(xiàn)，了解該領(lǐng)域前沿知識，并且在授課過程中介紹給學(xué)生，以開闊學(xué)生的視野，拓寬學(xué)生的知識面。同時，根據(jù)教材內(nèi)容和實(shí)際教學(xué)要求，編寫了《數(shù)據(jù)結(jié)構(gòu)上機(jī)指導(dǎo)與習(xí)題就解答》，并正式出版了《數(shù)據(jù)結(jié)構(gòu)實(shí)驗教程》一書，該書作為自治區(qū)教育廳統(tǒng)編教材已在各高校廣泛使用。

四、教學(xué)方法和教學(xué)手段

1．教學(xué)方法

在教學(xué)方法上，講課、討論和專題講座等多種形式并用，以科學(xué)、生動靈活的講授方式傳授知識，培養(yǎng)學(xué)生的創(chuàng)造思維。教師在認(rèn)真組織課堂講授，注意各環(huán)節(jié)正常運(yùn)行的同時，還針對不同的教學(xué)內(nèi)容采取不同的方法進(jìn)行講解，做到課程內(nèi)容既條理清晰、深入淺出，又重點(diǎn)突出、特色鮮明。教學(xué)內(nèi)容靈活，既有必講的內(nèi)容，也有針對不同專業(yè)需要和特點(diǎn)選講的內(nèi)容。

通過布置適量的課后習(xí)題，使學(xué)生能夠進(jìn)一步鞏固和提高對課上所學(xué)知識的領(lǐng)悟和應(yīng)用能力。我們在選擇習(xí)題時，一方面注重三基（基本理論，基本方法，基本技能）知識的掌握，另一方面也充分考慮知識的靈活應(yīng)用，使學(xué)生能多角度、多方法地解決問題，既鍛煉他們的系統(tǒng)性思維，又提高分析解決問題的能力。每兩周安排一次習(xí)題課，由指導(dǎo)教師集中解決同學(xué)課上課下遇到的問題。

上機(jī)實(shí)踐是學(xué)生對本門課程所學(xué)知識的一種全面、綜合的能力訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成必不可少的一個教學(xué)環(huán)節(jié)，也是對課堂教學(xué)效果的一種檢驗。通常，實(shí)習(xí)題中的問題比平時的習(xí)題復(fù)雜得多，也更接近實(shí)際。實(shí)習(xí)題注重原理與應(yīng)用的結(jié)合，目的讓學(xué)生學(xué)會如何把書上學(xué)到的知識運(yùn)用于解決實(shí)際問題的過程中去，培養(yǎng)從事軟件開發(fā)設(shè)計工作所必需的基本技能。同時，通過實(shí)踐能使書上的知識變“活”，起到深化理解和靈活掌握教學(xué)內(nèi)容的作用。平時的練習(xí)較偏重于如何編寫功能單一的“小”算法，而實(shí)習(xí)題是軟件設(shè)計的綜合訓(xùn)練，包括問題分析，總體結(jié)構(gòu)設(shè)計，用戶界面設(shè)計，程序設(shè)計基本技能和技巧，可以多人合作，有利于一整套軟件工程規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，實(shí)踐環(huán)節(jié)中有很重要的一點(diǎn)，就是機(jī)器是比任何教師都嚴(yán)格的主考官。

2．教學(xué)手段

為了適應(yīng)現(xiàn)代化教學(xué)的需求，我們在傳統(tǒng)教學(xué)的基礎(chǔ)上，充分利用現(xiàn)代科學(xué)技術(shù)，廣泛應(yīng)用多媒體教學(xué)課件和教學(xué)軟件。將授課內(nèi)容制作成了圖文并茂的多媒體課件，利用多媒體技術(shù)對數(shù)據(jù)結(jié)構(gòu)輔之以形象的動畫，動態(tài)演示抽象的復(fù)雜數(shù)據(jù)結(jié)構(gòu)的變化，用板書補(bǔ)充某些推導(dǎo)過程并完成和學(xué)生互動的內(nèi)容，改變了以前課堂教學(xué)單調(diào)的弊病，激發(fā)了學(xué)生的學(xué)習(xí)興趣。使用多媒體技術(shù)還可以直接在課堂上演示算法的實(shí)現(xiàn)過程，讓學(xué)生熟悉算法實(shí)現(xiàn)的環(huán)境和方法，增強(qiáng)了該門課的實(shí)踐性，提高了課堂授課效率和教學(xué)質(zhì)量，取得了滿意的教學(xué)效果。教師們?yōu)榱烁玫剡m應(yīng)社會的發(fā)展和改革的需要，本著強(qiáng)化算法的思想，在現(xiàn)有數(shù)據(jù)結(jié)構(gòu)內(nèi)容的基礎(chǔ)上，補(bǔ)充了新的算法，拓寬了學(xué)生的知識面。

五、課程建設(shè)取得的成果

1．教學(xué)科研論文

1）The Boundary Element Analysis for The Thermal Conduction of The Thermal Equipment。Proceedings of International Conference on Computational Physics, Rinton Press, US,(2005)199-202（SCI）

2）基于訪問控制列表的路由器防火墻在網(wǎng)絡(luò)安全中的應(yīng)用研究。計算機(jī)與網(wǎng)絡(luò) 24,(2004)52-53(核刊)3）信息系統(tǒng)在企業(yè)現(xiàn)代化管理中的應(yīng)用。《商場現(xiàn)代化（學(xué)術(shù)版）》，2005.2 25-26(核刊)4）可信網(wǎng)絡(luò)基本概念與基本屬性研究。《赤峰學(xué)院學(xué)報 》2007.5 5）基于包過濾技術(shù)路由器防火墻在網(wǎng)絡(luò)安全中的研究。《計算機(jī)應(yīng)用研究》,2007,vol23 6）Research on The Architecture of Tru-Network。2008 International Symposium on Information science and Engineering 7）路由器防火墻對沖擊波、震蕩波病毒的過濾研究。《赤峰學(xué)院學(xué)報》 2005.1 67-68 8）菲涅耳圓孔衍射的數(shù)值模擬。《赤峰學(xué)院學(xué)報》 2006.1 9）復(fù)雜軸承流體動力學(xué)特性的邊界元分析。《潤滑與密封》 2006.3(核刊 EI核心刊源)10）三葉軸承流體動力學(xué)特性的邊界元分析。《潤滑與密封》 2006.5(核刊 EI核心刊源)11）164-182Hf核的低能譜和電磁躍遷的相互作用玻色子模型。《高能物理與核物理》 28(12),(2004)119-122(核刊, SCI收錄)12）基于訪問控制列表的路由器防火墻在網(wǎng)絡(luò)安全中的應(yīng)用研究。《計算機(jī)與網(wǎng)絡(luò)》 2004.24 13）赤峰學(xué)院校園網(wǎng)路由器、交換機(jī)的選型及遠(yuǎn)程登錄。《赤峰教育學(xué)院學(xué)報》2004.5 81-82 14）《XML數(shù)據(jù)庫存儲策略綜述》 《計算機(jī)科學(xué)》 2005年9月（核刊）15）《XML數(shù)據(jù)庫結(jié)構(gòu)連接算法之研究》《計算機(jī)科學(xué)》 2007年6月（核刊）16）《XML中XPath包含關(guān)系判定算法》《內(nèi)蒙古大學(xué)學(xué)報》2008年10月（核刊）17）《基于關(guān)系數(shù)據(jù)庫的XML數(shù)據(jù)的存儲研究》《赤峰學(xué)院學(xué)報》 2006年 3 月 18）《XML數(shù)據(jù)庫模式匹配算法研究》 《赤峰學(xué)院學(xué)報》 2007年 5月 19）《Internet蠕蟲的分析與研究》 《赤峰學(xué)院學(xué)報》 2005年 4月 20）《如何防止外部網(wǎng)絡(luò)的攻擊》 《赤峰學(xué)院學(xué)報》 2004年2月 21）《射頻IC卡消費(fèi)系統(tǒng)的設(shè)計與實(shí)現(xiàn)》 《赤峰學(xué)院學(xué)報》 2008年10月 22）《XPath片斷的分析與研究》 《赤峰學(xué)院學(xué)報》 2008年1月 23）《一種基于層次結(jié)構(gòu)的XML編碼技術(shù)》 中國教育信息化》 2009年4月（核刊）24）《VC++實(shí)現(xiàn)圖形、數(shù)據(jù)庫應(yīng)用系統(tǒng)的思路》赤峰教育學(xué)院學(xué)報 2002年第2月 25）《基于IP組播的多媒體會議系統(tǒng)的設(shè)計》 赤峰教育學(xué)院學(xué)報 2002年6月 26）論文《個性化WINDOWS系統(tǒng)“開始”菜單》赤峰教育學(xué)院學(xué)報 2003年4月 27）淺談DEBUG程序的主要命令用法 赤峰學(xué)院學(xué)報 2007年5月 28）powerpoint技巧在課件制作中的妙用 赤峰學(xué)院學(xué)報 2006年1月 29）淺談用MASM運(yùn)行匯編程序 赤峰學(xué)院學(xué)報 2005年 1月 30）XML數(shù)字簽名淺析 赤峰學(xué)院學(xué)報 2008年 5月 31）《網(wǎng)絡(luò)層的靜態(tài)路由選擇綜述》 赤峰學(xué)院學(xué)報 2005年3月 32）《離散數(shù)學(xué)在計算機(jī)教學(xué)中的作業(yè)》 赤峰學(xué)院學(xué)報 2008年1月 33）《基于模擬退火算法的油井工礦數(shù)據(jù)挖掘的應(yīng)用研究》

赤峰學(xué)院學(xué)報2009年1月

2.教研課題

1）赤峰學(xué)院校園網(wǎng)項目 赤峰學(xué)院 2002年-2003年（已驗收）2）基于IP網(wǎng)QOS動態(tài)控制研究 內(nèi)蒙教育廳 2005年-2007年（已結(jié)題）3）基于結(jié)構(gòu)索引XML模式匹配方法研究 內(nèi)蒙教育廳 2005年—2007年（已結(jié)題）4）XML數(shù)據(jù)庫研究 赤峰學(xué)院 2006年—2008年（已結(jié)題）5）CAI系統(tǒng)中知識個性化組織與導(dǎo)航研究 內(nèi)蒙教育廳 2003年-2005年（已結(jié)題）6）XML安全數(shù)據(jù)發(fā)布關(guān)鍵問題研究 內(nèi)蒙教育廳 2009年—2010年（在研）3.教學(xué)獲獎

1）范體貴、門愛華、張國祥、王玉紅分別獲赤峰學(xué)院2005、2006年、2007年、2008年“課堂教學(xué)質(zhì)量優(yōu)秀獎”；

2）門愛華2007年、2008年連續(xù)獲的“畢業(yè)論文優(yōu)秀指導(dǎo)教師”獎勵； 3）王玉紅2007年獲院級“畢業(yè)實(shí)習(xí)優(yōu)秀實(shí)習(xí)指導(dǎo)教師”獎勵；

4）2009年《數(shù)據(jù)結(jié)構(gòu)課程教學(xué)和實(shí)踐》課題”獲赤峰學(xué)院“優(yōu)秀教學(xué)成果二等獎”。

數(shù)據(jù)結(jié)構(gòu)課程組 2009年5月14日

第二篇：數(shù)據(jù)結(jié)構(gòu)與算法課程總結(jié)[模版]

數(shù)據(jù)結(jié)構(gòu)與算法課程學(xué)習(xí)總結(jié)報告

11計本一班 許雪松 1104013018

數(shù)據(jù)結(jié)構(gòu)與算法是計算機(jī)程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機(jī)科學(xué)的核心課程，而且也已經(jīng)成為其他理工專業(yè)的熱門選修課。總的來說感觸還是比較深的，剛開始上的時候還蠻簡單的，越到后面感覺越難，算法也更復(fù)雜了，有時候甚至聽不懂，老師上課時講的也蠻快的，所以只能靠課下下功夫了。下面是我對本學(xué)期學(xué)習(xí)這門課的總結(jié)。

一、數(shù)據(jù)結(jié)構(gòu)與算法知識點(diǎn)

第一章的數(shù)據(jù)結(jié)構(gòu)和算法的引入，介紹了數(shù)據(jù)和數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、算法描述工具、算法和算法評價四個方面的知識。

第二章具體地介紹了順序表的概念、基本運(yùn)算及其應(yīng)用。基本運(yùn)算有：初始化表、求表長、排序、元素的查找、插入及刪除等。元素查找方法有：簡單順序查找、二分查找和分塊查找。排序方法有：直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序及歸并排序等。最后介紹了順序串的概念，重點(diǎn)在于串的模式匹配。

第三章主要介紹的是線性邏輯結(jié)構(gòu)的數(shù)據(jù)在鏈接存儲方法下數(shù)據(jù)結(jié)構(gòu)鏈表的相關(guān)知識。主要是單鏈表、循環(huán)鏈表的數(shù)據(jù)類型結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)、基本運(yùn)算及其實(shí)現(xiàn)以及鏈表的相關(guān)應(yīng)用問題，在此基礎(chǔ)上介紹了鏈串的相關(guān)知識。在應(yīng)用方面有多項式的相加問題、歸并問題、箱子排序問題和鏈表在字符處理方面的應(yīng)用問題等。本章未完全掌握的是循環(huán)鏈表的算法問題和C的描述。

第四章介紹在兩種不同的存儲結(jié)構(gòu)下設(shè)計的堆棧，即順序棧和鏈棧的相關(guān)知識，了解堆棧的相關(guān)應(yīng)用，掌握應(yīng)用堆棧來解決實(shí)際問題的思想及方法。本章主要內(nèi)容是順序棧和鏈棧的概念、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)定義和基本運(yùn)算算法及其性能分析。本章堆棧算法思想較為簡單，所以能較好掌握。

第五章主要介紹順序存儲和鏈接存儲方法下的兩種隊列、順序（循環(huán)）隊列和鏈隊列的數(shù)據(jù)結(jié)構(gòu)、基本運(yùn)算及其性能分析以及應(yīng)用。順序隊列(重點(diǎn)是循環(huán)隊列）和鏈隊列的概念、數(shù)據(jù)類型描述、數(shù)據(jù)結(jié)構(gòu)和基本運(yùn)算算法及其性能分析等。本章同堆棧有點(diǎn)類似，算法思想較為簡單，所以能較好掌握；但難點(diǎn)重在循環(huán)隊列隊空、隊滿的判斷條件問題。

第六章“特殊矩陣、廣義表及其應(yīng)用”將學(xué)習(xí)數(shù)組、稀疏矩陣和廣義表的基本概念，幾種特殊矩陣的存儲結(jié)構(gòu)及其基本運(yùn)算，在此基礎(chǔ)上學(xué)習(xí)特殊矩陣的計算算法與廣義表應(yīng)用等相關(guān)問題。本章的重點(diǎn)是相關(guān)數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)及其基本運(yùn)算算法。掌握了特殊矩陣的壓縮存儲結(jié)構(gòu)，在該存儲結(jié)構(gòu)下元素的定位方法，理解了稀疏矩陣的計算和廣義表的存儲結(jié)構(gòu)。

第七章二叉樹及其應(yīng)用。分為二叉樹的基本概念、二叉樹存儲結(jié)構(gòu)、二叉樹的遍歷算法、線索二叉樹、二叉樹的應(yīng)用（哈夫曼樹、二叉排序樹、堆和堆排序、基本算法）。基本算法包括二叉樹的建立、遍歷、線索化等算法。在此基礎(chǔ)上，介紹二叉樹的一些應(yīng)用問題，包括哈夫曼編碼問題、（平衡）二叉排序樹問題和堆排序問題等。

第八章說的是樹和森林，首先我們要知道樹與二叉樹是不同的概念。課本介紹了樹和森林的概念、遍歷和存儲結(jié)構(gòu)，還有樹、森林和二叉樹的相互關(guān)系，樹或森林怎樣轉(zhuǎn)化成二叉樹，二叉樹又如何轉(zhuǎn)換為樹和森林等算法。

第九章“散列結(jié)構(gòu)及其應(yīng)用”是邏輯結(jié)構(gòu)“集合型”的數(shù)據(jù)元素在散列存儲方法下的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用知識內(nèi)容。主要介紹散列函數(shù)的概念、散列結(jié)構(gòu)的概念、散列存儲結(jié)構(gòu)的概念---散列表、散列函數(shù)和散列表中解決沖突的處理方法---開放定址法、鏈地址法以及散列表的基本算法及其性能分析。本章概念較為多，所以掌握不太好。

第十章圖及其應(yīng)用。分為圖的概念、圖的存儲結(jié)構(gòu)及其基本算法、圖的遍歷及算法、有向圖的連通性和最小生成樹、圖的最小生成樹、非連通圖的生成森林算法、最短路徑、有向無環(huán)圖及其應(yīng)用。

二、對各知識點(diǎn)的掌握情況

我對各知識點(diǎn)的掌握情況總結(jié)如下：

對于第一章對數(shù)據(jù)結(jié)構(gòu)的概念理解頗深，大概是每次都要談?wù)摰桨伞λ惴ǖ臅r間性能，空間性能基本了解。這些在后面的章節(jié)都會有運(yùn)用。第二章本章重點(diǎn)和難點(diǎn)在查找和排序問題的算法思想上，6種排序方法的性能比較。本章未掌握的為希爾排序、快速排序、歸并排序的時間復(fù)雜度分析。第三章，對鏈表掌握還好，對其數(shù)據(jù)結(jié)構(gòu)進(jìn)行了分析，有循環(huán)鏈表，掌握的不是很好，對其中一些用法不熟練。第四章堆棧，本章堆棧算法思想較為簡單，所以能較好掌握，但表達(dá)式計算問題未掌握好的。第五章的循環(huán)隊列隊空、隊滿的判斷條件問題掌握的不是很好。第六章的重點(diǎn)是相關(guān)數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)及其基本運(yùn)算算法。掌握了特殊矩陣的壓縮存儲結(jié)構(gòu)，在該存儲結(jié)構(gòu)下元素的定位方法，理解了稀疏矩陣的計算和廣義表的存儲結(jié)構(gòu)。第七章對二叉樹掌握較好，其概念，存儲，遍歷有很好的掌握。就是對二叉排序樹有點(diǎn)生疏，它的生成算法不是很會。第八章樹樹與二叉樹之間的轉(zhuǎn)換，森林與二叉樹的轉(zhuǎn)換算法思想基本掌握。第九章散列的一些知識，沒有深入學(xué)習(xí)，大概了解了散列存儲結(jié)構(gòu)散列表，散列函數(shù)，沖突的處理方法。第十章了解了圖的逆鄰接表的存儲結(jié)構(gòu)，關(guān)鍵路徑求解算法未能掌握好，不能靈活運(yùn)用圖的不同數(shù)據(jù)結(jié)構(gòu)和遍歷算法解決復(fù)雜的應(yīng)用問題。

三、學(xué)習(xí)體會

剛剛接觸這門課時，看到課本中全是算法，當(dāng)時就暈了，因為我的C語言學(xué)的不好，我擔(dān)心會影響這門課的學(xué)習(xí)，后來上課時老師說學(xué)習(xí)這門課的基礎(chǔ)是C語言，所以我當(dāng)時就決定一定要好好補(bǔ)補(bǔ)，爭取不被拖后腿，在學(xué)習(xí)這門課的期間，也遇到了不少問。但是通過學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法，讓我對程序有了新的認(rèn)識，也有了更深的理解。同時，也讓我認(rèn)識到，不管學(xué)習(xí)什么，概念是基礎(chǔ)，所有的知識框架都是建立在基礎(chǔ)概念之上的，所以，第一遍看課本要將概念熟記于心，然后構(gòu)建知識框架。并且，對算法的學(xué)習(xí)是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。在第二遍看課本的過程中，要注重對算法的掌握。對于一個算法，讀一遍可能能讀懂，但不可能完全領(lǐng)會其中的思想。掌握一個算法，并不是說將算法背過，而是掌握算法的思想。我們需要的是耐心。每看一遍就會有這一遍的收獲。讀懂算法之后，自己再默寫算法，寫到不會的地方，看看課本想想自己為什么沒有想到。對算法的應(yīng)用上，學(xué)習(xí)算法的目的是利用算法解決實(shí)際問題。會寫課本上已有的算法之后，可以借其思想進(jìn)行擴(kuò)展，逐步提高編程能力。

四、對課程教學(xué)的建議

1、課程課時較緊，課堂上的練習(xí)時間較少，講解的東西越多，頭腦有時就很混亂。

2、感覺上課時的氣氛不是很好，雖然大部分人都在聽，可是效果不是很好。所以希望老師能在授課中間能穿插一些活躍課堂氛圍的話題，可以是大家都非常關(guān)心的一些內(nèi)容，這樣既讓大家能在思考之余有一個放松，也能夠提高學(xué)生的學(xué)習(xí)積極性和學(xué)習(xí)效率。

3、學(xué)習(xí)的積極性很重要，有時候我們花了很長時間去寫實(shí)驗報告，也很認(rèn)真的去理解去掌握，可是最后實(shí)驗報告可能就只得了一個C，抄的人反而得A，這樣的話很容易打擊學(xué)生的積極性，在后面的實(shí)驗報告中沒動力再去認(rèn)真寫。所以希望老師能在這方面有所調(diào)整。

4、雖然講課的時間很緊，但是還是希望老師能在講述知識點(diǎn)的時候能運(yùn)用實(shí)際的調(diào)試程序來給我們講解，這樣的話能讓我們對這些內(nèi)容有更深刻的印象和理解。

第三篇：數(shù)據(jù)結(jié)構(gòu)課程總結(jié).[小編推薦]

●數(shù)據(jù):能夠被計算機(jī)識別、存儲和加工處理的信息的載體。

●數(shù)據(jù)元素:數(shù)據(jù)的基本單位,可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨(dú)立含義的最小標(biāo)識單位。

●數(shù)據(jù)結(jié)構(gòu)的定義: ●邏輯結(jié)構(gòu):從邏輯結(jié)構(gòu)上描述數(shù)據(jù),獨(dú)立于計算機(jī)。線性結(jié)構(gòu):一對一關(guān)系。線性結(jié)構(gòu):多對多關(guān)系。

●存儲結(jié)構(gòu):是邏輯結(jié)構(gòu)用計算機(jī)語言的實(shí)現(xiàn)。順序存儲結(jié)構(gòu):如數(shù)組。鏈?zhǔn)酱鎯Y(jié)構(gòu):如鏈表。索引結(jié)構(gòu):索引表。散列存儲結(jié)

構(gòu):如散列表。

●對數(shù)據(jù)的操作:定義在邏輯結(jié)構(gòu)上,每種邏輯結(jié)構(gòu)都有一個運(yùn)算集合。常用的有:檢索、插入、刪除、更新、排序。

●數(shù)據(jù)類型:是一個值的集合以及在這些值上定義的一組操作的總稱。原子類型:簡單類型,由語言提供。結(jié)構(gòu)類型:由用戶借助

于描述機(jī)制定義,是導(dǎo)出類型。

●程序設(shè)計的實(shí)質(zhì)是對實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu),設(shè)計一個好的算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。

●算法是一個自定義的計算過程,以一個或多個值輸入,并以一個或多個值輸出。

●評價算法的好壞的因素:算法是正確的;執(zhí)行算法的時間;執(zhí)行算法的存儲空間;算法易于理解、編碼、調(diào)試。

●時間復(fù)雜度:是某個算法的時間耗費(fèi),它是該算法所求解問題規(guī)模n的函數(shù)。漸近時間復(fù)雜度:是指當(dāng)問題規(guī)模趨向無窮大時，該算法時間復(fù)雜度的數(shù)量級。評價一個算法的時間性能時,主要標(biāo)準(zhǔn)就是算法的漸近時間復(fù)雜度。

●算法中語句的頻度不僅與問題規(guī)模有關(guān),還與輸入實(shí)例中各元素的取值相關(guān)。●時間復(fù)雜度按數(shù)量級遞增排列依次為:常數(shù)階、對數(shù)階、線性階、線性對數(shù)階、平方階、立方階、……k次方階、指數(shù)階。

●空間復(fù)雜度:是某個算法的空間耗費(fèi),它是該算法所求解問題規(guī)模n的函數(shù)。●算法的時間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。

●線性表是由n≥0個數(shù)據(jù)元素組成的有限序列。n=0是空表;非空表,只能有一個開始結(jié)點(diǎn),有且只能有一個終端結(jié)點(diǎn)。

●線性表上定義的基本運(yùn)算:構(gòu)造空表:Initlist;求表長:Listlength;取結(jié)點(diǎn):GetNode;查找:LocateNode;插入:InsertList;刪

除:Delete。

●順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)

點(diǎn)相鄰關(guān)系是一致的。地址計算:? ●在順序表中實(shí)現(xiàn)的基本運(yùn)算:插入:平均移動結(jié)點(diǎn)次數(shù)為?;平均時間復(fù)雜度均為?。刪除:平均移動結(jié)點(diǎn)次數(shù)為?;平均時間復(fù)雜

度均為?。

●線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同,為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系,在存儲每個結(jié)點(diǎn)值的同時，還存儲了其后繼結(jié)點(diǎn)的地址信息。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)。一個單鏈表由頭指針的名字來命名。

●單鏈表運(yùn)算:建立單鏈表(頭插法:生成的順序與輸入順序相反。平均時間復(fù)雜度均為?。尾插法:平均時間復(fù)雜度均為?。加

頭結(jié)點(diǎn)的算法:對開始結(jié)點(diǎn)的操作無需特殊處理,統(tǒng)一了空表和非空表。查找(按序號:與查找位置有關(guān),平均時間復(fù)雜度均為?。

按值:與輸入實(shí)例有關(guān),平均時間復(fù)雜度均為。插入運(yùn)算:p=GetNode;s-next=p-next;p-next=s;平均時間復(fù)雜度均為?,刪除運(yùn)算:平均時間復(fù)雜度均為? ●單循環(huán)鏈表是一種首尾相接的單鏈表,終端結(jié)點(diǎn)的指針域指向開始結(jié)點(diǎn)或頭結(jié)點(diǎn)。鏈表終止條件是以指針等于頭指針或尾指針。

采用單循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點(diǎn)是查找頭指針和尾指針的時間都是O?,不用遍歷整個鏈表。

●雙鏈表就是雙向鏈表,就是在單鏈表的每個結(jié)點(diǎn)里再增加一個指向其直接前趨的指針域prior,形成兩條不同方向的鏈。由頭指針

head惟一確定。雙鏈表也可以頭尾相構(gòu)成雙循環(huán)鏈表。雙鏈表上的插入和刪除時間復(fù)雜度均為O?。

●順序表和鏈表的比較: ●基于空間:順序表的存儲空間是靜態(tài)分配,存儲密度為1;適于線性表事先確定其大小時采用。鏈表的存儲空間是動態(tài)分配,存儲

密度1;適于線性表長度變化大時采用。

●基于時間:順序表是隨機(jī)存儲結(jié)構(gòu),當(dāng)線性表的操作主要是查找時,宜采用。以插入和刪除操作為主的線性表宜采用鏈表做存儲

結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端,則宜采用尾指針表示的單循環(huán)鏈表。

●棧是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表,稱插入、刪除這一端為棧頂,另一端稱為棧底。表中無元素時為空棧。棧 的修改是按后進(jìn)先出的原則進(jìn)行的,我們又稱棧為LIFO表。通常棧有順序棧和鏈棧兩種存儲結(jié)構(gòu)。

●棧的基本運(yùn)算有六種:構(gòu)造空棧:InitStack,判棧空:StackEmpty,判棧滿:StackFull,進(jìn)棧:Push,退棧:Pop,取棧頂元素: StackTop ●在順序棧中有“上溢”和“下溢”的現(xiàn)象。“上溢”是棧頂指針指出棧的外面是出錯狀態(tài)。“下溢”可以表示棧為空棧,因此用來作為控制

轉(zhuǎn)移的條件。

●順序棧中的基本操作有六種:構(gòu)造空棧,判棧空,判棧滿,進(jìn)棧,退棧,取棧頂元素 ●鏈棧則沒有上溢的限制,因此進(jìn)棧不要判棧滿。鏈棧不需要在頭部附加頭結(jié)點(diǎn),只要有鏈表的頭指針就可以了。

●鏈棧中的基本操作有五種:構(gòu)造空棧,判棧空,進(jìn)棧,退棧,取棧頂元素 ●隊列是一種運(yùn)算受限的線性表,插入在表的一端進(jìn)行,而刪除在表的另一端進(jìn)行,允許刪除的一端稱為隊頭,允許插入的一端稱

為隊尾,隊列的操作原則是先進(jìn)先出的,又稱作FIFO表.隊列也有順序存儲和鏈?zhǔn)酱鎯煞N存儲結(jié)構(gòu)。

●隊列的基本運(yùn)算有六種:置空隊:InitQueue,判隊空:QueueEmpty,判隊滿:QueueFull,入隊:EnQueue,出隊:DeQueue,取

隊頭元素:QueueFront ●順序隊列的“假上溢”現(xiàn)象:由于頭尾指針不斷前移,超出向量空間。這時整個向量空間及隊列是空的卻產(chǎn)生了“上溢”現(xiàn)象。為了克

服“假上溢”現(xiàn)象引入循環(huán)向量的概念,是把向量空間形成一個頭尾相接的環(huán)形,這時隊列稱循環(huán)隊列。

●判定循環(huán)隊列是空還是滿,方法有三種:一種是另設(shè)一個布爾變量來判斷;第二種是少用一個元素空間,入隊時先測試%m=front? 滿:空;第三種就是用一個計數(shù)器記錄隊列中的元素的總數(shù)。

●隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列,一個鏈隊列就是一個操作受限的單鏈表。為了便于在表尾進(jìn)行插入的操作,在表尾增加一個尾

指針,一個鏈隊列就由一個頭指針和一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。在鏈隊列的出隊算法中,要注意當(dāng)原隊中只有一個結(jié)點(diǎn)時,出隊后要同進(jìn)修改頭尾指針并使隊列變空。

●串是零個或多個字符組成的有限序列。

●概念空串:是指長度為零的串,也就是串中不包含任何字符。空白串:指串中包含一個或多個空格字符的串。在一個串中任意

個連續(xù)字符組成的子序列稱為該串的子串,包含子串的串就稱為主串。子串在主串中的序號就是指子串在主串中首次出現(xiàn)的位置。

空串是任意串的子串,任意串是自身的子串。

●串分為兩種:串常量在程序中只能引用不能改變;串變量的值可以改變。●串的基本運(yùn)算有:求串長strlen,串復(fù)制strcpy,串聯(lián)接strcat,串比較charcmp,字符定位strchr。串是特殊的線性表,所以串的存

儲結(jié)構(gòu)與線性表的存儲結(jié)構(gòu)類似。串的順序存儲結(jié)構(gòu)簡稱為順序串。●順序串又可按存儲分配的不同分為:靜態(tài)存儲分配:直接用定長的字符數(shù)組來定義。優(yōu)點(diǎn)是涉及串長的操作速度快,但不適合插

入、操作。動態(tài)存儲分配:是在定義串時不分配存儲空間,需要使用時按所需串的長度分配存儲單元。

●串的鏈?zhǔn)酱鎯褪怯脝捂湵淼姆绞酱鎯Υ?串的這種鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點(diǎn)數(shù)據(jù)域為單

個字符。為了解決“存儲密度”低的狀況,可以讓一個結(jié)點(diǎn)存儲多個字符,即結(jié)點(diǎn)的大小。

●順序串上子串定位的運(yùn)算:又稱串的“模式匹配”或“串匹配”,是在主串中查找出子串出現(xiàn)的位置。在串匹配中,將主串稱為目標(biāo), 子串稱為模式。這是比較容易理解的,串匹配問題就是找出給定模式串P在給定目標(biāo)串T中首次出現(xiàn)的有效位移或者是全部有效位移。最壞的情況下時間復(fù)雜度是Om,假如m與n同階的話則它是O。鏈串上的子串定位運(yùn)算位移是結(jié)點(diǎn)地址而不是整數(shù)。

●數(shù)組一般用順序存儲的方式表示。

●存儲的方式有:行優(yōu)先順序,也就是把數(shù)組逐行依次排列。PASCAL、C。列優(yōu)先順序,就是把數(shù)組逐列依次排列。FORTRAN ●地址的計算方法:按行優(yōu)先順序排列的數(shù)組:LOC(a=?.。按列優(yōu)先順序排列的數(shù)組:LOC(a=?.矩陣的壓縮存儲:為多

個相同的非零元素分配一個存儲空間;對零元素不分配空間。

●特殊矩陣的概念:所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。

●稀疏矩陣的概念:一個矩陣中若其非零元素的個數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個數(shù),則該矩陣稱為稀疏矩陣。

●特殊矩陣的類型:對稱矩陣:三角矩陣:上三角陣,下三角陣,對角矩陣k=f(I,j, ●廣義表是n個元素的有限序列,其中的元素是原子或者是一個廣義表。廣義表表頭和表尾的概念: ●廣義表有兩種表示法,一種是括號表示法,一種是圖形表示法。

●廣義表有兩個特殊的基本運(yùn)算:取表頭head:取表中的第一個數(shù)據(jù)元素,不能對空表操作。取表尾tail;取除表頭外,其余數(shù)據(jù)元

素構(gòu)成的子表,不能對空表操作

●樹是n個結(jié)點(diǎn)的有限集合,非空時必須滿足:只有一個稱為根的結(jié)點(diǎn);其余結(jié)點(diǎn)形成m個不相交的子集,并稱根的子樹。根是開始

結(jié)點(diǎn);結(jié)點(diǎn)的子樹數(shù)稱度;度為0的結(jié)點(diǎn)稱葉子;度不為0的結(jié)點(diǎn)稱分支結(jié)點(diǎn);除根外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn);●有序樹是子樹有左,右之分的樹;無序樹是子樹沒有左,右之分的樹;森林是m個互不相交的樹的集合;●樹的四種不同表示方法:樹形表示法;嵌套集合表示法;凹入表示法;廣義表表示法。

●二叉樹的定義:是n≥0個結(jié)點(diǎn)的有限集,它是空集或由一個根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹

組成。二叉樹不是樹的特殊情形,與度數(shù)為2的有序樹不同。二叉樹的4個重要性質(zhì): ●二叉樹的順序存儲結(jié)構(gòu)就是把二叉樹的所有結(jié)點(diǎn)按照層次順序存儲到連續(xù)的存儲單元中。

●樹的存儲結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯Α６鏄涞逆準(zhǔn)酱鎯Y(jié)構(gòu),稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個指針域, n+1個空指針。

●根據(jù)結(jié)點(diǎn)的次序不同可得三種遍歷:先序遍歷,中序遍歷、后序遍歷。時間復(fù)雜度為。

●利用二叉鏈表中的n+1個空指針域來存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針,這些附加的指針就稱為“線索”,加

上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡單有效,但對于查找指定結(jié)點(diǎn)的前序前趨和后序后繼并沒有什么作用。

●樹和森林及二叉樹的轉(zhuǎn)換是唯一對應(yīng)的。二叉樹變樹:結(jié)點(diǎn)的右孩子與其雙親連。森林變二叉樹:樹變二叉樹,各個樹的根相連。

轉(zhuǎn)換方法? ●樹的存儲結(jié)構(gòu):有雙親鏈表表示法:孩子鏈表表示法:雙親孩子鏈表表示法:孩子兄弟鏈表表示法: ●樹的前序遍歷與相對應(yīng)的二叉樹的前序遍歷一致;樹的后序遍歷與相對應(yīng)的二叉樹的中序遍歷一致。

●樹的帶權(quán)路徑長度?最優(yōu)二叉樹?完全二叉樹?哈夫曼樹及其性質(zhì)，●變長編碼技術(shù)可以使頻度高的字符編碼短,而頻度低的字符編碼長,但是變長編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三

個碼無法在解碼時確定是哪一個,所以要求在字符編碼時任一字符的編碼都不是其他字符編碼的前綴,這種碼稱為前綴碼。哈夫曼樹的應(yīng)用。

●圖的邏輯結(jié)構(gòu)特征就是其結(jié)點(diǎn)的前趨和后繼的個數(shù)都是沒有限制的,即任意兩個結(jié)點(diǎn)之間之間都可能相關(guān)。

●圖,有向圖,無向圖,簡單路徑,簡單回路,網(wǎng)絡(luò)等及其性質(zhì)。

●圖的存儲結(jié)構(gòu):鄰接矩陣表示法:適合稠密圖。無向鄰接矩陣是對稱的。有向行是出度,列是入度。建立鄰接矩陣算法的時間是

O,其時間復(fù)雜度為O。鄰接表表示法:適合稀疏圖。時間復(fù)雜度為O,空間復(fù)雜度為O。

●圖的遍歷:深度優(yōu)先遍歷:借助于鄰接矩陣的列。使用棧保存已結(jié)點(diǎn)。廣度優(yōu)先遍歷:借助于鄰接矩陣的行。使用隊列保存已結(jié)

點(diǎn)。

●生成樹的定義:最小生成樹:Prim算法的時間復(fù)雜度為O與邊數(shù)無關(guān)適于稠密圖。Kruskal算法的時間復(fù)雜度為O,主要取決于邊

數(shù),較適合于稀疏圖。

●最短路徑的算法:Dijkstra算法,時間復(fù)雜度為O。

●拓?fù)渑判?無前趨的頂點(diǎn)優(yōu)先:每次輸出一個無前趨的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其出邊,最后得到的序列即拓?fù)湫蛄小o后繼的結(jié)點(diǎn)

優(yōu)先:每次輸出一個無后繼的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其入邊,最后得到的序列是逆拓?fù)湫蛄小?/p>

●關(guān)于排序

●關(guān)鍵字項,關(guān)鍵字。

●排序是使文件中的記錄按關(guān)鍵字遞增次序排列起來。●基本操作:比較關(guān)鍵字大小;改變指向記錄的指針或移動記錄。

●存儲結(jié)構(gòu):順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)。經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變,則稱這種排序方

法是穩(wěn)定的,否則排序算法是不穩(wěn)定的。

●排序過程中不涉及數(shù)據(jù)的內(nèi)、外存交換則稱之為“內(nèi)部排序”,反之,若存在數(shù)據(jù)的內(nèi)外存交換,則稱之為外排序。

●內(nèi)部排序方法可分五類:插入排序、選擇排序、交換排序、歸并排序和分配排序。

●評價排序算法好壞的標(biāo)準(zhǔn)主要有兩條:執(zhí)行時間和所需的輔助空間,另外算法的復(fù)雜程序也是要考慮的一個因素。

●插入排序:直接插入排序;逐個向前插入到合適位置;哨兵有兩個作用;作為臨變量存放R[i];是在查找循環(huán)中用來監(jiān)視下標(biāo)變量j是否

越界;直接插入排序是穩(wěn)定排序。時間復(fù)雜度為O ?比較次數(shù)為/2;移動次數(shù)為?。希爾排序:等間隔的數(shù)據(jù)比較并按要求順序排列,最后間隔為1;希爾排序是就地的不穩(wěn)定排序。時間復(fù)雜度為O,比較次數(shù)為;移動次數(shù)為;●交換排序:冒泡排序:自下向上確定最輕的一個。自上向下確定最重的一個。冒泡排序是就地的穩(wěn)定排序。時間復(fù)雜度為O?比

較次數(shù)為?;移動次數(shù)為?;快速排序:以第一個元素為參考基準(zhǔn),設(shè)定、動兩個指針,發(fā)生交換后指針交換位置,直到指針重合。

重復(fù)直到排序完成。快速排序是不穩(wěn)定排序。時間復(fù)雜度為O?比較次數(shù)為?。●選擇排序:直接選擇排序;選擇最小的放在比較區(qū)前;直接選擇排序不穩(wěn)定排序。時間復(fù)雜度為O?。比較次數(shù)為?。堆排序:建堆: 按層次將數(shù)據(jù)填入完全二叉樹,從int處向前逐個調(diào)整位置。然后將樹根與最后一個葉子交換值并斷開與樹的連接并重建堆,直到全斷開。堆排序是就地不穩(wěn)定的排序,時間復(fù)雜度為O,不適宜于記錄數(shù)較少的文件。

●歸并排序:先兩個一組排序,形成/2組,再將兩組并一組,直到剩下一組為止。歸并排序是非穩(wěn)定排序,時間復(fù)雜度是O? ●基數(shù)排序:從低位到高位依次對關(guān)鍵字進(jìn)行箱排序。基數(shù)排序是非就穩(wěn)定的排序,時間復(fù)雜度是O?。

●各種排序方法的比較和選擇: ●

1、待排序的記錄數(shù)目n;n較大的要用時間復(fù)雜度為O的排序方法;●

2、記錄的大小;記錄大最好用鏈表作為存儲結(jié)構(gòu),而快速排序和堆排序在鏈表上難于實(shí)現(xiàn);●

3、關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài);●

4、對穩(wěn)定性的要求;●

5、語言工具的條件;●

6、存儲結(jié)構(gòu);時間和輔助空間復(fù)雜度。●關(guān)于查找

●查找的同時對表做修改操作則相應(yīng)的表稱之為動態(tài)查找表,否則稱之為靜態(tài)查找表。

●衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)。

線性表查找的方法：順序查找：逐個查找，ASL=？;二分查找：取中點(diǎn) int 比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹 表示。ASL=？;分塊查找：要求“分塊有序”，將表分成若干塊內(nèi)部不一定有序，并抽取各塊中的最大關(guān)鍵字及其位置建立有序索引 表。

二叉排序樹定義是二叉排序樹是空樹或者滿足如下性質(zhì)的二叉樹：若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的 值;若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值;左、右子樹本身又是一棵二叉排序樹。

二叉排序樹的插入、建立、刪除的算法平均時間性能是

O？。二叉排序樹的刪除操作可分三種情況進(jìn)行處理：*P 是葉子，則直接刪除*P，即將*P 的雙親*parent 中指向*P 的指針域置空即可。*P 只有一個孩子*child，此時只需將*child 和*p 的雙親直接連接就可刪去*p。*p 有兩個孩子，則先將*p 結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)的數(shù) 據(jù)到*p，刪除中序后繼結(jié)點(diǎn)。

關(guān)于 B-樹。它適合在磁盤等直接存取設(shè)備上組織動態(tài)的查找表，是一種外查找算法。建立的方式是從下向上拱起。散列技術(shù)：將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲到散列表的過程稱為散列。散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡單和均勻。常見的散列 函數(shù)構(gòu)的造方法：平方取中法,除余法,相乘取整法,隨機(jī)數(shù)法。

處理沖突的方法：開放定址法：一般形式為?，開放定址法要求散列表的裝填因子 α≤1。開放定址法類型：線性探查法，二次探查 法，雙重散列法。拉鏈法：是將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)在同一個單鏈表中。拉鏈法的優(yōu)點(diǎn)：拉鏈法處理沖突簡單，且無堆積現(xiàn)象;鏈表上的結(jié)點(diǎn)空間是動態(tài)申請的適于無法確定表長的情況;拉鏈法中 α 可以大 于 1，結(jié)點(diǎn)較大時其指針域可忽略，因此節(jié)省空間;拉鏈法構(gòu)造的散列表刪除結(jié)點(diǎn)易實(shí)現(xiàn)。

拉鏈法也有缺點(diǎn)：當(dāng)結(jié)點(diǎn)規(guī)模較小時，用拉鏈法中的指針域也要占用額外空間，還是開放定址法省空間。

第四篇：《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱

Data Structure 執(zhí)筆人：

編寫日期：

一、課程基本信息

1.課程編號：

2.課程性質(zhì)/類別： 必修課 / 專業(yè)主干課

3.學(xué)時/學(xué)分： 48 學(xué)時（另實(shí)驗16學(xué)時）/ 4 學(xué)分

4.適用專業(yè)：計算機(jī)科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程、信息管理與信息系統(tǒng)等專業(yè)

二、課程教學(xué)目標(biāo)及學(xué)生應(yīng)達(dá)到的能力

數(shù)據(jù)結(jié)構(gòu)課程是計算機(jī)相關(guān)專業(yè)的專業(yè)基礎(chǔ)課、必修課程，主要介紹用計算機(jī)解決一系列問題特別是非數(shù)值信息處理問題時所用的各種組織數(shù)據(jù)的方法、存儲數(shù)據(jù)結(jié)構(gòu)的方法以及在各種結(jié)構(gòu)上執(zhí)行操作的算法。通過本課程的學(xué)習(xí)，要求學(xué)生掌握各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲表示、運(yùn)算方法以及在計算機(jī)科學(xué)中最基本的應(yīng)用，培養(yǎng)、訓(xùn)練學(xué)生選用合適的數(shù)據(jù)結(jié)構(gòu)和編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序的能力，培養(yǎng)學(xué)生分析問題、解決問題的能力，并為后續(xù)課程的學(xué)習(xí)打下良好的理論基礎(chǔ)和實(shí)踐基礎(chǔ)。

三、課程教學(xué)內(nèi)容與基本要求

（一）緒論（3 學(xué)時）1．主要內(nèi)容：

（1）介紹什么是數(shù)據(jù)結(jié)構(gòu)；

（2）基本概念和術(shù)語: 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象，以及數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)（理解）數(shù)據(jù)類型、抽象數(shù)據(jù)類型；

（3）抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)；

（4）算法和算法分析: 算法的概念、算法設(shè)計的要求以及算法效率的度量。2．基本要求

（1）了解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性；

（2）掌握數(shù)據(jù)結(jié)構(gòu)的定義及相關(guān)概念和術(shù)語；（3）了解抽象數(shù)據(jù)類型的定義、表示與實(shí)現(xiàn)方法；（4）理解算法的概念、特點(diǎn)并掌握度量其效率的基本方法。3．自學(xué)內(nèi)容：

類C語言的書寫規(guī)范。

（二）線性表（6 學(xué)時）1．主要內(nèi)容：

（1）線性表的抽象數(shù)據(jù)類型定義和相關(guān)概念：數(shù)據(jù)項、記錄、文件等；（2）線性表順序存儲表示和基本操作的實(shí)現(xiàn)；（3）線性表的鏈?zhǔn)酱鎯Ρ硎竞突静僮鞯膶?shí)現(xiàn)；

（4）稀疏多項式的抽象數(shù)據(jù)類型定義、表示和加法的實(shí)現(xiàn)。2．基本要求

（1）掌握線性表的定義和特點(diǎn)；

（2）熟練掌握線性表的順序存儲表示和插入、刪除、查找等實(shí)現(xiàn)算法；

（3）熟練掌握單鏈表、循環(huán)鏈表、雙向鏈表三種鏈表的表示，以及單鏈表的查找、插入、刪除、創(chuàng)建等實(shí)現(xiàn)算法。

3．自學(xué)內(nèi)容：

靜態(tài)鏈表。

（三）棧和隊列（5 學(xué)時）1．主要內(nèi)容：

（1）棧和隊列的結(jié)構(gòu)特性和抽象數(shù)據(jù)類型定義；（2）棧和隊列的順序存儲表示和實(shí)現(xiàn)；（3）棧和隊列的鏈?zhǔn)酱鎯Ρ硎竞蛯?shí)現(xiàn)；（4）棧和隊列在程序設(shè)計中的應(yīng)用。2．基本要求

（1）掌握棧和隊列兩種抽象數(shù)據(jù)類型的特點(diǎn)；

（2）掌握棧的兩種存儲表示和實(shí)現(xiàn)，特別注意棧滿棧空的條件；（3）掌握隊列的兩種存儲表示和實(shí)現(xiàn)，特別注意隊滿隊空的條件；（4）了解遞歸算法與棧的關(guān)系。3．自學(xué)內(nèi)容：

鏈棧，離散事件模擬

（四）串（3 學(xué)時）1．主要內(nèi)容：

（1）串的抽象數(shù)據(jù)類型定義；

（2）串的表示和實(shí)現(xiàn): 定長順序存儲結(jié)構(gòu)和堆分配存儲結(jié)構(gòu)；（3）串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用；（4）串的模式匹配操作。2．基本要求

（1）熟悉串的一些基本操作的定義，并能利用基本操作實(shí)現(xiàn)串的其它操作；（2）掌握串的定長順序存儲結(jié)構(gòu)以及基本操作的實(shí)現(xiàn)；（3）掌握串的堆分配存儲結(jié)構(gòu)以及基本操作的實(shí)現(xiàn)；（4）掌握串的簡單模式匹配算法，理解KMP算法。3．自學(xué)內(nèi)容：

串操作的應(yīng)用實(shí)例。

（五）數(shù)組和廣義表（4 學(xué)時）1．主要內(nèi)容：

（1）數(shù)組的抽象數(shù)據(jù)類型定義及其順序表示和實(shí)現(xiàn)；（2）特殊矩陣和稀疏矩陣的壓縮存儲；（3）廣義表的抽象數(shù)據(jù)類型定義和存儲結(jié)構(gòu)。2．基本要求

（1）了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法；（2）掌握對特殊矩陣進(jìn)行壓縮存儲時的下標(biāo)變換公式；

（3）熟悉稀疏矩陣的三元組順序表存儲結(jié)構(gòu)下的一般轉(zhuǎn)置和快速轉(zhuǎn)置算法；了解十字鏈表等存儲結(jié)構(gòu)；

（4）掌握廣義表的結(jié)構(gòu)特點(diǎn)、取表頭表尾操作，及其存儲表示方法。3．自學(xué)內(nèi)容：

采用十字鏈表存儲結(jié)構(gòu)創(chuàng)建稀疏矩陣。

（六）樹和二叉樹（10 學(xué)時）1．主要內(nèi)容：

（1）樹的抽象數(shù)據(jù)類型定義和基本術(shù)語；

（2）二叉樹的抽象數(shù)據(jù)類型定義、性質(zhì)和存儲結(jié)構(gòu)；（3）二叉樹的遍歷；

（4）線索二叉樹的定義、遍歷及線索化二叉樹；

（5）樹的存儲結(jié)構(gòu)、樹和森林的遍歷以及與二叉樹的轉(zhuǎn)換；（6）Huffman樹及其應(yīng)用。2．基本要求

（1）掌握樹型結(jié)構(gòu)的特點(diǎn)和基本術(shù)語；

（2）熟練掌握二叉樹的性質(zhì)，了解相應(yīng)的證明方法；

（3）了解二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，熟練掌握二叉鏈表存儲結(jié)構(gòu)；（4）熟練掌握二叉樹三種遍歷的遞歸算法和中序遍歷非遞歸算法，能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其他操作；

（5）熟練掌握二叉樹的線索化過程，以及在中序線索二叉樹上找結(jié)點(diǎn)的前驅(qū)與后繼的方法；

（6）熟悉樹的各種存儲結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法；（7）了解Huffman樹的特性，掌握建立Huffman樹和Huffman編碼的方法。3．自學(xué)內(nèi)容：

先序、后序遍歷二叉樹非遞歸算法，層次遍歷二叉樹算法。

（七）圖（9 學(xué)時）1．主要內(nèi)容：（1）圖的定義和術(shù)語；

（2）圖的四種存儲結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）、鄰接表、十字鏈表和鄰接多重表；（3）圖的兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；（4）圖的連通性和最小生成樹；

（5）有向無環(huán)圖及其應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑；（6）最短路徑問題。2．基本要求

（1）熟悉圖的定義和術(shù)語；

（2）了解圖的存儲結(jié)構(gòu)，熟練掌握數(shù)組表示法（鄰接矩陣）和鄰接表存儲表示；（3）熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法；（4）掌握無向連通帶權(quán)圖的最小生成樹求解算法；

（5）了解有向無環(huán)圖、AOV網(wǎng)、AOE網(wǎng)及其在實(shí)際中的應(yīng)用，熟悉拓?fù)渑判蛩惴ê完P(guān)鍵路徑算法；

（6）熟悉兩種最短路徑問題求解算法。3．自學(xué)內(nèi)容：

樹的先根遍歷算法與圖的深度優(yōu)先遍歷算法比較；

樹的層次遍歷算法與圖的廣度優(yōu)先遍歷算法比較。

（八）查找（4 學(xué)時）1．主要內(nèi)容：

（1）查找的基本概念和相關(guān)術(shù)語；

（2）靜態(tài)查找表：順序查找、折半查找和索引順序表查找；（3）動態(tài)查找表：二叉排序樹的查找、插入和刪除；（4）哈希表。2．基本要求

（1）了解查找的作用，熟悉相關(guān)術(shù)語；

（2）熟練掌握順序查找、折半查找和索引順序表查找；（3）熟練掌握二叉排序樹的特性、構(gòu)造和查找方法；

（4）熟練掌握哈希表的構(gòu)造方法，特別是哈希函數(shù)和處理沖突方法的選取；（5）通過分析等概率下的平均查找長度來衡量各種查找方法的效率。3．自學(xué)內(nèi)容：

平衡二叉樹。

（九）內(nèi)部排序（4 學(xué)時）1．主要內(nèi)容：

（1）排序的基本概念和相關(guān)術(shù)語；

（2）插入排序：直接插入排序、折半插入排序和希爾排序；（3）交換排序：起泡排序和快速排序；（4）選擇排序：簡單選擇排序和堆排序；（5）歸并排序：二路歸并排序；（6）基數(shù)排序：鏈?zhǔn)交鶖?shù)排序；（7）各種內(nèi)部排序方法的比較討論。2．基本要求

（1）了解排序作用，熟悉相關(guān)術(shù)語；

（2）掌握多種排序的基本思想、算法特點(diǎn)和排序過程，分析它們的時間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性。

3．自學(xué)內(nèi)容：

二路插入排序、表插入排序和樹形選擇排序。

四、教學(xué)安排建議

1.作業(yè)練習(xí) 完成每章的教學(xué)后進(jìn)行布置習(xí)題，使用教材配套的《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》。盡量選擇基礎(chǔ)的并且加注了標(biāo)記的題，應(yīng)注重于精，而不要求多。要求積極獨(dú)立完成所布置的習(xí)題，建議安排至少六次。

2.案例分析

可參考選擇以下一些案例：（1）學(xué)生通訊錄管理系統(tǒng)，（2）表達(dá)式求值問題（3）交通咨詢系統(tǒng)，等。3.專題研討

可參考選擇以下一些：（1）最小生成樹問題（2）航班信息查詢與檢索系統(tǒng)，（3）內(nèi)部排序算法比較，等。

4.實(shí)驗安排

為了達(dá)到理論與實(shí)際應(yīng)用的結(jié)合，讓學(xué)生能將所學(xué)知識應(yīng)用于實(shí)際問題的求解中，培養(yǎng)學(xué)生的實(shí)際動手能力，從而加深對概念及所學(xué)知識的理解，靈活、牢固掌握教材內(nèi)容，提高程序設(shè)計及解決實(shí)際問題的能力，實(shí)驗環(huán)節(jié)的安排非常重要。

建議實(shí)驗安排為八次，共16學(xué)時，分別如下：

實(shí)驗1 線性表的順序存儲結(jié)構(gòu)的實(shí)現(xiàn)(2學(xué)時)

實(shí)驗2 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的實(shí)現(xiàn)(2學(xué)時)

實(shí)驗3 棧的算法實(shí)現(xiàn)(2學(xué)時)

實(shí)驗4 隊列的算法實(shí)現(xiàn)(2學(xué)時)

實(shí)驗5 串類型及操作(2學(xué)時)

實(shí)驗6 二叉樹的建立與遍歷(2學(xué)時)

實(shí)驗7 圖的建立與遍歷(2學(xué)時)

實(shí)驗8 查找與排序(2學(xué)時)注：教師可根據(jù)教學(xué)實(shí)際情況（如：學(xué)生情況及學(xué)時情況等），適當(dāng)調(diào)整實(shí)踐教學(xué)內(nèi)容及學(xué)時分配。

五、課程考核

1.考核形式及成績評定辦法

本課程考核形式為：平時成績占40%，期末考試成績占60%。其中平時成績的結(jié)構(gòu)分包括：課堂表現(xiàn)10%、平時作業(yè)10%和實(shí)驗20%，期末考試為閉卷筆試考試：120分鐘，卷面分滿分100分。期末考試成績低于50分者，本課程成績按不及格論處。

2.本課程考核的基本要求

課堂表現(xiàn)10%：包括課堂考勤和課堂提問，如果缺課課時達(dá)到本課程教學(xué)時數(shù)的1/3，則取消考試資格。

平時作業(yè)10%：根據(jù)上交次數(shù)及完成情況進(jìn)行評定。

實(shí)驗20%：根據(jù)各次實(shí)驗完成情況及實(shí)驗報告成績進(jìn)行評定。

期末考試60%：本課程的期末考試考核內(nèi)容主要包括線性表、棧與隊列、串、數(shù)組與廣義表、樹與二叉樹、圖、查找和內(nèi)部排序。其中，線性表、二叉樹、圖、查找和內(nèi)部排序內(nèi)容為考核的重點(diǎn)。

六、本課程與其它課程的先行后續(xù)關(guān)系

先行課程：《高級程序設(shè)計語言》、《離散數(shù)學(xué)》

后續(xù)課程：《操作系統(tǒng)》、《編譯原理》、《數(shù)據(jù)庫理論》、《算法分析與設(shè)計》等

七、建議教材及教學(xué)參考書

1.教材：

嚴(yán)蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，清華大學(xué)出版，2012.5 嚴(yán)蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》，清華大學(xué)出版，2012.5 2.參考書：

[1] 許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結(jié)構(gòu)》，高等教育出版社，2004.[2] 徐孝凱，《數(shù)據(jù)結(jié)構(gòu)簡明教程》，清華大學(xué)出版社，1995 [3] 陳文博，朱青，《數(shù)據(jù)結(jié)構(gòu)與算法》，機(jī)械工業(yè)出版社，1996 [4] 李云清，楊慶紅，揭安全編著，《數(shù)據(jù)結(jié)構(gòu)》（C語言版），人民郵電出版社，2007.[5] 楊秀金主編，《數(shù)據(jù)結(jié)構(gòu)》，西安電子科技大學(xué)出版社，2002.[6] 李廉治，姜文清，郭福順，《數(shù)據(jù)結(jié)構(gòu)》，大連理工大學(xué)出版社，1989

[7] Aho A V, Hopcroft J E, Ullman J D.Data Structures and Algorithms.Addison-Wesley Publishing Company,Inc.,1983

[8] Baron R J, Shapiro L G.Data Structures and their Implementation.Van Nostrand Reinhold Company, 1980

[9] Esakov J, Weiss T.Data Structures: An Advanced Approach Using C.Prentice-Hall, Inc.,1989

[10] [美]S巴斯《計算機(jī)算法：設(shè)計和分析引論》朱洪等譯，復(fù)旦大學(xué)出版社，1985

第五篇：數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱

數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱

一、課程基本概況

課程名稱：數(shù)據(jù)結(jié)構(gòu)

課程名稱（英文）： Data Structures

課程編號：B09042

課程總學(xué)時：60（其中，講課48，實(shí)驗12）

課程學(xué)分：3

課程分類：專業(yè)選修課

開設(shè)學(xué)期：4

適用專業(yè)：計算機(jī)網(wǎng)絡(luò)工程本科

先修課程：集合論，圖論，高級語言（結(jié)構(gòu)或記錄，指針）

后續(xù)課程：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等

二、課程的性質(zhì)、目的和任務(wù)

數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)的一門核心專業(yè)課程，是軟件課程中非常重要的一門課程，在整個專業(yè)教學(xué)中占有十分重要的地位，是一門理論性非常強(qiáng)的課程。通過課堂教學(xué)、課外練習(xí)和上機(jī)實(shí)習(xí)，使學(xué)生了解數(shù)據(jù)對象的特性，數(shù)據(jù)組織的基本方法，并初步具備分析和解決現(xiàn)實(shí)世界問題在計算機(jī)中如何表示和處理的能力以及培養(yǎng)良好的程序設(shè)計技能，為后續(xù)課程的學(xué)習(xí)和科研工作的參與打下良好的基礎(chǔ)。

三、主要內(nèi)容、重點(diǎn)及深度

本門課程共60學(xué)時，其中理論教學(xué)48學(xué)時，實(shí)驗教學(xué)12學(xué)時。其中，理論教學(xué)部分：

第一章

緒論

（一）目的要求

了解數(shù)據(jù)結(jié)構(gòu)的意義與發(fā)展過程、數(shù)據(jù)結(jié)構(gòu)在計算機(jī)科學(xué)中的作用、學(xué)習(xí)本課程的目的、任務(wù)及要求。理解數(shù)據(jù)結(jié)構(gòu)的基本概念；算法設(shè)計；掌握算法的時間和空間復(fù)雜度。

（二）教學(xué)內(nèi)容 本章知識點(diǎn)：

1.相關(guān)的基本概念(掌握)；

2.算法五大要素(掌握)；

3.計算語句頻度和估算算法時間復(fù)雜度的方法（掌握）。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義；算法的描述方法。

難點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義；算法與程序的區(qū)別；時間復(fù)雜度及其計算。

第二章

線性表

（一）目的要求

掌握線性表的邏輯結(jié)構(gòu)；線性表的存儲結(jié)構(gòu)及操作的實(shí)現(xiàn)；理解一元多項式的表示；

（二）教學(xué)內(nèi)容 本章知識點(diǎn)：

1.線性表的邏輯結(jié)構(gòu)(掌握)；2.線性表的存儲結(jié)構(gòu)(掌握)；

3.線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)基本操作的方法(掌握)；

4.從時間和空間復(fù)雜度的角度比較線性表兩種存儲結(jié)構(gòu)的不同特點(diǎn)及其適用場合(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：線性表的概念；線性表的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)及其常用算法。難點(diǎn)：鏈?zhǔn)酱鎯Y(jié)構(gòu)及其常用算法；雙向循環(huán)鏈表。

第三章 棧和隊列

（一）目的要求

掌握棧的定義，表示及實(shí)現(xiàn)；表達(dá)式求值；棧與遞歸過程；隊列的定義、表示及實(shí)現(xiàn)。

（二）教學(xué)內(nèi)容 本章知識點(diǎn)： 1.棧和隊列的特點(diǎn)(掌握)；

2.在兩種存儲結(jié)構(gòu)上棧的基本操作的實(shí)現(xiàn)(掌握)； 3.循環(huán)隊列和鏈隊列的基本運(yùn)算(熟練掌握)； 4.遞歸算法執(zhí)行過程中棧狀態(tài)的變化過程(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：堆棧和隊列的概念；遞歸的定義；循環(huán)隊列和鏈隊列的基本運(yùn)算。難點(diǎn)：遞歸的編程實(shí)現(xiàn)；循環(huán)隊列和鏈隊列的基本運(yùn)算。

第四章 串

（一）目的要求

了解串的邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)；掌握串操作的實(shí)現(xiàn)(重點(diǎn)難點(diǎn)BF和KMP算法)串的應(yīng)用。

（二）教學(xué)內(nèi)容 本章知識點(diǎn)：

1.串的七種基本運(yùn)算的定義（了解）；

2.利用這些基本運(yùn)算來實(shí)現(xiàn)串的其它各種運(yùn)算的方法(掌握)； 3.在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法(掌握)；

4.KMP算法，熟悉NEXT函數(shù)和改進(jìn)NEXT函數(shù)的定義和計算(掌握)； 5.串名的存儲映象和在堆存儲結(jié)構(gòu)實(shí)現(xiàn)串操作的方法(理解)。

（三）重點(diǎn)與難點(diǎn) 重點(diǎn)：串定義和存儲方法；串的操作 難點(diǎn)：串操作實(shí)現(xiàn)方法

第五章 數(shù)組和廣義表

（一）目的要求

掌握數(shù)組的存儲結(jié)構(gòu)；稀疏矩陣的表示及操作的實(shí)現(xiàn)；廣義表的定義和存儲結(jié)構(gòu)；廣義表的遞歸算法。

（二）教學(xué)內(nèi)容 本章知識點(diǎn)：1.數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法(掌握)； 2.矩陣實(shí)現(xiàn)壓縮存儲時的下標(biāo)變換(掌握)；

3.理解稀疏矩陣的兩種存儲方式的特點(diǎn)和適用范圍，領(lǐng)會以三元組表示稀疏矩陣時進(jìn)行運(yùn)算采用的處理方法(掌握)；

4.廣義表的定義及其存儲結(jié)構(gòu)，學(xué)會廣義表的表頭，表尾分析方法(掌握)； 5.學(xué)習(xí)編制廣義表的遞歸算法(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：多維數(shù)組元素存儲地址的計算；稀疏矩陣的三元組表示；廣義表的存儲定義、操作。難點(diǎn)：稀疏矩陣的三元組表示；廣義表的存儲定義、操作。

第六章 樹和二叉樹

（一）目的要求

了解樹的基本概念；理解二叉樹的性質(zhì)和存儲結(jié)構(gòu)；遍歷二叉樹和線索二叉樹；理解樹的存儲結(jié)構(gòu)和遍歷；集合的一種表示方法；掌握哈夫曼樹及其應(yīng)用；

（二）教學(xué)內(nèi)容 本章知識點(diǎn)： 1.二叉樹的結(jié)構(gòu)特點(diǎn)(理解)；

2.二叉樹的各種存儲結(jié)構(gòu)的特點(diǎn)及適用范圍(掌握)； 3.按各種次序遍歷二叉樹的遞歸和非遞歸算法(掌握)；

4.二叉樹的線索化，在中序線索樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法(掌握)； 5.樹的各種存儲結(jié)構(gòu)及其特點(diǎn)(掌握)； 6.編寫樹的各種運(yùn)算的算法(掌握)；

7.建立最優(yōu)二叉樹和哈夫曼編碼的方法(掌握)。

（三）重點(diǎn)與難點(diǎn) 重點(diǎn)：二叉樹的概念、性質(zhì)；二叉樹的遍歷方式；構(gòu)造二叉排序樹。難點(diǎn)：二叉樹的遍歷方式；二叉排序樹的構(gòu)造方法；二叉樹的線索化。

第七章 圖

（一）目的要求

理解圖的基本概念；圖的存儲結(jié)構(gòu)；掌握圖的遍歷及應(yīng)用{最小生成樹，最短路徑等}；拓?fù)渑判蚝完P(guān)鍵路徑。

（二）教學(xué)內(nèi)容 本章知識點(diǎn)： 1.熟悉圖的各種存儲結(jié)構(gòu)；

2.了解實(shí)際問題與采用何種存儲結(jié)構(gòu)和算法有密切聯(lián)系(掌握)； 3.遍歷圖的遞歸和非遞歸算法(掌握)；

4.應(yīng)用圖的遍歷算法求各種簡單路徑問題（比如，最小生成樹、最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑等）(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：圖的存儲結(jié)構(gòu)；圖的遍歷 難點(diǎn)：圖遍歷的算法；

第八章

動態(tài)存儲管理

（一）目的要求

了解邊界標(biāo)識法和伙伴系統(tǒng)；無用單元收集和緊縮；

（二）教學(xué)內(nèi)容 本章知識點(diǎn)：

1.存儲器分配策略和算法（了解）；

2.無用單元收集時的標(biāo)志算法（了解）。

（三）重點(diǎn)與難點(diǎn)

存儲器分配策略和算法、無用單元收集時的標(biāo)志算法

第九章

查找

（一）目的要求

了解靜態(tài)查找表(順序表，有序表，索引順序表)；動態(tài)查找表(二叉排序樹，平衡二叉樹，B-樹和B+樹)的建立和查找；掌握哈希表的建立，查找及分析；

（二）教學(xué)內(nèi)容 本章知識點(diǎn)：

1.順序查找、折半查找和索引查找的方法、應(yīng)用(掌握)；

2.二叉排序樹的構(gòu)造方法(掌握)；

3.二叉平衡樹的建立方法(掌握)；

4.B-樹，B+樹和鍵樹的特點(diǎn)以及它們的建立過程（理解）；

5.哈希表的構(gòu)造方法(掌握)；

6.按定義計算各種查找方法在等概率情況下查找成功時和失敗時的平均查找長度；

7.哈希表在查找不成功時的平均查找長度的計算方法(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：二叉排序樹的構(gòu)造方法、二叉平衡樹的建立方法；哈希表的構(gòu)造、應(yīng)用；

難點(diǎn)：二叉排序樹的構(gòu)造及應(yīng)用；哈希表的構(gòu)造方法；查找的平均長度。

第十章

內(nèi)部排序

（一）目的要求

掌握插入排序、交換排序(起泡排序，快速排序)、選擇排序(簡單選擇，樹形選擇，堆)、歸并排序、基數(shù)排序等算法。

（二）教學(xué)內(nèi)容 本章知識點(diǎn)：

1.各種排序方法的特點(diǎn)并能靈活應(yīng)用(掌握)； 2.各種方法的排序過程(掌握)；

3.各種排序方法的時間復(fù)雜度分析(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：各種排序方法的特點(diǎn)及其應(yīng)用；實(shí)現(xiàn)排序的各種算法。難點(diǎn)：各種排序算法的時間復(fù)雜度分析。

十一章

外部排序

（一）目的要求

理解外部排序的基本方法；掌握敗者樹和多路平衡歸并的實(shí)現(xiàn)；置換--選擇排序；最佳歸并樹。

（二）教學(xué)內(nèi)容 本章知識點(diǎn)：

1.外部排序的兩個過程(理解)；

2.外排過程中所需進(jìn)行外存讀/寫次數(shù)的計算方法(掌握)；

3.敗者樹的建立過程(掌握)；

4.實(shí)現(xiàn)多路歸并的算法(掌握)；

5.置換-選擇排序的過程(掌握)；

6.最佳歸并樹的構(gòu)造方法（熟悉）；

7.按最佳歸并樹的歸并方案進(jìn)行平衡歸并時，外存讀/寫次數(shù)的計算方法(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：外部排序過程和實(shí)現(xiàn)方法；多路并歸算法及其實(shí)現(xiàn)； 難點(diǎn)：最佳并歸樹的構(gòu)造方法及其應(yīng)用。

實(shí)踐教學(xué)部分：上機(jī)實(shí)驗分4個專題，每個專題可提供2~4個難度不等的題目供選。

實(shí)驗一

停車場管理系統(tǒng)

（一）實(shí)驗內(nèi)容 以棧模擬車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。

（二）實(shí)驗過程 編程實(shí)現(xiàn)實(shí)驗內(nèi)容。

（三）實(shí)驗教學(xué)基本要求

通過實(shí)例，使學(xué)生掌握棧和隊列兩種特殊的線性結(jié)構(gòu)，掌握棧和隊列的特點(diǎn)。實(shí)驗后學(xué)生提交實(shí)驗報告。

（四）實(shí)驗設(shè)備和材料 計算機(jī)。

（五）實(shí)驗學(xué)時 4學(xué)時

實(shí)驗二

教學(xué)計劃編制問題

（一）實(shí)驗內(nèi)容

假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。編制一個教學(xué)計劃程序。

（二）實(shí)驗過程編程實(shí)現(xiàn)實(shí)驗內(nèi)容。

（三）實(shí)驗教學(xué)基本要求

通過實(shí)例，使學(xué)生熟悉圖的各種存儲結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實(shí)驗后學(xué)生提交實(shí)驗報告。

（四）實(shí)驗設(shè)備和材料 計算機(jī)。

（五）實(shí)驗學(xué)時 2學(xué)時

實(shí)驗三

最小生成樹問題

（一）實(shí)驗內(nèi)容

利用克魯斯卡爾算法求最小生成樹。以文本形式輸出樹中各條邊以及他們的權(quán)值。

（二）實(shí)驗過程 編程實(shí)現(xiàn)實(shí)驗內(nèi)容

（三）實(shí)驗教學(xué)基本要求

通過實(shí)例，使學(xué)生熟悉圖的各種存儲結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實(shí)驗后學(xué)生提交實(shí)驗報告。

（四）實(shí)驗設(shè)備和材料 計算機(jī)。

（五）實(shí)驗學(xué)時 2學(xué)時

實(shí)驗四

哈希表設(shè)計

（一）實(shí)驗內(nèi)容

假設(shè)人名為中國人的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測再散列法處理沖突。

（二）實(shí)驗過程 編程實(shí)現(xiàn)實(shí)驗內(nèi)容

（三）實(shí)驗教學(xué)基本要求 掌握索引技術(shù)的使用。

（四）實(shí)驗設(shè)備和材料 計算機(jī)

（五）實(shí)驗學(xué)時 4學(xué)時

五、課程教學(xué)的基本要求和主要環(huán)節(jié)

本課程可采用課堂講授、課堂討論、習(xí)題課等進(jìn)行課堂教學(xué);條件允許可采用CAI、電子教案、幻燈片、參觀等進(jìn)行輔助教學(xué);每章布置3~6道習(xí)題以鞏固教學(xué);在課程后半程，安排3~4個上機(jī)實(shí)驗，讓學(xué)生應(yīng)用數(shù)據(jù)結(jié)構(gòu)的理論、方法，分組設(shè)計幾個較大的軟件，使理論與實(shí)際相結(jié)合。

考試采用閉卷方式。總成績由平時成績和考試成績組成。平時成績占30%，考試成績占70%。

六、本課程與其它課程的聯(lián)系與分工

先修課包括：集合論，圖論，高級語言（結(jié)構(gòu)或記錄，指針）；

后續(xù)課包括：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等。

七、建議教材與參考教材

《數(shù)據(jù)結(jié)構(gòu)》（C語言版）

嚴(yán)蔚敏等

清華大學(xué)出版社

1997 《數(shù)據(jù)結(jié)構(gòu)題集》

嚴(yán)蔚敏等

清華大學(xué)出版社

1999

《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》

李春葆

清華大學(xué)出版社

2004

八、負(fù)責(zé)人

撰稿人：劉景匯、李玉香

審稿人：

系（院）領(lǐng)導(dǎo)：