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

1、 數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱課程性質(zhì)專業(yè)必修課課程編號(hào)xx881018課程名稱數(shù)據(jù)結(jié)構(gòu)適用專業(yè)通信工程先修課程C語(yǔ)言總學(xué)時(shí) 32 其中理論 26 學(xué)時(shí)、實(shí)驗(yàn)6學(xué)時(shí)學(xué)分?jǐn)?shù)2一、課程簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件之間的一門計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心課程，是操作系統(tǒng)、數(shù)據(jù)庫(kù)原理、編譯原理、軟件工程、人工智能等課程的基礎(chǔ)。通過(guò)本課程的學(xué)習(xí)，使學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算的原理和技術(shù)，為編譯原理、操作系統(tǒng)、算法分析和數(shù)據(jù)庫(kù)等課程的學(xué)習(xí)打下基礎(chǔ)，培養(yǎng)學(xué)生良好的程序設(shè)計(jì)風(fēng)格。二、課程教學(xué)目標(biāo)知識(shí)目標(biāo)：1、了解相關(guān)的基本概念，理解算法五大要素；2、理解線性表的邏輯結(jié)構(gòu)，掌握線性表的存儲(chǔ)結(jié)構(gòu)及操作的實(shí)現(xiàn)。3、

2、了解一元多項(xiàng)式的表示；理解棧的定義，表示及實(shí)現(xiàn)，掌握表達(dá)式求值，理解并掌握棧與遞歸過(guò)程，理解并掌握隊(duì)列的定義，表示及實(shí)現(xiàn)。4、了解串的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，理解并掌握串操作的實(shí)現(xiàn)。5、了解樹(shù)的基本概念，理解并掌握二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)，理解并掌握遍歷二叉樹(shù)和線索二叉樹(shù)，深刻理解樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷，掌握哈夫曼樹(shù)及其應(yīng)用。6、理解圖的基本概念及存儲(chǔ)結(jié)構(gòu)，深刻理解圖的遍歷及應(yīng)用，理解并應(yīng)用拓?fù)渑判蚝完P(guān)鍵路徑；了解靜態(tài)查找表(順序表、有序表、索引順序表)建立和查找，理解動(dòng)態(tài)查找表(二叉排序樹(shù)、平衡二叉樹(shù)、B-樹(shù)和B+樹(shù))的建立和查找；掌握哈希表的建立。7、理解動(dòng)態(tài)查找表；了解內(nèi)部排序概述，理解插入排序，

3、交換排序(起泡排序、快速排序)，選擇排序(簡(jiǎn)單選擇、樹(shù)形選擇、堆)，歸并排序，基數(shù)排序。能力目標(biāo)：本課程以培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和復(fù)雜程序設(shè)計(jì)的能力為總目標(biāo)。通過(guò)本課程的學(xué)習(xí)，學(xué)生可以學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的運(yùn)算，并初步掌握算法的時(shí)間分析和空間分析的技術(shù)；另一方面，本課程的學(xué)習(xí)過(guò)程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過(guò)程，要求學(xué)生編寫的程序結(jié)構(gòu)清楚和正確易讀，符合軟件工程的規(guī)范。三、課程教學(xué)基本要求有興趣且有志于軟件設(shè)計(jì)的信息類工程專業(yè)學(xué)生。四、課程教學(xué)、實(shí)驗(yàn)?zāi)K（或教學(xué)、實(shí)驗(yàn)內(nèi)容）與學(xué)時(shí)分配序號(hào)教學(xué)模塊知識(shí)點(diǎn)學(xué)時(shí)1緒論了解：1、數(shù)據(jù)

