《数据结构与算法》课程教学大纲、教学计划

《数据结构与算法》课程教学大纲、教学计划✦课程编号：英文名称：DataStructureandAlgorithm预修课程：线性代数，大学计算机基础，计算机程序设计，离散数学。学时安排：64学时，其中讲授40学时，实践24学时。学

分：4课程性质：专业必修课开课学期：二年级春01课程性质地位《数据结构与算法》是计算机科学与技术、网络工程、物联网工程、信息安全、网络空间安全、软件工程、人工智能与大数据等专业的技术基础必修课程，是软件开发与设计的基础，是一门集技术性、理论性和实践性于一体的课程。02课程目标学员通过本课程的学习，具有用计算机解决非数值计算中的数据抽象、数据结构设计与算法设计的能力，对所设计的算法效率能初步估计。（一）课程知识目标本课程的知识目标主要包括以下主要的知识单元：数据结构概述：包含数据结构定义、数据结构分类、抽象数据类型、算法时、空效率分析；线性结构：包括顺序表（线性表向量、栈、队列）、链表（单链表、双链表、循环链表、链栈、链队列）、顺序表与链表的应用；基本运算：排序算法（插入排序、选择排序、交换排序、分配排序、归并排序）、查找算法（顺序查找、折半查找、分块查找、散列查找、字符串的KMP模式匹配）；树和二叉树：结构定义、转换方法、存储方式、遍历算法，树型结构应用（Huffman最优二叉树与编码、堆排序、有序树（二叉排序树、B树、B+树）；图结构：结构定义、存储方式、深度优先遍历算法、宽度优先遍历算法；图结构应用：最小代价生成树、单源最短路径、最短路径、拓扑排序、关键路径；算法设计与分析：包括递归与分治、回溯法、分支限界法、贪心法、动态规划法。（二）课程能力目标本课程要发展的能力目标包括：1、能够进行数据抽象、数据结构设计与编程实现。2、能够运用数据结构与算法知识解决计算科学中的科学问题。03教学方法通过课内讲授，专题研究，案例讲解，课外练习，作业讲解与讨论，课内实践一系列环节使学员达到预期学习目标，具体包括课堂讲授，互动研讨，程序运行、问题讲解，答疑辅导等环节。本课程推荐主讲教员采用两类教学方法，一是案例导向法，通过实际问题的已有解决方案，如Josephus问题求解、事件驱动的银行模拟、打印缓冲池模拟，启发学员提出问题、分析思路、选用数据结构与算法、讨论求解算法，将源代码交给学员阅读理解后，对待改进的新问题引导学员修改代码后实现；二是合作学习方法，通过设置若干研究项目，引导学员以团队方式参与研究项目，形成问题讨论、项目界定、团队组建、项目分析与分解、项目方案实施以及项目答辩等环节，锻炼学员自主学习、团队合作攻关以及解决现实问题的综合能力。04课程学习目标和学习实现环节（一）知识学习目标和学习实现环节本课程的知识学习目标与相应实现环节采用表格方式进行描述，如下表1所示。（二）课程的学习目标对毕业标准和培养标准中知识-能力-素质相关学习结果的贡献及程度等级用表格方式描述，如下表2。05课程学习内容与时间节点按照章节说明本课程的内容要点及课内学时数，其中章节为顺序编号。如下表3所示。06课程综合计分方法（一）考核结构设计与各教学环节比例分配考核方式：考试与考查相结合组织方式：笔试/现场测试，笔试部分采用闭卷形式成绩评定：百分制记分标准：考试占80％，实验占10％，作业占10%（二）评分标准1、作业采用百分制进行评分，最后综合评分进行相应比例折算。评分标准如下表4所示。2、实验采用百分制进行评分，最后综合评分进行相应比例折算。评分标准如下表5所示。3、三级项目：无4、实习：无5、期末考试：随考试试卷制定评分标准。6、其它：如考勤、测验、课堂互动表现等07教材及推荐参考书（一）教材《数据结构与算法（第2版）》，熊岳山著，清华大学出版社，2016.04（二）推荐参考书（1）《数据结构》（第二版），严尉敏等编，清华大学出版社，1992.（2）《AlgorithmDesign》，JonKleinberg,EvaTardos著，清华大学出版社，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.✦《数据结构与算法》课程简介✦课程编号：170210025课程名称：数据结构与算法（DataStructureandAlgorithm）学时安排：64学时，其中讲授40学时，实践24学时。预修课程：线性代数，大学计算机基础，计算机程序设计，离散数学。内容简介：《数据结构与算法》是计算机学院本科学员计算机科学与技术、网络工程、人工智能与大数据等专业的学科基础必修课程，是计算机程序设计的基础。计算机科学各领域都要用到各种数据结构与算法设计与分析技术。学员通过本课程的学习，具有用计算机解决非数值计算中的数据抽象、数据结构设计与算法设计的能力，对所设计的算法效率能初步估计。课程涉及抽象数据类型、基本数据结构、算法设计与分析方法以及如何用C++（或C）来描述抽象数据类型，使学员能针对实际问题设计适合于计算机求解的数据结构和算法。课程内容包括：基本数据类型、抽象数据类型、顺序表、链表、串、树和二叉树、图、贪心法、动态规划、递归与分治、回溯法和分支限界法等。✦《数据结构与算法》实验教学大纲✦课程编号：170210025课程名称：数据结构与算法总学时：64学时实验学时：24学时实验地点：3号院教室或307实验楼01任务背景与目标（一）任务背景描述数据结构与算法是软件设计与维护的基础，抽象数据类型，基本数据结构：栈、队列、二叉树、树和图等的学习和理解不能只停留在概念层，应通过课程上机编程实践来加深理解。学生在学完C++语言和数据结构与算法相关知识点后已具备完成数据结构上机作业的基本条件。通过课程实验，使学生熟练掌握数据结构与实现，培养学生非数值问题的数据结构抽象与上机编程实现的能力。要求学生独立完成本课程实验规定的上机作业题，按要求完成好上机报告。（二）技术目标一是使用熟悉的C++软件开发工具进行编程；二是应用熟悉的编程语言C++编写数据结构及算法；三是使用运用数据结构与算法编程解决实际问题，简单分析算法效率，以验证课堂所学知识。（三）能力目标培养学员分析和解决现实问题的能力，包括三个方面：一是实际问题求解的数据抽象的能力；二是数据结构设计与编程实现能力；三是算法设计与分析能力。02主要内容与基本要求实验1

