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

1、數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱課程編號(hào)：課程名稱：數(shù)據(jù)結(jié)構(gòu)英文名稱：Data Structure課程類型：專業(yè)基礎(chǔ)必修課總 學(xué) 時(shí)：72 講課學(xué)時(shí)：56 上機(jī)學(xué)時(shí)：16 學(xué)時(shí)：72學(xué)分：4.5適用對(duì)象：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科生先修課程：計(jì)算機(jī)導(dǎo)論、C/C+程序設(shè)計(jì)I、C/C+程序設(shè)計(jì)II、離散數(shù)學(xué)一、課程性質(zhì)、目的和任務(wù)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科各專業(yè)本科學(xué)生必修的一門專業(yè)基礎(chǔ)課，是計(jì)算機(jī)程序設(shè)計(jì)的重要理論和實(shí)踐基礎(chǔ)，是培養(yǎng)學(xué)生軟件設(shè)計(jì)能力的一門重要課程，在計(jì)算機(jī)學(xué)科的本科教學(xué)中，起著非常重要的作用。本課程研究計(jì)算機(jī)系統(tǒng)中常用的線性表、二叉樹(shù)、圖等典型數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)方法，研究各種典型排序和查找算法的設(shè)計(jì)方法

2、和性能指標(biāo)，并介紹這些數(shù)據(jù)結(jié)構(gòu)和算法在實(shí)際工程中的應(yīng)用。通過(guò)學(xué)習(xí)本課程，使學(xué)生深入理解軟件設(shè)計(jì)的基本要素和基本結(jié)構(gòu)，培養(yǎng)邏輯思維能力，提高程序設(shè)計(jì)能力。數(shù)據(jù)結(jié)構(gòu)課程是一門理論和實(shí)踐相結(jié)合的課程，上機(jī)實(shí)驗(yàn)、課程設(shè)計(jì)等實(shí)踐性環(huán)節(jié)必不可少。二、教學(xué)基本要求本課程是理論與實(shí)踐并重的課程，要求學(xué)生既要掌握數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)理論知識(shí)，又要掌握操作計(jì)算機(jī)和運(yùn)行、調(diào)試程序的基本技能；能夠熟練運(yùn)用C/C+語(yǔ)言或其它計(jì)算機(jī)語(yǔ)言編制具有中等難度的應(yīng)用程序，在實(shí)踐中培養(yǎng)獨(dú)立分析問(wèn)題和解決問(wèn)題的作風(fēng)和能力。本課程的基本要求如下。理解線性表、棧、隊(duì)列、串、數(shù)組、樹(shù)、二叉樹(shù)、圖等基本的數(shù)據(jù)邏輯結(jié)構(gòu)，掌握描述這些數(shù)據(jù)結(jié)構(gòu)、選擇合

3、適的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)各種操作的方法。熟練運(yùn)用C/C+語(yǔ)言或其它計(jì)算機(jī)語(yǔ)言表達(dá)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；熟練運(yùn)用遞歸函數(shù)表達(dá)遞歸定義、遞歸算法和遞歸結(jié)構(gòu)。理解插入、交換、選擇、歸并等多種典型排序算法的思想，掌握在線性表、樹(shù)等各種不同數(shù)據(jù)結(jié)構(gòu)中的查找算法。掌握在計(jì)算機(jī)語(yǔ)言環(huán)境中編輯、編譯、運(yùn)行程序的方法，以及單步運(yùn)行、設(shè)置斷點(diǎn)、查看變量運(yùn)行時(shí)值等調(diào)試程序的方法。三、教學(xué)內(nèi)容及要求1緒論 了解數(shù)據(jù)結(jié)構(gòu)的基本概念，了解數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)的操作，了解抽象數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。 了解算法的概念、算法描述的方法、算法設(shè)計(jì)目標(biāo)和算法分析方法，掌握算法的時(shí)間復(fù)雜度分析方法。2線性表 理解線性表的邏輯結(jié)

4、構(gòu)和基本操作。 掌握線性表的順序存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)方法。 掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和實(shí)現(xiàn)方法；比較兩種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)和性能。 掌握單向鏈表、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表的概念和基本設(shè)計(jì)方法。3串 理解串的概念和串的基本操作，理解串的靜態(tài)存儲(chǔ)結(jié)構(gòu)、動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 掌握串的定義和基本操作的實(shí)現(xiàn)方法。 掌握串的模式匹配方法。4棧和隊(duì)列 理解棧的概念和作用，掌握順序棧和鏈?zhǔn)綏５脑O(shè)計(jì)方法，掌握使用棧的算法設(shè)計(jì)方法。理解棧在遞歸等算法中的應(yīng)用。 理解隊(duì)列的概念和作用，掌握順序循環(huán)隊(duì)列和鏈?zhǔn)疥?duì)列的設(shè)計(jì)方法，掌握使用隊(duì)列的算法設(shè)計(jì)方法。5數(shù)組和廣義表 理解數(shù)組的概念，理解一維數(shù)組和二維數(shù)組的

