吉林大学内部绝密资料数据结构总复习（课堂PPT）

1、.1数据结构数据结构总复习.2教学内容教学内容l第一章第一章绪论绪论l第二章第二章线性表、堆栈和队列线性表、堆栈和队列l第三章第三章数组和字符串数组和字符串l第六章第六章递归递归l第四章第四章树树l第五章第五章图图l第七章第七章排序排序l第八章第八章查找查找基础知识基础知识基础知识基础知识线性结构线性结构非线性结构非线性结构非线性结构非线性结构.3重点内容重点内容l三三两两三三两两l三要素（逻辑结构、存储结构、操作）l三个数据结构（线性表、树、图）l两类算法（排序、查找）l两个评价算法的主要标准（时间、空间复杂性）l两个表（33，22）.433（2、3、4、5章）章）线性表树图逻辑结构存储结构

2、操作.522（7、8章）章）时间复杂性空间复杂性排序插入、交换、选择、合并查找有序表的查找杂凑.6重点内容重点内容l3+2三类数据结构l线性表l树l图两类算法l排序l查找.7教学内容教学内容l基础知识第一章绪 论.8一、基础知识一、基础知识l掌握数据结构的基本概念和术语掌握数据结构的基本概念和术语包括：数据、数据元素、数据项、数据结构等基本包括：数据、数据元素、数据项、数据结构等基本 概念。概念。l算法和算法分析算法和算法分析掌握算法、算法的时间复杂度和空间复杂度等概念掌握算法、算法的时间复杂度和空间复杂度等概念掌握算法分析的方法，对一般算法能分析出时间复掌握算法分析的方法，对一般算法能分析出

3、时间复杂度。杂度。 .9一、基础知识一、基础知识l数据数据:计算机程序要处理的“原料”l数据元素数据元素:是组成数据的基本单位。在程序中通常把结点作为一个整体进行考虑和处理。l数据项数据项:每个数据元素都有学号、姓名这两个数据项构成。数据项是构成数据的最小单位。.10一、基础知识一、基础知识的定义：的定义：按某种逻辑关系将一批数据元素组织起按某种逻辑关系将一批数据元素组织起来来按一定的存储方式把它们存储起来；按一定的存储方式把它们存储起来；1.在数据上定义需要施加的操作。在数据上定义需要施加的操作。.11一、基础知识一、基础知识l数据结构的组成：数据结构的组成：数据的数据的数据的数据的数据需要

4、数据需要.12逻辑结构逻辑结构l数据元素之间的逻辑关系称为数据数据元素之间的逻辑关系称为数据的的逻辑结构逻辑结构。l逻辑结构的形式化表示逻辑结构的形式化表示逻辑结构表示为二元组逻辑结构表示为二元组 L=(N, R)，其中，其中N(L)是结点的有限集合，是结点的有限集合， R(L)是是N上的关系集合。上的关系集合。.13逻辑结构的分类逻辑结构的分类l线性结构结构中有且仅有一个有且仅有一个始结点和一个终结点，始结点只有一个后继结点，终结点只有一个前趋结点，每个内结点有且仅有一个有且仅有一个前趋结点和一个后继结点。l非线性结构（树、图）结构中的结点可能有多个可能有多个前趋结点和多个后继结点.14数据