线性表、链表的应用1．实验目的与任务实验目的：通过本实验，使学员熟悉线性表的顺序存储与循环报数的实现算法。实验任务：使用抽象数据类型向量解决中国式的击鼓传花问题。2．训练的能力点训练学员运用所学的向量类的知识来编程解决实际问题的能力点。3．实验原理用C++语言编程实现classVector，调用Vector中的取出、删除、插入等运算功能，增加循环报数的实现。4．实验内容及要求实验内容：创建Vector类并设计算法编程模拟实现中国式的击鼓传花游戏。实验要求：（1）描述数据抽象过程及使用的数据结构；（2）编程实现中国式的击鼓传花游戏。5．实验结果及要求对实验结果进行分析。实验2

排序、查找算法的实现1．实验目的与任务实验目的：通过本实验，使学员熟悉排序、查找算法使用的数据结构及算法思想。实验任务：使用C++编程实现分块查找算法。2．训练的能力点训练学员运用所学的数据结构和算法思想解决排序、查找需求的能力点。3．实验原理用C++语言编程实现。4．实验内容及要求实验内容：分别编程实现分块查找算法。实验要求：针对给定线性表的测试数据调试运行算法。5．实验结果及要求对实验结果进行分析。实验3树和二叉树的应用1．实验目的与任务通过本实验使学员了解和掌握编写基于二叉树的双链存储结构上的算法。2.训练的能力点训练学员运用所学的树状结构进行编程应用的能力点。3．实验原理

