考研辅导总复习公开课一等奖课件省课获奖课件

数据构造

第一讲——孟彩霞第1页考查目标

1．理解数据构造基本概念掌握数据逻辑构造、存放构造及其差异多种基本操作实现2．掌握基本数据处理原理和办法基础上，能够对算法进行基本时间复杂度与空间复杂

度进行设计与分析。3．能够选择合适数据构造和办法进行问题求解，具有采取

C

或

C++或

JAVA

语言设计与实

现算法能力

。第2页考试大纲

一、线性表（一）线性表定义和基本操作（二）线性表实现 1．次序存放构造 2．链式存放构造 3．线性表应用第3页考试大纲

二、栈、队列和数组（一）栈和队列基本概念（二）栈和队列次序存放构造（三）栈和队列链式存放构造（四）栈和队列应用（五）特殊矩阵压缩存放第4页考试大纲

三、树与二叉树（一）树基本概念（二）二叉树1．二叉树定义及其主要特性2．二叉树次序存放构造和链式存放构造3．二叉树遍历4．线索二叉树基本概念和构造（三）树、森林1．树存放构造2．森林与二叉树转换3．树和森林遍历（四）树与二叉树应用1．二叉排序树2．平衡二叉树3．哈夫曼（Huffman）树和哈夫曼编码第5页考试大纲

四、图（一）图基本概念（二）图存放及基本操作1．邻接矩阵法2．邻接表法（三）图遍历1．深度优先搜索2．广度优先搜索（四）图基本应用1．最小（代价）生成树2．最短途径3．拓扑排序4．关键途径第6页考试大纲

五、查找（一）查找基本概念（二）次序查找法（三）折半查找法（四）B-树及其基本操作、B+树基本概念

（五）散列（Hash）表及其查找（六）查找算法分析及应用第7页考试大纲六、内部排序（一）排序基本概念（二）插入排序1．直接插入排序2．折半插入排序（三）起泡排序（bubblesort）（四）简单选择排序（五）希尔排序（shellsort）（六）迅速排序（七）堆排序（八）二路归并排序（mergesort）（九）基数排序（十）多种内部排序算法比较（十一）内部排序算法应用第8页大纲解析

从统考大纲和考题类型来看：（1）10道(20分)选择题是对基本概念和基本理论理解和掌握，包括内容不会超出大纲中提及知识点。（2）两道大题(25分)中肯定会有一题编写算法，描述算法语言不限制，能够使用C、C++或Java语言来描述；另外一题能够是算法、与算法思想有关证明、或者综合应用题等。第9页知识点解析

一、数据构造概述 概述部分不是考试重点，不过背面每个知识点中数据构造都是以这里介绍数据构造三要素（数据逻辑构造、存放构造和多种运算）为主线来理解。算法统一根据这里介绍时间和空间复杂度进行分析。第10页知识点解析二、线性表线性表是一种最简单最常用数据构造，这部分内容考试形式一般是以大题形式出现，例如23年考题是一道15分算法设计题，23年考题是一道13分算法设计题。因此考生要灵活应用线性表合适存放表达法处理详细问题。要清楚两种不一样存放构造线性表：次序表和链表，尤其是线性表应用。第11页知识点解析三、栈、队列和数组 栈、队列都是操作受限特殊线性表，数组也能够看作是线性表推广。这部分内容考评多数也许是以选择题形式出现，如23年和23年考题中分别有2道选择题。单独以该部分知识点作为大题也许性比较小，不过在树、图等应用(大题)中使用到栈、队列和数组也许性比较大。第12页知识点解析四、树与二叉树这部分内容考评既也许以选择题形式出现，也也许作为大题出现，如23年考题中是3道选择题，23年有4道选择题。这部分重点要掌握几个主要知识点：二叉树性质、二叉树存放、二叉树遍历、二叉排序树、平衡二叉树、树（森林）与二叉树转换、树应用（如：哈夫曼树和哈夫曼编码）等。大题也许是算法题，也也许是有关证明题，或者计算类综合应用题。第13页知识点解析五、图同树同样，这部分内容考评既也许以选择题形式出现，也也许作为大题出现，如23年考题中是一道10分大题，23年有2道选择题。这部分重点要掌握几个主要知识点：图邻接矩阵和邻接表表达法、图深度优先和广度优先搜索、图几个典型应用。大题也许是算法题，也也许是有关证明题，或者计算类综合应用题。第14页知识点解析六、查找这部分内容考评多数也许是以选择题形式出现，大题也不排除，如23年考题中就是1道选择题，23年考题中是一道10分大题和1道选择题。这部分重点要掌握几个不一样查找办法以及对不一样查找算法评价，评价查找算法是用平均查找长度来衡量。第15页知识点解析七、内部排序这部分内容考评应当也是以选择题形式出现，大题出现也许性较小，如23年考题中有3道选择题，23年考题中有2道选择题。这部分重点是要掌握几个典型排序办法思想，并能够按照排序思想手动进行排序，以及多种不一样排序办法在时间、空间和稳定性方面区分。第16页数据构造绪论