5、的存储结构数据的存储结构l数据在计算机中的存储表示称为数据的存储结构。顺序存储结构链接存储结构.15数据需要施加的操作数据需要施加的操作l数据处理是指对数据进行查找、插入、删数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的除、合并、排序、统计以及简单计算等的操作过程。操作过程。线性表树图.16算法描述语言算法描述语言 ADLlADL 的格式算法（变量i1,变量im.变量j1,变量jn）/单行注释（或/*/多行注释） 步骤名1 步骤1所执行操作的高度概括 语句序列. 步骤名n 步骤n所执行操作的高度概括 语句序列. .17时间复杂性对所研究问题的基本操作对所研究问题的基本

6、操作数据结构数据结构逻辑结构逻辑结构存储结构存储结构操作操作线线性性结结构构树树型型结结构构图图状状结结构构集集合合顺顺 序序存存 储储结结 构构链链 式式存存 储储结结 构构.19二、常用数据结构线性表树图.20线性表l掌握线性表的定义和逻辑结构，了解线性表的基本运算。掌握线性表的定义和逻辑结构，了解线性表的基本运算。l掌握顺序表的插入和删除操作及平均时间性能分析。掌握顺序表的插入和删除操作及平均时间性能分析。l熟练掌握单链表查找、插入和删除操作并分析其时间复杂度。熟练掌握单链表查找、插入和删除操作并分析其时间复杂度。l了解循环单链表算法和单链表上相应算法的异同点。了解循环单链表算法和单链表

7、上相应算法的异同点。l熟练利用单链表设计算法解决简单的应用问题。熟练利用单链表设计算法解决简单的应用问题。l掌握双链表的基本操作。掌握双链表的基本操作。l掌握顺序表和链表的主要优缺点掌握顺序表和链表的主要优缺点.21线性表线性表定义：线性表定义：一个线性表是由零个或多个一个线性表是由零个或多个具有相同类型的结点组成的有序集合。具有相同类型的结点组成的有序集合。用（用（a0，a1，an-1）来表示一个线性）来表示一个线性表。当表。当n0时，时，a0称为表的始结点，称为表的始结点，an-1称为表的终结点，当称为表的终结点，当n=0时，线性表中时，线性表中有零个结点，称为空表。有零个结点，称为空表。

8、.22线性表的存储结构线性表的存储结构l顺序存储结构顺序存储结构l链接存储结构链接存储结构单链表单链表循环链表循环链表双向循环链表双向循环链表.23栈栈 和和 队队 列（线性表的应用）列（线性表的应用）l掌握栈的逻辑结构特点。掌握栈的逻辑结构特点。l掌握顺序栈和链栈上实现的进栈、退栈等基本掌握顺序栈和链栈上实现的进栈、退栈等基本算法。算法。l掌握队列的逻辑结构特点。掌握队列的逻辑结构特点。l掌握顺序队列（主要是循环队列）和链队列上掌握顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。实现的入队、出队等基本算法。.24栈栈 和和 队队 列（线性表的应用）列（线性表的应用）栈和队列都

9、是操作受限的线性表栈和队列都是操作受限的线性表栈的定义：栈是插入和删除只能在其一端进行的线性表。栈的定义：栈是插入和删除只能在其一端进行的线性表。并按先进后出（并按先进后出（ F I L O )F I L O )或后进先出（或后进先出（I I）的原则进行操作。的原则进行操作。队列的定义：队列是插入在一端进行而删除在其另一端队列的定义：队列是插入在一端进行而删除在其另一端进行的线性表。并按先进向出（进行的线性表。并按先进向出（FIFOFIFO）的原则进行操）的原则进行操作。能进行删除的一端称为队首（作。能进行删除的一端称为队首（frontfront），能进行），能进行插入操作的一端称为队尾（插入

10、操作的一端称为队尾（rearrear）。）。.25 栈的应用栈的应用算术表达式求值算术表达式求值运算规则：运算规则：(1) 先计算括号内，后计算括号外；先计算括号内，后计算括号外；(2) 在无括号或同层括号内，先进行乘除运算，在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算的优先级高于加后进行加减运算，即乘除运算的优先级高于加减运算的优先级；减运算的优先级；(3) 同一优先级运算，从左向右依次进行。同一优先级运算，从左向右依次进行。.26数组、字符串和集合（线性结构）数组、字符串和集合（线性结构）l掌握一维、二维数组的存储方法及对任意元素求地址公式l掌握稀疏矩阵的概念及存储方法

11、l掌握串的有关概念及基本算法。l了解串的两种存储表示。l了解模式匹配算法.27树树l掌握树的常用术语及含义。l掌握二叉树的递归定义及树与二叉树的差别。l熟练掌握二叉树的性质。l掌握二叉树的两种存储方法。l熟练掌握二叉树的四种遍历算法。l熟练掌握确定四种遍历所得到的相应的结点访问序列。.28树树l熟练掌握以二叉树遍历算法为基础，设计有关算法解决简单的应用问题。l掌握树的存储方法并设计有关算法解决简单的应用问题。l掌握线索二叉树的概念及存储方法并能将一棵二叉树线索化。l熟练掌握树和森林与二叉树之间的转换方法。l熟练掌握根据给定的叶结点及其权值构造出哈夫曼树。.29常用数据结构常用数据结构l树树是由

12、唯一的起始结点“根结点”( r o o t)出发的结点集合，其中，任何非根结点都有且仅有一个前任何非根结点都有且仅有一个前趋结点趋结点，称之为该结点的父结点；任何结点都可能任何结点都可能有多个后继结点有多个后继结点，称之为该结点的子结点；若某结点没有后继结点，则称之为叶子结点。若存在路径，其中是的后继结点，则称为的子孙结点，称为的祖先结点，该路径所经历的边的个数被称为路径的长度。一个结点到它的某个子孙结点有且仅有一条路径。.30二叉树 (Binary Tree)二叉树是结点的有限集合，它必须满足二叉树是结点的有限集合，它必须满足 下面的一个条件：下面的一个条件：（1）它是空集。）它是空集。（2

13、）它由一个根结点）它由一个根结点,根结点的左右子树根结点的左右子树构成，且其左右子树满足二叉树定义。构成，且其左右子树满足二叉树定义。.31树的储结构 1 1 顺序存储结构顺序存储结构 完全二叉树的顺序存储完全二叉树的顺序存储: :按层次次序给结点编号按层次次序给结点编号，使，使用用一维数组一维数组A来存放。来存放。A0A0存储二叉树的根结点，存储二叉树的根结点，AiAi结点的左孩子结点存放在结点的左孩子结点存放在2i+12i+1处，而处，而AiAi的右孩子的右孩子结点存放在结点存放在A2i+2A2i+2处处 2 2 链式存储结构链式存储结构 二叉树诸结点被随机存放在内存空间中，结点二叉树诸结

14、点被随机存放在内存空间中，结点之间的关系用指针说明。之间的关系用指针说明。( (线索树线索树) ).32基本操作l二叉树的遍历：按照一定次序访问树中所有结二叉树的遍历：按照一定次序访问树中所有结 点，并且每个结点的值仅被访问一次的过程。点，并且每个结点的值仅被访问一次的过程。遍历次序是树中结点的一遍历次序是树中结点的一个有序序列，称为二叉树的先根（中根、后根）个有序序列，称为二叉树的先根（中根、后根）序列。序列。.33构造哈夫曼树哈夫曼算法基本思想：哈夫曼算法基本思想： 根据给定的根据给定的n个权值个权值w1 , w2 , ,wn构成构成n棵二叉树的棵二叉树的森林森林F=T1 ,T2 , ,T

15、n ,其中每棵二叉树其中每棵二叉树Ti中都只有一中都只有一个权值为个权值为wi的根结点，其左、右子树均空；的根结点，其左、右子树均空； 在森林在森林F中选出两棵根结点权值最小的树作为一棵新中选出两棵根结点权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点的权值之和；右子树上根结点的权值之和； 从从F中删除构成新树的那两棵树，同时把新树加入中删除构成新树的那两棵树，同时把新树加入F中；中； 重复第和第步，直到重复第和第步，直到F中只含有一棵树为止，此中只含有一棵树为止，此树便是哈夫曼树。树便是哈夫曼树。.34图l掌握图

16、的常用术语及含义。掌握图的常用术语及含义。l掌握图的深度优先搜索和广度优先搜索两种遍掌握图的深度优先搜索和广度优先搜索两种遍历算法及执行过程。历算法及执行过程。l熟练掌握确定两种遍历所得到的顶点访问序列。熟练掌握确定两种遍历所得到的顶点访问序列。.35图l要求对给定的连通图，根据要求对给定的连通图，根据Prim和和Kruskar算算法构造最小生成树。法构造最小生成树。l对于给定的有向图，根据对于给定的有向图，根据Dijkstra算法能画出算法能画出求单源最短路径的过程示意图。求单源最短路径的过程示意图。l对于给定的有向图，若拓扑序列存在，则要求对于给定的有向图，若拓扑序列存在，则要求写出一个或

17、多个拓扑序列。写出一个或多个拓扑序列。l对于给定的有向图，能求出其关键路径等。对于给定的有向图，能求出其关键路径等。.36图l图（图（Graph）是一种较线性表和树更为复杂的）是一种较线性表和树更为复杂的非线性结构。在图结构中，对结点（图中常称非线性结构。在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结即结点之间的关系是任意的。图中任意两个结点之间都可能相关。图状结构可以描述各种复点之间都可能相关。图状结构可以描述各种复杂的数据对象。杂的数据对象。.37图的存储结构图的存储结构l邻接矩阵l邻接表

18、 (Adjacency List).38图的基本操作遍历遍历深度优先遍历深度优先遍历广度优先遍历广度优先遍历.39基于图的算法拓扑排序拓扑排序关键路径关键路径最短路径（最短路径（Dijkstra算法）算法）最小支撑树最小支撑树(Prim、Kruskar算法算法).40排序排序l排序排序：将一组杂乱无章的数据按一定的规律顺：将一组杂乱无章的数据按一定的规律顺次排列起来。次排列起来。l插入排序插入排序l交换排序交换排序l选择排序选择排序l合并排序合并排序各种内部排序方法的比较各种内部排序方法的比较 排序方法排序方法 最好时间最好时间 平均时间平均时间 最坏时间最坏时间稳定性稳定性辅助空间辅助空间冒泡冒泡O(n)O(n)O(nO(n2 2) )O(nO(n2 2) )稳定稳定O(1)O(1)希尔希尔 O(nO(n1.251.25) ) 不稳定不稳定O(1)O(1)直接插入直接插入O(n)O(n)O(nO(n2 2) )O(nO(n2 2) )稳定稳定O(1)O(1)直接选择直接选择O(nO(n2 2) )O(nO(n2 2) )O(nO(n2 2) )不稳定不稳定O(1)O(1)快速快速O(nlogO(nlog2 2n)n)O(nlogO(nlog2 2n)n)O(nO(n2 2) )不稳定不稳定O(l