彭長根-數(shù)據(jù)結(jié)構(gòu)與算法實驗教學(xué)大綱

1、 數(shù)據(jù)結(jié)構(gòu)與算法 實驗教學(xué)大綱理學(xué)院貴州大學(xué)二OO七年八月 數(shù)據(jù)結(jié)構(gòu)與算法 實驗教學(xué)大綱課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法 (Data Structure & Algorithms)課程編號：課程性質(zhì)：專業(yè)基礎(chǔ)課課程設(shè)置類別：非獨立設(shè)置課程課程總學(xué)時：72實驗總學(xué)時：18實驗總學(xué)分：1實驗周學(xué)時：1適用專業(yè)及年級：數(shù)學(xué)與應(yīng)用數(shù)學(xué)、信息與計算科學(xué)，第四學(xué)期先修課程：計算機應(yīng)用基礎(chǔ)、高級語言程序設(shè)計大綱主撰人： 彭長根一、實驗教學(xué)目的和基本要求數(shù)據(jù)結(jié)構(gòu)是數(shù)學(xué)與應(yīng)用數(shù)學(xué)、信息與計算科學(xué)信息管理與信息系統(tǒng)專業(yè)的重要專業(yè)基礎(chǔ)課，數(shù)據(jù)結(jié)構(gòu)是研究基本數(shù)據(jù)結(jié)構(gòu)和算法的學(xué)科，因此該課程的實踐環(huán)節(jié)很重要，要求學(xué)生在實驗中，

2、掌握基本算法的程序?qū)崿F(xiàn)，并能用其基本算法實現(xiàn)應(yīng)用問題的解決。課程教學(xué)的關(guān)鍵是要求學(xué)生掌握算法的設(shè)計與實現(xiàn)，通過實驗加深對講授內(nèi)容的理解和培養(yǎng)軟件開發(fā)的初步能力。本課程要求學(xué)生掌握算法的設(shè)計、程序設(shè)計和調(diào)試運行，能正確闡述設(shè)計和實驗結(jié)果、正確繪制系統(tǒng)和程序框圖，注重培養(yǎng)動手能力、知識的綜合應(yīng)用能力，并逐步建立正確的程序編寫風(fēng)格。并對結(jié)果進行分析。具體要求如下：1要求學(xué)生在上機前準備好本次實驗所編寫的程序，上機時輸入和調(diào)試自己所編寫的程序，解決程序運行過程中所出現(xiàn)的問題，以深入掌握調(diào)試程序的技巧。2每次實驗必須按要求的格式撰寫實驗報告，內(nèi)容大體包括：實驗?zāi)康?、實驗?nèi)容、算法原理及流程圖、程序清單、

3、程序運行結(jié)果分析、總結(jié)。3實驗成績作為平時成績的一部分。二、實驗內(nèi)容及學(xué)時分配 實驗一 線性表的表示與實現(xiàn)（驗證性實驗，2學(xué)時）內(nèi)容：線性表的順序表示與實現(xiàn)、線性表的鏈式表示與實現(xiàn)，包括線性表的插入、刪除等算法，并能對1-2實例進行處理。要求：通過實驗，要求學(xué)生掌握線性表的存儲方法，并基于相應(yīng)的存儲表示，如單鏈表、雙鏈表上能實現(xiàn)初始化、插入結(jié)點、刪除結(jié)點等算法。實驗二 棧與隊列的表示與實現(xiàn)（驗證性實驗，4學(xué)時）內(nèi)容：(1). 棧的順序存儲和鏈式存儲結(jié)構(gòu)實現(xiàn)的方法，基于相應(yīng)的表示實現(xiàn)棧的初始化，入棧、出棧等操作，并能對一個簡單實例進行處理。(2). 隊列的順序存儲和單鏈表存儲結(jié)構(gòu)的實現(xiàn)方法，實現(xiàn)

4、隊列的初始化，入隊、出隊等操作，并能對一個簡單實例進行處理。(3). 順序存儲結(jié)構(gòu)實現(xiàn)循環(huán)隊列的方法，并實現(xiàn)隊列的初始化，入隊、出隊、隊滿隊空判斷等操作，并能對一個簡單實例進行處理。要求：能熟練掌握棧和隊列的不同表示，并能基于此實現(xiàn)棧和隊列的典型操作，理解棧和隊列在軟件開發(fā)中的重要性。實驗三 數(shù)組的存儲與壓縮處理（驗證性實驗，2學(xué)時）內(nèi)容：(1). 數(shù)組的表示與實現(xiàn)，并運用于一個實際問題。(2). 用三元組表和十字鏈表存儲結(jié)構(gòu)實現(xiàn)稀疏矩陣的壓縮方法，并能實現(xiàn)壓縮后矩陣的基本運算。要求：通過實驗，使學(xué)生深刻理解數(shù)組的實現(xiàn)，進一步體會高級語言中一、二維數(shù)組功能；掌握矩壓縮的方法。實驗四 二叉樹的存