5、存儲(chǔ)結(jié)構(gòu)。 了解特殊矩陣的壓縮存儲(chǔ)方法。 了解稀疏矩陣的基本壓縮存儲(chǔ)方法。 了解廣義表的概念和存儲(chǔ)結(jié)構(gòu)。6樹(shù)和二叉樹(shù) 了解樹(shù)的定義、樹(shù)的術(shù)語(yǔ)、樹(shù)的表示方法和樹(shù)的幾種典型存儲(chǔ)結(jié)構(gòu)。 理解二叉樹(shù)的定義、二叉樹(shù)的性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和二叉樹(shù)的多種遍歷算法的基本概念。 掌握二叉樹(shù)結(jié)點(diǎn)類、二叉樹(shù)類的設(shè)計(jì)與實(shí)現(xiàn)；掌握多種二叉樹(shù)遍歷算法實(shí)現(xiàn)，比較二叉樹(shù)遍歷遞歸算法與非遞歸算法的實(shí)現(xiàn)和特點(diǎn)。 理解線索二叉樹(shù)的概念，掌握線索二叉樹(shù)結(jié)點(diǎn)類、中序線索二叉樹(shù)類的設(shè)計(jì)與實(shí)現(xiàn)，掌握中序線索化二叉樹(shù)的遞歸算法。 掌握哈夫曼樹(shù)的概念、算法實(shí)現(xiàn)，理解哈夫曼樹(shù)在信息論編碼中的應(yīng)用。 理解樹(shù)與二叉樹(shù)的轉(zhuǎn)換方法；理解樹(shù)的遍歷方法。

6、7圖 了解圖的基本概念和術(shù)語(yǔ)。 掌握?qǐng)D的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)。 理解并實(shí)現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法。 理解最小生成樹(shù)的概念，掌握兩種構(gòu)造圖的最小生成樹(shù)算法：普里姆算法和克魯斯卡爾算法。 了解最短路徑問(wèn)題的基本概念，了解單源最短路徑算法。 8查找 理解查找的基本概念和查找方法的評(píng)判標(biāo)準(zhǔn)。 掌握線性表的順序查找、折半查找、分塊查找的算法設(shè)計(jì)方法，理解索引查找的基本結(jié)構(gòu)。 掌握二叉排序樹(shù)的建立及其查找算法。 理解哈希表、哈希函數(shù)、解決沖突方法等哈希查找技術(shù)的概念，掌握拉鏈法哈希表的構(gòu)造方法、動(dòng)態(tài)插入、刪除元素、查找算法等。9排序 理解排序的基本概念和排序算法的評(píng)判標(biāo)準(zhǔn)。 掌握順序存儲(chǔ)結(jié)

7、構(gòu)的直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、二路歸并排序的算法思想和算法設(shè)計(jì)方法；比較各種排序方法的特點(diǎn)和性能。 了解鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的直接插入排序和直接選擇排序的算法設(shè)計(jì)方法。四、實(shí)踐環(huán)節(jié)數(shù)據(jù)結(jié)構(gòu)課程是一門理論和實(shí)踐相結(jié)合的課程，不僅僅要注重理解基本知識(shí)，更要注重培養(yǎng)軟件設(shè)計(jì)的基本技能。實(shí)踐性環(huán)節(jié)是鞏固所學(xué)理論知識(shí)、使理論與實(shí)際相結(jié)合、提高程序設(shè)計(jì)能力和計(jì)算機(jī)操作能力的一項(xiàng)必不可少的重要環(huán)節(jié)。因此，課后習(xí)題、上機(jī)實(shí)驗(yàn)和課程設(shè)計(jì)等都是加強(qiáng)程序設(shè)計(jì)訓(xùn)練所必需的。本課程安排的上機(jī)實(shí)驗(yàn)學(xué)時(shí)為16學(xué)時(shí)，課內(nèi)開(kāi)設(shè)的8個(gè)實(shí)驗(yàn)說(shuō)明如下。實(shí)驗(yàn)1 線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（設(shè)計(jì)型

