【正文】 要求學(xué)生學(xué)會分析研究計(jì)算機(jī)加工的數(shù)據(jù)對象的特征，以便在實(shí)際應(yīng)用中選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和相應(yīng)算法，初步掌握算法的時(shí)間與空間性能分析技巧，并培養(yǎng)復(fù)雜程序設(shè)計(jì)的技能。數(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)?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è)計(jì)模式．北京：電子工業(yè)出版社．．?dāng)?shù)據(jù)結(jié)構(gòu)與習(xí)題解析（用面向?qū)ο蠓椒ㄅcC++描述）．北京：清華大學(xué)出版社．六、課程簡介數(shù)據(jù)結(jié)構(gòu)是一門專業(yè)基礎(chǔ)課，是學(xué)習(xí)其他軟件開發(fā)與設(shè)計(jì)等方面課程的基礎(chǔ)?？傇u成績由平時(shí)成績和期末成績組成，其中平時(shí)成績占30%40%，期末考試占70%60%。同時(shí)，本課程又是軟件開發(fā)與設(shè)計(jì)等方面課程的基礎(chǔ)，如數(shù)據(jù)庫、操作系統(tǒng)、編譯原理、軟件工程等課程。實(shí)習(xí)針對較為復(fù)雜的應(yīng)用問題，能夠綜合運(yùn)用所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行算法設(shè)計(jì)和實(shí)現(xiàn)，注重學(xué)生數(shù)據(jù)抽象能力和算法設(shè)計(jì)能力的培養(yǎng)。實(shí)驗(yàn)針對相應(yīng)單元所學(xué)的內(nèi)容，能夠采取合適的數(shù)據(jù)結(jié)構(gòu)和算法解決有關(guān)問題。其中，課堂講授以教師講授為主，授課時(shí)將電子教案和板書相結(jié)合，充分發(fā)揮各自的優(yōu)點(diǎn)。基本要求：能將數(shù)據(jù)結(jié)構(gòu)課程中所學(xué)的基本知識融會貫通，綜合運(yùn)用所學(xué)的知識解決相關(guān)的實(shí)際問題，能夠把所學(xué)知識（包括算法和結(jié)構(gòu)）在計(jì)算機(jī)上用編程語言加以實(shí)現(xiàn)，并且能夠根據(jù)實(shí)際需求創(chuàng)建自己的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)自己的算法。(4)代碼測試：模塊組裝，整體測試。(2)方案設(shè)計(jì)：完成設(shè)計(jì)目標(biāo)、設(shè)計(jì)路線的確定，并進(jìn)行模塊設(shè)計(jì)和任務(wù)分工。實(shí)驗(yàn)要求：選取一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)存儲數(shù)據(jù)，能對數(shù)據(jù)進(jìn)行插入、刪除，用不同查找算法進(jìn)行查找、用不同的排序算法進(jìn)行排序等?？焖倥判?、堆排序和歸并排序等高效排序方法是本章的學(xué)習(xí)重點(diǎn)和難點(diǎn)。能從關(guān)鍵字間的比較次數(shù)和移動(dòng)次數(shù)分析算法的平均情況和最壞情況的時(shí)間性能。深刻理解排序算法的過程、特點(diǎn)及其依據(jù)的原則，并能加以靈活應(yīng)用。(7)排序算法分析：各種排序算法的比較和移動(dòng)次數(shù)，時(shí)間復(fù)雜度和空間復(fù)雜度的分析。(5)歸并排序：2路歸并排序。(3)交換排序：冒泡排序和快速排序。（理論8學(xué)時(shí)，實(shí)驗(yàn)2學(xué)時(shí)）教學(xué)內(nèi)容：(1)排序的基本概念，包括正序，逆序，穩(wěn)定性，排序方法的分類。熟練掌握散列表的構(gòu)造方法、處理沖突的方法，深刻理散列表與其他結(jié)構(gòu)的表的實(shí)質(zhì)性的差別，了解各種散列函數(shù)的特點(diǎn)。(4)散列表：散列表的基本概念，散列函數(shù)的構(gòu)造方法、處理沖突的方法、散列表的查找與分析。(2)基于線性表的查找：順序查找、折半查找。實(shí)驗(yàn)要求：使用鄰接矩陣或鄰接表表示法存儲一個(gè)圖，實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。了解關(guān)鍵路徑的概念和求解方法，了解弗洛伊德算法。熟練掌握圖的兩種搜索路徑的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。(6)兩類求最短路徑問題的算法，迪杰斯特拉算法和弗洛伊德算法。(4)構(gòu)造最小生成樹的兩種算法：普里姆算法和克魯斯卡爾算法。(2)圖的存儲結(jié)構(gòu)兩種存儲結(jié)構(gòu)：鄰接矩陣和鄰接表表示法。實(shí)驗(yàn)要求：利用二叉鏈表方法建立二叉樹，實(shí)現(xiàn)二叉樹的前、中、后序三種遍歷算法，并運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其他操作，如計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)、葉子結(jié)點(diǎn)個(gè)數(shù)、二叉樹的高度等。掌握哈夫曼樹的實(shí)現(xiàn)方法、構(gòu)造哈夫曼編碼的方法及帶權(quán)路徑長度的計(jì)算。掌握線索化二叉樹的特性及尋找某結(jié)點(diǎn)的前驅(qū)和后繼的方法。掌握二叉樹的概念、性質(zhì)及二叉樹的表示。(5)樹的應(yīng)用，哈夫曼樹及哈夫曼編碼。線索化二叉樹。(2)二叉樹的存儲結(jié)構(gòu)，順序存儲和二叉鏈表。了解廣義表的結(jié)構(gòu)特點(diǎn)及其存儲方法。掌握數(shù)組的地址計(jì)算方法?；疽螅毫私獯捻樞虼鎯Y(jié)構(gòu)和堆存儲結(jié)構(gòu)。(3)特殊矩陣和稀疏矩陣的壓縮存儲，稀疏矩陣的轉(zhuǎn)置運(yùn)算。古典的模式匹配算法。實(shí)驗(yàn)要求：借助棧來解決某些實(shí)際應(yīng)用問題，如表達(dá)式求值、迷宮問題等。了解隊(duì)列的應(yīng)用。理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程，了解將遞歸程序轉(zhuǎn)換為非遞歸程序的方法。熟練掌握棧的順序棧和鏈棧的進(jìn)棧出棧算法，特別應(yīng)注意棧滿和?？盏臈l件。(5)隊(duì)列的應(yīng)用舉例，如打印楊暉三角形，模擬汽車加油站等問題。(3)棧與遞歸的實(shí)現(xiàn)，遞歸程序轉(zhuǎn)換為非遞歸程序的方法。（理論6學(xué)時(shí)，實(shí)驗(yàn)4學(xué)時(shí)）教學(xué)內(nèi)容：(1)棧的類型定義，棧的順序存儲和鏈接存儲的表示和實(shí)現(xiàn)。實(shí)驗(yàn)：實(shí)驗(yàn)內(nèi)容：單鏈表的基本操作。能夠從時(shí)間和空間復(fù)雜度的角度比較兩種存儲結(jié)構(gòu)的不同特點(diǎn)及其適用場合。熟練掌握這兩類存儲結(jié)構(gòu)的描述方法，掌握鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的區(qū)別及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。(4)線性表的應(yīng)用，包括無序表和有序表的合并、多項(xiàng)式的加法運(yùn)算等。(2)線性表的順序表示和實(shí)現(xiàn)。基本要求：掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，了解抽象數(shù)據(jù)類型，掌握算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析方法。(3)算法的概念和特性。二、課程教學(xué)內(nèi)容、學(xué)時(shí)分配和課程教學(xué)基本要求（理論2學(xué)時(shí)）教學(xué)內(nèi)容：(1)數(shù)據(jù)結(jié)構(gòu)的一些基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)等。教學(xué)目的：通過本課程的學(xué)習(xí)，一方面，使學(xué)生學(xué)會分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法，并初步了解對算法的時(shí)間分析和空間分析技術(shù)。鏈表插入、刪除運(yùn)算的算法。了解算法分析方法。他們的含義大致為：了解是正確理解概念，掌握是學(xué)會所學(xué)知識，熟練掌握就是運(yùn)用所學(xué)知識解決實(shí)際問題。因此，簡單地說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題的學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法。由于軟件的核心是算法，而算法實(shí)際上是對加工數(shù)據(jù)過程的描述，所以研究數(shù)據(jù)結(jié)構(gòu)對提高編程能力和設(shè)計(jì)高性能的算法是至關(guān)重要的。 Schuster Company，1996(數(shù)據(jù)結(jié)構(gòu)——C++:清華大學(xué)出版社，1997)[4] 徐孝凱，數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C/C++描述），北京:清華大學(xué)出版社，1999 [5] （使用C++語言描述），南京:東南大學(xué)出版社，2001 [6] 殷人昆,陶永雷,（用面向?qū)ο蠓椒ㄅcC++描述），北京:清華大學(xué)出版社，1999第四篇：數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)大綱教學(xué)大綱數(shù)據(jù)結(jié)構(gòu)與算法（Data Structures）計(jì)算機(jī)技術(shù)已成為現(xiàn)代化發(fā)展的重要支柱和標(biāo)志，并逐步滲透到人類生活的各個(gè)領(lǐng)域。后續(xù)課程：操作系統(tǒng)，數(shù)據(jù)庫原理等?？傇u成績：平時(shí)作業(yè)占30%，閉卷考試占70%。（五）實(shí)驗(yàn)用C語言或C++語言完成一些算法設(shè)計(jì)題。教師應(yīng)認(rèn)真組織，安排重點(diǎn)發(fā)言，充分調(diào)動(dòng)每一名同學(xué)的學(xué)習(xí)積極性，做好總結(jié)。（二）課后自學(xué)為了培養(yǎng)學(xué)生整理歸納，綜合分析和處理問題的能力，每章都安排一部分內(nèi)容，課上教師只給出自學(xué)提綱，不作詳細(xì)講解，課后學(xué)生自學(xué)。在傳授知識原理的前提下，配合實(shí)際應(yīng)用例子，由淺入深善于誘導(dǎo)，使學(xué)生從被動(dòng)吸收知識的狀態(tài)下，轉(zhuǎn)化到主動(dòng)索取知識的狀態(tài)中來，并采用多媒體輔助教學(xué)，加大課堂授課的知識含量。在教學(xué)方法上采用課堂講授，課后自學(xué)，課堂討論等教學(xué)形式。在每類排序方法中，又從簡單方法入手，重點(diǎn)討論性能先進(jìn)的高效方法。第9章 內(nèi)部排序（8學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）了解排序的基本思想和基本概念，理解和掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、步驟及算法。第8章 查找（10學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）了解查找的基本思想及查找成功和不成功的概念，掌握在順序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長度。第7章 圖（12學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）理解圖的基本概念及術(shù)語，掌握圖的兩種存儲結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法；熟練掌握圖的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹；了解并掌握拓?fù)渑判?、關(guān)鍵路徑、最短路徑的算法思想。第6章 樹和二叉樹（12學(xué)時(shí)，2個(gè)學(xué)時(shí)實(shí)驗(yàn)上機(jī)）深刻理解樹的定義、性質(zhì)及其存儲方法，熟練掌握二叉樹的二叉鏈表存儲方式、結(jié)點(diǎn)結(jié)構(gòu)和類型定義，并能畫出給定二叉樹的二叉鏈表的結(jié)構(gòu)示意圖；理解并掌握二叉樹的三種遍歷方法，并能寫出該三種遍歷的算法；會完成樹、森林與二叉樹間的相互轉(zhuǎn)換；理解哈夫曼樹的構(gòu)造方法，并能對給定的數(shù)據(jù)集合