《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學(xué)大綱、教學(xué)計劃

《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學(xué)大綱、教學(xué)計劃?課程編號：英文名稱：DataStructureandAlgorithm預(yù)修課程：線性代數(shù)，大學(xué)計算機(jī)基礎(chǔ)，計算機(jī)程序設(shè)計，離散數(shù)學(xué)。學(xué)時安排：64學(xué)時，其中講授40學(xué)時，實踐24學(xué)時。學(xué)

分：4課程性質(zhì)：專業(yè)必修課開課學(xué)期：二年級春01課程性質(zhì)地位《數(shù)據(jù)結(jié)構(gòu)與算法》是計算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工程、物聯(lián)網(wǎng)工程、信息安全、網(wǎng)絡(luò)空間安全、軟件工程、人工智能與大數(shù)據(jù)等專業(yè)的技術(shù)基礎(chǔ)必修課程，是軟件開發(fā)與設(shè)計的基礎(chǔ)，是一門集技術(shù)性、理論性和實踐性于一體的課程。02課程目標(biāo)學(xué)員通過本課程的學(xué)習(xí)，具有用計算機(jī)解決非數(shù)值計算中的數(shù)據(jù)抽象、數(shù)據(jù)結(jié)構(gòu)設(shè)計與算法設(shè)計的能力，對所設(shè)計的算法效率能初步估計。（一）課程知識目標(biāo)本課程的知識目標(biāo)主要包括以下主要的知識單元：數(shù)據(jù)結(jié)構(gòu)概述：包含數(shù)據(jù)結(jié)構(gòu)定義、數(shù)據(jù)結(jié)構(gòu)分類、抽象數(shù)據(jù)類型、算法時、空效率分析；線性結(jié)構(gòu)：包括順序表（線性表向量、棧、隊列）、鏈表（單鏈表、雙鏈表、循環(huán)鏈表、鏈棧、鏈隊列）、順序表與鏈表的應(yīng)用；基本運算：排序算法（插入排序、選擇排序、交換排序、分配排序、歸并排序）、查找算法（順序查找、折半查找、分塊查找、散列查找、字符串的KMP模式匹配）；樹和二叉樹：結(jié)構(gòu)定義、轉(zhuǎn)換方法、存儲方式、遍歷算法，樹型結(jié)構(gòu)應(yīng)用（Huffman最優(yōu)二叉樹與編碼、堆排序、有序樹（二叉排序樹、B樹、B+樹）；圖結(jié)構(gòu)：結(jié)構(gòu)定義、存儲方式、深度優(yōu)先遍歷算法、寬度優(yōu)先遍歷算法；圖結(jié)構(gòu)應(yīng)用：最小代價生成樹、單源最短路徑、最短路徑、拓?fù)渑判?、關(guān)鍵路徑；算法設(shè)計與分析：包括遞歸與分治、回溯法、分支限界法、貪心法、動態(tài)規(guī)劃法。（二）課程能力目標(biāo)本課程要發(fā)展的能力目標(biāo)包括：1、能夠進(jìn)行數(shù)據(jù)抽象、數(shù)據(jù)結(jié)構(gòu)設(shè)計與編程實現(xiàn)。2、能夠運用數(shù)據(jù)結(jié)構(gòu)與算法知識解決計算科學(xué)中的科學(xué)問題。03教學(xué)方法通過課內(nèi)講授，專題研究，案例講解，課外練習(xí)，作業(yè)講解與討論，課內(nèi)實踐一系列環(huán)節(jié)使學(xué)員達(dá)到預(yù)期學(xué)習(xí)目標(biāo)，具體包括課堂講授，互動研討，程序運行、問題講解，答疑輔導(dǎo)等環(huán)節(jié)。本課程推薦主講教員采用兩類教學(xué)方法，一是案例導(dǎo)向法，通過實際問題的已有解決方案，如Josephus問題求解、事件驅(qū)動的銀行模擬、打印緩沖池模擬，啟發(fā)學(xué)員提出問題、分析思路、選用數(shù)據(jù)結(jié)構(gòu)與算法、討論求解算法，將源代碼交給學(xué)員閱讀理解后，對待改進(jìn)的新問題引導(dǎo)學(xué)員修改代碼后實現(xiàn)；二是合作學(xué)習(xí)方法，通過設(shè)置若干研究項目，引導(dǎo)學(xué)員以團(tuán)隊方式參與研究項目，形成問題討論、項目界定、團(tuán)隊組建、項目分析與分解、項目方案實施以及項目答辯等環(huán)節(jié)，鍛煉學(xué)員自主學(xué)習(xí)、團(tuán)隊合作攻關(guān)以及解決現(xiàn)實問題的綜合能力。04課程學(xué)習(xí)目標(biāo)和學(xué)習(xí)實現(xiàn)環(huán)節(jié)（一）知識學(xué)習(xí)目標(biāo)和學(xué)習(xí)實現(xiàn)環(huán)節(jié)本課程的知識學(xué)習(xí)目標(biāo)與相應(yīng)實現(xiàn)環(huán)節(jié)采用表格方式進(jìn)行描述，如下表1所示。（二）課程的學(xué)習(xí)目標(biāo)對畢業(yè)標(biāo)準(zhǔn)和培養(yǎng)標(biāo)準(zhǔn)中知識-能力-素質(zhì)相關(guān)學(xué)習(xí)結(jié)果的貢獻(xiàn)及程度等級用表格方式描述，如下表2。05課程學(xué)習(xí)內(nèi)容與時間節(jié)點按照章節(jié)說明本課程的內(nèi)容要點及課內(nèi)學(xué)時數(shù)，其中章節(jié)為順序編號。如下表3所示。06課程綜合計分方法（一）考核結(jié)構(gòu)設(shè)計與各教學(xué)環(huán)節(jié)比例分配考核方式：考試與考查相結(jié)合組織方式：筆試/現(xiàn)場測試，筆試部分采用閉卷形式成績評定：百分制記分標(biāo)準(zhǔn)：考試占80％，實驗占10％，作業(yè)占10%（二）評分標(biāo)準(zhǔn)1、作業(yè)采用百分制進(jìn)行評分，最后綜合評分進(jìn)行相應(yīng)比例折算。評分標(biāo)準(zhǔn)如下表4所示。2、實驗采用百分制進(jìn)行評分，最后綜合評分進(jìn)行相應(yīng)比例折算。評分標(biāo)準(zhǔn)如下表5所示。3、三級項目：無4、實習(xí)：無5、期末考試：隨考試試卷制定評分標(biāo)準(zhǔn)。6、其它：如考勤、測驗、課堂互動表現(xiàn)等07教材及推薦參考書（一）教材《數(shù)據(jù)結(jié)構(gòu)與算法（第2版）》，熊岳山著，清華大學(xué)出版社，2016.04（二）推薦參考書（1）《數(shù)據(jù)結(jié)構(gòu)》（第二版），嚴(yán)尉敏等編，清華大學(xué)出版社，1992.（2）《AlgorithmDesign》，JonKleinberg,EvaTardos著，清華大學(xué)出版社，2012.12（3）《IntroductiontoAlgorithm》，CormenGH,LeisersenCE,RivestRL,SteinC.2nded.New