8、） 2學(xué)時(shí)實(shí)驗(yàn)2 順序串類及串的模式匹配算法 2學(xué)時(shí)實(shí)驗(yàn)3 棧和隊(duì)列及其應(yīng)用 2學(xué)時(shí)實(shí)驗(yàn)4 建立及遍歷二叉樹(shù)（設(shè)計(jì)型） 2學(xué)時(shí)實(shí)驗(yàn)5 線索二叉樹(shù)，哈夫曼算法 2學(xué)時(shí)實(shí)驗(yàn)6 順序查找，折半查找，二叉排序樹(shù)（設(shè)計(jì)型） 2學(xué)時(shí)實(shí)驗(yàn)7 排序算法比較及性能評(píng)價(jià) 2學(xué)時(shí)實(shí)驗(yàn)8 圖的建立與遍歷，最小代價(jià)生成樹(shù) 2學(xué)時(shí)每次實(shí)驗(yàn)后均要求學(xué)生寫(xiě)出實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告內(nèi)容包括：題目、題意解釋、題意分析、設(shè)計(jì)方案、流程描述、源程序清單、程序運(yùn)行結(jié)果、程序存在問(wèn)題和改進(jìn)意見(jiàn)等。五、課外習(xí)題及課程討論本課程通過(guò)課堂講授例題、課堂練習(xí)、課后習(xí)題、上機(jī)實(shí)驗(yàn)以及課程設(shè)計(jì)等各個(gè)實(shí)踐環(huán)節(jié)，對(duì)學(xué)生進(jìn)行系統(tǒng)的程序設(shè)計(jì)訓(xùn)練。所有例題、課堂

9、練習(xí)題、課后習(xí)題、上機(jī)實(shí)驗(yàn)題都是精心挑選的，由淺入深，環(huán)環(huán)相扣，步步推進(jìn)，調(diào)動(dòng)學(xué)生的主動(dòng)性和自覺(jué)性并培養(yǎng)學(xué)生寫(xiě)程序的興趣。除了課內(nèi)安排的習(xí)題課、課堂討論、期中測(cè)驗(yàn)、復(fù)習(xí)課以外，每次課后都要求學(xué)生做至少2個(gè)完整的程序，并定期檢查學(xué)生做作業(yè)的情況，作業(yè)的數(shù)量和質(zhì)量占平時(shí)成績(jī)的一部分。六、教學(xué)方法與手段本課程的課堂教學(xué)采用板書(shū)與多媒體相結(jié)合的方式進(jìn)行，以板書(shū)教學(xué)為主，多媒體教學(xué)為輔。其中，課程主要內(nèi)容采用板書(shū)教學(xué)，計(jì)算機(jī)語(yǔ)言環(huán)境的使用和程序運(yùn)行需要采用多媒體的方式進(jìn)行演示。七、各教學(xué)環(huán)節(jié)學(xué)時(shí)分配章節(jié)（或內(nèi)容）講課習(xí)題課討論課實(shí)驗(yàn)其它合計(jì)緒論44線性表8210串426棧和隊(duì)列628數(shù)組和廣義表44樹(shù)和

10、二叉樹(shù)8412圖628查找628排序8210復(fù)習(xí)22合 計(jì)5421672八、考核方式本課程為考試課程，期末考試為閉卷筆試。學(xué)生的課程總評(píng)成績(jī)由平時(shí)成績(jī)（占30%）和期末考試成績(jī)兩部分構(gòu)成，平時(shí)成績(jī)中實(shí)驗(yàn)成績(jī)占20%，出勤、作業(yè)、課堂測(cè)驗(yàn)、學(xué)習(xí)主動(dòng)性等占10%。實(shí)驗(yàn)成績(jī)根據(jù)實(shí)驗(yàn)報(bào)告質(zhì)量評(píng)定，作業(yè)成績(jī)根據(jù)習(xí)題的數(shù)量和質(zhì)量評(píng)定。九、推薦教材和教學(xué)參考書(shū)教 材：數(shù)據(jù)結(jié)構(gòu)（C+版），葉核亞編著，機(jī)械工業(yè)出版社，2004年。參考書(shū)：數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程，嚴(yán)蔚敏等編著，清華大學(xué)出版社，2001年。數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+描述），殷人昆等編著，清華大學(xué)出版社，1999年。十、說(shuō)明另設(shè)一周課程設(shè)計(jì)。大綱

