数据结构(C语言版)唐国民版表示例.ppt

表 1-1 个人书库,返回,例1(1)求时间复杂度 (1) temp=i; i=j; j=temp; 解：T(n)=3 T(n)/1=3，说明T(n)和1数量级相同(同阶) 因此T(n)= O(1),(2)for （k=0;kn;k+) 比较语句执行n-0+1次 for (j=k;jn;j+) ck,j=akj+bkj; 解 T(n)=n+1+ + = n2 +3n+1 T(n)/ n2 =1，说明T(n)和n2数量级相同(同阶) T(n)=O(n2) 经验：由嵌套层数最深的循环语句的最内层语句决定,（3） FUNCTION fact(n:integer):integer; if (n1 T(n)= T(n-1)+O(1) =T(n-2)+2*O(1) =T(1)+(n-1)*O(1) =n*O(1) =O(n),返回,例2： 在数组A1n查找给定值K i:=n; while (i1) AND AiK DO i:=i-1; RETURN(i); 解 最好情况下，,其时间复杂度 T(n)=O(1) 最坏情况下，其时间复杂度 T(n)=O(n) 平均时间复杂度：所有可能的输入实例以等 概率出现的情况 T(n)= (1+2+.+n)/n=O(n),返回,广义表的建立,存储结构： #define elemtype char struct node1 int atom;/* atom是标志域，若为0，则表示为子表，若为1，则表 示为原子*/ struct node1 *link; /*link存放下一个元素的地址。*/ union struct node1 *slink; /slink域用来存放子表的指针 elemtype data; /*data域用来存放原子值*/ ds;,输入格式,广义表由键盘输入，全部为字母，输入格式为：元素之间用逗号分隔，表元素的起始符号分别为左右圆括号，空表在其圆括号内用“#”表示，最后用分号作为整个广义表的结束；,假定LS=(a,(),b,C(d,(e),则从键盘输入为： (a,(#),b,C(d,(e)； 链表建立算法：关键是对存储结构中的各个域进行赋值；,7.3.1深度优先搜索,深度优先搜索遍历： 假设给定图G的初态是所有顶点均未访问过，在G中任选一顶点vi为初始出发点，则深度优先搜索可定义如下： （1）访问出发点vi，并将其标记为已访问过。 （2）依次从vi出发搜索vi的每一个邻接点vj,若vj未曾访问过，则以vj为新的出发点继续进行深度优先搜索,直至图中所有和源点,例如，设x是刚访问过的顶点，按深度优先搜索方法，下一步将选择一条从x出发的未检测过的边(x，y)。 (1)若发现顶点y已被访问过，则重新选择另一条从x出发的未检测过的边。 (2)若发现顶点y未曾访问过，则沿此边从x到达y，访问y并将其标记为已访问过，然后从y开始搜索，直到搜索完从y出发的所有路径，才回溯到顶点x，然后再选择一条从x出发的未检测过的边。 (3)上述过程直至从x出发的所有边都已检测过为止。此时，若x不是初始出发点，则回溯到在x之前被访问过的顶点；若x是初始出发点，则整个搜索过程结束。 因此，若G是连通图，则从初始出发点开始的搜索过程结束，也就意味着完成了对图G的遍历。,3. 十字（正交）链表,特点 在行、列两个方向上，将非零元素链接在一起。克服三元组表在矩阵的非零元素位置或个数经常变动时的使用不便。 类型定义,思想：只要求出A中的每一列的第一个非零元在转置矩阵B中位置（即行号）即可。 若能在转置前求出矩阵A的每一列col（即B中每一行）的第一个非零元转置后在b.data中的正确位置potcol（0cola.cols），那么在对a.data的三元组依次作转置时，只要将三元组按列号col放置到b.datapotcol中，之后将potcol内容加1，以指示第col列的下一个非零元的正确位置。,十字链表的建立 (1)建立表头的循环链表： a.依次输入矩阵的行、列数和非零元素个数：m,n和t。 b.行、列链表共享一组表头结点，因此，表头结点的个数应该是矩阵中行、列数中较大的一个。假设用s 表示个数，即s=max（m，n）。 c.依次建立总表头结点（由hm指针指向）和s个行、列表头结点，并使用next域使s+1个头结点组成一个循环链表，总表头结点的行、列域分别为稀疏矩阵的行、列数目，s个表头结点的行列域分别为0。并且开始时，每一个行、列链表均是一个空的循环链表，即s个行、列表头结点中的行、列指针域rptr和cptr均指向头结点本身。,为了节省存储单元，记录每一列非零元个数的向量num可直接放入pot中，即上面的式子可以改为：potcol=potcol-1+potcol，其中1colacols 。 于是可用上面公式进行迭代，依次求出其他列的第一个非零元素转置后在b.data中的位置potcol。例如，给出的稀疏矩阵M，有： 每一列的非零元个数为 pot1=2 第0列非零元个数 pot2=1 第1列非零元个数 pot3=2 第2列非零元个数 pot4=2 第3列非零元个数 pot5= 0 第4列非零元个数 pot6=1 第5列非零元个数,每一列的第一个非零元的位置为 pot0=0 第0列第一个非零元位置 pot1=pot0+pot1=2 第1列第一个非零元位置 pot2=pot1+pot2=3 第2列第一个非零元位置 pot3=pot2+pot3=5第3列第一个非零元位置 pot4=pot3+pot4=7 第4列第一个非零元位置 pot5=pot4+pot5=7 第5列第一个非零元位置,十字链表的建立 (1)建立表头的循环链表： a.依次输入矩阵的行、列数和非零元素个数：m,n和t。 b.行、列链表共享一组表头结点，因此，表头结点的个数应该是矩阵中行、列数中较大的一个。假设用s 表示个数，即s=max（m，n）。 c.依次建立总表头结点（由hm指针指向）和s个行、列表头结点，并使用next域使s+1个头结点组成一个循环链表，总表头结点的行、列域分别为稀疏矩阵的行、列数目，s个表头结点的行列域分别为0。并且开始时，每一个行、列链表均是一个空的循环链表，即s个行、列表头结点中的行、列指针域rptr和cptr均指向头结点本身。,(2)生成表中结点：,依次输入t个非零元素的三元组（i,j,v），生成一个结点，并将它插入到第i行链表和第j列链表中的正确位置上，使第i个行链表和第j个列链表变成一个非空的循环链表。 在十字链表的建立算法中，建表头结点，时间复杂度为O(s)，插入t个非零元结点到相应的行、列链表的时间复杂度为O（t*s），故算法的总的时间复杂度为O(t*s)。,十字链表的建立,用十字链表实现稀疏矩阵相加运算 假设原来有两个稀疏矩阵A和B，如何实现运算A=A+B呢？假设原来A和B都用十字链表作存储结构，现要求将B中结点合并到A中，合并后的结果有三种可能： 1）结果为aij+bij； 2）aij（bij=0）； 3）bij（aij=0）。 由此可知当将B加到A中去时，对A矩阵的十字链表来说， 1)结点的v域值（aij+bij0）， 2)不变（bij=0）， 3)插入一个新结点（aij=0）， 4) 是删除一个结点（aij+bij=0）。,使用栈作为辅助数据结构来实现递归过程 DFS序列（深度优先搜索遍历序列）：对图进行深度优先搜索遍历时，按访问顶点的先后次序所得到的顶点序列。 DFS序列不唯一，它与初始出发点、存储结构及算法有关,具有5个顶点的无向图至少应有（ A ）条边才能确保是一个连通图。 A. 4 B. 5 C. 7 D.8,填空题 1.具有三个结点的二叉树有（ ）种不同的形态。 2.设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ） 。 3.从概念上讲，将树转化为二叉树的基本 目的是（ ） 。 4.一棵含有n个结点的k叉树，（ ）形态达到最大深度？（ ）形态达到最小深度？ 5.深度为h的完全二叉树至少有（ ）个结点，至多有（ ）个结点。,5,2h-1,采用二叉树的存储结构并利用二 叉树的已有算法解决树的有关问题,单支树,完全k叉树,2h-1,2h-1,关键字集：k0, k1, k2, k3, k4, k5, k6 h(key): 4, 6, 1, 4, 7, 6, 5,2,7,4,3,6,1,5,顺序查找的优点：对短表合适，方法简单 缺点：对长表不合适，查找速度慢 平均查找长度ASL： n：记录的个数 pi：查找第i个记录的概率( 不特别声明时认为等 概率pi =1/n ) ci：找到第i个记录所需的比较次数,例：设哈希函数h(k)=k mod 13; 则键值为 13，41，15，44，06，68，12，25，38，64，19，49的开哈希表如下：,13 ,15,41 ,68 ,44 ,06,19 ,49 ,64,38,12,25 ,0,1,2,3,4,5,6,7,8,9,10,11,12,ht,哨兵/监视哨的作用,简化边界条件的测试，提高算法时间效率。 性能分析 最好情况(原始数据按正序即非递减序排列) 第i趟的关键字比较次数 :1 总关键字比较次数:n-1 第i趟记录移动次数:0 总的记录移动次数:0 时间复杂度:0（n） 最坏情况(原始数据按逆序即非递增序排列) 第i趟的关键字比较次数 :i 总关键字比较次数:(n+2)(n-1)/2 第i趟记录移动次数: i+2 总的记录移动次数:2(n-1) 时间复杂度:0（n）Cmax=(n+2)(n-1)/2 Mmax=(n+4)(n-1)/2 随机情况 Cavg=(Cmin+ Cmax)/2n2/4 Mavg n2/4 时间复杂度O(n2) 空间复杂度O(1),首先看问题2如何解决 调整方法 将堆顶元素和堆的最后一个元素位置交换； 然后以当前堆顶元素和其左、右子树的根结点进行比较(此时，左、右子树均为堆)，并与值较大的结点进行交换； 重复，继续调整被交换过的子树，直到叶结点或没进行交换为止。 称这个调整过程为“筛选“。 例如：设有关键字13，38，27，49，76，65,49,97，按初始次序构成一棵完全二叉树，形成一个堆如图,例：,直接插入排序的基本操作是比较和移动元素，而且二者的大致次数相等。最坏情况下是原序列恰好从大到小排列，此时基本操作需要大约n2/2次。而平均情况下，基本操作约为n2/4次，故时间复杂度为O(n2)。我们有下面这个表：,直接插入排序是稳定的排序方法。,ORG 8000H LJMP START ORG 8030H START: ORL P1,#0FH ；P1口的低四位置“1”，定义为输入； 读入开关的状态 LOOP: MOV A,P1 SWAP A ；交换A的高低四位， 以便将读入开关的状态送入P1口的高四位 ORL A,#0FH ；A的低四位置“1”，以便将P1口的低四位定 义为输入 ；为下一次重 新读开关的状态作准备； MOV P1,A；将A的值送P1口显示，输出P1口的高四位 SJMP LOOP END,程序,ORG 8000H LJMP START ORG 8030H START: ORL P1,#0FH ；P1口的低四位置“1”，定义为输入； LOOP: MOV A,P1 SWAP A ORL A,#0FH MOV P1,A SJMP LOOP END,程序,地址错误,中断入口地址 外部中断0 8003H 外部中断1 8013H 定时器/计数器0 800BH 定时器/计数器1 801BH 74LS244 0CFFFH 74LS273 0CFFFH 错误：MOV DPTR, MOVX A,DPTR,0CFFFH,程序错误