数据结构冲刺班授课.ppt

1、,(1)队列: 只允许在表的一端删除元素，在另一端插入元素的线性表 (2)空队列: 不含元素的队列 (3)队首: 队列中只允许进行删除元素的一端 (4)队尾: 队列中只允许进行插入的一端 (5)队首元素: 处于队首的元素 (6)队尾元素: 处于队尾的元素 (7)进队: 插入一个元素 (8)出队: 删除一个元素 (9)队列中元素的进出原则: 先进先出( First In First Out )。 (10)队列的别名: 先进先出表，FIFO 表,队列示例 出队 A B C 进队 head tail (队首指针) (队尾指针),1 队列,如果采用单向链，设两个指针 head指向队首 tail指向队尾

2、 空队列 head=tail=NULL; 有一个元素的队列 data next headA 首(尾)结点 tail,一般队列 data next headA 首结点 B tailC 尾结点 ,1 队列,2 堆排序 1堆的定义,若有n个元素(a1，a2，a3，an)，当满足如下条件： aia2i aia2i （1） aia2i+1 或 (2) aia2i+1 其中i=1,2,n/2 则称此n个元素a1，a2，a3，an为一个堆。,若将此元素序列按顺序组成一棵完全二叉树，则（1）称为小根堆（二叉树的所有根结点值小于或等于左右孩子的值），（2）称为大根堆（二叉树的所有根结点值大于或等于左右孩子的值）

3、。,小根堆,大根堆,不是堆,不是堆,2.堆与完全二叉树关系 若n个元素a1，a2，a3，an满足堆，且让结点按1、2、3、n顺序编号，根据完全二叉树的性质（若i为根结点，则左孩子为2i，右孩子为2i+1）可知，一个堆对应着一颗完全二叉树，堆排序实际与一棵完全二叉树有关。若将元素初始序列组成一棵完全二叉树，则堆排序可以包含建立初始堆（使排序码变成能符合堆的定义的完全二叉树）和利用堆进行排序两个阶段。,3、实例 如序列(80,75,40,62,73,35,28,50,38,25,47,15)可以验证它满足堆的条件,因此是一个堆.下图给出其对应的完全二叉树.,1,堆排序：将无序序列建成一个堆，得到关

4、键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫 堆排序需解决的两个问题： 如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 第二个问题解决方法筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”,例,typedef SqList HeapType;,第一个问题解决方法 方法：从无序序列的第n/2个元

5、素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选,算法描述,例 含8个元素的无序序列（49，38，65，97，76，13，27，50）,50,97,13,65,38,13,27,49,2 算法描述,算法评价 时间复杂度：最坏情况下T(n)=O(nlogn) 空间复杂度：S(n)=O(1),堆排序的性能 堆排序是不稳定的； 堆排序适用于n 较大的情况,4 线性表及其顺序存储结构,一、线性表的逻辑结构 线性表 由n(n0)个数据元素a1,a2,.,an构成的有限序列记作: L( a1, a2, ., an ) 其中，a1称为首元素，an称为尾元素。 表的长度(

6、表长) 线性表中数据元素的数目。 空表 不含数据元素的线性表(n=0) 。,完全图： 无向完全图：任意两顶点间都有边的图。 在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。 有向完全图:任意两顶点之间都有方向互为相反的两条弧相连接的有向图。 在一个含有n个顶点的有向完全图中，有n(n-1)条弧。,5完全图,一 、深度优先遍历（DFS） 从图中某顶点v出发： 1）访问顶点v；2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；,V0,V1,V3,V7,V4,V2,V5,V6,由于没有规定 访问邻接点的顺序， DFS序列不唯一,例,求图G以V0起点的的深度优先序列：,V0,V1

7、,V4,V7,V3,V2,V5,V6,22 两种遍历思想,图中某未访问过的顶点vi出发： 1）访问顶点vi ； 2）访问 vi 的所有未被访问的邻接点w1 ,w2 , wk ； 3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；,二、广度优先遍历（BFS）,由于没有规定 访问邻接点的顺序， BFS序列不唯一,例,求图G 的以V0起点的的广度优先序列: V0,V1,V2,V3,V4,V5,V6,V7,24 哈夫曼树,哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各

