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

1、數(shù)據(jù)結(jié)構(gòu)課程教學大綱課程名稱：數(shù)據(jù)結(jié)構(gòu)英文名稱：Data Structures課程編號：學 時 數(shù)：48其中實驗學時數(shù)：8 課外學時數(shù)：0學 分 數(shù)：3.0適用專業(yè)：通信工程一、課程的性質(zhì)、目的和任務數(shù)據(jù)結(jié)構(gòu)是計算機科學與技術(shù)專業(yè)、軟件工程專業(yè)、網(wǎng)絡工程專業(yè)及各相關專業(yè)的一門專業(yè)基礎課，也是計算機專業(yè)的核心課程。主要討論現(xiàn)實世界中的數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)在計算機中的存儲結(jié)構(gòu)以及實現(xiàn)各種操作的算法設計問題。本課程的教學目的是使學生熟練掌握數(shù)據(jù)組織、數(shù)據(jù)存儲和數(shù)據(jù)處理的基本理論和基本方法，努力培養(yǎng)學生具備一定的分析問題和解決問題的能力，提高學生的獨立動手能力及實踐能力。為以后從事軟件開發(fā)和應用以及進

2、一步學習后續(xù)專業(yè)課程打下堅實的基礎。二、課程教學內(nèi)容的基本要求、重點和難點掌握數(shù)據(jù)結(jié)構(gòu)的基礎知識、基本應用。 認識數(shù)據(jù)結(jié)構(gòu)的本質(zhì)、掌握應用數(shù)據(jù)結(jié)構(gòu)思想，解決實際問題的基本思想和基本方法。（一）緒論了解和掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，這些概念包括：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、抽象數(shù)據(jù)類型、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)上的操作集合、 算法及算法特點等。了解和掌握算法效率分析的意義和方法。重點：抽象數(shù)據(jù)類型表示。難點：抽象數(shù)據(jù)類型的概念和表示形式。（二）線性表了解線性表的邏輯結(jié)構(gòu)和基本操作；理解線性表的順序存儲結(jié)構(gòu)和實現(xiàn)方法；理解線性表的鏈式存儲結(jié)構(gòu)和實現(xiàn)方法；了解單循環(huán)鏈表和雙向鏈表的概念和基本設

3、計方法。重點：順序存儲結(jié)構(gòu)和順序表的設計方法。難點：單鏈表的存儲結(jié)構(gòu)設計及算法的實現(xiàn)。（三）棧和隊列理解棧的概念、順序棧和鏈式棧的設計方法；理解隊列的概念、順序循環(huán)隊列和鏈式隊列的設計方法；了解堆棧和隊列的應用方法。重點：棧和隊列的基本概念及其各種操作算法的設計和實現(xiàn)。難點：棧的應用算法和循環(huán)隊列的實現(xiàn)。（四）數(shù)組熟練掌握數(shù)組的概念和數(shù)組的靜態(tài)、動態(tài)存儲結(jié)構(gòu)；了解特殊矩陣的壓縮存儲方法；了解稀疏矩陣的基本壓縮存儲方法。重點：特殊矩陣和稀疏矩陣的壓縮存儲方法。難點：特殊矩陣和稀疏矩陣的存儲結(jié)構(gòu)設計及其算法設計。（五）樹與二叉樹一般了解樹的定義、樹的表示方法和樹的幾種典型存儲結(jié)構(gòu)；正確理解二叉樹的

4、定義、二叉樹的性質(zhì)、二叉樹的存儲結(jié)構(gòu)和二叉樹操作的實現(xiàn)方法；熟練掌握二叉樹的遍歷算法和二叉樹問題的遍歷算法設計分析和實現(xiàn)；理解哈夫曼樹的概念和哈夫曼樹在編碼方面的應用方法；了解樹與二叉樹的轉(zhuǎn)換方法和遍歷方法。重點：二叉樹的性質(zhì)、二叉樹的存儲結(jié)構(gòu)；二叉樹的遍歷算法和二叉樹遍歷算法的應用；哈夫曼樹在編碼方面的應用方法。難點：有關樹和二叉樹的各種遞歸算法。（六）圖一般了解圖的基本概念和術(shù)語；熟練掌握圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)以及圖操作的實現(xiàn)方法；熟練理解圖的深度和廣度遍歷方法和算法設計方法；正確理解最小生成樹的概念、以及普里姆算法和單源最短路徑的狄克斯特拉算法。 重點：圖的鄰接矩陣和圖的鄰接表存儲

5、結(jié)構(gòu)；圖的深度和廣度遍歷方法；普里姆算法。難點：圖的兩種遍歷算法以及各應用問題的求解算法。（七）查找了解查找的基本概念和查找方法的評判標準；正確理解順序查找，熟練掌握有序查找的算法設計方法，理解索引查找的基本結(jié)構(gòu)；了解二叉排序樹的基本結(jié)構(gòu)和插入、刪除方法；熟練掌握哈希函數(shù)、哈希沖突函數(shù)和哈希表的構(gòu)造方法。重點：二叉排序樹和二叉排序樹的插入和刪除方法；哈希函數(shù)、哈希沖突函數(shù)和哈希表的構(gòu)造方法。（八）排序了解排序的基本概念和排序算法的評判標準；熟練掌握直接插入排序、希爾排序、直接選擇排序、堆排序、快速排序的算法思想和算法設計方法；正確理解各種排序方法的性能特點。重點：堆排序、快速排序、的算法思想。

6、難點：堆排序、快速排序算法設計方法。三、教學方式及學時分配序號主要內(nèi)容主要教學方式學時分配輔導答疑比例1緒論講授21：12線性表講授+實驗6+21：13棧和隊列講授+實驗6+21：14數(shù)組和廣義表講授21：15樹與二叉樹講授61：16圖講授+實驗6+21：17查找講授61：18排序講授+實驗6+21：1四、課程各教學環(huán)節(jié)的要求（一）實驗環(huán)節(jié)實驗一：線性表操作 要求：掌握順序存儲結(jié)構(gòu)的特點和順序存儲結(jié)構(gòu)的常見算法。實驗二：棧和隊列操作 要求：掌握棧和隊列操作，設計應用程序進行測試。實驗三：圖算法 要求：掌握圖的存儲思想及其存儲實現(xiàn)、圖的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)、圖的常見應用算法的思想及其程序?qū)崿F(xiàn)。實驗四：排序選擇 要求：掌握常見的排序算法的思想及其適用條件、常見的排序算法的程序?qū)崿F(xiàn)。（二）作業(yè)根據(jù)授課進度，布置作業(yè)，每章講授結(jié)束后，收一次作業(yè)，批改后做集體答疑，講解作業(yè)中出現(xiàn)的問題。五、本課程與其它課程的聯(lián)系本課程是自動化、通信專業(yè)選修課，其先修課程是C語言程序設計。六、教學參考書目1、數(shù)據(jù)結(jié)構(gòu)-C語言描述 耿國華 高等教育出版社200