11、制訂人：葉核亞大綱審定人：黃緯制訂日期：2010年5月數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱一、實(shí)驗(yàn)教學(xué)目標(biāo)與基本要求數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科各專業(yè)本科學(xué)生必修的一門專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)課程是一門理論和實(shí)踐相結(jié)合的課程，不僅僅要注重理解基本知識(shí)，更要注重培養(yǎng)軟件設(shè)計(jì)的基本技能。實(shí)踐性環(huán)節(jié)是鞏固所學(xué)理論知識(shí)、使理論與實(shí)際相結(jié)合、提高程序設(shè)計(jì)能力和計(jì)算機(jī)操作能力的一項(xiàng)必不可少的重要環(huán)節(jié)。其中，上機(jī)實(shí)驗(yàn)是加強(qiáng)程序設(shè)計(jì)訓(xùn)練所必需的一個(gè)重要環(huán)節(jié)。實(shí)驗(yàn)基本要求如下：驗(yàn)證教材中已設(shè)計(jì)好的算法，給出多種運(yùn)行結(jié)果并分析比較，進(jìn)一步理解和鞏固數(shù)據(jù)結(jié)構(gòu)基本原理和算法設(shè)計(jì)原則，積累軟件設(shè)計(jì)經(jīng)驗(yàn)。熟練運(yùn)用C/C+語(yǔ)言或其它計(jì)算機(jī)語(yǔ)言，綜

12、合數(shù)據(jù)結(jié)構(gòu)基本原理和算法設(shè)計(jì)原則，獨(dú)立設(shè)計(jì)出具有中等難度的應(yīng)用程序，編譯、運(yùn)行程序，獲得正確的結(jié)果；分析算法性能并給出總結(jié)，進(jìn)一步提高算法性能并降低算法復(fù)雜度。掌握在計(jì)算機(jī)語(yǔ)言環(huán)境中編輯、編譯、運(yùn)行程序的方法，以及單步運(yùn)行、設(shè)置斷點(diǎn)、查看變量運(yùn)行時(shí)值等調(diào)試程序的方法。具備操作計(jì)算機(jī)和運(yùn)行、調(diào)試程序的基本技能。二、本實(shí)驗(yàn)課程的基本理論與實(shí)驗(yàn)技術(shù)知識(shí)數(shù)據(jù)結(jié)構(gòu)的基本理論，根據(jù)數(shù)據(jù)的邏輯結(jié)構(gòu)，選擇合適的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)對(duì)數(shù)據(jù)進(jìn)行各種操作的算法。算法的基本設(shè)計(jì)原則，算法必須達(dá)到正確性、可讀性、健壯性、高時(shí)間效率、高空間效率等基本目標(biāo)。熟悉在計(jì)算機(jī)語(yǔ)言環(huán)境中編輯、編譯、運(yùn)行和調(diào)試程序的方法。三、實(shí)驗(yàn)方法

13、、特點(diǎn)與基本要求掌握計(jì)算機(jī)系統(tǒng)的基本操作，掌握在計(jì)算機(jī)語(yǔ)言環(huán)境中編輯、編譯、運(yùn)行和調(diào)試程序的多種方法，具備運(yùn)行和調(diào)試程序的基本技能，發(fā)現(xiàn)程序有錯(cuò)時(shí)，能夠找到錯(cuò)誤所在并改正錯(cuò)誤。四、實(shí)驗(yàn)主要儀器設(shè)備計(jì)算機(jī)。五、實(shí)驗(yàn)項(xiàng)目的設(shè)置與內(nèi)容提要總實(shí)驗(yàn)學(xué)時(shí)為 16 學(xué)時(shí)。序號(hào)實(shí)驗(yàn)項(xiàng)目?jī)?nèi) 容 提 要實(shí)驗(yàn)學(xué)時(shí)實(shí)驗(yàn)類型每組人數(shù)實(shí)驗(yàn)要求1線性表掌握線性表的概念，實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的基本操作，實(shí)現(xiàn)單鏈表復(fù)制等操作。2設(shè)計(jì)1必做3串順序串類的算法實(shí)現(xiàn)及串的模式匹配算法。2驗(yàn)證1必做4棧和隊(duì)列使用棧和隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)表達(dá)式計(jì)算等算法。2驗(yàn)證1必做5二叉樹(shù)驗(yàn)證建立及遍歷二叉樹(shù)算法，設(shè)計(jì)復(fù)制二叉樹(shù)的算法。2設(shè)計(jì)1必做6線索二叉樹(shù)及哈夫曼算法建立并線索化中序線索二叉樹(shù)；驗(yàn)證哈夫曼算法。2驗(yàn)證1必做8圖驗(yàn)證圖的建立與遍歷算法，最小代價(jià)生成樹(shù)算法2驗(yàn)證1必做7查找順序查找，折半查找，二叉排序樹(shù)2設(shè)計(jì)1必做2排序多個(gè)排序算法比較及性能評(píng)價(jià)。2驗(yàn)證1必做六、實(shí)驗(yàn)報(bào)告要求每次實(shí)驗(yàn)后均要求學(xué)生寫(xiě)出實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告內(nèi)容包括：題目、題意解釋、題意分析、設(shè)計(jì)方案、流程描述、源程序清單