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

 表 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++) c[k,j]=a[k][j]+b[k][j]; [解] 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 (n=1) then fact:=1 else fact:=n*fact(n-1) ENDF; {fact} [解] T(n)= O(1) n?1 T(n-1)+O(1) 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： {在数组A[1..n]查找给定值K} i:=n; while (i?1) AND A[i]?K 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深度优先有哪些信誉好的足球投注网站 3. 十字（正交）链表 特点 在行、列两个方向上，将非零元素链接在一起。克服三元组表在矩阵的非零元素位置或个数经常变动时的使用不便。 类型定义 思想：只要求出A中的每一列的第一个非零元在转置矩阵B中位置（即行号）即可。 若能在转置前求出矩阵A的每一列col（即B中每一行）的第一个非零元转置后在b.data中的正确位置pot[col]（0≤cola.cols），那么在对a.data的三元组依次作转置时，只要将三元组按列号col放置到b.data[pot[col]]中，之后将pot[col]内容加1，以指示第col列的下一个非零元的正确位置。 十字链表的建立 (1)建立表头的循环链表： a.依次输入矩阵的行、列数和非零元素个数：m,n和t。 b.行、列链表共享一组表头结点，因此，表头结点的个数应该是矩阵中行、列数中较大的一个。假设用s 表示个数，即s=max