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

1、數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱課程名稱：數(shù)據(jù)結(jié)構(gòu)英文名稱：Data Structures課程編號(hào)：學(xué) 時(shí) 數(shù)：80其中實(shí)驗(yàn)（實(shí)訓(xùn)）學(xué)時(shí)數(shù)：24 課外學(xué)時(shí)數(shù)：0學(xué) 分 數(shù)：5.0適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)一、課程的性質(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ù)據(jù)結(jié)構(gòu)的設(shè)計(jì)方法，研究各種典型排序和查找算法的設(shè)計(jì)方法和性能指標(biāo)，并介紹這些數(shù)據(jù)結(jié)構(gòu)和算法在實(shí)際工程中的應(yīng)用。通過學(xué)習(xí)本課程，使學(xué)生深入理解軟件設(shè)計(jì)的基本要

2、素和基本結(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é)內(nèi)容的基本要求、重點(diǎn)和難點(diǎn)本課程是理論與實(shí)踐并重的課程，要求學(xué)生既要掌握數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)理論知識(shí)，又要掌握操作計(jì)算機(jī)和運(yùn)行、調(diào)試程序的基本技能；能夠熟練運(yùn)用C/C+語言或其它計(jì)算機(jī)語言編制具有中等難度的應(yīng)用程序，在實(shí)踐中培養(yǎng)獨(dú)立分析問題和解決問題的作風(fēng)和能力。本課程的基本要求如下。理解線性表、棧、隊(duì)列、串、數(shù)組、樹、二叉樹、圖等基本的數(shù)據(jù)邏輯結(jié)構(gòu)，掌握描述這些數(shù)據(jù)結(jié)構(gòu)、選擇合適的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)各種操作的方法。熟練運(yùn)用C/C+語言或其它計(jì)算機(jī)語言表達(dá)鏈?zhǔn)酱?/p>

3、儲(chǔ)結(jié)構(gòu)；熟練運(yùn)用遞歸函數(shù)表達(dá)遞歸定義、遞歸算法和遞歸結(jié)構(gòu)。理解插入、交換、選擇、歸并等多種典型排序算法的思想，掌握在線性表、樹等各種不同數(shù)據(jù)結(jié)構(gòu)中的查找算法。掌握在計(jì)算機(jī)語言環(huán)境中編輯、編譯、運(yùn)行程序的方法，以及單步運(yùn)行、設(shè)置斷點(diǎn)、查看變量運(yùn)行時(shí)值等調(diào)試程序的方法。具體設(shè)置如下：（一）緒論了解和掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，這些概念包括:數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、抽象數(shù)據(jù)類型、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)上的操作集合、 算法及算法特點(diǎn)等。了解和掌握算法效率分析的意義和方法。重點(diǎn)：抽象數(shù)據(jù)類型表示。難點(diǎn)：抽象數(shù)據(jù)類型的概念和表示形式。（二）線性表了解線性表的邏輯結(jié)構(gòu)和基本操作；理解線性表的順序

4、存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)方法；理解線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和實(shí)現(xiàn)方法；了解單循環(huán)鏈表和雙向鏈表的概念和基本設(shè)計(jì)方法。重點(diǎn)：順序存儲(chǔ)結(jié)構(gòu)和順序表的設(shè)計(jì)方法。難點(diǎn)：單鏈表的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)及算法的實(shí)現(xiàn)。（三）棧和隊(duì)列理解棧的概念、順序棧和鏈?zhǔn)綏５脑O(shè)計(jì)方法；理解隊(duì)列的概念、順序循環(huán)隊(duì)列和鏈?zhǔn)疥?duì)列的設(shè)計(jì)方法；了解優(yōu)先級(jí)隊(duì)列以及優(yōu)先級(jí)隊(duì)列和一般隊(duì)列的差別；了解堆棧和隊(duì)列的應(yīng)用方法。重點(diǎn)：棧和隊(duì)列的基本概念及其各種操作算法的設(shè)計(jì)和實(shí)現(xiàn)。難點(diǎn)：棧的應(yīng)用算法和循環(huán)隊(duì)列的實(shí)現(xiàn)。（四）字符串理解串的概念和串的基本操作；理解串的靜態(tài)存儲(chǔ)結(jié)構(gòu)、動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；了解串基本操作的實(shí)現(xiàn)方法；了解串的BF模式匹配方法和KMP模式匹