8、码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。） 由于哈夫曼给出了构造这种树的规律，将给定结点构成一棵带权树的路径长度最小的二叉数，因此称为哈夫曼树。,哈夫曼树构造方法,方法： (1) 根据与n个权值w1,w2wn对应的n个结点构成具有n棵二叉树的森林F=T1,T2Tn,其中第i棵二叉树Ti(1 i n)都只有一个权值为wi的根结点，其左、右子树均为空 (2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、

9、右子树上根结点权值之和 (3) 从F中删除构成新树的那两棵，同时把新树加入F中 (4) 重复第(2)和第(3)步，直到F中只含有一棵为止，此树便为哈夫曼树,简单例子,简单例子: 一串信号源Ss1,s2,s3,s4,s5对应概率为p40，30，15，10，5，（百分率） 按照递减的格式排列概率后，根据第二步，会得到一个新的概率列表，依然按照递减排列，注意：如果遇到相同概率，合并后的概率放在下面！ 最后概率最大的编码为1，最小的编码为0。,简单例子,s1=1 s2=00 s3=010 s4=0110 s5=0111,1.4.4 算法分析,分析一个算法主要是看这个算法的执行需要花费多少机器资源。 在

10、进行算法分析时人们最关心的就是运行算法所要花费的时间和算法中使用的各种数据占有的空间。在文献中习惯称之为算法的时间代价和空间代价。,基本概念,算法的空间代价(或称空间复杂性)：当被解决问题的规模(以某种单位计算)由1增至n时，解该问题的算法所需占用的空间也以某种单位由f(1)增至f(n)，这时我们称该算法的空间代价是f(n)。 算法的时间代价(或称时间复杂性)：当问题规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由g(1)增至g(n)，这时我们称该算法的时间代价是g(n)。,问题的规模、空间单位和时间单位,问题的规模一般可以根据问题本身的提法确定。例如对n个记录进行排序，这里n即

11、可以作为问题的规模。 空间单位和时间单位没有统一的规定，通常取算法描述中的初等数据占用的空间和基本操作耗费的时间为单位。,大O表示法,在描述算法分析的结果时，人们通常采用大O表示法：说某个算法的时间代价(或者空间代价)为O(f(n)，如果存在正的常数c和n0，当问题的规模nn0后，该算法的时间(或空间)代价T(n)cf(n)。这时也称该算法的时间(或空间)代价的增长率为f(n)。,最坏情况下代价的数量级,每个算法的实际运行时的代价并不是固定不变的。由于不同的输入参数，可能使一个算法的实际代价出现很大差别。 要全面分析一个算法，应该考虑它在最坏情况下的代价、最好情况下的代价和平均情况下的代价等。

12、 本书不是专门讨论算法分析的教材，所以在分析算法时主要考虑它们在最坏情况下的代价，而且仅仅要求计算它们的数量级。,大O表示法,说某个算法的时间代价(或者空间代价)为O(f(n)，如果存在正的常数c和n0，当问题的规模nn0后，该算法的时间(或空间)代价T(n)cf(n)。 也称该算法的时间(或空间)代价的增长率为f(n)。 例如，如果有T(n) = 3n3，很容易证明T(n) = O(n3)。当然我们也可以证明T(n) = O(n4)。但从分析的精度来看，前一结论给出的是上确界(上界中最小的)，后者给出的仅是一般上界中的一个。,计算规则,1) 加法规则 T(n) = T1(n)+ T2(n)

13、= O(f1(n) + O(f2(n) = O(max(f1(n), f2(n) 2) 乘法规则 T(n) = T1(n)T2(n) = O(f1(n)O(f2(n)=O(f1(n)f2(n) 对于大O表示法，以非零正常数c形成的复杂性度量O(c)都 居于同一个量级，人们习惯把它们统一记为O(1)。,c log2 n n n log2 n n2 n3 10n,例子1：,考虑如下程序： action1(.); action2(.); 其中action1的时间代价是T1(n) = O(n2)， action2的时间代价是T2(n) = O(n3)。按照加法规则，计算整个程序的时间代价为： T(n)

14、 = T1(n) + T2(n) = O(max(n2, n3) = O(n3),例子2,for(i = 1; i = n; i+) action3(); /*假设action3()的执行中不改变i的值*/ 以操作action3的执行时间为单位，显然这里for循环的时间代价可以看作是T1(n) = O(n)；假设action3的时间代价是T2(n) = O(f(n)，根据乘法规则整个程序实际的时间复杂性应当是： T(n) = T1(n)T2(n) = O(n)O(f(n)= O(nf(n),二、线性表的顺序存储结构,序号 存储状态 存储地址 b 1 a1 b+k 2 a2 . . . . .

15、. b+(i-1)*k i ai . b+(n-1)*k n an / b+(maxlen-1)*k maxlen/ ,其中: b: 表的首地址(基地址), 即元素 a1 的首地址; K: 每个数据元素占有的存 储单元的个数; Maxlen:线性表的最大长度, 为某个常数。,二、线性表的顺序存储结构,插入一个元素 2 4 1720253540 1 2 3 4 5 6 7 8 9 | | 插入 8 n 2 4 1720253540 1 2 3 4 5 6 7 8 9 | | 插入 8 n 2 4 8 1720253540 1 2 3 4 5 6 7 8 9 | | 插入 8 之后 n,二、线性表

16、的顺序存储结构,算法分析 假设在线性表的第个位置插入一个元素的概率为Pj， 是线性表的长度, 1n,那么每插入一个元素所 需移动元素数目的期望值(平均数目)是： 其中，n-j+1 表示在第个元素之前插入一个新元素必须移动n-j+1个元素。假定在表的任意位置(1jn )插入元素的概率相等, 即1/n,那么移动元素的期望值为：,二、线性表的顺序存储结构,(2) 假设在线性表的第个位置删除元素的概率为, n是线性表的长度, 1n，那么每删除一个元素所需移动元素数目的期望值(平均数目)是: 其中，n-j 是表示删除表中第(1jn）个元素必须移动 n-j 个元素。假定在表中任意位置( 1jn )删除元素的概率相等，即1/n，那么移动元素的期望值为： 缺点：平均要移动表中约半数的元素。,二、线性表的顺序存储结构,顺序存储结构的评价 (1) 优点 a) 存取结构简单，存取任意元素的时间是一个常数，存取速度快 b) 不使用指针，存储密度大。 (2) 缺点 a) 需请求分配一个连续存储块； b) 插入可能发生溢出； c) 为了防止溢出，需保留一个较大的连续存储块，造成