数据结构第1章绪论.ppt

算法性能评价 例如： 下列程序段： for (i=1; i= n; i++) for (j=i; j= n; j++) x++; 语句x++的执行频度为 n+(n-1)+(n-2)+…+3+2+1 =n(n+1)/2 而该语句执行次数关于n的增长率为n2, 即时间复杂度为O(n2)。 算法性能评价 最坏时间复杂度：有时，算法中基本操作重复执行的次数随问题的输入不同而不同，通常分析最坏情况下的时间复杂度。 例，顺序查找算法 Status search ( int a[ ] ，int n ，int e ) { } for ( i = 0 ；i =n - 1 ；++i ) if ( e == a[i] ) return TRUE ； return FALSE ； 最好 1 次比较，最坏 n 次比较，平均 (n+1)/2 次比较。 算法性能评价 算法的空间复杂度 关于算法的存储空间需求，类似于算法的时间复杂度， 我们采用空间复杂度作为算法所需存储空间的量度，记作： S(n)=O(f(n)) 课程的基本结构 数据结构 基础数据结构 应用数据结构 非线性结构 线性结构 线 性 表 栈 队 列 串 数 组 广 义 表 树 二 叉 树 图 查 找 内 部 排 序 外 部 排 序 文 件 动 态 存 储 管 理 作业 《数据结构题集》 P7 ：（1.3、1.8、1.9、1.16） 例题 例1：设逻辑结构图如下，试给出其数据结构表示。 a b c d e f 数据结构定义为： Data_Structure = (D,S) 其中 D={a,b,c,d,e,f} S={R} R={(a,b),(a,c),(c,d),(c,e), (c,f),(d,f)} 例题 例2：设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数，写出其时间复杂度。 x=0; for( i=1; in ; i++) for( j=1; j=n-i ; j++) x++; 例题 例3：计算机执行下面的语句时，语句S的执行次数为多少？ for( i=1; in-1 ; i++) for( j=n; j=i ; j--) S; 例题 例4：试说明下列计算过程是否是一个算法？ （1）开始； （2）n = 0; （3）n++； （4）重复（3）； （5）结束； 不具备算法的有穷性，不是一个算法。 存储结构（物理结构） 元素n …….. 元素i …….. 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储 顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。 存储结构（物理结构） 非顺序存储结构（链式存储结构）：借助指示元素存储地址的指针表示数据元素间的逻辑关系。 1536 元素2 1400 元素1 1346 元素3 ∧ 元素4 1345 h h 存储结构（物理结构） 例：用顺序存储法和链式存储法表示下面的学生表。 学号 姓名 性别 班号 1 张斌 男 9901 8 刘丽 女 9902 34 李英 女 9901 20 陈华 男 9902 12 王奇 男 9901 26 董强 男 9902 5 王萍 女 9901 存储结构（物理结构） 用顺序存储方法存放学生表的结构体定义为： struct Stud { int no; /*学号*/ char name[8]; /*姓名*/ char sex[2]; /*性别*/ char class[4]; /*班号*/ } Studs[7]={ {1,“张斌”,“男”,“9901”}, …, {5,王萍,女,9901} }; 存储结构（物理结构） 结构体数组Studs各元素在内存中按顺序存放,即第i(1≤i≤6)个学生对应的元素Studs[i]存放在第i+1个学生对应的元素Studs[i+1]之前,Studs[i+1]正好在Studs[i]之后。 1 张斌 男 9901 8 刘丽 女 9902 34 李英 女 9901 20 陈华 男 9