吉林大学内部绝密资料-数据结构总复习市公开课金奖市赛课一等奖课件

1、数据结构总复习第1页教学内容第一章绪论第二章线性表、堆栈和队列第三章数组和字符串第六章递归第四章树第五章图第七章排序第八章查找基础知识基础知识线性结构非线性结构非线性结构第2页重点内容三三两两三要素（逻辑结构、存放结构、操作）三个数据结构（线性表、树、图）两类算法（排序、查找）两个评价算法主要标准（时间、空间复杂性）两个表（33，22）第3页33（2、3、4、5章）线性表树图逻辑结构存放结构操作第4页22（7、8章）时间复杂性空间复杂性排序插入、交换、选择、合并查找有序表查找杂凑第5页重点内容3+2三类数据结构线性表树图两类算法排序查找第6页教学内容基础知识第一章绪 论第7页一、基础知识掌握数

2、据结构基本概念和术语包含：数据、数据元素、数据项、数据结构等基本 概念。算法和算法分析掌握算法、算法时间复杂度和空间复杂度等概念掌握算法分析方法，对普通算法能分析出时间复杂度。 第8页一、基础知识数据:计算机程序要处理“原料”数据元素:是组成数据基本单位。在程序中通常把结点作为一个整体进行考虑和处理。数据项:每个数据元素都有学号、姓名这两个数据项组成。数据项是组成数据最小单位。第9页一、基础知识数据结构定义：按某种逻辑关系将一批数据元素组织起来按一定存放方式把它们存放起来；在数据上定义需要施加操作。第10页一、基础知识数据结构组成：数据逻辑结构数据存放结构数据需要施加操作第11页逻辑结构数据元

3、素之间逻辑关系称为数据逻辑结构。逻辑结构形式化表示逻辑结构表示为二元组 L=(N, R)，其中N(L)是结点有限集合， R(L)是N上关系集合。第12页逻辑结构分类线性结构结构中有且仅有一个始结点和一个终止点，始结点只有一个后继结点，终止点只有一个前趋结点，每个内结点有且仅有一个前趋结点和一个后继结点。非线性结构（树、图）结构中结点可能有多个前趋结点和多个后继结点第13页数据存放结构数据在计算机中存放表示称为数据存放结构。次序存放结构链接存放结构第14页数据需要施加操作数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等操作过程。线性表树图第15页算法描述语言 ADLADL

