吉林大学内部绝密资料数据结构总复习市公开课一等奖百校联赛获奖课件.pptx

数据结构数据结构总复习第1页教学内容教学内容l第一章第一章绪论绪论l第二章第二章线性表、堆栈和队列线性表、堆栈和队列l第三章第三章数组和字符串数组和字符串l第六章第六章递归递归l第四章第四章树树l第五章第五章图图l第七章第七章排序排序l第八章第八章查找查找基础知识基础知识基础知识基础知识线性结构线性结构非线性结构非线性结构非线性结构非线性结构第2页重点内容重点内容l三三两两三三两两l三要素（逻辑结构、存放结构、操作）l三个数据结构（线性表、树、图）l两类算法（排序、查找）l两个评价算法主要标准（时间、空间复杂性）l两个表（33，22）第3页33（2、3、4、5章）章）线性表树图逻辑结构存放结构操作第4页22（7、8章）章）时间复杂性空间复杂性排序插入、交换、选择、合并查找有序表查找杂凑第5页重点内容重点内容l3+2三类数据结构l线性表l树l图两类算法l排序l查找第6页教学内容教学内容l基础知识第一章绪 论第7页一、基础知识一、基础知识l掌握数据结构基本概念和术语掌握数据结构基本概念和术语包含：数据、数据元素、数据项、数据结构等基本包含：数据、数据元素、数据项、数据结构等基本 概念。概念。l算法和算法分析算法和算法分析掌握算法、算法时间复杂度和空间复杂度等概念掌掌握算法、算法时间复杂度和空间复杂度等概念掌握算法分析方法，对普通算法能分析出时间复杂度。握算法分析方法，对普通算法能分析出时间复杂度。第8页一、基础知识一、基础知识l数据数据:计算机程序要处理“原料”l数据元素数据元素:是组成数据基本单位。在程序中通常把结点作为一个整体进行考虑和处理。l数据项数据项:每个数据元素都有学号、姓名这两个数据项组成。数据项是组成数据最小单位。第9页一、基础知识一、基础知识数据结构数据结构定义：定义：1.按某种逻辑关系将一批数据元素组织起按某种逻辑关系将一批数据元素组织起来来2.按一定存放方式把它们存放起来；按一定存放方式把它们存放起来；3.在数据上定义需要施加操作。在数据上定义需要施加操作。第10页一、基础知识一、基础知识l数据结构组成：数据结构组成：数据数据逻辑结构逻辑结构数据数据存放结构存放结构数据需要数据需要施加操作施加操作第11页逻辑结构逻辑结构l数据元素之间逻辑关系称为数据数据元素之间逻辑关系称为数据逻逻辑结构辑结构。l逻辑结构形式化表示逻辑结构形式化表示逻辑结构表示为二元组逻辑结构表示为二元组 L=(N,R)，其中，其中N(L)是结点有限集合，是结点有限集合，R(L)是是N上关系集合。上关系集合。第12页逻辑结构分类逻辑结构分类l线性结构结构中有且仅有一个有且仅有一个始结点和一个终止点，始结点只有一个后继结点，终止点只有一个前趋结点，每个内结点有且仅有一个有且仅有一个前趋结点和一个后继结点。l非线性结构（树、图）结构中结点可能有多个可能有多个前趋结点和多个后继结点第13页数据存放结构数据存放结构l数据在计算机中存放表示称为数据存放结构。次序存放结构链接存放结构第14页数据需要施加操作数据需要施加操作l数据处理是指对数据进行查找、插入、删数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等操除、合并、排序、统计以及简单计算等操作过程。作过程。线性表树图第15页算法描述语言算法描述语言 ADLlADL 格式算法（变量i1,变量im.变量j1,变量jn）/单行注释（或/*/多行注释）步骤名1 步骤1所执行操作高度概括 语句序列.步骤名n 步骤n所执行操作高度概括 语句序列.第16页时间复杂性度量算法标准：度量算法标准：度量算法标准：度量算法标准：（1 1）能告诉算法所采取方法时间效率；）能告诉算法所采取方法时间效率；）能告诉算法所采取方法时间效率；）能告诉算法所采取方法时间效率；（2 2）与算法描述语言及设计格调无关；）与算法描述语言及设计格调无关；）与算法描述语言及设计格调无关；）与算法描述语言及设计格调无关；（3 3）与算法许多细节无关；）与算法许多细节无关；）与算法许多细节无关；）与算法许多细节无关；（4 4）足够准确和含有普通性。）足够准确和含有普通性。）足够准确和含有普通性。）足够准确和含有普通性。基本运算（关键操作）基本运算（关键操作）基本运算（关键操作）基本运算（关键操作）对所研究问题基本操作对所研究问题基本操作时间复杂性时间复杂性时间复杂性时间复杂性一个算法时间复杂性是指该算法基本运算次数。一个算法时间复杂性是指该算法基本运算次数。一个算法时间复杂性是指该算法基本运算次数。一个算法时间复杂性是指该算法基本运算次数。第17页数据结构数据结构逻辑结构逻辑结构存放结构存放结构操作操作线线性性结结构构树树型型结结构构图图状状结结构构集集合合顺顺 序序存存 储储结结 构构链链 式式存存 储储结结 构构第18页二、惯用数据结构线性表树图第19页线性表l掌握线性表定义和逻辑结构，了解线性表基本运算。掌握线性表定义和逻辑结构，了解线性表基本运算。l掌握次序表插入和删除操作及平均时间性能分析。掌握次序表插入和删除操作及平均时间性能分析。l熟练掌握单链表查找、插入和删除操作并分析其时间复杂度。熟练掌握单链表查找、插入和删除操作并分析其时间复杂度。l了解循环单链表算法和单链表上对应算法异同点。了解循环单链表算法和单链表上对应算法异同点。l熟练利用单链表设计算法处理简单应用问题。熟练利用单链表设计算法处理简单应用问题。l掌握双链表基本操作。掌握双链表基本操作。l掌握次序表和链表主要优缺点掌握次序表和链表主要优缺点第20页线性表线性表定义：线性表定义：一个线性表是由零个或多个一个线性表是由零个或多个含有相同类型结点组成有序集合。用含有相同类型结点组成有序集合。用（a0，a1，an-1）来表示一个线性表。）来表示一个线性表。当当n0时，时，a0称为表始结点，称为表始结点，an-1称为表称为表终止点，当终止点，当n=0时，线性表中有零个结时，线性表中有零个结点，称为空表。点，称为空表。第21页线性表存放结构线性表存放结构l次序存放结构次序存放结构l链接存放结构链接存放结构单链表单链表循环链表循环链表双向循环链表双向循环链表第22页栈栈 和和 队队 列（线性表应用）列（线性表应用）l掌握栈逻辑结构特点。掌握栈逻辑结构特点。l掌握次序栈和链栈上实现进栈、退栈等基本算掌握次序栈和链栈上实现进栈、退栈等基本算法。法。l掌握队列逻辑结构特点。掌握队列逻辑结构特点。l掌握次序队列（主要是循环队列）和链队列上掌握次序队列（主要是循环队列）和链队列上实现入队、出队等基本算法。实现入队、出队等基本算法。第23页栈栈 和和 队队 列（线性表应用）列（线性表应用）栈和队列都是操作受限线性表栈和队列都是操作受限线性表栈定义：栈是插入和删除只能在其一端进行线性表。并栈定义：栈是插入和删除只能在其一端进行线性表。并按先进后出（按先进后出（F I L O)F I L O)或后进先出（或后进先出（I I）标准）标准进行操作。进行操作。队列定义：队列是插入在一端进行而删除在其另一端进队列定义：队列是插入在一端进行而删除在其另一端进行线性表。并按先进向出（行线性表。并按先进向出（FIFOFIFO）标准进行操作。能）标准进行操作。能进行删除一端称为队首（进行删除一端称为队首（frontfront），能进行插入操作一），能进行插入操作一端称为队尾（端称为队尾（rearrear）。）。第24页 栈应用栈应用算术表示式求值算术表示式求值运算规则：运算规则：(1)先计算括号内，后计算括号外；先计算括号内，后计算括号外；(2)在无括号或同层括号内，先进行乘除运算，在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算优先级高于加减后进行加减运算，即乘除运算优先级高于加减运算优先级；运算优先级；(3)同一优先级运算，从左向右依次进行。同一优先级运算，从左向右依次进行。第25页数组、字符串和集合（线性结构）数组、字符串和集合（线性结构）l掌握一维、二维数组存放方法及对任意元素求地址公式l掌握稀疏矩阵概念及存放方法l掌握串相关概念及基本算法。l了解串两种存放表示。l了解模式匹配算法第26页树树l掌握树惯用术语及含义。l掌握二叉树递归定义及树与二叉树差异。l熟练掌握二叉树性质。l掌握二叉树两种存放方法。l熟练掌握二叉树四种遍历算法。l熟练掌握确定四种遍历所得到对应结点访问序列。第27页树树l熟练掌握以二叉树遍历算法为基础，设计相关算法处理简单应用问题。l掌握树存放方法并设计相关算法处理简单应用问题。l掌握线索二叉树概念及存放方法并能将一棵二叉树线索化。l熟练掌握树和森林与二叉树之间转换方法。l熟练掌握依据给定叶结点及其权值结构出哈夫曼树。第28页惯用数据结构惯用数据结构l树树是由唯一起始结点“根结点”(r o o t)出发结点集合，其中，任何非根结点都有且仅有一个前趋结任何非根结点都有且仅有一个前趋结点点，称之为该结点父结点；任何结点都可能有多个任何结点都可能有多个后继结点后继结点，称之为该结点子结点；若某结点没有后继结点，则称之为叶子结点。若存在路径，其中是后继结点，则称为子孙结点，称为祖先结点，该路径所经历边个数被称为路径长度。一个结点到它某个子孙结点有且仅有一条路径。第29页二叉树(Binary Tree)二叉树是结点有限集合，它必须满足二叉树是结点有限集合，它必须满足 下面一个条件：下面一个条件：（1）它是空集。）它是空集。（2）它由一个根结点）它由一个根结点,根结点左右子树组根结点左右子树组成，且其左右子树满足二叉树定义。成，且其左右子树满足二叉树定义。第30页树储结构 1 1 次序存放结构次序存放结构 完全二叉树次序存放完全二叉树次序存放:按层次次序给结点编号按层次次序给结点编号，使用，使用一维数组一维数组A来存放。来存放。A0A0存放二叉树根结点，存放二叉树根结点，AiAi结结点左孩子结点存放在点左孩子结点存放在2i+12i+1处，而处，而AiAi右孩子结点存右孩子结点存放在放在A2i+2A2i+2处处 2 2 链式存放结构链式存放结构 二叉树诸结点被随机存放在内存空间中，结点二叉树诸结点被随机存放在内存空间中，结点之间关系用指针说明。之间关系用指针说明。(线索树线索树)第31页基本操作l二叉树遍历：按照一定次序访问树中全部结二叉树遍历：按照一定次序访问树中全部结 点，而且每个结点值仅被访问一次过程。点，而且每个结点值仅被访问一次过程。先根先根先根先根（中根、后根）（中根、后根）（中根、后根）（中根、后根）遍历次序是树中结点一个有序遍历次序是树中结点一个有序序列，称为二叉树先根（中根、后根）序列。序列，称为二叉树先根（中根、后根）序列。第32页结构哈夫曼树哈夫曼算法基本思想：哈夫曼算法基本思想：依据给定依据给定n个权值个权值w1,w2,wn组成组成n棵二叉树森林棵二叉树森林F=T1,T2,Tn,其中每棵二叉树其中每棵二叉树Ti中都只有一个权值为中都只有一个权值为wi根结点，其左、右子树均空；根结点，其左、右子树均空；在森林在森林F中选出两棵根结点权值最小树作为一棵新树中选出两棵根结点权值最小树作为一棵新树左、右子树，且置新树根结点权值为其左、右子树上左、右子树，且置新树根结点权值为其左、右子树上根结点权值之和；根结点权值之和；从从F中删除组成新树那两棵树，同时把新树加入中删除组成新树那两棵树，同时把新树加入F中；中；重复第重复第和第和第步，直到步，直到F中只含有一棵树为止，此中只含有一棵树为止，此树便是哈夫曼树。树便是哈夫曼树。第33页图l掌握图惯用术语及含义。掌握图惯用术语及含义。l掌握图深度优先搜索和广度优先搜索两种遍历掌握图深度优先搜索和广度优先搜索两种遍历算法及执行过程。算法及执行过程。l熟练掌握确定两种遍历所得到顶点访问序列。熟练掌握确定两种遍历所得到顶点访问序列。第34页图l要求对给定连通图，依据要求对给定连通图，依据Prim和和Kruskar算法算法结构最小生成树。结构最小生成树。l对于给定有向图，依据对于给定有向图，依据Dijkstra算法能画出求算法能画出求单源最短路径过程示意图。单源最短路径过程示意图。l对于给定有向图，若拓扑序列存在，则要求写对于给定有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列。出一个或多个拓扑序列。l对于给定有向图，能求出其关键路径等。对于给定有向图，能求出其关键路径等。第35页图l图（图（Graph）是一个较线性表和树更为复杂非）是一个较线性表和树更为复杂非线性结构。在图结构中，对结点（图中常称为线性结构。在图结构中，对结点（图中常称为顶点）前趋和后继个数都是不加限制，即结点顶点）前趋和后继个数都是不加限制，即结点之间关系是任意。图中任意两个结点之间都可之间关系是任意。图中任意两个结点之间都可能相关。图状结构能够描述各种复杂数据对象。能相关。图状结构能够描述各种复杂数据对象。第36页图存放结构图存放结构l邻接矩阵l邻接表(Adjacency List)第37页图基本操作遍历遍历深度优先遍历深度优先遍历广度优先遍历广度优先遍历第38页基于图算法拓扑排序拓扑排序关键路径关键路径最短路径（最短路径（Dijkstra算法）算法）最小支撑树最小支撑树(Prim、Kruskar算法算法)第39页排序排序l排序排序：将一组杂乱无章数据按一定规律顺次排：将一组杂乱无章数据按一定规律顺次排列起来。列起来。l插入排序插入排序l交换排序交换排序l选择排序选择排序l合并排序合并排序第40页各种内部排序方法比较各种内部排序方法比较 排序方法排序方法 最好时间最好时间 平均时间平均时间 最坏时间最坏时间稳定性稳定性辅助空间辅助空间冒泡冒泡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(logO(log2 2n)n)堆堆O(nlogO(nlog2 2n)n)O(nlogO(nlog2 2n)n)O(nlogO(nlog2 2n)n)不稳定不稳定O(1)O(1)归并归并O(nlogO(nlog2 2n)n)O(nlogO(nlog2 2n)n)O(nlogO(nlog2 2n)n)稳定稳定O(n)O(n)第41页查找查找l线性表查找线性表查找次序查找次序查找有序表查找有序表查找二叉查找（搜索）树二叉查找（搜索）树第42页l杂凑杂凑杂凑函数杂凑函数l抽取法抽取法l压缩法压缩法l除法杂凑函数除法杂凑函数l乘法杂凑函数乘法杂凑函数第43页l冲突调整冲突调整拉链法 线性探查 双重杂凑 第44页