York:McGraw-Hill,2001.（4）《DataStructureswithC++》，WilliamFord&WilliamTopp,PrenticeHall,1996.（5）《DataStructures,Algorithms,andApplicationsinC++》，SartajSahni,WCBMcGraw-Hill,1998.?《數(shù)據(jù)結(jié)構(gòu)與算法》課程簡介?課程編號：170210025課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法（DataStructureandAlgorithm）學(xué)時安排：64學(xué)時，其中講授40學(xué)時，實踐24學(xué)時。預(yù)修課程：線性代數(shù)，大學(xué)計算機(jī)基礎(chǔ)，計算機(jī)程序設(shè)計，離散數(shù)學(xué)。內(nèi)容簡介：《數(shù)據(jù)結(jié)構(gòu)與算法》是計算機(jī)學(xué)院本科學(xué)員計算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工程、人工智能與大數(shù)據(jù)等專業(yè)的學(xué)科基礎(chǔ)必修課程，是計算機(jī)程序設(shè)計的基礎(chǔ)。計算機(jī)科學(xué)各領(lǐng)域都要用到各種數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計與分析技術(shù)。學(xué)員通過本課程的學(xué)習(xí)，具有用計算機(jī)解決非數(shù)值計算中的數(shù)據(jù)抽象、數(shù)據(jù)結(jié)構(gòu)設(shè)計與算法設(shè)計的能力，對所設(shè)計的算法效率能初步估計。課程涉及抽象數(shù)據(jù)類型、基本數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計與分析方法以及如何用C++（或C）來描述抽象數(shù)據(jù)類型，使學(xué)員能針對實際問題設(shè)計適合于計算機(jī)求解的數(shù)據(jù)結(jié)構(gòu)和算法。課程內(nèi)容包括：基本數(shù)據(jù)類型、抽象數(shù)據(jù)類型、順序表、鏈表、串、樹和二叉樹、圖、貪心法、動態(tài)規(guī)劃、遞歸與分治、回溯法和分支限界法等。?《數(shù)據(jù)結(jié)構(gòu)與算法》實驗教學(xué)大綱?課程編號：170210025課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法總學(xué)時：64學(xué)時實驗學(xué)時：24學(xué)時實驗地點：3號院教室或307實驗樓01任務(wù)背景與目標(biāo)（一）任務(wù)背景描述數(shù)據(jù)結(jié)構(gòu)與算法是軟件設(shè)計與維護(hù)的基礎(chǔ)，抽象數(shù)據(jù)類型，基本數(shù)據(jù)結(jié)構(gòu)：棧、隊列、二叉樹、樹和圖等的學(xué)習(xí)和理解不能只停留在概念層，應(yīng)通過課程上機(jī)編程實踐來加深理解。學(xué)生在學(xué)完C++語言和數(shù)據(jù)結(jié)構(gòu)與算法相關(guān)知識點后已具備完成數(shù)據(jù)結(jié)構(gòu)上機(jī)作業(yè)的基本條件。通過課程實驗，使學(xué)生熟練掌握數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)，培養(yǎng)學(xué)生非數(shù)值問題的數(shù)據(jù)結(jié)構(gòu)抽象與上機(jī)編程實現(xiàn)的能力。要求學(xué)生獨立完成本課程實驗規(guī)定的上機(jī)作業(yè)題，按要求完成好上機(jī)報告。（二）技術(shù)目標(biāo)一是使用熟悉的C++軟件開發(fā)工具進(jìn)行編程；二是應(yīng)用熟悉的編程語言C++編寫數(shù)據(jù)結(jié)構(gòu)及算法；三是使用運用數(shù)據(jù)結(jié)構(gòu)與算法編程解決實際問題，簡單分析算法效率，以驗證課堂所學(xué)知識。（三）能力目標(biāo)培養(yǎng)學(xué)員分析和解決現(xiàn)實問題的能力，包括三個方面：一是實際問題求解的數(shù)據(jù)抽象的能力；二是數(shù)據(jù)結(jié)構(gòu)設(shè)計與編程實現(xiàn)能力；三是算法設(shè)計與分析能力。02主要內(nèi)容與基本要求實驗1

