【正文】 表的查找、插入和刪除算法，掌握鏈表的查找、插入和刪除算法。能夠從時(shí)間和空間復(fù)雜度的角度比較兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。掌握無(wú)序表和有序表的合并算法，了解多項(xiàng)式的加法運(yùn)算。實(shí)驗(yàn)：實(shí)驗(yàn)內(nèi)容：?jiǎn)捂湵淼幕静僮?。?shí)驗(yàn)要求：以單鏈表形式創(chuàng)建一個(gè)學(xué)生表或圖書(shū)表，并能實(shí)現(xiàn)相關(guān)的查找、插入和刪除等算法。（理論6學(xué)時(shí)，實(shí)驗(yàn)4學(xué)時(shí)）教學(xué)內(nèi)容：(1)棧的類型定義，棧的順序存儲(chǔ)和鏈接存儲(chǔ)的表示和實(shí)現(xiàn)。(2)棧的應(yīng)用舉例，如迷宮求解和表達(dá)式求值。(3)棧與遞歸的實(shí)現(xiàn)，遞歸程序轉(zhuǎn)換為非遞歸程序的方法。(4)隊(duì)列的類型，隊(duì)列的順序存儲(chǔ)(循環(huán)隊(duì))和鏈接存儲(chǔ)的表示和實(shí)現(xiàn)。(5)隊(duì)列的應(yīng)用舉例，如打印楊暉三角形，模擬汽車(chē)加油站等問(wèn)題?；疽螅赫莆諚：完?duì)列的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用。熟練掌握棧的順序棧和鏈棧的進(jìn)棧出棧算法，特別應(yīng)注意棧滿和?？盏臈l件。掌握利用棧實(shí)現(xiàn)表達(dá)式求值的算法，了解迷宮求解算法。理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程，了解將遞歸程序轉(zhuǎn)換為非遞歸程序的方法。熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的進(jìn)隊(duì)出隊(duì)算法，特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況。了解隊(duì)列的應(yīng)用。實(shí)驗(yàn)：實(shí)驗(yàn)內(nèi)容：棧的應(yīng)用。實(shí)驗(yàn)要求：借助棧來(lái)解決某些實(shí)際應(yīng)用問(wèn)題，如表達(dá)式求值、迷宮問(wèn)題等。、數(shù)組和廣義表（理論2學(xué)時(shí)）教學(xué)內(nèi)容：(1)串的表示和實(shí)現(xiàn)，包括順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)表示。古典的模式匹配算法。(2)數(shù)組的存儲(chǔ)方法。(3)特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)，稀疏矩陣的轉(zhuǎn)置運(yùn)算。(4)廣義表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)?；疽螅毫私獯捻樞虼鎯?chǔ)結(jié)構(gòu)和堆存儲(chǔ)結(jié)構(gòu)。掌握串的古典的模式匹配算法。掌握數(shù)組的地址計(jì)算方法。了解稀疏矩陣的兩種壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍。了解廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)方法。（理論8學(xué)時(shí)，實(shí)驗(yàn)2學(xué)時(shí)）教學(xué)內(nèi)容：(1)二叉樹(shù)的定義和術(shù)語(yǔ)，二叉樹(shù)的性質(zhì)，特殊的二叉樹(shù)。(2)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，順序存儲(chǔ)和二叉鏈表。(3)二叉樹(shù)的的前序、中序、后序、層次遍歷方法。線索化二叉樹(shù)。(4)樹(shù)和森林的定義，樹(shù)的存儲(chǔ)，樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換。(5)樹(shù)的應(yīng)用，哈夫曼樹(shù)及哈夫曼編碼?；疽螅毫私鈽?shù)和森林的概念，包括樹(shù)的定義、樹(shù)的術(shù)語(yǔ)。掌握二叉樹(shù)的概念、性質(zhì)及二叉樹(shù)的表示。熟練掌握二叉樹(shù)的遍歷算法，并且能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其他操作。掌握線索化二叉樹(shù)的特性及尋找某結(jié)點(diǎn)的前驅(qū)和后繼的方法。了解樹(shù)的存儲(chǔ)、樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法。掌握哈夫曼樹(shù)的實(shí)現(xiàn)方法、構(gòu)造哈夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算。實(shí)驗(yàn)：實(shí)驗(yàn)內(nèi)容：二叉樹(shù)的基本算法。實(shí)驗(yàn)要求：利用二叉鏈表方法建立二叉樹(shù)，實(shí)現(xiàn)二叉樹(shù)的前、中、后序三種遍歷算法，并運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其他操作，如計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)、葉子結(jié)點(diǎn)個(gè)數(shù)、二叉樹(shù)的高度等。（理論8學(xué)時(shí)，實(shí)驗(yàn)2學(xué)時(shí)）教學(xué)內(nèi)容：(1)圖的定義和術(shù)語(yǔ)。(2)圖的存儲(chǔ)結(jié)構(gòu)兩種存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表表示法。(3)圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索。(4)構(gòu)造最小生成樹(shù)的兩種算法：普里姆算法和克魯斯卡爾算法。(5)拓?fù)渑判蚝完P(guān)鍵路徑。(6)兩類求最短路徑問(wèn)題的算法，迪杰斯特拉算法和弗洛伊德算法?；疽螅赫莆?qǐng)D的基本概念及相關(guān)術(shù)語(yǔ)和性質(zhì)，掌握?qǐng)D的鄰接矩陣和鄰接表表示法，了解實(shí)際問(wèn)題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系。熟練掌握?qǐng)D的兩種搜索路徑的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。掌握構(gòu)造最小生成樹(shù)的兩種算法及拓?fù)渑判蛩惴ǖ乃枷?，掌握迪杰斯特拉算法。了解關(guān)鍵路徑的概念和求解方法，了解弗洛伊德算法。實(shí)驗(yàn)：實(shí)驗(yàn)內(nèi)容：圖的建立和搜索。實(shí)驗(yàn)要求：使用鄰接矩陣或鄰接表表示法存儲(chǔ)一個(gè)圖，實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。（理論6學(xué)時(shí)）教學(xué)內(nèi)容：(1)查找的基本概念，平均查找長(zhǎng)度。(2)基于線性表的查找：順序查找、折半查找。(3)基于樹(shù)表的查找：二叉排序樹(shù)、平衡二叉樹(shù)、B樹(shù)和B+樹(shù)。(4)散列表：散列表的基本概念，散列函數(shù)的構(gòu)造方法、處理沖突的方法、散列表的查找與分析。基本要求：熟練掌握順序表和有序表的查找方法及其實(shí)現(xiàn)，掌握二叉排序樹(shù)的插入和查找算法及其實(shí)現(xiàn)，了解平衡二叉樹(shù)、B樹(shù)和B+樹(shù)的各種操作。熟練掌握散列表的構(gòu)造方法、處理沖突的方法，深刻理散列表與其他結(jié)構(gòu)的表的實(shí)質(zhì)性的差別，了解各種散列函數(shù)的特點(diǎn)。掌握描述折半查找過(guò)程的判定樹(shù)的構(gòu)造方法，以及按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。（理論8學(xué)時(shí)，實(shí)驗(yàn)2學(xué)時(shí)）教學(xué)內(nèi)容：(1)排序的基本概念，包括正序，逆序，穩(wěn)定性，排序方法的分類。(2)插入排序：直接插入排序、折半插入排序和希爾排序。(3)交換排序：冒泡排序和快速排序。(4)選擇排序：簡(jiǎn)單選擇排序和堆排序。(5)歸并排序：2路歸并排序。(6)基數(shù)排序：多關(guān)鍵字的排序和鏈數(shù)基數(shù)排序。(7)排序算法分析：各種排序算法的比較和移動(dòng)次數(shù)，時(shí)間復(fù)雜度和空間復(fù)雜度的分析。基本要求：明確排序的基本概念，排序方法的分類。深刻理解排序算法的過(guò)程、特點(diǎn)及其依據(jù)的原則，并能加以靈活應(yīng)用。掌握各種排序方法的時(shí)間和空間復(fù)雜度的分析方法。能從關(guān)鍵字間的比較次數(shù)和移動(dòng)次數(shù)分析算法的平均情況和最壞情況的時(shí)間性能。理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的?？焖倥判?、堆排序和歸并排序等高效排序方法是本章的學(xué)習(xí)重點(diǎn)和難點(diǎn)。實(shí)驗(yàn)：實(shí)驗(yàn)內(nèi)容：綜合性實(shí)驗(yàn)。實(shí)驗(yàn)要求：選取一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，能對(duì)數(shù)據(jù)進(jìn)行插入、刪除，用不同查找算法進(jìn)行查找、用不同的排序算法進(jìn)行排序等。（1周）教學(xué)內(nèi)容：(1)設(shè)計(jì)準(zhǔn)備：理解實(shí)習(xí)任務(wù)，明確相關(guān)算法，搜集可用資源，熟悉實(shí)習(xí)環(huán)境。(2)方案設(shè)計(jì)：完成設(shè)計(jì)目標(biāo)、設(shè)計(jì)路線的確定，并進(jìn)行模塊設(shè)計(jì)和任務(wù)分工。(3)代碼編寫(xiě)：各模塊代碼編寫(xiě)，模塊測(cè)試。(4)代碼測(cè)試：模塊組裝，整體測(cè)試。(5)設(shè)計(jì)報(bào)告：完成設(shè)計(jì)文檔，制作設(shè)計(jì)報(bào)告?；疽螅耗軐?shù)據(jù)結(jié)構(gòu)課程中所學(xué)的基本知識(shí)融會(huì)貫通，綜合運(yùn)用所學(xué)的知識(shí)解決相關(guān)的實(shí)際問(wèn)題，能夠把所學(xué)知識(shí)（包括算法和結(jié)構(gòu)）在計(jì)算機(jī)上用編程語(yǔ)言加以實(shí)現(xiàn)，并且能夠根據(jù)實(shí)際需求創(chuàng)建自己的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)自己的算法。本課程的教學(xué)環(huán)節(jié)包括：課堂講授、實(shí)驗(yàn)、實(shí)習(xí)、作業(yè)、答疑、小測(cè)驗(yàn)等。其中，課堂講授以教師講授為主，授課時(shí)將電子教案和板書(shū)相結(jié)合，充分發(fā)揮各自的優(yōu)點(diǎn)。采用啟發(fā)式教學(xué)，鼓勵(lì)學(xué)生自學(xué)，培養(yǎng)學(xué)生的自學(xué)能力，以“少而精”為原則，精選教學(xué)內(nèi)容，調(diào)動(dòng)學(xué)生學(xué)習(xí)的主觀能動(dòng)性。實(shí)驗(yàn)針對(duì)相應(yīng)單元所學(xué)的內(nèi)容，能夠采取合適的數(shù)據(jù)結(jié)構(gòu)和算法解決有關(guān)問(wèn)題。實(shí)驗(yàn)重點(diǎn)培養(yǎng)學(xué)生的動(dòng)手能力。實(shí)習(xí)針對(duì)較為復(fù)雜的應(yīng)用問(wèn)題，能夠綜合運(yùn)用所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行算法設(shè)計(jì)和實(shí)現(xiàn)，注重學(xué)生數(shù)據(jù)抽象能力和算法設(shè)計(jì)能力的培養(yǎng)。三、本課程與其它課程的聯(lián)系和分工本課程的先修課為程序設(shè)計(jì)基礎(chǔ)和離散數(shù)學(xué)，本課程可以C/C++或Java語(yǔ)言作為算法描述和上機(jī)實(shí)踐的工具。同時(shí)，本課程又是軟件開(kāi)發(fā)與設(shè)計(jì)等方面課程的基礎(chǔ)，如數(shù)據(jù)庫(kù)、操作系統(tǒng)、編譯原理、軟件工程等課程。四、本課程的考核方式期末考試采用筆試形式，考試題型為：選擇、填空、判斷、應(yīng)用題和算法設(shè)計(jì)題。總評(píng)成績(jī)由平時(shí)成績(jī)和期末成績(jī)組成，其中平時(shí)成績(jī)占30%40%，期末考試占70%60%。課程實(shí)習(xí)的成績(jī)由平時(shí)成績(jī)和實(shí)習(xí)作業(yè)兩部分組成，其中平時(shí)成績(jī)占30%，實(shí)習(xí)作業(yè)占70%。五、建議教材與教學(xué)參考書(shū)建議教材：，李冬梅，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）．北京：人民郵電出版社． ．?dāng)?shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）．北京：清華大學(xué)出版社．．?dāng)?shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）．北京：清華大學(xué)出版社． 建議教學(xué)參考書(shū)：1.[美]Bruno ，胡廣斌，王崧等譯．?dāng)?shù)據(jù)結(jié)構(gòu)與算法－面向?qū)ο蟮腃++設(shè)計(jì)模式．北京：電子工業(yè)出版社．．?dāng)?shù)據(jù)結(jié)構(gòu)與習(xí)題解析（用面向?qū)ο蠓椒ㄅcC++描述）．北京：清華大學(xué)出版社．六、課程簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu)是一門(mén)專業(yè)基礎(chǔ)課，是學(xué)習(xí)其他軟件開(kāi)發(fā)與設(shè)計(jì)等方面課程的基礎(chǔ)。主要內(nèi)容包括：線性表、棧和隊(duì)列、串、數(shù)組和廣義表、樹(shù)、圖、查找算法和排序算法。數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的組織方式，內(nèi)容豐富、學(xué)習(xí)量大，隱含在各部分內(nèi)容中的方法和技術(shù)多，旨在讓學(xué)生掌握計(jì)算機(jī)軟件系統(tǒng)所必需的數(shù)據(jù)結(jié)構(gòu)的算法。要求學(xué)生掌握貫穿全課程的動(dòng)態(tài)鏈表存儲(chǔ)結(jié)構(gòu)，掌握算法設(shè)計(jì)的動(dòng)態(tài)性和抽象性。要求學(xué)生學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特征，以便在實(shí)際應(yīng)用中選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相應(yīng)算法，初步掌握算法的時(shí)間與空間性能分析技巧，并培養(yǎng)復(fù)雜程序設(shè)計(jì)的技能。執(zhí)筆人：審核人：教學(xué)院長(zhǎng)：院學(xué)術(shù)委員會(huì)：院長(zhǎng)：