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