选用数据结构、设计相应算法，用C++语言编程实现。4．实验内容及要求假设用二叉树的LeftChild-RightChild表示法存储二叉树，每个结点所含数据元素均为单字母，试编程实现按树状打印二叉树的算法。例如：图1的二叉树打印为右边的形状。■

图1二叉树结点的树状输出方式5．实验结果及要求对实验结果进行分析。实验4图的应用1．实验目的与任务通过本实验使学员了解和掌握编写图结构的应用程序。任务就是编程实现基于图的第一、第二和第三最短路径。2.训练的能力点训练学员运用所学的图结构开发图应用的能力点。3．实验原理选用图的存储结构、设计算法，用C++语言编程实现。4．实验内容及要求在网络通信中，经常需要求最短路径。但完全采用最短路径传输有这样一个问题：如果最终在两个终端节点之间给出的最短路径只有一条，则在该路径中的任一个节点或链路出现故障时，信号传输将面临中断的危险。因此，对网络路由选择作了以下改进：为任意两节点之间通信提供三条路径供其选择，即第一最短路径、第二最短路径、和第三最短路径。

第一最短路径的定义为：给定一个不含负回路的网络D=（V，E，W），其中V={v1,v2,…vn},E为边集合，W为权集合，设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)路径。第三最短路径的定义为：设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个节点的网络，，求给定两点间的第一、第二和第三最短路径。用相邻矩阵表示网络。例如，含有n=5的网络的相邻矩阵为：则第一、第二、第三(v1,v5)最短路径为4（1，2，3，4，5）5（1，3，4，5）6（1，2，3，5）5．实验结果及要求至少给出四组测试结果能正确求出带权网络中给定两点间的第一、第二和第三最短路径。实验5

