《数据结构》-数据结构复习课

复习课,第一章 基本概念,一、数据与数据结构,二、数据类型,是数据（集合）中的一个“个体”,数据元素:,是数据结构中讨论的基本单位,数据类型 是一个 值的集合和定义在此集合上的 一组操作的总称。,不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。,数据的逻辑结构可归结为以下四类:,线性结构,树形结构,图状结构,集合结构,关系的映象方法：,（表示x, y的方法）,顺序映象,以相对的存储位置表示后继关系,例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C,而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息,x y,链式映象,以附加信息(指针)表示后继关系,需要用一个和 x 在一起的附加信息指示 y 的存储位置,y x,算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：,1有穷性 2确定性 3可行性4有输入 5有输出,算法,算法设计的原则,设计算法时，通常应考虑达到以下目标：,1正确性,2. 可读性,3健壮性,4高效率与低存储量需求,假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：,T (n) = O(f(n),称T (n) 为算法的(渐近)时间复杂度。,算法 = 控制结构 + 原操作 （固有数据类型的操作）,算法的执行时间 =原操作(i)的执行次数原操作(i)的执行时间,算法的执行时间 与 原操作执行次数之和 成正比,从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。,例一两个矩阵相乘,void mult(int a, int b, int /for /mult,基本操作: 乘法操作,时间复杂度: O(n3),例二选择排序,void select_sort(int& a, int n) / 将 a 中整数序列重新排列成自小至大有序的整数序列。 / select_sort,基本操作: 比较(数据元素)操作,时间复杂度: O(n2),j = i; / 选择第 i 个最小元素for ( k = i+1; k n; +k ) if (ak aj ) j = k;,for ( i = 0; inext; p-next = q-next; e = q-data; free(q);,p,q,1. 双向链表,其它形式的链表,typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;,最后一个结点的指针域的指针又指回第一个结点的链表,a1 a2 . an,2. 循环链表,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,双向循环链表,空表,非空表,a1 a2 . an,第三章 栈和队列,一、栈的类型定义和实现,二、队列的类型定义和实现,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,栈和队列是两种常用的数据类型,Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。,a1,a2,an,e, ,Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。,a1,a2,an,an-1, ,栈类型的实现,顺序栈,链栈,EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。,a1,a2,an,e, ,DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。,a1,a2,an, ,队列类型的实现,链队列链式映象,循环队列顺序映象,typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;,a1,an,Q.frontQ.rear,Q.frontQ.rear,空队列,#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;,循环队列顺序映象,第四章 串,一、串的数据类型定义,二、串的表示与实现,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,串的块链存储表示,也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。,存储密度 =,数据元素所占存储位,实际分配的存储位,第五章 数组与广义表,一、数组的类型定义和实现,二、广义表的类型定义和实现,数组的顺序表示和实现,类型特点:1) 只有引用型操作，没有加工型操作；2) 数组是多维的结构，而存储空间是 一个一维的结构。,有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。,例如：,称为基地址或基址。,以“行序为主序”的存储映象,二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij),a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,L,L,推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系,称为 n 维数组的映象函数。数组元素的存储位置是其下标的线性函数。,其中 cn = L，ci-1 = bi ci , 1 i n。,LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji,i,=1,n,假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子。通常认为 0.05 的矩阵为稀疏矩阵。,稀疏矩阵的压缩存储,何谓稀疏矩阵？,十字链表,3 0 0 50 -1 0 02 0 0 0,1,1,3,1,4,5,2,2,-1,3,1,2,广义表是递归定义的线性结构，,LS = ( 1, 2, , n )其中：i 或为原子 或为广义表,例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) ),广义表是一个多层次的线性结构,例如：,D=(E, F),其中: E=(a, (b, c) F=(d, (e),D,E,F,a,( ),d,( ),b,c,e,第六章 树和二叉树,一、树和二叉树的类型定义,二、二叉树的遍历,三、哈夫曼树与哈夫曼编码,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素(一个前驱、 一个后继),其它数据元素(一个前驱、 多个后继),结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,D,H,I,J,M,(从根到结点的)路径：,孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,A,B,C,D,E,F,G,H,I,J,M,K,L,假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大层次,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,性质1： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1),用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；,假设对所有的 j，1 j i，命题成立；,二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。,性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,证明：,设 二叉树上结点总数 n = n0 + n1 + n2又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1由此， n0 = n2 + 1 。,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。,证明：,设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,二叉树的存储结构,二、二叉树的链式 存储表示,一、 二叉树的顺序 存储表示,例如:,A,B,C,D,E,F,A B D C E F,0 1 2 3 4 5 6 7 8 9 10 11 12 13,1,4,0,13,2,6,二、二叉树的链式存储表示,1. 二叉链表,2三叉链表,3双亲链表,4线索链表,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，,每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。,先左后右的遍历算法,先（根）序的遍历算法,中（根）序的遍历算法,后（根）序的遍历算法,哈 夫 曼 树 与 哈 夫 曼 编 码,最优树的定义 如何构造最优树 前缀编码,最优树的定义,树的路径长度定义为： 树中每个结点的路径长度之和。,结点的路径长度定义为： 从根结点到该结点的路径上 分支的数目。,树的带权路径长度定义为： 树中所有叶子结点的带权路径长度之和 WPL(T) = wklk (对所有叶子结点)。,在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。,例如：,指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,前缀编码,利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。,第七章 图,一、图的存储表示,二、图的遍历,三、最小生成树与最短路径,顶点的出度: 以顶点v为弧尾的弧的数目；,A,B,E,C,F,对有向图来说，,顶点的入度: 以顶点v为弧头的弧的数目。,顶点的度(TD)=出度(OD)+入度(ID),例如:,ID(B) = 2,OD(B) = 1,TD(B) = 3,有向图的邻接矩阵为非对称矩阵,A,B,E,C,F,1 4,2,3,0 1,2,0 1 2 3 4,A B C D E,有向图的邻接表,A,B,E,C,F,可见，在有向图的邻接表中不易找到指向该顶点的弧。,图的遍历,从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。,深度优先搜索,广度优先搜索,最小生成树,假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？,问题：,构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。,算法二：（克鲁斯卡尔算法）,该问题等价于：,算法一：（普里姆算法）,两点之间的 最短路径问题,求从某个源点到其余各点的最短路径,每一对顶点之间的最短路径,求从源点到其余各点的最短路径的算法的基本思想:,依最短路径的长度递增的次序求得各条路径,源点,v1,其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。,v2,第九章 查找,一、静态查找表,二、动态查找树表,三、哈希表,(n)(1)(n)(1)(nlogn),综合上一节讨论的几种查找表的特性：,查找 插入 删除,无序顺序表 无序线性链表有序顺序表 有序线性链表 静态查找树表,(n)(n)(logn)(n)(logn),(1)(1)(n)(1)(nlogn),（1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值；,二叉排序树：,二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：,（3）它的左、右子树也都分别是二叉 排序树。,（2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值；,二叉平衡树是二叉查找树的另一种形式，其特点为：,树中每个结点的左、右子树深度之差的绝对值不大于1 。,例如:,5,4,8,2,5,4,8,2,1,是平衡树,不是平衡树,查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，,哈希表是什么？,查找的过程为给定值依次和关键字集合中各个关键字进行比较，,查找的效率取决于和给定值进行比较的关键字个数。,构造哈希函数的方法,对数字的关键字可有下列构造方法：,若是非数字关键字，则需先对其进行数字化处理。,1. 直接定址法,3. 平方取中法,5. 除留余数法,4. 折叠法,6. 随机数法,2. 数字分析法,处理冲突的方法,“处理冲突” 的实际含义是：为产生冲突的地址寻找下一个哈希地址。,1. 开放定址法,2. 链地址法,第十章 排序,一、排序的定义,二、内部排序方法的分类,一、什么是排序？,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。,例如：将下列关键字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,调整为,14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,1. 插入类,将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。,2. 交换类,通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,3. 选择类,从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,4. 归并类,通过“