4、格式算法（变量i1,变量im.变量j1,变量jn）/单行注释（或/*/多行注释） 步骤名1 步骤1所执行操作高度概括 语句序列. 步骤名n 步骤n所执行操作高度概括 语句序列. 第16页时间复杂性度量算法标准： （1）能告诉算法所采取方法时间效率； （2）与算法描述语言及设计格调无关； （3）与算法许多细节无关； （4）足够准确和含有普通性。基本运算（关键操作）对所研究问题基本操作时间复杂性一个算法时间复杂性是指该算法基本运算次数。第17页数据结构逻辑结构存放结构操作线性结构树型结构图状结构集合顺 序存 储结 构链 式存 储结 构第18页二、惯用数据结构线性表树图第19页线性表掌握线性表定义和

5、逻辑结构，了解线性表基本运算。掌握次序表插入和删除操作及平均时间性能分析。熟练掌握单链表查找、插入和删除操作并分析其时间复杂度。了解循环单链表算法和单链表上对应算法异同点。熟练利用单链表设计算法处理简单应用问题。掌握双链表基本操作。掌握次序表和链表主要优缺点第20页线性表线性表定义：一个线性表是由零个或多个含有相同类型结点组成有序集合。用（a0，a1，an-1）来表示一个线性表。当n0时，a0称为表始结点，an-1称为表终止点，当n=0时，线性表中有零个结点，称为空表。第21页线性表存放结构次序存放结构链接存放结构单链表循环链表双向循环链表第22页栈 和 队 列（线性表应用）掌握栈逻辑结构特点

6、。掌握次序栈和链栈上实现进栈、退栈等基本算法。掌握队列逻辑结构特点。掌握次序队列（主要是循环队列）和链队列上实现入队、出队等基本算法。第23页栈 和 队 列（线性表应用）栈和队列都是操作受限线性表栈定义：栈是插入和删除只能在其一端进行线性表。并按先进后出（ F I L O )或后进先出（I）标准进行操作。队列定义：队列是插入在一端进行而删除在其另一端进行线性表。并按先进向出（FIFO）标准进行操作。能进行删除一端称为队首（front），能进行插入操作一端称为队尾（rear）。第24页 栈应用算术表示式求值运算规则：(1) 先计算括号内，后计算括号外；(2) 在无括号或同层括号内，先进行乘除运算

7、，后进行加减运算，即乘除运算优先级高于加减运算优先级；(3) 同一优先级运算，从左向右依次进行。第25页数组、字符串和集合（线性结构）掌握一维、二维数组存放方法及对任意元素求地址公式掌握稀疏矩阵概念及存放方法掌握串相关概念及基本算法。了解串两种存放表示。了解模式匹配算法第26页树掌握树惯用术语及含义。掌握二叉树递归定义及树与二叉树差异。熟练掌握二叉树性质。掌握二叉树两种存放方法。熟练掌握二叉树四种遍历算法。熟练掌握确定四种遍历所得到对应结点访问序列。第27页树熟练掌握以二叉树遍历算法为基础，设计相关算法处理简单应用问题。掌握树存放方法并设计相关算法处理简单应用问题。掌握线索二叉树概念及存放方法

8、并能将一棵二叉树线索化。熟练掌握树和森林与二叉树之间转换方法。熟练掌握依据给定叶结点及其权值结构出哈夫曼树。第28页惯用数据结构树树是由唯一起始结点“根结点”( r o o t)出发结点集合，其中，任何非根结点都有且仅有一个前趋结点，称之为该结点父结点；任何结点都可能有多个后继结点，称之为该结点子结点；若某结点没有后继结点，则称之为叶子结点。若存在路径，其中是后继结点，则称为子孙结点，称为祖先结点，该路径所经历边个数被称为路径长度。一个结点到它某个子孙结点有且仅有一条路径。第29页二叉树 (Binary Tree)二叉树是结点有限集合，它必须满足 下面一个条件：（1）它是空集。（2）它由一个根

9、结点,根结点左右子树组成，且其左右子树满足二叉树定义。第30页树储结构 1 次序存放结构 完全二叉树次序存放:按层次次序给结点编号，使用一维数组A来存放。A0存放二叉树根结点，Ai结点左孩子结点存放在2i+1处，而Ai右孩子结点存放在A2i+2处 2 链式存放结构 二叉树诸结点被随机存放在内存空间中，结点之间关系用指针说明。(线索树)第31页基本操作二叉树遍历：按照一定次序访问树中全部结 点，而且每个结点值仅被访问一次过程。先根（中根、后根）遍历次序是树中结点一个有序序列，称为二叉树先根（中根、后根）序列。第32页结构哈夫曼树哈夫曼算法基本思想： 依据给定n个权值w1 , w2 , ,wn组成

10、n棵二叉树森林F=T1 ,T2 , ,Tn ,其中每棵二叉树Ti中都只有一个权值为wi根结点，其左、右子树均空； 在森林F中选出两棵根结点权值最小树作为一棵新树左、右子树，且置新树根结点权值为其左、右子树上根结点权值之和； 从F中删除组成新树那两棵树，同时把新树加入F中； 重复第和第步，直到F中只含有一棵树为止，此树便是哈夫曼树。第33页图掌握图惯用术语及含义。掌握图深度优先搜索和广度优先搜索两种遍历算法及执行过程。熟练掌握确定两种遍历所得到顶点访问序列。第34页图要求对给定连通图，依据Prim和Kruskar算法结构最小生成树。对于给定有向图，依据Dijkstra算法能画出求单源最短路径过程

11、示意图。对于给定有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列。对于给定有向图，能求出其关键路径等。第35页图图（Graph）是一个较线性表和树更为复杂非线性结构。在图结构中，对结点（图中常称为顶点）前趋和后继个数都是不加限制，即结点之间关系是任意。图中任意两个结点之间都可能相关。图状结构能够描述各种复杂数据对象。第36页图存放结构邻接矩阵邻接表 (Adjacency List)第37页图基本操作遍历深度优先遍历广度优先遍历第38页基于图算法拓扑排序关键路径最短路径（Dijkstra算法）最小支撑树(Prim、Kruskar算法)第39页排序排序：将一组杂乱无章数据按一定规律顺次排列起来。插入排序交换排序选择排序合并排序第40页各种内部排序方法比较 排序方法最好时间平均时间最坏时间稳定性辅助空间冒泡O(n)O(n2)O(n2)稳定O(1)希尔 O(n1.25) 不稳定O(1)直接插入O(n)O(n2)O(n2)稳定O(1)直接选择O(n2)O(n2)O(n2)不稳定O(1)快速O(nlog