【正文】 選用原則；(3)熟練掌握圖的兩種遍歷算法；(4)理解各種圖的應(yīng)用問題的算法。重點和難點：二叉樹和樹的遍歷及其應(yīng)用是本章的學(xué)習(xí)重點，而編寫實現(xiàn)二叉樹和樹的各種操作的遞歸算法也恰是本章的難點所在。知識點：數(shù)組的類型定義、數(shù)組的存儲表示、特殊矩陣的壓縮存儲表示方法、隨機稀疏矩陣的壓縮存儲表示方法。數(shù)組和廣義表(4學(xué)時)學(xué)習(xí)目標(biāo)：(1)理解數(shù)組類型的特點及其在高級編程語言中的存儲表示和實現(xiàn)方法，并掌握數(shù)組在“以行為主”的存儲表示中的地址計算方法；(2)掌握特殊矩陣的存儲壓縮表示方法；(3)理解稀疏矩陣的兩類存儲壓縮方法的特點及其適用范圍，領(lǐng)會以三元組表示稀疏矩陣時進(jìn)行矩陣運算所采用的處理方法。本章的難點是理解實現(xiàn)串匹配的KMP算法的思想。串(2學(xué)時)學(xué)習(xí)目標(biāo)：(1)理解串類型定義中各基本操作的特點，并能正確利用它們進(jìn)行串的其它操作；(2)理解串類型的各種存儲表示方法；(3)理解串匹配的各種算法。重點與難點：棧和隊列是在程序設(shè)計中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，因此本章的學(xué)習(xí)重點在于掌握這兩種結(jié)構(gòu)的特點，以便能在應(yīng)用問題中正確使用。知識點：線性表、順序表、鏈表、有序表。重點與難點：鏈表是本章的重點和難點。線性表(4學(xué)時)學(xué)習(xí)目標(biāo)：(1)了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計算機中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。重點與難點：本章無。“數(shù)據(jù)結(jié)構(gòu)”的前序課是《離散數(shù)學(xué)》、《C語言程序設(shè)計與算法初步》。要求學(xué)生從算法和數(shù)據(jù)結(jié)構(gòu)的相互依存關(guān)系中把握應(yīng)用算法設(shè)計的藝術(shù)和技能。通過課程的學(xué)習(xí)，應(yīng)使學(xué)生理解和掌握各種數(shù)據(jù)結(jié)構(gòu)(物理結(jié)構(gòu)和邏輯結(jié)構(gòu))的概念及其有關(guān)的算法；熟悉并了解目前常用數(shù)據(jù)結(jié)構(gòu)在計算機諸多領(lǐng)域中的基本應(yīng)用。數(shù)據(jù)結(jié)構(gòu)是針對處理大量非數(shù)值性程序問題而形成的一門學(xué)科，內(nèi)涵豐富、應(yīng)用范圍廣。二、課程的教學(xué)目標(biāo)“數(shù)據(jù)結(jié)構(gòu)”是計算機相關(guān)專業(yè)的一門重要專業(yè)基礎(chǔ)課，是計算機學(xué)科的公認(rèn)主干課。課程以結(jié)構(gòu)化程序設(shè)計語言C語言作為算法的描述工具，強化數(shù)據(jù)結(jié)構(gòu)基本知識和結(jié)構(gòu)化程序設(shè)計基本能力的雙基訓(xùn)練。第一篇：數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱一、課程基本信息課程名稱：數(shù)據(jù)結(jié)構(gòu)總學(xué)時：64(理論課內(nèi)學(xué)時48，上機課內(nèi)學(xué)時16)課程設(shè)計：24 課程類型：必修課考試形式：半開卷考試 講課對象：計算機本科建議教材：《數(shù)據(jù)結(jié)構(gòu)》(C語言版)陳明 編著 清華大學(xué)出版社課程簡介：數(shù)據(jù)結(jié)構(gòu)課程介紹如何組織各種數(shù)據(jù)在計算機中的存儲、傳遞和轉(zhuǎn)換。內(nèi)容包括：數(shù)組、鏈接表、棧和隊列、串、樹與森林、圖、排序、查找、索引與散列結(jié)構(gòu)等。為后續(xù)計算機專業(yè)課程的學(xué)習(xí)打下堅實的基礎(chǔ)。課程內(nèi)容由數(shù)據(jù)結(jié)構(gòu)和算法分析初步兩部分組成。它既有完整的學(xué)科體系和學(xué)科深度，又有較強的實踐性。算法分析強調(diào)最基本的算法設(shè)計技術(shù)和分析方法。經(jīng)過上機實習(xí)和課程設(shè)計的訓(xùn)練，使學(xué)生能夠編制、調(diào)試具有一定難度的中型程序；以培養(yǎng)良好的軟件工程習(xí)慣和面向?qū)ο蟮能浖季S方法。三、理論教學(xué)內(nèi)容的基本要求及學(xué)時分配序論(2學(xué)時)學(xué)習(xí)目標(biāo)：熟悉各類文件的特點，構(gòu)造方法以及如何實現(xiàn)檢索，插入和刪除等操作。知識點：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型、算法及其設(shè)計原則、時間復(fù)雜度、空間復(fù)雜度。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表；(2)熟練掌握這兩類存儲結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲結(jié)構(gòu)上的實現(xiàn)；(3)能夠從時間和空間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合；(4)結(jié)合線性表類型的定義增強對抽象數(shù)據(jù)類型的理解。扎實的指針操作和內(nèi)存動態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求，分清鏈表中指針 p 和結(jié)點 *p 之間的對應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點、頭指針和首元結(jié)點的不同所指以及循環(huán)鏈表、雙向鏈表的特點等。棧和隊列(4學(xué)時)學(xué)習(xí)目標(biāo)：(1)掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點，并能在相應(yīng)的應(yīng)用問題中正確選用它們；(2)熟練掌握棧類型的兩種實現(xiàn)方法；(3)熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法；(4)理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。知識點：順序棧、鏈棧、循環(huán)隊列、鏈隊列。重點和難點：相對于其它各個知識點而言，本章非整個課程的重點，鑒于串已是多數(shù)高級語言中已經(jīng)實現(xiàn)的數(shù)據(jù)類型，因此本章重點僅在于了解串類型定義中各基本操作的定義以及串的實現(xiàn)方法，并學(xué)會利用這些基本操作來實現(xiàn)串的其它操作。知識點：串的類型定義、串的存儲表示、串匹配、KMP算法。重點和難點：本章重點是學(xué)習(xí)數(shù)組類型的定義及其存儲表示。樹和二叉樹(8學(xué)時)學(xué)習(xí)目標(biāo)：(1)領(lǐng)會樹和二叉樹的類型定義，理解樹和二叉樹的結(jié)構(gòu)差別；(2)熟記二叉樹的主要特性，并掌握它們的證明方法；(3)熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作；(4)理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法；(5)熟練掌握二叉樹和樹的各種存儲結(jié)構(gòu)及其建立的算法；(6)學(xué)會編寫實現(xiàn)樹的各種操作的算法；(7)了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。知識點：樹的類型定義、二叉樹的類型定義、二叉樹的存儲表示、二叉樹的遍歷以及其它操作的實現(xiàn)、線索二叉樹、樹和森林的存儲表示、樹和森林的遍歷以及其它操作的實現(xiàn)、最優(yōu)樹和赫夫曼編碼。重點和難點：圖的應(yīng)用極為廣泛，而且圖的各種應(yīng)用問題的算法都比較經(jīng)典，因此本章重點在于理解各種圖的算法及其應(yīng)用場合。查找(6學(xué)時)學(xué)習(xí)目標(biāo)：(1)理解“查找表”的結(jié)構(gòu)特點以及各種表示方法的適用性；(2)熟練掌握以順序表或有序表表示靜態(tài)查找表時的查找方法；(3)熟悉靜態(tài)查找樹的構(gòu)造方法和查找算法，理解靜態(tài)查找樹和折半查找的關(guān)系；(4)熟練掌握二叉查找樹的構(gòu)造和查找方法；(5)理解二叉平衡樹的構(gòu)造過程；(6)熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實質(zhì)性的差別；(7)掌握描述查找過程的判定樹的構(gòu)造方法，以及按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。知識點：順序表、有序表、索引順序表、靜態(tài)查找樹、二叉查找樹、二叉平衡樹、哈希表。排序方法有不同的分類方法，基于“關(guān)鍵字間的比較”進(jìn)行排序的方法可以按排序過程所依據(jù)的不同原則分為插入排序、交換排序、選擇排序、歸并排序和計數(shù)排序等五類；(2)掌握各種排序方法的時間復(fù)雜度的分析方法。按平均時間復(fù)雜度劃分，內(nèi)部排序可分為三類：O(n2)的簡單排序方法，O(n*logn)的高效排序方法和O(d*n)的基數(shù)排序方法；(3)理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。知識點：排序、直接插入排序、折半插入排序、表插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序、堆排序、2路歸并排序、基數(shù)排序、排序方法的綜合比較。重點和難點：本章重點在于了解各種文件的結(jié)構(gòu)特點及其適用場合。四、實驗教學(xué)內(nèi)容的基本要求及學(xué)時分配線性表(1學(xué)時)實驗一 順序表的應(yīng)用 實驗二 鏈表的應(yīng)用要求：理解線性表的定義及其運算；理解順序表和鏈表的定義，組織形式，結(jié)構(gòu)特征和類型說明；掌握在這兩種表上實現(xiàn)的插入，刪除和按值查找的算法；了解循環(huán)鏈表，雙(循環(huán))鏈表的結(jié)構(gòu)特點和在其上施加的插入，刪除等操作。隊列()實驗四 隊列的應(yīng)用要求：理解隊列的定義，特征及在其上所定義的基本運算；掌握在兩種存儲結(jié)構(gòu)上對隊列所施加的基本運算的實現(xiàn)。數(shù)組和廣義表()實驗六 稀疏矩陣的應(yīng)用要求：理解多維數(shù)組的結(jié)構(gòu)特點和在內(nèi)存中的兩種順序存儲方式；理解并掌握矩陣和特殊矩陣元素在存儲區(qū)中地址的計算；領(lǐng)會稀疏矩陣的壓縮方式和簡單運算；了解廣義表的定義和基本運算。深刻理解二叉樹的定義，性質(zhì)及其存儲方法；熟練掌握二叉樹的二叉鏈表存儲方式，結(jié)點結(jié)構(gòu)和類型定義；理解并掌握二叉樹的三種遍歷算法；掌握二叉樹的線索化方法；靈活運用二叉樹的遍歷方法解決相關(guān)的應(yīng)用問題。查找(3學(xué)時)實驗九 順序查找 實驗十 折半查找 實驗十一 哈希表的應(yīng)用 實驗十二 二叉排序樹的綜合練習(xí)要求：了解查找的基本思想及查找成功和不成功的概念；掌握在順序表，有序表，索引表，散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長度；理解并掌握二叉排序樹，平衡二叉樹B樹的各種算法。五、大綱說明課堂講述的論題只是核心或有特色的知識內(nèi)容，還有相當(dāng)數(shù)量的篇章內(nèi)容留給學(xué)生自學(xué)，所確定的自學(xué)部分內(nèi)容亦屬考查范圍。上機訓(xùn)練由平時的上機訓(xùn)練和小學(xué)期的實訓(xùn)課程設(shè)計兩部分組成。本課強調(diào)能力的培養(yǎng)，期末采用半開卷考試(允許同學(xué)攜帶一頁A4紙的總結(jié)資料)。主要參考書：[1]《數(shù)據(jù)結(jié)構(gòu)與算法教程》鄒永林 周蓓 唐曉陽 楊劍勇 編著 機械工業(yè)出版社[2]《數(shù)據(jù)結(jié)構(gòu)(C語言版)》(含CD)嚴(yán)蔚敏 吳為民 編著 清華大學(xué)出版社[3]《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語言版)》嚴(yán)蔚敏 編著 清華大學(xué)出版社[4]《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實訓(xùn)》張世和 編著 清華大學(xué)出版社第二篇：《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計教學(xué)大綱（Data Structures amp。通過這個實驗，培養(yǎng)學(xué)生綜合運用數(shù)據(jù)結(jié)構(gòu)基本知識和程序設(shè)