【正文】 習(xí)要求：了解查找的基本思想及查找成功和不成功的概念；掌握在順序表，有序表，索引表，散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長(zhǎng)度；理解并掌握二叉排序樹，平衡二叉樹B樹的各種算法。主要參考書：[1]《數(shù)據(jù)結(jié)構(gòu)與算法教程》鄒永林 周蓓 唐曉陽(yáng) 楊劍勇 編著 機(jī)械工業(yè)出版社[2]《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》(含CD)嚴(yán)蔚敏 吳為民 編著 清華大學(xué)出版社[3]《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語(yǔ)言版)》嚴(yán)蔚敏 編著 清華大學(xué)出版社[4]《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)》張世和 編著 清華大學(xué)出版社第三篇：《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)教學(xué)大綱（Data Structures amp。、勤奮工作、勇于創(chuàng)新、勇于探索、勇于實(shí)踐，虛心向指導(dǎo)教師請(qǐng)教，向同學(xué)學(xué)習(xí)，獨(dú)立完成設(shè)計(jì)任務(wù)。（鼓勵(lì)學(xué)生創(chuàng)新。隨著計(jì)算機(jī)硬件的發(fā)展，對(duì)計(jì)算機(jī)軟件的發(fā)展也提出了越來(lái)越高的要求。二、教學(xué)重點(diǎn)與難點(diǎn)數(shù)據(jù)結(jié)構(gòu)中基本概念和術(shù)語(yǔ)，算法描述和分析方法。在學(xué)習(xí)C語(yǔ)言這一課程時(shí)，我們逐漸開始了解函數(shù)的調(diào)用的原理，利用子函數(shù)中包含的運(yùn)算規(guī)則，從而實(shí)現(xiàn)函數(shù)的功能。在第三章中，主要講的是鏈?zhǔn)酱鎯?chǔ)特性。而遞歸設(shè)計(jì)出來(lái)的程序，具有結(jié)構(gòu)清晰，可讀性強(qiáng)，便于理解等優(yōu)點(diǎn)。在第七章中，說到了樹的擴(kuò)展二叉樹。生成最小生成樹有Prim算法和Kruskal算法，相對(duì)于這兩種算法，后一種算法要更加易于理解。圖的存儲(chǔ)室通過鄰接矩陣?yán)洗鎯?chǔ)圖的信息。有雙親表示法，孩子表示法，以及孩子兄弟表示法。在對(duì)稱矩陣的壓縮，三角矩陣的壓縮，稀疏矩陣在存儲(chǔ)中能夠合理的進(jìn)行，能大大提高空間的開支。在存儲(chǔ)隊(duì)列之中，數(shù)據(jù)的刪除和存儲(chǔ)分別在表的兩端進(jìn)行操作，所以存儲(chǔ)數(shù)據(jù)很方便。通過這學(xué)期的學(xué)習(xí)，讓我在去年C語(yǔ)言的基礎(chǔ)上對(duì)數(shù)據(jù)與數(shù)據(jù)之間的邏輯關(guān)系有了更深的理解和認(rèn)識(shí)。教學(xué)目的為：了解算法對(duì)于程序設(shè)計(jì)的重要性 ； 學(xué)習(xí)掌握基本數(shù)據(jù)結(jié)構(gòu)的描述與實(shí)現(xiàn)方法，熟練掌握典型數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用算法的設(shè)計(jì)。附錄二開發(fā)步驟、目的； ；； ； 、上機(jī)調(diào)試； 、評(píng)價(jià)。：按照軟件開發(fā)規(guī)范的要求書寫設(shè)計(jì)報(bào)告（參見附錄三報(bào)告書寫格式）；要求報(bào)告層次結(jié)構(gòu)清晰、圖表完整、語(yǔ)言通順、字跡工整。三、基本要求、設(shè)計(jì)、上機(jī)實(shí)現(xiàn)等諸環(huán)節(jié)上投入精力，加強(qiáng)指導(dǎo)、討論和答疑的力度。本課強(qiáng)調(diào)能力的培養(yǎng)，期末采用半開卷考試(允許同學(xué)攜帶一頁(yè)A4紙的總結(jié)資料)。深刻理解二叉樹的定義，性質(zhì)及其存儲(chǔ)方法；熟練掌握二叉樹的二叉鏈表存儲(chǔ)方式，結(jié)點(diǎn)結(jié)構(gòu)和類型定義；理解并掌握二叉樹的三種遍歷算法；掌握二叉樹的線索化方法；靈活運(yùn)用二叉樹的遍歷方法解決相關(guān)的應(yīng)用問題。重點(diǎn)和難點(diǎn)：本章重點(diǎn)在于了解各種文件的結(jié)構(gòu)特點(diǎn)及其適用場(chǎng)合。知識(shí)點(diǎn)：順序表、有序表、索引順序表、靜態(tài)查找樹、二叉查找樹、二叉平衡樹、哈希表。樹和二叉樹(8學(xué)時(shí))學(xué)習(xí)目標(biāo)：(1)領(lǐng)會(huì)樹和二叉樹的類型定義，理解樹和二叉樹的結(jié)構(gòu)差別；(2)熟記二叉樹的主要特性，并掌握它們的證明方法；(3)熟練掌握二叉樹的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作；(4)理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法；(5)熟練掌握二叉樹和樹的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法；(6)學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法；(7)了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。知識(shí)點(diǎn)：順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列。知識(shí)點(diǎn)：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型、算法及其設(shè)計(jì)原則、時(shí)間復(fù)雜度、空間復(fù)雜度。它既有完整的學(xué)科體系和學(xué)科深度，又有較強(qiáng)的實(shí)踐性。嚴(yán)蔚敏，吳偉民：《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》 及《數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）》，清華大學(xué)出版社，2003年第一版。掌握文件和記錄的基本概念以及基本操作。第九章 內(nèi)部排序（一）教學(xué)目的與要求介紹插入排序、交換排序、選擇排序、快速排序、歸并排序、基數(shù)排序的方法及其實(shí)現(xiàn)，快速排序、堆排序、二路歸并排序的方法及其實(shí)現(xiàn)，各種排序方法的穩(wěn)定性、時(shí)間復(fù)雜度和空間復(fù)雜度。哈希表的定義，構(gòu)造哈希函數(shù)的多種方法，以及處理沖突的方法；B樹的定義，查找、插入和刪除元素的方法。最優(yōu)樹和赫夫曼編碼樹和森林遍歷二叉樹和線索二叉樹二叉樹樹的定義和基本術(shù)語(yǔ)第七章 圖（一）教學(xué)目的與要求介紹圖的定義和術(shù)語(yǔ)；圖的存儲(chǔ)結(jié)構(gòu)及深度和廣度優(yōu)先搜索方法及其實(shí)現(xiàn)；圖的生成樹的概念，求圖的最小生成樹的普里姆算法和克魯斯卡爾算法并了解其實(shí)現(xiàn)算法；拓?fù)渑判虻姆椒ú⒘私馄鋵?shí)現(xiàn)算法；計(jì)算關(guān)鍵路徑的方法及其實(shí)現(xiàn)算法。（四）教學(xué)時(shí)數(shù)6學(xué)時(shí)。優(yōu)先級(jí)隊(duì)列 隊(duì)列 棧與遞歸的實(shí)現(xiàn) 棧的應(yīng)用舉例棧第一節(jié)一、串的定義二、串的基本操作第二節(jié)一、定長(zhǎng)順序存儲(chǔ)表示二、堆分配存儲(chǔ)表示三、串的塊鏈存儲(chǔ)表示四、字符串操作的實(shí)現(xiàn)第三節(jié)二、模式匹配的一種改進(jìn)算法（三）教學(xué)方法與形式課堂講授、多媒體課件。教學(xué)難點(diǎn)：遞歸的實(shí)現(xiàn)、循環(huán)隊(duì)列中對(duì)邊界條件的處理。教學(xué)難點(diǎn)：用所學(xué)的基本知識(shí)設(shè)計(jì)有效算法解決與線性表相關(guān)的應(yīng)用問題。教學(xué)重點(diǎn)：有關(guān)數(shù)據(jù)結(jié)構(gòu)的各個(gè)名詞和術(shù)語(yǔ)的含義，以及語(yǔ)句頻度和時(shí)間復(fù)雜度、空間復(fù)雜度的估算。（三）教學(xué)時(shí)數(shù)課堂講授每周4學(xué)時(shí)，18周，共72學(xué)時(shí)。另一方面，本課程的學(xué)習(xí)過程也是進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，要求學(xué)生會(huì)書寫符合軟件工程規(guī)范的文件，編寫的程序代碼應(yīng)結(jié)構(gòu)清晰、正確易讀，能上機(jī)調(diào)試并排除錯(cuò)誤。算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析。教學(xué)重點(diǎn)：在順序表和鏈表上各種基本算法的實(shí)現(xiàn)及相關(guān)的時(shí)間性能分析。教學(xué)重點(diǎn)：棧和隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算。教學(xué)難點(diǎn)：利用串的基本操作來(lái)實(shí)現(xiàn)串的其它操作。第一節(jié) 第二節(jié)一、數(shù)組的存儲(chǔ)方式二、數(shù)組元素存儲(chǔ)位置的計(jì)算三、基本操作的實(shí)現(xiàn)第三節(jié)一、特殊矩陣二、稀疏矩陣第四節(jié)一、廣義表的基本概念二、廣義表的三個(gè)重要結(jié)論第五節(jié)一、頭尾鏈表存儲(chǔ)表示二、擴(kuò)展線性鏈表存儲(chǔ)表示第六節(jié)廣義表的遞歸算法 廣義表的存儲(chǔ)表示 廣義表的定義 矩陣的壓縮存儲(chǔ) 數(shù)組類型 數(shù)組的順序表示和實(shí)現(xiàn)一、求廣義表的深度二、復(fù)制廣義表三、建立廣義表的存儲(chǔ)結(jié)構(gòu)（三）教學(xué)方法與形式課堂講授、多媒體課件。（四）教學(xué)時(shí)數(shù)10學(xué)時(shí)。最短路徑 有向無(wú)環(huán)圖及其應(yīng)用最小生成樹 圖的遍歷 圖的存儲(chǔ)表示 圖的定義和術(shù)語(yǔ)第八章 查找表（一）教學(xué)目的與要求介紹順序表查找和有序表查找的方法及實(shí)現(xiàn)；二叉排序樹和平衡二叉樹的定義、對(duì)二叉排序樹和平衡二叉樹進(jìn)行插入、刪除和查找的方法和實(shí)現(xiàn)。（四）教學(xué)時(shí)數(shù)10學(xué)時(shí)。第十章 文件（一）教學(xué)目的與要求介紹文件和記錄的基本概念以及基本操作。四、教材選用殷人昆，陶永雷，謝若陽(yáng)等：《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語(yǔ)言描述）》，清華大學(xué)出版社。數(shù)據(jù)結(jié)構(gòu)是針對(duì)處理大量非數(shù)值性程序問題而形成的一門學(xué)科，內(nèi)涵豐富、應(yīng)用范圍廣。重點(diǎn)與難點(diǎn)：本章無(wú)。重點(diǎn)與難點(diǎn)：棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，因此本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，以便能在應(yīng)用問題中正確使用。知識(shí)點(diǎn)：數(shù)組的類型定義、數(shù)組的存儲(chǔ)表示、特殊矩陣的壓縮存儲(chǔ)表示方法、隨機(jī)稀疏矩陣的壓縮存儲(chǔ)表示方法。重點(diǎn)和難點(diǎn)：本章重點(diǎn)在于理解查找表的結(jié)構(gòu)特點(diǎn)及其各種表示方法的特點(diǎn)和適用場(chǎng)合。文件(4學(xué)時(shí))學(xué)習(xí)目標(biāo)：熟悉各類文件的特點(diǎn)，構(gòu)造方法以及如何實(shí)現(xiàn)檢索，插入和刪除等操作。樹與二叉樹(4學(xué)時(shí))實(shí)驗(yàn)七 樹與二叉樹的應(yīng)用要求：理解樹的定義，術(shù)語(yǔ)；領(lǐng)會(huì)并掌握樹的各種存儲(chǔ)結(jié)構(gòu)；熟練掌握森林與二叉樹間的相互轉(zhuǎn)換；領(lǐng)會(huì)樹和森林的遍歷；了解樹的簡(jiǎn)單應(yīng)用。課內(nèi)學(xué)時(shí)安排說明：前8周每周4學(xué)時(shí)全為理論課，從第9周開始理論和上機(jī)為1：1，也即2學(xué)時(shí)理論，2學(xué)時(shí)上機(jī)訓(xùn)練。3．使學(xué)生初步具備查閱資料、分析設(shè)計(jì)、上機(jī)實(shí)現(xiàn)和書寫科技 報(bào)告的能力。：第13天，選定題目，明確題目要求、確定數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)算法，并分析算法復(fù)雜度；第48天，編寫程序、調(diào)試程序、測(cè)試程序；第9