吉林大学内部绝密资料-数据结构总复习.

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