線性表、鏈表的應(yīng)用1．實驗?zāi)康呐c任務(wù)實驗?zāi)康模和ㄟ^本實驗，使學(xué)員熟悉線性表的順序存儲與循環(huán)報數(shù)的實現(xiàn)算法。實驗任務(wù)：使用抽象數(shù)據(jù)類型向量解決中國式的擊鼓傳花問題。2．訓(xùn)練的能力點訓(xùn)練學(xué)員運用所學(xué)的向量類的知識來編程解決實際問題的能力點。3．實驗原理用C++語言編程實現(xiàn)classVector，調(diào)用Vector中的取出、刪除、插入等運算功能，增加循環(huán)報數(shù)的實現(xiàn)。4．實驗內(nèi)容及要求實驗內(nèi)容：創(chuàng)建Vector類并設(shè)計算法編程模擬實現(xiàn)中國式的擊鼓傳花游戲。實驗要求：（1）描述數(shù)據(jù)抽象過程及使用的數(shù)據(jù)結(jié)構(gòu)；（2）編程實現(xiàn)中國式的擊鼓傳花游戲。5．實驗結(jié)果及要求對實驗結(jié)果進(jìn)行分析。實驗2

排序、查找算法的實現(xiàn)1．實驗?zāi)康呐c任務(wù)實驗?zāi)康模和ㄟ^本實驗，使學(xué)員熟悉排序、查找算法使用的數(shù)據(jù)結(jié)構(gòu)及算法思想。實驗任務(wù)：使用C++編程實現(xiàn)分塊查找算法。2．訓(xùn)練的能力點訓(xùn)練學(xué)員運用所學(xué)的數(shù)據(jù)結(jié)構(gòu)和算法思想解決排序、查找需求的能力點。3．實驗原理用C++語言編程實現(xiàn)。4．實驗內(nèi)容及要求實驗內(nèi)容：分別編程實現(xiàn)分塊查找算法。實驗要求：針對給定線性表的測試數(shù)據(jù)調(diào)試運行算法。5．實驗結(jié)果及要求對實驗結(jié)果進(jìn)行分析。實驗3樹和二叉樹的應(yīng)用1．實驗?zāi)康呐c任務(wù)通過本實驗使學(xué)員了解和掌握編寫基于二叉樹的雙鏈存儲結(jié)構(gòu)上的算法。2.訓(xùn)練的能力點訓(xùn)練學(xué)員運用所學(xué)的樹狀結(jié)構(gòu)進(jìn)行編程應(yīng)用的能力點。3．實驗原理

選用數(shù)據(jù)結(jié)構(gòu)、設(shè)計相應(yīng)算法，用C++語言編程實現(xiàn)。4．實驗內(nèi)容及要求假設(shè)用二叉樹的LeftChild-RightChild表示法存儲二叉樹，每個結(jié)點所含數(shù)據(jù)元素均為單字母，試編程實現(xiàn)按樹狀打印二叉樹的算法。例如：圖1的二叉樹打印為右邊的形狀?！?/p>

圖1二叉樹結(jié)點的樹狀輸出方式5．實驗結(jié)果及要求對實驗結(jié)果進(jìn)行分析。實驗4圖的應(yīng)用1．實驗?zāi)康呐c任務(wù)通過本實驗使學(xué)員了解和掌握編寫圖結(jié)構(gòu)的應(yīng)用程序。任務(wù)就是編程實現(xiàn)基于圖的第一、第二和第三最短路徑。2.訓(xùn)練的能力點訓(xùn)練學(xué)員運用所學(xué)的圖結(jié)構(gòu)開發(fā)圖應(yīng)用的能力點。3．實驗原理選用圖的存儲結(jié)構(gòu)、設(shè)計算法，用C++語言編程實現(xiàn)。4．實驗內(nèi)容及要求在網(wǎng)絡(luò)通信中，經(jīng)常需要求最短路徑。但完全采用最短路徑傳輸有這樣一個問題：如果最終在兩個終端節(jié)點之間給出的最短路徑只有一條，則在該路徑中的任一個節(jié)點或鏈路出現(xiàn)故障時，信號傳輸將面臨中斷的危險。因此，對網(wǎng)絡(luò)路由選擇作了以下改進(jìn)：為任意兩節(jié)點之間通信提供三條路徑供其選擇，即第一最短路徑、第二最短路徑、和第三最短路徑。

第一最短路徑的定義為：給定一個不含負(fù)回路的網(wǎng)絡(luò)D=（V，E，W），其中V={v1,v2,…vn},E為邊集合，W為權(quán)集合，設(shè)P1是D中最短(v1，v2)路。稱P1是D中第一最短(v1，v2)路徑。第二最短路徑的定義為：如果D中有一條(v1,v2)路，P2滿足以下條件：

（1）P2

≠P1

（2）D中不存在異于P1的路P，使得

（3）W（P1）≤W（P)＜w(p2)則稱P2為D中第二最短(v1,v2)路徑。第三最短路徑的定義為：設(shè)P2是D中第二最短(v1,v2)路徑,如果D中有一條(v1,v2)路P3滿足以下條件：

（1）P3≠P2

（2）D中不存在異于P1，P2的路P，使得

（3）W（P2）≤W（P)＜w(p3)則稱P3為D中第三最短(v1,v2)路徑。

