高級程序設(shè)計語言C課程教學大綱

1、數(shù)據(jù)結(jié)構(gòu)A課程教學大綱一、課程基本信息課程中文名稱:數(shù)據(jù)結(jié)構(gòu)課程英文名稱：Data Structure課程編號：10072105課程性質(zhì)：學科基礎(chǔ)課課程學時和學分：總學時：64 總學分：3.5 理論學時：48 上機學時：16適用專業(yè)：計算機科學與技術(shù)、網(wǎng)絡(luò)工程、軟件工程先修課程：計算機程序設(shè)計語言、離散數(shù)學等開課系部、教研室：電子與信息工程系、計算機應用教研室二、課程的地位與作用數(shù)據(jù)結(jié)構(gòu)是計算機科學中一門綜合性的專業(yè)核心基礎(chǔ)課程。它是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)原理、算法設(shè)計與分析及計算機應用方面的主要基礎(chǔ)。三、課程總的教學目的和要求本課程教學目的是通過本課程的學習，要求學生掌握數(shù)據(jù)結(jié)構(gòu)的特

2、點、存儲方法和基本運算，培養(yǎng)學生運用C（C+）語言正確編程及調(diào)試的能力，運用數(shù)據(jù)結(jié)構(gòu)解決簡單的實際問題的能力，為后續(xù)計算機專業(yè)課程的學習打下堅實的基礎(chǔ)。四、各章主要教學內(nèi)容 第1章 數(shù)據(jù)結(jié)構(gòu)概述（2學時）本章應了解數(shù)據(jù)結(jié)構(gòu)及算法的概念；掌握計算語句頻度和估算算法時間復雜度的方法。重點：數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)的運算三方面的概念及相互關(guān)系難點：算法復雜度的分析方法第2章 線性表（8學時）本章應了解線性表的邏輯結(jié)構(gòu)特性，以及線性表的兩種存儲實現(xiàn)方式； 熟練掌握順序表的定義與實現(xiàn)，包括查找、插入、刪除算法的實現(xiàn)； 熟練掌握在各種鏈表結(jié)構(gòu)中實現(xiàn)線性表操作的基本方法，能在實際應用中選用適當?shù)逆?/p>

3、表結(jié)構(gòu)；本章實驗應掌握線性表的基本操作在順序和鏈式存儲結(jié)構(gòu)上的實現(xiàn)。重點：順序表和單鏈表上實現(xiàn)的各種基本算法及相關(guān)的時間性能分析難點：使用本章所學到的基本知識設(shè)計有效算法解決與線性表相關(guān)的應用問題第3章 棧和隊列（8學時）本章應掌握棧和隊列的定義、特性，并能正確應用它們解決實際問題；熟練掌握棧的順序表示、鏈表表示以及相應操作的實現(xiàn)；熟練掌握隊列的順序表示、鏈表表示以及相應操作的實現(xiàn)；本章實驗應掌握棧和隊列的特點及棧和隊列的基本運算。重點：棧和隊列在兩種存儲結(jié)構(gòu)上實現(xiàn)的基本運算難點：循環(huán)隊列中對邊界條件的處理第4章 串(2學時)本章應理解串的基本操作的定義，并能利用這些基本操作來實現(xiàn)串的其它各種

4、操作的方法；熟練掌握在串的順序存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法；了解串操作的應用方法和特點。重點：順序存儲結(jié)構(gòu)上串的各種操作難點：串上實現(xiàn)的模式匹配算法第5章 數(shù)組與廣義表(4學時)本章應了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法；掌握對特殊矩陣進行壓縮存儲時的下標變換公式；了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍，理解以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法；掌握廣義表的結(jié)構(gòu)特點及其存儲表示方法，會對非空廣義表進行分解。重點：多維數(shù)組的存儲方式、矩陣的壓縮存儲方式、廣義表的定義及其求表頭和表尾的運算難點：稀疏矩陣的壓縮存儲表示下實現(xiàn)的算法第6章

5、樹與森林（10學時）本章應了解樹和森林的概念。包括樹的定義、樹的術(shù)語和性質(zhì)；熟練掌握二叉樹的結(jié)構(gòu)特性，熟悉二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍；熟練掌握二叉樹的遍歷方法及遍歷算法；熟悉樹的各種存儲結(jié)構(gòu)及其特點，掌握樹、森林與二叉樹的轉(zhuǎn)換方法；掌握建立哈夫曼樹和哈夫曼編碼的方法及帶權(quán)路徑長度的計算；本章實驗應掌握二叉樹的結(jié)構(gòu)特性，以及用指針類型描述、訪問和處理二叉樹的運算。重點：二叉樹的遍歷算法及其相關(guān)應用難點：使用本章所學到的有關(guān)知識設(shè)計出有效算法，解決與樹或二叉樹相關(guān)的應用問題第7章 圖（10學時）本章應理解圖的基本概念，熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法；熟練掌握圖的兩種搜索路徑的遍歷, 并