5、配方法。重點(diǎn)：字符串操作算法的設(shè)計(jì)和實(shí)現(xiàn)。難點(diǎn)：串的模式匹配算法。（五）廣義線性表熟練掌握數(shù)組的概念和數(shù)組的靜態(tài)、動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)；了解特殊矩陣的壓縮存儲(chǔ)方法；了解稀疏矩陣的基本壓縮存儲(chǔ)方法，包括稀疏矩陣的三元組概念，以及稀疏矩陣三元組的順序表、單鏈表和十字鏈表存儲(chǔ)結(jié)構(gòu)。重點(diǎn)：特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法。難點(diǎn)：特殊矩陣和稀疏矩陣的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)及其算法設(shè)計(jì)。（六）遞歸算法正確理解遞歸的概念、遞推公式的歸納方法和遞歸算法的執(zhí)行過程；熟練掌握遞歸算法的問題分析和算法設(shè)計(jì)方法；了解遞歸算法時(shí)間效率低的原因。重點(diǎn)：遞推公式的歸納；遞歸算法的執(zhí)行過程；遞歸算法的設(shè)計(jì)方法。難點(diǎn)：遞歸技術(shù)的原理、實(shí)現(xiàn)和運(yùn)用

6、。（七）樹與二叉樹了解樹的定義、表示方法及其典型存儲(chǔ)結(jié)構(gòu)；理解二叉樹的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)方法；掌握二叉樹的遍歷算法及其應(yīng)用實(shí)現(xiàn)；理解哈夫曼樹的概念及其應(yīng)用；了解樹與二叉樹的關(guān)系。重點(diǎn)：二叉樹的性質(zhì)、二叉樹的存儲(chǔ)結(jié)構(gòu)；二叉樹的遍歷算法和二叉樹遍歷算法的應(yīng)用；哈夫曼樹在編碼方面的應(yīng)用方法。難點(diǎn)：有關(guān)樹和二叉樹的各種遞歸算法。（八）圖了解圖的基本概念和術(shù)語；掌握?qǐng)D的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)以及圖操作的實(shí)現(xiàn)方法；理解圖的深度和廣度優(yōu)先遍歷方法和算法設(shè)計(jì)方法；理解最小生成樹的概念以及普里姆算法和單源最短路徑的狄克斯特拉算法。重點(diǎn)：圖的鄰接矩陣和圖的鄰接表存儲(chǔ)結(jié)構(gòu)；圖的深度和廣度遍歷方法；普

7、里姆算法和狄克斯特拉算法。難點(diǎn)：圖的兩種遍歷算法以及各應(yīng)用問題的求解算法。（九）排序了解排序的基本概念和排序算法的評(píng)判標(biāo)準(zhǔn)；掌握直接插入排序、希爾排序、直接選擇排序、堆排序、快速排序、二路歸并排序、基數(shù)排序的算法思想和算法設(shè)計(jì)方法；理解各種排序方法的性能特點(diǎn)。重點(diǎn)：希爾排序、堆排序、快速排序、二路歸并排序和基數(shù)排序的算法思想。難點(diǎn)：堆排序、快速排序、二路歸并排序和基數(shù)排序的算法設(shè)計(jì)方法。（十）查找了解查找的基本概念和查找方法的評(píng)判標(biāo)準(zhǔn)；理解順序查找，掌握有序查找的算法設(shè)計(jì)方法，理解索引查找的基本結(jié)構(gòu)；了解二叉排序樹和B-樹的基本結(jié)構(gòu)和插入、刪除方法；掌握哈希函數(shù)、哈希沖突函數(shù)和哈希表的構(gòu)造方法

8、。重點(diǎn)：二叉排序樹和二叉排序樹的插入和刪除方法；哈希函數(shù)、哈希沖突函數(shù)和哈希表的構(gòu)造方法。難點(diǎn)：二分查找，二叉排序樹的構(gòu)造，哈希表的沖突處理。三、教學(xué)方式及學(xué)時(shí)分配序號(hào)主要內(nèi)容主要教學(xué)方式學(xué)時(shí)分配輔導(dǎo)答疑比例一緒論講授42：1二線性表講授+實(shí)驗(yàn)12+42：1三棧和隊(duì)列講授+實(shí)驗(yàn)6+22：1四字符串講授22：1五廣義線性表講授+實(shí)驗(yàn)4+22：1六遞歸算法講授22：1七樹與二叉樹講授+實(shí)驗(yàn)8+42：1八圖講授+實(shí)驗(yàn)10+42：1七排序講授+實(shí)驗(yàn)6+22：1十查找講授+實(shí)驗(yàn)6+22：1四、課程其他教學(xué)環(huán)節(jié)要求數(shù)據(jù)結(jié)構(gòu)課程是一門理論和實(shí)踐相結(jié)合的課程，不僅僅要注重理解基本知識(shí)，更要注重培養(yǎng)軟件設(shè)計(jì)的基