給定一條有n個節(jié)點的網(wǎng)絡(luò)，，求給定兩點間的第一、第二和第三最短路徑。用相鄰矩陣表示網(wǎng)絡(luò)。例如，含有n=5的網(wǎng)絡(luò)的相鄰矩陣為：則第一、第二、第三(v1,v5)最短路徑為4（1，2，3，4，5）5（1，3，4，5）6（1，2，3，5）5．實驗結(jié)果及要求至少給出四組測試結(jié)果能正確求出帶權(quán)網(wǎng)絡(luò)中給定兩點間的第一、第二和第三最短路徑。實驗5

算法設(shè)計與分析應(yīng)用1．實驗?zāi)康呐c任務(wù)實驗?zāi)康模和ㄟ^本實驗，使學(xué)員熟悉用算法設(shè)計策略設(shè)計與分析算法，并編程實現(xiàn)。實驗任務(wù)：設(shè)計算法，用C語言（或C++）編程實現(xiàn)。2．訓(xùn)練的能力點訓(xùn)練學(xué)員使用C語言（或C++）驗證課堂上學(xué)過的算法設(shè)計策略的能力點。3．實驗原理設(shè)計算法，用C語言（或C++）編程實現(xiàn)。4．實驗內(nèi)容及要求實驗內(nèi)容：使用算法設(shè)計策略設(shè)計算法，解決實際問題。實驗要求：分別選用1種學(xué)過的算法設(shè)計策略（貪心法、動態(tài)規(guī)劃、遞歸與分治、回溯法和分支限界法），編程實現(xiàn)0-1背包問題或旅行商問題或流水作業(yè)調(diào)度問題。5．實驗結(jié)果及要求對給定的數(shù)據(jù)集測試程序，實驗結(jié)果進(jìn)行分析。03實施安排04考核與評價（一）考核形式與要求考核方式：考查組織方式：現(xiàn)場測試成績評定：百分制（二）評分標(biāo)準(zhǔn)評分標(biāo)準(zhǔn)見表5。05實驗教材或指導(dǎo)書《數(shù)據(jù)結(jié)構(gòu)與算法（第2版）》，熊岳山著，清華大學(xué)出版社，2016.04參考書籍《數(shù)據(jù)結(jié)構(gòu)與算法(第3版)》ISBN：9787302643463作者：熊岳山定價：59元內(nèi)容簡介“數(shù)據(jù)結(jié)構(gòu)與算法”是計算機(jī)科學(xué)與技術(shù)、軟件工程等相關(guān)專業(yè)的重要基礎(chǔ)課，是這些專業(yè)的核心課程之一，是一門集技術(shù)性、理論性和實踐性于一體的課程。本書內(nèi)容包括基本數(shù)據(jù)類型、抽象數(shù)據(jù)類型、線性表、鏈表、串、樹和二叉樹、圖、遞歸與分治算法、貪心算法、分支限界法和動態(tài)規(guī)劃法等內(nèi)容；并重點介紹抽象數(shù)據(jù)類型、基本數(shù)據(jù)結(jié)構(gòu)、C語言數(shù)據(jù)結(jié)構(gòu)描述、數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法設(shè)計與分析以及算法性能評價等內(nèi)容，目的是讓讀者理解數(shù)據(jù)抽象與編程實現(xiàn)的關(guān)系，提高用計算機(jī)解決實際問題的能力。本書結(jié)構(gòu)合理，內(nèi)容豐富，算法描述清晰，用C語言編寫的算法代碼都已調(diào)試通過，便于自學(xué)，可作為高等院校計算機(jī)科學(xué)與技術(shù)專業(yè)、軍事院校的基礎(chǔ)合訓(xùn)專業(yè)和其他相關(guān)專業(yè)的教材和參考書，也可供從事計算機(jī)軟件開發(fā)的科技工作者參考。第1章數(shù)據(jù)結(jié)構(gòu)概述11.1基本概念11.1.1數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象11.1.2數(shù)據(jù)結(jié)構(gòu)21.2數(shù)據(jù)結(jié)構(gòu)的分類31.3數(shù)據(jù)類型51.3.1基本類型和組合類型51.3.2抽象數(shù)據(jù)類型51.4算法和算法分析81.4.1算法概念81.4.2算法分析9習(xí)題11第2章向量、棧和隊列132.1線性表132.1.1線性表的抽象數(shù)據(jù)類型132.1.2線性表的結(jié)構(gòu)表示152.2向量182.2.1向量的抽象數(shù)據(jù)類型182.2.2向量的插入和刪除202.2.3向量的應(yīng)用222.3棧252.3.1棧的抽象數(shù)據(jù)類型及其實現(xiàn)252.3.2棧的應(yīng)用272.4遞歸效率分析342.4.1遞歸方程求解342.4.2生成函數(shù)求解遞歸方程352.4.3特征方程求解遞歸方程362.4.4遞歸樹方法372.5隊列382.5.1隊列的抽象數(shù)據(jù)類型及其實現(xiàn)392.5.2隊列的應(yīng)用——模擬銀行活動44習(xí)題51第3章鏈表533.1單鏈表533.1.1基本概念533.1.2單鏈表結(jié)點結(jié)構(gòu)543.1.3單鏈表結(jié)構(gòu)563.1.4棧的單鏈表實現(xiàn)653.1.5隊列的單鏈表實現(xiàn)663.1.6單鏈表的應(yīng)用舉例703.2循環(huán)鏈表743.3雙鏈表76習(xí)題78第4章串814.1基本概念814.2串的存儲824.3串結(jié)構(gòu)和串的運算834.4模式匹配854.4.1樸素的模式匹配算法854.4.2KMP匹配算法864.4.3BM匹配算法89習(xí)題91第5章排序935.1基本概念935.2插入排序945.2.1直接插入排序945.2.2折半插入排序955.2.3Shell排序975.3選擇排序995.3.1直接選擇排序995.3.2樹形選擇排序1005.4交換排序1015.4.1起泡排序1015.4.2快速排序1035.5分配排序1065.5.1基本思想1065.5.2基數(shù)排序1075.6歸并排序1105.7外部排序1135.7.1二路合并排序1135.7.2多路替代選擇合并排序1145.7.3最佳合并排序114習(xí)題116第6章查找1176.1基本概念1176.2順序查找1176.3折半查找1196.4分塊查找1216.5散列查找1236.5.1概述1236.5.2散列函數(shù)1246.5.3沖突的處理1266.5.4散列查找的效率129習(xí)題130第7章樹和二叉樹1327.1樹的概念1327.2二叉樹1337.2.1二叉樹的概念1337.2.2二叉樹的性質(zhì)1337.2.3二叉樹的存儲方式1367.2.4樹(樹林)與二叉樹的相互轉(zhuǎn)換1387.3樹(樹林)、二叉樹的遍歷1397.3.1樹(樹林)的遍歷1397.3.2二叉樹的遍歷1397.4抽象數(shù)據(jù)類型BinaryTree以及BinaryTree結(jié)構(gòu)1407.4.1抽象數(shù)據(jù)類型BinaryTree1407.4.2一個完整的包含構(gòu)建二叉樹與遍歷實現(xiàn)的例子1427.5二叉樹的遍歷算法1437.5.1非遞歸(使用棧)的遍歷算法1437.5.2線索化二叉樹的遍歷145習(xí)題148第8章樹結(jié)構(gòu)的應(yīng)用1508.1二叉排序樹1508.1.1二叉排序樹與BinarySTree結(jié)構(gòu)1508.1.2二叉排序樹的檢索、插入、刪除運算1518.1.3等概率查找對應(yīng)的最佳二叉排序樹1548.2平衡的二叉排序樹1578.2.1平衡二叉排序樹的定義1578.2.2平衡二叉排序樹的插入、刪除1578.2.3AVL樹高度1618.3B-樹、B+-樹1618.4鍵樹和2-3樹1658.4.1鍵樹1658.4.22-3樹1678.5Huffman最優(yōu)樹與樹編碼1688.5.1Huffman最優(yōu)樹1688.5.2樹編碼1718.6堆排序1738.7判定樹1788.8等價類和并查集1798.8.1等價類1798.8.2并查集1808.9紅黑樹1828.10跳表1868.10.1跳表時間復(fù)雜度分析1878.10.2跳表的空間復(fù)雜度分析1878.10.3高效的動態(tài)插入和刪除1888.10.4小結(jié)189習(xí)題189第9章圖1919.1基本概念1919.2圖的存儲表示1939.2.1相鄰矩陣表示圖1939.2.2圖的鄰接表表示1949.2.3鄰接多重表1959.3基于鄰接表表示的Graph結(jié)構(gòu)1979.4圖的遍歷1979.4.1深度優(yōu)先遍歷1989.4.2廣度優(yōu)先遍歷2009.5最小代價生成樹2019.6單源最短路徑問題2059.7每一對頂點間的最短路徑問題2089.8有向無回路圖2099.8.1DAG圖和AOV、AOE網(wǎng)2099.8.2AOV網(wǎng)的拓?fù)渑判?119.8.3AOE網(wǎng)的關(guān)鍵路徑213習(xí)題215第10章算法設(shè)計與分析21710.1遞歸與分治21710.1.1遞歸方法設(shè)計21710.1.2分治法21810.2回溯法22010.3分支限界法22510.4貪心算法23110.5動態(tài)規(guī)劃法23210.6數(shù)據(jù)結(jié)構(gòu)中的Catalan數(shù)23510.6.1問題描述23510.6.2問題解析23510.6.3遞歸方程求解236習(xí)題237關(guān)鍵詞索引239參考文獻(xiàn)242第1章數(shù)據(jù)結(jié)構(gòu)概述11.1基本概念11.1.1數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象11.1.2數(shù)據(jù)結(jié)構(gòu)21.2數(shù)據(jù)結(jié)構(gòu)的分類31.3數(shù)據(jù)類型51.3.1基本類型、組合類型51.3.2抽象數(shù)據(jù)類型51.4算法和算法分析81.4.1算法概念81.4.2算法分析9習(xí)題11第2章向量、棧和隊列132.1線性表132.1.1線性表的抽象數(shù)據(jù)類型132.1.2線性表的結(jié)構(gòu)表示152.2向量182.2.1向量的抽象數(shù)據(jù)類型182.2.2向量的插入和刪除202.2.3向量的應(yīng)用232.3棧262.3.1棧的抽象數(shù)據(jù)類型及其實現(xiàn)262.3.2棧的應(yīng)用292.4遞歸效率分析362.4.1遞歸方程求解362.4.2生成函數(shù)求解遞歸方程372.4.3特征方程求解遞歸方程382.4.4遞歸樹方法392.5隊列402.5.1隊列的抽象數(shù)據(jù)類型及其實現(xiàn)402.5.2隊列的應(yīng)用——模擬銀行活動46習(xí)題54第3章鏈表563.1單鏈表563.1.1基本概念563.1.2單鏈表結(jié)點結(jié)構(gòu)573.1.3單鏈表結(jié)構(gòu)593.1.4棧的單鏈表實現(xiàn)703.1.5隊列的單鏈表實現(xiàn)713.1.6單鏈表的應(yīng)用舉例753.2循環(huán)鏈表803.3雙鏈表82習(xí)題84第4章串874.1基本概念874.2串的存儲884.3串結(jié)構(gòu)和串的運算894.4模式匹配914.4.1樸素的模式匹配算法914.4.2KMP匹配算法924.4.3BM匹配算法95習(xí)題98第5章排序995.1基本概念995.2插入排序1005.2.1直接插入排序1005.2.2折半插入排序1025.2.3Shell排序1045.3選擇排序1055.3.1直接選擇排序1055.3.2樹形選擇排序1075.4交換排序1085.4.1起泡排序1085.4.2快速排序1095.5分配排序1135.5.1基本思想1135.5.2基數(shù)排序1145.6歸并排序1175.7外部排序1205.7.1二路合并排序1205.7.2多路替代選擇合并排序1215.7.3最佳合并排序122習(xí)題123第6章查找1256.1基本概念1256.2順序查找1256.3折半查找1276.4分塊查找1296.5散列查找1316.5.1概述1316.5.2散列函數(shù)1326.5.3沖突的處理1346.5.4散列查找的效率137習(xí)題138第7章樹和二叉樹1407.1樹的概念1407.2二叉樹1417.2.1二叉樹的概念1417.2.2二叉樹的性質(zhì)1417.2.3二叉樹的存儲方式1447.2.4樹(樹林)與二叉樹的相互轉(zhuǎn)換1467.3樹(樹林)、二叉樹的遍歷1477.3.1樹(樹林)的遍歷1477.3.2二叉樹的遍歷1477.4抽象數(shù)據(jù)類型BinaryTree以及BinaryTree結(jié)構(gòu)1487.4.1抽象數(shù)據(jù)類型BinaryTree1487.4.2一個完整的包含構(gòu)建二叉樹與遍歷實現(xiàn)的例子1507.5二叉樹的遍歷算法1517.5.1非遞歸(使用棧)的遍歷算法1517.5.2線索化二叉樹的遍歷153習(xí)題157第8章樹狀結(jié)構(gòu)的應(yīng)用1598.1二叉排序樹1598.1.1二叉排序樹與BinarySTree結(jié)構(gòu)1598.1.2二叉排序樹的檢索、插入、刪除運算1608.1.3等概率查找對應(yīng)的最佳二叉排序樹1648.2平衡的二叉排序樹1668.2.1平衡二叉排序樹的定義1668.2.2平衡二叉排序樹的插入、刪除1678.2.3AVL樹高度1708.3B-樹、B+-樹1718.4鍵樹和2-3樹1758.4.1鍵樹1758.4.22-3樹1778.5Huffman最優(yōu)樹與樹編碼1788.5.1Huffman最優(yōu)樹1788.5.2樹編碼1818.6堆排序1838.7判定樹1898.8等價類和并查集1908.8.1等價類1908.8.2并查集1908.9紅黑樹1938.10跳表1978.10.1跳表時間復(fù)雜度分析1988.10.2跳表的空間復(fù)雜度分析1988.10.3高效的動態(tài)插入和刪除1998.10.4小結(jié)200習(xí)題201第9章圖2039.1基本概念2039.2圖的存儲表示2059.2.1相鄰矩陣表示圖2059.2.2圖的鄰接表表示2069.2.3鄰接多重表2079.3基于鄰接表表示的Graph結(jié)構(gòu)2099.4圖的遍歷2109.4.1深度優(yōu)先遍歷2109.4.2廣度優(yōu)先遍歷2129.5最小代價生成樹2139.6單源最短路徑問題2179.7每一對頂點間的最短路徑問題2209.8有向無回路圖2229.8.1DAG圖和AOV、AOE網(wǎng)2229.8.2AOV網(wǎng)的拓?fù)渑判?249.8.3AOE網(wǎng)的關(guān)鍵路徑226習(xí)題228第10章算法設(shè)計與分析23010.1遞歸與分治23010.1.1遞歸方法設(shè)計23010.1.2分治法23110.2回溯法23310.3分支限界法23810.4貪心算法24510.5動態(tài)規(guī)劃法24610.6數(shù)據(jù)結(jié)構(gòu)中的Catalan數(shù)24910.6.1問題描述24910.6.2問題解析24910.6.3遞歸方程求解251習(xí)題252關(guān)鍵詞索引254參考文獻(xiàn)257第1章數(shù)據(jù)結(jié)構(gòu)概述/11.1基本概念/11.1.1數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象/11.1.2數(shù)據(jù)結(jié)構(gòu)/21.2數(shù)據(jù)結(jié)構(gòu)的分類/31.3數(shù)據(jù)類型/51.3.1基本類型、組合類型/51.3.2抽象數(shù)據(jù)類型/51.4算法和算法分析/81.4.1算法概念/81.4.2算法分析/9習(xí)題/11第2章向量、棧和隊列/132.1線性表/132.1.1線性表的抽象數(shù)據(jù)類型/132.1.2線性表的結(jié)構(gòu)表示/152.2向量/182.2.1向量的抽象數(shù)據(jù)類型/182.2.2向量的插入和刪除/202.2.3向量的應(yīng)用/232.3棧/262.3.1棧的抽象數(shù)據(jù)類型及其實現(xiàn)/262.3.2棧的應(yīng)用/292.4遞歸效率分析/362.4.1遞歸方程求解/362.4.2生成函數(shù)求解遞歸方程/372.4.3特征方程求解遞歸方程/382.4.4遞歸樹方法/392.5隊列/402.5.1隊列的抽象數(shù)據(jù)類型及其實現(xiàn)/402.5.2隊列的應(yīng)用——模擬銀行活動/46習(xí)題/54第3章鏈表/563.1單鏈表/563.1.1基本概念/563.1.2單鏈表結(jié)點結(jié)構(gòu)/573.1.3單鏈表結(jié)構(gòu)/593.1.4棧的單鏈表實現(xiàn)/703.1.5隊列的單鏈表實現(xiàn)/713.1.6單鏈表的應(yīng)用舉例/753.2循環(huán)鏈表/803.3雙鏈表/82習(xí)題/84第4章串/874.1基本概念/874.2串的存儲/884.3串結(jié)構(gòu)和串的運算/894.4模式匹配/914.4.1樸素的模式匹配算法/914.4.2KMP匹配算法/924.4.3BM匹配算法/95習(xí)題/98第5章排序/995.1基本概念/995.2插入排序/1005.2.1直接插入排序/1005.2.2折半插入排序/1025.2.3Shell排序/1045.3選擇排序/1055.3.1直接選擇排序/1055.3.2樹形選擇排序/1075.4交換排序/1085.4.1起泡排序/1085.4.2快速排序/1095.5分配排序/1135.5.1基本思想/1135.5.2基數(shù)排序/1145.6歸并排序/1175.7外部排序/1205.7.1二路合并排序/1205.7.2多路替代選擇合并排序/1215.7.3最佳合并排序/122習(xí)題/123第6章查找/1256.1基本概念/1256.2順序查找/1256.3折半查找/1276.4分塊查找/1296.5散列查找/1316.5.1概述/1316.5.2散列函數(shù)/1326.5.3沖突的處理/1346.5.4散列查找的效率/137習(xí)題/138第7章樹和二叉樹/1407.1樹的概念/1407.2二叉樹/1417.2.1二叉樹的概念/1417.2.2二叉樹的性質(zhì)/1417.2.3二叉樹的存儲方式/1447.2.4樹(樹林)與二叉樹的相互轉(zhuǎn)換/1467.3樹(樹林)、二叉樹的遍歷/1477.3.1樹(樹林)的遍歷/1477.3.2二叉樹的遍歷/1477.4抽象數(shù)據(jù)類型BinaryTree以及BinaryTree結(jié)構(gòu)/1487.4.1抽象數(shù)據(jù)類型BinaryTree/1487.4.2一個完整的包含構(gòu)建二叉樹與遍歷實現(xiàn)的例子/1507.5二叉樹的遍歷算法/1517.5.1非遞歸(使用棧)的遍歷算法/1517.5.2線索化二叉樹的遍歷/153習(xí)題/157第8章樹狀結(jié)構(gòu)的應(yīng)用/1598.1二叉排序樹/1598.1.1二叉排序樹與BinarySTree結(jié)構(gòu)/1598.1.2二叉排序樹的檢索、插入、刪除運算/1608.1.3等概率查找對應(yīng)的最佳二叉排序樹/1648.2平衡的二叉排序樹/1668.2.1平衡二叉排序樹的定義/1668.2.2平衡二叉排序樹的插入、刪除/1678.2.3AVL樹高度/1708.3B-樹、B+-樹/1718.4鍵樹和2-3樹/1758.4.1鍵樹/1758.4.22-3樹/1768.5Huffman最優(yōu)樹與樹編碼/1788.5.1Huffman最優(yōu)樹/1788.5.2樹編碼/1818.6堆排序/1838.7判定樹/1898.8等價類和并查集/1908.8.1等價類/1908.8.2并查集/1908.9紅黑樹/193習(xí)題/197第9章圖/1999.1基本概念/1999.2圖的存儲表示/2019.2.1相鄰矩陣表示圖/2019.2.2圖的鄰接表表示/2029.2.3鄰接多重表/2039.3基于鄰接表表示的Graph結(jié)構(gòu)/2059.4圖的遍歷/2069.4.1深度優(yōu)先遍歷/2069.4.2廣度優(yōu)先遍歷/2089.5最小代價生成樹/2099.6單源最短路徑問題/2139.7每一對頂點間的最短路徑問題/2169.8有向無回路圖/2189.8.1DAG圖和AOV、AOE網(wǎng)/2189.8.2AOV網(wǎng)的拓?fù)渑判?2209.8.3AOE網(wǎng)的關(guān)鍵路徑/222習(xí)題/224第10章算法設(shè)計與分析/22610.1遞歸與分治/22610.1.1遞歸方法設(shè)計/22610.1.2分治法/22710.2回溯法/22910.3分支限界法/23410.4貪心算法/24110.5動態(tài)規(guī)劃法/242習(xí)題/245圖目錄/247算法目錄/252關(guān)鍵詞索引/247參考文獻(xiàn)/250圖目錄圖1.1基本的邏輯結(jié)構(gòu)3圖1.2基本存儲方法4圖1.3游泳池及環(huán)形過道8圖2.1向量的順序存儲19圖2.2順序存儲的棧26圖2.3中綴表達(dá)式的計值過程30圖2.4后綴表達(dá)式的計值30圖2.5中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的過程31圖2.6漢諾塔問題的遞歸求解過程33圖2.7活動記錄的進(jìn)棧情況35圖2.8活動記錄的退棧情況36圖2.9式(2.1)的遞歸樹39圖2.10式(2.2)的遞歸樹40圖2.11順序存儲的隊列40圖2.12隊列的操作41圖2.13循環(huán)隊列的隊空和隊滿41圖3.1單鏈表56圖3.2從鏈表中刪除一個結(jié)點56圖3.3往鏈表中插入一個結(jié)點56圖3.4附加頭結(jié)點的單鏈表57圖3.5一個實際的單鏈表結(jié)構(gòu)65圖3.6空的循環(huán)鏈表80圖3.7雙鏈表結(jié)點82圖3.8雙鏈表82圖3.9往雙鏈表中插入一個結(jié)點82圖3.10從雙鏈表中刪除一個結(jié)點82圖3.11題3.2用圖85圖4.1串的順序存儲88圖4.2串的緊縮順序存儲88圖4.3串的鏈接存儲89圖4.4第1趟比較91圖4.5第2趟比較92圖4.6樸素的模式匹配算法執(zhí)行過程92圖4.7模式P="abcabcd"的next數(shù)組的計算過程95圖4.8基于KMP匹配算法的模式匹配過程96圖5.1直接插入排序的過程100圖5.2折半查找過程102圖5.3Shell排序過程104圖5.4直接選擇排序106圖5.5第一次樹形選擇排序選出最小排序碼13107圖5.6第二次樹形選擇排序選出最小排序碼14107圖5.7起泡排序過程108圖5.8第1趟快速排序的比較過程110圖5.9基數(shù)排序的分配和收集過程115圖5.10二路歸并過程118圖5.11二路歸并排序示意121圖5.12實現(xiàn)五路合并敗者樹122圖5.13實現(xiàn)五路合并一次替代選擇后的敗者樹122圖5.14順序合并的三路合并樹122圖5.15三路最佳合并樹123圖6.1折半查找過程128圖6.2分塊查找過程130圖6.3用分離的同義詞子表解決沖突137圖6.4用結(jié)合的同義詞子表解決沖突137圖6.5幾種不同的解決碰撞方法時的平均檢索長度（橫坐標(biāo)為負(fù)載因子的取值）138圖6.6題6.8用圖139圖7.1家族樹140圖7.2二叉樹的五種基本形態(tài)141圖7.3表達(dá)式二叉樹142圖7.4深度為3的滿二叉樹142圖7.5特殊的二叉樹143圖7.6i與i+1在同一層的完全二叉樹143圖7.7i與i+1不在同一層的完全二叉樹143圖7.8完全二叉樹的順序存儲144圖7.9非完全二叉樹的順序存儲144圖7.10二叉樹的LeftChild-RightChild表示145圖7.11樹(樹林)與二叉樹之間相互轉(zhuǎn)換146圖7.12樹林的例子147圖7.13圖7.12對應(yīng)的二叉樹148圖7.14二叉樹遍歷實例150圖7.15對稱序線索樹153圖7.16在對稱序線索化二叉樹中插入新結(jié)點156圖7.17題7.5用圖157圖7.18題7.7用圖157圖7.19題7.14用圖158圖7.20題7.15用圖158圖8.1二叉排序樹159圖8.2構(gòu)造二叉排序樹162圖8.3二叉排序樹中刪除一個結(jié)點164圖8.4刪除結(jié)點11后的另一種形式164圖8.5兩種不同的二叉排序樹164圖8.6兩棵擴(kuò)充二叉樹164圖8.7最佳二叉排序樹的構(gòu)造165圖8.8二叉樹與結(jié)點的平衡因子167圖8.9平衡的二叉排序的生成過程(帶★的點為插入后引起不平衡的點)168圖8.10二叉排序樹的平衡旋轉(zhuǎn)169圖8.11AVL二叉排序樹結(jié)點的刪除(結(jié)點中右邊數(shù)字代表平衡因子)170圖8.12一棵7階的B-樹171圖8.13B-樹的插入173圖8.14圖8.13中刪除元素80173圖8.15圖8.13中刪除元素4173圖8.16在圖8.15中刪除元素60174圖8.17在圖8.16中刪除元素70174圖8.18一棵3階的B+-樹174圖8.19鍵樹示例175圖8.20由圖8.19壓縮后的鍵樹176圖8.21鍵樹中插入記錄176圖8.22兩棵不同形式的2-3樹177圖8.232-3樹的插入177圖8.24在圖8.22(b)中插入8后2-3樹的變化圖178圖8.252-3樹的刪除178圖8.26一棵擴(kuò)充的二叉樹178圖8.27赫夫曼最優(yōu)樹的構(gòu)造過程179圖8.28Huffman編碼樹182圖8.29堆對應(yīng)的完全二叉樹183圖8.30堆中插入新結(jié)點183圖8.31堆中根結(jié)點的刪除184圖8.32篩法建堆過程184圖8.33堆排序過程185圖8.34三個元素排序的判定樹189圖8.35鑒別偽幣的判定樹189圖8.36用父指針表示的樹狀結(jié)構(gòu)存儲的并查集191圖8.37并查集的查找、合并過程191圖8.38Union加權(quán)規(guī)則示意圖192圖8.39路徑壓縮的例子193圖8.40一棵階為2的紅黑樹194圖8.41紅黑樹的生長過程194圖8.42一棵2階紅黑樹195圖8.43紅黑樹中刪除元素88195圖8.44圖8.43調(diào)整后的紅黑樹196圖8.45圖8.44中刪除元素71196圖8.46圖8.45調(diào)整后的紅黑樹196圖8.47圖8.46中刪除元素63196圖8.48調(diào)整圖8.47后的紅黑樹197圖8.49題8.15用圖198圖9.1無向圖和有向圖199圖9.2圖G4=(V,E)200圖9.3圖G3的強(qiáng)連通分量201圖9.4G1的生成樹201圖9.5G3的生成樹林201圖9.6圖G5(網(wǎng)絡(luò))201圖9.7圖的鄰接表表示203圖9.8G5的鄰接表表示204圖9.9圖9.7(a)的鄰接多重表表示204圖9.10圖9.7(c)的多重鏈表表示205圖9.11有向圖深度優(yōu)先搜索過程206圖9.12無向圖深度方向優(yōu)