4、結(jié)構(gòu)的概念 2、數(shù)據(jù)結(jié)構(gòu)的地位和作用 3、算法分析的基本方法22線性表掌握：1、線性表定義和基礎(chǔ)運(yùn)算2、線性表的存儲(chǔ)結(jié)構(gòu) 3、鏈?zhǔn)奖淼膽?yīng)用:多項(xiàng)式的表示與相加。43棧和隊(duì)列理解：1、棧的概念和運(yùn)算掌握：2、表達(dá)式求值3、隊(duì)列的定義，表示及實(shí)現(xiàn)24串了解：1、基本概念掌握： 2、串的表示和實(shí)現(xiàn) 3、串的應(yīng)用。25數(shù)組和廣義表理解：1、數(shù)組的定義和運(yùn)算 2、數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及存儲(chǔ)地址 3、稀疏矩陣的表示及操作的實(shí)現(xiàn)26樹(shù)理解：1、基本概念掌握：2、二叉樹(shù)定義，性質(zhì)，基本運(yùn)算和存儲(chǔ)結(jié)構(gòu)3、二叉樹(shù)的遍歷和線索二叉樹(shù)4、樹(shù)，二叉樹(shù)與森林的轉(zhuǎn)換，樹(shù)與森林的遍歷5、二叉樹(shù)的應(yīng)用47圖理解：1、圖的概念 2

5、、圖的存儲(chǔ)結(jié)構(gòu) 3、圖的遍歷 4、連通性問(wèn)題 5、有向無(wú)環(huán)圖及其應(yīng)用 6、最短路徑。48查找了解：1、靜態(tài)查找表（順序表，有序表，靜態(tài)樹(shù)表，索引順序表）2、動(dòng)態(tài)查找表（二叉排序樹(shù)與平衡二叉樹(shù)）理解：3、哈希表的建立，查找及分析。29內(nèi)部排序理解：1、基本概念2、插入排序（直接插入，其他插入，希爾排序）3、快速排序4、選擇排序5、歸并排序6、基數(shù)排序4實(shí)驗(yàn)?zāi)K序號(hào)實(shí)驗(yàn)項(xiàng)目名稱內(nèi)容摘要實(shí)驗(yàn)學(xué)時(shí)實(shí)驗(yàn)類型開(kāi)出要求1順序表的基本操作掌握使用VC+進(jìn)行控制 臺(tái)應(yīng)用程序編寫的基本方法；2、掌握順序表的初始化、銷毀、數(shù)據(jù)元素的插入和刪除以及順序表的輸出等基本操作。2驗(yàn)證性必做2棧的基本操作1、會(huì)定義順序棧和鏈

6、棧的結(jié)點(diǎn)類型。2、掌握順序棧的插入和刪除結(jié)點(diǎn)在操作上的特點(diǎn)3、熟悉對(duì)順序棧的一些基本操作和具體的函數(shù)定義2設(shè)計(jì) 必做3矩陣的轉(zhuǎn)置1、了解多維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及其地址計(jì)算方式2、了解特殊矩陣和稀疏矩陣的概念3、掌握疏矩陣的壓縮存儲(chǔ)方式三元組表4、掌握稀疏矩陣的兩種轉(zhuǎn)置運(yùn)算算法2設(shè)計(jì)性選做（二選一）4二叉樹(shù)的遍歷（遞歸）1、熟悉二叉樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)和對(duì)二叉樹(shù)的基本操作2、掌握對(duì)二叉樹(shù)每一種操作的具體實(shí)現(xiàn)3、學(xué)會(huì)利用遞歸方法編寫對(duì)二叉樹(shù)這種遞歸數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法2驗(yàn)證性選做（二選一）五、教學(xué)方法與策略課程以課堂講授為主，輔以案例討論、視頻教學(xué)、分組討論、現(xiàn)場(chǎng)指導(dǎo)等方法和手段。六、學(xué)生學(xué)習(xí)成效考核方式考核環(huán)節(jié)構(gòu)成（均為100分制）評(píng)分依據(jù)占總成績(jī)的比重期末考試期末考試試卷60實(shí)驗(yàn)每次完成實(shí)驗(yàn)情況20作業(yè)課堂作業(yè)10考勤現(xiàn)場(chǎng)考勤10七、選用教材 1數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）