1.数据构造定义2.四种基本构造3.数据构造在计算机中表达次序存放：链式存放：导学：这一部分必须清楚数据构造包括数据逻辑构造、存放构造和运算集合三部分。逻辑构造定义了数据元素之间逻辑关系；存放构造是逻辑构造在计算机中表达。一种逻辑构造能够采取不一样存放方式寄存在计算机中，存放构造有次序存放和链式存放。第17页数据构造绪论4.算法为了实现某类数据构造上运算（操作），就需要设计算法。算法时间度量记作T(n)=○(f(n))，它表达随问题规模n增大，算法执行时间增加率和f(n)增加率相同，称做算法时间复杂度。

导学：切忌算法实现是与所选用存放构造有关，同一种问题存放表达不一样，编写程序也不一样。第18页线性表

1.线性表定义

导学：线性表是最基本数据构造，相对比较简单，一定要深入理解线性表中数据元素之间关系。第19页线性表2.线性表次序存放构造

导学：需要深入理解线性表次序存放是一种随机存取构造，体会次序表上基本操作实现特性，不要与链式存放操作实现混同。第20页线性表3.线性表链式存放构造

导学：需要深入理解线性表链式存放是一种次序存取构造，切忌不要根据元素位置直接访问数据元素。理解链式存放下操作和次序表操作不一样，千万不要混同。需要纯熟掌握多种基本操作算法实现。第21页线性表4.线性表应用

导学：主要是要能够灵活应用线性表合适存放表达处理详细问题，编写有关算法。在编写算法时，假如使用链表，牢记操作中千万不能使链意外“断开”。另外要懂得链表中存放空间是动态分派，需要时申请空间，使用完成要记得释放存放空间。第22页栈、队列和数组

1.栈和队列基本概念

导学：这里主要是要理解栈和队列特性，栈是后进先出表，队列是先进先出表。2.栈存放构造

导学：栈操作较为简单，是线性表子集。一般是在其他应用（算法）中使用到栈，使用时对于栈存放构造不作要求，既能够是次序栈也能够是链栈。第23页栈、队列和数组

3.队列存放构造

导学：链队列操作类似于链表，较为简单，容易掌握。循环队列比较复杂，关键是要弄清楚队满和队空判断。入队时，先判断队列是否满，若不满才能够进行入队操作；出队时，先判断队列是否为空，若不空才能进行出队操作。在某些应用（算法）中也经常使用到队列，使用时对其存放构造不会作要求。队列单独出考题话，考查循环队列也许性大。第24页栈、队列和数组

4.栈和队列应用

导学：栈和队列应用很广泛，利用栈和队列能够控制处理问题次序。实际应用中，凡是对元素保存次序与使用次序相反，都能够利用栈；凡是对元素保存次序与使用次序相同，都能够使用队列。例如：树和图数据构造某些运算中，也多处有栈和队列应用。像二叉树遍历递归和非递归算法，图深度优先遍历等都用到栈，而树按层次遍历、图广度优先遍历等则要用到队列。第25页栈、队列和数组

5.特殊矩阵压缩存放

导学：这部分只要清楚特殊矩阵压缩存放中下标计算公式，以及稀疏矩阵压缩存放基本知识即可。第26页树与二叉树

1.树概念

导学：这部分只要理解递归是树特性、树基本术语即可。第27页树与二叉树

2.二叉树（1）二叉树定义及其主要特性二叉树5种基本形态二叉树5个性质两种特殊二叉树：满二叉树和完全二叉树（2）二叉树次序存放构造和链式存放构造第28页树与二叉树

3.二叉树遍历（1）常用二叉树遍历策略有：先序（根）遍历中序（根）遍历后序（根）遍历按层次遍历（2）体现式前缀、中缀、后缀表达（3）遍历算法（4）遍历算法应用：输出二叉树中结点；输出二叉树中叶子结点；统计二叉树叶子结点数目；求二叉树高度；交换二叉树中所有结点左右孩子；求从二叉树根结点到r结点之间途径等。第29页树与二叉树