9、本技能。實(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í)為24學(xué)時(shí)，課內(nèi)開設(shè)的12個(gè)實(shí)驗(yàn)說明如下。實(shí)驗(yàn)一：線性表操作（一） 要求：掌握順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)和常見算法。實(shí)驗(yàn)二：線性表操作（二） 要求：掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)和常見算法。實(shí)驗(yàn)三：棧和隊(duì)列操作 要求：掌握棧和隊(duì)列操作，設(shè)計(jì)新的成員函數(shù)，并進(jìn)行測(cè)試。實(shí)驗(yàn)四：多維數(shù)組和廣義表操作 要求：掌握這兩種操作、及新的成員函數(shù)，并測(cè)試。實(shí)驗(yàn)五：樹和二叉樹（一） 要求：掌握二叉樹的存儲(chǔ)實(shí)現(xiàn)、二叉樹的遍歷思

10、想。實(shí)驗(yàn)六：樹和二叉樹（二） 要求：掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)七：圖的有關(guān)操作（一） 要求：掌握?qǐng)D的存儲(chǔ)思想及其存儲(chǔ)實(shí)現(xiàn)、圖的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。實(shí)驗(yàn)八：圖的有關(guān)操作（二） 要求：掌握?qǐng)D的常見應(yīng)用算法的思想及其程序?qū)崿F(xiàn)。實(shí)驗(yàn)九：查找 要求：掌握順序查找，折半查找，二快速排序，堆排序等二叉排序樹算法。實(shí)驗(yàn)十：排序 要求：掌握常見的排序算法的思想及其適用條件、常見的排序算法的程序?qū)崿F(xiàn)。實(shí)驗(yàn)十一：綜合實(shí)驗(yàn)（一） 要求：使用數(shù)據(jù)結(jié)構(gòu)中各種算法編寫系統(tǒng)類結(jié)構(gòu)。實(shí)驗(yàn)十二：綜合實(shí)驗(yàn)（二） 要求：結(jié)合實(shí)驗(yàn)十一的設(shè)計(jì)，完成綜合系統(tǒng)的實(shí)現(xiàn)和調(diào)試。本課程通過課堂講授例題、課堂練習(xí)、課后

11、習(xí)題、上機(jī)實(shí)驗(yàn)以及課程設(shè)計(jì)等各個(gè)實(shí)踐環(huán)節(jié)，對(duì)學(xué)生進(jìn)行系統(tǒng)的程序設(shè)計(jì)訓(xùn)練。所有例題、課堂練習(xí)題、課后習(xí)題、上機(jī)實(shí)驗(yàn)題都是精心挑選的，由淺入深，環(huán)環(huán)相扣，步步推進(jìn)，調(diào)動(dòng)學(xué)生的主動(dòng)性和自覺性并培養(yǎng)學(xué)生寫程序的興趣。除了課內(nèi)安排的習(xí)題課、課堂討論、期中測(cè)驗(yàn)、復(fù)習(xí)課以外，每次課后都要求學(xué)生做至少2個(gè)完整的程序，并定期檢查學(xué)生做作業(yè)的情況，作業(yè)的數(shù)量和質(zhì)量占平時(shí)成績的一部分?？己朔绞秸f明：本課程為考試課程，期末考試為閉卷筆試。學(xué)生的課程總評(píng)成績由平時(shí)成績（占30%）和期末考試成績(70%)兩部分構(gòu)成，平時(shí)成績中實(shí)驗(yàn)成績占20%，出勤、作業(yè)、課堂測(cè)驗(yàn)、學(xué)習(xí)主動(dòng)性等占10%。實(shí)驗(yàn)成績根據(jù)實(shí)驗(yàn)報(bào)告質(zhì)量評(píng)定，作業(yè)成績根據(jù)習(xí)題的數(shù)量和質(zhì)量評(píng)定。五、本課程與其他課程的聯(lián)系本課程是計(jì)算機(jī)專業(yè)基礎(chǔ)課，其先修課程是程序設(shè)計(jì)語言、離散數(shù)學(xué)，后續(xù)課程包括算法設(shè)計(jì)與分析、編譯技術(shù)、操作系統(tǒng)等課程。六、教學(xué)參考書目數(shù)據(jù)結(jié)構(gòu)（C+版），王紅梅編著，清華大學(xué)出版社，2008年。數(shù)據(jù)結(jié)構(gòu)（C+版），葉核亞編著，機(jī)械工業(yè)出版社，2004年。數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程，嚴(yán)蔚敏等編著，清華大學(xué)出版社，2001年。數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+描述），殷人昆等編著，清華大學(xué)出版社，1999年。數(shù)據(jù)結(jié)構(gòu)教程