6、理解算法；掌握構(gòu)造最小生成樹的方法；理解用Dijkstra方法求解單源最短路徑問題；掌握求活動網(wǎng)絡(luò)的拓撲排序的方法，并理解算法；了解求解關(guān)鍵路徑的方法；本章實驗應熟悉圖的存儲結(jié)構(gòu)及鄰接矩陣和鄰接表等有關(guān)概念，掌握圖的兩種搜索路徑的遍歷方法。重點：圖的兩種存儲結(jié)構(gòu)上實現(xiàn)的遍歷算法難點：圖的應用的實現(xiàn)第8章 查找（8學時）本章應熟練掌握順序表和有序表的查找算法及其性能分析方法；熟練掌握二叉排序樹的構(gòu)造和查找算法及其性能分析方法；理解AVL樹的維護平衡方法；了解B_樹、B+的特點、查找及構(gòu)造方法；熟練掌握哈希函數(shù)的構(gòu)造及解決沖突的方法；本章實驗應熟練掌握二叉排序樹的構(gòu)造和查找方法。重點：順序查找、二

7、分查找，二叉查找樹上查找以及散列表上查找的基本思想和算法實現(xiàn)難點：二叉查找樹的刪除算法及B樹上的插入和刪除算法第9章 排序（12學時）本章應掌握排序的基本概念和各種排序方法的特點，并能加以靈活應用；掌握插入排序、交換排序、選擇排序、歸并排序的方法及其性能分析方法；了解基數(shù)排序方法及其性能分析方法；本章實驗應掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法。重點：快速排序、堆排序、歸并排序和希爾排序的基本思想及排序過程難點：這四個排序算法的實現(xiàn)實驗1 線性表的應用（4學時）實驗目的：掌握線性表的基本操作在順序和鏈式存儲結(jié)構(gòu)上的實現(xiàn)。實驗要求：（1）建立含有若干個元素的順序表鏈表；（2）對已

8、建立的順序表實現(xiàn)插入、刪除、查找、逆置等操作。實驗2 棧和隊列的應用（2學時）實驗目的：掌握棧和隊列的特點，及棧和隊列的基本運算。實驗要求：（1）棧的初始化、判棧是否為空、進棧、出棧等運算的實現(xiàn)。（2）利用棧實現(xiàn)判定表達式中的括號是否匹配。實驗3 數(shù)組的應用（2學時）（選作）實驗目的：熟悉數(shù)組的有關(guān)概念，掌握稀疏矩陣的三元組存儲結(jié)構(gòu)的轉(zhuǎn)置方法。實驗要求：采用兩種方法實現(xiàn)稀疏矩陣的轉(zhuǎn)置。實驗4 樹和森林的應用（2學時）實驗目的：掌握二叉樹的結(jié)構(gòu)特性，以及用指針類型描述、訪問和處理二叉樹的運算。實驗要求：（1）創(chuàng)建以二叉鏈表作存儲結(jié)構(gòu)的二叉樹；（2）按中序遍歷二叉樹；（3）計算二叉樹的單枝結(jié)點數(shù)；

9、（4）按層次遍歷二叉樹。實驗5 圖的應用（4學時）實驗目的：熟悉圖的存儲結(jié)構(gòu)及鄰接矩陣和鄰接表等有關(guān)概念，掌握圖的兩種搜索路徑的遍歷方法。實驗要求：（1）創(chuàng)建以鄰接表作存儲結(jié)構(gòu)的無向圖；（2）按深度優(yōu)先遍歷圖；（3）按廣度優(yōu)先遍歷圖。實驗6 查找方法的實現(xiàn)（2學時）實驗目的：熟練掌握二叉排序樹的構(gòu)造和查找方法。實驗要求：（1）創(chuàng)建以二叉鏈表作存儲結(jié)構(gòu)的二叉排序樹；（2）實現(xiàn)二叉排序樹的查找、插入、中序遍歷操作。實驗7 排序方法的實現(xiàn)（2學時）實驗目的：掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法。實驗要求：用各種排序方法實現(xiàn)學生考試成績表的排序并輸出。學生的考試成績表必須通過鍵盤輸入數(shù)據(jù)而建立，同時要對輸出格式進行控制。實驗課考核方式采用課堂表現(xiàn)和實驗報告相結(jié)合方式。實驗課成績占課程總成績的10%。五、課程考核和成績評定方式閉卷考試和平時考核方式結(jié)合，期末考試占70%；平時成績占30%。六、教材與主要參考書1教材1王紅梅，胡明，王濤.數(shù)據(jù)結(jié)構(gòu)（c+版）.北京：清華大學出版社，2005.2實驗指導書或教材1王紅梅，胡明，王濤.數(shù)據(jù)結(jié)構(gòu)（c+版）學習輔導與實驗指導.北京：清華大學出版社，2005.2嚴蔚敏，吳偉民著.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）.北京：清華大學出版社，1997.3、主要參考教材和參考