4．线索二叉树基本概念和构造线索二叉树有：先序线索二叉树、中序线索二叉树、后序线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树过程称为线索化。在线索树上进行遍历，只要先找到序列中第一种结点，然后依次找结点后继直至其后继为空时而止。

第30页树和森林

1．树存放构造2．树、森林与二叉树互相转换3．树和森林遍历导学：这部分主要掌握树（森林）与二叉树之间互相转换办法。一般对于树操作是把树转换成二叉树后利用二叉树操作完成即可。第31页哈夫曼树

树带权途径长度：树中从根到所有叶子结点各个带权途径长度之和。

哈夫曼树：设有n个权值{w1,w2,…,wn}，构造一棵有n个叶子结点二叉树，每个叶子结点权值为wi，其中带权途径长度WPL最小二叉树称为哈夫曼树（或最优二叉树）。构造哈夫曼树算法步骤哈夫曼树特点：没有度为1结点，树中共有2n-1结点第32页哈夫曼树

前缀编码：定长编码中任一种字符编码都不是另一种字符编码前缀。

哈夫曼编码（最优前缀码）：对于n种字符，以它们使用频率作为叶子结点权值构造哈夫曼树，则该树对应二进制前缀编码称为哈夫曼编码。求哈夫曼编码需要从叶子结点出发走一条从叶子到根途径，从而得到各个字符编码；译码时需从根出发走一条从根到叶子途径。

导学：要能够手工构造哈夫曼树和进行哈夫曼编码，需要清楚为何存放构造采取静态三叉链表。第33页树与二叉树

树与二叉树概念较多，能够考查知识点也比较多。要求理解树与二叉树概念和术语，尤其要深入理解二叉树几个性质以及完全二叉树特点。根据应用不一样，二叉树能够采取二叉链表或者三叉链表存放构造，对于完全二叉树能够采取次序存放构造。对于一般树，常采取树二叉链表（孩子弟兄链表）存放，这样其操作办法就和二叉树有关操作实现办法基本相同。二叉树遍历很主要，要掌握先序、中序、后序、层次遍历算法。二叉树遍历应用十分广泛，很多操作都是在遍历过程中实现其操作。二叉树主要应用之一：哈夫曼树和哈夫曼编码要掌握。第34页图

1.图概念

导学：基本概念中，完全图、连通图、连通分量、生成树和邻接点是重点。第35页图

2.图存放及基本操作（1）邻接矩阵表达法：也称为数组表达法（2）邻接表表达法：是图一种链式存放构造

导学：在编写图应用程序时，要选择合适存放构造，一般是使用邻接矩阵和邻接表或者是对它们稍加修改。例如拓扑排序时能够在邻接表头结点中增加一种寄存顶点入度域即可。第36页图

3.图遍历（1）深度优先搜索遍历：类似于树先根遍历实现其算法能够编写递归算法；若不用递归，则算法中必须定义一种栈。深度优先生成树（2）广度优先搜索遍历：类似于树按层次遍历实现广度优先搜索遍历图算法应当定义一种队列。广度优先生成树导学：图遍历是图多种运算基础，必须深刻理解并纯熟掌握DFS和BFS遍历算法思想，要学会针对图不一样应用选择合适遍历办法。在（强）连通图中，主过程一次调用深（广）度优先遍历过程（dfs/bfs），即可遍历完所有顶点，故可用此办法求出连通分量个数，要会画出遍历过程中形成深（广）度优先生成树和生成森林。第37页图

4.图应用（1）最小（代价）生成树：在一种连通网所有生成树中，各边代价之和最小那棵生成树常用算法有：普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法导学：连通网最小生成树一般不是唯一，但最小生成树边上权值之和是唯一，要掌握Prim和Kruskal算法，尤其是手工分步模拟生成树生成过程。普里姆算法时间复杂度为○(n2)，与网中边数无关，因此适用于求边稠密网最小生成树。克鲁斯卡尔算法时间复杂度为○(eloge)(e为网中边数目)，适合于求边稀疏网最小生成树。

第38页图

4.图应用（2）拓扑排序：拓扑排序是把AOV-网中顶点按照优先关系排成一种线性序列，得到这个序列称为拓扑有序序列实现该算法时，能够采取邻接表作存放构造，且在头结点中增加一种寄存顶点入度域。入度为0顶点即为没有前驱顶点，删除顶点及以它为尾弧操作，即可换以弧头顶点入度减1来实现。导学：AOV-网拓扑序列不是惟一。掌握拓扑排序算法基本思想以及采取存放构造，并能够手工模拟算法得到拓扑有序序列。第39页图

