軟件專題課程教學(xué)大綱課程英文名稱：SoftwareTopic課程編號(hào)：050769課程類型：專業(yè)任選課總學(xué)時(shí)：64學(xué)分：3適用對(duì)象：信息與計(jì)算科學(xué)、數(shù)學(xué)與應(yīng)用數(shù)學(xué)、統(tǒng)計(jì)學(xué)周學(xué)時(shí)：4開設(shè)學(xué)期：第七學(xué)期開課單位：數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院先修課程：離散數(shù)學(xué)、C：2017：2017年7月教材：《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（第二版，2006參考書：《數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)——C++語(yǔ)言描述》（影印版）RobertL.Kruse,AlexanderJ.Ryba,高等教育出版社，2001《數(shù)據(jù)結(jié)構(gòu)（C，1997一、課程教學(xué)目的和任務(wù)通過本課程教學(xué)，使學(xué)生了解線性表、集合、廣義表、棧、隊(duì)列、樹、二叉樹、圖、查找等幾種數(shù)據(jù)結(jié)構(gòu)的基本概念、操作及其典型應(yīng)用例子，通過課堂教學(xué)、課外練習(xí)和上機(jī)實(shí)習(xí)，使學(xué)生了解數(shù)據(jù)對(duì)象的特性，數(shù)據(jù)組織的基本方法，并初步具備分析和解決現(xiàn)實(shí)世界問題在計(jì)算機(jī)中如何表示和處理的能力以及培養(yǎng)良好的程序設(shè)計(jì)技能，為后續(xù)課程的學(xué)習(xí)和科研工作的參與打下良好的基礎(chǔ)。二、課程教學(xué)基本要求1、在保證該課程教學(xué)的科學(xué)性和系統(tǒng)性的前提下，著重突出線性表、棧、隊(duì)列、樹、圖等數(shù)據(jù)結(jié)構(gòu)的基本概念、基本知識(shí)和基本技能，作為教學(xué)的重點(diǎn)內(nèi)容，要求學(xué)生牢固掌握并熟練運(yùn)用。2的存儲(chǔ)結(jié)構(gòu)及其在相應(yīng)存儲(chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)上。3題的能力放在重要位置。4布置一定量的課后作業(yè)，要求學(xué)生按時(shí)完成。三、課程教學(xué)重點(diǎn)和難點(diǎn)存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法實(shí)現(xiàn)；二叉樹的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)和相關(guān)運(yùn)算；二叉搜索樹的運(yùn)算，堆的存儲(chǔ)結(jié)構(gòu)及運(yùn)算，哈夫曼樹的構(gòu)造；圖的存儲(chǔ)結(jié)構(gòu)，圖的遍歷操作；圖的最小生成樹難點(diǎn)隊(duì)列的入隊(duì)與出隊(duì)，循環(huán)隊(duì)列的隊(duì)空、隊(duì)滿判斷條件；二叉樹的建立，求二叉樹的深度，二叉樹中查找結(jié)點(diǎn)，二叉樹的輸出；二叉搜索樹的插入、刪除運(yùn)算，堆的插入、刪除運(yùn)算；圖的按層遍歷算法；圖的最小生成樹算法：普里姆算法、克魯斯卡爾算法，從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑：狄克斯特拉算法；四、課程教學(xué)內(nèi)容第一章緒論[教學(xué)目的]從而為后面章節(jié)的學(xué)習(xí)打下基礎(chǔ)。另外，對(duì)一個(gè)算法好壞的度量，時(shí)間復(fù)雜度是一個(gè)重要的指標(biāo)，通過這一章的學(xué)習(xí)，應(yīng)使學(xué)生對(duì)算法的時(shí)間復(fù)雜度有所了解。[教學(xué)要求]領(lǐng)會(huì)數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間的關(guān)系；實(shí)現(xiàn)；理解抽象數(shù)據(jù)類型的概念；掌握進(jìn)行簡(jiǎn)單算法分析的方法。[重點(diǎn)難點(diǎn)]重點(diǎn)：邏輯結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)在概念上的聯(lián)系與區(qū)別；抽象數(shù)據(jù)類型和數(shù)據(jù)抽象；評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)及方法；難點(diǎn)：抽象數(shù)據(jù)類型與數(shù)據(jù)抽象；算法的時(shí)間復(fù)雜度分析[教學(xué)內(nèi)容]第一節(jié)常用術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)常用術(shù)語(yǔ)；邏輯結(jié)構(gòu)的表示第二節(jié)算法描述算法的描述方法第三節(jié)算法評(píng)價(jià)算法好壞的評(píng)價(jià)指標(biāo)第四節(jié)*與算法描述相關(guān)的C++知識(shí)（注：*為選學(xué)內(nèi)容，以下同）C++的頭文件；C++中的數(shù)據(jù)類型第二章線性表[教學(xué)目的]通過本章的學(xué)習(xí)，應(yīng)使學(xué)生掌握對(duì)線性數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)和處理以及應(yīng)用。[教學(xué)要求]理解線性表的定義及其運(yùn)算；理解順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說明；掌握在這兩種表上實(shí)現(xiàn)的插入、刪除和按值查找的算法；了解循環(huán)鏈表、雙向鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入、刪除等操作。[重點(diǎn)難點(diǎn)]重點(diǎn)：線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)；線性表的各種操作運(yùn)算難點(diǎn)：線性表在存儲(chǔ)結(jié)構(gòu)下的插入、刪除運(yùn)算[教學(xué)內(nèi)容]第一節(jié)線性表的定義和抽象數(shù)據(jù)類型線性表的定義及相關(guān)概念；線性表的抽象數(shù)據(jù)類型表示第二節(jié)線性表的順序存儲(chǔ)與操作實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)；順序存儲(chǔ)下線性表操作的實(shí)現(xiàn)第三節(jié)*線性表應(yīng)用舉例線性表順序存儲(chǔ)下的應(yīng)用舉例第四節(jié)線性表的鏈接存儲(chǔ)結(jié)構(gòu)鏈接存儲(chǔ)的概念；鏈接存儲(chǔ)的表示；單鏈表的插入刪除操作；雙向單鏈表的插入刪除操作；第五節(jié)線性表操作在單鏈表上的實(shí)現(xiàn)單鏈表存儲(chǔ)下的線性表操作的實(shí)現(xiàn)第六節(jié)多項(xiàng)式計(jì)算多項(xiàng)式的表示方式及多項(xiàng)式的計(jì)算第三章集合、稀疏矩陣和廣義表[教學(xué)目的]通過本章的學(xué)習(xí)，應(yīng)使學(xué)生了解集合在內(nèi)存空間中的存儲(chǔ)方法。另外為了節(jié)省空間，將特殊和稀疏矩陣采用特殊的存儲(chǔ)方法以及在這些存儲(chǔ)方法下的矩陣運(yùn)算。了解廣義表的概念，存儲(chǔ)結(jié)構(gòu)以及廣義表的運(yùn)算操作。[教學(xué)要求]理解集合的定義、存儲(chǔ)結(jié)構(gòu)及其操作的實(shí)現(xiàn)；理解稀疏矩陣的概念及其存儲(chǔ)結(jié)構(gòu)；理解廣義表的定義、存儲(chǔ)結(jié)構(gòu)及其操作[重點(diǎn)難點(diǎn)]重點(diǎn)：順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)；集合的插入、刪除、交、并和差運(yùn)算；稀疏矩陣的存儲(chǔ)難點(diǎn)：集合在存儲(chǔ)結(jié)構(gòu)下插入、刪除、交、并和差運(yùn)算[教學(xué)內(nèi)容]第一節(jié)集合的定義和抽象數(shù)據(jù)類型集合的定義及相關(guān)概念；集合的抽象數(shù)據(jù)類型表示第二節(jié)集合的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)集合的順序存儲(chǔ)結(jié)構(gòu)；順序存儲(chǔ)下集合操作的實(shí)現(xiàn)第三節(jié)集合的鏈接存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)集合的鏈接存儲(chǔ)結(jié)構(gòu)；鏈接存儲(chǔ)下集合操作的實(shí)現(xiàn)第四節(jié)稀疏矩陣稀疏矩陣的概念及三元組表示；稀疏矩陣的存儲(chǔ)結(jié)構(gòu)第五節(jié)廣義表廣義表的定義及表示方法；廣義表的相關(guān)運(yùn)算第四章棧和隊(duì)列[教學(xué)目的]通過本章學(xué)習(xí)，應(yīng)使學(xué)生熟練掌握棧和隊(duì)列的實(shí)現(xiàn)方法，并能使用棧和隊(duì)列解決問題。[教學(xué)要求]理解棧的定義、特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)棧所施加的基本運(yùn)算的實(shí)現(xiàn)；理解算術(shù)表達(dá)式在計(jì)算機(jī)中的實(shí)現(xiàn)掌握遞歸算法思想理解隊(duì)列的定義、特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。[重點(diǎn)難點(diǎn)]重點(diǎn)：棧與隊(duì)列的特性、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法實(shí)現(xiàn)難點(diǎn)：棧的入棧與出棧、隊(duì)列的入隊(duì)與出隊(duì)；循環(huán)隊(duì)列的隊(duì)空、隊(duì)滿判斷條件；[教學(xué)內(nèi)容]第一節(jié)棧棧的定義及相關(guān)概念；棧的抽象數(shù)據(jù)類型表示第二節(jié)棧的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)棧的順序存儲(chǔ)結(jié)構(gòu)；順序存儲(chǔ)下棧操作的實(shí)現(xiàn)第三節(jié)棧的鏈接存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)棧的鏈接存儲(chǔ)結(jié)構(gòu)；鏈接存儲(chǔ)下棧操作的實(shí)現(xiàn)第四節(jié)棧的簡(jiǎn)單應(yīng)用舉例逆序輸出；語(yǔ)法檢查；十進(jìn)制數(shù)的轉(zhuǎn)換第五節(jié)算術(shù)表達(dá)式的計(jì)算算術(shù)表達(dá)式的表示形式；后綴表達(dá)式的求值算法；中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的算法第六節(jié)棧與遞歸遞歸思想的應(yīng)用；棧在遞歸中的使用第七節(jié)隊(duì)列隊(duì)列的定義及相關(guān)概念；隊(duì)列的抽象數(shù)據(jù)類型表示；隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)；順序存儲(chǔ)下隊(duì)列操作的實(shí)現(xiàn)；隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)；鏈接存儲(chǔ)下隊(duì)列操作的實(shí)現(xiàn)第八節(jié)*隊(duì)列應(yīng)用舉例隊(duì)列在計(jì)算機(jī)領(lǐng)域的應(yīng)用第五章樹[教學(xué)目的]通過本章的學(xué)習(xí)，應(yīng)使學(xué)生熟練掌握樹型結(jié)構(gòu)的特點(diǎn)，要讓學(xué)生理解不是為了處理樹型結(jié)構(gòu)數(shù)據(jù)去構(gòu)造樹，而是客觀世界中的一些問題滿足樹型結(jié)構(gòu)。對(duì)樹型問題的處理過程就是遍歷樹的過程，而不同的遍歷方法與實(shí)際的樹型問題相關(guān)。[教學(xué)要求]理解樹的定義、相關(guān)基本概念及性質(zhì)；深刻理解二叉樹的定義、性質(zhì)及其存儲(chǔ)方法；熟練掌握二叉樹的鏈接存儲(chǔ)方式、結(jié)點(diǎn)結(jié)構(gòu)和類型定義；理解并掌握二叉樹的四種遍歷算法；掌握在鏈接存儲(chǔ)結(jié)構(gòu)上對(duì)二叉樹所施加的基本運(yùn)算的實(shí)現(xiàn)。了解樹的存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)[重點(diǎn)難點(diǎn)]重點(diǎn)：二叉樹的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)和相關(guān)運(yùn)算；難點(diǎn)：二叉樹上的遍歷操作[教學(xué)內(nèi)容]第一節(jié)樹的概念樹的定義；樹的表示方法；樹的基本術(shù)語(yǔ)；樹的性質(zhì)第二節(jié)二叉樹二叉樹的定義；二叉樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類型及存儲(chǔ)結(jié)構(gòu)第三節(jié)二叉樹遍歷前序遍歷；中序遍歷；后序遍歷；按層遍歷第四節(jié)二叉樹其他運(yùn)算鏈接存儲(chǔ)下二叉樹的操作實(shí)現(xiàn)第五節(jié)樹的存儲(chǔ)結(jié)構(gòu)和運(yùn)算樹的抽象數(shù)據(jù)類型；樹的存儲(chǔ)結(jié)構(gòu)；樹的操作實(shí)現(xiàn)第六章特殊二叉樹[教學(xué)目的]通過本章的學(xué)習(xí)，應(yīng)使學(xué)生熟練掌握特殊樹型結(jié)構(gòu)的特點(diǎn)，掌握特殊二叉樹運(yùn)算特點(diǎn)，它們?cè)趯?shí)際的學(xué)習(xí)與生活中都有不同的應(yīng)用。[教學(xué)要求]理解哈夫曼樹的定義，掌握哈夫曼樹的構(gòu)造方法；[重點(diǎn)難點(diǎn)]重點(diǎn)：二叉搜索樹的運(yùn)算；堆的存儲(chǔ)結(jié)構(gòu)及運(yùn)算；哈夫曼樹的構(gòu)造難點(diǎn)：二叉搜索樹的刪除運(yùn)算；堆的插入、刪除運(yùn)算[教學(xué)內(nèi)容]第一節(jié)二叉搜索樹二叉搜索樹的定義；二叉搜索樹的抽象數(shù)據(jù)類型；鏈接存儲(chǔ)下二叉搜索樹的操作實(shí)現(xiàn)第二節(jié)堆堆的定義；堆的抽象數(shù)據(jù)類型；堆的存儲(chǔ)結(jié)構(gòu)；順序存儲(chǔ)下堆的操作實(shí)現(xiàn)第三節(jié)哈夫曼樹哈夫曼樹的常用術(shù)語(yǔ)；哈夫曼樹的構(gòu)造算法；哈夫曼編碼第四節(jié)*二叉樹線索化；利用線索遍歷二叉樹第五節(jié)*平衡二叉樹的定義；平衡二叉樹的調(diào)整第七章圖[教學(xué)目的]圖是最復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，通過本章的學(xué)習(xí)，應(yīng)使學(xué)生熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其圖的遍歷算法。[教學(xué)要求]理解圖的基本概念及術(shù)語(yǔ)；掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)(鄰接矩陣、鄰接表和邊集數(shù)組)的表示方法；列出在兩種存儲(chǔ)結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；[重點(diǎn)難點(diǎn)]重點(diǎn)：圖的存儲(chǔ)結(jié)構(gòu)；圖的遍歷操作難點(diǎn)：圖的按層遍歷[教學(xué)內(nèi)容]第一節(jié)圖的概念圖的定義及基本術(shù)語(yǔ)；圖的抽象數(shù)據(jù)類型；第二節(jié)圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)表示鄰接矩陣、鄰接表和邊集數(shù)組及相應(yīng)操作實(shí)現(xiàn)；第三節(jié)圖的遍歷廣度優(yōu)先搜索遍歷、深度優(yōu)先搜索遍歷第八章圖的應(yīng)用[教學(xué)目的]通過本章的學(xué)習(xí)，應(yīng)使學(xué)生熟悉如何求圖的最小生成樹、最短路徑、拓?fù)渑判蚣瓣P(guān)鍵路徑等特定運(yùn)算問題。[教學(xué)要求]PrimKruskalDijkstraAOV[重點(diǎn)難點(diǎn)]重點(diǎn)：普里姆算法、克魯斯卡爾算法、狄克斯特拉算法難點(diǎn)：狄克斯特拉算法[教學(xué)內(nèi)容]第一節(jié)圖的生成樹和最小生成樹最小生成樹的定義；普里姆算法和克魯斯卡爾算法；第二節(jié)最短路徑最短路徑的概念；迪杰斯特拉算法第三節(jié)拓?fù)渑判蛲負(fù)渑判虻母拍睿籄OV頂點(diǎn)事件的發(fā)生時(shí)間；關(guān)鍵路徑的計(jì)算與算法五、實(shí)踐環(huán)節(jié)（實(shí)驗(yàn)總學(xué)時(shí)：32學(xué)時(shí)）實(shí)驗(yàn)?zāi)康模和ㄟ^上機(jī)實(shí)踐加深對(duì)課程內(nèi)容的理解，增加感性認(rèn)識(shí)，提高軟件設(shè)計(jì)、編寫及調(diào)試程序的能力。實(shí)驗(yàn)要求：掌握數(shù)據(jù)結(jié)構(gòu)的基本理論和概念，數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)、線性表、棧、隊(duì)列、串、數(shù)組、樹和二叉數(shù)以及圖等基本數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)及應(yīng)用。掌握查找、排序的實(shí)現(xiàn)方法，以及從時(shí)間上進(jìn)行定性和定量的分析和比較，為進(jìn)一步的學(xué)習(xí)打下良好基礎(chǔ)。實(shí)驗(yàn)內(nèi)容及要求一覽表：章目實(shí)驗(yàn)項(xiàng)目名稱實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)類型學(xué)時(shí)分配演示驗(yàn)證綜合1熟悉VC++運(yùn)行環(huán)境熟悉完整的C程序運(yùn)行過程√22線性表的順序存儲(chǔ)線性表順序存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)√23線性表的鏈接存儲(chǔ)線性表鏈接存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)√24集合的順序存儲(chǔ)集合順序存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)√25集合的鏈接存儲(chǔ)集合順序存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)√26棧的順序存儲(chǔ)棧的順序存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)√27棧的鏈接存儲(chǔ)棧的鏈接存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)√28隊(duì)列的順序存儲(chǔ)棧的順序存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)√29二叉樹二叉樹的創(chuàng)建及遍歷操作的實(shí)現(xiàn)√210二叉搜索樹二叉搜索樹創(chuàng)建及刪除操作的實(shí)現(xiàn)√211堆堆的創(chuàng)建及刪除操作的操作實(shí)現(xiàn)√212哈夫曼樹哈夫曼樹的構(gòu)造算法的操作實(shí)現(xiàn)√213圖的遍歷圖的四種遍歷算法的操作實(shí)現(xiàn)√214普里姆算法普里姆算法的操作實(shí)現(xiàn)√215克魯斯卡爾算法克魯斯卡爾算法的操作實(shí)現(xiàn)√216狄克斯特拉算法狄克斯特拉算法的操作實(shí)現(xiàn)√2總學(xué)時(shí)32六、學(xué)時(shí)分配總學(xué)時(shí)：64學(xué)時(shí)其中課堂教學(xué)：32學(xué)時(shí)；實(shí)踐教學(xué)：32學(xué)時(shí)課堂教學(xué)學(xué)時(shí)分配一覽