《数据结构(C语言版)唐国民版表示例.ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言版)唐国民版表示例.ppt（33页珍藏版）》请在金锄头文库上搜索。
1、表1-1个人书库返回例例1(1)1(1)求时间复杂度求时间复杂度(1) temp=i;(1) temp=i; i=j; i=j; j=temp; j=temp; 解解 ：T(n)=3T(n)=3 T(n)/1=3T(n)/1=3，说明T(n)和1数量级相同(同阶)因此因此T(n)= O(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+1T(n)/n2=1，说明T(n)和n2数量级相同(同阶)T(n)=O(n2)经验：由嵌套层数最深的循环语句的最内层语句决定（3）FUNCTI
2、ONfact(n:integer):integer;if(n1T(n)=T(n-1)+O(1)=T(n-2)+2*O(1)=T(1)+(n-1)*O(1)=n*O(1)=O(n)返回例2：在数组A1.n查找给定值Ki:=n;while(i1)ANDAiKDOi:=i-1;RETURN(i);解最好情况下，,其时间复杂度T(n)=O(1)最坏情况下，其时间复杂度T(n)=O(n)平均时间复杂度：所有可能的输入实例以等概率出现的情况T(n)=(1+2+.+n)/n=O(n)返回广义表的建立存储结构：#defineelemtypecharstructnode1int atom;/* atom是 标
3、志 域 ， 若 为 0， 则 表 示 为 子 表 ， 若 为 1， 则 表 示为原子*/structnode1*link;/*link存放下一个元素的地址。*/unionstructnode1*slink;/slink域用来存放子表的指针elemtypedata;/*data域用来存放原子值*/ds;输入格式广义表由键盘输入，全部为字母，输入格式为：元素之间用逗号分隔，表元素的起始符号分别为左右圆括号，空表在其圆括号内用“#”表示，最后用分号作为整个广义表的结束；假定LS=(a,(),b,C(d,(e),则从键盘输入为：(a,(#),b,C(d,(e)；链表建立算法：关键是对存储结构中的各个域
4、进行赋值；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
5、出发的所有路径，才回溯到顶点x，然后再选择一条从x出发的未检测过的边。(3)上述过程直至从x出发的所有边都已检测过为止。此时，若x不是初始出发点，则回溯到在x之前被访问过的顶点；若x是初始出发点，则整个搜索过程结束。因此，若G是连通图，则从初始出发点开始的搜索过程结束，也就意味着完成了对图G的遍历。3. 3. 十字（正交）链表十字（正交）链表特点 在行、列两个方向上，将非零元素链接在一起。克服三元组表在矩阵的非零元素位置或个数经常变动时的使用不便。类型定义ijv/nextcptrrptr列指针域（cptr）：用来指向本列中下一个非零元素行指针域（rptr）：用来指向本行中下一个非零元素同一行的
6、非零元通过向右的rptr指针链接成一个带表头结点的循环链表。同一列的非零元也通过向下的cptr指针链接成一个带表头结点的循环链表。思想：只要求出A中的每一列的第一个非零元在转置矩阵B中位置（即行号）即可。若能在转置前求出矩阵A的每一列col（即B中每一行）的第一个非零元转置后在b.data中的正确位置potcol（0cola.cols），那么在对a.data的三元组依次作转置时，只要将三元组按列号col放置到b.datapotcol中，之后将potcol内容加1，以指示第col列的下一个非零元的正确位置。v十字链表的建立(1)建立表头的循环链表：a.依次输入矩阵的行、列数和非零元素个数：m,n
7、和t。b.行、列链表共享一组表头结点，因此，表头结点的个数应该是矩阵中行、列数中较大的一个。假设用s 表示个数，即s=max（m，n）。c.依次建立总表头结点（由hm指针指向）和s个行、列表头结点，并使用next域使s+1个头结点组成一个循环链表，总表头结点的行、列域分别为稀疏矩阵的行、列数目，s个表头结点的行列域分别为0。并且开始时，每一个行、列链表均是一个空的循环链表，即s个行、列表头结点中的行、列指针域rptr和cptr均指向头结点本身。Hm34000 00 00 00 00 00 00 000080- 50040 07为了节省存储单元，记录每一列非零元个数的向量num可直接放入pot中
8、，即上面的式子可以改为：potcol=potcol-1+potcol，其中1colA交换A的高低四位A的低四位置“1”将A的值送P1口显示ORG8000HLJMPSTARTORG8030HSTART:ORLP1,#0FH；P1口的低四位置“1”，定义为输入；LOOP:MOVA,P1SWAPAORLA,#0FHMOVP1,ASJMPLOOPEND程序开始P1.0-P1.3置“1”读入K1-K4的状态-A交换A的高低四位A的低四位置“1”将A的值送P1口显示程序框图地址错误中断入口地址外部中断08003H外部中断18013H定时器/计数器0800BH定时器/计数器1801BH74LS2440CFFFH74LS2730CFFFH错误：MOVDPTR,MOVXA,DPTR0CFFFH程序错误例子.MOVDPTR,D_TABLP1:MOVA,R1MOVCA,A+DPTR.X 示例示例 R(0) R(-4) R(8) R(1) R(-4) R(-6) n=6 i=1 0 -4 8 1 -4 -6 i=2 -4 0 8 1 -4 -6 i=3 -4 0 8 1 -4 -6 i=4 -4 0 1 8 -4 -6 i=5 -4 -4 0 1 8 -6 i=6 -6 -4 -4 0 1 8 显然，显然， 每次使有序区增加一个记录每次使有序区增加一个记录稳定排序