4.图应用（3）AOE-网在工程计划和管理中很有用。在研究实际问题时，一般关怀：(1)完成整个工程最少需要多少时间？(2)哪些活动是影响工程进度关键？关键途径：从源点到汇点最长途径长度即为完成整个工程任务所需时间，该途径叫做关键途径。关键途径上活动叫做关键活动。导学：关键途径是在拓扑有序前提下求出来从源点到汇点最长途径。用拓扑排序和深度优先遍历都可判断图是否存在回路。

第40页图

4.图应用（4）最短途径：是指两点间途径中边权值之和最小途径。迪杰斯特拉(Dijkstra)算法：弗洛伊德(Floyd)算法：导学：掌握Dijkstra和Floyd算法基本思想，并能手工纯熟模拟，以及用最短途径处理实际问题（如医院设在哪个村庄等）。第41页查找

1.查找基本概念平均查找长度（ASL）。即：ASL=导学：查找表是个集合，集合中元素非常涣散，其操作需借助于其他数据构造来实现，查找表能够采取：线性表、树表、哈希表实现其运算。查找算法基本操作是用给定值与关键字值进行比较，因此一般用平均查找长度来衡量查找算法性能。第42页查找

2.基于线性表查找（1）次序查找法（2）折半查找法对查找表有两个要求：①必须采取次序存放构造；②必须按关键字大小有序排列。折半查找过程可用二叉判定树描述导学：次序查找效率低，记住能够通过设置监视哨提升查找效率。折半查找效率高，但要求关键字有序且次序存放，而排序是一种费时运算，为保持有序性，插入、删除操作时必须移动大量数据元素，故折半查找适合于一经建立就很少改动而又经常要查询线性表。必须清楚有序表判定树只与查找表中结点个数有关，而与查找表中详细关键字无关，其判定树是唯一，平均查找长度不超出判定树深度。索引次序查找综合了二者长处。第43页查找

3.基于树查找（1）二叉排序树有n个结点二叉排序树其形态不是惟一，它与这n个结点关键字输入次序有关，其评价查找算法效率平均查找长度也是与得到二叉树形态有关。ASL最差情况与次序查找相同，即ASL=(n+1)/2；最佳情况与折半查找判定树相同，即为（2）平衡二叉树失衡后四种调整办法：LL型平衡旋转、LR型平衡旋转、RR型平衡旋转、RL型平衡旋转（3）B-树一种平衡多路查找树，它在文献系统中很有用。第44页查找

3.基于树查找导学：二叉排序树形态取决于元素输入次序，在最差情况下形成单支树，平均查找长度是○(n)，最佳情况下是○(nlogn)，按中序遍历可得到结点有序序列，必须纯熟掌握其建立、查找、插入和删除算法。最佳二叉排序树是平均查找长度最短二叉排序树，平衡二叉树是介于最佳二叉排序树和一般二叉排序树之间，要掌握手工绘制平衡二叉树。B-树是多路平衡查找树，要理解B-树定义。B-树用于文献系统，要能够手工模拟在B-树中插入和删除关键字使B-树增高和减少。第45页查找

4.计算式查找法——哈希表哈希法又称散列法、杂凑法或关键字地址计算法等，对应表称为哈希表、散列表、杂凑表等。哈希表：根据给定哈希函数H(k)和处理冲突办法将一组关键字映射到一种有限连续地址集(区间)上，并以关键字在地址集中“象”作为统计在表中存放位置，这种表称为哈希表。哈希法主要包括：(1)如何构造哈希函数；(2)如何处理冲突。第46页查找

4.计算式查找法——哈希表常用构造哈希函数办法有：(1)直接定址法；(2)数字分析法；(3)平方取中法；(4)分段叠加法；(5)除留余数法；(6)随后数法。第47页查找

4.计算式查找法——哈希表常用处理冲突办法有：(1)开放定址法；①线性探测再散列②二次探测再散列③伪随机探测再散列(2)再哈希法；(3)链地址法；(4)建立公共溢出区；第48页内部排序

1.排序基本概念排序过程两个基本操作：

比较、移动

稳定排序办法不稳定排序办法第49页内部排序

2.插入排序直接插入排序：折半插入排序：希尔排序：导学：应当纯熟掌握几个不一样插入排序算法思想。理解元素个数较少且基本有序情况下，直接插入排序是一种效率很高排序办法。记住希尔排序最后一趟增量必须是1。第50页内部排序

3.交换排序