5、儲與實現(xiàn)（驗證性實驗，2學(xué)時）內(nèi)容：二叉樹的存儲和基本操作（2學(xué)時）、二叉樹的應(yīng)用（Huffman樹和Huffman編碼，2學(xué)時）。要求：通過實驗，要求學(xué)生掌握用二叉鏈表存儲結(jié)構(gòu)實現(xiàn)二叉樹的表示方法，并能實現(xiàn)其基本運算：二叉鏈表建立及其它有關(guān)處理，在此基礎(chǔ)上實現(xiàn)Huffman樹和Huffman編碼。要求掌握樹的編程，加深理解遞歸的原理。實驗五 圖的表示與遍歷（驗證性實驗，2學(xué)時）內(nèi)容：(1). 圖的表示：鄰接矩陣和鄰接表存儲一個圖或網(wǎng)絡(luò)。(2). 圖的遍歷：DFS遍歷和BFS遍歷實現(xiàn)。(3). 圖的應(yīng)用：最小生成樹、拓樸排序、關(guān)鍵路徑和最短路徑應(yīng)用實現(xiàn)。要求：通過實驗，要求學(xué)生掌握圖的存儲與實

6、現(xiàn)，在此基礎(chǔ)上實現(xiàn)圖的DFS遍歷和BFS遍歷及圖的其它處理；通過實驗理解圖的應(yīng)用，包括最小生成樹、拓樸排序、關(guān)鍵路徑和最短路徑應(yīng)用，理解貪心算法。實驗六 查找及排序算法設(shè)計（驗證性實驗，2學(xué)時）內(nèi)容：(1). 順序查找、二分查找、HASH表查找的算法實現(xiàn)。(2). 典型排序算法實現(xiàn)。要求：通過實驗，要求學(xué)生掌握基本的查找方法的實現(xiàn)，重點是順序查找、二分查找、HASH表查找等方法；掌握查找表的特點，并能根據(jù)查找方法定義合理的存儲結(jié)構(gòu)；針對應(yīng)用，要能基本寫出相應(yīng)的查找算法，并對算法作出分析。通過實驗，熟悉目前典型的排序算法及特點，并能比較各種排序算法效率。實驗七 應(yīng)用實例的數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計（設(shè)計

7、性實驗，4學(xué)時）內(nèi)容：利用學(xué)生所學(xué)的程序設(shè)計、算法設(shè)計和相關(guān)數(shù)學(xué)課程實現(xiàn)一個具實例的綜合設(shè)計，解決數(shù)據(jù)結(jié)構(gòu)的選取及算法設(shè)計，并用C/C+實現(xiàn)程序設(shè)計。在項目的實施過程中，要有需求分析、數(shù)據(jù)分析、系統(tǒng)設(shè)計和系統(tǒng)實施過程。要求：本項目涉及到實驗項目需要數(shù)據(jù)結(jié)構(gòu)課程的知識點有：棧、隊列、樹、圖等數(shù)據(jù)結(jié)構(gòu)的設(shè)計，也涉及到查找、排序基本算法。還需要熟練的C/C+編程技術(shù)。本項目重點要解決數(shù)據(jù)結(jié)構(gòu)和算法。本項目要求具有需求分析、功能分析、算法設(shè)計和程序?qū)崿F(xiàn)，最好能以圖形界面進行設(shè)計。三、主要儀器設(shè)備 計算機，VC+平臺。四、實驗教學(xué)方式 機房實驗。五、實驗考核方式1、本實驗課程考核內(nèi)容主要考查實驗報告完成

8、的質(zhì)量；2、實驗課成績占課程總成績的20%。六、推薦實驗教材和教學(xué)參考書 教材：1. 吳艷等數(shù)據(jù)結(jié)構(gòu)與算法實驗教程北京：科學(xué)出版社，2006年 2. 嚴蔚敏，吳偉民編數(shù)據(jù)結(jié)構(gòu)（C語言版）北京：清華大學(xué)出版，2003年主要參考書：嚴蔚敏，吳偉民編著數(shù)據(jù)結(jié)構(gòu)題集清華大學(xué)出版社，1999年 七、實驗課程與學(xué)時分配表序號實驗項目名稱實驗內(nèi)容提要學(xué)時分配實驗屬性實驗類型每組人數(shù)實驗要求指導(dǎo)教師已開/未開1線性表的表示與實現(xiàn)線性表的順序鏈式表示與實現(xiàn)，以及線性表的插入、刪除等算法2基礎(chǔ)驗證1必做彭長根已開2棧與隊列的表示與實現(xiàn)棧和隊列的二種表示與實現(xiàn)，以及初始化，入棧、出棧等操作4基礎(chǔ)驗證1必做彭長根已開3數(shù)組的存儲與壓縮處理數(shù)組的表示與實現(xiàn)；數(shù)組的壓縮實現(xiàn)2基礎(chǔ)驗證1必做彭長根已開4二叉樹的存儲與實現(xiàn)二叉樹的存儲、基本操作、應(yīng)用2基礎(chǔ)驗證1必做彭長根已開5圖