算法设计与分析应用1．实验目的与任务实验目的：通过本实验，使学员熟悉用算法设计策略设计与分析算法，并编程实现。实验任务：设计算法，用C语言（或C++）编程实现。2．训练的能力点训练学员使用C语言（或C++）验证课堂上学过的算法设计策略的能力点。3．实验原理设计算法，用C语言（或C++）编程实现。4．实验内容及要求实验内容：使用算法设计策略设计算法，解决实际问题。实验要求：分别选用1种学过的算法设计策略（贪心法、动态规划、递归与分治、回溯法和分支限界法），编程实现0-1背包问题或旅行商问题或流水作业调度问题。5．实验结果及要求对给定的数据集测试程序，实验结果进行分析。03实施安排04考核与评价（一）考核形式与要求考核方式：考查组织方式：现场测试成绩评定：百分制（二）评分标准评分标准见表5。05实验教材或指导书《数据结构与算法（第2版）》，熊岳山著，清华大学出版社，2016.04参考书籍《数据结构与算法(第3版)》ISBN：9787302643463作者：熊岳山定价：59元内容简介“数据结构与算法”是计算机科学与技术、软件工程等相关专业的重要基础课，是这些专业的核心课程之一，是一门集技术性、理论性和实践性于一体的课程。本书内容包括基本数据类型、抽象数据类型、线性表、链表、串、树和二叉树、图、递归与分治算法、贪心算法、分支限界法和动态规划法等内容；并重点介绍抽象数据类型、基本数据结构、C语言数据结构描述、数据结构的应用、算法设计与分析以及算法性能评价等内容，目的是让读者理解数据抽象与编程实现的关系，提高用计算机解决实际问题的能力。本书结构合理，内容丰富，算法描述清晰，用C语言编写的算法代码都已调试通过，便于自学，可作为高等院校计算机科学与技术专业、军事院校的基础合训专业和其他相关专业的教材和参考书，也可供从事计算机软件开发的科技工作者参考。第1章数据结构概述11.1基本概念11.1.1数据、数据元素、数据对象11.1.2数据结构21.2数据结构的分类31.3数据类型51.3.1基本类型和组合类型51.3.2抽象数据类型51.4算法和算法分析81.4.1算法概念81.4.2算法分析9习题11第2章向量、栈和队列132.1线性表132.1.1线性表的抽象数据类型132.1.2线性表的结构表示152.2向量182.2.1向量的抽象数据类型182.2.2向量的插入和删除202.2.3向量的应用222.3栈252.3.1栈的抽象数据类型及其实现252.3.2栈的应用272.4递归效率分析342.4.1递归方程求解342.4.2生成函数求解递归方程352.4.3特征方程求解递归方程362.4.4递归树方法372.5队列382.5.1队列的抽象数据类型及其实现392.5.2队列的应用——模拟银行活动44习题51第3章链表533.1单链表533.1.1基本概念533.1.2单链表结点结构543.1.3单链表结构563.1.4栈的单链表实现653.1.5队列的单链表实现663.1.6单链表的应用举例703.2循环链表743.3双链表76习题78第4章串814.1基本概念814.2串的存储824.3串结构和串的运算834.4模式匹配854.4.1朴素的模式匹配算法854.4.2KMP匹配算法864.4.3BM匹配算法89习题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基数排序1075.6归并排序1105.7外部排序1135.7.1二路合并排序1135.7.2多路替代选择合并排序1145.7.3最佳合并排序114习题116第6章查找1176.1基本概念1176.2顺序查找1176.3折半查找1196.4分块查找1216.5散列查找1236.5.1概述1236.5.2散列函数1246.5.3冲突的处理1266.5.4散列查找的效率129习题130第7章树和二叉树1327.1树的概念1327.2二叉树1337.2.1二叉树的概念1337.2.2二叉树的性质1337.2.3二叉树的存储方式1367.2.4树(树林)与二叉树的相互转换1387.3树(树林)、二叉树的遍历1397.3.1树(树林)的遍历1397.3.2二叉树的遍历1397.4抽象数据类型BinaryTree以及BinaryTree结构1407.4.1抽象数据类型BinaryTree1407.4.2一个完整的包含构建二叉树与遍历实现的例子1427.5二叉树的遍历算法1437.5.1非递归(使用栈)的遍历算法1437.5.2线索化二叉树的遍历145习题148第8章树结构的应用1508.1二叉排序树1508.1.1二叉排序树与BinarySTree结构1508.1.2二叉排序树的检索、插入、删除运算1518.1.3等概率查找对应的最佳二叉排序树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最优树与树编码1688.5.1Huffman最优树1688.5.2树编码1718.6堆排序1738.7判定树1788.8等价类和并查集1798.8.1等价类1798.8.2并查集1808.9红黑树1828.10跳表1868.10.1跳表时间复杂度分析1878.10.2跳表的空间复杂度分析1878.10.3高效的动态插入和删除1888.10.4小结189习题189第9章图1919.1基本概念1919.2图的存储表示1939.2.1相邻矩阵表示图1939.2.2图的邻接表表示1949.2.3邻接多重表1959.3基于邻接表表示的Graph结构1979.4图的遍历1979.4.1深度优先遍历1989.4.2广度优先遍历2009.5最小代价生成树2019.6单源最短路径问题2059.7每一对顶点间的最短路径问题2089.8有向无回路图2099.8.1DAG图和AOV、AOE网2099.8.2AOV网的拓扑排序2119.8.3AOE网的关键路径213习题215第10章算法设计与分析21710.1递归与分治21710.1.1递归方法设计21710.1.2分治法21810.2回溯法22010.3分支限界法22510.4贪心算法23110.5动态规划法23210.6数据结构中的Catalan数23510.6.1问题描述23510.6.2问题解析23510.6.3递归方程求解236习题237关键词索引239参考文献242第1章数据结构概述11.1基本概念11.1.1数据、数据元素、数据对象11.1.2数据结构21.2数据结构的分类31.3数据类型51.3.1基本类型、组合类型51.3.2抽象数据类型51.4算法和算法分析81.4.1算法概念81.4.2算法分析9习题11第2章向量、栈和队列132.1线性表132.1.1线性表的抽象数据类型132.1.2线性表的结构表示152.2向量182.2.1向量的抽象数据类型182.2.2向量的插入和删除202.2.3向量的应用232.3栈262.3.1栈的抽象数据类型及其实现262.3.2栈的应用292.4递归效率分析362.4.1递归方程求解362.4.2生成函数求解递归方程372.4.3特征方程求解递归方程382.4.4递归树方法392.5队列402.5.1队列的抽象数据类型及其实现402.5.2队列的应用——模拟银行活动46习题54第3章链表563.1单链表563.1.1基本概念563.1.2单链表结点结构573.1.3单链表结构593.1.4栈的单链表实现703.1.5队列的单链表实现713.1.6单链表的应用举例753.2循环链表803.3双链表82习题84第4章串874.1基本概念874.2串的存储884.3串结构和串的运算894.4模式匹配914.4.1朴素的模式匹配算法914.4.2KMP匹配算法924.4.3BM匹配算法95习题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基数排序1145.6归并排序1175.7外部排序1205.7.1二路合并排序1205.7.2多路替代选择合并排序1215.7.3最佳合并排序122习题123第6章查找1256.1基本概念1256.2顺序查找1256.3折半查找1276.4分块查找1296.5散列查找1316.5.1概述1316.5.2散列函数1326.5.3冲突的处理1346.5.4散列查找的效率137习题138第7章树和二叉树1407.1树的概念1407.2二叉树1417.2.1二叉树的概念1417.2.2二叉树的性质1417.2.3二叉树的存储方式1447.2.4树(树林)与二叉树的相互转换1467.3树(树林)、二叉树的遍历1477.3.1树(树林)的遍历1477.3.2二叉树的遍历1477.4抽象数据类型BinaryTree以及BinaryTree结构1487.4.1抽象数据类型BinaryTree1487.4.2一个完整的包含构建二叉树与遍历实现的例子1507.5二叉树的遍历算法1517.5.1非递归(使用栈)的遍历算法1517.5.2线索化二叉树的遍历153习题157第8章树状结构的应用1598.1二叉排序树1598.1.1二叉排序树与BinarySTree结构1598.1.2二叉排序树的检索、插入、删除运算1608.1.3等概率查找对应的最佳二叉排序树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最优树与树编码1788.5.1Huffman最优树1788.5.2树编码1818.6堆排序1838.7判定树1898.8等价类和并查集1908.8.1等价类1908.8.2并查集1908.9红黑树1938.10跳表1978.10.1跳表时间复杂度分析1988.10.2跳表的空间复杂度分析1988.10.3高效的动态插入和删除1998.10.4小结200习题201第9章图2039.1基本概念2039.2图的存储表示2059.2.1相邻矩阵表示图2059.2.2图的邻接表表示2069.2.3邻接多重表2079.3基于邻接表表示的Graph结构2099.4图的遍历2109.4.1深度优先遍历2109.4.2广度优先遍历2129.5最小代价生成树2139.6单源最短路径问题2179.7每一对顶点间的最短路径问题2209.8有向无回路图2229.8.1DAG图和AOV、AOE网2229.8.2AOV网的拓扑排序2249.8.3AOE网的关键路径226习题228第10章算法设计与分析23010.1递归与分治23010.1.1递归方法设计23010.1.2分治法23110.2回溯法23310.3分支限界法23810.4贪心算法24510.5动态规划法24610.6数据结构中的Catalan数24910.6.1问题描述24910.6.2问题解析24910.6.3递归方程求解251习题252关键词索引254参考文献257第1章数据结构概述/11.1基本概念/11.1.1数据、数据元素、数据对象/11.1.2数据结构/21.2数据结构的分类/31.3数据类型/51.3.1基本类型、组合类型/51.3.2抽象数据类型/51.4算法和算法分析/81.4.1算法概念/81.4.2算法分析/9习题/11第2章向量、栈和队列/132.1线性表/132.1.1线性表的抽象数据类型/132.1.2线性表的结构表示/152.2向量/182.2.1向量的抽象数据类型/182.2.2向量的插入和删除/202.2.3向量的应用/232.3栈/262.3.1栈的抽象数据类型及其实现/262.3.2栈的应用/292.4递归效率分析/362.4.1递归方程求解/362.4.2生成函数求解递归方程/372.4.3特征方程求解递归方程/382.4.4递归树方法/392.5队列/402.5.1队列的抽象数据类型及其实现/402.5.2队列的应用——模拟银行活动/46习题/54第3章链表/563.1单链表/563.1.1基本概念/563.1.2单链表结点结构/573.1.3单链表结构/593.1.4栈的单链表实现/703.1.5队列的单链表实现/713.1.6单链表的应用举例/753.2循环链表/803.3双链表/82习题/84第4章串/874.1基本概念/874.2串的存储/884.3串结构和串的运算/894.4模式匹配/914.4.1朴素的模式匹配算法/914.4.2KMP匹配算法/924.4.3BM匹配算法/95习题/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基数排序/1145.6归并排序/1175.7外部排序/1205.7.1二路合并排序/1205.7.2多路替代选择合并排序/1215.7.3最佳合并排序/122习题/123第6章查找/1256.1基本概念/1256.2顺序查找/1256.3折半查找/1276.4分块查找/1296.5散列查找/1316.5.1概述/1316.5.2散列函数/1326.5.3冲突的处理/1346.5.4散列查找的效率/137习题/138第7章树和二叉树/1407.1树的概念/1407.2二叉树/1417.2.1二叉树的概念/1417.2.2二叉树的性质/1417.2.3二叉树的存储方式/1447.2.4树(树林)与二叉树的相互转换/1467.3树(树林)、二叉树的遍历/1477.3.1树(树林)的遍历/1477.3.2二叉树的遍历/1477.4抽象数据类型BinaryTree以及BinaryTree结构/1487.4.1抽象数据类型BinaryTree/1487.4.2一个完整的包含构建二叉树与遍历实现的例子/1507.5二叉树的遍历算法/1517.5.1非递归(使用栈)的遍历算法/1517.5.2线索化二叉树的遍历/153习题/157第8章树状结构的应用/1598.1二叉排序树/1598.1.1二叉排序树与BinarySTree结构/1598.1.2二叉排序树的检索、插入、删除运算/1608.1.3等概率查找对应的最佳二叉排序树/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最优树与树编码/1788.5.1Huffman最优树/1788.5.2树编码/1818.6堆排序/1838.7判定树/1898.8等价类和并查集/1908.8.1等价类/1908.8.2并查集/1908.9红黑树/193习题/197第9章图/1999.1基本概念/1999.2图的存储表示/2019.2.1相邻矩阵表示图/2019.2.2图的邻接表表示/2029.2.3邻接多重表/2039.3基于邻接表表示的Graph结构/2059.4图的遍历/2069.4.1深度优先遍历/2069.4.2广度优先遍历/2089.5最小代价生成树/2099.6单源最短路径问题/2139.7每一对顶点间的最短路径问题/2169.8有向无回路图/2189.8.1DAG图和AOV、AOE网/2189.8.2AOV网的拓扑排序/2209.8.3AOE网的关键路径/222习题/224第10章算法设计与分析/22610.1递归与分治/22610.1.1递归方法设计/22610.1.2分治法/22710.2回溯法/22910.3分支限界法/23410.4贪心算法/24110.5动态规划法/242习题/245图目录/247算法目录/252关键词索引/247参考文献/250图目录图1.1基本的逻辑结构3图1.2基本存储方法4图1.3游泳池及环形过道8图2.1向量的顺序存储19图2.2顺序存储的栈26图2.3中缀表达式的计值过程30图2.4后缀表达式的计值30图2.5中缀表达式转换成后缀表达式的过程31图2.6汉诺塔问题的递归求解过程33图2.7活动记录的进栈情况35图2.8活动记录的退栈情况36图2.9式(2.1)的递归树39图2.10式(2.2)的递归树40图2.11顺序存储的队列40图2.12队列的操作41图2.13循环队列的队空和队满41图3.1单链表56图3.2从链表中删除一个结点56图3.3往链表中插入一个结点56图3.4附加头结点的单链表57图3.5一个实际的单链表结构65图3.6空的循环链表80图3.7双链表结点82图3.8双链表82图3.9往双链表中插入一个结点82图3.10从双链表中删除一个结点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朴素的模式匹配算法执行过程92图4.7模式P="abcabcd"的next数组的计算过程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基数排序的分配和收集过程115图5.10二路归并过程118图5.11二路归并排序示意121图5.12实现五路合并败者树122图5.13实现五路合并一次替代选择后的败者树122图5.14顺序合并的三路合并树122图5.15三路最佳合并树123图6.1折半查找过程128图6.2分块查找过程130图6.3用分离的同义词子表解决冲突137图6.4用结合的同义词子表解决冲突137图6.5几种不同的解决碰撞方法时的平均检索长度（横坐标为负载因子的取值）138图6.6题6.8用图139图7.1家族树140图7.2二叉树的五种基本形态141图7.3表达式二叉树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树(树林)与二叉树之间相互转换146图7.12树林的例子147图7.13图7.12对应的二叉树148图7.14二叉树遍历实例150图7.15对称序线索树153图7.16在对称序线索化二叉树中插入新结点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构造二叉排序树162图8.3二叉排序树中删除一个结点164图8.4删除结点11后的另一种形式164图8.5两种不同的二叉排序树164图8.6两棵扩充二叉树164图8.7最佳二叉排序树的构造165图8.8二叉树与结点的平衡因子167图8.9平衡的二叉排序的生成过程(带★的点为插入后引起不平衡的点)168图8.10二叉排序树的平衡旋转169图8.11AVL二叉排序树结点的删除(结点中右边数字代表平衡因子)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一棵扩充的二叉树178图8.27赫夫曼最优树的构造过程179图8.28Huffman编码树182图8.29堆对应的完全二叉树183图8.30堆中插入新结点183图8.31堆中根结点的删除184图8.32筛法建堆过程184图8.33堆排序过程185图8.34三个元素排序的判定树189图8.35鉴别伪币的判定树189图8.36用父指针表示的树状结构存储的并查集191图8.37并查集的查找、合并过程191图8.38Union加权规则示意图192图8.39路径压缩的例子193图8.40一棵阶为2的红黑树194图8.41红黑树的生长过程194图8.42一棵2阶红黑树195图8.43红黑树中删除元素88195图8.44图8.43调整后的红黑树196图8.45图8.44中删除元素71196图8.46图8.45调整后的红黑树196图8.47图8.46中删除元素63196图8.48调整图8.47后的红黑树197图8.49题8.15用图198图9.1无向图和有向图199图9.2图G4=(V,E)200图9.3图G3的强连通分量201图9.4G1的生成树201图9.5G3的生成树林201图9.6图G5(网络)201图9.7图的邻接表表示203图9.8G5的邻接表表示204图9.9图9.7(a)的邻接多重表表示204图9.10图9.7(c)的多重链表表示205图9.11有向图深度优先搜索过程206图9.12无向图深度方向优